Viackriteriálne evolučné algoritmy

Abstrakt

Strojové učenie poskytuje množstvo mocných nástrojov, ktorými je možné riešiť komplikované problémy. Osobitnú kategóriu tvoria evolučné algoritmy, ktoré využívajú operátory inšpirované evolučnou teóriou. Sú vhodné na riešenie zložitých problémov, akým je aj viackriteriálna optimalizácia. V tomto prípade sa nehladajú riešenia, ktoré spĺňajú len jedno kritérium, ale je ich niekoľko.

Úvod

Evolučné algoritmy našli uplatnenie v množstve oblastí, akými sú financie (oceňovanie, výber akcií, manažment rizika), predpovedanie časových radov, ekonomické modelovanie, kontrola procesov, ale tiež v spracovaní signálov a obrázkov, hrách, či v medicíne (5) (12). Najproduktívnejšie však sú pri riešení problémov, kde sú slabo pochopené vzťahy medzi vstupnými premennými, sú dostupné veľké množstvá elektronických údajov, existujú dobré simulátory, konvenčná matematická analýza zlyháva a dostatočné sú približné riešenia (12). Množstvo z týchto problémov vyžaduje definíciu viacerých kritérií.

Viackritérová optimalizácia

Viackritériový optimalizačný problém je hľadanie hodnoty rozhodovacích premenných,

z celkovej množiny vektorov v prehľadávanom priestore, ktoré bude riešením:

.

kde k je počet kritériových funkcií s obmedzeniami. Riešenie

sa nazýva pareto dominantné nad iným riešením

ak je lepšie aspoň v plnení jedného kritéria a nie je v žiadnom horšie. Tento vzťah sa značí

Pri viacerých kritériách nie je možné nájsť jediné najlepšie riešenie, pretože kritériá si môžu protirečiť. Preto sa hľadajú pareto optimálne riešenia, teda riešenia, nad ktorými nie je žiadne riešenie pareto dominantné. Inými slovami, pre ktoré nie je možné zmenou riešenia dosiahnuť lepšie plnenie niektorého kritériá bez zhoršenia v plnení iného kritériá. Množina pareto riešení (tzv. pareto front) je teda množina najlepších riešení (5).

Evolučné algoritmy

Evolučné algoritmy vychádzajú z Darwinovej evolučnej teórie. V tomto prístupe sa každé riešenie chápe ako chromozóm, ktorý má priradenú tzv. fitness (ide vlastne o úspešnosť vyjadrenú číselne), ktorá vyjadruje úspešnosť daného riešenia. Skupiny chromozómov vytvárajú populáciu, ktorá sa mení reprodukciou, a to výberom chromozómov (náhodne, pravdepodobnosť výberu je priamo úmerná fitness), krížením (skombinovaním vybraných chromozómov, z angl. crossover) a mutovaním. Najjednoduchšou formou evolučného algoritmu sú genetické algoritmy, kde je riešenie reprezentované reťazcom, zväčša binárnym s pevnou dĺžkou (12). Ukážku kríženia vidíme na obr. 1 a mutácie na obr. 2.

Obrázok 1  Kríženie (6).

Obrázok 2  Mutácia zmenou bitu (7).

Ďalšou kategóriou sú evolučné stratégie, ktoré využívajú vektorovú reprezentáciu riešenia (reťazac reálnych čísiel). Primárnym operátorom sú mutácie, ktoré vytárajú potomkov pripočítaním náhodnej normálne distribuovanej hodnoty. Selekcia sa vykonáva dvomi spôsobmi:

• Elitárska verzia vytvorí novú generáciu z λ rodičov a µ potomkov predošlej generácie. Táto metóda sa nazýva plusová stratégia, alebo (µ + λ).
• Čiarková stratégia, označovaná (µ, λ), vytvára novú generáciu len z potomkov.

Označenie (µ ,+ λ) značí využitie oboch spôsobov (4). Ďalším operátorom je zmiešané kríženie (z angl. intermediate recombination), ktoré vytvorí potomka spriemerovaním hodnôt rodičov (7). Ukážku vidíme na obr. 3.

Obrázok 3  Zmiešané kríženie (7).

Evolučné programovanie využíva reprezentáciu podľa problémovej oblasti, ale väčšinou ide tiež o vektor reálnych čisiel. Rozdiel oproti predošlým metódam je, že sa nevyužíva kríženie. Typicky sa vytvorí z n rodičov mutáciou n potomkov a z tejto spojenej množiny 2n riešení sa podľa fitness hodnoty vyberie n členov novej generácie (7).

Genetické programovanie je evolučný algoritmus na automatické hľadanie riešení, kde riešenie je program, ktorý je zväčša reprezentovaný stromovou štruktúrou. Najčastejšia reprezentácia programu v genetickom programovaní je tzv. syntaktický strom. Vychádza z toho, že program je možno zapísať ako hierarchiu príkazov. Obrázok 4 ukazuje syntaktický strom pre program max(x+x,x+3*y). Pre jednoduchšiu predstavu, ako vytvoriť tento stromový zápis sa prevádza zápis programu do tzv. prefixového tvaru, známeho z funcionálneho programovania. Ten by vyzeral (max (+ x x) (+ x (* 3 y))). Z toho zápisu je lepšie vidieť vzťah medzi príkazmi a podpríkazmi (12).

Obrázok 4  Reprezentácia programu max(x+x,x+3*y) (12).

Viackritériové evolučné algoritmy

V praxi sa často stretávame s problémami, ktoré nemajú iba jedno najlepšie riešenia. Problém sa skládá z mnohých, často protichodných cieľov, alebo kritérií. Príkladom sú investičné stratégie, kde sa snažíme maximalizovať výnosy a minimalizovať riziko.

Intuitívnym spôsobom, ako riešiť tento problém, je spojiť kritéria do jedného. Na tomto princípe je založený agregačný postup, pri ktorom vytvoríme jednu agregovanú funkcia, ktorá spája kritériové (fitness) funkcie do jednej, ako vážený súčet. Problémom je, že dostávame jedno riešenie a nie pareto front (5).

Ďalším prístupom je tzv. populačný. Algoritmus VEGA (z angl. Vector Evaluated Genetic Algorithm) rozdelí populáciu na časti, kde každá časť sa špecializuje na riešenie jedného kritéria. Potom sa vybrané riešenia premiešajú a aplikujú sa evolučné operátory. Problémom tohto algoritmu je, že uprednostňuje riešenia, ktoré excelujú v jednom kritériu (bez ohľadu na výkon v iných kritériách). Iným algoritmom je CCGA (z angl. Cooperative Co-evolutionary Algorithm), kde každá subpopulácia reprezentuje jednu rozhodovaciu premennú alebo časť problému. Z čiastkových riešení sa potom skladá celkové riešenie (5).

Ďalšou skupinou, ktorou sa budeme bližšie zaoberať, sú založené na pareto optimalite. Tieto algoritmy využívajú pareto dominanciu na hodnotenie riešení. Výstupom sú riešenia v okolí pareto frontu a používateľ si z nich má vybrať.

SPEA (z angl. Strength Pareto Evolutionary Algorithm) využíva elitarizmus, nedominované riešenia uchováva v samostatnom archíve. Algoritmus pozostáva z týchto krokov (13):

1. Vytvor náhodnú populáciu a prázdny externý archív
2. Aktualizuj archív
3. Vypočítaj fitness hodnoty v populácii aj archíve
4. Vyber turnajovým výberom riešenia z populácie aj archívu na aplikáciu evolučných operátorov
5. Aplikuj mutáciu a kríženie na vytvorenie novej populácie
6. Ak sme dosiahli maximálny počet generácii alebo iné ukončovacie kritérium, ukončiť. Ináč pokračovat na krok 2.

Do archívu sa kopírujú nedominované riešenia z populácie. Každému riešeniu z archívu je priradená sila, ktorá sa rovnu počtu riešení z populácie, ktorým dominuje, predelené veľkosťou populácie, plus 1. Fitness hodnota riešenia v populácii je rovná súčtu síl riešení v archíve, ktoré mu dominujú. V prípade, že veľkosť archívu presiahne maximálnu veľkosť, používa sa aglomeračný zhlukovací postup, aby odstránil niektoré riešenia a zachovala sa rôznorodosť. Náročnosť tohto algoritmu bola určená ako O(mn²), kde m je počet kritérií a n je veľkosť populácie (5).

SPEA2 vznikol ako odpoveď na niektoré nedostatky v SPEA, dosahuje lepšie výsledky vďaka zachovaniu rôznorodosti riešení. Jeho náročnosť je O(N²), kde N je súčet veľkosti populácie a archívu.

Kroky v algoritme sú podobné (15), avšak je tam niekoľko odlišností (5):

• Veľkosť archívu je konštantná, pričom
  •  ak presiahne stanovenú veľkosť, odstránia sa riešenia, ktoré majú najmenšiu vzdialenosť k inému riešeniu a
  •  ak je veľkosť nižšia, pridajú sa najlepšie dominované riešenia z populácie.
• Sila a fitness hodnota sa počíta aj z archívu aj populácie, čize sila každého riešenia z archívu aj populácie sa rovná počtu dominovaných riešení v archíve aj populácii. Hrubá fitness hodnota je potom rovná súčtu síl dominantných riešení v archíve aj populácii.
• K celkovej fitness hodnote jedinca sa priráta aj jeho hustota, rovná inverznej hodnote vzdialenosti ku k-temu susedovi.

MOGA (z angl. Multi objective genetic algorithm) priraďuje riešeniam hodnotenie rovné počtu riešení v populácií, ktoré im dominujú, plus 1. Nedominované riešenia majú teda najnižšie hodnotenie rovné 1. Podľa tohto hodnotenie sa zoradia a fitness hodnota sa priradí interpoláciou od najlepšieho hodnotenia po najhoršie. Fitness hodnoty riešení s rovnakým hodnotením sa spriemerujú (3).

NPGA (z angl. Niched Pareto Genetic Algorithm) využíva upravenú verziu turnajového výberu. Z populácie sa vyberú dve náhodné riešenia a skúšobná množina. Ak niektoré riešenie zo skušobnej množiny dominuje nad prvým riešením a nie nad druhým, vybere sa druhé riešenie. Ak nedominuje ani nad jedným alebo nad oboma, použije sa na výber metóda tzv. zdieľania (6).

NSGA (z angl. Non dominated sorting algorithm) priraďuje nedominované riešenia do jednej kategórie a je im priradená pseudo-fitness hodnota, proporčná k veľkosti populácie. Táto kategória je potom oddelená od populácie a kategorizácia nedominovaných riešení pokračuje (14). Problémom tohto algoritmu je jeho náročnosť O(mn³) (4). NSGA2 rieši hlavný problém NSGA, a to výpočtovú náročnosť. Jeho náročnosť poklesla na O(mn²).

PAES (z angl. Pareto archived evolution strategy) využíva externý archív pre nedominované riešenia a generuje potomka z riešenia pomocou mutácie. Ak nové riešenie dominuje nad pôvodným, je akceptované, ináč sa zahodí a vytvorí sa nový potomok. Ak ani pôvodné ani nové riešenie nie je dominantné, zistí sa, či potomok dominuje nad niektorým riešením v archíve. Ak áno, akceptuje sa do novej populácie a dominované riešenie za zahodí. Ak nie, vybere sa medzi nimi to riešenie, ktoré sa nachádza v menej hustom regióne prehľadávaného priestoru. Takto sa dosahuje väčšia rôznorodosť . Regióny vznikajú rozdelením priestoru daného kritériami na mriežku. Náročnosť algoritmu je O(mn²) (5). Z tohto algoritmu vzniklo množstvo modifikácií, na príklad:

• IS PAES (z angl. Inverted Shrinkable PAES) rieši problém veľkého množstva buniek v mriežke tým, že postupne koncentruje hľadanie na menšiu oblasť (2).
• APAES (z angl. Adaptive PAES) reprezentuje riešenie ako dvojicu reťazca a využitej abecedy, pričom abeceda sa počas trénovania mení, teda adaptuje (11).
• M-PAES (z angl. Memetis PAES) pridáva populáciu, nad ktorou sa robí kríženie (8).

PESA (z angl. Pareto Envelope-Based Selection Algorithm) spája myšlienky z PAES a SPEA. Algoritmus pozostáva z týchto krokov:

1. Vytvor náhodnú internú populáciu (IP) a prázdnu externú populáciu (EP).
2. Pridaj riešenia z IP nedominované žiadnym riešením v IP ani EP do EP. Všetky riešenia, ktorým v EP dominuje sa odtiaľ odstránia. Ak sa presiahne veľkosť EP, odstránia sa riešenia podľa tzv. faktoru tlačenia (z angl. squeeze factor).
3. Ak sme dosiahli maximálny počet generácii alebo iné ukončovacie kritérium, ukončiť. Ináč vymaž obsah IP a opakuj kým nie je IP znova naplnená:
   1. S pravdepodobnosťou p vyber dve riešenia z EP, vytvor nové riešenie ich skrížením a zmutuj ho.
   2. S pravdepodobnosťou 1-p vyber jedno riešenie a zmutuj ho.
   3. Pokračuj od kroku 2.

Turnajový výber riešení v kroku 3 sa taktiež robí podľa faktory tlačenia, riešenie s nižšou hodnotou je vybraté. Všetky riešenia su umiestnené v hypermriežke (vytvorenej podľa fitness hodnôt), pričom faktor je rovný počtu ostatných riešení v danej časti hypermriežky. Autori algoritmus porovnávali s PAES a PEAS a vo väššine testov víťazil. Hlavne pri predlžovaní doby trénovania (2). Existujú ďalšie algoritmy, medzi ktoré patria VOES, PPES, TDGM, REMOEA, ENSGA, či DBPGA (4).

Záver

Evolučným algoritmom sa v posledných rokoch venuje veľká pozornosť a veľa problémov bolo vyriešených, stále ich však veľa zostáva (4):

• Aplikovateľnosť na reálnych problémoch.
• Určovanie ukončovacieho kritéria, lebo nie je jasné, kedy ukončiť trénovanie.
• Výber najlepšieho riešenia z pareto frontu.
• Hybridizácia algoritmov.
• Kvantové evolučné algoritmy, ktoré kombinujú evolučné algoritmy a kvantové postupy (9) (10).
• Chýba ucelená teória viackritériových evolučných algoritmov, s prehľadom rôznych fitness priraďovaní v kombinácii s rôznymi selekciami.
• Vplyv obmedzenia kríženia, hoci tieto obmedzenia sa často nepoužívajú.

Medzi časté problémy pri implementácii patrí (5):

• Udržanie rôznorodosti riešení.
• Škálovateľnosť pri veľkom množstve kritérií.
• Robustnosť, teda schopnosť prispôsobiť sa zmenám prostredia.

Použité zdroje

1. Aguirre, A. H. a kol. 2003. IS-PAES: A Constraint-Handling Technique Based on Multiobjective Optimization Concepts. Lecture Notes in Computer Science Volume 2632, 2003, pp. 73 – 87.
2. Corne, D. W. a kol. 2000. The Pareto Envelope-based Selection Algorithm for Multiobjective Optimization. Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature, pp.839 – 848.
3. Fonseca, C. M. – Fleming, P. J. 1993. Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization. Proceedings of the Fifth InternationalConferenceon Genetic Algorithms, pp.416 – 423.
4. Ghosh, A. – Dehuri, S. 2005. Evolutionary Algorithms for Multicriterion Optimization: A Survey. Internation Journal of Computing & Information Sciences, vol. 2, no. 1. pp. 38-57.
5. Hassan, G. N. A. 2010. Multiobjective genetic programming for financial portfolio management in dynamic environments. Dizertačná práca. University College London.
6. Horn, J. a kol. 1994. A Niched Pareto Genetic Algorithm for Multiobjective Optimization. Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, pp. 82 – 87.
7. Hussain, T. S. 1998. CITO Researcher Retreat, Hamilton, Ontario.
8. Knowles, J. D. – Corne, D. W. 2000. M-PAES: A Memetic Algorithm for Multiobjective Optimization. Proceedings of the Congress on  Evolutionary Computation, vol. 1, pp. 325 – 332.
9. Laboudi, Z. – Chikhi, S. 2012. Comparison of Genetic Algorithm and Quantum Genetic Algorithm. The International Arab Journal of Information Technology, vol. 9, no. 3, pp. 243 – 249.
10. Malcher, V. 2014. Quantum assembly languages,  Digital Science Magazine [elektronický zdroj], ISSN 1339-3782, vol. 3, no. 1, [online]  URL http://www.digitalmag.sk/
11. Oltean, M. 2005. Multiobjective Optimization Using Adaptive Pareto Archived Evolution Strategy. Intelligent Systems Design and Applications, pp. 558 – 563.
12. Poli, R. – Langdon, W. B. – McPhee, N. F. 2008. A Field Guide to Genetic Programming [Online]. Zverejnené pomocou http://lulu.com. Dostupné na internete: http://www.gp-field-guide.org.uk, 2008. ISBN 978-1-4092-0073-4
13. Potti, S. – Chinnasamy, Ch. 2011. Strength Pareto Evolutionary Algorithm based Multi-Objective Optimization for Shortest Path Routing Problem in Computer Networks. Journal of Computer Science, vol. 7, pp. 17 – 26.
14. Srinivas, N. – Deb, K. 1994. Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Journal of Evolutionary Computation, vol. 2, no. 3, pp. 221 – 248.
15. Zitzler, E. – Laumanns, M. – Thiele, L. 2001. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Evolutionary Methods for Design, Optimization, and Control, CIMNE, pp. 95 – 100.

Autor:

Ing. Mgr. Martin Jakubeci

Pracovisko:
Department of Information Systems
Faculty of Management
Comenius University in Bratislava
Odbojárov 10,
820 05 Bratislava 25,
Slovakia
e-mail: martin.jakubeci@fm.uniba.sk

Recenzenti:

Ing. Jaroslav Vojtechovský, PhD.
Pracovisko: Fakulta managementu UK, Odbojárov 10, Bratislava

Ing. Martin Čuboň
Pracovisko: Adastra s.r.o., Bratislava

Vydanie:

Digital Science Magazine, Číslo 2, Ročník III.