Vliv PRT parametru na řízení asynchronního SOMA algoritmu

Pavel  VAŘACHA

Univerzita Tomáše Bati ve Zlíně
Fakulta aplikované informatiky, Nad Stráněmi 4511, 760 05 Zlín, Česká republika
email: varacha@fai.utb.cz

Abstrakt:
SOMA – Self – Organizing Migration Algorithm je velmi efektivním nástrojem optimalizace pomocí evolučních algoritmů, což už bylo dříve dokázáno na mnoha problémech z reálného života. Tento článek představuje novou inovativní strategii, jak nastavit jeden z nejdůležitějších řídících parametrů asynchronně distribuovaného SOMA, tzv. PRT parametr, která činí tento algoritmus ještě efektivnějším. Aby bylo možno statisticky dokázat dopad této inovace, bylo provedeno 996.3 * 106 jednotlivých vyhodnocení pro 10 různých testovacích funkcí. Uplatnění strategie navržené tímto článkem může přinést lepší výsledky v asi 50 % případů optimalizovaných funkcí. Tato metoda může přinést úspěšné řešení i vpřípadech, ve kterých standardní nastavení SOMA podává nedostatečné výsledky.

Abstract:
SOMA - Self-Organizing Migration Algorithm is highly effective tool of evolutionary optimization as already proven on many real life problems. This article introduces new innovative strategy how to set one of the most important asynchronously distributed SOMA control parameter PRT, which makes the algorithm even more efficient. 996.3E6 single evaluations have been calculated for 10 different test functions to statistically prove impact of this improvement. Application of the strategy proposed by this article can bring better results in about 50% of optimized functions and possibly even achieve breakthrough in cases, which standard SOMA setting does not perform well.

Klíčová slova:
asynchronní, distribuovaný, SOMA, optimalizace, evoluční algoritmy, PRT, PRTVektor

Keywords:
asynchronous, distributed, SOMA, optimization, evolutionary algorithm, PRT, PRTVector.

Úvod

 V posledních letech byla vyvinuta široká třída algoritmů pro stochastickou optimalizaci, tzn. pro optimalizaci systémů, ve kterých funkční závislost mezi nezávislými vstupními proměnnými x a výstupem (objektivní funkcí) y systému S je neznámý. Použitím stochastických optimalizačních algoritmů, jako jsou genetické algoritmy, simulované žíhání nebo diferenciální evoluce, je systém konfrontován s náhodným vstupním vektorem. Odezva systému je poté využita tímto algoritmem k nastavení vstupního vektoru takovým způsobem, aby systém produkoval žádaný výstup nebo cílovou hodnotu. Tento proces má přitom iterativní charakter. [1]

 SOMA – Self – Organizing Migration Algorithm je založený  na samoorganizujícím se chování skupin jedinců v „sociálním prostředí“. Může být také klasifikován jako evoluční algoritmus navzdory faktu, že žádné nové generace jedinců během procesu prohledávání nevznikají (v souladu s filozofií tohoto algoritmu). V průběhu generace, která je zde nazývána „migračním kolem“ nebo anglicky „migration loop“ (ML) se jedinci pouze přesouvají (migrují) po hyper-ploše účelové funkce „cost function“. Tento algoritmus byl publikován v široké škále časopisů, knih, mezinárodních konferencí, sympózií a také prezentován v celé řadě přednášek [2,3,4].

 Nevýhodou SOMA, stejně tak jako ostatních evolučních algoritmů, je jejich silná závislost na nastavení řídících parametrů. V průběhu celé škály statistických testů bylo zjištěno, že SOMA je v tomto ohledu více citlivá než jiné evoluční algoritmy. Nicméně existuje nastavení řídících parametrů, které je téměř univerzální a SOMA v něm dobře pracuje pro většinu experimentů a simulací. [5] Tento článek představuje průlomovou strategii nastavení kontrolních parametrů SOMA tak, aby bylo možno dosáhnout ještě lepších výsledků.

DASOMA  All-to-One

 Ačkoliv existuje několik verzí SOMA, tento článek je zaměřen pouze na distribuovanou asynchronní verzi All-to-one (DASOMA). Všechny základní principy DASOMA All-to-one, potřebné k pochopení provedených experimentů, jsou popsány níže.

Definice parametrů

 Ke spuštění DASOMA je třeba definovat následující řídící parametry: Step, PathLength, PopSize, PRT. Také musí být definována účelová funkce. Zjednodušeně řečeno vrací účelová funkce skalár, který přímo slouží jako měřítko vhodnosti.

Vytvoření populace

 Populace jedinců je vytvořena náhodně. Každý parametr každého jedince je náhodně zvolen z daného rozsahu <Low, High.>.

Migrační kolo

 Každý jedinec populace (PopSize) je vyhodnocen účelovou funkcí a pro dané migrační kolo je vybrán Leader (jedinec s největší vhodností).  Následně všichni jedinci začnou „skákat“ (podle definice parametru Step) směrem k Leaderovi.  Každý jedinec je vyhodnocen po každé změně pozice účelovou funkcí. Migrace pokračuje dokud jedinec nedosáhne nové pozice stanovené parametrem PathLength. Nová pozice xi,j  je po každém skoku spočítána pomocí (1). Toto je znázorněno graficky na obr.1. Jedinec se poté navrátí na pozici, kde nalezl nejlepší vhodnost na své migrační trajektorii.

(1)

kde  t Î <0, po kroku Step, PathLegth> a ML je aktuální migrační kolo

 Před tím než jedinec začne své skoky směrem k Leaderovi je vygenerováno náhodné číslo rnd (unikátní pro každý parametr jedince). Poté je toto číslo porovnáno s PRT. Pokud je vygenerované náhodné číslo větší než PRT, příslušný parametr jedince je nastaven na 0 ve smyslu PRTVektoru:

pokud rndj < PRT pak PRTVectorj = 0 jinak 1

(2)

kde  rnd Î <0, 1> a  j = 1, … nparam

j	rndj	PRTVector
1	0.234	1
2	0,545	0
3	0,865	0
4	0,012	1

Tab. 1: Příklad PRTVektoru pro čtyřparametrového jedince a PRT = 0.3

 Tímto se jedinec pohybuje po N-k dimenzionálním subprostoru, který vznikl redukcí původního prostoru.  Tato skutečnost významně přispívá vysoké robustnosti tohoto algoritmu. Dřívější experimenty ukázaly, že bez použití PRT DASOMA tíhne k uváznutí v lokálním extrému, spíše než k nalezení globálního optima. [5]

Podmínka ukončení algoritmu

 Pokud je dosaženo stanoveného počtu migračních kol, algoritmus zastaví a vrátí se k nejlepšímu nalezenému řešení.

Obr. 1: PRTVektor a jeho dopad na pohyb jedince

Doporučené nastavení DASOMA

 Na základě velkého množství experimentů, které autor SOMA (prof. Zelinka) provedl, bylo stanoveno doporučené nastavení tohoto algoritmu:

Parameter name	Doporučený rozsah
PathLenght	<1.1 ;3>
Step	<0.11, PathLength>
PRT	<0,1>
PopSize	<10, podle uživatele>

Tab. 2: Parametry SOMA a jejich doporučené hodnoty

 Jak můžete vidět na obr. 2, publikovaném v [5], PRT parametr byl testován v rozsahu <0.1; 0.9>  a podával nejlepší výsledky pro PRT Î <0.1 ; 0.3>.

 Tento článek porovnává chování DASOMA vpůvodně navrhovaném rozsahu PRT snově zkoumaným rozsahem PRTÎ <0.005 ; 0.1>. Následující kapitola popisuje důvody, proč tento rozsah nebyl nikdy před tím brán vpotaz.

Obr. 2: Závislost SOMA na velikosti PRT [5]

Definice problému nulového PRTVektoru

Všechny experimenty zmíněné v [5] byly prováděny na účelové funkci se 100 parametry. Přirozeně délka PRTVektoru (L) byla také 100. Pravděpodobnost P0, že PRTVektor bude vygenerován jako nulový vektor (vektor, který obsahuje samé nuly, viz také (2)) je velmi malá pro PRT Î <0.1 ; 0.3>.

P0 = (1 – PRT)L

(3)

PRT	P0
0,005	0,60577
0,01	0,366032
0,03	0,047553
0,05	0,005921
0,07	0,000705
0,1	2,66*10-05
0,2	2,04*10-10
0,3	3,23*10-16

Tab. 3: Pravděpodobnost nulového PRTVektoru pro L = 100

Obr. 3: Pravděpodobnost nulového PRTVektoru pro L = 100

 Nicméně s rostoucími hodnotami L nebo PRT dramaticky roste i P0.

PRT	P0
0,005	0,886654
0,01	0,785678
0,03	0,481417
0,05	0,291989
0,07	0,175223
0,1	0,079766
0,2	0,004722
0,3	0,000192

Tab. 4: Pravděpodobnost nulového PRTVektoru pro L = 25

Obr. 3: Pravděpodobnost nulového PRTVektoru pro L = 25

Pokud je pro jedince vygenerován nulový PRTVektor, jedinec se v daném migračním kole nepohybuje a účelová funkce je vždycky vyhodnocena se stejnými parametry např. pokud Step = 0.11 a PathLength = 3 je zbytečně vyplýtváno 27 vyhodnocení účelové funkce.  Tato ztráta výpočetního času je velmi nepravděpodobná pro L = 100 a vyplýtvaný čas je velmi malý, pokud je vyhodnocována pouze teoretická funkce , viz (6) až (15).

 Pokud však uvažujeme některý z problémů reálného života, např. optimalizaci parametrů teplárny [6],  L = 24 (jeden parametr pro každou hodinu dne). Pokud se PRT = 0.1 je P0 = 0.79, tzn., že téměř 8 % vyhodnocení účelové funkce je duplicitní – tedy „vyplýtvaný“ výpočetní čas. Současně je každé vyhodnocení účelové funkce velmi časově náročné (dokonce v řádu minut [7]), protože v průběhu tohoto procesu musí být prohledána rozsáhlá databáze.

 Tyto skutečnosti vedou k zavedení jednoduchého opravného mechanismu pro případ vygenerování nulového PRTVektoru:

Pokud je vygenerován nulový PRTVektor je tento vektor nahrazen novým PRTVektorem.

(4)

Díky zavedení pravidla (4) je P0 vždycky 0. Místo P0 můžeme ovšem pracovat s pravděpodobností P1, která definuje výskyt PRTVektoru, jež obsahuje pouze jednu jedničku.

P1 = (1 – PRT)L+ L * PRT * (1 - PRT)(L - 1)

(5)

PRT	P1
0,005	0,910178
0,01	0,735762
0,03	0,194622
0,05	0,037081
0,07	0,006013
0,1	0,000322
0,2	5,3*10-09
0,3	1,42*10-14

Tab. 5: P1 pro L = 100

Obr. 5: P1 pro L = 100

 Aplikace (4) na DASOMA umožňuje nastavit PRT parametr v rozsahu (0;0.1>, který byl dříve nedosažitelný díky vysokým hodnotám P0.

 Následující experiment je navržen s cílem statisticky prozkoumat efektivitu DASOMA pro PRT Î (0; 0.1>  a porovnat ji s výsledky dosaženými při PRT  Î <0.1; 0.3>, jinými slovy experiment měří závislost chování DASOMA na hodnotě P1.

Metody měření

 Pro tento experiment bylo vybráno 10 různých testovacích funkcí (6) - (15). Všechny tyto funkce, stejně jako řídící parametry DASOMA, vychází z [5] a jsou použity stejně jako je použil prof. Zelinka při svých experimentech s původní verzí SOMA.

     PopSize = 60, PathLength = 3, Step = 0.11 a počet parametrů = 100. Tato nastavení jsou stejná pro všechny funkce. Počet migračních kol a meze parametrů jednotlivých funkcí se mění podle tab. 6.

(6)

(7)

(8)

(9)

(10)

kdea

(11)

(12)

(13)

(14)

(15)

Funkce	ML	Levá mez	Pravá mez
Ackley (6)	400	-30	30
EggHolder (7)	800	-512	512
Griewangk (8)	200	-100	100
Masters (9)	400	-5	5
Michalewicz (10)	200	0	3,1415
Rana (11)	125	-500	500
Rastrigin (12)	400	-5,12	5,12
Rosenbrock (13)	125	-2,048	2,048
Schwefel (14)	400	-512	512
SineWave (15)	400	-10	10

Tab. 6: Testovací funkce, ML a jejich meze

Výsledky

 Pro každou testovanou funkci byla optimalizace (hledání globálního minima) pomocí DASOMA opakována 100 x pro různé PRT. PRT = {0.005, 0.01, 0.03, 0.05, 0.07, 0.1, 0.2, 0.3}. Celkem bylo provedeno 800 opakování na hardwareové platformě SuperMicro server [8]. Nejlepší dosažené výsledky ukazuje tabulka 7. Celkem bylo vypočítáno 996.3 * 106 vyhodnocení účelové funkce. Pravidlo (4) bylo použito ve všech případech.

 Tabulka 8 ukazuje normalizované výsledky. Nejlepší případ pro danou testovací funkci je nastaven jako 0 (základna) a všechny ostatní případy jsou vyjádřeny jako jeho procentuální odchylka. Obr. 6 a obr. 7 ukazují nejlepší výsledky dosažené pro jednotlivé testovací funkce a různá nastavení PRT, v souladu s tab. 8.

Funkce, PRT:	0,005	0,01	0,03	0,05	0,07	0,1	0,2	0,3
Ackley	3396,471	3385,351	3369,294	3367,189	3367,029	3369,882	3436,885	3535,938
EggHolder	-60853,8	-60689,4	-58605,1	-55524,3	-56757,5	-64070,9	-53516,6	-47802,1
Griewangk	3,648798	1,997721	1,141929	1,06382	0,984458	0,887719	0,8797	1,020321
Masters	-73,4884	-73,4238	-71,2417	-69,7727	-73,1274	-78,0405	-70,2647	-62,7373
Michalewicz	-93,4514	-95,2696	-98,3304	-98,9742	-98,6515	-97,467	-93,3395	-90,3364
Rana	-30867	-30231,2	-27648,7	-25222,9	-23317,8	-21496,6	-33287,1	-33768,3
Rastrigin	-995940	-997159	-998127	-990621	-975417	-949321	-881218	-835457
Rosenbrock	4560,49	3226,998	1255,186	703,7341	483,8931	362,4504	282,7966	262,769
Schwefel	-41837,5	-41871,1	-41890,8	-41742,6	-41248,4	-40193,7	-36314,4	-33433,1
SineWave	-669,678	-660,256	-617,631	-578,989	-550,005	-519,842	-464,395	-446,799

Tab. 7: Nejlepší dosažené výsledky pro různé testovací funkce a pro různé nastavené PRT

Funkce, PRT:	0,005	0,01	0,03	0,05	0,07	0,1	0,2	0,3
Ackley	0,008744	0,005442	0,000673	4,76E-05	0	0,000847	0,020747	0,050166
EggHolder	0,050211	0,052778	0,085308	0,133392	0,114146	0	0,164728	0,253919
Griewangk	3,147777	1,270912	0,29809	0,209299	0,119085	0,009116	0	0,159852
Masters	0,058331	0,059158	0,08712	0,105943	0,062956	0	0,099639	0,196093
Michalewicz	0,055801	0,037431	0,006505	0	0,003261	0,015229	0,056931	0,087273
Rana	0,085919	0,104747	0,181223	0,25306	0,309478	0,36341	0,01425	0
Rastrigin	0,002191	0,000969	0	0,00752	0,022753	0,048897	0,117128	0,162975
Rosenbrock	16,35551	11,28074	3,776765	1,678147	0,841515	0,37935	0,076217	0
Schwefel	0,001273	0,00047	0	0,003538	0,015335	0,040512	0,133118	0,201899
SineWave	0	0,014069	0,07772	0,135422	0,178702	0,223744	0,306541	0,332815

Tab. 8: Normované nejlepší dosažené výsledky pro různé testovací funkce a pro různé nastavené PRT

Obr. 6: Testovací funkce s dosaženými nejlepšími výsledky pro PRT Î <0.005; 0.07>

Obr. 7: Testovací funkce s dosaženými nejlepšími výsledky pro PRT Î <0.1; 0.3>.

Diskuze

Z deseti testovaných funkcí (6) – (15) měla DASOMA v tomto experimentu lepší výsledky u pěti pro PRT Î <0.005; 0.07>  a u dalších pěti pro PRT Î <0.1; 0.3>. Tato skutečnost je důležitým průlomem v přístupu k PRT parametru. Původně doporučovaný rozsah PRT Î <0.1; 0.3> může být rozšířen na PRT Î <0.01; 0.3>.  Dokonce se ukázalo, že 50 % testovacích funkcí DASOMA optimalizuje efektivněji, pokud je PRT Î <0.01; 0.07>. Rostoucí hodnota P1 může pozitivně ovlivnit dosažené výsledky. Nicméně efektivita DASOMA klesá vždycky, pokud je P1 > 0.74.

Na základě dosažených výsledků můžeme formulovat závěrečné doporučení:

Pokud DASOMA nepodává uspokojivé výsledky pro PRT Î <0.1; 0.3>, je možné aplikovat pravidlo (4) a snížit hodnotu PRT parametru, aby bylo dosaženo vyšší P1.

Toto opatření má velmi dobrou pravděpodobnost přinést zvýšenou kvalitu výsledku.

Poděkování

Tato práce byla provedena za finanční podpory výzkumného projektu NPVII-2C06007 Ministerstva školství, mládeže a tělovýchovy České republiky a European Regional Development Fund vrámci projektu CEBIA-Tech No. CZ.1.05/2.1.00/03.0089

Reference

[1] E. Král, V. Dolinay, L. Vašek, P. Vařacha, Usage of PSO Algorithm for Parameters Identification of District Heating Network Simulation Model. In  14th WSEAS International Conference on Systems. Latest Trands on Systems.Volume II,  Rhodes, WSEAS Press (GR) , 2010. p. 657-659.  ISBN/ISSN: 978-960-474-214-1.
[2] L. Kouřil,I. Zelinka,Evolutionary Synthesis of Rules for Programming the Turing Machine.Trilobit,2010 ,roč.2010 ,č.2 ,s.10-21. ISSN:1804-1795
[3] Z. Oplatková, I. Zelinka, Investigation on Shannon - Kotelnik Theorem Impact on DASOMA Algorithm Performance. In  European Simulation Multiconference, 2005, Riga, ESM , 2005.   p. 66-71.  ISBN/ISSN: 1-84233-112-4.
[4] R. Šenkeřík, I.  Zelinka, Optimization and Evolutionary Control of Chemical Reactor. In  10th International Research/Expert Conference Trends in the Development of Machinery and Associated Technology, TMT, Zenica, Bosna and Hercegovina, 2006,   p. 1171-1174.  ISBN/ISSN: 9958-617-30-7.
[5] I. Zelinka, Studies in Fuzziness and Soft Computing,  New York : Springer-Verlag, 2004.
[6] P. Vařacha, Impact of Weather Inputs on Heating Plant - Agglomeration Modeling. In  Proceedings of the 10th WSEAS Ing. Conf. on Neural Networks,  Athens, WSEAS World Science and Engineering Academy and Science , 2009. p. 159-162.  ISBN/ISSN: 978-960-474-065-9.
[7] B. Chramcov, Forecast of heat demand according the Box-Jenkins methodology for specific locality. In  Latest Trends on Systems (Volume I),  Rhodes, WSEAS Press (GR) , 2010, p. 252-256,  ISBN/ISSN: 978-960-474-199-1.
[8] M. Bližňák, T. Dulík, Virtual Laboratory of Microprocessor Technology Applications. In . Annals of DAAAM for 2010 & PROCEEDINGS of the 21st International DAAAM Symposium. Vienna : DAAAM International, 2010. s. 345-346. ISBN 978-3-901509-73-5, ISSN 1726-9687.