Table of Contents
Evoluční algoritmy pro úlohy s omezeními
Cílem dnešního cvičení je implementace evolučního algoritmu pro úlohy s omezeními. Podobně jako u vícekriteriálního algoritmu NSGA-II i teď stačí implementovat jednoduché úpravy základního evolučního algoritmu. Vyzkoušíme si dvě varianty adaptivní penalizace, které jsem probrali na přednášce:
- metoda [Hadj-Alouane92], která adaptuje váhu penalizace na základě toho, jaké bylo nejlepší řešení v posledních $k$ generacích,
- metoda využívající tzv. Stochastic Ranking pro seřazení jedinců na základě hodnot účelové funkce i penalizace za porušená omezení.
Pokud úkoly nestihnete na cvičení, dokončete je doma.
Adaptace váhy penalizace
Tato metoda adaptuje váhu $r_g(t)$ v čase následujícím způsobem:
- pokud bylo nejlepší řešení v posledních $k$ generacích vždy přípustné, tak se váha upraví $r_g(t+1) = (1/\beta_1) * r_g(t)$
- pokud bylo nejlepší řešení v posledních $k$ generacích vždy nepřípustné, tak se váha upraví $r_g(t+1) = \beta_2 * r_g(t)$
- jinak se $r_g(t)$ nemění, tedy $r_g(t+1) = r_g(t)$
$\beta_1, \beta_2 > 1$ a $\beta_1 \neq \beta_2$
Implementujte tuto adaptivní metodu.
| Vstup | Aktuální $r_g(t)$ |
|---|---|
| Vstup | Informace o přípustnosti nejlepšího řešení v posledních $k$ generacích |
| Výstup | Aktualizovaná hodnota $r_g(t+1)$ |
Implementujte metodu pro výpočet fitness daného jedince ve tvaru $fitness(x) = f(x) + r_g(t)*\sum_{i=1}^{m+p}G_i(x)$, kde
- $f(x)$ je hodnota účelové funkce
- $G_i(x)$ je rozsah porušení $i$-tého omezení
| Vstup | $f(x)$ |
|---|---|
| Vstup | $G_i(x)$ pro $i = 1 ... m+k$ |
| Vstup | $r_g(t)$ |
| Výstup | fitness |
Implementujte evoluční algoritmus s generační náhradovou strategií, používající implementovanou fitness funkci s adaptovanou váhou penalizace nepřípustných řešení.
Stochastic Ranking
Tato metoda nejprve seřadí jedince v populaci od nejlepšího po nejhoršího pomocí stochastické metody podobné Bubble-sort. Na takto seřazenou populaci potom můžeme aplikovat např. turnajovou selekci, ve které jedinec s nižším pořadím vítězí nad jedincem s vyšším pořadím.
Implementujte metodu stochastického Bubble-sortu, viz přednáška.
| Vstup | Populace jedinců; každý jedinec má napočítané hodnoty $f(x)$ a $\sum_{i=1}^{m+p}G_i(x)$ |
|---|---|
| Výstup | Populace seřazená od nejlepšího k nejhoršímu |
Implementujte evoluční algoritmus s generační náhradovou strategií, používající implementovanou metodu stochastického řazení a pořadovou turnajovou selekci.
Experimentální ověření
Jako testovací problém použijeme optimalizaci reálných funkcí se spojitými parametry. Konkrétně problémy g06, g08, g11 a g24 z článku problem_definitions.
Použijte již naimplementované operátory pro reálnou reprezentaci.
Problém g06:
- dvě nelineární nerovnostní omezení $g_1(x)$ a $g_2(x)$
- optimální řešení (červený bod) leží na hranici mezi přípustnými a nepřípustnými řešeními
- zeleně jsou zobrazeny oblasti pro daná omezení
Problém g08:
- dvě nelineární nerovnostní omezení $g_1(x)$ a $g_2(x)$
- optimální řešení leží uvnitř oblasti přípustných řešení
Problém g11:
- jedno nelineární rovnostní omezení $h(x)$
- použijte relaxaci rovnostního omezení ve tvaru $g \equiv |h(x)|-\epsilon \leq 0$
- doporučená hodnota $\epsilon = 0.0015$, můžete vyzkoušet i jiné
Problém g24:
- dvě nelineární nerovnostní omezení $g_1(x)$ a $g_2(x)$
- přípustná oblast je rozdělena na dvě disjunktní podoblasti
- optimální řešení leží na hranici přípustné oblasti
