Úkol 5 - Řešení problému batohu genetickým algoritmem

• CTU Prague, MI-PAA, ZS 2011
• Autor: Tomáš Borovička (borovto1)

• Seznamte se se zvolenou pokročilou iterativní metodou na problému batohu.

Genetické algoritmy jsou typem evolučních algoritmů, algoritmů jež jsou inspirovány evolučními procesy v přírodě. Jedná se o iterativní algoritmy, které v každé iteraci zlepšují množinu řešení (populaci) pomocí operací selekce, křížení, nebo mutace. Výhodou těchto algoritmů, je jejich nezávislost na typu problému. Jedinou jejich znalostí je výpočet fitness funkce, která reprezentuje kvalitu řešení (potomka).

Pro řešení jsme zvolil Generational metodu genetického algoritmu, tedy metodu, které v každé iteraci generuje novou populaci. Její princip naznačuje následující pseudokód a popis fází algoritmu.

Pseudokód:

1. Vygeneruj výchozí náhodnou populaci P(0).
2. N-krát opakuj:
   1. Vytvoř novou práznou populaci P(N).
      1. Selekce - vyber rodiče z populace P(N-1)
      2. Křížení - proveď s rodiči operaci křížení
      3. Mutace - proveď s potomky operaci mutace
      4. Přidej potomky do nové populace
   2. Nahraď starou populaci novou populací P(N-1)=P(N)
3. Potomek z populace P(N) s nejlepší kondicí je řešením

Fitness, neboli kondice genotypu, určuje kvalitu řešení. V případě problému batohu je to cena věcí v batohu s podmínkou překročení váhy. V případě překročení váhy je kondice nejhorší možná.

Pro selekci jsem implementoval metodu náhodného výběru a metodu turnaje. Použil jsem nakonec pouze metodu turnaje.

• Turnajová selekce
  1. Z populace náhodně vyberu N prvků, kde N se je velikost turnaje.
  2. Z těchto N prvků vyberu prvek s nejlepší kondicí.

Implementoval jsem jednobodové a dvoubodové křížení. Při křižení dvou genomů se 50% pravděpodobností uskuteční jednobodové křížení a s 50% pravděpodobností dvoubodové křížení.

• Jednobodové křížení
• Dvoubodové křížení

Každý gen genomu zmutuje s pravděpodobností, jež lze parametricky určit.

Windows Server 2008 EE x64, Intel Core2 Duo E8500@3.16GHz, 8 GB DDR2

• Velikost populace 50
• Počet iterací 25
• Pravděpodobnost křížení 0.8
• Pravděpodobnost mutace genu 0.05

S velikostí instance roste i výpočetní čas. Podle očekávání výpočetní čas roste s velikostí instance lineárně.

Podle očekávání čas výpočtu roste lineárně i s počtem iterací.

Jak je patrné z grafu, se zvyšujícím se počtem iterací, exponencielně klásá relativní chyba řešení. Po určitém počtu iterací se již řešení nezlepšuje, tento počet iterací je ideální pro výchozí konfiguraci. V tomto případě ustálení nastává po 25 iteracích.

Stejně jako u velikosti instance, nebo počtu iterací i s velikostí populace roste čas výpočtu lineárně.

Stejně jako s rostoucím počtem iterací, tak i se zvětšující se populací, exponencielně klesá relativní chyba. Ustálení nastalo u populace čítající 50 genomů.

Relativní chyba s nárůstajícím počtem mutací do určité hodnoty klesá, pak ale začne opět výrazně stoupat. Dosažené minimum je ideální pro výchozí nastavení genetického algoritmu pro tento problém.

Z grafu není patrná žádná závislost relativní chyby na pravděpodobnosti křížení. Narozdíl od pravděpodobnosti mutace, pravděpodobnost křížení neměla na relativní chybu příliš velký vliv v celém svém rozsahu.

Čas výpočtu roste s velikostí instance, velikostí populace a počtem iterací lineárně. Genetický algoritmus lze tedy použít na velké instance s lineárně rostoucími požadavky na výpočetní výkon.
Z experimentu vyplývá, že relativní chyba klesá s počtem iterací do určité hranice, kde se už řešení nezlepšuje. Stejně tak klesá relativní chyba i s velikostí populace až se zastaví a dál zvětšování populace nezlepšuje výsledek. Zajímavé chování vykazuje algoritmus v závislosti na pravděpodobnosti mutace, kdy hodnota relativní chyby klesá do určité hodnoty, kde se zastaví a pak opět roste. Ukazuje se, že je to jeden z parametrů, na který je genetický algoritmus nejvíce citlivý. Naopak pravděpodobnost křížení neměla výrazný vliv na výslednou relativní chybu.

Experimentální nastavení GA s nejlepšími výsledky

• Velikost populace 50
• Počet iterací 25
• Pravděpodobnost křížení 0.8
• Pravděpodobnost mutace genu 0.05

S tímto nastavením dosahoval algoritmus nejmenší relativní chyby a to pod 1,5%, což lze považovat za velmi dobrý výsledek.

• http://en.wikipedia.org/wiki/Knapsack_problem
• http://rosettacode.org/wiki/Knapsack_problem/0-1