Genetické algoritmy Petr Dostál Genetické algoritmy se používají tam, kde p esné ešení úloh z praxe by systematickým prozkoumáváním trvalo tém nekone n dlouho. Umož ují tak ešit složité problémy velmi elegantn . Genetické procesy v p írod odhalil v 19. stol. Mendel a rozvinul Charles Darwin. Po íta ová realizace genetických algoritm se za ala objevovat v 70. letech 20. století a je spojena se jmény J. Hollanda a D. Goldberga. Teprve v nedávné dob lze pozorovat zna né rozší ení aplikací genetických algoritm do oblastí ízení firem. V evolu ním vývoji nebo p i šlecht ní rostlin i živo ich se prosazují jedinci, kte í mají jisté žádoucí charakteristiky, které jsou na genetické úrovni determinovány kombinováním rodi ovských chromozom . U zrodu genetických algoritm stála myšlenka, že p i hledání lepších ešení složitých problém by bylo možno obdobným zp sobem kombinovat ásti existujících ešení. Uve me zde n kolik pojm z genetiky, které se objevují i v terminologii genetických algoritm . Chromozóm se skládá ze sekven n uspo ádaných gen . Každý gen ídí d di nost jednoho nebo n kolika znak a jeho pozice v chromozómu má název locus. Chromozóm p edstavuje tzv. genotyp a jeho význam, tj. informace zakódovaná v chromozómu, má název fenotyp. V tšina implementací genetických algoritm pracuje s p vodní reprezentací chromozomu pomocí nul a jedni ek, tj. s binární reprezentací. V tomto p ípad jsou chromozomy p edstavovány binárními et zci, nap . 0110. Tyto binární et zce v tšinou p edstavují zakódovaná dekadická ísla. Schéma je tedy et zec, v n mž se alespo na jedné pozici vyskytuje povolený symbol (v p ípad binární reprezentace je to 0 nebo 1). Pro manipulace s chromozómy bylo navrženo n kolik genetických operátor . Nej ast ji používanými operátory jsou selekce (selection), k ížení (crossover) a mutace (mutation). Proces reprodukce, který se opakuje, se nazývá epochou evoluce populace (jednou generací) a p edstavuje uvedené t i kroky: selekce, k ížení a mutace. Genetické algoritmy pracují tím zp sobem, že se nejprve vytvo í po áte ní populace m chromozóm , a potom se tato populace m ní pomocí genetických operátor tak dlouho, dokud není proces ukon en, nap . po tem cykl (generací). Viz obr.1.
Ne
Selekce
Inicializace
K ížení
Mutace
Konec? Ano Ukon ení
Obr. 1 Proces reprodukce Samotný genetický algoritmus lze popsat detailn ji následujícími kroky
- náhodné vytvo ení po áte ní populace n jedinc , - ocen ní kvality všech jedinc (chromozom ) dané populace pomocí fitness funkce, - tvorba nových chromozom aplikací operátor selekce, mutace a k ížení (proces reprodukce, rekombinace), - odstran ní starých jedinc z p vodní populace pro vytvo ení prostoru pro jedince nové, - vložení nových jedinc do populace a jejich ocen ní - je-li spln na ukon ující podmínka, ozna í se nejlepší chromozom jako ešení problému, jinak se opakuje innost tvorby nových chromozóm . Velmi d ležitým krokem v celém procesu je zejména vytvo ení po áte ní populace n jedinc a vhodné zakódování informací o ešeném problému. Je t eba vytvo it takovou populaci jedinc , aby co nejlépe postihovala ešenou úlohu a p itom se zamezilo tvorb nefunk ních chromozom , které nespl ují n kterou z omezujících podmínek (nap . duplicitní chromozomy p i ešení problému obchodního cestujícího). V opa ném p ípad je nutné do fitness (ú elové) funkce zabudovat tzv. penaliza ní funkci, která vyjad uje postih za nespln ní daného omezení. Symbolicky lze celý proces popsat následovn . Chromozom x chápeme jako abstraktní matematický objekt, který je obvykle tvo en et zcem symbol nebo reálných i celých ísel. Kone nou množinu všech možných chromozom ozna íme jako X X = {x1 , x 2 ,
, xn }.
Fitness funkce pak každému x ∈ X p i azuje reálné íslo f (x) , tj. f : X → R . Optimaliza ní problém má poté strukturu xopt = arg min f ( x) . x∈ X
Cílem genetického algoritmu je nalezení takového chromozomu x , který má hodnotu fitness funkce f (x) blízkou nebo dokonce rovnu f ( xopt ) . Po áte ní populace se obvykle získá náhodným generováním. Byly provedeny také pokusy nasadit do po áte ní populace kvalitní ešení, získaná jinými heuristickými technikami a pomoci tak genetickému algoritmu dosp t rychleji k lepšímu ešení. P i tomto zp sobu se však zvyšuje nebezpe í p ed asné konvergence do n jakého, ješt ne dost dobrého lokálního optima. Pokud jde o velikost populace, je jasné, že p íliš malá populace m že zavinit špatné pokrytí prostoru ešení, zatímco p íliš velká populace zvyšuje výpo etní náro nost. Experimentální práce nazna ují, že v mnoha p ípadech je dosta ující velikost populace kolem 100, resp. mezi n a 2n, kde n je délka binárního et zce. Jednou z možností zm ny m- lenné populace je vygenerovat pomocí k ížení a mutace novou generaci m potomk a nahradit rodi ovskou generaci an bloc. Jiné zp soby umož ují n jaké p ekrývání populace rodi a potomk . Nap . vygenerovaný potomek nahrazuje náhodn vybraného p íslušníka aktuální populace. P i ešení optimaliza ních problém se objevuje požadavek, aby nejlepší len aktuální populace se objevil i v populaci nové. To je možno zajistit nap . tak, že nový chromozóm nahrazuje jedince náhodn vybraného z t ch, kte í mají podpr m rnou kvalitu. P i aplikaci genetických algoritm na problémy ízení firem (resp. nevratného rozhodování), každý chromozóm kóduje n jaké ešení problému (tedy chromozóm je genotyp a odpovídající ešení je fenotyp) a jeho fitness je kladná hodnota, která n jakým zp sobem odpovídá hodnot ú elové funkce v tomto ešení. V genetických algoritmech jsou
2
preferovány chromozómy s vyšší hodnotou fitness. Fitness funkce musí být konstruovaná tak, že její hodnota je tím vyšší, ím lepší je hodnota ú elové funkce. Stochastický operátor selekce (ozna ený jako Oselect ( P ) , kde P p edstavuje ur itou populaci, tj. kone nou podmnožinu, jedinc z X umož uje výb r chromozom , které se stanou rodi i pro vytvo ení jedinc následující generace s pravd podobností závislou na hodnot fitness funkce. Tuto, tzv. selekci, ukazuje p íklad, kdy íslo 7 (binárn 0111) je v tší jak 2 (binárn 0010), proto chromozom 0111 p ejde do další generace. Viz tab.1. 0111 > 0010 7 > 2 Tab. 1 Selekce D ležité je, aby selek ní princip preferoval na jedné stran jedince s dobrou hodnotou fitness funkce, ale na druhé stran zachovával populaci dostate n r znorodou, aby nedocházelo k p ed asné konvergenci. Tento fakt lze dle popsat pomocí tzv. selek ní intenzity (selek ního tlaku) I M∗ −M I= , ∗
σ
kde M ozna uje pr m rnou hodnotu fitness funkce po selekci, M pr m rnou hodnotu fitness funkce p ed selekcí a σ rozptyl fitness hodnot p ed selekcí. ím vyšší je hodnota selek ního tlaku, tím rychleji algoritmus konverguje, ale hrozí nebezpe í p ed asné konvergence. Nej ast jší používanou metodou selekce je výb r pomocí rulety (roulette wheel selection), tj. pravd podobnost výb ru jedince je úm rná hodnot jeho fitness funkce. Metody výb ru jedinc jsou následující: - proporcionální selekce (metoda rulety) – zde pravd podobnost výb ru i -tého jedince je v závislosti na hodnot fitness funkce, - truncation selekce – celá populace se set ídí sestupn dle hodnoty fitness funkce a do další generace je vybrán pouze ur itý po et nejlepších jedinc . Op t ovšem dochází k vysoké ztrát genetického materiálu b hem selekce, - lineární ranking – op t se vychází ze set íd né populace, kde nejhorší jedinec je ozna en indexem 1 a nejlepší indexem N . - exponenciální ranking – pravd podobnost výb ru je rozložena exponenciáln a nikoli lineárn jako v p edchozím p ípad , - tournament selekce – zde se vybere z N jedinc v populaci t sout žících, z nichž do další generace p ejde ten nejlepší, což se opakuje práv N -krát, aby byla vytvo ena nová populace o N jedincích. Operátor k ížení lze symbolicky zapsat ve tvaru Oc : X 2 → X 2 (pro dva rodi e a dva potomky). Jedná se o operátor, který dv ma rodi ovským chromozom m x1 , x 2 ∈ X p i azuje stochasticky nový pár chromozom (x1′ , x 2′ ) = Oc (x1 , x 2 ) . Tento proces p edstavuje obvykle vým nu ástí rodi ovských chromozom , což zp sobuje modifikaci p vodních chromozom p i zachování ásti genetické informace obou rodi . Obvykle se tato operace neprovádí se 100% pravd podobností, ale asi s 95% pravd podobností. Nej ast jší jsou tyto zp soby k ížení - bodové k ížení – nejjednodušší p ístup, kdy k rekombinaci gen dochází v jednom i více bodech chromozomu. P íklad jednobodového k ížení udává tab.2a, p íklad dvoubodového k ížení tab.2b. 3
rodi e potomci 1|001 1100 1|100 1001 Tab. 2a Jednobodové k ížení
rodi e potomci 1|10|1 1111 0|11|0 0100 Tab. 2b Vícebodové k ížení
Bodové k ížení m že být ale realizováno i jiným zp sobem, jak je tomu nap . u ešení problému obchodního cestujícího, kdy k ížení sestává z náhodného výb ru dvou pozic v chromozomu a se azení hodnot gen mezi t mito pozicemi v opa ném sledu (dvoubodové k ížení p i jednom rodi i), -
jednotné k ížení - v tomto p ípad se prochází celý chromozom o délce n gen a s pravd podobností p uc dojde k vým n p íslušného genu. Je dobrým postupem pro zamezení p ed asné konvergence, nebo do populace vnáší pot ebnou r znorodost, naopak dle teorie stavby blok vede k p ílišnému rozvracení kódu.
Operátor mutace lze symbolicky zapsat ve tvaru Om : X → X . P i azuje stochasticky každému chromozomu x ∈ X nový chromozom x ′ = Om (x ) ∈ X . Spolu s operátorem k ížení pak tvo í tzv. operátor reprodukce, který lze chápat jako složení obou zmi ovaných operátor . Nej ast jší je bitová negace, k níž dochází s pravd podobností cca 0,0005 až 0,01. Jiným p ípadem je nap . operátor inverze, který invertuje po adí bit mezi dv ma náhodn zvolenými body chromozomu. Mutace je d ležitá jakožto zdroj nových informací v populaci, p i emž p íliš astá mutace m že vyvolat nestabilitu populace a p íliš nízká úrove mutace nedokáže vnášet do populace nutné informace pro její další vývoj. P íklad mutace uvádí tab.3. p ed po mutací mutaci 1100 0101 Tab. 3 Mutace Klasický genetický algoritmus lze modifikovat r znými zp soby. Cílem je obvykle zlepšení vlastností výpo etního procesu, a to zejména jeho urychlení a nalezení ešení co možná nejblíže optimálnímu. Velice významným rozší ením základních variant genetických algoritm jsou tzv. paralelní genetické algoritmy a s nimi související operátor migrace. V tomto p ípad jde o využití genetických algoritm pro ešení v n kolika menších populacích, p i emž n kte í jedinci p edávají svoje genetické informace do spole né populace, což urychluje konvergenci k cílovému ešení. Z n kterých vybraných metod paralelních genetických algoritm se lze zmínit o modelu -
Farminga - jedná se o klasický genetický algoritmus, kdy ovšem n které jeho ásti jsou provád ny („farmed out“) na pomocných procesorech (nap . k ížení, mutace a výpo et fitness funkce), které tyto výsledky a vzniklé jedince posílají zp t hlavnímu procesoru (host master), kde jsou provád ny globální výpo ty na celé populaci,
-
migra ním - pod pojmem migrace se rozumí smísení ur ité populace s jinou populací. Tím dochází k rozší ení stávajících genetických informací o nové. Migrace je bu jednosm rná, nebo vzájemná; jednorázová periodická nebo trvalá. Migra ní modely mnohem lépe simulují skute ný vývoj v p írod než klasické genetické algoritmy. Fungují tak, že se p vodní populace rozd lí na ur itý po et podpopulací, které si vym ují po jisté dob ur itý po et jedinc . V každé podpopulaci p itom probíhá vývoj dle klasického sekven ního genetického algoritmu s místním ízením. Po jistém 4
po tu generací pak dojde k migraci, ili vým n genetické informace mezi podpopulacemi. Op t to ve svém d sledku vede ke snížení rizika p ed asné konvergence. Spojení podpopulací se d je prost ednictvím komunika ní sít , která m že mít rozdílný charakter (nap . ostrovní model, „stepping-stone“ model nebo žeb íkový model). -
difuzním - jedná se o model, kdy celá populace je rozd lena do velkého po tu procesor . Bývá také nazýván model soused , p i emž hlavní roli hraje zejména propojení soused . Všichni jedinci jsou zde aktivní a hledají si partnery k reprodukci mezi svými sousedy. Využívá se model se ty mi sousedy i dvourozm rné m ížky s 9, 25 nebo 49 sousedy. Již u 25 jedinc jsou získané výsledky velice p íznivé. asto se také navíc provádí tzv. hill-climbing. Výrazn se takto zejména zvyšuje rychlost výpo tu.
P íklad 1. Na jednoduchém p íklad s použitím populace o ty ech lenech a ty bitovém chromozómu uvedeme, jak pracují genetické algoritmy. K ukázce využijeme programu Excel. Viz tab.4. P i inicializaci, kdy volíme chromozómy s dekadickými hodnotami 8, 4, 2, 1, nabývá ú elová funkce (suma hodnot Xi(10)) hodnoty 15. Prvním krokem první generace (populace) je selekce, kdy nejsiln jší chromozóm s dekadickou hodnotou 8 je dvakrát zopakován a nejslabší chromozóm s hodnotou 1 vypadá z tabulky. Dále dojde ke k ížení mezi (chromozómy) x1 a x3 od 2. pozice (bitu) vlevo v etn a mezi x2 a x4 od 3. pozice vlevo v etn , mutace se neprovede u žádného bitu žádného chromozómu. V druhé populaci, kdy hodnota ú elové funkce nabývá hodnoty 22 (což je 47 % zlepšení), dojde nejd íve k selekci, kdy nejsiln jší chromozóm s dekadickou hodnotou 12 je dvakrát zopakován a nejslabší chromozom s dekadickou hodnotou 0 vypadá z tabulky. Dále dojde ke k ížení mezi x1 a x3 od 3. pozice vlevo v etn a mezi x2 a x4 od 4. pozice vlevo v etn , mutace se provede u x4 v 2. pozici vlevo. Po ukon ení druhé generace je suma hodnoty ú elové funkce rovna 38 (což je zlepšení o 153 % proti po áte ní hodnot ú elové funkce). Takto je možné pokra ovat dalšími populacemi, kdy v praxi nalézáme stále lepší ešení. Inicializace i 1 2 3 4
První generace
Druhá generace
Xi(10) 8 4 2
Xi(2) 1000 0100 0010
Po selekci 1/000 10/00 0/100
K 2 3 2
Po k ížení 1/100 10/10 0/000
M 0 0 0
Po mutaci x'i(2) 1100 1010 0000
1
0001
00/10
3
00/00
0
0000
15
x' i(10) 12 10 0
Po selekci 11/00 110/0 10/10
K 3 4 3
Po k ížení 11/10 110/0 10/00
M 0 0 0
Po mutaci x''i(2) 1110 1100 1000
0
000/0
4
000/0
2
0100
22
x'' i(10) 14 12 8 4 38
Tab. 4 Výpo et genetickým algoritmem V ukázce bylo využito funkce dec2bin a bin2dec p evád jící dekadická ísla na binární a naopak.
P íklad 2. Jako první p íklad optimalizace uvedeme velmi jednoduchý problém. Pro výrobu desetilitrových plechovek budeme chtít ur it polom r plechovky r a její výšku v tak, aby spot eba materiálu byla minimální. Tento úkol vy ešíme pomocí komer n prodávaného programu GeneHunter od firmy Ward Systems Group. Program pracuje s tabulkou v prost edí programu Excel. Pro výpo et je nutné - stanovit ú elovou funkci, tj. rovnici, kterou budeme optimalizovat na maximum, respektive minimum, respektive ur itou hodnotu, - ur it hodnoty, které mají být optimalizovány, 5
- ur it typ chromozóm , který záleží na typu úlohy. Jde-li o spojitý problém (racionální ísla) nebo problém v rámci celých (integer) ísel, používá se typ chromozómu continuous, pokud jde o úlohy typu obchodního cestujícího nebo optimalizace portfolia, jde o typ chromozómu enumerated. - volit omezení optimalizovaných hodnot, a to rozsahy, podmínkami a funkcemi. Omezení rozsahem znamená, že optimalizovaná bu ka je limitována rozsahem. Omezení podmínkou znamená, že hodnota v bu ce má být menší, v tší nebo rovná jiné hodnot v bu ce nebo konkrétní hodnot se zvolenou tolerancí. Omezení funkcí znamená, že krom hlavní ú elové funkce lze použít další podružné funkce, které budeme optimalizovat na maximum, respektive minimum, respektive ur itou hodnotu, - volit další d ležité hodnoty pro nastavení optimalizace - population size, které ur uje ur uje po et populací, které bude program používat p i výpo tu. P i b žném výpo tu volíme hodnotu Population size 100 len . V p íkladu 1 to byly ty i lenové populace, - chromozome length, které ur uje délku chromozómu, který bude program používat p i výpo tu. P i b žném výpo tu volíme délku chromozómu 8, 16 nebo 32. V tší hodnota dává lepší výsledek, ale proces se zpomaluje. V p íkladu 1 to byly ty i chromozómy, - crossover rate, který zna í etnost k ížení, tj. jak asto p i výpo tu dochází ke k ížení (rozsah je 0 až 1). V b žném výpo tu se volí vysoká hodnota, nap . 0,9, - mutation rate, který zna í etnost mutace, tj. jak asto p i výpo tu dochází k procesu mutace (rozsah je 0 až 1). V b žném výpo tu se volí nízká hodnota, nap . 0,01, - generation gap - zna í etnost populace, která nep echází do další generace bez mutace a k ížení (rozsah je 0 až 1). V b žném výpo tu se volí vysoká hodnota, nap . 0,98. Volba parametr pro program pro optimalizaci je ukázána na obr.2.
Obr. 2 Volba parametr pro optimalizaci Uvedený jednoduchý problém vy ešíme pomocí programu takovým zp sobem, že program m ní polom r r a výšku v tak, aby povrch válce P byl minimální p i zachování 6
objemu V. Pro objem válce platí vzorec V = πr2v a pro povrch P = 2πr2 + 2πrv. Tyto vzorce zapíšeme do bun k programu Excel. Viz tab.5. B 2 3 4 5
C Výška V 0
D Polom r R 0
6
Povrch
P
=2*3.1415*D4*C4+2*3.1415*D4*D4
7
Objem
V
=3.1415*D4*D4*C4
Tab. 5 Tabulka závislosti vzorc V Excelu tedy máme výraz pro povrch v bu ce D6 a pro objem v bu ce D7. Hodnotu výšky v bu ce C4 nastavíme na 0 a polom r r v bu ce D4 také na 0. Viz obr.3.
Obr. 3 Tabulka p ed výpo tem Po spušt ní programu GeneHunter se zobrazí okno, kde navolíme údaje nezbytné pro výpo et. Viz obr.4.
Obr. 4 Volba parametr pro optimalizaci V našem p ípad je ú elová funkce rovnice pro povrch P, která se nachází v bu ce D6. Hledáme minimum této funkce, proto volíme Search for Min. Hodnoty, které program m ní,
7
jsou výška v a polom r r, které se nacházejí v bu ce C4 a D4. Typ chromozómu Chromozome type volíme Continuous, protože výška v a polom r r jsou ísla reálná. Dále volíme omezení maximálního a minimálního polom ru r a výšky v, která je dána nerovnicemi 0,5 <= v <= 4 a 0,1 <= r <= 2. Tato podmínka se zapíše ve volb Show list of ranges kliknutím na tla ítko Add. Protože výška v, která je umíst na v bu ce C4, má být menší jak 4, provedeme vypln ní tabulky, tak jak je to patrné na obr.5.
Obr. 5 Tvorba podmínek pro výpo et optimalizace Tuto innost opakujeme pro všechny podmínky. Viz obr.6.
Obr. 6 Omezující podmínky pro výšku v a polom r r Poslední podmínkou je, že objem nádoby má být deset litr . Tuto podmínku stanovíme s vysokou mírou platnosti (spln ní) s toleranci + 0,01. Tato podmínka se zapíše ve volb Show list of constraints vypln ním tabulky, tak jak je to patrné na obr.7. Objem V se nachází v bu ce D7.
Obr. 7 Tvorba podmínek pro výpo et optimalizace Navolená podmínka pro objem V je zobrazena na obr.8.
Obr. 8 Omezující podmínka pro objem V
8
Dále se provede navolení podmínek pro výpo et, kdy využijeme menu pro volby Options. Po et populace volíme st ední velikosti, tj. Population size = 100, délku chromozómu zvolíme také st ední, tj. Chromozome length = 16-bit, parametr k ížení, tj. Crossover rate = 0,9, parametr mutace, tj. Mutation rate = 0,01, parametr p echodu jedinc populace do další generace, tj. Generation gap = 0,98. Dále navolíme použití strategie elit Elitist strategy a diversifika ní operátor Diversity operator. Obnovu obrazovky p i výpo tu volíme ob asnou, tj. Screen diversity = Smart. Ukon ení programu m žeme navolit podmínkou, nedojde-li ke zm n populace po dobu 75 generací, program se ukon í. Viz obr.9.
Obr. 9 Volba parametr pro optimalizaci Máme-li nastaveny všechny parametry výpo tu, spustíme výpo et, který se po n kolika minutách ukon í. Výsledek optimalizace je patrný z tabulky 10. Zvolíme-li výšku v = 2,34 dm a polom r r = 1,14 dm, bude objem V = 10,01 litr a minimalizovaný povrch bude init P = 25,72 dm2.
Obr. 10 Tabulka po výpo tu P íklad 3. Velmi astou úlohou je aproximace nam ených bod polynomem. Tuto úlohu m žeme ešit regresní analýzou, lze použít i genetických algoritm . Máme nam eny xi a yi hodnoty dané tabulkou 6.
9
xi
yi
1 2 3 4 5
2.00 2. 91 3.56 5.45 8.08
yi’
xi
yi‘
yi
xi
yi
4.95 6 11.45 10.74 11 39.41 2.77 7 15.56 15.31 12 47.22 2.77 8 20.41 20.62 13 55.77 4.30 9 26.00 26.60 14 65.06 7.03 10 32.30 33.20 15 75.09 Tab. 6 Tabulka nam ených hodnot
yi‘ 40.35 48.03 56.19 64.80 73.85
Tyto nam ené body budeme chtít proložit polynomem 2. stupn tvaru y(x) = a2x2 + a1x + a0. Ú elová funkce, kterou se minimalizuje, je sou et kvadrát odchylek hodnot nam ených a vypo tených polynomem. M n né hodnoty jsou a2, a1, a a0. Po ukon ení výpo tu dostaneme hodnoty viz tab.7. a2 a1 a0 0.376 0.699 2.334 Tab.7 Hodnoty konstant Dosadíme-li získané konstanty do polynomu, má tvar y(x) = 0.376x2 – 0.699x + 2.334. Tab.7 zobrazuje nem ené hodnoty xi a yi a hodnoty vypo tené polynomem yi’. Obr.11 zobrazuje graf t chto skute ných hodnot a hodnot vypo tených polynomem. P ekrytí t chto k ivek je d kazem o správnosti výpo tu konstant polynomu. Hodnota ú elové funkce (suma kvadrát odchylek) je 16,88. 80 70 60 50 40 30 20 10 0
Obr. 11 Graf hodnot P íklad 4. Genetických algoritm lze použít pro ešení jednoduchých neuronových sítí. Viz obr.12. V kapitole o neuronových sítích byla zmínka, že u ící se proces neuronové sít lze interpretovat jako optimaliza ní úlohu s ú elovou funkcí E, definovanou v hyperprostoru, p i které se hledá její minimum. Pokud sestavíme tabulku, obsahující vstupní, výstupní hodnoty a hodnoty vah neuronové sít s odpovídajícími vzorci, lze spustit optimalizaci, která nastaví váhové koeficienty neuronové sít za pomoci genetických algoritm . Viz tab.8. Ú elová funkce, která se minimalizuje, je výpo et chyby E, která je definována vzorcem E=
(ni - oi )2,
kde ni je i-tá hodnota na výstupu a oi je i-tá o ekávaná hodnota. M n né hodnoty jsou w11,1, w11,2, w12,1, w12,2, b11, b12, w21,1, w22,1, b21. Horní indexy definují p íslušnost k vrstv .
10
Neuronová sí je u ena na vstupních hodnotách p1,k a p2,k s výstupem O1,k. Z obr.12 je patrné, že je-li vstupem dvojice 1,1 (0,0), je výstupem 1 (0). Pro výpo et je použito p enosové funkce tansig, jehož výstup je v intervalu (-1, 1). Smyslem použití transformace je modifikace úrovn výstup na normované hodnoty. vstupní vrstva
skrytá vrstva
výstupní vrstva a
w11,1
1
1
p1
p2
w11,2
w21,1
w12,1
w22,1 w12,2
a 12 b
1
b
1
1
a 21
b 21
2
Obr. 12 Typologie neuronové sít Výsledkem optimalizace je nastavení vah w11,1, w11,2, w12,1, w12,2, b11, b12, w21,1, w22,1, b21 tak, aby sí byla nau ená a dávala správné výsledky na výstupu po zadání vstupních hodnot. V tomto jednoduchém p íkladu bylo dosaženo nulové hodnoty chyby E. Viz tab.8. i 1 2 3 4
p1,k 1 0 0 1
p2,k 1 0 0 1
o1,k 1 0 0 1
w11,1 w12,1 b 11
-0.984 -0.090 0.812
w11,2 w12,2 b 12
-0.835 -0.796 0.663
a11,k -0.26 0.67 0.67 -0.26
a12,k -0.75 0.58 0.58 -0.75
a21,k 1.00 -1.00 -1.00 1.00
n1,k 1.00 0.00 0.00 1.00 E w21,1 w22,1 b 21
E1,k 0.00 0.00 0.00 0.00 0.00 -0.906 -0.875 0.114
Tab. 8 Zadané a vypo tené hodnoty Z uvedené ukázky, kdy bylo použito 5 neuron , je patrné, že realizace složit jší neuronové sít s v tším po tem neuron by byla výše uvedeným zp sobem velmi pracná.
P íklad 5. Genetických algoritm uvedeme následující p íklad.
lze použít pro stanovení optima výroby. Na ukázku
Máme vyrobit 12 výrobk , z toho 5 výrobk typu A, 3 výrobky typu B, 2 výrobky typu C, 1 typ výrobku D a E. K výrob je pot eba 6 r zných pracoviš . Doba ke zpracování r zných typ výrobk na r zných pracovištích je r zná a je dána k ížovou tab.9 vpravo naho e. Po et stroj na pracovištích je ur en uprost ed dole. Pokud bychom výrobky zadávali libovoln , nap . tak jak je to uvedeno v tabulce uprost ed, od ísla 1 po íslo 12, pot ebný as na zpracování všech výrobk , které by byly zadávány do výroby v uvedeném po adí, by inil 11
13 hodin 54 minut. Volit lze jak po et stroj na jednotlivých pracovištích, tak dobu zpracování r zných výrobk na r zných pracovištích. Plánování výroby: íslo výrobku
Typ výrobku
1 2 3 4 5 6 7 8 9 10 11 12
A B C D E A B C A A A A Celkový as:
Po adí výrobku Výchozí - stav - kone ný
1 2 3 4 5 6 7 8 9 10 11 12 13:54
První
Poslední
3 8 5 4 7 1 6 11 2 9 10 12 12:00
íslo pracovišt
A
B
C
D
E
1 2 3 4 5 6
0.1 0.2 0.3 0.4 0.3 0.2
0.2 0.3 0.4 0.3 0.2 0.1
1.5 2 2.5 2 1.5 1
0.7 0.6 0.5 0.4 0.8 0.3
0.6 0.3 0.4 0.5 5 0.8
íslo pracovišt
Po et stroj
1
1 2 3 4 5 2
2 3 4 5 6
Tab. 9 Optimalizace plánování výroby Ú elová funkce, která se minimalizuje, je celková doba výroby všech výrobk . Tuto úlohu je nutné naprogramovat a je sou ástí spoušt ného makra. M n nými hodnotami je po adí výrobk vstupujících do výroby, které je nastaveno na po átku v po adí 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Provedeme-li výpo et optimalizace programem GeneHunter, je ur eno po adí výrobk azených do technologického procesu tak, aby as výroby všech výrobk byl minimální. Po skon ení procesu optimalizace jsme obdrželi výsledek, že v p ípad azení výrobk do výroby v po adí 3, 8, 5, 4, 7, 1, 6, 11, 2, 9, 10, 12, bude celkový as výroby 12 hodin, tedy as tém o dv hodiny kratší. Takto lze optimalizovat výrobní proces, snížit náklady, pop . zvýšit zisk ve výrob .
P íklad 6. Genetických algoritm lze použít p i úloze d lení materiálu, tzn. stanovení ezných plán . Úloha m že být ešena pro materiál jedno, dvou i t í dimenzionální. Optimalizace tohoto problému umož uje minimalizovat odpad. ešení ezného plánu u jednorozm rné úlohy lze ukázat na následujícím p ípad . Na sklad jsou zásoby r zných délek potrubí (kulatiny, prut atd.), nap . 10 kus délky 4 m a 20 kus délky 5 m. Požadujeme 9 kus potrubí délky 1 m, 14 kus délky 2 m a 20 kus délky 3 m, p i emž chceme nalézt variantu, která zajistí nulové nebo minimální množství odpadu. Cílem je tedy ur ení po tu a velikosti trubek a ur ení zp sobu jejich roz ezání. Pro ešení je nutné ur it možné varianty roz ezání trubek, které jsou k dispozici na sklad . ezné varianty m žeme omezit nap íklad po tem trubek ve skladu. Ú elová funkce, kterou budeme minimalizovat, je odpad. M n né hodnoty jsou po ty kus , které mají být na ezány podle jednotlivých ezných plán . Viz tab.10. Po áte ní stav je dán nulovými po ty kus , které mají být na ezány u jednotlivých ezných variant. Po ukon ení výpo tu optimalizace obdržíme výsledek ve form po tu kus , které mají být na ezány u jednotlivých ezných 12
variant. Viz tabulka vpravo. P ípad je vy ešen pot ebou 3 kus trubek délky 4 m (tyto 3 kusy budou roz ezány po 1 jednometrovém kusu a 1 t ímetrovém kusu) a 17 kus trubek délky 5 m (3 kusy budou roz ezány po 2 jednometrových kusech a 1 t ímetrovém kuse, 14 kus bude roz ezáno po 1 dvoumetrovém kuse a po 1 t ímetrovém kuse). Tabulka dole zobrazuje výsledek optimalizace, kdy je ur en po et pot ebných trubek dostupných ve skladu (je kontrolováno maximální množství materiálu na sklad ), spln ní podmínky minimálního odpadu a kontrola správného množství na ezaného materiálu (není-li p ebytek). Vypo tený ezný plán nemusí spl ovat požadavek, že odpad bude nulový a po et na ezaných trubek bude p esn požadovaný, ale ešení se bude tomuto požadavku p ibližovat. Neúplné spln ní požadavk m že být dáno neexistencí ešení problému nebo skute ností, že algoritmus nenalezne nejlepší ešení. Nalezení co možná nejlepšího ešení m žeme realizovat opakováním procesu optimalizace s r zn nastavenými parametry optimaliza ního algoritmu, nap . velikostí populace, délkou chromozóm , parametrem k ížení, mutace, p echodu generace apod. Varianta
1m
4a
4
4b
3
2m
4c
2
1
4d
1
1
4e
1
5a
5
5b
4
5c
3
1
5d
2
1
5e
2
5f
1
5g
1
Varianta:
ks.
1m
2m
3m
4a
0 0 0 0
0
0
0
0
0
0
0
0
0
0
0
0
3 0
3
0
3
0
0
0
0 0 0 3 0 0
0
0
0
0
0
0
0
0
0
6
0
3
0
0
0
0
0
0
0
0
0
5i
0 14
0
14
14
1
4b
1
4d
4c 4e 5a 1
5b 5c
1
5d
1
5e
2
5f 1
2
5i
1
0
Zbytek
1
5h
Odpad:
3m
1
5g
1
5h
1
Délka:
1m
2m
3m
Díly 4m:
3
10
Skute nost:
9
14
20
Díly 5m:
17
20
Požadavek:
9
14
20
Skut.
Sklad
P ebytek(+):
0
0
0
Tvary: 1m 2m 3m Materiál: 4m 5m
Tab. 10 ezný plán – jednorozm rná úloha P íklad 7. Genetických algoritm lze využít p i shlukové analýze, tedy klastrování. Jedná se o zp sob, kdy se snažíme rozd lit data do oblastí (shluk , klastr ) a nalézt jejich st edy. Vstupem m že být libovolný po et vektor o libovolném po tu hodnot a lze zvolit libovolný po et oblastí. Úloha m že být vícedimenzionální. Jako p íklad bude uvedena dvou-dimenzionální úloha, ešící svoz odpadu, prezentovaná tab.11. Vstupem jsou sou adnice míst odvozu X a Y, uvedené ve 2. a 3. sloupci levé ásti tabulky. Ú elová funkce, která se minimalizuje, je sou et vzdáleností mezi místy odvozu a svozu. M n né hodnoty jsou sou adnice X, Y míst svozu A, B, C a p i azení míst svozu A, B, C k míst m odvozu. Po ukon ení procesu optimalizace dojde na základ zadaných sou adnic míst odvozu a zvoleného po tu (nap . t í míst svozu A, B, C) k rozd lení míst odvozu do t í oblastí a ur ení sou adnic místa svozu tak, aby vzdálenosti mezi místy odvozu a svozu byly minimální.
13
íslo místa odvozu
Sou adnice místa odvozu X Y ….. ….. 25.00 4.19
….. 22
P i azení místa svozu
A
23
16.00
2.62
A
24
111.00
16.79
C
25
66.80
10.10
B
26
20.40
4.10
A
27
120.00
17.01
C
28
56.80
5.69
B
29 …..
59.90 …..
10.80 …..
B …...
Tab. 11 Shluková analýza – ást vstupní tabulky Místo svozu
Sou adnice místa svozu X Y 18.4 3.1
A B
59.8
9.0
C
106.8
15.9
Tab. 12 Sou adnice míst svozu Výstupem jsou tedy nejen sou adnice t í míst svozu, vyhovující podmínce optimálnosti, ale i p i azení p íslušných míst odvozu k místu svozu. Viz tab.12 a pravý sloupec tab.11. Obr.13 reprezentuje grafickou realizaci uvedeného p íkladu. (P íklad byl uveden s ilustrativními sou adnicemi, v praxi však sou adnice míst odvozu budou více rozptýleny.) 20
B
15
10
C
A
5
0 0
20
40
60
80
100
120
Obr. 13 Místa odvozu a svozu A,B,C P íklad 8. Další ukázkou použití genetických algoritm je ešení úlohy obchodního cestujícího. Tato úloha spo ívá v nalezení nejkratší cesty, p i podmínce návšt vy všech zadaných míst pouze jednou. ešení této úlohy se stává tém nerealizovatelným i pro po íta v p ípad v tšího po tu míst, pokud bychom zkoumali všechny varianty. Použití genetických algoritm u této úlohy zkracuje dobu pot ebnou pro výpo et. Jako p íklad uvedeme p ípad m st v R, uvedených v tabulce 13. Vstupem je uvedená k ížová tabulka se vzdálenostmi mezi všemi m sty (jak je to uvád no v automapách), které se mají navštívit. Genetický algoritmus provádí optimalizaci tak, aby ujetá celková trasa byla co nejkratší, p i zachování podmínky, že každé m sto má být navštíveno jednou. Výsledkem je tedy doporu ené navštívení m st v takovém po adí, aby celková ujetá trasa byla minimální.
14
P ed opt.
Po opt.
M sto
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
6
Praha
0
202
362
94
275
102
112
140
92
104
297
31
349
133
123
2
9
Brno
202
0
165
296
78
239
142
186
294
138
100
233
152
335
93
3
1
Ostrava
362
165
0
456
93
335
240
346
454
240
104
393
35
495
253
4
12
Plze
94
296
456
0
369
196
206
133
146
198
391
87
443
83
186
5
14
Olomouc
275
78
93
369
0
246
149
259
367
147
63
306
74
408
166
6
4
Liberec
102
239
335
196
246
0
97
242
92
118
309
133
300
205
185
7
8
Hrad. Králové
112
142
240
206
149
97
0
217
166
21
212
143
205
245
110
8
15
. Bud jovice
140
186
346
133
259
242
217
0
232
196
281
166
333
216
126
9
2
Ústí n Labem
92
294
454
146
367
92
166
232
0
196
389
81
369
122
215
10
11
Pardubice
104
138
240
198
147
118
21
196
196
0
210
135
210
237
89
11
3
Zlín
297
100
104
391
63
309
212
281
389
210
0
328
111
430
188
12
13
Kladno
31
233
393
87
306
133
143
166
81
135
328
0
380
114
154
13
5
Opava
349
152
35
443
74
300
205
333
369
210
111
380
0
482
240
14
10
Karlovy Vary
133
335
495
83
408
205
245
216
122
237
430
114
482
0
256
15
7
Jihlava
123
93
253
186
166
185
110
126
215
89
188
154
240
256
0
Tab. 13 Obchodní cestující – k ížová tabulka vzdáleností m st Ú elová funkce, která se minimalizuje, je celková délka trasy ujetá mezi m sty. M n nými hodnotami je po adí m st, jak mají být navštíveny. P ed výpo tem je nutné nastavit inicializa ní hodnoty po adí m st, které je libovolné. V našem p ípad jsme inicializa ní hodnoty nastavili podle velikosti po tu obyvatel od 1 do 12. Viz tab.13, první sloupe ek vlevo. Délka ujeté trasy by v tomto p ípad byla 3959 km. Genetický algoritmus nalezl nejkratší celkovou trasu ve variant navštívení m st v po adí 6, 9, 1, 12, 14, 4, 8, 15, 2, 11, 3, 13, 5, 10, 7 s celkovou délkou 1342 km. Viz tab.13, druhý sloupe ek vlevo. Došlo tedy o zkrácení trasy o 2617 km, tedy o 66%. Trasa po R
Obr. 14a
Trasa po R
ešení úlohy obchodního cestujícího Obr. 14b
Pokud zobrazíme trasu mezi m sty v R v grafu, pak obdržíme obr.14a pro variantu s inicializa ními hodnotami p ed optimalizací a obr.14b pro variantu po optimalizaci. Uvedená úloha se velmi asto objevuje v praxi p i ešení dopravní obslužnosti m st, oblastí, kraj , svozu nebo rozvozu pošty, materiálu, odpad atd. Kritérium m že být nejen délka trasy, ale doba trvání cesty apod.
P íklad 9. Další použití genetických algoritm pro úlohy opera ní analýzy uvedeme na p ípadu, kdy t i prvky A, B, C jsou obsaženy ve ty ech slou eninách. Obsah prvk
15
v jednotlivých slou eninách, jakož i ceny slou enin a pot ebné množství prvk jsou v tab.14. Úkolem je zjistit, které slou eniny a v jakém množství je t eba nakoupit, abychom získali pot ebné množství prvk za nejnižší cenu.
A B C Cena slou eniny (K /kg)
S1
S2
S3
S4
0 2 10
2 2 5
4 0 4
5 4 10
15
10
12
25
Pot ebné množ. 5000 6000 18000
Tab. 14. Tabulka zadaných hodnot Pro výše uvedený p íklad m žeme psát soustavu nerovnic ve tvaru 2S2 + 4S3 + 5S4 >= 5000 2S1 + 2S2 + 4S4 >= 6000 10S1 + 5S2 + 4S3 +10S4 >= 18000 15S1 +10S2 + 12S3 + 25S4 = z Zp sob sestavení soustavy lineárních nerovnic je p edm tem ekonomicko matematických metod a nebude zde probírán. Podstatné pro náš p íklad je skute nost, že chceme minimalizovat náklady, které jsou dány ú elovou funkcí z. Optimalizací obdržíme údaje, které slou eniny a v jakém množství je t eba nakoupit, abychom získali pot ebné množství prvk co nejlevn ji. M žeme tedy op t využít možnosti optimalizace genetickými algoritmy M n nými veli inami budou pot ebné množství suroviny S1, S2, S3 a S4. Po áte ní nulové hodnoty množství surovin a p íslušné rovnice zapíšeme do tabulky Excelu. Viz tab. 15. 1 2 3 4 5 6 7 8 9 10 11
A Optimalizace výrobního programu Optimalizované prom nné S1 0 Ú elová funkce
B
C
D
S2 0
S3 0
S4 0
z= =15*A5+10*B5+12*C5+25*D5 Omezující podmínky A B C
=2*B5+4*C5+5*D5 =2*A5+2*B5+4*D5 =10*A5+5*B5+4*C5+10*D5
5000 6000 18000
Tab. 15 Tabulka vzorc a hodnot Je-li tab.15 vypln na, je pot ebné zadat do programu GeneHunter parametry pro výpo et. Viz obr.15.
16
Obr. 15 Volba parametr pro optimalizaci Optimalizace výrobního programu Optimalizované prom nné S1 S2 550 2500 Ú elová funkce z= 33250 Omezující podmínky 5000 A 6100 B 18000 C
S3 0
S4 0
5000 6000 18000
Tab. 16 Tabulka po optimalizaci Optimalizací hledáme minimum ú elové funkce z, kdy m níme množství suroviny S1, S2, S3 a S4. Omezení, vyplývající z uvedených nerovností, jsou zobrazeny ve spodní ásti okna. Po výpo tu obdržíme optimalizované hodnoty. Viz tab.16. Tedy optimálním (minimálním) ešením je koup 550 kg slou eniny S1 a 2500 kg slou eniny S2. Minimální hodnoty nákladu dosáhnou 33 250 K . Nad pot ebné množství získáme 100 kg prvku B. Viz údaj v p edposledním ádku tab.16, kde platí 6100 >= 6000.
P íklad 10. Jako p íklad použití programovacího pros edí MATLAB s Genetic Algorithm Toolboxem uvedeme nalezení minima Rastriginsovy funkce, která pat í svým pr b hem mezi ty, kterými se prov uje schopnost algoritm hledat optimum. Tato funkce je definována následujícím vzorcem z(x,y) = 20 + x2 +y2 – 10 * (cos2 x + cos2 y). Nejd íve budou popsány možnosti voleb. Spušt ní provedeme v p íkazovém okn p íkazem optimtool. Na obrazovce se zobrazí okno. Viz obr.16.
17
Obr. 16 Okno nástroje optimtool Jednotlivá menu mají následující významy. V levé ásti okna se zadává metoda ešení Solver, v našem p ípad ga-Genetic algorithm, dále odkaz na fitness funkci ve tvaru @fitnessf, kde fitnessf.m je M-soubor, který vrací hodnotu ú elové funkce v zadaném bod (pro zadaný vektor). Dále se specifikuje po et nezávislých prom nných fitness funkce, které jsou reprezentovány jednotlivými chromozomy a mají se optimalizovat. Lze zadat i omezení na prom nné ve tvaru soustavy lineárních (ne)rovnic A * x = b (resp. A * x b). Rovn ž lze vymezit dolní a horní hranice hodnot, které mohou nezávislé prom nné nabývat ve tvaru vektoru. Pokud je t eba použít nelineární omezení, musí se vytvo it M-soubor s názvem nap . omezeni.m, na který se v p íslušném poli odkážeme p es funkci @omezeni. Funkce popsaná v tomto souboru musí vracet vektory C a Ceq, které odpovídají nelineárním omezením tvaru C 0 a Ceq = 0. V další ásti okna se zadává, které funkce si p ejeme vykreslovat v pr b hu výpo tu - best fitness – zobrazuje hodnotu fitness funkce nejúsp šn jšího jedince dané generace, - expectation – zobrazuje o ekávaný po et potomk jednotlivých jedinc dané populace v závislosti na jejich „skóre“ (hodnot fitness funkce), - score diversity – zobrazuje histogram etností jednotlivých hodnot fitness funkce v dané generaci, - stopping – zobrazuje aktuální úrove kritérií pro ukon ení výpo tu, - best individual – zobrazuje hodnotu nezávislých prom nných pro nejúsp šn jšího jedince dané generace, - genealogy – zobrazuje genealogii jedinc ( erné linie ozna ují elitní jedince, kte í p echázejí do následující generace, ervené úse ky indikují jedince kte í vznikli mutací a modré úse ky spojují jedince, kte í vznikli k ížením s jejich rodi i), - scores – zobrazuje hodnoty fitness funkce pro jednotlivé jedince dané generace 18
-
max constraint – znázor uje maximální vzdálenost (míru nespln ní) nelineárního omezení pro danou generaci, distance – zobrazuje pr m rnou vzdálenost mezi jedinci v dané generaci, range – znázor uje minimální, maximální a pr m rnou hodnotu fitness funkce v dané generaci, selection – zobrazuje histogram po tu potomk p ipadajících na jednotlivé t ídy rodi v dané generaci.
Do pole Custom lze zadat libovolnou definovanou kreslící funkci formou M-souboru. Pole Plot interval popisuje frekvenci vykreslování výše popsaných grafických výstup . V pravé ásti okna se zadávají další parametry výpo tu týkající se zejména funkce k ížení, mutace a selekce. Lze využít již p eddefinovaných funkcí nebo si op t formou Msouboru vytvo it vlastní. Najdeme zde následující menu - population - zde se zadávají parametry týkající se námi zvolené populace, tj. typ populace (double, bit string, custom - vlastní), velikost populace (po et jedinc ), vytvo ující funkci (uniform – pomocí rovnom rného rozd lení, custom - vlastní), po áte ní populaci, po áte ní skóre a interval, z n hož se mají vybírat hodnoty pro po áte ní populaci, - fitness scaling – zde se zadává zp sob, jakým budou hodnoceni jedinci dané populace (lze volit: rank – vychází z po adí jedinc , proportional – proporcionáln odpovídá hodnot fitness funkce, top – zadává se po et nejlepších jedinc , kte í budou produkovat potomky, shift linear – zadává se konstanta o ekávání pro nejlepšího jedince, custom - vlastní), - selection – zde se zadává, jakým zp sobem se budou vybírat rodi e pro vznik další generace (stochastic uniform – náhodný rovnom rný výb r vzhledem k o ekávání, remainder – deterministický výb r s užitím rulety, uniform – náhodný výb r z rovnom rného rozd lení s ohledem na o ekávání a po et rodi , roulette – simuluje kolo rulety, kde jednotlivá pole odpovídají o ekávání jednotlivých segment rodi , tournament – náhodn vybere ur itý po et jedinc a z nich toho nejlepšího, custom vlastní), - reproduction – do pole elite count se zadává po et nejlepších jedinc , kte í automaticky p echázejí do další generace a dále se zadává, kolik procent jedinc bude krom t chto elitních vytvo eno k ížením (crossover fraction), zbývající po et vznikne mutací, - mutation – zde se zadává, jakým zp sobem bude probíhat mutace (Gaussian – na základ Gaussova rozd lení, uniform – na základ rovnom rného rozd lení, adaptive feasible – adaptivn s ohledem na dodržení omezení, custom - vlastní), - crossover – zde se zadává zp sob k ížení (scattered – zobecn né k ížení, single point – jednobodové k ížení, two point – dvoubodové k ížení, intermediate – vážený pr m r rodi , heuristic – uvažuje i ú elovou funkci, arithmetic – vážený aritmetický pr m r rodi s ohledem na p ípustnost, custom - vlastní), - migration – migrací se rozumí pohyb jedinc mezi subpopulacemi a používá se, zadáme-li velikost populace ve tvaru vektoru délky alespo 2. Nejlepší jedinci jedné subpopulace tak nahrazují nejhorší jedince druhé subpopulace. M že jít o migraci dop ednou forward, kdy jedinci p echázejí z n - té do n+1 - té populace nebo o migraci ob ma sm ry both. Po et p echázejících jedinc se zadává zlomkem fraction a frekvence migrace íslem interval,
19
-
-
algorithm settings initial penalty – po áte ní penalizace algoritmu (v tší než 1), penalty factor – zvyšuje hodnotu parametru penalizace, není-li problém vy ešen s požadovanou p esností a omezení nejsou spln na (v tší než 1), hybrid function – zde se nastavuje další optimaliza ní funkce, která se spustí po ukon ení genetického algoritmu (fminsearch, patternsearch, fminunc, fmincon), stopping criteria – zde se zadávají kritéria pro ukon ení výpo tu (po et generací, asový limit, fitness limit, po et generací, po které nedojde k významné zm n fitness funkce, as, po který nedojde k významné zm n fitness funkce, kumulativní zm na fitness funkce, maximální tolerance porušení nelineárního omezení), output function – zde lze zadat výpis historie algoritmu, display to command window – zde lze zadat, jaké informace si p ejeme zobrazovat v p íkazovém okn (iterative – v každé iteraci výpo tu, diagnose – navíc se zobrazí další informace, final – zobrazí se d vod ukon ení výpo tu), vectorize – vektorizace udává, zda se fitness funkce volá pro každého jedince zvláš .
Po zadání všech parametr algoritmu se spustí výpo et stiskem tla ítka Start. Výpo et lze kdykoli pozastavit stiskem tla ítka Pause, resp. zastavit tla ítkem Stop. V p íkazovém okn se pak objeví popis pr b hu výpo tu a na záv r výsledné hodnoty nezávisle prom nných. Pro výpo et v programovém prost edí MATLAB musíme nejd íve naprogramovat Rastriginsovu funkci v M-souboru, který nazveme rfcn.m. Viz prog.1. function scores = rfcn(pop) scores = 10.0 * size(pop,2) + sum(pop .^2 - 10.0 * cos(2 * pi .* pop),2); Prog. 1 Rastriginsova funkce Do okna Optimization Tools se zadá do pole Solver metoda ga - Genetic Algorithm a do Fitness function ú elová funkce zapsaná v M-souboru @rfcn a do pole Number of variables po et prom nných 2. Ostatní parametry lze ponechat s defaultním nastavením. Takto p ipravené údaje nám umožní spustit výpo et tla ítkem Start. Viz obr.16. Po ukon ení výpo tu obdržíme výsledky v okn Final point 1 a 2. Výsledek nás informuje, že p i hodnotách x = 0 a y = 0 je nalezene minimum, který najdeme v poli Status and results, kde hodnota fitness funkce Fitness function value z = 0. Minimum funkce se nachází na sou adnicích [0 0] a jho hodnota je nulová, což odpovídá výpo tu. Viz obr.16.
P íklad 11. Pro ukázku ešení v prost edí MATLAB využijeme p ípad popsaný v p íkladu 2. Pro výrobu desetilitrových plechovek budeme chtít ur it polom r plechovky r a její výšku v tak, aby spot eba materiálu byla minimální. Tento úkol vy ešíme pomocí programu takovým zp sobem, že program m ní polom r r a výšku v tak, aby povrch válce P byl minimální p i zachování objemu V. Pro objem válce platí vzorec V = πr2v a pro povrch P = 2πr2 + 2πrv. P i použití Genetic Algorithm Toolboxu v programovém prost edí MATLAB musíme nejd íve definovat fitness funkci povrch_fun jako soubor povrch_fun.m. Viz prog.2. function z = povrch_fun(x) z = 2*3.1415*x(1)*x(1)+2*3.1415*x(1)*x(2); Prog. 2 Funkce výpo tu povrchu
20
Dále je zapot ebí zadat op t v souboru typu M-file nelineární omezení, které odpovídá zadanému objemu. Funkci nazveme omezeni. Viz prog.3. function [c, ceq] = omezení(x) c = []; ceq = [3.1415*x(1)*x(1)*x(2)-10]; Prog. 3 Funkce omezení konstantního objemu Po spušt ní p íkazu optimtool a zvolení ešitele Solver ga - Genetic Algorithm je nutné do okna Optimization Tool zadat do pole Fitness function ú elovou funkci zapsanou v M-souboru @povrch_fun, do pole Number of variables po et prom nných 2, omezení, že ešením jsou pouze nezáporná ísla tj. r 0 a v 0 zapíšeme do pole Bounds Lower [0 0], omezení že objem V má být konstantní je zapsán v souboru omezeni.m a proto je nutné tuto skute nost uvést do pole Nonlinear constraint function ve tvaru @omezení. Pokud chceme p i výpo tu sledovat pr b h hodnoty ú elové funkce, zaškrtneme polí ko Best fitness. Je vhodné zm nit velikost populace na po et 100. Proto v poli Population size zapíšeme 100. Ostatní parametry ponecháme s defaultním nastavením. Viz obr.18. Takto p ipravené údaje v tabulce nám umožní spustit výpo et tla ítkem Start. Pr b h výpo tu m žeme sledovat na grafu zobrazující hodnoty ú elové funkce. Viz obr.17. Po ukon ení výpo tu obdržíme výsledky v okn Final point 1 a 2. Výsledek nás informuje, že p i polom ru r = 1,17 dm a výšce v = 2,34 dm je povrch optimalizovaný na minimum. Údaj o velikosti povrchu se dozvíme v poli Status and results, kde hodnota fitness funkce Fitness function value P = 25,6947 dm2. Zde je také uvedena informace o ukon ení optimalizace, kdy chyba výpo tu je nižšší jak nastavená Current tolerance on f(x) =3.4383e-32. Ukazuje se, že s vyšším po tem jedinc v populaci se p esnost výpo tu zvyšuje. Okno nástroje optimtool po výpo tu je na obr.18.
Obr. 17 Graf pr b hu hodnot ú elové funkce p i výpo tu
21
Literatura: DOSTÁL, P. Moderní metody ekonomických analýz, UTB – FAME - Zlín 2002, ISBN 80-7318-075-8. DOSTÁL, P., RAIS, K., SOJKA, Z. Pokro ilé metody manažerského rozhodování, Grada, 2005. DAVIS L. Handbook of Genetic Algorithms, Int. Thomson Com. Press, 1991, ISBN 1-850-32825-0. THE MATHWORKS. MATLAB – Genetic Algorith Toolbox - User’s Guide, The MathWorks, Inc., 2008.
22
