Evolucijski algoritem

Iz Wikipedije, proste enciklopedije

Evolucijski algoritem je v računalništvu postopek optimizacije po vzoru biološke evolucije.

Evolucija uspe, s spremembo dednega zapisa, tudi najbolj zapletena bitja prilagoditi okoliščinam. To pomeni, da evolucija rešuje zelo zapletene optimizacijske probleme. Presenetljiva lastnost evolucije je njena preprostost. Postopek iskanja rešitve je moč opisati s tremi osnovnimi opravili: mutacija, selekcija in rekombinacija.

Mutacija dednega zapisa je neusmerjen proces. Njen namen je iskanje alternativ. V jeziku optimizacije je naloga mutacije preseči lokalni minimum.
Rekombinacija, (križanje, angl. Crossover) dednega zapisa ima vlogo iskanja rešitve med mutacijo in selekcijo. V naravi rekombinacija ni nujna (nespolno razmnoževanje), je pa prisotna pri veliki večini vrst.
Selekcija je krmar na poti evolucije. Določa v katero smer se bo spreminjal dedni zapis. Brez motenj, bi bila selekcija deterministična. Vendar se tudi najbolj prilagojeni predstavniki vrste lahko ponesrečijo preden dobijo potomce.

[uredi] Zgodovina

Začetki posnemanja evolucije v optimizacijske namene segajo v šestdeseta leta 20. stoletja. Tako so neodvisno nastali pojmi genetski algoritmi, evolucijsko programiranje in evolucijsko strateški algoritmi. Skupno ime zanje je evolucijski algoritmi. Njihov skupni imenovalec je posnemanje evolucije za iskanje optimalne rešitve problema.

[uredi] Uporaba

Evolucijski algoritmi se uporabljajo za zahtevnejše probleme (nelinearnost, diskontinuiteta in multimodalnost), kjer tradicionalne metode odpovedo. Vzrok za robustnost evolucijskega algoritma je v veliki populaciji rešitev in v odsotnosti predsodkov.

Prednosti in slabosti evolucijskih algoritmov lahko opišemo:

Vzporedno iskanje možne rešitve v celotni populaciji. Tako najdemo več potencialnih rešitev.
Ker je iskanje rešitve »v skokih« oziroma brez gradienta, najde rešitve tudi za nelinearne in diskontinuirane probleme.
Ni potreben superračunalnik. Mnoge druge optimizacije so računalniško bolj zahtevne.
Slabost evolucijskih algoritmov je, da pri mutacijah potrebna sreča za hitro in kvalitetno rešitev.