Biologicky inspirované výpočty: evoluční algoritmy

Biologicky inspirované výpočty: evoluční algoritmy Testovací funkce

prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Po této prezentaci by jste měli

znát vybrané testovací funkce, které jsou používány pro otestování robustnosti evolučních algoritmů.


Testování evolučních algoritmů Pro testování optimalizačních algoritmů se používají dva rozdílné postupy. V prvním obvykle vycházíme z již existujících příkladů, které již byly řešeny jinými algoritmy. Výsledky právě testovaného algoritmu pak porovnáme s výsledky již existujícími. Druhý způsob spočívá v tom, že použijeme množinu testovacích funkcí, osahující funkce s různými vlastnostmi, jako je nelinearita, různé patologie typu rovina okolo extrému (Obr. 13.16) apod. Vzhledem k tomu, že jsou známy analytické vztahy, je u většiny z nich velmi jednoduché vypočítat pozici a hodnotu extrému pro libovolnou dimenzi. Pouze pár funkcí (Obr. 13.14, Obr. 13.15, Obr. 13.16, Obr. 13.19 - Obr. 13.24) z této množiny funkcí jsou oříškem díky své nepravidelnosti a proto u nich nelze provést jednoduchým způsobem výpočet globálního extrému. Výpočet je jednoduše proveditelný. Vše, co je potřeba vědět, je hodnota extrému v 1D realizaci. Například u tzv. Schwefelovy funkce (Obr. 13.8) je v E1 pozice globálního extrému na souřadnicích x = 420,97 a hodnota funkce je f(x) = –418,9829. Pro výpočet hodnoty extrému v např. E15 stačí vynásobit hodnotu extrému v E1 číslem dimenze tj. číslem 15. V tomto případě je hodnota globálního extrému pro Schwefelovu funkci v E15 rovna f (x1, …, x15) = 15 (-418,9829) = -6284,7435. Tento extrém leží na souřadnicích x1, … , x15 = 420,97. Tentýž princip platí i pro další funkce mimo již zmíněné funkce (Obr. 13.14, Obr. 13.15, Obr. 13.16, Obr. 13.19 - Obr. 13.24).


Testování evolučních algoritmů Na Obr. 13.1, je průřez Schwefelovou funkcí na souřadnicích x1 = 0 a x2 [–512, 511]. Na grafu je vodorovná čára reprezentující vzdálenost 25% od globálního extrému. Je vidět, že množina bodů, jenž se liší od globálního extrému x%, je poměrně členitá (viz též Obr. 13.2). Se snižováním hranice by samozřejmě těchto bodů ubývalo, až by zůstal nakonec jen jeden globální extrém. To však v případě funkcí s několika globálními extrémy není pravda (zůstal nakonec více globálních extrémů). Tato zobrazovací „filozofie“ byla použita i v galerii testovacích funkcí (Zelinka, 2002), (Zelinka, 2004) pro demonstrování někdy až extrémní složitosti, již některé testovací funkce vykazují.


Testování evolučních algoritmů


Testování evolučních algoritmů

Obr. 13.2 Množina bodů Schwefelovy funkce lišící se od globálního extrému v různých hodnotách % ve smyslu hodnoty účelové funkce. prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů První de Jongova funkce (1st De Jong)

Obr. 13.3 První de Jongova funkce. Červený bod vpravo reprezentuje pozici globálního extrému.

Globální minimum: v E2 o na pozici … (x1, x2) = (0, 0) o o hodnotě … y = 0 v En o na pozici … (x1, x2, …, xn) = (0, 0, …, 0) o o hodnotě … y = 0 n = 0 prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Druhá de Jongova funkce- Rosenbrockovo sedlo (Rosenbrock’s saddle)

Obr. 13.4 Rosenbrokovo sedlo (též banánová funkce). Červený bod vpravo reprezentuje pozici globálního extrému.

Globální minimum: v E2 o na pozici … (x1, x2) = (1, 1) o o hodnotě … y = 0 v En o na pozici … (x1, x2, …, xn) = (1, 1, … 1) o o hodnotě … y = 0 n = 0 prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Třetí de Jongova funkce (3rd De Jong)

Obr. 13.5 Třetí de Jongova funkce. Červený bod vpravo reprezentuje pozici globálního extrému. Globální minimum: v E2 o na pozici … (x1, x2) = (0, 0) o o hodnotě … y = 0 v En o na pozici … (x1, x2, …, xn) = (0, 0, … 0) o o hodnotě … y = 0 n = 0 prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Čtvrtá de Jongova funkce (4th De Jong)

Obr. 13.6 Čtvrtá de Jongova funkce. Červený bod vpravo reprezentuje pozici globálního extrému. Globální minimum: v E2 o na pozici … (x1, x2) = (0, 0) o o hodnotě … y = 0 v En o na pozici … (x1, x2, …, xn) = (0, 0, … 0) o o hodnotě … y = 0 n = 0 prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Rastriginova funkce (Rastrigin’s function)

Obr. 13.7 Rastriginova funkce. Červený bod vpravo reprezentuje pozici globálního extrému. Globální minimum: v E2 o na pozici … (x1, x2) = (0, 0) o o hodnotě … y = -400 v En o na pozici … (x1, x2, …, xn) = (0, 0, … 0) o o hodnotě … y = -200 . n prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Schwefelova funkce (Schwefel’s function)

Obr. 13.8 Schwefelova funkce. Červený bod vpravo reprezentuje pozici globálního extrému.

Globální minimum: v E2 • na pozici … (x1, x2) = (420,969; 420,969) • o hodnotě … y = -837,966 v En •na pozici … (x1, x2, …, xn) = (420,969; …; 420,969) •o hodnotě … y = -418,983 n prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Griewangkova funkce (Griewangk’s function)

Obr. 13.9 Griewangkova funkce. Červený bod vpravo reprezentuje pozici globálního extrému.

Globální minimum: v E2 • na pozici … (x1, x2) = (0, 0) • o hodnotě … y = 0 v En • na pozici … (x1, x2, …, xn) = (0, 0, …, 0) • o hodnotě … y = 0 n = 0 prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Sinová obálková sinusoidalní funkce (sine envelope sine wave function)

Obr. 13.10 Sinová obálková sinusoidalní funkce. Červená kružnice reprezentuje pozici globálního extrému.

Globální minimum: v E1 • na pozici … x1 = -2,06668 nebo 2,06668 • o hodnotě … y = -1,4915 v En • na pozici … kružnice v En • o hodnotě … y = -1,4915 (n-1) prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Roztažená sinusoidální V funkce (stretched V sine wave function)

Obr. 13.11 Roztažená sinusoidální V funkce. Červený bod vpravo reprezentuje pozici globálního extrému.

Globální minimum: v E2 • na pozici … (x1, x2) = (0, 0) • o hodnotě … y = 0 v En • na pozici … (x1, x2, …, xn) = (0, 0, … , 0) • o hodnotě … y = 0 n = 0 prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Ackleyho funkce I (Ackley’s function I)

Obr. 13.12 Testovací funkce Ackley s detailním výřezem uprostřed. Červené body reprezentujíe pozici globálního extrému. Globální minimum: v E2 • na pozici … (x1, x2) = (-1,50236; -0,754865) nebo (1,50236; -0,754865) • o hodnotě … y1,2 = -4,5901 v E3 • na pozici … (x1, x2, x3) = (1,51563; -1,10937; -0,747245) • o hodnotě … y = -7,54276 v En (přibližně) • na pozici … (x1, x2, …, xn) = (1,51563; -1,1151; -1,10972; …, -1.10972, -0.747245) • hodnotě… y = -7,54276 -2,91867 (n-3) prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Ackleyho funkce II (Ackley’s function II)

Obr. 13.13 Ackelyho funkce II. Červený bod uprostřed reprezentuje pozici globálního extrému. Globální minimum: v E2 • na pozici … (x1, x2) = (0, 0) • o hodnotě … y = 0 v En • na pozici … (x1, x2, … , xn) = (0, 0, … , 0) • hodnotě … y = 0 n = 0 Poznámka: Při numerických experimentech s touto funkcí lze získat zobrazení, jaké je na grafu vpravo. Jde jasně o schodovitou funkci, která se nezmění ani při výpočtu a vykreslení s extrémně velkým rozlišením. Evidentně jde o numerickou nepřesnost použitého software. Hodnota funkce v globálním minimu byla vždy 2,6645410-15, ačkoliv podle předpisu funkce musí být 0. prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Plato vajec (egg holder)

Obr. 13.14 Držák (plato) vajec.

Globální minimum: Přesnou hodnotu globálního minima autoři v literatuře nikde nenašli.


Testování evolučních algoritmů Ranova funkce (Rana’s function)

Obr. 13.15 Ranova funkce.



Testování evolučních algoritmů Patologická funkce (pathological function)

Obr. 13.16 Patologická funkce (detail vpravo).



Testování evolučních algoritmů Michalewiczova funkce (Michalewicz’s function)

Obr. 13.17 Michalewiczova funkce. Červený bod reprezentuje pozici globálního extrému.

Globální minimum: v E2 • na pozici … (x1, x2) = (2,20291; 1,57096) • o hodnotě … y = -1,8013 v En > 2 • na pozici … (x1, x2, … , xn) = (2,20291; 1,57104; … …, 1,57104) • o hodnotě … y = 1,00098 (n-2) prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Mastersova funkce (Master’s cosine wave function)

Obr. 13.18 Mastersova funkce. Červený bod reprezentuje pozici globálního extrému.

Globální minimum: v E2 • pozice … (x1, x2) = (0, 0) • hodnota … y = -1 v En • pozice • hodnota

… (x1, x2, …, xn) = (0, 0, … , 0) … y = -1 . n prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Problém dělení čaje Zadání problému zní: obchodník s bylinnými čaji nakoupil od pěstitelů a sběratelů bylin 3 kg usušené máty (5% odpadu) a 1,5 kg usušené třezalky (8% odpadu). Z těchto bylin chce připravit sáčky s hmotností 10 g jednak s čistou mátou, jednak se směsí máty a třezalky. Uvažujme dva druhy směsí, a to směs I, ve které bude poměr máty a třezalky 3:2, a směs II, ve které budou obě tyto byliny zastoupeny stejným dílem. Předpokládaný zisk z prodeje jednoho sáčku uvažovaných druhů čaje je po řadě 2 Kč, 3 Kč, 2 Kč. Kolik sáčků s mátou, se směsí I a se směsí II má obchodník z nakoupených bylin připravit, aby si jejich prodejem zajistil co největší zisk? Neznámé veličiny v dané úloze představují počty sáčků naplněných jednotlivými druhy čajů, a to x1 ……. počet sáčků s mátou x2 ……. počet sáčků se směsí I x3 ……. počet sáčků se směsí II Po odečtení 5% z nakoupeného množství máty a 8% z nakoupeného množství třezalky bude k dispozici 2850 g máty a 1380 g třezalky. Omezení, která jsou dána těmito množstvími, jsou vyjádřena nerovnicemi (13.2)


Testování evolučních algoritmů Problém dělení čaje

Obr. 13.19 Graf (z = 0) zobrazující možná řešení dávkování čaje (vlevo) a detail s globálním extrémem (vpravo).

Obr. 13.20 Graf (y = 345) zobrazující možná řešení dávkování čaje (vlevo) a detail s globálním extrémem (vpravo). prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Problém dělení čaje

Obr. 13.21 Graf (x = 78) zobrazující možná řešení dávkování čaje (vlevo) a detail s globálním extrémem (vpravo).

Globální minimum: v E3 • pozice … (x1, x2, x3) = (78, 345, 0) • hodnota … y = 1191


Testování evolučních algoritmů Shekelova funkce (Shekel’s foxhole)

Data: c = (0,806; 0,517; 0,1; ,908; 0,965; 0,669; 0,524; 0,902; 0,531; 0,876; 0,462; 0,491; 0,463; 0,714; 0,352; 0,869; 0,813; 0,811; 0,828; 0,964; 0,789; 0,360; 0,369; 0,992; 0,332; 0,817; 0,632; 0,883; 0,608; 0,326);

a={ {9,681; 0,667; 4,783; 9,095; 3,517; 9,325; 6,544; 0,211; 5,122; 2,020}; {9,400; 2,041; 3,788; 7,931; 2,882; 2,672; 3,568; 1,284; 7,033; 7,374}; {8,025; 9,152; 5,114; 7,621; 4,564; 4,711; 2,996; 6,126; 0,734; 4,982}; {2,196; 0,415; 5,649; 6,979; 9,510; 9,166; 6,304; 6,054; 9,377; 1,426}; {8,074; 8,777; 3,467; 1,863; 6,708; 6,349; 4,534; 0,276; 7,633; 1,567}; {7,650; 5,658; 0,720; 2,764; 3,278; 5,283; 7,474; 6,274; 1,409; 8,208}; {1,256; 3,605; 8,623; 6,905; 4,584; 8,133; 6,071; 6,888; 4,187; 5,448}; {8,314; 2,261; 4,224; 1,781; 4,124; 0,932; 8,129; 8,658; 1,208; 5,762}; {0,226; 8,858; 1,420; 0,945; 1,622; 4,698; 6,228; 9,096; 0,972; 7,637}; {7,305; 2,228; 1,242; 5,928; 9,133; 1,826; 4,060; 5,204; 8,713; 8,247}; {0,652; 7,027; 0,508; 4,876; 8,807; 4,632; 5,808; 6,937; 3,291; 7,016}; {2,699; 3,516; 5,874; 4,119; 4,461; 7,496; 8,817; 0,690; 6,593; 9,789}; {8,327; 3,897; 2,017; 9,570; 9,825; 1,150; 1,395; 3,885; 6,354; 0,109}; {2,132; 7,006; 7,136; 2,641; 1,882; 5,943; 7,273; 7,691; 2,880; 0,564}; {4,707; 5,579; 4,080; 0,581; 9,698; 8,542; 8,077; 8,515; 9,231; 4,670}; {8,304; 7,559; 8,567; 0,322; 7,128; 8,392; 1,472; 8,524; 2,277; 7,826}; {8,632; 4,409; 4,832; 5,768; 7,050; 6,715; 1,711; 4,323; 4,405; 4,591}; {4,887; 9,112; 0,170; 8,967; 9,693; 9,867; 7,508; 7,770; 8,382; 6,740}; {2,440; 6,686; 4,299; 1,007; 7,008; 1,427; 9,398; 8,480; 9,950; 1,675}; {6,306; 8,583; 6,084; 1,138; 4,350; 3,134; 7,853; 6,061; 7,457; 2,258}; {0,652; 2,343; 1,370; 0,821; 1,310; 1,063; 0,689; 8,819; 8,833; 9,070}; {5,558; 1,272; 5,756; 9,857; 2,279; 2,764; 1,284; 1,677; 1,244; 1,234}; {3,352; 7,549; 9,817; 9,437; 8,687; 4,167; 2,570; 6,540; 0,228; 0,027}; {8,798; 0,880; 2,370; 0,168; 1,701; 3,680; 1,231; 2,390; 2,499; 0,064}; {1,460; 8,057; 1,336; 7,217; 7,914; 3,615; 9,981; 9,198; 5,292; 1,224}; {0,432; 8,645; 8,774; 0,249; 8,081; 7,461; 4,416; 0,652; 4,002; 4,644}; {0,679; 2,800; 5,523; 3,049; 2,968; 7,225; 6,730; 4,199; 9,614; 9,229}; {4,263; 1,074; 7,286; 5,599; 8,291; 5,200; 9,214; 8,272; 4,398; 4,506}; {9,496; 4,830; 3,150; 8,270; 5,079; 1,231; 5,731; 9,494; 1,883; 9,732}; {4,138; 2,562; 2,532; 9,661; 5,611; 5,500; 6,886; 2,341; 9,699; 6,500} }


Testování evolučních algoritmů Shekelova funkce (Shekel’s foxhole)

Globální minimum: v E2 • na pozici … (x1, x2) = (8,02407; 9,14653) • o hodnotě … y = -12,119 Poznámka: tato funkce je obvykle používána jen v E2. prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Pseudo-Dirakova funkce


Testování evolučních algoritmů Pseudofraktální funkce Za fraktální funkci jsme zvolili modifikaci slavné Weierstrassovy – Mandelbrotovy funkce (Mandelbrot, 1983), (Back, 1996), která je zadána nekonečnou řadou,

(13.4)

kde i je imaginární jednotka, b > 1 ovlivňuje optickou zřetelnost fraktality grafu, φj je libovolný fázový úhel a D (1 < D < 2) je fraktální dimenze křivky W. Tato křivka, objevená Karlem Weierstrassem v roce 1872, je grafem spojité funkce, ale v žádném bodě nemá konečnou derivaci (viz Zelinka, Včelař, Čandík, 2006). Touto křivkou šokoval Weierstrass v r. 1872 berlínskou Akademii. Na tato fakta mnozí matematici reagovali velmi negativně (Ch. Hermite v dopise T. Stieltjesovi: „...odvrátil jsem se s hrůzou a ošklivostí od toho politováníhodného zla, kterým jsou funkce bez derivace...“). Výše uvedené platí rovněž pro reálnou část zjednodušené funkce (13.4) (φj = 0):


Testování evolučních algoritmů Pseudofraktální funkce Tato verze Weierstrassovy – Mandelbrotovy funkce bývá rovněž nazývána Weierstrass – Mandelbrotova kosinová fraktální funkce (Back, 1996), (Mandelbrot, 1983). Podle (Berry, Lewis, 1980) vykazuje (13.5) určitý trend, který je ovlivňován parametrem D. Aby byla fraktální funkce prosta jakéhokoliv trendu, byla navržena varianta funkce, v níž je příslušný trend maximálně eliminován. Tato varianta je dána vztahem (13.6).

(13.6)

Průběh funkce (13.6) je zobrazen na Obr. 13.25.


Testování evolučních algoritmů Pseudofraktální funkce Pro použití takového fraktálního průběhu k testování EVT je vhodné jej použít spolu s již existujícími multimodálními testovacími funkcemi. To lze provést tak, že (13.6) jednoduše přičteme k příslušné testovací funkci. Vztah (13.7) demonstruje použití fraktální funkce (13.6) s testovací funkcí z Obr. 13.3 (Back, 1996): (13.7) Na Obr. 13.26 a) je vidět výsledný efekt na funkci z Obr. 13.3. Z celkového průběhu na Obr. 13.25 je vidět, že pouhá superpozice nemusí vždy stačit k „zašumění“ testovací funkce, protože „amplituda“ fraktální složky je malá v porovnání s jejími hodnotami (viz například Obr. 13.8 a Obr. 13.15). To lze řešit v případě potřeby zesílením fraktální složky (vynásobením vhodnou konstantou). Výsledek je na Obr. 13.26 b).


Testování evolučních algoritmů Pseudofraktální funkce

Obr. 13.28 Fraktální funkce (13.6) superponovaná na funkci z Obr. 13.3 s různou dimenzí D. prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Testování evolučních algoritmů Pseudofraktální funkce

Obr. 13.27 Fraktální funkce (13.6) superponovaná na funkci z Obr. 13.3 v E2 s různým stupněm zesílení fraktální složky.


Testování evolučních algoritmů Program


Chcete vědět víc? Testovací funkce používané na ověření výkonnosti EVT lze najít v mnoha odborných zdrojích. Evoluční algoritmy lze v podstatě testovat dvojím způsobem. Buď se použijí umělé testovací funkce, nebo příklady z praxe, které byly již optimalizovány jinými algoritmy. Přehled testovacích funkcí, podobný výše uvedenému seznamu, lze nalézt v (Babu, Onwubolu, 2004), v (Richter, 2006) kde je studováno použití evolucí na složité problémy, postavené na chaotických systémech. Chaotický systém, v tomto případě tzv. CML systém slouží jako velmi komplexní testovací funkce, jejíž geometrická reprezentace se v čase dynamicky mění. Hodně testovacích funkcí lze nalézt na Internetu. Jako příklad za všechny lze použít www-optima.amp.i.kyoto-u.ac.jp/ member/student/hedar/Hedar_files/TestGO.htm, kde je relativně velké množství testovacích funkcí.


Literatura Prezentace byla udělána na základě této publikace. Více detailů, odkazů na další zdroje a příkladů naleznete v této knize, příp. na www.fai.utb.cz/people/zelinka/evoluce.


Biologicky inspirované výpočty: evoluční algoritmy

Recommend Documents