Particle Swarm Optimization and Ant Colony Optimization -by B.Siri, M.Aamani, M.Aiswarya, Tanuja Ananthaneni(Group 15)

Abstract:

Optimization theory and methods have been applied in many fields to handle various practical problems. In light to the advancing computing systems, optimization techniques have become increasingly important and popular in different engineering applications. Swarm intelligence is one of the many fields which uses optimization to find effective solutions. In this project we attempt to understand two major optimization techniques in swarm intelligence namely Particle swarm optimization (PSO) and Ant colony optimization (ACO). We also try to compare the algorithms and find the probability of a node being a cluster head by using both the algorithms (PSO and ACO).

Introduction:

Everyone wants to use their resources as effectively as possible. Optimization is a process by which we bring out the best solution with least use of resource investment. It means to find a process to maximize or minimize the value of an objective function. there are many optimization techniques. Among them, Bio-inspired optimization techniques can be more effective compared to other optimization techniques and are widely accepted due to the same fact. As the name suggests Bio-inspired optimization techniques are inspired from the nature and behaviour of biological societies. Swarm Intelligence based optimization techniques which are a subset of these Bio-inspired techniques is based on collective social behaviour of organisms. Ant colony optimization which is based on behaviour of ants and particle swarm optimization which is based on flocking of birds, schools of fish etc. are two most famous swarm intelligence based optimization algorithms.

PARTICLE SWARM OPTIMIZATION

Particle swarm optimization is a bio-inspired stochastic technique. Stochastic means to have a random probability distribution or pattern which could be analysed statistically but may not be predicted precisely. PSO was developed by James Kennedy and Russ Eberhart in 1995. In PSO, the search of the solution takes place by a swarm of particles. Each particle in the swarm moves according to both the directions of its personal best (pbest or local best) and global best (gbest) of the swarm. This process will be iterative and continuously updating pbest and gbest with each iteration.

Each particle has two characteristics:

1.position

2. velocity

The velocity is influenced by 3 terms:

Inertia term
Personal influence( pbest)
Social influence( gbest)

This velocity is used to calculate the current position term which in turn used to calculate the current fitness equation.

If there are N_p particles and we have t iterations, then

And then the fitness function is compared with previous lbest , gbest and gets updated.

Pseudo code for particle swarm optimization is as follows :

//Initialize the particles of the swarm

//initialize the characteristics of particles randomly

//Evaluate particle fitness function

// do While (stopping criterion is not met)

//for every particle

//calculate fitness value

// if fitness is better than fitness value of previous pbest

//compare and update

//end

//let the particle with best fitness value as gbest

//for each particle

//calculate particle velocity

// update particle velocity

//end.

// While (stopping criterion is not met)

ANT COLONY OPTIMIZATION

Ant colony optimization (ACO) is a bio inspired and population-based meta-heuristic technique. A meta-heuristic is a high-level problem-independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. A heuristic technique is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect or rational, but which is nevertheless sufficient for reaching an immediate, short-term goal. The concept of ant colony optimization was developed and conceptualized by Marco Dorigo in 1992. The main idea of ant colony optimization is to forge the behaviour of ants in order to find the shortest distance between a source and a destination. The algorithm is based on a set of ants, where each ant is moving from one place to another in search of food. Updating the pheromone values by all the ants which have completed the tour is the main characteristic of the ACO.

The update with regard to pheromone for T_ij for joining places i and j is as follows:
Each move is based on local probability value as-

After the ants end the tours, the trail levels are updated based on the tour length of the previous solution and evaporation based on the following formulas:

The iteration process continues to take place until a certain criteria like fixed number of iterations, a limited amount of CPU time has elapsed or when required solution quality has been achieved.

Components of Ant Colony Optimization (ACO)-

1. A set of concurrent computing agents (ANTS).

2. Each ant moves based on stochastic local decision based on-

A) Trails (globally affected).

B) Attractiveness (locally affected).

3. Global mechanisms

A) Trail evaporation.

B) Daemon activities.

4. Ants iteratively construct the solutions by local choices from state i to state j.

5. At each step σ, ant k computes a set of feasible expansions A_k^σ(i) from its state.

6. Probability of moving from state i to state j depends on

A) Attractiveness n_ij of the move.

B) Trail level T_ij of the move.

Pseudo code for ant colony system is as follows-

//Initialization: Initialize T_ij and n_ij values.

//construction:

for each ant k(in state i)do:

repeat

choose the state j to move to(with probability)

Append the chosen move to tabu_k.

Until ant k has completed its solution

//Trail Update:

for each ant move(i j) do:

compute ∆T(i j)

update trail matrix

//Termination

If not end of test, go to step 2.

General differences between PSO and ACO :

· Robust nature of ACO is better than Robust nature of PSO

· ACO coding is somewhat complicated, not as straight forward as PSO

· Computation time of PSO is less than ACO

· PSO has less algorithm parameters to handle than ACO.

In this project we aim to simulate the probability of a node being a cluster head by using the above discussed algorithms. In wireless sensor networks groups of nodes form clusters for more efficient functioning and one of the node in the cluster becomes the cluster head. The cluster head collects the required data from other nodes in the cluster and sends it to the base station which is otherwise known as the sink. The cluster head must always be in active state where as the other nodes can switch to sleep mode, thus the energy consumed by the cluster head is greater than the energy consumed by other nodes in the network. The lifetime of a network is said to be completed when the first node dies. So, in order to increase the life time of the network the cluster head must be changed periodically. As transmitting the data is the task which consumes the most energy we can also design the algorithm to suppress the transfer of unwanted data for the efficient use of the constrained amount of energy available.

The above pictures are matlab simulated graphs which tell us about the residual energy of the two nodes taken
after each iteration. In figure a both the nodes start with same amount of residual energy and node 1 is the
cluster head which consumes greater amount of energy compared to node 2. It can be seen that node 1
exhausts all its energy by 400 cycles. Thus the lifetime of the network only lasted for 400 iterations. Where as in
figure b node 1 remains the cluster head for iterations 0-249 and then gives the cluster head position to node b
for 250-500 cycles. The lifetime of the network in this case is 500 cycles. Thus we can say that the periodic
changing the cluster head increases the lifetime of the network.

In literature, two methods have been proposed for changing the position of cluster head to a new node. The
first method is called time-driven cluster head selection method. According to this method the sensor node
takes the role of a cluster head for a predetermined time period. The second method is energy-driven cluster
head selection method. This method takes into account the residual energy of the sensor nodes and changes
the cluster head node when a predetermined amount of energy is consumed.

FUTURE WORK-

Taking assumptions that the nodes are stationary and assumptions about the starting level of energy of the

nodes, their weights and energy functions into consideration we aim to calculate the probability of a node
being the cluster head by considering parameters like the amount of residual energy left in the node,
throughput of the node etc.