Genetické programování (část 1)
Nebojte se - genetické programování nemá nic společného s roubováním, zaléváním, opylováním a podobnými záležitostmi, kterým se technicky založený člověk spíše vyhýbá, než aby se jim po večerech věnoval. Naopak, díky nárůstu výkonu moderních počítačů už není doménou akademických týmů a nám, nadšencům nic nebrání pořídit si „pěstitelskou laboratoř“ přímo v obýváku.
Nebojte se - genetické programování nemá nic společného s roubováním, zaléváním, opylováním a podobnými záležitostmi, kterým se technicky založený člověk spíše vyhýbá, než aby se jim po večerech věnoval. Naopak, díky nárůstu výkonu moderních počítačů už není doménou akademických týmů a nám, nadšencům nic nebrání pořídit si „pěstitelskou laboratoř“ přímo v obýváku.
O co tedy jde?
Zjednodušeně řečeno – o to, jak najít optimální řešení problému bez složitého přemýšlení a ještě složitějšího programování.
Zkusme si to vysvětlit na školním případě obchodního cestujícího: Obchodník firmy Držgrešle & syn má za úkol během jedné cesty navštívit všechny zákazníky firmy a převzít nové objednávky. Zákazníci jsou ovšem roztroušeni po všech městech České republiky a obchodník si platí benzín ze svého. Musí se tedy snažit, aby nenajel ani o kilometr víc, než je třeba.
Protože ani hodinové zápolení s autoatlasem nenese výsledky, obrátí se na svého kamaráda programátora a požádá ho o jednoduchý prográmek, kterým by nejkratší trasu našel. Netuší ovšem, že mu tím připravil nejednu bezesnou noc, neboť vymyslet takový algoritmus není nic jednoduchého (zkuste si to)...
Pokud by ovšem kamarád znal genetické programování, měl by úkol o dost jednodušší. Postupoval by asi takto:
1) vytvořil by náhodně deset tras, které vedou přes všechna města
2) z nich by vybral dvě nejkratší
3) ty mezi sebou zkřížil a zmutoval (příště si ukážeme jak)
4) tím by získal dalších 10 tras – už podstatně kratších
5) body 2) až 4) by opakoval tak dlouho, dokud by nenašel optimální trasu.
Jak je vidět, genetický algoritmus vede k výsledku i bez velkého úsilí a hlavně bez detailní znalosti problému.
Pojďme se na chvíli věnovat suchým definicím - Genetický algoritmus (GA) je heuristický postup, který se snaží aplikací principů evoluční biologie nalézt řešení složitých problémů, pro které neexistuje použitelný exaktní algoritmus (http://cs.wikipedia.org/wiki/Genetický_algoritmus). Přeloženo do normální řeči – pokud známe několik špatných řešení daného problému a dokážeme vyjádřit, jak moc jsou špatně, můžeme je mezi sebou křížit a mutovat podobně jako živé organismy a tím dojít ke správnému výsledku.
To, jak je řešení dobře nebo špatně se vyčísluje pomocí tzv. fitness funkce. Řečeno opět suchou řečí Wikipedie - fitness vyjadřuje cenu jedince z hlediska evoluce (Takže dneska večer honem do posilovny :-)).
Schopnost správně definovat fitness funkci tedy klíčová. Pokud vezmeme problém zástupce firmy Držgrešle & syn, pak fitness funkcí bude celkový počet ujetých kilometrů – čím menší, tím lepší.
Jak konkrétně to může fungovat si ukážeme v příštím díle...
Diskuze