Optimaliza ní algoritmy inspirované chováním mravenc •Biologická analogie •ACO metaheuristic •Ant system a jeho modifikace •Specifikace problém •Aplikace
Motivace • NP-hard problémy – asová náro nost nalezení optimálního $ešení roste exponenciáln' s velikostí problému ° Kombinatorické problémy
• Jednou z mo*ností jsou aproxima ní metody, které naleznou $ešení alespo, blízké optimálnímu v rozumném ase • Aproxima ní metody ° Lokální prohledávání/optimalizace • Iterativní zlepšování po áte ního $ešení a* do uváznutí v lok. ext.
° Konstruktivní algoritmy • Budování $ešení s vyu*itím heuristické znalosti
• Ant Colony Optimization (ACO) – rozší$ení tradi ních konstruktivních heuristik o schopnost vyu*ití zkušeností získaných v pr b'hu $ešení daného problému
Lokální prohledávání Procedure IterativeImprovement(s S) s’ = Improve(s) while s’ s do s = s’ s’ = Improve(s) end return s end
Problémy ° asto uvázne v lokálním extrému ° výsledek velice závisí na po áte ním $ešení
Konstruktivní algoritmy • Pracují s áste n* rozpracovaným ,ešením, sna*í se jej rozší$it nejvýhodn'jším zp sobem – vyu.ívají hladový algoritmus Procedure GreedyConstructionHeur sp = empty_solution while not complete(sp) do e = GreedyComponent(sp) sp = sp e end return sp end
TSP: p,idávání nejbli.šího souseda
• Výhody/nevýhody + rychlé - mnohdy generují ne moc dobrá $ešení (ikdy* o p$ijatelné kvalit') - generuje pouze velice omezený po et $ešení - rozhodnutí u in'ná na za átku výpo tu zna n' omezují mo*nosti v pozd'jších fázích
Mraven í algoritmy: biologická inspirace • Inspirované chováním mraven ích kolonií ° Sociální hmyz – chování sm'$uje k zachování kolonie ° Jednoduché chování jedinc × slo*ité chování kolonie • Schopnost nalézt nejkratší cestu od zdroje potravy k mraveništi pomocí vzájemné komunikace prost$ednictvím Feromonu • Zápis - mravenci ukládají feromon po cest' za potravou • 6tení – mravenci umí detekovat feromony (a rozlišovat mezi r znými koncentracemi) zanechané ostatními soukmenovci a vybírá si cestu s nejv'tší koncentrací feromonu • Emergence – toto chování aplikované celou kolonií mravenc m *e vést k emergenci nejkratší cesty
Experimenty se skute nými mravenci • Deneuborg et al. (mravenci Linepithema humile) • Mraveništ* odd*lené od zdroje potravy dvojitým mostem ° Ob' cesty stejn' dlouhé ° Na za átku není *ádný feromon na *ádné z cest ° Po ase jedna z cest díky náhodným fluktuacím p$evá*í
Mosty s r zn* dlouhými variantami • Vliv náhodných fluktuací je zna n* redukován a v*tšina mravenc nakonec volí tu nejkratší cestu
P,íklad •
P,íklad • V ka*dém kroku jde 30 nových mravenc z B do A, 30 z E do D ° mravenec jde rychlost 1 s-1 ° za jednotku asu polo*í 1 jednotku feromonu
Stigmergie • Chování kolonie – distribuovaný optimaliza ní algoritmus, kde ka*dý mravenec p$ispívá svou trochou do mlýna (umí zkonstruovat celou cestu). • Stigmergie - nep$ímá komunikace mravenc zprost$edkovaná pomocí feromonu ° Fyzikální podstata informace uvoln'né komunikujícími mravenci – modifikace místa navštíveného mravencem ° Lokálnost zanechané informace – je viditelná pouze mravenci, kte$í navštíví místo s feromonem nebo jeho okolí ° Autokatalytický mechanismus • Odpa,ování feromonu – realizuje zapomínání, které zabra,uje p$ed asné konvergenci k suboptimálnímu $ešení
Um*lí mravenci • Podobnosti se skute nými mravenci: ° Kolonie kooperujících mravenc ° Feromonová stopa a stigmergie ° Pravd'podobnostní rozhodování, lokálnost strategie • Apriorní informace daná problémovou specifikací • Lokální modifikace stav , indukované p$edcházejícími mravenci
• Rozdílnosti oproti skute ným mravenc m: ° ° ° ° ° °
Diskrétní sv't Vnit$ní stavy – osobní pam'A zaznamenávající doposud vykonané akce Nejsou zcela slepí Mno*ství zanechaného feromonu je funkcí kvality nalezeného $ešení Problémov' závislé asování ukládání feromonu Extras – lokální optimalizace, backtracking
Ant Colony Optimization Metaheuristic • ACO m *e být pou*ito pro $ešení jakéhokoliv diskrétního optimaliza ního problému, pro který lze pou*ít n'jakou konstruktivní heuristickou proceduru • Mravenci pou*ití v ACO fungují jako stochastické konstruktivní procedury, které vytvá$ejí $ešení iterativním p$idáváním komponent do do áste ného $ešení, p$i em* p$i výb'ru ka*dé další komponenty uva*ují ° heuristickou informaci o $ešeném problému, která sm'ruje výpo et ke slibným $ešením a ° zkušenosti získané všemi mravenci od za átku výpo tu, reprezentované feromonovými stopami, které se b'hem výpo tu neustále adaptují • Stochastická slo.ka umo*,uje vygenerování velkého po tu r zných $ešení
Ant System (AS) - definice • Problém: M'jme n m'st, cílem je nalézt nejkratší uzav$enou cestu, která prochází všemi m'sty práv' jednou ° uva*ujeme úplný graf ° dij je euklidovská vzdálenost z m'sta i do m'sta j • Definice ° bi(t), i=1,...,n je po et mravenc v m'st' i v ase t ° m je celkový po et mravenc ° ij(t) je intenzita feromonu na spojnici (i, j) v ase t ° ij je viditelnost vyjád$ená hodnotou 1/dij ° (1- ) reprezentuje faktor vypa$ování, je konstantní b'hem výp. ° tabuk je dynamicky rostoucí vektor, obsahuje seznam m'st, kterými mraevnec prošel v dané cest' ° iterace AS je posun všech m mravenc o jeden krok ° cyklus AS se skládá z n iterací b'hem nich* mravenci dokon í cestu
AS – ukládání feromonu •
ij(t+n)
• D ij =
=
ij(t)
kD
+D
ij
k ij
Q/Lk, jestli*e k-tý mravenec pou*il hranu (i, j) • D
k
ij
= 0, kdy* ji nepou*il.
kde A ijk je mno*ství feromonu polo*eného na hranu (i, j) k-tým mravencem v intervalu (t, t+n) Q je konstanta Lk je délka cesty, kterou urazil k-tý mravenec musí být menší ne* 1, jinak by se neomezen' kumuloval feromon ij(0) je nastaveno na malé kladné hodnoty
AS - pravd*podobnost p,echodu z i do j [ ij(t)] [
ij
] /
l[ ij(t)]
[
ij
] , kdy* j {N - tabuk}
• pijk(t) = 0, jinak. kde l {N - tabuk} , ur ují relativní d le*itost feromonu a viditelnosti • Pravd'podobnost je po ítána jako kompromis mezi ° viditelností, která $íká, *e bli*ší m'sta by m'la být preferována a ° intenzitou feromonu, která $íká, *e asto pou*ívaná hrana je z$ejm' *ádoucí
AS – algoritmus Ant-cycle •
Ant-cycle: 1. Inicializace • asu: t=0 • po tu cykl : NC=0 • feromonu: ij(t)=c • imíst'ní m mravenc na n m'st 2. Inicializace tabu seznam 3. Jinnost mravenc • iterativní vybudování cesty • výpo et délky cesty Lk pro všechna k • aktualizace nejkratší nalezené cesty • výpo et D ijk a aktualizace ij(t+n) 4. Inkrementace diskrétního asu • t = t+n, NC = NC+1 5. If(NC < NCmax) then goto step 2 else stop
AS – modifikace •
Liší se zp sobem adaptace feromonu – mravenci ukládají feromon pr b'*n' po ka*dé iteraci ° Ant-density – po projití hrany (i, j) mravenec ulo*í konstantní mno*ství feromonu Q °
Ant-quantity - po projití hrany (i, j) mravenec ulo*í mno*ství feromonu Q/dij
•
Ob' modifikace jsou horší ne* Ant-cycle, proto*e pou*ívají lokální informaci pro ukládání feromonu.
AS – nastavení •
Optimální hodnota je 0.5 ° po úvodním hladovém prohledávání je t$eba dát prostor adaptaci globální informace ulo*ené v ij(t) ° jinými slovy, je t$eba zapomenout
AS – význam , •
význam , (optimální =1, =2) ° Vysoká hodnota znamená, *e intenzita feromonu je prioritní, tak*e °
•
mravenci volí cestu, kterou šli jejich p$edch dci Nízká nebo nulová m'ní metodu na stochastický restartovaný hladový algoritmus
Stagnace – v'tvící faktor 2, všeichni mravenci jdou stejnou cestou
AS – elitismus •
Intenzita feromonu je posílena na hranách, které le*í na nejkratší cest' °
Mno*ství p$idaného feromonu: e Q/L* , kde e je po et „elitních“ mravenc a L* je nejkratší cesta
°
Ale pozor na p,ed asnou konvergenci
Implementace ACO procedure ACO metaheuristics ScheduleActivities ManageAntActivity() EvaporatePheromone() // zapomínání DaemonActions() {optional} // centralizované akce end ScheduleActivities
end ACO metaheuristics • • • •
Nalezení vhodné garfové reprezentace Definování pozitivní zp'tné vazby Výb'r konstruktivní heuristika Model práce s omezeními – tabu seznamy u TSP
Reprezentace problému • Nalézt vhodnou grafovou reprezentaci • Uva*ujme minimaliza ní problém (S, f, ), kde S je mno*ina kandidát $ešení, f je objektivní funkce a je mno*ina omezení. Cílem je najít globální optimum Sopt S, které vyhovuje omezením • Reprezentace kombinatorického problému (S, f, mravenci je charakterizována takto:
.
), kterou vyu*ívají
° Je dána kone ná mno*ina C={c1, c2, …, cNc}komponent ° Stavy problému jsou dány sekvencemi x= ci, cj, …, ck, … , délka x je |x|. Mno*ina všech sekvencí se zna í . ° Mno*ina stav vyhovujících omezením je * . ° Mno*ina proveditelných $ešení S* *, S* S. ° Ka*dému mo*nému $ešení Sopt S je p$i$azeno ohodnocení f(s,t).
Chování mravence • Mravenec funguje jako konstruktivní procedura, která vytvá$í $ešení procházením konstruk ního grafu G=(C, L), kde komponenty C jsou vrcholy grafu a L reprezentuje hrany (úpln' propojený graf). • Komponenty ci C a spoje lij L mohou mít p$i$azenu feromonovou stopu , která reprezentuje dlouhodobou pam'A (zkušenost mravenc ) upravovanou mravenci a heuristickou hodnotu , která reprezentuje apriorní informaci o $ešeném problému (odhad ceny spojené s rozší$ením daného stavu). Tyto hodnoty pou*ívá mravenec p$i rozhodování o následujícím tahu. • Ka.dý mravenec má následující vlastnosti: ° Prohledává graf G s cílem najít optimální proveditelné $ešení ° Má pam'A Mk, která uchovává doposud provedené tahy. Vyu*ívá ji pro • vytvá$ení proveditelných $ešení (implementaci omezení) • ohodnocování nalezeného $ešení • zp'tné trasování nalezené cesty b'hem n'ho* ukládá feromon ° Vybírá tahy pomocí pravd'podobnostního pravidla, které je fukcí • lokáln' dostupného feromonu, pam'ti Mk a omezení ° Feromon m *e být upraven p$i ka*dém p$idání komponenty do $ešení (online step-by-step pheromone update) nebo najednou a* po zkompletování celého $ešení (delayed pheromone update)
Applications of ACO algorithms • Static problems ° ° ° ° ° °
Traveling salesman Quadratic assigment Job-shop scheduling Vehicle routing Graph colouring Shortest common supersequence
• Dynamic problems ° Connection-oriented network routing ° Connection-less network routing
Aplikace ACO na mTSP • mTSP – TSP s více cestujícími ° Zadání: 100 m'st, 3 agenti ° Cíl: Rozd'lit práci mezi všechny agenty tak, aby se minimalizovalo zatí*ení nejvytí*en'jšího agenta
Aplikace ACO na JSP • Definice problému: ° M stroj a J úkol ° j-tý úkol se skládá z uspo$ádané posloupnosti operací z mno*iny O={…, ojm, …}, celkový po et operací je N=|O| ° ka*dá operace má danou délku trvání ° cílem je nalézt nejkratší rozvrh prací, bez konflikt , tj. *ádné dva úkoly nebudou zpracovány sou asn' na stejném stroji
Aplikace ACO na JSP • Implementace ° Orientovaný graf Q=(O’, A), kde O’=O {o0} a A je mno*ina hran spojující o0 s první operací ka*dého úkolu a realizující úplné propojení operací z O, vyjma operací stejného úkolu. ° Ke ka*dé hran' jsou p$i$azeny váhy { ij, ij} • •
ij
intenzita feromonu
viditelnost, odvozená pomocí Longest Processing Time nebo Shortest Completion Time heuristik ij
• P,íklad ° 3 úkoly, 2 stroje 1. stroj: o1, o3, o5 2. stroj: o2, o4, o6
Aplikace ACO na JSP •
Pr b*h výpo tu: 1. Na za átku jsou všichni mravenci v uzlu o0 2. V ka*dém kroku mravenec vybírá další tah z • mno*iny Gk, která obsahuje všechny uzly, které mají být navštíveny a • mno*iny Sk, která obsahuje uzly, které mohou být navštíveny v daném kroku P$.: na za átku je Gk={1, 2, 3, 4, 5, 6} a Sk={1, 2, 3} 3. Kdy* je vybrán další uzel u, tak je • p$idán do tabu seznamu a • vymazán z Gk a Sk 4. Pokud u nebyl poslední uzel daného úkolu, tak p$idej do Sk bezprost$edního následníka u 5. Opakuj kroky 2.-4. dokud Gk=
Zdroje [Dorigo et al., 1996] Dorigo M., V. Maniezzo & A. Colorni (1996). The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1):29-41 [Dorigo & Gambardella, 1997] Dorigo M. & L.M. Gambardella (1997). Ant Colonies for the Traveling Salesman Problem. BioSystems, 43:73-81. [Dorigo et al., 1999] Dorigo M., G. Di Caro & L. M. Gambardella (1999). Ant Algorithms for Discrete Optimization. Artificial Life, 5(2):137-172. [Dorigo & Stützle, 2002] M. Dorigo and T. Stützle, 2002. The ant colony optimization metaheuristic: Algorithms, applications and advances. In F. Glover and G. Kochenberger editors, Handbook of Metaheuristics, volume 57 of International Series in Operations Research & Management Science, pages 251-285. Kluwer Academic Publishers, Norwell, MA.
http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
