Algoritmus S-ACO
Algoritmus byl poprvé publikovaný Marcem Dorigem a Thomasem Stützlem v roce 1992 (www). Od té doby byla uvedena celá řada jeho variant, které vycházejí ze stejné myšlenky, kterou je napodobování mravenčího chování. Výpočetní metoda řešící komplexní problémy je potom vyjádřena jako hledání optimální cesty v grafu. V aplikaci je implementována jednoduchá didaktická varianta algoritmu autory nazvaná jako Simple Ant Colony Optimization algorithm (S-ACO).
Úkolem mravenců v přírodě je sehnat co nejvíce potravy a po co nejkratší cestě (tedy v nejkratším čase) ji donést zpět do mraveniště. Při cestě zpět mravenci vypouštějí tzv. feromony, chemické látky které dělají cestu pro ostatní mravence více atraktivnější. Kratší cesta je proto postupem času značkována feromony silněji než cesta delší, kde feromony se s časem vypařují, a delší cesta tedy přestává být pro mravence atraktivní.
Na podobném principu pracuje i v aplikaci implementovaný algoritmus S-ACO. Uživatelem nadefinovaný počet mravenců postupně prochází bludiště, kdy výchozí buňkou pro ně je vstupní buňka bludiště a směr jejich pohybu (tzn. výběr následujících buněk) se řídí intenzitou feromonu na každé jim sousedící buňce. Tedy na počátku je jejich pohyb náhodný. Toto je tzv. forward mód pohybu.
Jakmile se některý z mravenců ocitne na buňce výstupní (nalezne jídlo), uloží se trasa, kterou urazil, a mravenec se vrací po už optimalizované trase (tzn. trase, ve které byly eliminovány zacyklení) zpět k výchozí buňce, přičemž se v každém jeho kroku aktualizují (zvyšují) hodnoty feromonů na buňkách, na kterých se v daný okamžik nachází. Zjednodušeně řečeno, čím více je cesta využívaná, tím větší je pravděpodobnost jejího výběru v budoucnosti. V aplikaci je hodnota feromonů na dané buňce zvýrazněna intenzitou jejího červeného zbarvení. Toto je tzv. backward mód mravence.
Jakmile všichni mravenci vykonají pohybovou akci, nad každou buňkou bludiště se provede procedura vypařování feromonů, tedy poníží se hodnoty feromonů o definovaný koefient vypařování. Takto je zajištěno, aby algoritmus nalezl co největší počet možných řešení bludiště. A tím je ukončen jeden cyklus algoritmu, tzv. iterace.
S ohledem na to, že uvedený optimalizační algoritmus negarantuje stoprocentní nalezení optimálního řešení, je nutné nadefinovat podmínky, při jejichž splnění se algoritmus ukončí. První ukončovací podmínkou je nastavení konečného počtu iterací, které algoritmus provede. Druhou implementovanou podmínkou ukončení algoritmu je jeho konvergence, tedy že se charakteristiky nalezeného řešení všemi mravenci s časem blíží k požadovanému řešení, tzn. nejkratší trase. Tato situace nastává, když feromony indikující řešení mají tak vysokou hodnotu, že každá další iterace nepřináší žádnou další změnu. Toto řešení je implementováno za pomoci uživatelem definované ukončovací podmínky T. Zjednodušeně řečeno, pokud není T-krát nalezeno lepší řešení bludiště, je doposud nejlepší nalezené řešení označeno za celkově nejlepší a algoritmus se ukončí.
|
|
