Abstract:

This paper will present an overview of ant

algorithms that is algorithms for colony optimization that took insight which

was observed from ant colonies .We are going to discuss about the findings on

real ants and Ant Colony Optimization (ACO) algorithm is applied to wide range

of problems like Travelling Salesman , Job-Shop Scheduling ,Vehicle Routing.

Introduction:

Ant Colony Optimization is a probabilistic technique which is used for

searching optimal path in the graph based on behaviour of ants seeking a path

between their colony and source of food. It is a Meta-heuristic optimization.

It was first proposed by Marco Dorigo in 1992 as a multi-agent approach to

difficult combinatorial optimization problems such as Travelling salesman

problem (TSP), Quadratic assignment problem (QAP).

The ACO metaheuristic consists of group of

artificial ants with the characteristics to search good solutions to discrete

optimization problem. An Ant algorithm was inspired by the observation of real

ant colonies, Ants are social insects (i.e.) insects that lives in colonies and

whose behavior is directed more to the survival of the colony as a whole than

to that of a single individual component of the colony. An important and

interesting behavior of ant colonies is that their behavior and in particular,

how ants can find the shortest paths between food sources and their nest.

While walking from food sources to the

nest and vice versa, ants deposit on the ground a substance called pheromone,

forming in this way a pheromone trail. Ants can smell these this chemical and

when choosing their way tend to choose, in probability paths marked by them and

allows them to travel from food source to their colonies. Other ants from the

colony follow their nestmates to follow their paths to the food source. This is

how shortest path is emerged for their food hunting.

The

?rst ants to arrive at the food source are those that took the two shortest

branches, so that, when these ants start their return trip, more pheromone is

present on the short branch than on the long branch, stimulating successive

ants to choose the short branch.

Ant

Optimization Algorithms:

Ant Colony Optimization Algorithm:

1 procedure ACO Meta heuristic()

2 while (termination criterion not

satisfied)

3 schedule activities

4 ants generation and activity();

5 pheromone evaporation();

6 daemon actions(); foptionalg

7 end schedule activities

8

end while

9 end procedure

10 procedure ants generation and

activity()

11 while (available resources)

12 schedule the creation of a new ant();

13 new active ant();

14 end while

15 end procedure

16 procedure new active ant() fant

lifecycleg

17 initialize ant();

18 M = update ant memory();

19 while (current state 6= target state)

20 A = read local ant-routing table();

21 P = compute transition probabilities(A;

M; problem constraints);

22 next state = apply ant decision

policy(P; problem constraints);

23 move to next state(next state);

24 if (online step-by-step pheromone

update)

25 deposit pheromone on the visited arc();

26 update ant-routing table();

27 end if

28 M = update internal state();

29 end while

30 if (online delayed pheromone update)

31 evaluate solution();

32 deposit pheromone on all visited

arcs();

33

update ant-routing table();

34 end if

35 die();

36 end procedure

Ant

System(AS):

First ACO

algorithm to be proposed (1992) 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 System Algorithm:

1: for each colony do

2:

for each ant do

3: generate route

4: evaluate route

5:

evaporate pheromone in trails

6:

deposit pheromone on trails

7: end for

8: end for

Ant Colony System(ACS):

First major

improvement over Ant System Differences with Ant System:

1 Decision

Rule – Pseudorandom proportional rule

2 Local

Pheromone Update

3 Best only

offline Pheromone Update

Ants in ACS

use the pseudorandom proportional rule Probability for an ant to move from city

i to city j depends on a random variable q uniformly distributed over 0, 1,

and a parameter q0. If q ? q0, then, among the feasible components, the

component that maximizes the product ?il? ? il is chosen, otherwise the same

equation as in Ant System is used. This rule favours exploitation of pheromone

information

Diversifying

component against exploitation: local pheromone update. The local pheromone

update is performed by all ants after each step. Each ant applies it only to

the last edge traversed: ?ij = (1 ? ?) · ?ij + ? · ?0 where ? ? (0, 1 is the

pheromone decay coefficient ?0 is the initial value of the pheromone

Best only

offline pheromone update after construction Offline pheromone update equation

?ij ? (1 ? ?) · ?ij + ? · ?? best ij where ? best ij = ( 1/Lbest if best ant k

travels on edge i, j 0 otherwise Lbest can be set to the length of the best

tour found in the current iteration or the best solution found since the start

of the algorithm.

Ant Colony System Algorithm:

1:

for each colony do

2:

for each ant do

3:

generate route

4:

evaluate route

5: evaporate pheromone in all trails (? rate)

6:

deposit pheromone on all trails

7:

end for

8: evaporate pheromone in best global route (?2 rate)

9:

deposit pheromone on best global route

10:

end for

Max-Min Ant System (MMAS):

Developed

by St¨utzle and Hoos (1996), as another variation for the TSP, the MMAS

algorithm shows di?erences in the steps of pheromone deposition and

evaporation, that occur only after the i-th ant for each colony stablish its

trail.

Differences

with Ant System: 1 Best only offline Pheromone Update 2 Min and Max values of

the pheromone are explicitly limited ?ij is constrained between ?min and ?max

(explicitly set by algorithm designer). After pheromone update, ?ij is set to

?max if ?ij > ?max and to ?min if ?ij