SamoOrganizující se Migrační Algoritmus (SOMA) vznikl v roce 1999 a je významný tím, že jeho autorem je prof. Ing. Ivan Zelinka, Ph.D. z domovské univerzity. Algoritmus se od klasických evolučních algoritmů odlišuje tím, že noví potomci nevznikají křížením rodičů, ale jeho princip je založen na kooperativním migrování jedinců v prostoru řešení, tedy k prohledávání prostoru řešení. Proto se cykly algoritmu nenazývají generace, ale migrační kola, během kterých se střídají fáze soutěžení a spolupráce. Ve fázi spolupráce si jedinci vyměňují informace o nejlepším řešení a ve fázi soutěže se přesunují směrem k nejlepšímu řešení, přičemž se sami snaží najít nejlepší řešení. Samoorganizace populace spočívá v tom, že se jedinci vzájemně ovlivňují, mohou vnikat skupiny jedinců, které migrují společně, rozpadají se a zase spojují. Algoritmus je inspirován podobným chováním v přírodě, kdy skupiny jedinců (smečka vlků, kolonie termitů, roj včel) spolupracují při hledání potravy.
Slovní popis algoritmu SOMA:
| 1. | Stanovení parametrů algoritmu. |
| 2. | Tvorba populace - vytvoření náhodné prvotní populace podle specimenu. |
| 3. | Migrační kola – každý jedinec v populaci je ohodnocen účelovou funkcí a
je zvolen vedoucí jedinec s nejlepší hodnotou účelové funkce. Každý jedinec se začne opakovaně pomocí
skoků definovaných parametrem Step pohybovat směrem k vedoucímu jedinci, dokud není dosaženo cílové pozice,
která vychází z parametru PathLenght. Pohyb jedince je ovlivňován pertubačním vektorem, slouží k rušení pohybu
jedince, jedná se o stochastickou složku v algoritmu, která se dá přirovnat k mutaci. |
| 4. | Ukončení a vyhodnocení – pokud není diverzita mezi nejlepším a nejhorším jedincem menší než MinDiv a
neproběhlo více migračníh kol než je hodnota parametru Migrace, pokračuje se bodem dva, jinak dojde k ukončení a z výsledné populace se vrací nejlepší jedinec.
|
Popis parametrů:
| Parametr |
Typ |
Popis |
Doporučená hodnota |
| PathLength |
Řídící |
Délka cesty, určuje, jak daleko se zastaví aktivní jedinec od vedoucího jedince. |
[1,1 ; 5] |
| Step |
Řídící |
Určuje zrnitost, s jakou bude mapována cesta aktivního jedince. Vyšší hodnota urychluje algoritmus, ale vniká riziko uváznutí v lokálním extrému. |
[0,11 ; PathLength] |
| PRT |
Řídící |
Petrubace, slouží k vytváření petrubačního vektoru, který určuje, zdali se aktivní jedinec bude pohybovat přímo k vedoucímu jedinci, či ne. |
[0 ; 1] |
| D |
Řídící |
Počet parametrů účelové funkce. |
Dle účelové funkce |
| PopSize |
Řídící |
Počet jedinců, kteří budou tvořit populaci. |
0,2 až 0,5D pro multimodální funkce, pro unimodální může být nižší. |
| Migrace |
Ukončovací |
Udává, kolik migračních kol proběhne. |
10 a více |
| MinDiv |
Ukončovací |
Určuje minimální diverzitu, tedy jaký je povolen maximální rozdíl mezi nejhorším a nejlepším jedincem v populaci. |
Libovolný |