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.

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.

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í

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í.

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.

Implementujte evoluční algoritmus s generační náhradovou strategií, používající implementovanou metodu stochastického řazení a pořadovou turnajovou selekci.

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