next up previous contents
Next: Učení RBF sítí pomocí Up: Genetický algoritmus Previous: Genetický algoritmus   Obsah


Algoritmus 5.1.1:

Vstup: pravděpodobnost mutace $p_m$, pravděpodobnost křížení $p_k$, počet jedinců v populaci $N$, kritérium ukončení výpočtu
Výstup: řešení daného problému

1. Start
: Vytvoř počáteční populaci $N$ jedinců $P(0) = \{ I_1,
\cdots , I_N \}$.
$i:=0$
2. Výpočet účelové funkce
: Ke každému jedinci spočti odpovídající hodnotu účelové funkce.
3. Test
: Je-li maximum účelové funkce v dané populaci dostatečně velké, skonči a vrať řešení odpovídající jedinci s maximální hodnotou účelové funkce.
4. Nová populace
: Vytvoř prázdnou populaci $P(i+1)$ a opakuj následující postup, dokud populace nebude obsahovat $N$ jedinců.
i) Selekce
: Vyber dva jedince z populace $P(i)$ v závislosti na jejich účelové funkci.
ii) Křížení
: S pravděpodobností $p_k$ vytvoř dva nové jedince aplikací operace křížení na vybrané jedince. Pokud nedojde ke křížení, noví jedinci jsou kopií vybraných jedinců.
iii) Mutace
: Na každého z nových jedinců aplikuj s pravděpodobností $p_m$ operaci mutace.
iv) Vložení
: Vlož nové jedince do populace $P(i+1)$.
5. Nová generace
: $i:=i+1$
Přejdi k bodu 2.

Chceme-li aplikovat algoritmus 5.1.1 na nějakou konkrétní úlohu, musíme určit

  1. způsob zakódování potencionálního řešení do řetězce bitů resp. čísel, znaků.
  2. způsob vytváření počáteční populace.
  3. účelovou funkci
  4. genetické operátory (popis realizace operátorů nad řetězci kódu)
  5. parametry genetického algoritmu (velikost populace, pravděpodobnosti operátorů)

Genetické algoritmy se používají typicky v případech, kdy parametrický prostor je příliš velký pro úplné prohledávání a proto se spokojíme s přibližným řešením. Jeho síla spočívá v tzv. implicitním paralelismu, kdy populace jedinců paralelně prochází parametrický prostor a navzájem se ovlivňuje a modifikuje. Populace jedinců tak najde řešení rychleji, než kdyby prostor prohledávali izolovaně. Rychlost učení však vždy závisí na konkrétní aplikaci.


next up previous contents
Next: Učení RBF sítí pomocí Up: Genetický algoritmus Previous: Genetický algoritmus   Obsah
Petra Kudova
2001-04-19