Heuristiky UNIVERZITA PALACKÉHO V OLOMOUCI KATEDRA MATEMATICKÉ ANALÝZY A APLIKACÍ MATEMATIKY. Vypracovala:

UNIVERZITA PALACKÉHO V OLOMOUCI PŘÍRODOVĚDECKÁ FAKULTA KATEDRA MATEMATICKÉ ANALÝZY A APLIKACÍ MATEMATIKY

BAKALÁŘSKÁ PRÁCE Heuristiky

Vedoucí bakalářské práce: Mgr. Jaroslav Marek, Ph.D. Rok odevzdání: 2008

Vypracovala: Lucie Koděrová ME, III. ročník

Prohlášení Prohlašuji, že jsem tuto bakalářskou práci vypracovala samostatně za odborného vedení Mgr. Jaroslava Marka Ph.D. Dále prohlašuji, že veškeré podklady, ze kterých jsem čerpala, jsou uvedeny v seznamu literatury.

V Olomouci dne 8. dubna 2008

Poděkování Ráda bych poděkovala Mgr. Jaroslavu Markovi, Ph.D. za jeho trpělivost, úsilí, rady a čas, který mi věnoval při konzultacích.

Obsah Úvod

4

1 Globální optimalizace 1.1 Metody klasické optimalizace . . . . . . . . . . . . . . . . . 1.2 Řešení optimalizačních úloh pomocí stochastických algoritmů 1.3 Problematika využívání stochastických algoritmů . . . . . . 1.4 Evoluční algoritmy . . . . . . . . . . . . . . . . . . . . . . .

5 5 6 7 8

. . . .

. . . .

. . . .

2 Testovací funkce 3 Algoritmy pro globální optimalizaci 3.1 Genetické algoritmy . . . . . . . . . . . . . . . . . 3.2 Slepé prohledávání . . . . . . . . . . . . . . . . . 3.3 Horolezecký algoritmus . . . . . . . . . . . . . . . 3.4 Algoritmus SOMA . . . . . . . . . . . . . . . . . 3.5 Diferenciální evoluce (DE) . . . . . . . . . . . . . 3.6 Metoda simulovaného žíhání . . . . . . . . . . . . 3.6.1 Fyzikální interpretace žíhání tuhého tělesa 3.6.2 Metropolisův algoritmus . . . . . . . . . . 3.6.3 Simulované žíhání . . . . . . . . . . . . . . 3.6.4 Simulované žíhání s elitizmem . . . . . . . 3.6.5 Paralelní simulované žíhání . . . . . . . . 3.7 Vlastní algoritmus RYPOŠ . . . . . . . . . . . . .

9

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

12 12 13 14 15 17 18 18 19 20 22 22 23

4 Aplikace heuristik

28

5 Testování uvedených algoritmů – praktická část

29

6 Závěr

36

Literatura

38

Přílohy

40

Úvod Optimalizační problémy jsou s naším běžným životem provázány pevněji, než by se mohlo zdát. Setkáme se s nimi například při hledání nejvhodnějších dokumentů obsahujících požadované informace, při objevování nejzajímavějších informací v dostupných datech, rozmisťování strojů ve výrobní hale tak, aby zabíraly co nejméně místa, a při dalších činnostech, kdy můžeme výsledné hodnoty získat pouze empiricky. Optimalizací rozumíme postup zaměřený na nalezení určitého vyhovujícího řešení nějaké úlohy. Protože deterministické algoritmy mnohdy při řešení úlohy globální optimalizace selhávaly, začaly být nahrazovány algoritmy heuristickými. Moderní informatika se při navrhování nových algoritmů, postupů a metod inspiruje v okolním světě, převážně v přírodě. Darwinova evoluční teorie posloužila odborníkům jako základ evolučních algoritmů, které tvoří aktuální problematiku informatiky a numerické matematiky. Počítačové simulace evolučních algoritmů mohou vědcům pomoci získat odpovědi na různé důležité otázky z biologie, psychologie, sociologie atd. Vznikly také evoluční algoritmy, které svoji inspiraci nehledaly v živé přírodě, ale ve fyzice. Patří mezi ně metoda simulovaného žíhání (Simulated Annealing, SA), která vychází z představ evoluce termodynamických systémů. Objasnění principu metody simulovaného žíhání a její implementace je jedním z cílů této bakalářské práce. Hlavním úkolem je obeznámit čtenáře s problémem stochastické optimalizace, zmínit problémy spojené s použitím stochastických algoritmů pro hledání globálních extrémů (slepého prohledávání, horolezeckých algoritmů, zakázaného hledání, simulovaného žíhání, genetických algoritmů, diferenciální evoluci). Potřeba porovnat úspěšnost jednotlivých algoritmů vedla k zavedení tzv. testovacích funkcí. V práci provedeme vyhodnocení úspěšnosti uvedených algoritmů na těchto testovacích funkcích (např. Ackleyho funkce, De Jongova funkce, Griewangkova funkce, Rastrigova funkce, Rosenbrockovo sedlo, Schwefelova funkce). V práci navrhneme vlastní algoritmus a prozkoumáme jeho úspěšnost. 4

1. Globální optimalizace Při řešení problému globální optimalizace (podrobněji popsáno např. v [1]) hledáme pro danou účelovou funkci f : D → R, D ⊂ Rd ,

(1)

x? = arg minx∈D f (x) .

(2)

bod x? tak, aby

Bod x* se nazývá globální minimum. Pro jednoduchost budeme uvažovat, že D je souvislá množina tvaru

D=

d Y hai , bi i, ai < bi , i = 1, . . . , d .

(3)

i=1

Pod pojmem heuristika budeme chápat nedeterministické pravidlo, které z bodů více či méně náhodně generované populace vytváří posloupnost bodů, které aproximují globální minimum.

1.1. Metody klasické optimalizace Než se začneme zabývat stochastickými metodami optimalizace minima, zmíníme nejprve základní klasické metody pro řešení těchto úloh. Klasickými metodami se rozumí takové, které se opírají o podmínky optimality (podrobně je studováno např. ve skriptech [2]). Pro diferencovatelnou funkci f stanovíme stacionární body, tj. všechna řešení rovnice grad f (x) = 0. Ty z nich, v nichž je Hessova matice pozitivně definitní, jsou body minima. Hessova matice má tvar  H=

∂f (x) ∂xi ∂xj

 i, j = 1, . . . , n .

Pozitivně definitní je taková matice A, pro kterou platí: • x0 Ax > 0 pro každý nenulový vektor x ∈ Rd , • všechna vlastní čísla matice A jsou kladná, 5

(4)

• všechny hlavní minory M1 , M2 , . . . , Md matice A jsou kladné. Poznámka. Minor příslušný k prvku ai,j matice A je determinant matice Ai,j , kterou získáme z matice A odstraněním i-tého řádku a j-tého sloupce. Pokud nemáme podrobnější informace o účelové funkci f , každá z následujících metod určuje v případě optimalizace bez omezení lokální řešení. Metody pro řešení úloh nepodmíněné optimalizace rozdělujeme do tří kategorií podle požadavků na hladkost funkce f . Metody přímého výběru – nevyžadují výpočty derivací. Speciální spádové metody – vyžadují výpočet gradientů (např. metoda největšího spádu, kvazinewtonovské metody). Newtonova metoda – vyžaduje výpočet druhých derivací. Protože případy globální optimalizace řešíme často především v praxi, je velmi důležité zabývat se také teoretickou stránkou, všeobecnou úlohou globální optimalizace. Mnohdy velmi jednoduchá formulace celého optimalizačního problému může být matoucí a vyvolávat dojem, že určení deterministického algoritmu řešícího všeobecnou úlohu globální optimalizace je jednoduché. Ve skutečnosti analýza ukazuje, že takovýto deterministický algoritmus neexistuje. Dále budeme tedy uvažovat pro řešení těchto problémů stochastické algoritmy.

1.2. Řešení optimalizačních úloh pomocí stochastických algoritmů Alternativou pro řešení složitých optimalizačních příkladů je použití stochastických algoritmů, především evolučních algoritmů, jejichž popularita stále roste. Tak zvané heuristické metody jsou vesměs založeny na principu postupného zlepšování řešení. Tyto algoritmy nám sice umožní nalézt globální optimum, ale v průběhu hledání nejsme schopni určit ani vzdálenost aktuálně dosaženého řešení od globálního optima, ani s jakou pravděpodobností může být globálního optima dosaženo. 6

Evoluční algoritmy jsou typické svojí robustností – schopností řešit obtížné optimalizační úlohy, nebo úlohy, ve kterých potřebujeme o něčem rozhodnout. Lze je charakterizovat vlastnostmi jako je multimodálnost a multikriteriálnost. Jejich nasazení je efektivní v úlohách, které lze definovat následovně: • Prostor řešení je příliš rozsáhlý a chybí odborná znalost, která by umožnila zúžit prostor slibných řešení. • Nelze provést matematickou analýzu problému. • Tradiční metody selhávají. • Jde o úlohy s mnohačetnými extrémy, kritérii a omezujícími podmínkami. Evoluční algoritmy mají v praxi široké použití v různorodých odvětvích od strojového plánování až po ekonomii a psychologii. Je však třeba poukázat na jisté nevýhody evolučních algoritmů.

1.3. Problematika využívání stochastických algoritmů Úlohy, které jsou pro nás deterministicky neřešitelné, nám pomáhají vyřešit stochastické algoritmy. Tím se sice dozvíme výsledek složitého úkolu, ale musíme vzít na vědomí, že používání heuristických metod je spojeno s problémy ovlivňujícími kvalitu řešení. Tato podkapitola vychází ze zdroje [3]. Na rozdíl od jiných optimalizačních metod stanovují evoluční algoritmy optimum dané funkce pouze na základě práce s jejími funkčními hodnotami. Získání těchto funkčních hodnot bývá často hodně nákladné a časově náročné. Blíží se proto k optimu velmi pomalu vzhledem k jiným optimalizačním metodám, které navíc využívají ještě informace o gradientu cílové funkce, případně o jejích druhých derivacích. Pokud ovšem známe z předchozích zkušeností hodnoty cílové funkce, můžeme pro optimalizaci sestrojit aproximaci založenou na základě této databáze. Původní funkci potom používáme pouze pro ověřování výsledků získaných pomocí její aproximace. Tímto postupem můžeme docílit snížení nákladů na testování. Dále bychom si měli před užitím evolučního algoritmu uvědomit, že daný konkrétní typ algoritmu se hodí pro řešení jen určitého okruhu problémů. Evoluční 7

algoritmy nejsou tedy vhodné pro řešení všech úloh. Neměli bychom proto také zapomínat na škálu klasických metod (např. uvedených v kapitole 1.1), které jsou schopny vyřešit řadu optimalizačních úloh s relativně nízkou výpočetní náročností. Shrnutí nevýhod evolučních algorimů: • Pro mnohé úlohy je typická velká časová náročnost. • Nelze otestovat, zda se jedná o globální optimum. • Pro příliš rozsáhlé úlohy poskytují řešení příliš vzdálená od optima. • Ukončení optimalizace je předem určené na základě časového limitu nebo stagnace kriteriální funkce.

1.4. Evoluční algoritmy Evoluční algoritmy jsou algoritmy založené na základě Darwinovy evoluční teorie vývoje populací. Vycházejí tedy z poznatků převzatých z života v přírodě a aplikují zákonitosti, které použil Darwin ve své teorii. Populací chápeme všeobecné vyjádření sledu generací. Při práci s populacemi využívají evoluční algoritmy také evolučních operátorů: selekce, křížení a mutace. selekce – předpokládáme, že nejsilnější jedinci z populace mají větší pravděpodobnost přežít a předat své vlastnosti, křížení – dva nebo více jedinců z populace si vymění informace a vzniknou noví jedinci, kteří kombinují vlastnosti rodičů, mutace – informace zakódovaná v jedinci může být náhodně změněna. Předpis evolučního algoritmu bez explicitní mutace (viz [1]): procedura EA vygenerujeme P (populaci o N bodech náhodně vybranou z D) repeat najdeme nejhorší bod v P , xworst , s nejlepší hodnotou f zkopírujeme M nejlepších bodů z P do nové populace Q, 1 ≤ M < N repeat 8

repeat vygenerujeme nový zkušební bod y podle heuristiky aplikované na P until f (y) ≤ xworst zapisujeme nové zkušební body do Q until Q není tvořeno N body nahradíme P za Q dokud není splněna ukončovací podmínka end Za heuristiku zde považujeme libovolné nedeterministické pravidlo generující nový bod y ∈ D, většinou tím míníme postup užívající evoluční operátory, který z bodů v generaci P vygeneruje nový bod y ∈ D.

2. Testovací funkce Pro testování spolehlivosti a úspěšnosti algoritmů jsou využívány speciální testovací funkce, jejichž hodnotu globálního minima známe a u nichž je úloha optimalizace extrému velmi složitá. Pro praktické testování bylo použito těchto šest funkcí: Ackleyho funkce, první De Jongova funkce, Griewangkova funkce, Rastrigova funkce, Rosenbrockovo sedlo (Druhá De Jongova funkce) a Schwefelova funkce. Jejich funkční předpisy, definiční obory a reálné hodnoty minima jsou převzaté z [4] a jsou uvedeny u jednotlivých grafů (viz obr. 2.1 a) – f)), které byly vykresleny pomocí Matlabu vždy pro případ Dim = d = 2.

9

a) Ackleyho funkce D = h−30, 30i × · · · × h−30, 30i, minimum x = (0, . . . , 0), f (x) = 0

funkční předpis: f (x) =

PDim −1 i=1

(20 + e−0.2

√

0.5(x2i−1 −x2i )

− e0.5(cos(2πxi+1 )+cos(2πxi )) )

b) První DeJongova funkce D = h−5.12, 5.12i × · · · × h−5.12, 5.12i, minimum x = (0, . . . , 0), f (x) = 0

funkční předpis: f (x) =

PDim i=1

x2i

c) Griewangkova funkce D = h−600, 600i × · · · × h−600, 600i, minimum x = (0, . . . , 0), f (x) = 0

funkční předpis: f (x) = −

QDim i=1

xi cos( √ + i

PDim i=1

x2i 4000

+ 1)

Obr. 2.1: Testovací funkce, předpisy, globální minima a jejich funkční hodnoty

d) Rastrigova funkce D = h−5.12, 5.12i × · · · × h−5.12, 5.12i, minimum x = (0, . . . , 0), f (x) = 0

funkční předpis: f (x) = 10 Dim

PDim i=1

(x2i − 10 cos(2πxi ))

e) Rosenbrockovo sedlo D = h−2.048, 2.048i × · · · × h−2.048, 2.048i, minimum x = (1, . . . , 1), f (x) = 0

funkční předpis: f (x) =

PDim −1 i=1

(100(x2i − xi+1 )2 + (1 − xi )2 )

f) Schwefelova funkce D = h−a, ai × · · · × h−a, ai, a = 500.12, minimum x = (420.97, . . . , 420.97), f (x) = −418.9829 ∗ d

funkční předpis: f (x) =

PDim i=1

p −xi sin( |xi |)

Obr. 2.1: Testovací funkce, předpisy, globální minima a jejich funkční hodnoty

3. Algoritmy pro globální optimalizaci Heuristiky můžeme popsat jako zkratkovitý postup hledání založený na zkušenostech, poskytující řešení v přijatelném čase, ale bez záruky na správný výsledek. Lze je použít, pokud na řešení úlohy neexistuje jednoznačný algoritmus, nebo je hledání pomocí něj příliš zdlouhavé. Vzhledem k obtížnosti problematiky globální optimalizace se mnohdy musíme spokojit pouze s určitou pravděpodobností, že při hledání uspějeme. Záměrem je umět poznat a zkoušet řídit pravděpodobnost správného řešení. Určit, jaké minimální množství pokusů musíme provést, abychom se dostali na přiměřenou hladinu rizika neúspěchu. Existuje celá řada užívaných algoritmů, které pomáhají řešit optimalizační úlohy. Pro bližší seznámení jsem si vybrala metody: genetické algoritmy, slepé prohledávání, horolezecké algoritmy, zakázané hledání, simulované žíhání, diferenciální evoluci a algoritmus SOMA. Princip fungování stochastických algoritmů je dobře popsán ve zdrojích [6], [7] a [12].

3.1. Genetické algoritmy Genetické algoritmy jsou druhem evolučních algoritmů, jsou nejlépe popsány ve zdrojích [3], [5]. Jejich základní myšlenka spočívá v zakódování informace při hledání tak, aby slabší generace byla v dalším kroku nahrazena lepší generací. Při hledání optima můžeme považovat body na funkci za části dědičného materiálu a potom uplatnit evoluční operátory (křížení, mutace), stejně jako je pozorujeme v přírodě. Řízení heuristiky je možné pomocí parametrizace nebo selekce. Nabízí se zde možnosti jako: • Mutaci a křížení lze řídit elitářstvím, řízenou mutací (určíme sílu mutace a její úbytek v průběhu generace), řízením křížení (určíme procentuální část neelitního podílu populace, která se bude křížit). • Nastavením maximálního počtu generací. 12

• Řízením výběru rodiče na základě jeho fitness (síla, robustnost, ohodnocení). • Porovnávání fitness pro snazší nalezení vhodných rodičů pro budoucí generaci. • Handicapováním oblasti hledání, o které víme, že zde pravděpodobně globální extrém neleží. • Užití vyhledávacího algoritmu na dohledání optima poté, co genetické algoritmy ukončily svou činnost.

3.2. Slepé prohledávání Nejjednodušším způsobem hledání optimálního řešení je jeho náhodné (stochastické) hledání. Vygeneruje se náhodné řešení a toto řešení se vyzkouší, t.j. vyhodnotí se jeho fitness funkce. První řešení je zaznamenáno vždy, dále zaznamenáváme jen ta řešení, kdy je fitness nového nalezeného minima větší než fitness nejlepšího doposud nalezeného. Pokračuje se generováním dalšího řešení a jeho vyzkoušením. Důležitým faktorem je tu náhodnost každé iterace. Každé minimum je nalezeno bez souvislosti s předcházejícími. Mohlo by se zdát, že optimalizace v této formě nemá praktické uplatnění. Této metodě sice chybí cílenost vývoje (tzv. „selekční tlakÿ), ale na druhou stranu se úspěšně vyhýbá problému uváznutí v lokálním minimu, který je typický pro gradientní metody. Vyhovující řešení může být nalezeno na několik málo pokusů, stejně tak nemusí být nalezené vůbec (zvlášť při vícerozměrné úloze). Proto se náhodné prohledávání stavového prostoru používá především na inicializaci některých jiných metod, zejména metod založených na množině řešení (populaci). Popsaný algoritmus má v programu Matlab tento předpis: function [x,fx] = blindsearch(fn name, a, b, t) % vstupní parametry: % fn_name % a,b

minimalizovaná funkce (M file) řádek vektorů, hranice prohledávacího prostoru 13

% t

číslo iterace

% výstupní parametry: % fx

nalezená minimální funkční hodnota

% x

hledáním nalezeného minima

d=length(a); fx=realmax; for i = 1 : t y=a+(b-a).*rand(1,d); fy= feval(fn name, y); if fy < fx x=y f(x)=f(y) end end

3.3. Horolezecký algoritmus Slepý algoritmus můžeme dále proměnit na tzv. horolezecký algoritmus (hill climbing), kde se iteračně hledá nejlepší lokání řešení v určitém okolí, a to je v dalším kroku použito jako střed nové oblasti. Základním principem horolezeckého algoritmu je tedy prohledání lokálního okolí nejlepšího nalezeného řešení (nebo náhodně vygenerovaného řešení na začátku optimalizace). Namísto náhodného hledání dalšího řešení se použije nejlepší doposud nalezené řešení (střed oblasti), ve kterém se vytvoří určitá malá změna (např. změníme 5 % parametrů tohoto řešení). Nový bod se přijme, pokud je lepší než ten, ze kterého vznikl. Pokud je horší, opět se provede jiná malá změna nejlepšího řešení. Z principu průběhu horolezeckého algoritmu je patrná silná závislost mezi předcházejícím a novým řešením. Horolezecké algoritmy jsou typické rychlým zjištěním lokálního extrému, ve kterém uváznou, pokud se v prohledávaném okolí nenachází lepší řešení. Proto se horolezecké metody při optimalizaci používají na „dotáhnutí do extrémuÿ řešení 14

nalezeného jinou metodou. Jiné varianty horolezeckého algoritmu jsou horolezecký algoritmus s učením a zakázané hledání (tabu search). Průběh horolezeckého algoritmu (viz [8], str. 43): procedura horolezecký algoritmus begin generování P (populace o N bodech náhodně vybranou z D) repeat localpoint = false náhodně z populace vyber bod v a urči jeho funkční hodnotu repeat vyber všechny nové body z okolí vc vyber bod vn ze sady nových bodů s nejmenší hodnotou if hodnota vn lepší než hodnota vc then hodnota vc = vn else localpoint = true until localpoint t=t+1 if vc je lepší než nejlepší bod v then hodnota v = vc until t=max end

3.4. Algoritmus SOMA Optimalizační algoritmus SOMA (Self-Organizing migrating algorithm), jehož autorem je Ivan Zelinka (viz [4]), je charakteristický především prací s populací řešení, uplatňují se v něm strategie soutěže a spolupráce. V algoritmu SOMA se nevytváří žádní noví jedinci, dochází pouze k jejich přemisťování ve stavovém prostoru. Samoorganizace prostoru, o které se hovoří v názvu algoritmu, vzniká v důsledku vzájemného působení jedinců populace v průběhu jejich pohybu. 15

V Algoritmu SOMA chápeme souřadnice jedince ve stavovém prostoru jako hodnoty parametrů, což umožňuje dobrou geometrickou interpretovatelnost a detailní vykreslení průběhu algoritmu. Vycházíme z náhodného počtu jedinců, u kterých vyhodnotíme jejich fitness. Na základě té se určí nejlepší jedinec – lídr. Pak vytvoříme další populaci, ve které se každý jedinec mimo lídra pokusí najít vhodnější polohu v prostoru skoky určité délky po přímce směrem k vůdci. Skoky mají normální rozdělení se střední hodnotou, kterou je délka skoku, a rozptylem, který způsobuje nárůst diverzity v populaci. Po absolvování celé cesty se jedinec v další populaci usadí na nejvýhodnějším místě z celé trasy.

Obr. 3.1: Znázornění průběhu algoritmu SOMA, viz [9] Migrace jedince (A) směrem k lídrovi (L). Jedinec se pohybuje skoky a ohodnocuje každou pozici (prázdné kroužky), na kterou skočí. Po průchodu celé trajektorie se usadí na té pozici, která měla nejlepší ohodnocení (viz obr. 3.1, bod B). Původní populaci tvoří modré body a červený lídr. Variací algoritmu SOMA je mnoho, uvedeme zde jen dvě základní: All-to-one — „Všichni k jedinému.ÿ Základní variace algoritmu, kdy všichni jedinci z populace migrují k statickému lídrovi. All-to-All — „Všichni ke všem.ÿ V této variaci neexistuje lídr, každý jedinec migruje ke všem ostatním, což zvyšuje výpočetní náročnost, prohledávaný prostor 16

a pravděpodobnost nalezení globálního extrému. Dalšími variantami jsou například: All-to-One-Rand — „Všichni k jedinému náhodněÿ, All-To-All-Adaptive — „Adaptivně všichni ke všemÿ, Clusters — „Svazkyÿ. Jednotlivé varianty jsou popsány v [4] a [9].

3.5. Diferenciální evoluce (DE) Nová populace Q je v algoritmu diferenciální evoluce vytvářena tak, že pro každý bod ze staré populace P se vytvoří jeho potenciální konkurent y. Do nové populace zahrneme ten z této dvojice bodů, který má nižší funkční hodnotu. Zkřížíme-li bod u a bod xi tak, že kterýkoliv prvek xij nahradíme hodnotou uj s pravděpodobností C, získáme nového potenciálního konkurenta y. Nejčastěji používané postupy na generování nového bod u jsou: Postup RAND, který generuje bod u ze třech bodů ze staré populace podle vztahu: u = r1 + F (r1 − r3 ) ,

(5)

kde r1 , r2 a r3 jsou navzájem různé body náhodně vybrané z populace P mimo aktuálního bodu xi , F je vstupný parametr. Heuristika BEST využívá modifikace bodu xbest , nejlepšího bodu z populace P podle vztahu: u = xbest + F (r1 + r2 − r3 − r4 ) ,

(6)

kde r1 , r2 , r3 a r4 jsou vzájemně různé náhodně vybrané body z populace P různé od aktuálního bodu xi od bodu xbest s nejnižší funkční hodnotou v P . F > 0 je vstupní parametr. Nový vektor y vznikne „kříženímÿ vektoru u a náhodně vybraného vektoru x tak, že každá složka xi je přepsána hodnotou ui s pravděpodobností C. C ∈ h0, 1i je další vstupní parametr heuristiky.  yi =

ui pro U < C nebo i = j xi jinak

i = 1, 2, . . . , d ,

(7)

Kde U je náhodná veličina rovnoměrně rozdělená na intervalu h0, 1) a j je náhodně 17

vybraný index složky vektoru zabezpečující přepis alespoň jedné složky vektoru x při jakékoliv volbě hodnoty C. Agoritmus DE je vhodný pro použití především díky poměrně výpočetně nenáročnému generování bodu y i celkové jednoduchosti. Velkou pozornost musíme ale věnovat výběru vstupních hodnot F a C, na které je algoritmus velmi citlivý. Žádná z těchto heuristik nezaručuje, že vygenerovaný bod y bude ležet v D. Pokud nastane tento případ, je aplikována tzv. perturbace, která zrcadlově překlopí souřadnici yi 6∈ ha, bi.

3.6. Metoda simulovaného žíhání Doposud byly v této práci zmíněny pouze algoritmy, jejichž princip je založen na poznatcích z biologie. Metoda simulovaného žíhání (Simulated Annealing, ozn. SA) patří mezi stochastické optimalizační algoritmy, které mají základ ve fyzice. Počátkem 80. let přišli Kirkpatrick, Gelatt, Vecchi a Černý s myšlenkou, že problém hledání globálního minima funkce lze realizovat podobným způsobem jako žíhání tuhého tělesa. Tento princip nazvali metodou simulovaného žíhání. Metoda simulovaného žíhání je velmi dobře zpracovaná ve zdrojích [6], [7], [10], [12]. 3.6.1. Fyzikální interpretace žíhání tuhého tělesa Termín žíhání označuje ve fyzice proces, při kterém je těleso vyhřáté v peci na vysokou teplotu a postupným pomalým ochlazováním (= žíháním) se odstraňují vnitřní defekty tělesa. Vlivem vysoké teploty se částice dané látky v tělese náhodně uspořádají v prostoru (těleso je roztopené). Pravděpodobnost zániku defektů krystalické mřížky je při vysoké teplotě velmi velká. Pomalým ochlazováním potom docílíme také snižování pravděpodobnosti vzniku nových defektů. Při postupném ochlazování se částice ustalují do rovnovážné polohy, čímž celková energie tělesa a tím i defektovost klesá. Je-li proces ochlazování dostatečně pomalý, potom je za každé teploty T žíhané těleso v rovnovážném stavu. Tento stav popisuje Boltzmannovo rozdělení 18

pravděpodobnosti toho, že při teplotě T je těleso ve stavu i s energií Ei .

WT (Ei ) =

Ei 1 e kT , Q(T )

(8)

kde T je Boltzmannova konstanta a Q(T ) =

X

Ei

e kT ,

(9)

i

když i v sumě reprezentuje všechny stavy tělesa. S klesající teplotou T preferuje Boltzmannovo rozdělení stavy s nižší energií. V případě, že se teplota blíží k nule, má stav s minimální energií nenulovou pravděpodobnost. Existuje analogie tohoto přírodního procesu s procesem řešení optimalizačních problémů. 3.6.2. Metropolisův algoritmus Postup simulovaného žíhání je založen na simulování fyzikálních procesů probíhajících při odstraňování defektů krystalické mřížky. Je to zároveň také varianta horolezeckého algoritmu, v němž jsou heuristické kroky směrem k horšímu řešení řízeny s určitou pravděpodobností. V roce 1953 navrhl N. Metropolis se svými kolegy jednoduchý algoritmus založený na metodě Monte Carlo, která funguje na tomto principu: Nechť je daný aktuální stav systému, určený polohou částic tělesa. Potom jsou částice jemně posunuty a tím je způsobena malá náhodná symetrická porucha (tj. pravděpodobnost změny stavu A na stav B vlivem poruchy, musí být stejná jako změna stavu B na A). Poruchy jsou generovány dokud rozdíl energií aktuálního a porušeného stavu 4E není nezáporný. Potom je pravděpodobnost přijetí porušeného stavu do dalšího procesu určena vztahem  (−4E)  . Pr = min 1, e kT

(10)

Toto pravidlo přijetí porušeného stavu nazýváme Metropolisovým kritériem. Řídíme-li se tímto kritériem a aplikujeme-li jej na velký počet poruch, dostaneme systém tepelné rovnováhy. Tato forma metody Monte Carlo se nazývá Metropolisův algoritmus. Malá náhodná změna řešení (perturbation) potom odpovídá 19

kmitání částic při žíhání tuhého tělesa a ochlazování je postupné snižování pravděpodobnosti, se kterou v dalším kroku akceptujeme horší řešení. Účelem Metropolisova algoritmu je především zabránit uváznutí v lokálním extrému tím, že za určitých podmínek přijmeme za lepší řešení i to, které má mírně nižší fitness funkci než předcházející nejlepší řešení. 3.6.3. Simulované žíhání Simulované žíhání je variantou horolezeckého algoritmu, v němž kroky heuristiky směřují k horšímu řešení s určitou pravděpodobností. Je to sekvence Metropolisových algoritmů s postupným snižováním teploty, přičemž vycházíme vždy z výstupů předcházejícího běhu Metropolisova algoritmu. Na začátku optimalizačního procesu můžeme tento algoritmus přirovnat k stochastickému prohledávání stavového prostoru, ale v závěru průběhu je již spíše verzí horolezeckého algoritmu. Implementace Metropolisova algoritmu (viz [8]): procedura Metropolisuv algoritmus(input: xini , kmax , T ; output : xout ); begin k = 0; x = xini ; while k < kmax do begin k =k+1; x0 = Opertur (x); Pr = min(1, exp(−(f (x0 )–f (x))/T ); if náhodné číslo ¡ Pr then x = x0 end xout = x end V algoritmu xini označuje počáteční stav, kmax je maximální počet kroků, Opertur (x) reprezentuje malou změnu ze stavu x do stavu x0 . V algoritmu se použije Metropolisovo kritérium za teploty T a výstupem je poslední stav xout . 20

Algoritmus Simulovaného žíhání (obsahuje výše uvedený Metropolisův algoritmus) lze popsat takto: procedura Simulovane zihani(input : Tmin , Tmax , kmax , α; output : xopt ); begin xini = náhodně vygenerovaný vektor z D; T = Tmax ; while T > Tmin do begin Metropolisuv algoritmus (xini , xout , kmax , T ); xini = xout T = αT end xopt = xout end Algoritmus je zahájen vygenerováním počátečního stavu xini a maximální teplotou Tmax . Cyklus while se opakuje se snižující teplotou kmax krát. Výstupem je konečný „zamrzlýÿ stav xout . Parametr α volíme z intervalu 0 < α < 1 a jde o koeficient snižování teploty. Algoritmus je ukončen, pokud je teplota snížena na minimum a za této teploty již není žádný stav s vyšší funkční hodnotou, který bychom mohli akceptovat. Fyzikální systém okolní podmínky energie základní stav rychlost ochlazování teplota obezřetné žíhání

Optimalizační problém množina přípustných řešení hodnotící funkce optimalizační podmínka lokální vyhledávání kontrolní parametr simulované žíhání

Tab. 3.1: Tabulka ekvivalentů fyzikálního a optimalizačního pojetí (viz [8])

21

3.6.4. Simulované žíhání s elitizmem Za simulované žíhání s elitizmem považujeme pozměněnou variantu základního simulovaného žíhání s tím rozdílem, že za počáteční stav považujeme nejlepší řešení, které bylo zjištěno při předchozích průbězích za vyšší teploty. V původní verzi byl počátečním stavem výsledný stav předchozího Metropolisova algoritmu při stejné teplotě T . Nevýhody této varianty: • nedostatečně velká konstanta kmax , • pro diskrétní kroky teploty není Metropolisův algoritmus v tepelné rovnováze, protože vlivem změněné počáteční podmínky může pro nižší teploty nastat stav, kdy výsledné řešení Metropolisova algoritmu odpovídá lokálnímu minimu, které se liší od globálního minima. 3.6.5. Paralelní simulované žíhání Tato verze obecného simulovaného žíhání je vyjímečná svou úspěšností i při řešení složitých kombinatorických problémů, kdy by obecná verze neuspěla. Základní myšlenka spočívá v aplikaci simulovaného žíhání na množinu P stavů x, x0 , x00 , . . . , které jsou sladěny tak, že Metropolisovy algoritmy probíhají ve všech současně se stejnou teplotou. V práci se stavy zde používáme operaci křížení převzatou z genetických algoritmů. Nechť existují dva rodičovské stavy x = (x1 , x2 , . . . , xN ) a x0 = (x01 , x02 , . . . , x0N ) délky N . Jejich křížením potom získáme potomky definované takto:

z = (x1 , x2 , . . . , xr , x0r+1 , . . . x0N ) ,

(11)

z0 = (x01 , x02 , . . . , x0r , xr+1 , . . . xN ) ,

(12)

kde r je náhodně vybraný bod křížení, 1 < r < N . Zda jsou nové stavy akceptovány, řeší Metropolisův algoritmus aplikovaný zvlášť na páry (x, z) a (x0 , z0 ). Akceptujeme-li pomocí MA nový stav z, obnovíme množinu P nahrazením z za x. 22

Výsledkem je nejlepší řešení z množiny P , tj. množiny řešení vycházející z dokončeného simulovaného žíhání. Paralelní simulované žíhání znázorňuje následující obrázek. Na jednotlivé stavy znázorněné černými obdélníky jsou aplikované nezávislé Metropolisovy algoritmy se stejnou teplotou T . Interakce mezi stavy je znázorněna šipkami, probíhá s malou pravděpodobností 0 < Pcross << 1.

Obr. 3.2: Znázornění paralelního simulovaného žíhání.

3.7. Vlastní algoritmus RYPOŠ Při vytváření vlastního algoritmu jsme vycházeli z chování australského hlodavce rypoše žijícího v podzemních chodbách pod povrchem pouště. Rypoš patří mezi živočišné druhy tvořící kolonie se sociálním uspořádáním a hierarchií podobnou hmyzu. V kolonii se rozmnožuje jen jedna samice – královna, k páření má několik plodných samců a zbytek kolonie tvoří nerozmnožující se dělníci. Z toho vyplývá, že dělníci jsou více spřízněni s královnou, než sami se sebou, a jejich rozmnožování je nevýhodné. Naopak královna rodí efektivní potomstvo nesoucí veškeré v populaci se vyskytující geny. Tím se zároveň zvyšuje úspěšnost i četnost kolonie

Obr. 3.3: Rypoš lysý. 23

Princip fungování algoritmu RYPOŠ: • Nejprve náhodně vygenerujeme původní populaci o 10 jedincích (žlutá kolečka). • Poté vybíráme místa, kde mohou vzniknout hnízda (červený čtverec). První hnízdo je zvoleno v prvním generovaném bodě populace, jako další jsou zaznamenána jen ta hnízda, která mají lepší funkční hodnotu, než v historii nalezené hnízdo. • Ostatní žluté body se stávají dělníky, kteří se budou starat o shánění potravy pro kolonii. • Dále je náhodně vygenerována královna (modrá hvězdička). • Královna si vybírá „ženichaÿ (hnízdo, bílý čtverec) podle dvou hledisek: buď zvolí takové hnízdo, které je nejblíž (ženichovy feromony na ni působí nejvíce, je jejímu srdci nejblíž). Nebo zvolí hnízdo v bodě s nejnižší funkční hodnotou, protože tento ženich je pro ni nejlepší, je „nejbohatšíÿ. Je také středem pro generování další populace. • Královna má s ženichem 10 potomků (modrá kolečka), kteří jsou v našem případě generováni z normálního rozdělení kolem vybraného hnízda. Všechny potomky z jednoho vrhu posouváme o stejnou vzdálenost (disperzi) závislou na pořadí vrhu (číslu iterace). • V případě, že noví potomci leží mimo definiční obor (prohledávaný prostor), jsou pomocí funkce zrcad, která je vlastně středovou souměrností, překlopeny podle hnízda zpět do našeho definičního oboru. • Nyní máme k dispozici 20 jedinců, ale pro tak velkou kolonii by v okolí nebyl dostatek hlíz, a proto musí ti jedinci, kteří nejsou dost dobří (mají nejhorší funkční hodnotu) odejít. Královna již splnila svou funkci a také kolonii opouští. Máme tedy opět kolonii nejlepších 10 rypošů složenou z jedinců původní populace i z přeživších potomků (světle modrá kolečka). • Nyní se opět náhodně objeví (vygeneruje) královna a cyklus rození probíhá znovu dokola. Pro zachování integrity s ostatními algoritmy bylo generováno vždy v každé iteraci 10 bodů a náš cyklus byl ukončen po 20 vrzích. Jako 24

aproximace minima (řešení) je vyhodnocen jedinec s nejlepším hnízdem ze všech iterací. Pro ilustraci zde uvádíme grafické znázornění průběhu algoritmu RYPOŠ při testování Schwefelovy funkce. Z 20 iterací jsou na obr. 3.4 zobrazeny 1., 5., 10., 15. a 20. iterace. Oscilace mezi vybranými hnízdy je způsobena možností volby způsobu, kterým může královna vybrat hnízdo. Zabraňujeme tak uváznutí v lokálním extrému. Na obr. 3.5 je krabičkový diagram pro funkce Ackleyho, první De Jongovu, Griewangkovu, Rastrigovu a pro Rosenbrockovo sedlo vytvořený z funkčních hodnot získaných testováním algoritmu RYPOŠ. Schwefelova funkce byla z tohoto diagramu vynechána, protože naměřené odchylky od funkční hodnoty reálného minima byly příliš vysoké v porovnání s daty z testování ostatních funkcí. Na ose y by bylo příliš velké rozpětí mezi krajními hodnotami a diagram by byl nepřehledný. V porovnání s jinými algoritmy je ale Schwefelova funkce otestováná algoritmem RYPOŠ se srovnatelnými výsledky. Větší odchylky jsou dány složitostí funkce.

25

Schwefelova funkce

1. iterace algoritmu RYPOŠ

5. iterace algoritmu RYPOŠ

10. iterace algoritmu RYPOŠ

15. iterace algoritmu RYPOŠ

Schwefelova funkce: p PDim f (x) = i=1 −xi sin( |xi |) D = h−a, ai × · · · × h−a, ai, a = 500.12 minimum x = (420.97, . . . , 420.97), f (x) = −418.9829 ∗ d nalezená aproximace minima: (−259.9673, 427.2054), f (x) = −519.0165

20. iterace algoritmu RYPOŠ Obr. 3.4: Populace v několika iteracích u algoritmu RYPOŠ

1 2 3 4 5

Krabičkový diagram – Ackleyova funkce – DeJongova funkce – Griewangkova funkce – Rastringova funkce – Rosenbrockovo sedlo

Obr. 3.5: Výsledek testování algoritmu RYPOŠ

27

4. Aplikace heuristik V posledních letech se rozmohlo používání heuristik v různých oblastech vědy od psychologie, informatiky, matematiky až po ekonomii a jiné podobné vědy. V ekonomii se heuristiky používají zejména na zjišťování minimálních nákladů spojených s určitým výkonem. Časté je také jejich využití v logistických úlohách, kde se může jednat o zefektivnění umístění skladů, centrálních středisek nebo jiných základen tak, aby náklady na dopravu do odbytových míst byly co nejnižší. K výpočtu je třeba zjistit souřadnice odbytových míst a vektor vah, kterým jsou počty cest uskutečněných do odbytových cílů. Hledáme souřadnice (x, y) pro umístění skladu. Funkci, jejíž minimum budeme zjišťovat, získáme načítáním euklidovských vzdáleností bodů, ve kterých jsou umístěna odbytová místa, a imaginárního bodu pro umístění skladu (x, y) násobených příslušnou složkou z vektoru vah. Pro určení minima této funkce můžeme použít libovolný algoritmus (heuristiku). V oblasti behaviorální ekonomie se aplikují heuristiky na problém rozhodování nakupujících. V tradiční ekonomii je předpoklad plné informovanosti buď o ceně a umístění na trhu nebo o pravděpodobnosti rozdělení cen na trhu. V určitých případech, kdy nakupující vstupuje na specifický trh pouze velmi nepravidelně (trh zboží dlouhodobé spotřeby, nebo naopak trh práce),tyto předpoklady neplatí. V behaviorální ekonomii rozlišujeme tři heuristiky pro řešení tohoto problému popsané ve zdroji [11]: Přizpůsobivou heuristiku (prvotní ideu výše přijatelné ceny měnící se v závislosti na aktuálních cenách objevených během hledání řešení), Bargainovu heuristiku (ideu o výši přijatelné ceny založené na určitém rozptylu od odhadované průměrné ceny získané z cen objevených během hledání) a vývojovou heuristiku (myšlenku, že přijmeme takovou cenu, která je rovná předpovídané ceně nalezené v dalším kroku zvýšenou o hodnotu tohoto kroku). Heuristiky lze použít také například v teorii portfolia, kde je můžeme využít ke zjištění optimálního rozložení akcií v portfoliu. Výsledkem minimalizace je vektor vah odpovídající doporučené volbě akcií do portfolia.

28

5. Testování uvedených algoritmů – praktická část V programu Matlab 6.1 byly vygenerovány grafy testovacích funkcí uvedených v kapitole 2, spolu se zakreslenými body minima nalezenými slepým vyhledáváním (obr. 5.1), algoritmem simulovaného žíhání (obr. 5.2) a horolezeckým algoritmem (obr. 5.3). Vysvětlení značení a použité parametry: – Slepé vyhledávání: žlutá kolečka = body vyhodnocené v průběhu algoritmu jako lepší červené kolečko = algoritmem nalezené minimum (nejlepší bod) – Simulované žíhání: bílý čtvereček = náhodně vybraný počáteční bod žlutá kolečka = body vyhodnocené v průběhu algoritmu jako lepší fialový trojúhelník = algoritmem nalezené minimum (nejlepší bod) Parametry: Tmin = 0,0001, Tmax = 1000, α = 0,15, kmax = 200. (názvy proměnných korespondují se značením použitým v kapitole 3.6 a byly zvoleny náhodně) – Horolezecký algoritmus: žluté křížky = body vyhodnocené v průběhu algoritmu jako lepší červené kolečko = algoritmem nalezené minimum (nejlepší bod) U všech algoritmů byly nastaveny parametry tak, aby bylo ve všech iteracích vygenerováno 200 bodů. Např. algoritmus RYPOŠ byl testován pro 20 iterací, ve kterých bylo generováno po 10 bodech.

29

a) Ackleyho funkce

nalezené minimum x = (−3.0810, 1.4614), f (x) = 7.5449 c) Griewangkova funkce

nalezené minimum x = (7.2641, −42.2653), f (x) = 1.8233 e) Rosenbrockova funkce

nalezené minimum x = (0.4348, 0.1898), f (x) = 0.3195

b) první De Jongova funkce

nalezené minimum x = (−0.1214, 0.2311), f (x) = 0.0681 d) Rastrigova funkce

nalezené minimum x = (−1.0244, −1.0851), f (x) = 3.7386 f) Schwefelova funkce

nalezené minimum x = (−307.0660, 409.6987), f (x) = −701.0586

Obr. 5.1: Iterace a nalezená řešení ve slepém algoritmu

a) Ackleyho funkce

nalezené minimum x = (6.9286, −6.8498), f (x) = 13.0650 c) Griewangkova funkce

nalezené minimum x = (431.3778, −431.4111), f (x) = 93.7802 e) Rosenbrockova funkce

nalezené minimum x = (0.0009, −0.0038), f (x) = 0.9996

b) první De Jongova funkce

nalezené minimum x = (0.0376, −0.0745), f (x) = 0.0070 d) Rastrigova funkce

nalezené minimum x = (0.0205, 0.0013), f (x) = 0.0839 f) Schwefelova funkce

nalezené minimum x = (221.5650, −221.5663), f (x) = −0.0057

Obr. 5.2: Iterace a nalezená řešení v simulovaném žíhání

a) Ackleyho funkce

b) první De Jongova funkce

nalezené minimum x = (0.1013, 0.1114), f (x) = 2.0001

nalezené minimum x = (−0.1353, −0.0150), f (x) = 2.0015

c) Griewangkova funkce

nalezené minimum x = (1.1543, 3.0194), f (x) = 11.2813 e) Rosenbrockova funkce

nalezené minimum x = (0.1013, 0.1114), f (x) = 2.0001

d) Rastrigova funkce

nalezené minimum x = (0.0684, −0.0402), f (x) = 2.0026 f) Schwefelova funkce

nalezené minimum x = (0.1386, 0.2616), f (x) = 2.0230

Obr. 5.3: Iterace a nalezená řešení v horolezeckém algoritmu

Slepé vyhledávání, horolezecký algoritmus, simulované žíhání a algoritmus SOMA (varianta All-to-one) byly testovány 20 × na každou z šesti vybraných testovacích funkcí. Data jsou v tabulkách a jsou součástí přílohy. Pro porovnání úspěšnosti jsou z výsledných nalezených funkčních hodnot vytvořeny krabičkové diagramy (obr. 5.4) vyjadřující vhodnost aplikace algoritmu pro danou funkci. Krabičkové diagramy jsou řazeny vždy v pořadí: 1 — slepé vyhledávání (BS), 2 — simulované žíhání (SA), 3 — horolezecký algoritmus (HILL), 4 — algoritmus SOMA, 5 — algoritmus RYPOŠ. Nejprve připomeneme údaje, které jsou v krabičkovém diagramu znázorňovány.

Obr. 5.4: Krabičkový diagram

33

Výsledek testování — Ackleyho funkce Výsledek testování — první De Jongova funkce

Výsledek testování — Griewangkova funkce

Výsledek testování — Rastrigova funkce

Výsledek testování — Rosenbrockova funkce Výsledek testování — Schwefelova funkce

Obr. 5.5: Porovnání úspěšnosti algoritmů 34

Vyhodnocení: Podle vzhledu box diagramů můžeme určit, jaký algoritmus byl v našem testování pro každou funkci nejvhodnější. Můžeme sledovat např. jak daleko se nachází medián (určený ze získaných aproximací minima) od známé hodnoty globálního minima. Pokud bychom dle úspěšnosti při testování jednotlivých funkcí měli použité algoritmy ocenit prvním až třetím místem, výsledky by byly následující:

1. 2. 3.

Ackleyho SOMA HILL RYPOŠ

De Jongova SOMA + SA RYPOŠ + BS

Funkce Griewangkova Rastrigova SOMA SA RYPOŠ SOMA BS RYPOŠ

Rosenbrockova BS SOMA SA

Schwefelova SOMA BS + RYPOŠ

Tab. 5.1: Vyhodnocení úspěšnosti algoritmů Z tabulky vyplývá, že z testovaných pěti algoritmů řeší otázku optimalizace nejlépe algoritmus SOMA. Je velmi potěšující, že algoritmus RYPOŠ je spolu je simulovaným žíháním hned na druhém místě. Lze se domnívat, že jeho úspěšnost půjde ještě zvýšit vhodnou volbou parametrů tak, aby byla v průběhu algoritmu volena vhodnější posloupnost bodů s co nejvyšší pravděpodobností konvergující k hledanému minimu. Toto optimální nastavení je u většiny uváděných algoritmů známo nebo odzkoušeno a může to být i důvod jejich větší úspěšnosti. Důležité je, že navržený algoritmus RYPOŠ obstál v konkurenci běžných algoritmů a dokonce nikdy neskončil na posledním (pátém) místě. U Schwefelovy funkce dosvědčil, že dobře řeší i optimalizační úlohu u multimodálních funkcí, aniž by uvízl v lokálním minimu.

35

6. Závěr V bakalářské práci jsme vysvětlili princip fungování jednotlivých stochastických algoritmů. Uvedli jsme také výhody a nevýhody jejich použití a typy úloh, kdy je jejich aplikace nejvhodnější. Dále jsme detailně popsali algoritmus simulovaného žíhání, který je jediný založen na fyzikální analogii. Dále jsme se věnovali testování algoritmů. V programu Matlab 6.1 byly pomocí m-souborů vytvořeny předpisy šesti testovacích funkcí. Pro algoritmus slepého vyhledávání, simulovaného žíhání, horolezeckého algoritmu a algoritmus SOMA jsme vždy dvacetkrát hledali aproximaci globálního minima (při stejném počtu generovaných bodů). Výsledky jsou uvedeny v tabulkách v příloze a byly použity pro vytvoření krabičkových diagramů pro jednotlivé funkce. Účelem bylo zjistit, který z algoritmů pro hledání aproximace globálního minima byl nejvhodnější. Odchylky výsledků od známé hodnoty minima jsou způsobeny především multimodálností funkce a tendencí algoritmů uváznout v lokálním minimu, na což je nejvíce náchylný horolezecký algoritmus, který v průběhu 200 iterací nedosahoval u složitějších funkcí uspokojivých výsledků. Výsledky algoritmu simulovaného žíhání mohou být trochu zklamáním. Zde ale může být problém v nastavení počátečních parametrů, především parametru α, který mění rychlost změny teploty. Úprava parametrů by mohla výsledky zlepšit. Jako nejúspěšnější je možné vyhodnotit algoritmus SOMA, kde byla testována verze All-to-one. Velkou pozornost ale mohou vzbudit i výsledky dosažené novým algoritmem RYPOŠ. Ten je založen na myšlence evolučních algoritmů a jeho průběh je popsán ve třetí kapitole. Hlavním cílem bylo dosahovat uspokojivých výsledků a omezit možnost uváznutí v lokálním minimu, což zabezpečují dvě možnosti volby hnízda. Algoritmus RYPOŠ je podle získaných výsledků srovnatelný s ostatními zde testovaným algoritmy. Výborně řeší optimalizační otázku například i u Schwefelovy funkce, která svým předpisem patří k nejnáročnějším testovacím funkcím. Během zpracování bakalářské práce jsem vylepšila své znalosti programování 36

a prostudovala jsem zajímavou oblast optimalizačních metod. Při zpracování této práce jsem si uvědomila, že i v matematice je prostor pro experimentování. Doufám, že se budu moci tomuto tématu věnovat v rámci diplomové práce na navazujícím studiu. Také doufám, že se mi vhodnou volbou parametrů podaří docílit zpřesnění výsledků a algoritmus RYPOŠ se stane úspěšnějším než ostatní testované a dnes používané algoritmy.

37

Literatura [1] Tvrdík, J.: Porovnání heuristik v algoritmech globální optimalizace. sborník konference Robust, JČMF, 2002, str. 321–332. [2] Míka, S.: Matematická optimalizace. Západočeská univerzita, Plzeň, 1997. [3] Blažek, J., Habibbala, H., Pavliska, V., Vybrané heuristiky pro globální optimalizaci a jejich implementace v Matlabu. http://www.volny.cz/habiballa/publ/matlab05.pdf [citováno 8. 4. 2008]. [4] Zelinka, I., Algoritmus SOMA, http://www.ft.utb.cz/people/zelinka/soma/ [citováno 8. 4. 2008].

testovací

funkce.

[5] Obitk, M., Genetické algoritmy: Matrice života v počítačích, 2001, http://www.scienceworld.cz/sw.nsf/ID/9B80774399F1B837C1256E9700489AEC?OpenDocument&cast=1 [citováno 8. 4. 2008]. [6] Babjak, J., Optimalizačné algoritmy, 2003, http://www.scienceworld.cz/sw.nsf/ID/36E02F629C5BD4D3C1256E970048C6ED?OpenDocument&cast=1 [citováno 8. 4. 2008]. [7] Kvasnička, V., Evolučné algoritmy, http://math.chtf.stuba.sk/evol/prednaskaSTU.htm [citováno 8. 4. 2008].

2003,

[8] Michalewicz, Z., Fogel D. B.: How to solve it: Modern Heuritics. Second, revised and extended edition, Springer-Verlag Berlin Heidelberg, 2004. [9] Babjak, J., Algoritmus SOMA – najlepšie, čo doma máme, 2003, http://scienceworld.cz/sw.nsf/ID/DF1541FD80584131C1256E970048FA7C?OpenDocument&cast=1 [citováno 8. 4. 2008]. [10] Kalátová, E., Dobiáš, J., Evoluční algoritmy, 2000, http://www.kiv.zcu.cz/studies/predmety/uir/gen alg2/E alg.htm [citováno 8. 4. 2008]. [11] Skořepa, M., Tři heuristiky pro hledání nízké ceny na málo známém trhu, 2007, http://www.ekonomie-management.cz/c.php?a=542 [citováno 8. 4. 2008].

38

[12] Majer, P., disertační práce Moderní vrhování výroby, kapitola 3: Metody majer.czweb.org/scheduling/30Metody reseni.doc [citováno 8. 4. 2008].

39

metody řešení,

roz2004.

Přílohy Na následujících stranách jsou uvedeny výsledky z testování stochastických algoritmů pro hledání aproximace globálního minima. Údaje z přílohy sloužily pro konstrukci krabičkových diagramů. Součástí přílohy je i vložené CD obsahující vytvořené m–soubory použitých testovacích funkcí a spouštěcí programy pro jednotlivé algoritmy. Všechny algoritmy jsou původní s výjimkou algoritmu SOMA, jehož varianta All-to-one byla převzata z internetové stránky Ivana Zelinky uvedené ve zdroji číslo [4].

40

Výsledky testování slepým algoritmem Algoritm us Slepý alg.

Test.fce Ackleyho

Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= 0.3632 -3.0810 -0,8161 -1,3948 1,0005 -0,7111 -4,2049 0,4616 -1,9607 0,9266 -2,1708 0,8200 0,8226 0,8905 -0,2578 -0,4341 0,6671 1,1031 0,5128 0,0951

y= -2.1133 1,4614 -0,2364 -1,8736 0,1619 1,3539 0,9601 -1,9264 1,1104 0,9266 -0,6330 -0,7244 0,1777 -2,6199 -0,5345 -1,0538 0,3647 1,5053 2,5243 -0,7133

F(x,y) 5,4260 7,5449 0,2364 5,9277 2,5013 4,9004 7,8581 5,3497 4,3678 3,7555 5,8581 3,6490 2,7803 6,5311 3,2717 3,8584 3,6220 5,2192 6,8893 2,7583

Test.fce De Jongova

Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= -0.1550 0.0620 -0.5258 -0.1393 -0.1214 -0.3900 0.0788 -0.3346 0.1581 -0.3705 0.1400 0.1404 0.1520 -0.0440 -0.0741 0.1138 0.1883 0.0875 0.0162 -0.1550

y= -0.1637 -0.3607 0.2494 -0.0403 0.2311 0.5771 -0.3288 0.1895 0.1039 -0.1080 -0.1236 0.0303 -0.4471 -0.0912 -0.1798 0.0622 0.2569 0.4308 -0.1217 -0.1637

F(x,y) 0.0508 0.1339 0.3387 0.0210 0.0681 0.4852 0.1143 0.1479 0.0358 0.1489 0.0349 0.0206 0.2230 0.0103 0.0378 0.0168 0.1014 0.1933 0.0151 0.0508

Test.fce Pokus x= Griew angkova 1 -3,7423 2 79,7761 3 -24,8245 4 14,1683 5 10,6785 6 6,5595 7 21,3780 8 52,9471 9 -18,3206 10 11,1787 11 37,2206 12 -13,0949 13 -68,5660 14 -54,0189 15 -33,3367 16 -6,7061 17 -26,8076 18 -79,4188 19 -5,6609 20 52,6668

y= -45,7564 -31,9346 -13,2400 -24,1885 40,9420 41,5458 -6,1144 -30,7798 -41,0559 -18,6318 25,4366 11,7197 -12,2039 20,6573 -57,2827 41,3274 -18,8394 -36,5616 28,0070 -7,0743

F(x,y) 1,0058 2,5287 0,2985 1,2241 1,4318 1,7745 0,3087 1,0866 1,5980 1,2991 0,6307 0,2899 1,3735 1,3298 1,7782 1,6579 1,1645 3,4485 1,0958 1,0247

Test.fce Rastrigova

Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= -0.1107 0.9745 -1.0336 -0.0974 -0,0440 -0.1063 1,0430 1,1506 -0,9810 -0,0122 1,0503 1,9774 0,9627 -1,0486 -0,0835 0,9576 -0,0758 -1,0163 0,9918 -1,9092

y= 1,0445 1,0588 0,9241 -0,0069 -1,0714 0,8666 0,0188 -0,0394 0,0594 -0,8850 1,0950 1,1642 -1,0488 0,1171 1,0804 -2,0139 0,9222 -1,9378 1,0115 0,0006

F(x,y) 3,8143 2,8735 3,2605 1,8330 3,1375 6,2225 1,5210 5,7811 1,7263 3,3123 4,5256 10,2320 2,7670 4,1622 3,7660 5,3638 3,1402 5,5933 2,0461 5,2304

y= 0,7520 1,6170 1,3191 1,0311 1,1434 1,3936 0,1497 0,6935 1,0082 1,0053 1,5068 0,4769 0,5428 1,5733 0,0065 0,9809 0,6677 1,0565 0,2713 0,8658

F(x,y) 0,0232 0,2253 0,0221 0,3310 0,0159 0,2475 0,4080 0,1220 0,0130 0,0394 0,3400 0,1053 0,1736 0,3577 0,8685 0,0052 0,4722 0,0396 0,2562 0,0591

y= 415,7447 432,9852 409,0796 -317,9510 436,6416 409,8560 418,8454 -293,8434 -289,7799 405,9069 433,8188 446,6866 416,3645 436,4530 423,3167 393,2750 424,1833 433,0504 420,6944 428,6373

F(x,y) -611,8482 -811,8952 -795,5805 -601,7888 -806,4378 -726,7498 -697,0232 -701,1028 -621,3824 -687,4890 -595,1604 -677,1049 -710,3762 -800,3950 -810,9720 -738,8665 -628,8470 -757,2156 -786,3565 -653,3546

Test.fce Pokus Rosenbrockova 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= 0,8719 1,2864 1,1487 0,9867 1,0741 1,1997 0,4201 0,8515 1,0097 0,9927 1,2051 0,6849 0,7595 1,2321 0,0683 0,9868 0,7763 1,0373 0,5090 0,9181

41

Test.fce Pokus x= Schw efelova 1 197,1848 2 428,8802 3 406,8517 4 393,9384 5 418,5725 6 392,6841 7 -289,2336 8 412,5063 9 446,0922 10 452,6938 11 197,5867 12 395,3475 13 -295,3429 14 428,6768 15 435,4402 16 413,4558 17 463,0054 18 443,3844 19 400,4458 20 -324,2924

Výsledky testování simulovaným žíháním Algoritm us SA

Test.fce Ackleyho

Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= -3.2637 0.6001 -3.7645 6,6910 -0.2120 -1.1291 -0.0058 -4.6094 -0.7259 -5.3616 -0.2755 1,5646 4,9506 -0.0159 0.1811 0.7131 -0.1124 2,5151 -0.0801 -8.2188

y= 3,2276 -0,6392 3,7859 -6,6644 0,2224 1,1424 -0,0054 4,5979 0,7061 5,3898 0,2804 -1,5686 -4,9512 0,0260 -0,1927 -0,6962 0,1489 -2.5028 0,1165 8,1808

F(x,y) 9,0526 3,9128 9,8214 14,2941 2,0965 3,7567 0,0175 11,8367 3,8353 12,8744 2,6495 6,2917 10,1953 0,0856 1,7694 3,8602 1,1199 8,3236 0,7515 15,0857

Test.fce Pokus De Jongova 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= 0.0124 -0.0071 0.0088 -0.0343 0.0016 0.0111 0.0181 0.0129 -0.0101 -0.0081 -0.0040 -0.0065 0.0210 -0.0358 -0.0300 -0.0298 0.0236 -0.0247 0.0134 -0.0343

y= -0.0109 -0.0369 -0.0118 0.0022 0.0116 -0.0306 -0.0024 0.0142 -0.0048 -0.0046 -0.0316 -0.0127 0.0294 0.0488 -0.0326 0.0008 0.0145 -0.0293 -0.0320 -0.0034

F(x,y) 2.7104e-004 0.0014 2.1698e-004 0.0012 1.3773e-004 0.0011 3.3451e-004 3.6833e-004 1.2448e-004 8.6313e-005 0.0010 2.0376e-004 0.0013 0.0037 0.0020 8.8847e-004 7.6410e-004 0.0015 0.0012 0.0012

Test.fce Pokus Griew angkova 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= 47.3386 -252.1487 -131.8425 82.8454 -555.6741 -210.0293 44.3566 -173.1653 225.9850 -85.9278 374.0921 -147.1246 265.2248 -484.5962 290.9547 -217.1092 113.5963 31.8917 -250.7576 -16.8098

y= -47,3343 252,1508 131,8713 -82,8591 555,6241 210,0112 -44,3415 173,1419 -225,9586 85,9567 -374,1680 147,0671 -265,2032 484,6291 -290,8896 217,0604 -113,5978 -31,8654 250,7669 16,7525

F(x,y) 2,2230 32,1654 10,6870 4,7613 155,5740 22,8429 2,8992 16,1549 25,5603 4,9343 71,1406 11,5687 35,9808 119,0691 43,5265 24,4264 6,6014 2,3747 31,6317 0,9154

Test.fce Rastrigova

x= 0.0456 0.0094 0.0531 0.0389 0.0158 0.0189 -0.0123 0.0767 -0.0125 0.0061 0.0097 -0.0063 -0.0390 -0.0383 -0.0250 0.0293 -0.0117 0.0270 -0.0281 -0.0048

y= -0.0416 0.0309 -0.0701 0.0325 0.0154 0.0026 -0.0213 -0.0785 0.0094 0.0054 0.0503 0.0371 -0.0321 -0.0132 -0.0056 -0.0228 0.0128 -0.0210 -0.0130 0.0022

F(x,y) 0.7502 0.2062 1,5146 0.5087 0.0965 0.0720 0.1202 2,3423 0.0485 0.0130 0.5160 0.2797 0.5041 0.3249 0.1302 0.2727 0.0594 0.2311 0.1896 0.0056

Test.fce Pokus Rosenbrockova 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= 0.0174 -0.0178 -0.0246 -0.0028 -0.0198 0.0115 0.0012 0.0304 0.0009 0.0017 -0.0083 -0.0011 0.0013 -0.0029 -0.0060 0.0099 0.0081 -0.0025 -0.0213 0.0188

y= 0,0155 -0,0078 -0,0290 -0,0050 -0,0059 0,0119 0,0021 0,0031 -0,0038 -0,0035 -0,0096 -0,0021 0,0017 0,0050 -0,0043 0,0150 0,0097 0,0047 0,0041 0,0136

F(x,y) 0,9887 1,0424 1,1372 1,0081 1,0439 0,9910 0,9981 0,9405 0,9996 0,9979 1,0259 1,0026 0,9977 1,0083 1,0140 1,0024 0,9932 1,0071 1,0444 0,9803

y= -368.1140 -48.2152 136.6801 -54.2918 -96.3549 -155.2560 93.6017 -350.5672 -223.3520 -36.4834 -321.7717 -127.5922 -59.7703 99.1890 61.7169 -359.5858 115.6748 -284.6315 -206.6935 94.6741

F(x,y) 0.3253 0.0733 0.0972 -0.0886 0.1095 -0.0168 -0.0952 0.4879 -0.0908 -0.1205 -0.1361 -0.0177 0.0340 -0.0850 0.0045 0.0787 0.0342 0.1720 -0.0088 0.0185

42

Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Test.fce Pokus x= Schw efelova 1 368.0793 2 48.1934 3 -136.7127 4 54.3259 5 96.3772 6 155.2588 7 -93.6210 8 350.5139 9 223.3327 10 36.5281 11 321.8006 12 127.6169 13 59.7471 14 -99.2067 15 -61.7214 16 359.5775 17 -115.6596 18 284.6719 19 206.6814 20 -94.6703

Výsledky testování horolezeckým algoritmem Algoritm us HILL

Tes t.fce Ackleyho

Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= 0.1013 0.1013 0.0684 0.1130 -0.1353 0.1141 1,1543 0,1181 -0,1373 4,3547 -0,8973 -0,1211 0,1317 -0,1111 -0,1128 -0,0781 -0,1473 -0,1490 -0,1401 0,0622

y= F(x,y) 0.1114 2,0001 0,1114 2,0001 -0,0402 2,0026 2,8210 8,8822 -0,0150 2,0015 0,1470 2,0024 3,0194 11,2813 2,5821 7,6882 -0,1429 2,0207 4,2690 37,4834 4,0365 17,5238 0,1287 2,0013 -0,0014 2,0010 0,1277 2,0009 1,2379 3,0900 -0,0119 2,0006 2,6679 8,1120 0,3181 2,0362 -0,0135 2,0018 0,4515 2,0671

Tes t.fce Pokus x= Griew angkova 1 1,1543 2 0,1141 3 1,1543 4 0,1181 5 -0,1373 6 4,3547 7 -0,8973 8 -0,1211 9 0,1317 10 -0,1111 11 -0,1128 12 -0,0781 13 -0,1473 14 -0,1490 15 -0,1401 16 0,0622 17 -0,0735 18 0,0812 19 0,0128 20 0,1180

y= 3,0194 0,1470 3,0194 2,5821 -0,1429 4,2690 4,0365 0,1287 -0,0014 0,1277 1,2379 -0,0119 2,6679 0,3181 -0,0135 0,4515 1,9214 -0,0036 -0,0052 0,2281

F(x,y) 11,2813 2,0024 11,2813 7,6882 2,0207 37,4834 17,5238 2,0013 2,0010 2,0009 3,0900 2,0006 8,1120 2,0362 2,0018 2,0671 4,9685 2,0004 2,0076 2,0147

Tes t.fce Pokus x= Rosenbrockova 1 0,1013 2 0,1013 3 0,0684 4 0,1130 5 -0,1353 6 0,1141 7 1,1543 8 0,1181 9 -0,1373 10 4,3547 11 -0,8973 12 -0,1211 13 0,1317 14 -0,1111 15 -0,1128 16 -0,0781 17 -0,1473 18 -0,1490 19 -0,1401 20 0,0622

y= F(x,y) 0,1114 2,0001 0,1114 2,0001 -0,0402 2,0026 2,8210 8,8822 -0,0150 2,0015 0,1470 2,0024 3,0194 11,2813 2,5821 7,6882 -0,1429 2,0207 4,2690 37,4834 4,0365 17,5238 0,1287 2,0013 -0,0014 2,0010 0,1277 2,0009 1,2379 3,0900 -0,0119 2,0006 2,6679 8,1120 0,3181 2,0362 -0,0135 2,0018 0,4515 2,0671

43

Test.fce Pokus x= De Jongova 1 -0.1353 2 -0,0735 3 0,0812 4 0,0128 5 0,1180 6 0,0947 7 -0,0538 8 -0,0657 9 -0,0724 10 -0,0913 11 -1,2163 12 0,1366 13 -0,0345 14 0,1163 15 0,0797 16 -0,0803 17 -0,0881 18 0,1013 19 0,0684 20 0,1130

Tes t.fce Rastrigova

y= -0.0150 1,9214 -0,0036 -0,0052 0,2281 -0,1111 -0,0035 2,0222 0,6167 2,1790 3,7001 1,1356 4,0977 1,6491 1,8023 -0,0027 0,5408 0,1114 -0,0402 2,8210

F(x,y) 2,0015 4,9685 2,0004 2,0076 2,0147 2,0091 2,0021 5,3248 2,1789 5,9247 15,7301 2,8940 17,1932 4,1134 4,5736 2,0004 2,1239 2,0001 2,0026 8,8822

Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= 0.1130 0,0947 -0,0538 -0,0657 -0,0724 -0,0913 -1,2163 0,1366 -0,0345 0,1163 0,0797 -0,0803 -0,0881 0,0711 0,0850 -1,2959 0,0657 0,1457 0,1482 0,2259

y= 2,8210 -0,1111 -0,0035 2,0222 0,6167 2,1790 3,7001 1,1356 4,0977 1,6491 1,8023 -0,0027 0,5408 -0,1071 0,8807 2,1274 0,0488 1,4131 0,2684 3,9014

F(x,y) 8,8822 2,0091 2,0021 5,3248 2,1789 5,9247 15,7301 2,8940 17,1932 4,1134 4,5736 2,0004 2,1239 2,0051 2,4706 7,3941 2,0036 3,4928 2,0266 15,7516

Tes t.fce Pokus Schw efelova 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= 0,1386 -0,0704 -0,0855 0,0574 -0,1348 0,0390 -0,1128 -0,0559 -0,0522 0,1279 0,0551 -0,0709 0,7981 0,2982 -0,0093 0,1333 -0,0890 0,1421 0,1287 -0,1463

y= 0,2616 0,2975 0,0233 2,5731 0,1176 -0,0086 1,8144 0,0922 0,2833 0,1350 0,0395 -0,0405 2,7037 1,5053 -0,0018 2,0085 0,2783 0,0918 0,0027 0,0500

F(x,y) 2,0230 2,0145 2,0008 7,6347 2,0015 2,0038 4,6191 2,0020 2,0097 2,0020 2,0036 2,0025 8,9052 3,7927 2,0082 5,2883 2,0141 2,0018 2,0008 2,0046

Výsledky testování algoritmem SOMA Algoritmus SOMA

Test.fce Ackleyho

Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= y= F(x,y) -0.0790 0.0043 0.7108 -0.0150 0.0058 0.0595 -0.0367 -0.1129 1.2662 -0.0730 0.0050 0.6322 0.0033 -0.0245 0.1136 -0.0689 0.0149 0.5984 -0.0847 0.0879 1.3660 0.0364 -0.0198 0.2580 -0.0498 0.0514 0.6254 -0.0168 -0.0044 0.0667 -0.0151 -0.0446 0.3165 -0.0223 0.0246 0.1813 0.5022 0.0253 1.0485 -0.5266 -0.4975 1.4722 -0.4602 -0.0975 1.8001 -0.0103 0.0295 0.1640 -0.0145 -9.7898e-005 0.0514 -0.0048 0.0348 0.1970 -0.0084 -0.0153 0.0675 0.0506 -0.5158 1.2869

Test.fce Pokus De Jongova 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Test.fce Pokus x= Griew angkova 1 -6.5511 2 -23.0414 3 -21.8517 4 3.1405 5 -6.1632 6 50.2776 7 0.2780 8 -22.2375 9 6.3713 10 3.0388 11 31.9493 12 12.3793 13 -15.6631 14 -3.3314 15 -13.0215 16 3.1648 17 -15.8905 18 21.7990 19 -3.4296 20 0.1340

y= -24.6629 -6.1180 -19.2557 -18.1043 0.0731 0.0825 12.7649 -6.2979 12.1589 19.0598 -12.7167 12.1712 6.8389 6.3850 25.0113 6.2103 -6.6190 -6.6623 -6.0684 0.4159

F(x,y) 0.2249 0.6465 0.2421 0.1530 0.0173 0.6329 0.0839 0.1638 0.0716 0.1039 0.4370 0.1119 0.1124 0.0322 0.3022 0.0131 0.1045 0.1659 0.0588 0.0304

Test.fce Rastrigova

Test.fce Pokus x= Rosenbrockova 1 0.4074 2 0.6150 3 0.6803 4 0.5483 5 1.0193 6 0.4339 7 1.2162 8 1.1464 9 0.9024 10 1.1785 11 1.2575 12 1.4236 13 0.6037 14 0.3092 15 0.1810 16 0.2820 17 0.4533 18 0.4064 19 1.3228 20 0.8739

y= 0.1716 0.3713 0.4683 0.2984 1.0047 0.1783 1.5038 1.3323 0.8058 1.5615 1.6006 2.0390 0.3615 0.0881 0.0279 0.0794 0.1946 0.1718 1.7528 0.7098

F(x,y) 0.3543 0.1531 0.1052 0.2045 0.1182 0.3303 0.1079 0.0543 0.0169 3.0075 0.1032 0.1950 0.1579 0.4829 0.6732 0.5155 0.3107 0.3568 0.1051 0.3058

Test.fce Pokus Schw efelova 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

44

x= 0.0020 0.0060 4.9345e-004 8.0681e-004 0.0014 -0.0067 0.0265 0.0134 0.0083 -0.0022 0.0036 9.5584e-004 -0.0047 -0.0038 4.9382e-004 0.0100 2.0147e-004 -0.0068 0.0050 0.0075

y= 0.0040 -3.3663e-004 0.0028 0.0098 -0.0018 -0.0041 -0.0013 0.0258 0.0020 -9.3209e-004 0.0020 0.0094 0.0083 0.0105 -0.0012 -9.3673e-004 0.0169 -0.0210 -0.0262 2.8046e-004

Pokus x= y= 1 0.0059 0.0016 2 0.0501 -0.0464 3 1.0039 -0.0261 4 -5.9226e-004 -0.0079 5 -0.0311 0.0015 6 -0.0015 -0.9973 7 0.9984 0.0020 8 1.0018 -0.0036 9 -1.0015 0.9954 10 -0.0395 0.0419 11 1.0007 0.9991 12 -0.0564 0.0016 13 -0.9977 0.0474 14 -0.0153 -0.9887 15 -1.0129 1.0017 16 0.0017 0.0136 17 -0.9983 -9.4154e-004 18 -0.9949 0.9940 19 0.0063 -1.0218 20 -0.0042 -0.0068

x= 418.5153 -302.3783 420.7291 422.0177 -302.4253 -302.4856 421.7856 417.3355 426.5122 423.0127 -301.6791 -302.7995 -302.2038 420.5714 421.1018 -124.7712 419.4744 203.8152 -302.4753 412.7645

y= 421.2353 420.4383 418.7633 421.3186 420.9839 203.9255 419.3220 423.0606 423.6840 420.3605 422.3039 421.4159 -302.1428 -302.8827 419.0537 420.2985 419.5274 421.1641 -302.6247 416.9433

F(x,y) 1.9794e-005 3.6318e-005 8.2915e-006 9.6494e-005 5.3831e-006 6.1579e-005 7.0142e-004 8.4671e-004 7.3491e-005 5.8025e-006 1.6843e-005 8.9740e-005 9.0973e-005 1.2585e-004 1.7231e-006 1.0161e-004 2.8617e-004 4.8779e-004 7.0931e-004 5.6424e-005

F(x,y) 0.0075 0.9175 1.1461 0.0125 0.1914 0.9965 0.9982 1.0069 1.9985 0.6546 1.9998 0.6252 1.4386 1.0492 2.0631 0.0375 0.9974 1.9901 1.1456 0.0125

F(x,y) -837.1982 -719.4892 -837.3455 -837.8114 -719.5262 -502.3860 -837.5396 -835.7510 -833.1549 -837.3916 -719.2118 -719.4927 -601.0576 -719.4913 -837.5012 -541.8020 -837.4222 -620.8213 -601.0875 -827.4882

Výsledky testování algoritmem RYPOŠ Algoritm us RYPOŠ

Test.fce Ackleyho

Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= -0.0676 -1.2042 1.1129 -0.6465 0.4716 -0.7007 0.4188 -0.5969 -1.0537 -1.0834 0.0245 1.0980 0.2695 -5.4584 -1.0371 -1.0606 0.2531 -1.8516 -1.5438 1.1073

y= -0.1232 -0.5268 -0.1899 -0.1675 -5.0117 -0.4386 0.1908 1.0255 0.9869 -0.0484 -0.0738 1.1751 0.7089 2.4885 0.5104 -0.0155 0.0317 1.1784 -0.9644 -2.2581

F(x,y) 1.5900 4.1278 4.1039 3.3319 8.0087 3.3529 2.7188 3.0453 2.9871 2.8383 0.6992 4.8092 3.7805 9.2117 2.3353 2.3861 2.2601 6.0255 3.6434 6.4866

Test.fce Griew angkova

Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= -3.2240 0.2506 50.5920 16.4528 -6.4650 41.0867 -27.6101 6.4480 -43.6597 -10.8949 59.2657 28.0650 -32.1347 -15.4929 -31.7194 -41.1486 -10.2057 26.7029 3.5990 -21.7135

y= 18.9259 -49.0140 13.5167 -22.7491 -38.6950 18.7205 -67.9701 12.0711 24.3367 25.7739 -20.4585 -55.2417 -14.3881 -9.3988 24.5392 15.9427 -8.4362 3.7396 7.5804 5.0642

F(x,y) 0.0963 0.8154 0.8433 1.4691 0.5207 0.5418 1.6837 0.0905 0.7503 1.2911 1.3508 1.1832 0.8485 1.0694 0.4895 1.3753 0.7069 1.1819 0.3026 0.3357

Test.fce Rastrigova

Test.fce Pokus Rosenbrockova 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= 0.6036 1.2458 1.2081 1.1008 1.2056 1.0291 0.9026 -1.0738 0.3138 0.2421 0.2553 0.8718 0.5353 0.4226 0.5205 0.0936 0.5525 0.3523 1.2061 0.6548

y= 0.4329 1.5639 1.4599 1.1971 1.4640 1.0617 0.7933 1.1610 0.1620 0.0117 -0.0048 0.7584 0.2771 0.1810 0.2635 -0.0260 0.2964 0.1112 1.4692 0.4064

F(x,y) 0.6264 0.0744 0.0433 0.0318 0.0534 0.0015 0.0555 4.3071 0.8743 0.7945 1.0441 0.0167 0.2247 0.3339 0.2354 0.9426 0.2082 0.4363 0.0638 0.1692

Test.fce Pokus x= Schw efelova 1 417.3389 2 409.1394 3 471.2053 4 419.6183 5 418.8881 6 421.1226 7 421.2626 8 412.1524 9 -304.9758 10 396.5879 11 406.9669 12 414.6422 13 430.7741 14 -302.0026 15 393.9911 16 427.8983 17 415.1025 18 423.4145 19 378.0267 20 447.3656

45

Test.fce Pokus De Jongova 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Pokus 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x= 0.7191 -0.4114 0.0447 -0.3106 -0.1192 -0.0048 0.0719 0.0663 0.0302 -0.0415 -0.0194 0.0294 -0.5348 0.0605 -0.0791 -0.3558 -0.0820 -0.3225 0.2250 0.0809

y= -0.1679 0.2967 0.0826 -0.0351 -0.0148 0.0223 0.1771 -0.0804 0.1710 0.2397 -0.0315 -0.0272 -0.1963 -0.0393 0.0212 -0.5314 -0.0065 0.2773 0.0697 0.0000

F(x,y) 0.5452 0.2573 0.0088 0.0977 0.0144 0.0005 0.0365 0.0108 0.0302 0.0592 0.0014 0.0016 0.3245 0.0052 0.0067 0.4089 0.0068 0.1809 0.0555 0.0065

x= 0.0823 -0.0276 -0.0685 0.0504 0.0099 0.9871 -0.0123 -0.9870 -0.9217 0.0588 -2.0307 0.9818 -0.0049 1.1021 -1.0135 -0.0189 1.0255 -0.0791 -0.0063 -0.9540

y= -0.0176 -1.9727 -1.0986 -0.9228 0.0869 1.0041 0.8930 0.0306 0.0400 1.9721 -0.9541 -0.0237 -1.0467 0.9793 -1.0348 0.0358 -0.0035 1.0663 0.0063 0.0212

F(x,y) 1.3749 4.1885 3.9793 2.5034 1.4806 2.0185 3.0025 1.1921 2.3510 4.7207 5.6329 1.1406 1.5274 4.2455 2.3731 0.3243 1.1820 3.2072 0.0155 1.4137

y= 390.4546 400.3675 422.7926 210.3426 418.1415 205.2129 395.8770 -300.7889 409.5440 418.2096 -285.4510 -295.4946 417.9132 -306.4291 423.4800 -303.6812 408.8230 380.0770 420.2640 394.5897

F(x,y) -725.6775 -768.5295 -550.5419 -615.1619 -836.4129 -620.5736 -761.7928 -709.4099 -702.4769 -764.9462 -659.3420 -708.2852 -824.6703 -599.1223 -749.6450 -713.2973 -815.2518 -647.0351 -630.2913 -668.3058