====== 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 {{ :courses:a0m33eoa:cviceni:2006_problem_definitions_and_evaluation_criteria_for_the_cec_2006_special_session_on_constraint_real-parameter_optimization.pdf | 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í 

{{:courses:a0m33eoa:cviceni:g06.png?700|}}

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

{{:courses:a0m33eoa:cviceni:g08_detail.png?600|}}

**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é

{{:courses:a0m33eoa:cviceni:g11.png?700|}}

**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:g24.png?700|}}