1 Cel ¢wiczenia.

1

POLITECHNIKA ‘LSKA

w Gliwicach

WYDZIAŠ AUTOMATYKI, ELEKTRONIKI i INFORMATYKI

Instytut Elektroniki

Zakªad Elektroniki Biomedycznej

LABORATORIUM

BIOCYBERNETYKI

ACO - Algorytmy mrówkowe

Opracowaª: mgr Jan Juszczyk

1 Cel ¢wiczenia.

Celem ¢wiczenia jest zapoznanie studentów z ide¡ algorytmów mrówkowych, oraz z ich podstawowymi odmia-
nami.

2 Wprowadzenie.

Algorytmy mrówkowe s¡ metodami optymalizacji, poprzez poszukiwanie optymalnej ±cie»ki w grae. Pierwszy
algorytm mrówkowy zostaª opracowany przez M. Doringo, A. Colornie oraz R. Maniezzo w 1991 roku. Opierali
si¦ oni na wcze±niejszych badaniach J. L. Deneubourga oraz S. Gossa. Badania Deneubourga i Gossa, które
dotyczyªy sposobów poszukiwania pokarmu przez argenty«skie mrówki. Okazaªo si¦, »e mimo tego, »e pojedyncza
mrówka porusza si¦ w sposób chaotyczny, to jako caªo±¢ potra¡ znale¹¢ ±cie»k¦, która jest bardzo zbli»ona do
optymalnej. Dodatkowo, w momencie zablokowania dotychczas najlepszej drogi, szybko wybieraj¡ krótsz¡ drog¦
obej±cia przeszkody.

3 Rzeczywiste mrówki

Mrówki podczas poszukiwania po»ywienia pozostawiaj¡ na ±cie»ce ±lad, substancj¦ chemiczn¡ okre±lan¡ fero-
monem, która jest wyczuwana przez pozostaªe mrówki kopca. Inne mrówki poszukuj¡ce pokarmu sugeruj¡ si¦
±ladami feromonowymi podczas wyboru drogi. Im mocniejszy ±lad feromonowy tym bardziej atrakcyjna dla
mrówki jest dana ±cie»ka. Feromon na danej ±cie»ce jest uzale»niony od dªugo±ci drogi oraz od ilo±ci mrówek,
które wykorzystaªy dan¡ drog¦. Dodatkowo feromon odparowuje, co prowadzi do tego, »e ±cie»ki nie u»ywane
wraz z upªywem czasu staj¡ si¦ coraz mniej atrakcyjne.

4 Cyfrowe mrówki

2

4 Cyfrowe mrówki

Ró»nice mi¦dzy prawdziwymi mrówkami a ich komputerowymi odpowiednikami wynikaj¡ ze specyki pracy
komputera. Podstawow¡ ró»nic¡ jest kwantowanie czasu. Mrówki nie poruszaj¡ si¦ pªynnie po ±cie»kach, tylko
skokowo przeskakuj¡c z punktu do punku. Czyli zakªadamy, »e mi¦dzy punktami poruszaj¡ si¦ po liniach pro-
stych. Mrówki nie poruszaj¡ si¦ równolegle, w tym samym czasie, tylko jedna za drug¡.

4.1 Wªa±ciwo±ci feromonu

1. Jego intensywno±¢ zmienia si¦ wraz z dªugo±ci¡ ±cie»ki, w taki sposób, »e na krótszej ±cie»ce znajduje si¦

wi¦ksza ilo±¢ feromonu.

2. Nie utrzymuje si¦ caªy czas na ±cie»ce, ale paruje z pewn¡ szybko±ci¡.

3. Feromon od kilku mrówek na tej samej ±cie»ce jest do siebie dodawany.

4. Mrówka z najwi¦kszym prawdopodobie«stwem wybierze ±cie»k¦ o najwi¦kszej intensywno±ci feromonu,

ale nie oznacza to »e wybierze j¡ z prawdopodobie«stwem 1.

4.2 Wªa±ciwo±ci mrówki

1. Ka»da mrówka posiada tyle samo feromonu

2. Mrówka wybiera drog¦ w sposób losowy, z prawdopodobie«stwem okre±lonym dla danej ±cie»ki.

5 Przykªad: Zablokowane przej±cie

Najprostszym przykªadem dziaªania algorytmu mrówkowego jest sytuacja, kiedy na drodze mrówek znajdzie

si¦ jaka± przeszkoda. Mrówka po lewej i po prawej stronie ma przed sob¡ wybór mi¦dzy dwoma ±cie»kami. Sama
mrówka nie wie, która ±cie»ka jest krótsza, wi¦c wybiera j¡ losowo, prawdopodobie«stwo wybrania ka»dej z nich
wynosi 0,5. Zaªó»my, »e mrówka po lewej wybraªa ±cie»k¦ np. B. W tym samym czasie mrówka po prawej wybraªa

6 Problem komiwoja»era TSP (ang. Travelling Salesman Problem)

3

±cie»k¦ A. Poniewa» ka»da mrówka niesie ze sob¡ tyle samo feromonu, to na krótszej ±cie»ce jest on bardziej
intensywny. Dlatego dla trzeciej mrówki ±cie»ka A b¦dzie ju» bardziej atrakcyjna ni» ±cie»ka B. Po przej±ciu
wielu mrówek wi¦kszo±¢ b¦dzie wybieraªa ±cie»k¦ A, poniewa» na niej b¦dzie odkªadane coraz wi¦cej feromonu.
‘cie»ka B wraz z upªywem czasu stanie si¦ coraz mniej atrakcyjna z powodu odparowywania feromonu. Dla
przykªadu omówionego powy»ej mo»na ªatwo wyznaczy¢ prawdopodobie«stwo wybrania okre±lonej ±cie»ki:

P

A

=

(k + A

i

)

n

(k + A

i

)

n

+ (k + B

i

)

n

(1)

gdzie:

P

A

 prawdopodobie«stwo wybrania ±cie»ki A

A

i

, B

i

 liczba mrówek, które wybraªy okre±lon¡ ±cie»k¦

i

 indeks okre±laj¡cy iteracj¦

k

 parametr okre±laj¡cy atrakcyjno±¢ nieucz¦szczanej drogi

n

 parametr okre±laj¡cy nieliniowo±¢ zmiany prawdopodobie«stwa

Wyra»enie 1  PB, wskazuje, »e je»eli mrówka nie wybraªa jednej ±cie»ki to musi wybra¢ drug¡, nie ma

mo»liwo±ci, aby nie wybraªa »adnej. Ró»nice w ilo±ci mrówek wybieraj¡cych okre±lon¡ ±cie»k¦ b¦d¡ tym wi¦ksze,
im wi¦ksza b¦dzie ró»nica w dªugo±ciach ±cie»ek. Dla szczególnego przypadku, kiedy ±cie»ki maj¡ tak¡ sam¡
dªugo±¢, po dªugim czasie ±rednio przez ka»d¡ z nich przejdzie tyle samo mrówek.

6 Problem komiwoja»era TSP (ang. Travelling Salesman Problem)

Problem komiwoja»era jest zagadnieniem poszukiwania najkrótszej drogi mi¦dzy miastami. Komiwoja»er ma do
objechania okre±lon¡ liczb¦ miast i do ka»dego z nich mo»e przyby¢ tylko jeden raz. Zadaniem jest wyznaczenie
jak najkrótszej trasy przejazdu zaliczaj¡cej wszystkie miasta.

Liczba mo»liwych rozwi¡za« TSP wyra»a si¦ wzorem

(n−1)!

2

, co powoduje praktycznie brak mo»liwo±ci spraw-

dzenia wszystkich mo»liwych rozwi¡za« w rozs¡dnie krótkim czasie dla liczby miast wi¦kszej ni» ok 30.

7 Zastosowanie algorytmu mrówkowego do rozwi¡zania problemu komiwoja»era

4

7 Zastosowanie algorytmu mrówkowego do rozwi¡zania problemu ko-

miwoja»era

Algorytm mrówkowy wydaje si¦ by¢ jak na razie najlepszym sposobem rozwi¡zania TSP. Nie tylko daje najlepsze
wyniki w porównaniu z innymi zastosowanymi algorytmami, równie» przystosowanie go na potrzeby TSP jest
prawie intuicyjne.

Schemat algorytmu

1. Mrówka wybiera w sposób losowy ±cie»k¦ przej±¢ mi¦dzy miastami. Do zapami¦tania ma tylko kolejno±¢

odwiedzanych miast

2. Wyznaczana jest dªugo±¢ przebytej drogi na podstawie kolejno±ci miast.

3. Na podstawie przebytej drogi wyznaczany jest poziom feromonu na ±cie»kach mi¦dzy miastami.

1-3 s¡ wykonywanie tyle razy ile wpuszczonych jest mrówek

4. Feromon jest nakªadany na odpowiednie ±cie»ki (akutalizowany) dla wszystkich wpuszczonych mrówek

(zasada jest taka, jakby mrówki byªy wpuszczane równolegle)

5. Nast¦puje odparowanie feromonu

Powrót do 1

Prawdopodobie«stwo w tym przypadku dane jest wzorem:

F

ij

=







(τ

ij

)

α

(η

ij

)

β

P

k∈Ω

(τ

ih

)

α

(η

ih

)

β

dla

j ∈ Ω

0

dla

j /

∈ Ω

(2)

gdzie:
τ

ij

- feromon znajduj¡cy si¦ na ±cie»ce mi¦dzy miastami i oraz j

η

ij

- warto±¢ lokalnej funkcji kryterium  element losowy wyboru ±cie»ki

α

- paramet reguluj¡cy wpªyw τ

ij

β

- paramet reguluj¡cy wpªyw η

ij

8 Typy algorytmów mrówkowych

Od czasów powstania pierwszego algorytmu mrówkowego (AS) pojawiªo si¦ kilka inny odmian. W zasadzie
wszystkie ró»nice mi¦dzy kolejnymi odmianami algorytmów mrówkowych sprowadzaj¡ si¦ do ró»nych sposobów
dozowania feromonu.

8.1 Ant System (AS)

Jest to pierwszy opracowany algorytm mrówkowy, feromon dany jest wzorem:

τ

ij

← (1 − ρ)· τ

ij

+

m

X

k=1

∆τ

k

ij

(3)

gdzie:
τ

ij

- feromon

ρ

- wspóªczynnik parowania feromonu

m

- liczba mrówek

∆τ

k

ij

jest zdeniowane:

∆τ

k

ij

=

(

Q/L

k

,

jezeli mrowka uzyla sciezki (i, j)

0

,

w przeciwnym przypadku

(4)

8.2 MAX-MIN Ant System (MMAS)

5

i jest ilo±ci¡ feromonu zostawion¡ przez k-t¡ mrówk¦ na ±cie»ce (i, j)
gdzie:
Q

- staªa ilo±¢ feromonu niesiona przez mrówk¦

L

k

-dªugo±¢ drogi przebytej przez k-t¡ mrówk¦

System ten jest najprostszym systemem najbardziej intuicyjnym. Ka»de nast¦pne algorytmy s¡ rozwini¦ciem
tego systemu.

8.2 MAX-MIN Ant System (MMAS)

System MMAS ró»ni si¦ tym od AS, »e aktualizowany jest w taki sposób, »e wyró»niona jest najlepsza droga,
a dokªadnie dotychczas najlepsza droga.

τ

ij

←

(1 − ρ)· τ

ij

+ ∆τ

best

ij



(5)

gdzie operator [] jest dany:

[x]

b
a

=











a

dla

x > a

b

dla

x < b

x

dla

pozostaych

(6)

∆τ

best

ij

jest zdeniowane:

∆τ

best

ij

=

(

1/L

best

,

jezeli sciezka nalezy do najlepszej drogi (i, j)

0

,

w przeciwnym przypadku

(7)

8.3 Ant Colony System (ACS)

W ACS feromon jest aktualizowany dopiero po przebiegu wszystkich mrówek w iteracji, tak jak jest to zreali-
zowane w rozwi¡zaniu problemu komiwoja»era w przykªadzie.

9 Inne zastosowania algorytmów mrówkowych

Oprócz problemu komiwoja»era, algorytmy mrówkowe s¡ wykorzystywane do rozwi¡zywania problemów opty-
malizacyjnych w:
- transporcie
- transferze danych
- sortowaniu
- szeregowaniu zada«
Algorytmy mrówkowe równie» s¡ stosowane przy segmentacji obrazów.

10 Program ¢wiczenia

1. Zapoznanie studentów z teoretycznymi podstawami algorytmów mrówkowych

2. Znalezienie parametrów optymalizuj¡cych dziaªanie algorytmu mrówkowego wykonanego w ±rodowisku

Matlab, dla problemu komiwoja»era przy zadanym przez prowadz¡cego ukªadzie miast.

3. Podanie, który z otrzymanych parametrów okre±la najkrótsz¡ drog¦.

LITERATURA

6

Literatura

[1] M.Dorigo, M.Birattari Ant Colony Optimization IEEE Computational Intelligence Magazine, Nov 2006

Addison-Wesley, 2004.

[2] M.Dorigo, G. Di Caro Ant Algorithms Discrete Optimization MIT Press, 1999

[3] L. Li, Y. Ren, X. Gong Medical Image Segmentation Based on Modied Ant Colony Algorithm with GVF

Snake Model IEEE Computer Society, 2008

[4] L. M. Gambardella, M. Dorigo Soloving Symmetric and Asymmetric TSPs by Ant Colonies IEEE, 1996

[5] http://www.aco-metaheuristic.org/

[6] http://www.iis.pwr.wroc.pl/~kwasnick/prace_studenckie.htm