Engineering Optimization: Theory and Practice, Fourth Edition

13.5 Ant Colony Optimization 719

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

Home Food (Destination)

Figure 13.4 Possible paths for an ant (possible discrete values ofx≡x 1 ).

To select the specific path (or discrete variable) chosen by an ant using a

random number generated in the range (0, 1), cumulative probability ranges are

associated with different paths of Fig. 13.4 as (using roulette-wheel selection

process in step 3):

x 11 =

(

0 ,^17

)

=( 0. 0 , 0. 1428 ), x 12 =

( 1

7 ,

2

7

)

=( 0. 1428 , 0. 2857 ),

x 13 =

( 2

7 ,

3

7

)

=( 0. 2857 , 0. 4286 ),

x 14 =

( 3

7 ,

4

7

)

=( 0. 4286 , 0. 5714 ), x 15 =

( 4

7 ,

5

7

)

=( 0. 5714 , 0. 7143 ),

x 16 =

( 5

7 ,

6

7

)

=( 0. 7143 , 0. 8571 ),

x 17 =

( 6

7 ,^1

)

=( 0. 8571 , 1. 0 )

Step 3: Generate four random numbersri(i= 1 , 2 , 3 , 4 )inthe range (0, 1), one for
each ant asr 1 = 0. 3122 , r 2 = 0. 8701 , r 3 = 0. 4 729, andr 4 = 0. 6 190. Using the
cumulative probability range (given in step 2) in which the value ofrifalls,
thediscrete 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 17 = 3. 0 ;ant 3 :x 14 = 1. 5 ;ant 4 :x 15 = 2. 0

Theobjective 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 17 ) =f( 3. 0 )= − 8. 0 ;

ant 3 :f 3 = f(x 14 )=f( 1. 5 )= − 11. 75 ;ant 4 :f 4 = f(x 15 ) =f( 2. 0 )= − 11. 0

It can be seen that the path taken by ant 1 is the best one (with minimum value

of the objective function):xbest=x 13 = 1. 0 ,fbest=f 1 = − 12 .0; and the path

taken by ant 2 is the worst one (with maximum value of the objective function):

xworst=x 17 = 3. 0 ,fworst=f 2 = − 8. 0.