Genetické algoritmy - srovnání

Zadání úloh na genetické algoritmy

Naimplementujte jednoduchý genetický algoritmus, viz níže, a otestujte jeho funkčnost podle jednoho ze tří navržených zadání. Ve všech případech se používá, pokud nebude uvedeno jinak,

• binární reprezentace,
• populace o velikosti 100,
• generační nahrazovací strategie s elitismem (2 nejlepší jedinci z dané populace jdou přímo do populace nové),
• 1-bodové křížení s pravděpodobností 0.9,
• jednoduchá mutace invertující 1 bit v chromozomu (v každém chromozomu se změní právě jeden náhodně vybraný bit),
• a turnajová selekce (nejlepší ze 3 náhodně zvolených jedinců je vybrán pro křížení).

Pro zvolené zadání použijte předepsané testovací funkce.

Vhodný vs. nevhodný operátor krížení

Ověřte, jaký vliv má zvolený operátor křížení na správné fungování GA. Porovnejte tyto operátory:

• 1-bodové křížení. Pro dva rodičovské chromozomy parent1 a parent2 se náhodně zvolí bod křížení. Nové chromozomy child1 a child2 vzniknou tak, že child1 zdědí začátek chromozomu z parent1 a konec z parent2; potomek child2 zdědí začátek chromozomu z parent2 a konec z parent1.
• Uniform křížení. Při generování child1 se u každého bitu rozhoduje s pravděpodobností 0,5 jestli zdědí daný bit z parent1 nebo z parent2. Potomek child2 dědí bity z opačného rodiče než child1.

Testovací funkce: F101, Rosenbrock, OneMax.

Grafy závislosti Ø-fitness na generaci

Červeně jsou znázorněny průměrné hodnoty pro crossover: one-point, modře pro crossover: uniform.

• fitness: f101
  
• fitness: rosenbrock
  
• fitness: one-max
  

Závěr

Při zkoumání vlivu cross-over funkce na rychlost nalezení optimálního řešení jsme provedli séri dvaceti měření evoluce padesáti generací pro každou z námi testovaných funkcí. U každé generace jsme stanovili celkovou fitness hodnotu, dále fitness, jako průměr ze všech odpovídajících průměrných fitness hodnot dílčích měření.

Funkce F101 v obou případech začínala s nulovou fitness první generace a končila na 83%, resp. 76% při použití funkce one-point, resp. uniform.

Pro Rosenbrockovu funkci platilo že v prvním případě začínala na 2,23*10^16 a končila na 6*10^12, zato v druhém případě začínala na 2,21*10^16 a končila na 1,20*10^13.

Funkce One-Max začínala v obou případech na 50% a končila na 98%, resp. ~100%.

Na základě dosažených výsledků nelze jednoznačně zamítnout hypotézu, že použití uniform cross-overu urychluje nalezení optimálního řešení. Tato hypotéza je postavena na přepokladu, že uniform cross-over zvětšuje prohazováním segmentů genů diverzitu množiny všech různých genů v celé populaci a umožňuje tak během stejného počtu generací prozkoumat vetší množství kombinací genů, z čehož plyne vyšší šance na nalezení optimálního řešení.

Jednoduché vs. klamné problémy

Overte, jaký vliv májí vlastnosti optimalizované funkce na správné fungování GA. Porovnejte tyto funkce:

• OneMax.
• DF3.
• Trap5.

Grafy závislosti Ø-fitness a Max-fitness na generaci

Červeně jsou znázorněny průměrné hodnoty, modře maximální.

• fitness: one-max, crossover: one-point
  
• fitness: df3, crossover: one-point
  
• fitness: trap-5, crossover: one-point
  

Závěr

Pro lepší představu o vlivu fitness funkce na rychlost nalezení optimálního řešení jsme provedli séri dvaceti měření evoluce padesáti generací pro každou z námi testovaných funkcí. U každé generace jsme stanovili celkovou fitness hodnotu, dále fitness, jako průměr ze všech odpovídajících průměrných fitness hodnot dílčích měření.

Funkce One-Max měla nejvyšší fitness počáteční generace - cca 50%, což se dá vysvětlit způsobem generování chromozomu, při kterém se každá allela obsadí buď 0 nebo 1 se stejnou pravděpodobností. Také měla nejvyšší fitness v poslední generaci, přes 98%, a celkový přírůstek fitness tedy činil cca 48%.

Funkce DF3 začínala na 37% a končila na 56%, přírůstek byl celkem 56%.

Poslední funkce Trap5 se chovala obdobně jako DF3, naměřené počáeční, resp. koncové hodnoty byly 38%, resp. 92% a přírůstek v tomto případě činil 55%. Z uvedených dat lze usuzovat na lepší přizpůsobivost funkcí DF3 a Trap5 než One-Max.