Ant Colony Optimization (Bio Inspired Algorithm) by Ing.Lenka S., PhD

Ant Colony Optimization Biology inspired optimization algorithm including example and quiz.

1. BiologicallyInspired
Algorithms
Ant ColonyOptimization
Ing. Lenka Skanderová, Ph.D.

2. Historyand Use
•Introducedin 1992
•Author: Marco Doringo
•Basedon thebehavioroftherealant colonies
•Originallyappliedto TravellingSalesmanProblem(TSP)
•Developedto solvediscreteoptimizationproblems
[1]
•History
•Principle
•Example
1/21

3. Inspirationby Real Ants
•Each ant producespheromoneswhiletravellingfromthenestto food and
fromtheplace withthefood to thenest→type ofcommunicationwith
theotherantsfromthecolony
•Themovementoftheantsisrandom, however, duringtime, theirdecision
isinfluencedby thepheromones
•On theshortestpath, thepheromonesare accumulated
•Importantfeatureofpheromones: vaporization
[1]
•History
•Principle
•Example
2/21

4. Principle
•Thanks to vaporization, thepathswhichare not theshortestare not so
attractivefortheants
•In theTSP:
•Theprobability thatanant �atnode �willchoosethedestination
node �is
�
��,�=൞
??????�,�
�
??????�,�
�
σ
�∈�
??????
??????�,�
�
??????�,�
�
,����????????????
�
0,��ℎ��??????���
[1]
•History
•Principle
•Example
3/21

5. Principle
�
��,�=൞
??????�,�
�
??????�,�
�
σ
�∈�
??????
??????�,�
�
??????�,�
�
,����????????????
�
0,��ℎ��??????���
•where:
•�… thedegreeofimportanceofpheromone
•�… degreeofimportanceofthedistance
•�∈??????
�… isa choicethatbelongsant �(neighborhood) whenhe was
atno �
•Neighborhoodofant �atnode �containsallthenodesthatare
incident withthenode �exceptalreadyvisitednodes
[1]
pheromone
1
��,�
•History
•Principle
•Example
4/21

6. PrincipleofPheromonesrecalculationI
[1]
•When allantsfinishedtheirjourney, thepheromonesmustberecalculated:
1.Vaporization
??????
�,�=??????
�,�∗??????
2.Calculationwithpheromonesleftby allantsduringtheirjourney
??????
�,�=??????
�,�+
??????
�(�)
Where:
??????… isa constant(usually1)
�… thevalueoftheobjectivefunctionofthesolution�
vaporizationcoefficient
•History
•Principle
•Example
5/21

7. PrincipleofPheromonesrecalculationII
[1]
•When ant �passingtheedge, itwillleavea pheromoneon thisedge. Theamount
ofpheromonecontainedin thesegment �jafterpassedby ant �isgivenby:
??????
�,�←??????
�,�+Δ??????
�
where:
Δ??????
�,�
�
=ቐ
�∗�
????????????��
�????????????���
����∈�������������ℎ
0,��ℎ��??????���
where:
�
����… isthebestvalueoftheobjectivefunction
�… constant
�
????????????���… istheworstvalueoftheobjectivefunction
•History
•Principle
•Example
6/21

8. PrincipleofPheromonesrecalculationII
[1]
•With increasingvalueofpheromoneon segment �,�theprobability ofthis
segment to bechosenby antsatthenextiterationincreases
•Whena node ispassed, thenthepheromoneevaporationwilloccurusingthe
followingequation:
??????
�,�←1−????????????
�,�,∀(�,�)∈??????
Where:
??????∈[0,1]… evaporationrateparameter
??????… segmentsthathavebeenpassedby ant �as part ofthepathfromthe
nestto thefood
•History
•Principle
•Example
7/21

9. Example
Step 1
[1]
•5 cities
•Distance matrix forthese citiesis:
010121114
10013158
12130914
11159016
14814160
•Matrix ofinverse distances
(visibilitymatrix):
0 0.10000.08330.09090.0174
0.10000 0.07690.06670.1250
0.08330.07690 0.11110.0714
0.09090.06670.11110 0.0625
0.07140.1250.07140.06250
•History
•Principle
•Example
8/21

10. Example
Step 1
[1]
•5 cities, city 1 isa departurecity. Sincecity 1 ischosenas thebeginning, itcannot
bechosenagain→visibilityofthecity is0
•Initialpheromonematrix
11111
11111
11111
11111
11111
0 0.10000.08330.09090.0174
0 0 0.07690.06670.1250
0 0.07690 0.11110.0714
0 0.06670.11110 0.0625
0 0.1250.07140.06250
•Visibilitymatrix
•History
•Principle
•Example
9/21

11. Example
Step 2
[1]
•Wecalculatetheposibility to visit othercity usingtheformula
0 0.10000.08330.09090.0174
0 0 0.07690.06670.1250
0 0.07690 0.11110.0714
0 0.06670.11110 0.0625
0 0.1250.07140.06250
•Visibilitymatrix
�
��,�=൞
??????�,�
�
??????�,�
�
σ
�∈�
??????
??????�,�
�
??????�,�
�
,����????????????
�
0,��ℎ��??????���
??????1,�
1
??????1,�
2
:
•1∗0.1000
2
=0.0100
•1∗0.0833
2
=0.0069
•1∗0.0909
2
=0.0083
•1∗0.07142
2
=0.0051
෍
�∈�
??????
??????1,�
1
??????1,�
2
=0.0303
•History
•Principle
•Example
10/21

12. Example
Step 2
[1]
0 0.10000.08330.09090.0174
0 0 0.07690.06670.1250
0 0.07690 0.11110.0714
0 0.06670.11110 0.0625
0 0.1250.07140.06250
•Visibilitymatrix
??????1,�
1
??????1,�
2
:
•1∗0.1000
2
=0.0100
•1∗0.0833
2
=0.0069
•1∗0.0909
2
=0.0083
•1∗0.07142
2
=0.0051
෍
�∈�
??????
??????1,�
1
??????1,�
2
=0.0303
Theprobabilities:
City 1 to 2:
0.01
0.0303
=0.3299 City 1 to 4:
0.0083
0.0303
=0.2727
City 1 to 3:
0.0069
0.0303
=0.2291 City 1 to 5:
0.0051
0.0303
=0.1683
•History
•Principle
•Example
11/21

13. Example
Step 2
[1]
•The probabilities:
City 1 to 2:
0.01
0.0303
=0.3299 City 1 to 4:
0.0083
0.0303
=0.2727
City 1 to 3:
0.0069
0.0303
=0.2291 City 1 to 5:
0.0051
0.0303
=0.1683
•Thecumulativenumbersofthese probabilities:
•City 2: 0.3299
•City 3: 0.5590
•City 4: 0.8317
•City 5: 1
•History
•Principle
•Example
12/21

14. Example
Step 3
[1]
•The cumulativenumbersofthese probabilities:
•City 2: 0.3299
•City 3: 0.5590
•City 4: 0.8317
•City 5: 1
•Generaterandomnumber�∈[0,1]: supposewehavegeneratednumber�=0.6841
•Compare�withcumulativenumbers:
•&#3627409358;.&#3627409363;&#3627409363;&#3627409367;&#3627409358;<??????<&#3627409358;.&#3627409366;&#3627409361;&#3627409359;&#3627409365;⇒anant willvisit thecity 4
•History
•Principle
•Example
13/21

15. Example
Step 4
[1]
•The city 4 wasvisited⇒thevisibilitymatrix mustbeadjusted:
0 0.10000.08330 0.0174
0 0 0.07690 0.1250
0 0.07690 0 0.0714
0 0.06670.11110 0.0625
0 0.1250.07140 0
•Now, theproces ofthecalculationoftheprobability ofvisitingtheneighborcity will
berepeated
•History
•Principle
•Example
14/21

16. Example
Step 5
[1]
??????4,&#3627408480;
1
??????4,&#3627408480;
2
:
•1∗0.0667
2
=0.0044
•1∗0.1111
2
=0.0123
•1∗0.07142
2
=0.0039
෍
&#3627408480;∈&#3627408448;
??????
??????1,&#3627408480;
1
??????1,&#3627408480;
2
=0.0207
Theprobabilities:
City 4 to 2:
0.0044
0.0207
=0.2147 City 4 to 5:
0.0039
0.0207
=0.1887
City 4 to 3:
0.0123
0.0207
=0.2291
0 0.10000.08330 0.0174
0 0 0.07690 0.1250
0 0.07690 0 0.0714
0 0.06670.11110 0.0625
0 0.1250.07140 0
•Visibilitymatrix
•History
•Principle
•Example
15/21

17. Example
Step 5
[1]
•The cumulativenumbersofthese probabilities:
•City 2: 0.2147
•City 3: 0.8113
•City 5: 1
•Generaterandomnumber&#3627408479;∈[0,1]: supposewehavegeneratednumber&#3627408479;=0.4024.
Compare &#3627408479;withcumulativenumbers:
•&#3627409358;.&#3627409360;&#3627409359;&#3627409362;&#3627409365;<??????<&#3627409358;.&#3627409366;&#3627409359;&#3627409359;&#3627409361;⇒anant willvisit thecity 3
•Fornow, wehavepath1→4→3
•History
•Principle
•Example
16/21

18. Example
Step 5
[1]
•This processsisrepeateduntilallantshavetheirownpaths
•Remember: Eachant startsfromanothercity
•Supposethatwehavethepathsas follows:
•Ant 1: 1→4→3→5→2→1 Totaldistance: 52
•Ant 2: 1→4→2→5→3→1 Totaldistance: 60
•Ant 3: 1→4→5→2→3→1 Totaldistance: 60
•Use totaldistances(objectivefunctionevaluation) to recalculatethepheromones
on theedges:
??????
&#3627408479;,&#3627408480;←1−????????????
&#3627408479;,&#3627408480;+෍
&#3627408472;=1
&#3627408449;
∆??????
&#3627408479;,&#3627408480;
&#3627408472;
•History
•Principle
•Example
17/21

19. Example
Step 6
[1]
•Use totaldistances(objectivefunctionevaluation) to recalculatethepheromones
on theedges:
??????
&#3627408479;,&#3627408480;←1−????????????
&#3627408479;,&#3627408480;+෍
&#3627408472;=1
&#3627408449;
∆??????
&#3627408479;,&#3627408480;
&#3627408472;
??????… evaporationcoefficientequalsto 0.5
•Pheromonematrix recalculatedbasedon theAnt 1:
0.50000.50000.50000.51920.5000
0.51920.50000.50000.50000.5000
0.50000.50000.50000.50000.5192
0.50000.50000.51920.50000.5000
0.50000.51920.50000.50000.5000
∆??????
&#3627408479;,&#3627408480;
&#3627408472;
=
??????
&#3627408467;(&#3627408480;)
=
1
52
•History
•Principle
•Example
18/21

20. Example
Step 6
[1]
•Use totaldistances(objectivefunctionevaluation) to recalculatethepheromones
on theedges:
??????
&#3627408479;,&#3627408480;←1−????????????
&#3627408479;,&#3627408480;+෍
&#3627408472;=1
&#3627408449;
∆??????
&#3627408479;,&#3627408480;
&#3627408472;
??????… evaporationcoefficientequalsto 0.5
•Pheromonematrix recalculatedbasedon theAnt 2:
0.50000.50000.50000.53590.5000
0.51920.50000.50000.50000.5167
0.51670.50000.50000.50000.5192
0.50000.51670.51920.50000.5000
0.50000.51920.51670.50000.5000
∆??????
&#3627408479;,&#3627408480;
&#3627408472;
=
??????
&#3627408467;(&#3627408480;)
=
1
60
•History
•Principle
•Example
19/21

21. Example
Step 6
[1]
•Use totaldistances(objectivefunctionevaluation) to recalculatethepheromones
on theedges:
??????
&#3627408479;,&#3627408480;←1−????????????
&#3627408479;,&#3627408480;+෍
&#3627408472;=1
&#3627408449;
∆??????
&#3627408479;,&#3627408480;
&#3627408472;
??????… evaporationcoefficientequalsto 0.5
•Pheromonematrix recalculatedbasedon theAnt 3:
0.50000.50000.50000.55260.5000
0.51920.50000.51670.50000.5167
0.53340.50000.50000.50000.5192
0.50000.51670.51920.50000.5167
0.50000.53590.51670.50000.5000
∆??????
&#3627408479;,&#3627408480;
&#3627408472;
=
??????
&#3627408467;(&#3627408480;)
=
1
60
•History
•Principle
•Example
20/21

22. Example
Step 7
[1]
•Repeattheproces untilthenumberofiterationsequalsto themaximum numberof
iterations
•History
•Principle
•Example
21/21

23. Literature
[1] BudiSantosa: Tutorial on Ant Colony Optimization, Institut
TeknologiSepuluhNopember, ITS, bsantosa.com