Engineering Optimization: Theory and Practice, Fourth Edition

13.5 Ant Colony Optimization 721

value assumed (or the path selected in Fig. 13.4) by different ants can be seen

to be

ant 1 :x 13 = 1. 0 ;ant 2 :x 16 = 2. 5 ;ant 3 :x 11 = 0. 0 ;ant 4 :x 13 = 1. 0

This shows that two ants (probabilistically) selected the pathx 13 due to higher

pheromone left on the best path(x 13 ) ound in the previous iteration. Thef

objective function values corresponding to the paths chosen by different ants

are given by

ant 1 :f 1 = f(x 13 ) =f( 1. 0 )= − 12. 0 ;ant 2 :f 2 = f(x 16 ) =f( 2. 5 )= − 9. 75 ;

ant 3 :f 3 = f(x 11 )=f( 0. 0 )= − 11. 0 ;ant 4 :f 4 = f(x 13 ) =f( 1. 0 )= − 12. 0

It can be seen that the path taken by ants 1 and 4 is the best one with

xbest=x 13 = 1. 0 andfbest=f 1 =f 4 = − 12. 0

and the path taken by ant 2 is the worst one with

xworst=x 16 = 2. 5 andfworst=f 2 = − 9. 75

Now we go to step 4 to update the pheromone values on the various paths.
Step 4: Assuming that the ants return home and start again in search of food, we set
the iteration number asl=3. We need to update the pheromone array as

τ 1 (j^3 )=τ 1 (jo ld)+

∑

k

τ(k) (E 2 )

where

∑

k

τ(k)is the pheromone deposited by the best antkand the summation

extends over all the best antsk(if multiple ants take the best path). In the

present case, there are two best ants,k=1 and 4, which used the pathx 13.

Thus the value of

∑

k

τ(k)can be determined in this case as

∑

k

τ(k)= τ(k=^1 )+ τ(k=^4 )=

2 ςfbest

fworst

=

( 2 )( 2 )(− 12. 0 )

(− 9. 75 )

= 4. 9231

where the scaling parameterςis assumed to be 2. Using a pheromone decay

factor ofρ= 0 .5 in Eq. (13.43),τ 1 ( ldoj )can be computed as

τ 1 ( ldoj )=( 1. 0 − 0. 5 )τ 1 (j^2 )= 0. 5 ( 0. 5 )= 0. 25 ;j= 1 , 2 , 4 , 5 , 6 , 7

Thus Eq. (E 2 ) gives

τ 1 (j^3 )= 4. 0 + 4. 9231 = 8 .9231 forj=3 and

τ

( 3 )

1 j =^0.^25 forj=^1 ,^2 ,^4 ,^5 ,^6 ,^7

With this, we go to step 2.