Optimizacija kolonijom mrava
PAŽNJA!
Biblioteka JFreeChart koja se koristi je malo veća te stoga i učitavanje appleta prvi puta traje malo duže. Budite strpljivi.
Također morate imati instaliran Java plugin za Vaš preglednik kako biste mogli pokrenuti program.
Objašnjenja pojedinih algoritama
Simple Ant Colony Algorithm
- Pseudokod
-
Inicijaliziraj tragove
Dok nije kraj
Za svakog od X mrava
Obavi šetnju
Ažuriraj globalno najbolje rješenje
Za Y najboljih mrava
Ažuriraj tragove puteva kojima je prošao
Ispari tragove
- Inicijaliziraj tragove
-
Svakom putu se na pošetku postavlja količina feromona od 0.001 jedinica
- Odabir puta
-
Svaki mrav bira sljedeće odrediste iz skupa gradova koje još nije posjetio
(budic da radimo sa potpuno povezanim grafom, iz svakog grada se može docć u sve preostale)
sa vjerojatnošću
gdje su
-
- vjerojatnost odabira puta iz grada i u grad j
-
- skup gradova koje nismo posjetili
-
- jakost feromona na putu iz grada i u grad j
-
- alfa konstanta
- Ažuriranje tragova
-
Svaki mrav ažurira tragove na putu kojim je prošao koristeći relacije
i
gdje su
-
- duljina puta mrava koji ažurira
-
- jakost feromona na putu iz grada i u grad j
- Isparavanje tragova
-
Svim putevima se tragovi ažuriraju koristeći relaciju
gdje su
Ant System
- Pseudokod
-
Inicijaliziraj tragove
Dok nije kraj
Za svakog od X mrava
Obavi šetnju
Ažuriraj globalno najbolje rješenje
Ispari tragove
Za svakog od X mrava
Ažuriraj tragove puteva kojima je prosao
- Inicijaliziraj tragove
-
Svakom putu se na pocetku postavlja količina feromona jednaka recipročnoj vrijednosti
duljini puta pronađenoj uz pomoc pohlepnog algoritma
- Odabir puta
-
Svaki mrav bira sljedeće odredište iz skupa gradova koje još nije posjetio
(budući da radimo sa potpuno povezanim grafom, iz svakog grada se moze doći u sve preostale)
sa vjerojatnošću
gdje su
-
- vjerojatnost odabira puta iz grada i u grad j
-
- skup gradova koje nismo posjetili
-
- jakost feromona na putu iz grada i u grad j
-
- vrijednost heurističke funkcije na putu iz grada i u grad j
(u našem slucaju recipročna vrijednost njihove međusobne udaljenosti)
-
- alfa konstanta
-
- beta konstanta
- Ažuriranje tragova
-
Svaki mrav ažurira tragove na putu kojim je prošao koristeći relacije
i
gdje su
-
- duljina puta mrava koji ažurira
-
- jakost feromona na putu iz grada i u grad j
- Isparavanje tragova
-
Svim putevima se tragovi ažuriraju koristeći relaciju
gdje su
Korišteni alati otvorenog koda