Warning
This page is located in archive.

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 \ldots 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

courses/a0m33eoa/cviceni/tyden_07.txt · Last modified: 2018/11/09 10:04 by kubalik