Zadání: Máme dáno n předmětů. Pro každý předmět i = 1 ... n máme dánu hmotnost W[i] a cenu P[i]. Je dána kapacita C. Máme najít takový binární vektor x = (x[1] ... x[n]) takový, že
Nabízí se hned několik možností, jak tento problém řešit pomocí genetických algoritmů. Ukažme si některé z nich.
V těchto algoritmech reprezentujeme vektory pomocí binárních řetězců délky n. (Tzn. předmět je v batohu právě když x[i] = 1). Kvalitu (fitness) eval(x) spočteme takto:
eval(x) = x[i] * P[i] - Pen(x),
kde Pen(x) je penalizační funkce.
V našem vyhledávacím prostoru se nacházejí i řetězce, které nesplňují podmínku (1) zadání. Pro tyto řetězce potřebujeme určit nějaké znehodnocení (potřebujeme zmenšit jejich fitness). Toto znehodnocení je reprezentováno penalizační funkcí. Penalizační funkce má hodnotu 0 pro řetězce splňující podmínku (1) zadání. Pro řetězce, které tuto podmínku nesplňují, je kladná. Je mnoho způsobů, jak vypočítávat penalizační funkci. Ukažme si některé možnosti:
Reprezentace generace bude v tomto typu algoritmu stejná, jako v Ap[i]. Odlišný bude výpočet kvality řetězce. Stejně jako v předchozím algoritmu nastává situace, kdy řetězec reprezentuje "přeplněný" batoh. Na tyto řetězce voláme opravnou funkci, která některé přebytečné věci z batohu vyhází. Nebo-li bude odebírat předměty z batohu (měnit 1 na 0 na určitých místech řetězce) tak dlouho, dokud nebude splněna podmínka (1) ze zadání (neboli dokud se zbytek do batohu nevejde). Tímto způsobem dostaneme z původního řetězce x řetězec x', který bude reprezentovat platné řešení.
V těchto algoritmech kódujeme problém tak, abychom prohledávali pouze tu část prostoru, která splňuje podmínku (1) ze zadání. Vzdáváme se přitom reprezentace batohu jako binárního řetězce.
Zadání: Obchodní cestující má každé město navštívit právě jednou a pak se vrátit do města, ze kterého vycestoval. Naším úkolem je při znalosti ceny cesty mezi jednotlivými městy najít co nejlevnější způsob (pořadí měst), jak tuto cestu provést.
Nejdůležitější při použití genetického algoritmu bude problém, jak cestu zakódovat a jak provést křížení a mutaci. Ukažme si opět několik možností, jak lze úlohu zakódovat.
Města jsou očíslovaná. Cestu budeme kódovat do vektorů délky rovné počtu měst. Číslice na j-tém místě vektoru udává, kam se má vydat obchodník z j-tého města. Cestu přitom vždy začínáme z města číslo 1. Čili například pro 9 měst reprezentuje vektor (2, 4, 8, 3, 9, 7, 1, 5, 6) reprezentuje následující cestu 1-2-4-3-8-5-9-6-7. Ne každý vektor ovšem reprezentuje cestu přes všechna města. Například cesta (3, 1, 2, 4, 5, 6, 7, 8, 9) skončí poměrně brzy. Tyto nepříjemné cykly by se vytvářeli při klasickém použití křížení. Proto je nutné nadefinovat jiné křížení, které obsahuje opravný algoritmus.