Engineering Optimization: Theory and Practice, Fourth Edition

718 Modern Methods of Optimization

Step 4: Test for the convergence of the process. The process is assumed to have con-

verged if allNants take the same best path. If convergence is not achieved,

assume that all the ants return home and start again in search of food. Set the

new iteration number asl=l+1, and update the pheromones on different

arcs (or discrete values of design variables) as

τi(l)j =τij( ldo )+

∑

k

τi(k)j (13.42)

whereτij(o ld)denotes the pheromone amount of the previous iteration left after

evaporation, which is taken as

τij ld(o ) =( 1 −ρ)τi(lj−^1 ) (13.43)

andτi(k)j is the pheromone deposited by the best antkon its path and the

summation extends over all the best antsk(if multiple ants take the same best

path). Note that the best path involves only one arcij(out ofppossible arcs)

for the design variablei. The evaporation rate or pheromone decay factorρis

assumed to be in the range 0.5 to 0.8 and the pheromone depositedτi(k)j is

computedusing Eq. (13.37).

With the new values ofτi(l)j , go to step 2. Steps 2, 3, and 4 are repeated until

the process converges, that is, until all the ants choose the same best path.

In some cases, the iterative process is stopped after completing a prespecified

maximum number of iterations(lmax).

Example 13.5 Find the minimum of the functionf (x)=x^2 − 2 x− 1 1 in the range

(0, 3) using the ant colony optimization method.

SOLUTION

Step 1: Assume the number of ants is N=4. Note that there is only one design

variable in this example(n= 1 ). The permissible discrete values ofx=x 1

are assumed, within the range ofx 1 , as (p= 7 ):

x 11 = 0. 0 ,x 12 = 0. 5 , x 13 = 1. 0 , x 14 = 1. 5 , x 15 = 2. 0 , x 16 = 2. 5 ,x 17 = 3. 0

Each ant can choose any of the discrete values (paths or arcs) x 1 j,

j= 1 , 2 ,... ,7 shown in Fig. 13.4. Assume equal amounts of pheromone

along each of the paths or arcs(τ 1 j) hown in Fig. 13.4. For simplicity,s

τ 1 j= is assumed for 1 j= 1 , 2 ,... ,7.

Set the iteration number asl=1.

Step 2: For any antk, the probability of selecting path (or discrete variable)x 1 j is

given by

p 1 j=

τ 1 j

∑^7

p= 1

τ 1 p

=

1

7