Algoritmy optimalizace kolonií mravenců - Ant colony optimization algorithms

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto problémech na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek případně obsahuje původní výzkum. Prosím vylepši to podle ověřování vznesené nároky a přidání vložené citace. Výroky sestávající pouze z původního výzkumu by měly být odstraněny. (Srpna 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Srpna 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Chování mravenců bylo inspirací pro metaheuristickou optimalizační techniku

Když je kolonie mravenců konfrontována s výběrem dosažení potravy dvěma různými cestami, z nichž jedna je mnohem kratší než druhá, je jejich výběr zcela náhodný. Ti, kteří používají kratší cestu, se však dostanou k jídlu rychleji, a proto se častěji pohybují tam a zpět mezi mraveništěm a jídlem.^[1]

v počítačová věda a operační výzkum, optimalizace kolonií mravenců algoritmus (ACO) je pravděpodobnostní technika řešení výpočetních problémů, kterou lze snížit na hledání dobrých cest grafy. Umělé mravenci stát za multiagent metody inspirované chováním skutečných mravenců. Feromonová komunikace biologická mravenci je často používaným paradigmatem.^[2] Kombinace umělých mravenců a místní vyhledávání Algoritmy se staly metodou volby pro řadu optimalizačních úkolů zahrnujících nějaký druh graf, např. směrování vozidel a internet směrování. Rostoucí aktivita v této oblasti vedla ke konferencím věnovaným výhradně umělým mravencům a k četným komerčním aplikacím specializovaných společností, jako jsou AntOptima.

Jako příklad lze uvést optimalizaci kolonií mravenců^[3] je třída optimalizace algoritmy po vzoru akcí mravenčí kolonie. Umělí „mravenci“ (např. Simulační agenti) lokalizují optimální řešení pohybem a prostor parametrů představující všechna možná řešení. Skuteční mravenci si lehli feromony vzájemné směrování ke zdrojům při zkoumání jejich prostředí. Simulované „mravenci“ podobně zaznamenávají své pozice a kvalitu svých řešení, takže v pozdějších simulačních iteracích najde více mravenců lepší řešení.^[4] Jednou z variant tohoto přístupu je algoritmus včel, což je analogičtější s hledáním potravy včelí med, další sociální hmyz.

Tento algoritmus je členem algoritmy kolonií mravenců rodina, v rojová inteligence metody, a to představuje některé metaheuristické optimalizace. Původně navrhl Marco Dorigo v roce 1992 ve své disertační práci,^[5][6] První algoritmus byl zaměřen na hledání optimální cesty v grafu na základě chování mravenci hledají cestu mezi jejich kolonie a zdroj potravy. Původní myšlenka se od té doby diverzifikovala, aby vyřešila širší třídu numerických problémů, a ve výsledku se objevilo několik problémů, čerpajících z různých aspektů chování mravenců. Z širší perspektivy provádí ACO modelové vyhledávání^[7] a sdílí některé podobnosti s odhad distribučních algoritmů.

Přehled

V přírodním světě se mravenci některých druhů (zpočátku) potulují náhodně, a když našli jídlo, vraťte se do jejich kolonie, zatímco jste se ukládali feromon stezky. Pokud ostatní mravenci najdou takovou cestu, pravděpodobně nebudou pokračovat v náhodném cestování, ale místo toho budou sledovat stezku, vracet se a posilovat ji, pokud nakonec najdou jídlo (viz Ant komunikace ).^[8]

Postupem času se však feromonová stezka začíná vypařovat, čímž se snižuje její atraktivní síla. Čím více času mravenci potřebuje, aby cestoval po cestě a zase zpátky, tím více času musí feromony odpařovat. Krátká cesta se ve srovnání s tím častěji pochoduje, a tím se hustota feromonů zvyšuje na kratších cestách než na delších. Odpařování feromonů má také tu výhodu, že se vyhne konvergenci k místně optimálnímu řešení. Pokud by nedocházelo k žádnému odpařování, cesty zvolené prvními mravenci by měly tendenci být nadměrně atraktivní pro následující. V takovém případě by byl omezen průzkum prostoru řešení. Vliv odpařování feromonů ve skutečných systémech mravenců je nejasný, ale v umělých systémech je velmi důležitý.^[9]

Celkovým výsledkem je, že když jeden mravenec najde dobrou (tj. Krátkou) cestu z kolonie ke zdroji potravy, je pravděpodobnější, že tuto cestu budou následovat další mravenci a Pozitivní zpětná vazba nakonec vede k mnoha mravencům, kteří sledují jednu cestu. Myšlenkou algoritmu kolonií mravenců je napodobit toto chování pomocí simulovaných mravenců, kteří procházejí kolem grafu představujícího problém, který je třeba vyřešit.

Ambientní sítě inteligentních objektů

Jsou zapotřebí nové koncepty, protože „inteligence“ již není centralizována, ale lze ji najít ve všech nepatrných objektech. Je známo, že antropocentrické koncepty vedly k výrobě IT systémů, ve kterých jsou centralizovány zpracování dat, řídicí jednotky a výpočetní síly. Tyto centralizované jednotky neustále zvyšovaly svůj výkon a lze je srovnávat s lidským mozkem. Model mozku se stal konečnou vizí počítačů. Ambientní sítě inteligentních objektů a dříve či později nová generace informačních systémů, které jsou ještě rozptýlenější a založené na nanotechnologii, tuto koncepci zásadně změní. Malá zařízení, která lze přirovnat k hmyzu, sama o sobě nemají vysokou inteligenci. Jejich inteligenci lze skutečně klasifikovat jako poměrně omezenou. Je například nemožné integrovat vysoce výkonnou kalkulačku se schopností řešit jakýkoli druh matematického problému do biočipu, který je implantován do lidského těla nebo integrován do inteligentního štítku určeného ke sledování komerčních článků. Jakmile jsou však tyto objekty vzájemně propojeny, disponují formou inteligence, kterou lze přirovnat ke kolonii mravenců nebo včel. V případě určitých problémů může být tento typ inteligence lepší než uvažování centralizovaného systému podobného mozku.^[10]

Příroda nabízí několik příkladů toho, jak mohou nepatrné organismy, pokud všechny dodržují stejné základní pravidlo, vytvořit formu kolektivní inteligence na makroskopické úrovni. Kolonie sociálního hmyzu dokonale ilustrují tento model, který se výrazně liší od lidských společností. Tento model je založen na spolupráci nezávislých jednotek s jednoduchým a nepředvídatelným chováním.^[11] Pohybují se kolem svého okolí, aby plnili určité úkoly, a mají k tomu jen velmi omezené množství informací. Kolonie mravenců například představuje řadu kvalit, které lze také použít na síť okolních objektů. Kolonie mravenců mají velmi vysokou schopnost přizpůsobit se změnám v prostředí a mají obrovskou sílu při řešení situací, kdy jeden jedinec nesplní daný úkol. Tento druh flexibility by byl také velmi užitečný pro mobilní sítě objektů, které se neustále vyvíjejí. Balíky informací, které se pohybují z počítače na digitální objekt, se chovají stejně jako mravenci. Pohybují se sítí a procházejí z jednoho uzlu do druhého s cílem co nejrychleji dorazit do svého konečného cíle.^[12]

Systém umělých feromonů

Komunikace založená na feromonech je jedním z nejúčinnějších způsobů komunikace, který je v přírodě široce pozorován. Feromon je používán společenským hmyzem, jako jsou včely, mravenci a termiti; jak pro komunikaci mezi agenty, tak pro agent-roj. Díky své proveditelnosti byly umělé feromony přijaty v robotických systémech s více roboty a roji. Komunikace založená na feromonech byla implementována různými způsoby, například chemickými ^[13][14][15] nebo fyzické (RFID tagy,^[16] světlo,^{[17][18][19][20]} zvuk^[21]) způsoby. Tyto implementace však nebyly schopny replikovat všechny aspekty feromonů, jak jsou vidět v přírodě.

Použití promítaného světla bylo prezentováno v dokumentu IEEE 2007 od Garniera, Simona a kol.^[22] jako experimentální nastavení ke studiu komunikace založené na feromonech s mikro autonomními roboty. Další studie, která navrhla novou feromonovou komunikační metodu, COSΦ,^[23] robotický systém roje je založen na přesné a rychlé vizuální lokalizaci.^[24] Systém umožňuje simulaci prakticky neomezeného počtu různých feromonů a poskytuje výsledek jejich interakce jako obraz v šedé stupnici na vodorovné LCD obrazovce, na kterou se roboti pohybují. Za účelem demonstrace feromonové komunikační metody byl jako rojová robotická platforma nasazen autonomní mikro robot Colias.^{[Citace je zapotřebí ]}

Algoritmus a vzorce

V algoritmech optimalizace kolonií mravenců je umělý mravenec jednoduchý výpočetní agent, který hledá dobrá řešení daného optimalizačního problému. Chcete-li použít algoritmus kolonií mravenců, je třeba problém s optimalizací převést na problém s nalezením nejkratší cesta na váženém grafu. V prvním kroku každé iterace každý mravenec stochasticky konstruuje řešení, tj. Pořadí, ve kterém by měly být sledovány okraje v grafu. Ve druhém kroku jsou porovnány cesty nalezené různými mravenci. Poslední krok spočívá v aktualizaci úrovní feromonů na každém okraji.

postup ACO_MetaHeuristic je    zatímco not_termination dělat        generateSolutions () daemonActions () pheromoneUpdate () opakovatukončete postup

Výběr hrany

Každý mravenec potřebuje zkonstruovat řešení pro pohyb v grafu. Chcete-li vybrat další hranu na své cestě, mravenec vezme v úvahu délku každé hrany, která je k dispozici od jeho aktuální polohy, a odpovídající úroveň feromonů. V každém kroku algoritmu se každý mravenec pohybuje ze stavu ${ displaystyle x}$ do stavu ${ displaystyle y}$, což odpovídá úplnějšímu mezilehlému řešení. Každý mravenec tedy ${ displaystyle k}$ spočítá množinu ${ displaystyle A_ {k} (x)}$ proveditelných expanzí do aktuálního stavu v každé iteraci a pravděpodobně se přesune na jednu z nich. Pro mravence ${ displaystyle k}$, pravděpodobnost ${ displaystyle p_ {xy} ^ {k}}$ stěhování ze státu ${ displaystyle x}$ do stavu ${ displaystyle y}$ závisí na kombinaci dvou hodnot, přitažlivost ${ displaystyle eta _ {xy}}$ pohybu, jak je vypočítáno nějakou heuristikou označující a priori vhodnost tohoto tahu a úroveň stezky ${ displaystyle tau _ {xy}}$ pohybu, což naznačuje, jak zdatné bylo v minulosti provést tento konkrétní tah. The úroveň stezky představuje a posteriori indikaci vhodnosti tohoto tahu.

Obecně platí, že ${ displaystyle k}$mravenec se pohybuje ze státu ${ displaystyle x}$ do stavu ${ displaystyle y}$ s pravděpodobností

${ displaystyle p_ {xy} ^ {k} = { frac {( tau _ {xy} ^ { alpha}) ( eta _ {xy} ^ { beta})}} { sum _ {z v mathrm {povoleno} _ {x}} ( tau _ {xz} ^ { alpha}) ( eta _ {xz} ^ { beta})}}}$

kde

${ displaystyle tau _ {xy}}$ je množství feromonu uloženého pro přechod ze stavu ${ displaystyle x}$ na ${ displaystyle y}$, 0 ≤ ${ displaystyle alpha}$ je parametr pro řízení vlivu ${ displaystyle tau _ {xy}}$, ${ displaystyle eta _ {xy}}$ je žádoucí přechod státu ${ displaystyle xy}$ (a priori znalosti, obvykle ${ displaystyle 1 / d_ {xy}}$, kde ${ displaystyle d}$ je vzdálenost) a ${ displaystyle beta}$ ≥ 1 je parametr pro řízení vlivu ${ displaystyle eta _ {xy}}$. ${ displaystyle tau _ {xz}}$ a ${ displaystyle eta _ {xz}}$ představují úroveň stezky a atraktivitu pro další možné přechody stavu.

Aktualizace feromonů

Stezky se obvykle aktualizují, když všichni mravenci dokončili své řešení, čímž se zvyšuje nebo snižuje úroveň stezek odpovídajících tahům, které byly součástí „dobrých“ nebo „špatných“ řešení. Příkladem globálního pravidla aktualizace feromonů je

${ displaystyle tau _ {xy} leftarrow (1- rho) tau _ {xy} + sum _ {k} Delta tau _ {xy} ^ {k}}$

kde ${ displaystyle tau _ {xy}}$ je množství feromonu uloženého pro přechod stavu ${ displaystyle xy}$, ${ displaystyle rho}$ je koeficient odpařování feromonů a ${ displaystyle Delta tau _ {xy} ^ {k}}$ je množství feromonu uloženého ${ displaystyle k}$ten mravenec, typicky daný pro a TSP problém (s pohyby odpovídajícími obloukům grafu) o

${ displaystyle Delta tau _ {xy} ^ {k} = { begin {cases} Q / L_ {k} & { mbox {if ant}} k { mbox {používá křivku}} xy { mbox {v jeho prohlídce}} 0 & { mbox {jinak}} end {případů}}}$

kde ${ displaystyle L_ {k}}$ jsou náklady na ${ displaystyle k}$prohlídka mravence (obvykle délka) a ${ displaystyle Q}$ je konstanta.

Společná rozšíření

Zde jsou některé z nejpopulárnějších variant ACO algoritmů.

Ant System (AS)

Ant System je první algoritmus ACO. Tento algoritmus odpovídá algoritmu uvedenému výše. Byl vyvinut společností Dorigo.^[25]

Ant Colony System (ACS)

V algoritmu Ant Colony System byl původní Ant System upraven ve třech aspektech: (i) výběr hran je předpojatý směrem k využití (tj. Upřednostňuje pravděpodobnost výběru nejkratších hran s velkým množstvím feromonu); (ii) při vytváření řešení mění mravenci hladinu feromonů na okrajích, které vybírají, použitím pravidla aktualizace místního feromonu; (iii) na konci každé iterace smí aktualizovat stopy pouze ten nejlepší mravenec pomocí upraveného globálního pravidla aktualizace feromonů.^[26]

Elitářský mravenčí systém

V tomto algoritmu ukládá nejlepší globální řešení feromon na svoji stopu po každé iteraci (i když tato stopa nebyla znovu navštívena) spolu se všemi ostatními mravenci.

Systém Max-Min Ant (MMAS)

Tento algoritmus řídí maximální a minimální množství feromonů na každé stopě. Pouze globální nejlepší prohlídka nebo iterační nejlepší prohlídka mohou přidat feromon na jeho stopu. Aby se zabránilo stagnaci vyhledávacího algoritmu, je rozsah možných množství feromonů na každé stopě omezen na interval [τ_max, τ_min]. Všechny hrany jsou inicializovány na τ_max vynutit si větší průzkum řešení. Stezky jsou znovu inicializovány na τ_max když se blíží stagnaci.^[27]

Hodnostní systém mravenců (ASrank)

Všechna řešení jsou řazena podle délky. Pouze stálý počet nejlepších mravenců v této iteraci může aktualizovat své pokusy. Množství uloženého feromonu je váženo pro každé řešení, takže roztoky s kratšími cestami ukládají více feromonu než roztoky s delšími cestami.

Kontinuální kolonie ortogonálních mravenců (COAC)

Mechanismus ukládání feromonů COAC je umožnit mravencům spolupracovat a efektivně hledat řešení. Pomocí metody ortogonálního návrhu mohou mravenci v proveditelné doméně rychle a efektivně prozkoumat své vybrané regiony se zvýšenou schopností a přesností globálního vyhledávání. Metodu ortogonálního návrhu a metodu adaptivního poloměru lze také rozšířit na další optimalizační algoritmy, které poskytují širší výhody při řešení praktických problémů.^[28]

Rekurzivní optimalizace kolonií mravenců

Jedná se o rekurzivní formu mravenčího systému, který rozděluje celou vyhledávací doménu na několik subdomén a řeší cíl na těchto subdoménách.^[29] Výsledky ze všech subdomén jsou porovnány a pár nejlepších z nich je povýšeno na další úroveň. Subdomény odpovídající vybraným výsledkům se dále dělí a postup se opakuje, dokud se nezíská výstup požadované přesnosti. Tato metoda byla testována na špatně vystavených problémech geofyzikální inverze a funguje dobře.^[30]

Konvergence

U některých verzí algoritmu je možné dokázat, že je konvergentní (tj. Je schopen najít globální optimum v konečném čase). První důkaz konvergence pro algoritmus mravenčí kolonie byl učiněn v roce 2000, algoritmus mravenčího systému založeného na grafech, a později pro algoritmy ACS a MMAS. Jako většina metaheuristika, je velmi obtížné odhadnout teoretickou rychlost konvergence. Analýza výkonu algoritmu kontinuální kolonie mravenců s ohledem na jeho různé parametry (strategie výběru hrany, metrika měření vzdálenosti a rychlost odpařování feromonů) ukázala, že jeho výkon a rychlost konvergence jsou citlivé na vybrané hodnoty parametrů, zejména na hodnotu rychlosti odpařování feromonů.^[31] V roce 2004 Zlochin a jeho kolegové^[32] ukázal, že algoritmy typu COAC lze asimilovat jako metody stochastický gradient, na křížová entropie a odhad distribučního algoritmu. Navrhli je metaheuristika jako "model založený na výzkumu ".

Aplikace

Problém s batohem: Mravenci preferují menší kapku medu před hojnějším, ale méně výživným cukrem

Algoritmy optimalizace kolonií mravenců byly použity u mnoha kombinatorická optimalizace problémy, od kvadratického přiřazení do protein skládací nebo směrování vozidel a mnoho odvozených metod bylo přizpůsobeno dynamickým problémům v reálných proměnných, stochastickým problémům, více cílům atd paralelní Bylo také použito k výrobě téměř optimálních řešení pro problém obchodního cestujícího. Mají výhodu nad simulované žíhání a genetický algoritmus přístupy podobných problémů, kdy se graf může dynamicky měnit; algoritmus kolonie mravenců může být spuštěn nepřetržitě a přizpůsoben změnám v reálném čase. To je zajímavé pro síťové směrování a městské dopravní systémy.

První algoritmus ACO se nazýval mravenčí systém^[25] a jejím cílem bylo vyřešit problém obchodního cestujícího, jehož cílem je najít nejkratší zpáteční cestu k propojení řady měst. Obecný algoritmus je relativně jednoduchý a je založen na sadě mravenců, z nichž každý provádí jeden z možných zpátečních letů po městech. V každé fázi se mravenec rozhodne přesunout z jednoho města do druhého podle některých pravidel:

1. Musí navštívit každé město přesně jednou;
2. Vzdálené město má menší šanci na výběr (viditelnost);
3. Čím intenzivnější je feromonová stezka položená na okraji mezi dvěma městy, tím větší je pravděpodobnost, že bude zvolena tato hrana;
4. Po dokončení cesty mravenec ukládá více feromonů na všechny okraje, které prošel, pokud je cesta krátká;
5. Po každé iteraci se stopy feromonů odpaří.

Problém s plánováním

• Problém se sekvenčním objednáváním (ÚPLATEK) ^[33]
• Plánování pracovních míst problém (JSP)^[34]
• Plánování otevřeného obchodu problém (OSP)^[35][36]
• Problém obchodu s permutací (PFSP)^[37]
• Problém totální pozdnosti jednoho stroje (SMTTP)^[38]
• Problém celkového váženého tardinessu jednoho stroje (SMTWTP)^[39][40][41]
• Problém s plánováním projektu omezeného zdroji (RCPSP)^[42]
• Problém s plánováním skupinového obchodu (GSP)^[43]
• Problém totální prodlevy jednoho stroje s časy nastavení závislými na sekvenci (SMTTPDST)^[44]
• Vícestupňový problém plánování plánovače (MFSP) se sekvenčně závislými časy nastavení / přepnutí^[45]

Problém s směrováním vozidla

• Kapacitní problém se směrováním vozidla (CVRP)^[46][47][48]
• Problém se směrováním vozidel ve více depech (MDVRP)^[49]
• Periodický problém se směrováním vozidla (PVRP)^[50]
• Problém s rozdělením dodávky vozidla (SDVRP)^[51]
• Stochastický problém s směrováním vozidla (SVRP)^[52]
• Problém s směrováním vozidla s vyzvednutím a doručením (VRPPD)^[53][54]
• Problém s směrováním vozidla s časovými okny (VRPTW)^{[55][56][57][58]}
• Časově závislý problém s směrováním vozidla s časovými okny (TDVRPTW)^[59]
• Problém s směrováním vozidel s časovými okny a více servisními pracovníky (VRPTWMS)

Problém s přiřazením

• Problém kvadratického přiřazení (QAP)^[60]
• Zobecněný problém s přiřazením (MEZERA)^[61][62]
• Problém s přiřazením frekvence (FAP)^[63]
• Problém s přidělením nadbytečnosti (RAP)^[64]

Nastavit problém

• Nastavit problém s krytem (SCP)^[65][66]
• Problém s oddílem (SPP)^[67]
• Váhově omezený problém s oddílem grafového stromu (WCGTPP)^[68]
• Obloukem vážený problém stromu L-mohutnosti (AWlCTP)^[69]
• Problém s více batohy (MKP)^[70]
• Maximální problém nezávislé sady (MIS)^[71]

Problém s dimenzováním zařízení ve fyzickém designu nanoelektroniky

• Optimalizace optimalizace kolonií mravenců (ACO) obvodu 45ms smyslového zesilovače založeného na CMOS mohla konvergovat k optimálnímu řešení za velmi minimální čas.^[72]
• Optimalizace reverzních obvodů založená na optimalizaci kolonií mravenců (ACO) by mohla výrazně zlepšit účinnost.^[73]

Optimalizace a syntéza antén

Loopback vibrátory 10 × 10, syntetizované pomocí algoritmu ACO^[74]

Unloopback vibrátory 10 × 10, syntetizované pomocí algoritmu ACO^[74]

K optimalizaci formy antén lze použít algoritmy kolonií mravenců. Jako příklad lze považovat antény RFID tagy založené na algoritmech mravenčích kolonií (ACO),^[75] loopback a unloopback vibrátory 10 × 10^[74]

Zpracování obrazu

Algoritmus ACO se používá při zpracování obrazu pro detekci hran obrazu a jeho propojení.^[76][77]

• Detekce hrany:

Graf je zde 2D obrazem a mravenci procházejí z jednoho pixelu ukládajícího feromon. Pohyb mravenců z jednoho pixelu na druhý je řízen lokální variací hodnot intenzity obrazu. Tento pohyb způsobuje, že se na okrajích ukládá nejvyšší hustota feromonu.

Následující kroky jsou součástí detekce hran pomocí ACO:^[78][79][80]

Krok 1: Inicializace:
Náhodně místo ${ displaystyle K}$ mravenci na obrázku ${ displaystyle I_ {M_ {1} M_ {2}}}$ kde ${ displaystyle K = (M_ {1} * M_ {2}) ^ { tfrac {1} {2}}}$ . Feromonová matice ${ displaystyle tau _ {(i, j)}}$ jsou inicializovány náhodnou hodnotou. Hlavní výzvou v procesu inicializace je stanovení heuristické matice.

Existují různé metody k určení heuristické matice. V níže uvedeném příkladu byla heuristická matice vypočítána na základě místních statistik: místní statistiky na pozici pixelu (i, j).

${ displaystyle eta _ {(i, j)} = { tfrac {1} {Z}} * Vc * I _ {(i, j)}}$

Kde ${ displaystyle I}$ je obrázek velikosti ${ displaystyle M_ {1} * M_ {2}}$
${ displaystyle Z = sum _ {i = 1: M_ {1}} sum _ {j = 1: M_ {2}} Vc (I_ {i, j})}$, což je normalizační faktor

${ displaystyle { begin {zarovnáno} Vc (I_ {i, j}) = & f left ( left vert I _ {(i-2, j-1)} - I _ {(i + 2, j + 1 )} right vert + left vert I _ {(i-2, j + 1)} - I _ {(i + 2, j-1)} right vert right. & + left vert I _ {(i-1, j-2)} - I _ {(i + 1, j + 2)} right vert + left vert I _ {(i-1, j-1)} - I_ { (i + 1, j + 1)} right vert & + left vert I _ {(i-1, j)} - I _ {(i + 1, j)} right vert + left vert I _ {(i-1, j + 1)} - I _ {(i-1, j-1)} right vert & + left. left vert I _ {(i-1, j +2)} - I _ {(i-1, j-2)} right vert + left vert I _ {(i, j-1)} - I _ {(i, j + 1)} right vert right) end {aligned}}}$

${ displaystyle f ( cdot)}$ lze vypočítat pomocí následujících funkcí:
${ displaystyle f (x) = lambda x, quad { text {pro x ≥ 0; (1)}}}$
${ displaystyle f (x) = lambda x ^ {2}, quad { text {pro x ≥ 0; (2)}}}$
${ displaystyle f (x) = { begin {cases} sin ({ frac { pi x} {2 lambda}}), & { text {pro 0 ≤ x ≤}} lambda { text {; (3)}} 0, & { text {else}} end {cases}}}$
${ displaystyle f (x) = { begin {cases} pi x sin ({ frac { pi x} {2 lambda}}), & { text {pro 0 ≤ x ≤}} lambda { ext{; (4)}} 0, & { text {else}} end {cases}}}$
Parametr ${ displaystyle lambda}$ v každé z výše uvedených funkcí upravuje příslušné tvary funkcí.
Krok 2 Proces výstavby:
Pohyb mravence je založen na 4-připojeno pixelů nebo 8-připojeno pixelů. Pravděpodobnost, s jakou se mravenec pohybuje, je dána rovnicí pravděpodobnosti ${ displaystyle P_ {x, y}}$
Krok 3 a krok 5 Proces aktualizace:
Feromonová matice se aktualizuje dvakrát. v kroku 3 stopa mravence (daná ${ displaystyle tau _ {(x, y)}}$ ) se aktualizuje, kde stejně jako v kroku 5 se aktualizuje rychlost odpařování stopy, která je dána níže uvedenou rovnicí.
${ displaystyle tau _ {nový} leftarrow (1- psi) tau _ {starý} + psi tau _ {0}}$, kde ${ displaystyle psi}$ je koeficient rozpadu feromonu ${ displaystyle 0 < tau <1}$

Krok 7 Proces rozhodování:
Jakmile se mravenci K přesunou o pevnou vzdálenost L pro N iteraci, rozhodnutí, zda je to hrana nebo ne, je založeno na prahové hodnotě T na feromonové maticiτ. Prahová hodnota pro níže uvedený příklad se vypočítá na základě Otsuova metoda.

Image Edge detekován pomocí ACO:
Níže uvedené obrázky jsou generovány pomocí různých funkcí daných rovnicí (1) až (4).^[81]

• Propojení hran:^[82] ACO se také osvědčilo v algoritmech spojování hran.

Další aplikace

• Predikce bankrotu^[83]
• Klasifikace^[84]
• Orientováno na připojení síťové směrování^[85]
• Směrování bez připojení^[86][87]
• Dolování dat^{[84][88][89][90]}
• Zlevněné peněžní toky při plánování projektu^[91]
• Distribuováno vyhledávání informací^[92][93]
• Návrh energetické a elektrické sítě^[94]
• Problém s plánováním pracovního postupu v mřížce^[95]
• Návrh inhibičního peptidu pro interakce proteinů a proteinů^[96]
• Inteligentní testovací systém^[97]
• Napájení design elektronických obvodů^[98]
• Skládání bílkovin^{[99][100][101]}
• Identifikace systému^[102][103]

Obtížnost definice

S algoritmem ACO je nejkratší cesta v grafu mezi dvěma body A a B vytvořena z kombinace několika cest.^[104] Není snadné přesně definovat, jaký algoritmus je nebo není mravenčí kolonií, protože definice se může lišit podle autorů a použití. Obecně lze říci, že algoritmy kolonií mravenců jsou považovány za osídlené metaheuristika přičemž každé řešení představuje mravenec pohybující se ve vyhledávacím prostoru.^[105] Mravenci označují nejlepší řešení a při optimalizaci vyhledávání berou v úvahu předchozí označení. Mohou být viděni jako pravděpodobnostní multiagent algoritmy používající a rozdělení pravděpodobnosti provést přechod mezi nimi opakování.^[106] Ve svých verzích pro kombinatorické problémy používají iterativní konstrukci řešení.^[107] Podle některých autorů je věcí, která odlišuje algoritmy ACO od jiných příbuzných (jako jsou algoritmy pro odhad distribuce nebo optimalizace roje částic) právě jejich konstruktivní aspekt. V kombinatorických problémech je možné, že nakonec bude nalezeno nejlepší řešení, i když by se žádný mravenec neosvědčil. V příkladu problému Traveling salesman tedy není nutné, aby mravenec skutečně cestoval po nejkratší trase: nejkratší cestu lze vytvořit z nejsilnějších segmentů nejlepších řešení. Tato definice však může být problematická v případě problémů se skutečnými proměnnými, kde neexistuje struktura „sousedů“. Kolektivní chování sociální hmyz zůstává zdrojem inspirace pro výzkumné pracovníky. Široká škála algoritmů (pro optimalizaci či nikoli) usilujících o sebeorganizaci v biologických systémech vedla ke konceptu „rojová inteligence ",^[10] což je velmi obecný rámec, do kterého zapadají algoritmy kolonií mravenců.

Stigmergy algoritmy

V praxi existuje velké množství algoritmů, které tvrdí, že jsou „mravenčími koloniemi“, aniž by vždy sdílely obecný rámec optimalizace kanonickými mravenčími koloniemi.^[108] V praxi se využívá výměna informací mezi mravenci prostřednictvím prostředí (princip zvaný „stigmergy „) se považuje za dostačující na to, aby algoritmus patřil do třídy algoritmů kolonií mravenců. Tento princip vedl některé autory k vytvoření termínu„ hodnota “k uspořádání metod a chování založených na hledání potravy, třídění larev, dělbě práce a kooperaci přeprava.^[109]

Související metody

• Genetické algoritmy (GA) spíše než jen jedno udržují soubor řešení. Proces hledání vynikajících řešení napodobuje evoluci, přičemž řešení se kombinují nebo mutují, aby se změnila skupina řešení, přičemž řešení nižší kvality jsou vyřazena.
• An odhad distribučního algoritmu (EDA) je evoluční algoritmus který nahrazuje tradiční operátory reprodukce operátory vedenými podle modelu. Takové modely se učí od populace pomocí technik strojového učení a představují jako pravděpodobnostní grafické modely, ze kterých lze vzorkovat nová řešení^[110][111] nebo generované z řízeného výhybky.^[112][113]
• Simulované žíhání (SA) je související globální optimalizační technika, která prochází prostor hledání generováním sousedních řešení aktuálního řešení. Nadřízený soused je vždy přijímán. Nižší soused je pravděpodobnostně přijat na základě rozdílu v kvalitě a teplotním parametru. S postupujícím algoritmem se mění parametr teploty, aby se změnila povaha hledání.
• Optimalizace reaktivního vyhledávání se zaměřuje na kombinování strojového učení s optimalizací přidáním interní zpětnovazební smyčky k vyladění volných parametrů algoritmu podle charakteristik problému, instance a místní situace kolem aktuálního řešení.
• Tabu vyhledávání (TS) je podobný simulovanému žíhání v tom, že oba procházejí prostorem řešení testováním mutací jednotlivého řešení. Zatímco simulované žíhání generuje pouze jedno mutované řešení, vyhledávání tabu generuje mnoho mutovaných řešení a přechází k řešení s nejnižší vhodností vygenerovaných. Aby se zabránilo cyklování a podporoval větší pohyb v prostoru řešení, je udržován seznam tabu částečných nebo úplných řešení. Je zakázáno přesouvat se k řešení, které obsahuje prvky seznamu tabu, který se aktualizuje, když řešení prochází prostorem řešení.
• Umělý imunitní systém Algoritmy (AIS) jsou modelovány na imunitním systému obratlovců.
• Optimalizace roje částic (PSO), a rojová inteligence metoda
• Inteligentní kapky vody (IWD), optimalizační algoritmus založený na roji založený na přirozených vodních kapkách tekoucích v řekách
• Algoritmus gravitačního vyhledávání (GSA), a rojová inteligence metoda
• Metoda shlukování kolonií mravenců (ACCM), metoda využívající shlukovací přístup, rozšiřující ACO.
• Stochastické difúzní vyhledávání (SDS), agent-based probabilistic global search and optimization technique best suited to problems where the Object function can be decomposed into multiple independent partial-functions

Dějiny

Vynálezci jsou Frans Moyson a Bernard Manderick. Mezi průkopníky oboru patří Marco Dorigo, Luca Maria Gambardella.^[114]

Chronologie algoritmů COA

Chronologie algoritmů optimalizace kolonií mravenců.

• 1959, Pierre-Paul Grassé vynalezl teorii stigmergy vysvětlit chování stavby hnízda v termiti;^[115]
• 1983 studoval Deneubourg a jeho kolegové kolektivní chování z mravenci;^[116]
• 1988, a Moyson Manderick mají článek o sebeorganizace mezi mravenci;^[117]
• 1989, práce Goss, Arona, Deneubourgu a Pasteelsa na kolektivní chování argentinských mravenců, který poskytne představu o algoritmech optimalizace kolonií mravenců;^[118]
• 1989, implementace modelu chování pro potraviny Eblingem a jeho kolegy;^[119]
• 1991 navrhl M. Dorigo mravenčí systém ve své disertační práci (která byla zveřejněna v roce 1992^[6]). Technická zpráva extrahovaná z práce a spoluautorem V. Maniezzo a A. Colorni^[120] byla zveřejněna o pět let později;^[25]
• 1994, Appleby a Steward z British Telecommunications Plc zveřejnili první aplikaci pro telekomunikace sítí^[121]
• 1995 navrhli Gambardella a Dorigo mravenec-q, ^[122] předběžná verze systému kolonií mravenců jako první estence systému mravenců; ^[25].
• 1996 navrhli Gambardella a Dorigo systém kolonií mravenců ^[123]
• 1996, vydání článku o mravenčím systému;^[25]
• 2000, Hoos a Stützle vynalezli max-min mravenčí systém;^[27]
• 1997, Dorigo a Gambardella navrhli systém kolonií mravenců hybridizovaný s lokálním vyhledáváním;^[26]
• 1997 Schoonderwoerd a jeho kolegové publikovali vylepšenou aplikaci pro telekomunikace sítě;^[124]
• 1998, Dorigo zahajuje první konferenci věnovanou algoritmům ACO;^[125]
• 1998 navrhuje Stützle iniciálku paralelní implementace;^[126]
• 1999 navrhli Gambardella, Taillard a Agazzi macs-vrptw, první systém více kolonií mravenců aplikovaný na problémy s směrováním vozidla s časovými okny, ^[127]
• 1999, Bonabeau, Dorigo a Theraulaz vydávají knihu zabývající se hlavně umělými mravenci^[128]
• 2000, speciální vydání časopisu Future Generation Computer Systems o mravenčích algoritmech^[129]
• 2000, první aplikace do plánování, plánovací sekvence a uspokojení omezení;
• 2000, Gutjahr poskytuje první důkazy o konvergence pro algoritmus mravenčích kolonií^[130]
• 2001, první použití algoritmů COA společnostmi (Eurobios a AntOptima );
• 2001 Iredi a jeho kolegové publikovali první více cílů algoritmus^[131]
• 2002, první aplikace v návrhu harmonogramu, Bayesovské sítě;
• 2002 navrhla Bianchi a její kolegové první algoritmus pro stochastický problém;^[132]
• 2004, Dorigo a Stützle publikují knihu Mravenčí optimalizace kolonií s MIT Press ^[133]
• 2004, Zlochin a Dorigo ukazují, že některé algoritmy jsou ekvivalentní s stochastický gradient, metoda cross-entropie a algoritmy pro odhad distribuce^[32]
• 2005, první aplikace do skládání bílkovin problémy.
• 2012 Prabhakar a kolegové publikují výzkum týkající se fungování jednotlivých mravenců komunikujících v tandemu bez feromonů, odrážející principy organizace počítačové sítě. Komunikační model byl porovnán s protokol kontroly přenosu.^[134]
• 2016, první aplikace na návrh peptidové sekvence.^[96]
• 2017, úspěšná integrace multikriteriální rozhodovací metody PROMETHEE do algoritmu ACO (Algoritmus HUMANT ).^[135]

Reference

Publikace (výběr)

• M. Dorigo, 1992. Optimalizace, učení a přirozené algoritmy, Disertační práce, Politecnico di Milano, Itálie.
• M. Dorigo, V. Maniezzo & A. Colorni, 1996. "Ant System: Optimalizace kolonií spolupracujících agentů ", IEEE Transactions on Systems, Man, and Cybernetics - Part B, 26 (1): 29-41.
• M. Dorigo & L. M. Gambardella, 1997. "Ant Colony System: Kooperativní přístup k učení problému Traveling Salesman ". IEEE Transactions on Evolutionary Computation, 1 (1): 53–66.
• M. Dorigo, G. Di Caro a L. M. Gambardella, 1999. "Ant Algoritmy pro diskrétní optimalizaci ". Umělý život, 5 (2): 137–172.
• E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: Od přírodních po umělé systémy, Oxford University Press. ISBN  0-19-513159-2
• M. Dorigo & T. Stützle, 2004. Optimalizace kolonie mravenců, MIT Stiskněte. ISBN  0-262-04219-3
• M. Dorigo, 2007. „Optimalizace kolonie mravenců“. Scholarpedia.
• C. Blum, 2005 "Optimalizace kolonií mravenců: Úvod a nejnovější trendy ". Physics of Life Reviews, 2: 353-373
• M. Dorigo, M. Birattari a T. Stützle, 2006 Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique. TR / IRIDIA / 2006-023
• Mohd Murtadha Mohamad, „Plánování pohybu kloubových robotů využívající strategii hledání mravenců“, Journal of Information Technology - Special Issues in Artificial Intelligence, Vol.20, č. 4, str. 163–181, prosinec 2008, ISSN  0128-3790.
• N. Monmarché, F. Guinand a P. Siarry (eds), „Artificial Ants“, srpen 2010, vázaná kniha 576 s.ISBN  978-1-84821-194-0.
• A. Kazharov, V. Kureichik, 2010. "Algoritmy optimalizace kolonií mravenců pro řešení přepravních problémů ", Journal of Computer and Systems Sciences International, sv. 49. Č. 1. str. 30–43.
• CM. Pintea, 2014, Pokroky v biologicky inspirovaných výpočtech pro problém kombinatorické optimalizace Springer ISBN  978-3-642-40178-7
• K. Saleem, N. Fisal, M. A. Baharudin, A. A. Ahmed, S. Hafizah a S. Kamilah, „Ant-kolonie inspirovaná samooptimalizovaný směrovací protokol založený na architektuře mezivrstvy pro bezdrátové senzorové sítě“, WSEAS Trans. Commun., Sv. 9, č. 10, s. 669–678, 2010. ISBN  978-960-474-200-4
• K. Saleem a N. Fisal, „Algoritmus Enhanced Ant Colony pro samooptimalizované směrování dat v bezdrátových senzorových sítích“, Networks (ICON) 2012, 18. mezinárodní konference IEEE, str. 422–427. ISBN  978-1-4673-4523-1
• Abolmaali S, Roodposhti FR. Optimalizace portfolia pomocí metody Ant Colony a případová studie na teheránské burze. Účetní deník. 2018 března; 8 (1).

externí odkazy

• Stránka Optimalizace kolonií mravenců Scholarpedia
• Domovská stránka optimalizace kolonií mravenců
• „Ant Colony Optimization“ - ruská vědecká a výzkumná komunita
• AntSim - Simulace algoritmů kolonií mravenců
• Řešič MIDACO Obecný optimalizační software založený na optimalizaci kolonií mravenců (Matlab, Excel, VBA, C / C ++, R, C #, Java, Fortran a Python)
• University of Kaiserslautern, Germany, AG Wehn: Ant Colony Optimization Applet Vizualizace Traveling Salesman řešená mravenčím systémem s řadou možností a parametrů (Java Applet)
• Ant Farm Simulator
• Simulace algoritmu mravence (Java Applet)
• Rámec systému Java Ant Colony System