Optimizacija kolonijom mrava

Evolucijski algoritmi

Pojašnjenje opcija

Gradovi

koordinate gradova u formatu . Za gradove unesene kao pocetne vrijednosti, optimalna putanja je oko 7542

Sjeme

Cijeli broj koji se koristi kao sjeme za generator nasumičnih brojeva

Broj mrava

Određuje koliko se mrava seće

Algoritam

Određuje koji se algoritam koristi za simulaciju. Moguće je odabrati izmedu sljedećih algoritama

• Simple ACO
• Ant System

Konstanta isparavanja

konstanta isparavanja koja određuje kojim intenzitetom se obavlja isparavanje (u formulama oznaka )

Alfa

konstanta alfa (u formulama oznaka )

Beta

konstanta beta (u formulama oznaka )

Broj mrava azurira

Određuje koliko se mrava sa najboljim rješenjem korisit za ažuriranje feromonskih tragova

Broj šetnji

Određuje koliko šetnji će svaki mrav napraviti

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

• - Konstanta isparavanja
• - jakost feromona na putu iz grada i u grad j

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

• - Konstanta isparavanja
• - jakost feromona na putu iz grada i u grad j

Korišteni alati otvorenog koda

• JFreeChart
• exp4j