Abstract:

In this paper

we will be presenting about an overview and evolution of ant algorithms which

was observed from ant colonies. The types of ant algorithms like Ant System,

Ant colony System, Max-Min Ant System are disclosed and they are interpreted

through the flow chart. Comparative study is done between ant algorithms and it

is implemented in Travelling Salesman Problem, the better suited algorithm is

derived.

Introduction:

Ant Colony Optimization:

Evolution:

Ant System Algorithm(AS):

Ant system was

originally the term used to refer to a range of ant based algorithm where the

specific algorithm implementation was referred to as ant cycle. The so called

Ant Cycle Algorithm is canonically referred to as Ant System. The ant algorithm

is the baseline for ant colony optimization method. The first ACO algorithm was

proposed in the year 1992.The ant system algorithm is inspired by the foraging

behaviour of ants especially the pheromone communication between ants and

regarding a good path between the colony and the food resource in the

environment. This mechanism is called stigmergy.

Pheromone values are

updated by all the ants that have completed the tour.

?ij ?

(1 ? ?) · ?ij + Pm k=1 ?? k ij

where

? is the

evaporation rate

m is the number of

ants

?? k ij is

pheromone quantity laid on edge (i, j) by the k th ant

?? k i,j = ( 1/Lk

if ant k travels on edge i, j 0 otherwise where Lk is the tour length of the k

th ant.

Ant Colony System Algorithm:

Ant Colony System algorithm is an example of an ant colony

optimization method. From the field of Swarm intelligence,Meta heuristic and

computational intelligence. Ant colony system is an extension to the ant system

algorithm and it is related to other ant colony optimization.

?ij ? (1 ? ?) x ?ij + ? x ? ?ij

where

s?ij represents the

pheromone for the component (graph edge) (i,j),

? is the decay

factor,

and ? ?ij is

the maximizing solution cost for the best solution found so far if the

component ij is used in the

globally best known solution, otherwise it is 0.

MAX MIN ANT

SYSTEM:

Max min ant system is to combine an improved exploitation of the

best solutions found during the search with an effective mechanism for avoiding

early search stagnation. max min ant which has been specifically developed to

meet these requirements differ in three accepts in AS.

i). This ant may be the one which found the best solution in

the current iteration (iteration-best ant) or the one which found the best

solution from the beginning of the trial (global-best ant).

ii)To avoid stagnation of the search the range of possible

pheromone trails on each solution component is limited to an interval (?min ?max + ).

iii) we initialize the pheromone trails to ?max, achieving

in this way a higher exploration of solutions at the start of the algorithm.

The algorithm constructs a solution by adding solution components in the list

of components that specify partial solutions, until an entire solution is

constructed. The probability of selecting solution component c(i) is given in

(1). Index i denotes a solution construction step, ?c(i) is the trail value

associated with component c(i), and ?c(i) is the heuristic value associated

with c(i). In step i, a component is selected from Li , a set of components.

Parameters ? and ? are used to maintain balance between trails and heuristic

values.

pc(i)

After the population of solutions is constructed the best

solution is found and trails are updated. The update process includes trail

evaporation (2) for all trails, and trail reinforcement (3) for all components

included in the iteration or global best solution.

?c (j)=(1-P). ?c(j)