Evolucijski algoritmi

Evolucijski algoritmi delujejo nad populacijo potencialnih kadnidatov za rešitev problema. Ti kandidati se razvijajo z iterativno rabo stohastičnih operatorjev mutacije, križanja in selekcije. Evolucijski algoritmi oponašajo pojave v naravi.

Osnovni pojmi

• osebek - možna rešitev problema,
• generacija - je množica osebkov - več različnih rešitev,
• populacija - množica iz katere izbiramo osebke v generaciji,
• genotip - zapis genov, ki jih izvajamo v algoritmu - zapis osebkov,
• kromosom - genotip z binarnimi vrednostmi,
• gen - posamezen bit kromosoma,
• fenotip - interpretacija genotipa.

Velika zanka

Evolucijski cikel (big loop) vsebuje naslednje korake:

1. kreiranje začetne generacije
2. izračun prileganja generacije (fitnes funkcija)
3. selekcija
4. križanje
5. mutacija
6. če je pogoj za konec izpolnjen končaj, sicer pojdi na korak 2

Selekcija

Selekcija na osnovi funkcije prileganja določi populacijo za reprodukcijo. Verjetnost, da izberemo posamezen osebek raste z njegovo funkcijo prileganja (večja kot je funkcija prileganja, večja je verjetnost, da bo osebek izbran za reprodukcijo).

Križanje

Naključno združujemo po vrsti po dva in dva osebka. Križanje med njima se ne izvede zmeraj, ampak je predpisano z neko verjetnostjo. Če pride do križanja, naključno izberemo točko križanja in premešamo gene izbranih osebkov.

Mutacija

Prav tako kot križanje se tudi mutacija izvede z določeno verjetnostjo, le da je ta verjetnost občutno manjša. Ponavadi izvajamo mutacijo tako, da gremo čez vse bite vseh kromosomov in jih obrnemo z verjetnostjo mutacije. Mutacija je zelo pomemben operator, saj bi brez nje bili omejeni samo na različne premešave začetnih kromosomov.

Genetsko programiranje

Genetsko programiranje je uporaba genetskega modela učenja na programih. Osebki so različni programski moduli. Pri genetskem programiranju je sintaksa programskih modulov v prefiksni obliki, zato jih lahko zapišemo v obliki binarnega drevesa. Jezik je omejen z določenim številom spremenljivk, konstant in operatorjev. Podan imamo funkcijski niz - možne funkcije in terminalski niz - možne vhode.

Nad drevesom izvajamo genetske operatorje:

• križanje - zamenjava poddreves dveh starševskih dreves,
• mutacija - naključna odstranitev poddrevesa in zamenjava z novim poddrevesom,
• evolucijske strategije - različne variante mutacije, križanja in selekcije.