Machine Learning Tools Evolutionary Computation Jan Žižka Centrum Biostatistiky & Analýz (CBA) Masarykova universita Kamenice 126/3 62500 Brno zizka@cba.muni.cz Evoluční výpočty Genetické algoritmy (Zlepšování hledaného řešení simulací darwinovské evoluce) 2 Machine Learning Tools Evolutionary Computation OBSAH Optimalizace a její problémy dané výpočetní složitostí úloh Evoluční výpočty, Darwin, simulace darwinovského vývoje Genetické algoritmy (GA), základní principy a parametry Výběr členů populace pro reprodukci (přizpůsobenost) Reprodukce a základní metody (křížení, mutace) Diversita populace a její využití Ukázka aplikace GA na TSP (problém obchodního cestujícího) 3 Machine Learning Tools Evolutionary Computation VÝPOČETNÍ SLOŽITOST Velké množství parametrů a/nebo kombinací jejich různých hodnot, které mohou mít vzájemnou interakci do různého stupně, vede k obvykle silně nelineárnímu nárůstu výpočetní složitosti hledání optima. Výpočetní složitost spojená s generováním všech možných řešení a následným hledáním optima bývá pak často prakticky nepřekonatelnou překážkou, protože požadovaný čas i paměť jsou pro dosažení požadovaného výsledku nepřijatelné a nesplnitelné. Hledání optima v závislosti na prostředí, v němž se generují potenciální řešení, také obvykle ovlivňuje chování algoritmu zvoleného pro řešení úlohy. Výběr algoritmu hraje důležitou roli, protože tutéž funkci lze někdy realizovat mnoha různými metodami v různém čase s různou pamětí ­ rozdíly mohou dosahovat mnoha řádů. Výpočetní složitost se stanovuje nezávisle na použitém hardware, protože ten se časem mění a i když se zlepšuje významně, z hlediska výpočetní složitosti daného problému je to nepříliš významné (např. šachy, go, apod.). 4 Machine Learning Tools Evolutionary Computation VÝPOČETNÍ SLOŽITOST (pokračování) Výpočetní složitost nějaké funkce f(x) se odhaduje nejčastěji prostřednictvím tří funkcí O, , a (c, c1 , c2 , a x0 jsou kladné konstanty). Funkce O zvaná ,,big oh" určuje asymptotickou horní hranici: O[(g(x)] je funkce mající c a x0 takové, že 0 f(x) cg(x) pro x x0 f(x) x cg(x) x0 f(x)=O[g(x)] asymptotická horní hranice velká x 5 Machine Learning Tools Evolutionary Computation VÝPOČETNÍ SLOŽITOST (pokračování) Funkce zvaná ,,big omega" určuje asymptotickou spodní hranici: [(g(x)] je funkce mající c a x0 takové, že 0 cg(x) f(x) pro x x0 f(x) x cg(x) x0 f(x)= [g(x)] asymptotická spodní hranice velká x 6 Machine Learning Tools Evolutionary Computation VÝPOČETNÍ SLOŽITOST (pokračování) Funkce zvaná ,,big theta" určuje asymptotické vymezující pásmo : [(g(x)] je funkce mající c1 , c2 a x0 takové, že 0 c1 g(x) f(x) c2 g(x) pro x x0 f(x) x c2g(x) x0 f(x)= [g(x)] asymptotická vymezující hranice c1g(x) velká x 7 Machine Learning Tools Evolutionary Computation VÝPOČETNÍ SLOŽITOST (pokračování) Funkce O (.) se používá velmi často, protože je velmi užitečné mít odhad o horní hranici výpočetní složitosti aplikovaného algoritmu ­ zda jde o složitost lineární, polynomickou, nebo exponenciální může být rozhodující. Je-li např. f(x) = 12x3 ­ 7x2 + 94x + 16, pak horní limit složitosti je O(x3 ), protože pro dostatečně velká x (která nás zajímají) jsou konstanty, kvadratické a lineární členy nerelevantní: existuje hodnota x0 taková, že např. 13x3 12x3 ­ 7x2 + 94x + 16 pro x x0 (c = 13). Roste-li tedy řekněme časová (nebo paměťová) výpočetní složitost v závislosti na x = počet jedinců v populaci s kubickou parabolou O(x3 ) a nás zajímají hodnoty x >100, pak např. pro c = 20 (zde by šlo použít již c = 12) platí, že O[cg(x)] = O (20x3 ) = O (x3 ) dává horní hranici již od x0 3.109966, tj. určitě pro velikost populace x 4. Proto lze použít pro přibližný odhad výpočetní složitosti algoritmu horní hranici O(x3 ), tedy ,,kubická výpočetní složitost" nebo ještě obecněji ,,polynomická výpočetní složitost" O(xk ). Tj. výpočet je náročnější než pro lineární složitost O(x), ale nedosahuje exponenciální složitosti typu O(k x ), kde k je konstanta. 8 Machine Learning Tools Evolutionary Computation VÝPOČETNÍ SLOŽITOST (pokračování) Ilustrace vztahu funkce f(x) a g(x) vzhledem k O[g(x)] : 1 2 3 4 5 6 7 8 910 20 30 40 50 60 70 100 20 50 100 200 500 1000 2000 5000 10000 20000 50000 100000 200000 500000 1000000 2000000 5000000 f(x) = 75ln(x)+908 g(x) = 50x f(x) = 12x3-7x2+94x+16 g(x) = 20x3 10000000 20000000 x0 pro O(x3) x0 pro O(x) 9 Machine Learning Tools Evolutionary Computation VYHLEDÁVÁNÍ V MNOHAROZMĚRNÉM PROSTORU Existuje mnoho metod umožňujících hledat optimum. Patří k nim metody analytické (derivační a numerické výpočty), a pokud je nelze použít, pak metody využívající ,,hrubé síly" jako je systematické prohledávání sekvenční (nebo náhodné s vysokým počtem pokusů), nebo různé metody aplikované v umělé inteligenci (hledání do šířky, do hloubky, mini-max, -, A* a řada dalších). Metody umělé inteligence se snaží redukovat vysokou výpočetní náročnost systematického prohledávání a zároveň vysokou nejistotu náhodného hledání. Jednou z možností, které v praxi prokazují mnoho aplikačních úspěchů, je použít simulaci evoluce biologických druhů. Evoluce směřuje k dosažení nějakého optimálního výsledku v daném prostředí. U biologických objektů to může být přežití taková evoluce obecně vede k rozvoji stále složitějších organismů. Prostředí vývoje je chápáno jako nestacionární stochastický proces řádu n, kde předchozích n symbolů ovlivňuje pravděpodobnost výskytu dalšího symbolu. Míra korelace pak umožnuje předpověď. U živých systémů jsou předpovědi velmi obtížné. 10 Machine Learning Tools Evolutionary Computation DARWINOVSKÁ EVOLUCE Darwina vedly jeho výzkumy k založení teorie, popsané v knize O původu druhů prostřednictvím přirozeného výběru (listopad 1859). Jeho klasická teorie vývoje v kombinaci s Weismannovým selekcionismem a Mendelovou genetikou je akceptována jako základ současných neo-darwinistických přístupů ke zkoumání vzniku a vývoje živočišných druhů. Darwinova teorie měla a má řadu zastánců i odpůrců, a v den svého skonu 19. dubna 1882 patřil bezesporu k již obecně vysoce uznávaným vědcům. Pohřben je na hřbitově v Westminster Abbey. Charles Robert Darwin (1809-1882) je autorem evoluční teorie, která vznikla jeho pozorováním různých druhů v přírodě. Svá pozorování prováděl jako neplacený výzkumník na pětileté vědecké expedici, která začala 27. prosince 1831 vyplutím plachetnice HMS Beagle. Darwin mohl zkoumat živočichy i fosilie na různých kontinentech (převážně v Jižní Americe, ale i jinde) a svá pozorování navzájem porovnávat. 11 Machine Learning Tools Evolutionary Computation DARWINOVSKÁ EVOLUCE A JEJÍ SIMULACE Darwinova evoluce je v principu jednoduchá, vychází z existence různorodé populace, v níž přežívají jedinci s nejlepšími vlastnostmi pro dané prostředí. Tento pohled na Darwinovu teorii vedl k myšlence modelovat výpočetně složité úlohy tak, že se vytvoří počáteční rozsáhlá populace, jejímiž členy jsou různě kvalitní počáteční řešení cílem je dostatečně pokrýt prostor možných řešení, přičemž není nutno generovat všechna, a vývojem tvořit nová lepší řešení z přibližně (či zcela náhodně) navržených počátečních. Mnoharozměrný prostor (dimenze jsou dány parametry řešené úlohy) obecně obsahuje mnoho lokálních extrémů a cílem je najít extrém globální. Proto je zejména na počátku nutná co největší různorodost členů populace, protože hodnoty jejich vlastností jsou souřadnice jednotlivých řešení v prostoru. Čím hustěji a rovnoměrněji je prostor obydlen, tím větší je šance, že jeden z obyvatel je přinejmenším někde poblíž hledaného globálního extrému, tj. optimálního řešení. Na druhé straně, rozsáhlá populace zvyšuje výpočetní složitost, takže je zapotřebí najít vhodný kompromis. 12 Machine Learning Tools Evolutionary Computation DARWINOVSKÁ EVOLUCE A GENETICKÉ ALGORITMY Simulovaná evoluce vychází z předpokladu, že v dané populaci existují jedinci kvalitnější a méně kvalitní. Kvalitnější jedinci jsou ti, kteří jsou blíže hledanému globálnímu extrému. Na určení kvality jedince se používá funkce ohodnocující jeho přizpůsobenost prostředí (fitness function). Tato funkce je stanovena konkrétně vzhledem k hledanému cíli úlohy. Sleduje se, zda kvalita řešení úlohy se zvyšuje, zda klesá velikost chyby, apod. Lepší jedinci mají větší pravděpodobnost přežití, protože vývoj probíhá tak, že se vybírají kvalitnější členové pro vytvoření následující generace, a méně kvalitní vyhynou (nemají potomky). Kvalita jedince je dána kombinací hodnot jeho parametrů, které jako souřadnice udávají jeho blízkost optimu (polohu optima však neznáme). Každý parametr se považuje za gen, tj. za jednu z vlastností. Soubor genů jedince pak tvoří chromosom, což je popis jedince z hlediska relevantních parametrů řešené úlohy (je důležité definovat správně relevantní parametry). Noví jedinci, potomci, vznikají kombinací chromosomů vybraných rodičů s možností zlepšit (i zhoršit) své vlastnosti. 13 Machine Learning Tools Evolutionary Computation GENETICKÉ ALGORITMY Princip vývoje zlepšeného řešení úlohy je založen na naději, že kombinací vlastností kvalitních rodičů vzniknou ještě kvalitnější potomci, kteří od každého z rodičů zdědí souřadnice, které je posunou blíže k optimu. Protože se neví, kde se optimum nachází, ale ví se, jak měřit funkcí přizpůsobenosti přibližování (nebo vzdalování) se jedince k optimu, lze úspěšnost vývoje sledovat pomocí růstu kvality nejlepšího jedince. Nelze jednoznačně stanovit, kdy se má evoluce zastavit. Je možné např. ukončit vývoj tehdy, kdy již přestalo zlepšování, nebo kdy byl vyčerpán předem stanovený maximální počet generací. Žádná metoda nezaručuje konec vývoje dosažením optima, protože v reálných úlohách běžně hrozí uváznutí v lokálním extrému a obecně nelze určit, že dosažený extrém je nebo není globální. Nalezené řešení, představované nejkvalitnějším jedincem v populaci, může nebo nemusí být přijatelné, pokud se zlepšování populace zastavilo. To je zcela na interpretaci uživatelů genetických algoritmů. 14 Machine Learning Tools Evolutionary Computation GENETICKÉ ALGORITMY (pokračování) Genetické algoritmy (GA) mají některé základní parametry a řadu dalších parametrů, kterými lze podle aplikační potřeby metodu modifikovat. K základním parametrům standardně patří: definice jednotlivých vlastností jedince (geny) stanovení metody kódování vlastností (genů) do/z chromosomu počet členů populace (velikost populace): čím větší, tím lepší funkce měření přizpůsobenosti způsob seřazování jedinců dle kvality metoda vytvoření počáteční ,,nulté" generace metoda generování potomků (tvorba nové generace z předchozí) kritérium ukončení vývoje Evoluce probíhá cyklicky, vhodné je sledovat kvalitu nejlepšího jedince v každé generaci a průměrnou kvalitu populace. Pokud se nejlepší jedinec již málo liší od ostatních, došlo k usazení se populace v nějakém místě, které může být optimem (či přijatelným suboptimem) nebo populace zdegenerovala a skončila v lokálním extrému, z něhož již nemůže uniknout. 15 Machine Learning Tools Evolutionary Computation IQ váha 168 217 241 168 241 217chromozom: 3 geny 10101000 11110001 11011001 representace bitovým řetězcem výška GENETICKÉ ALGORITMY (pokračování) Příklad popisu jedince pomocí tří vlastností: IQ, výška, váha 16 Machine Learning Tools Evolutionary Computation OBECNÝ GENETICKÝ ALGORITMUS 1. Definice problému a funkce přizpůsobenosti každého řešení, stanovení genetických operátorů pro reprodukci. 2. Inicializace počáteční generace vzhledem k omezením (stanovení velikosti populace, zakódování náhodně vygenerovaných hodnot genů do vektoru- -chromosomu ). Nultá generace je vytvořena z mnoha co nejrůznějších jedinců (zabydlení prostoru). 3. Dekódování všech chromosomů zpět do původního prostoru (může představovat značnou režii), stanovení jejich individuálních kvalit funkcí přizpůsobenosti a přiřazení příslušných skóre vzhledem k cíli řešení. 4. Přiřazení pravděpodobnosti reprodukce pro každý chromosom úměrně jeho kvalitě vzhledem k ostatním chromosomům v populaci. 5. Pravděpodobnostním výběrem jsou zvoleny chromosomy, na něž se použijí specifické genetické operátory (např. křížení a mutace ) pro vytvoření potomků další generace. Aplikací elitismu se do další generace mohou dostat přímo i někteří nejlepší jedinci beze změny. 6. Test, zda bylo dosaženo kritérium ukončení vývoje nebo zda byl vyčerpán disponibilní čas pro vývoj. Pokud ne, návrat do bodu 3. Pokud ano, funkce přizpůsobení předá nejlepšího dekódovaného jedince jako výsledek. STOP 17 Machine Learning Tools Evolutionary Computation STANDARDNÍ METODA VÝBĚRU Funkce přizpůsobení přiřadí každému chromosomu tzv. skóre. Nejvyšší skóre pak znamená nejvyšší pravděpodobnost výběru pro vytvoření nové generace. Standardní metoda počítá přizpůsobenost fi i-tého chromosomu jako podíl kvality chromosomu qi ku součtu kvalit všech n jedinců (0.0 fi 1.0): f i = qi j =1 n q j Standardní metoda neumožňuje ovlivňovat výběr, a kromě toho jedinec s nulovou kvalitou má nulovou pravděpodobnost se zúčastnit reprodukce. Vyřazování jedinců však vede k rychlejší degeneraci populace snižováním různorodosti (je dobré být i odlišný , tj. nejen přizpůsobený ). I nekvalitní jedinec může mít nějaké geny, které by mohly v kombinaci s geny jiného chromosomu vytvořit potomka kvalitnějšího než jsou rodiče. 18 Machine Learning Tools Evolutionary Computation SEŘAZOVACÍ METODA VÝBĚRU Kvalita se zde použije pouze pro seřazení chromosomů od nejlepšího po nejhoršího. Nejlepší kandidát dostane přiřazenu hodnotu pravděpodobnosti p takovou, že platí 0.5 < p < 1.0, tj. pravděpodobnost musí být vyšší než náhodná a nižší než jistota, aby nenulové pravděpodobnosti výběru získali i ostatní jedinci. Pro p je možno zvolit např. hodnotu 2/3 0.667, a hodnoty zbývající do 1.0 jsou rozděleny mezi ostatní jedince podle vztahu: Seřazovací metoda tedy přidělí pravděpodobnost výběru nenulovou (i když velmi malou) jedincům i s nulovou kvalitou. Takoví jedinci většinou vybráni stejně nejsou, ale mohou se občas podílet na tvorbě nové generace. Křížení umožňuje efektivní prohledávání mnoharozměrných prostorů s množstvím lokálních extrémů. Takové prostory připomínají velmi zvlněnou krajinu s mnoha horami, hřebeny, rovinami i propastmi, v níž se jedinci ubírají různými směry. Popsané křížení je ,,hermafroditické"; existují i modifikace na ,,dvoj- a více-pohlavní", kdy existují specifické geny (aplikačně závislé). p i = 1-p j =1 i -1 p j , i =1,,n 19 Machine Learning Tools Evolutionary Computation RULETOVÉ KOLO PRO VÝBĚR Často používanou metodou výběru jedince pro repodukci na základě pravděpodobnosti vyplývající z přizpůsobenosti je tzv. ruletové kolo. Lze si představit roztočení kola, jehož obvod má délku = 1 a je rozdělen oblouky, jejichž počet odpovídá počtu členů populace a jejichž délka je dána pravděpodobností výběru příslušných jedinců. Kolo se náhodně zastaví v nějaké pozici, která určí vybraného jedince. Šance na výběr jedince roste s délkou jeho příslušného oblouku: VÝBĚR 20 Machine Learning Tools Evolutionary Computation MUTACE Mutace je napodobenina náhodných změn. Míra mutace odpovídá míře náhodného prohledávání prostoru; u GA se používá střídmě. Lze ovšem hledat řešení i pouze mutací, pokud prostor nemá lokální extrémy. Výhoda použití mutace je v tom, že umožňuje vnášet zcela nové hodnoty genů, jinak by hodnoty byly omezeny jen na inicializační z nulté generace. Mutace snižuje degeneraci zvyšováním různorodosti a zabraňuje potenciální ztrátě pohybu podél některých dimenzí prostoru (všechny parametry úlohy jsou relevantní). Křížením a degenerací může dojít k tomu, že dlouhé řetězce bitů jsou složeny pouze z nul (nebo pouze z jedniček) a další křížení již nepřináší žádné změny, takže populace ustrne v určitém místě prostoru bez možnosti například dostat se z uvíznutí v lokálním extrému podél jiných dimenzí. Mutace znamená náhodný výběr určité pozice (hodnoty) v chromosomu, např. jednoho bitu a změnu hodnoty z ,0` na ,1` (nebo naopak): ...010000000000000100011010... ...010000001000000100011010... 21 Machine Learning Tools Evolutionary Computation REPRODUKCE 168 241 217 = 10101000 11110001 11011001 10101000 1111011 100011100 = 101 219 284 = 1100101 11011011 100011100 1100101 110110001 11011001 = IQ VÝŠKA VÁHA náhodně zvolený bod křížení IQ VÝŠKA VÁHA 168 123 284 10001000 1111011 100011100 = 136 123 284 101 433 217 1110101 110110001 11011001 = 117 433 217 náhodně zvolený bod mutace generace k generace k+1 IQ VÝŠKA VÁHA 22 Machine Learning Tools Evolutionary Computation DIVERSITA A PŘEŽITÍ NEJRŮZNORODĚJŠÍCH Chromosomy mají tendenci vymizet i tehdy, pokud je jejich skóre jen o málo nižší než u chromosomů blízkých nejlepšímu. Tato uniformita (či již zmíněná degenerace ) nutí pak populaci se vyvíjet už jenom určitým směrem, který nemusí vést ke kýženému globálnímu extrému. V přírodě však bylo ukázáno, že i nepřizpůsobeně vypadající (odlišní) jedinci a druhy přežívají docela dobře v ekologických prostředích, která leží mimo ostatní (přizpůsobeně vyhlížející) členy populace. Prostorově-seřazovací metoda využívá princip diversity integrací kvality a diversity do přizpůsobenosti tak, že jedince ohodnocuje pro výběr k reprodukci i z hlediska jeho přínosu k různorodosti populace. Míra odlišnosti se spočítá jednoduše jako součet převrácených hodnot čtverců vzdáleností di kandidáta od n již vybraných chromosomů: diversita = i =1 n 1 d i 2 23 Machine Learning Tools Evolutionary Computation DIVERSITA A VÝBĚR JEDINCŮ Jedince v populaci lze na jedné ose seřadit podle kvality a na druhé ose podle diversity, což umožní vytvořit výsledné dvourozměrné pořadí, které bere ohled na obě důležité vlastnosti. Jedinci s nejvyšší kvalitou i diversitou jsou umístěni v pravém horním rohu příslušné roviny, horší jedinci blíže levému spodnímu rohu. Na takto seřazenou populaci lze nakonec aplikovat výše zmíněnou seřazovací metodu (nejlepší kandidát na reprodukci dostane přiděleno 0.5 < p < 1.0, ostatní jedinci si dle svého pořadí rozdělí zbytek pravděpodobností pro účast na reprodukci). diversita kvalita kvalitní různorodí nekvalitní různorodí nekvalitní uniformní kvalitní uniformní průměr 24 Machine Learning Tools Evolutionary Computation DIVERSITA A PŘEKONÁVÁNÍ LOKÁLNÍCH EXTRÉMŮ Pro mnoho algoritmů (např. umělé neuronové sítě) jsou lokální extrémy ,,pastí", a aby v nich trvale neuvázly, vyžadují zabudování mechanismů, které umožní se z pastí dostat (např. backtracking, návrat po vlastní stopě). Další možnost je paralelní hledání (velký počet různých počátečních startovních bodů), kde je naděje, že jedna z větví bude chycena do extrému, který je zároveň globálním. U genetických algoritmů umožňuje diversita jako složka přizpůsobenosti vyhnout se již obsazenému lokálnímu extrému a ,,strhnout" za sebou další putující jedince. Tím se lze vyhnout tomu, aby celá populace uvízla v jednom extrému a nebyla schopna najít i další, možná ještě lepší extrémy. Je-li dostatečný počet jedinců na obsazení lokálních extrémů, pak je dobrá šance, že někdo doputuje až do optima. Genetické algoritmy nemají jako cíl se vyhýbat lokálním extrémům. Naopak: obsadí je a zbytek populace, odlišný od již ,,zabydlených" členů, putuje dál a může (i nemusí) najít ještě lepší řešení. 25 Machine Learning Tools Evolutionary Computation Já sem našel to voptymum! V m-té generaci se vyvinul jedinec, který se vyšplhal až na globální extrém. Ostatní jedinci obsadili své niky. Zde jsou jedinci, jejichž předkové přežili vlivem evoluce. Nepřizpůsobiví jedinci vyhynuli. Jedinci v okolí optima již mají velmi podobné vlastnosti (degenerace). 26 Machine Learning Tools Evolutionary Computation APLIKACE GA NA PROBLÉM OBCHODNÍHO CESTUJÍCÍHO (TSP ) Jednou z typických testovacích i reálných úloh je problém obchodního cestujícího (traveling salesman problem, TSP). Je dána rozsáhlá množina bodů (měst) a úkolem je najít optimální cestu mezi nimi tak, aby obchodník přijel do každého města jen jednou a aby náklady na cestu byly minimální (nejkratší/nejlevnější cesta). Na tuto úlohu lze převést velké množství nejrůznějších problémů reálného světa (např. optimalizaci pohybu automatické vrtačky vytvářející otvory pro elektronické součástky na plošných spojích, propojování lokalit pro přenos signálu nebo energie, minimalizaci času a nákladů na včasné stanovení správné diagnózy a léčby pacienta, různá plánování a rozvrhování, apod.). Není známo, jak pro velký počet bodů (desítky, stovky a víc) najít optimální řešení. Genetické algoritmy jsou použitelné i pro tuto velmi obtížou úlohu, i když také nemohou zaručit nalezení optima kvůli velmi vysoké výpočetní složitosti: pro n měst existuje celkem T = (n -1)!/2 různých řešení, tedy kombinatoricky extrémně náročná úloha. 27 Machine Learning Tools Evolutionary Computation Snadno lze z existujících návrhů spojnic měst zjistit, která cesta je nejkratší, i pro velký počet měst. Není ale známo, jak najít optimální cestu. Množství různých řešení roste vlivem kombinatorické složitosti velmi rychle, silně nelineárně. Výpočetní složitost (čas a paměť) neumožňuje prakticky pro n vyšší než pár desítek měst najít zaručeně optimální výsledek. chromosom chromosom 28 Machine Learning Tools Evolutionary Computation 29 Machine Learning Tools Evolutionary Computation UKÁZKA ČINNOSTI GA PŘI ŘEŠENÍ TSP Demonstrační program GATSP.exe, vytvořený jako bakalářská práce studenta FI MU Tomáše Černého v r. 2004, umožňuje sledovat na grafickém výstupu činnost GA při řešení několika modelových úloh, na něž lze aplikovat TSP. Program GATSP.exe umožňuje nastavit velké množství nejrůznějších parametrů genetických algoritmů a sledovat jejich vliv na řešení obtížné úlohy TSP. SHRNUTÍ Genetické algoritmy jsou jednou z universálně použitelných metod na hledání vhodného nebo optimálního řešení mnoha reálných problémů, pokud nelze spolehlivě použít tradiční metody. GA jsou výpočetně náročné a zahrnují nezanedbatelnou režiji na nutnost oboustranné transfomace parametrů řešeného problému pro stanovení přizpůsobenosti jednotlivých členů rozsáhlé populace. GA obecně nezaručují nalezení optima (globálního extrému), přesto obvykle vedou k vylepšení výsledku. Jejich praktická aplikace na velmi mnoho rozličných problémů byla většinou úspěšná a stojí téměř vždy za pokus. GATSP.exe