Geneettinen algoritmi

Abstract

Tässä opinnäytetyössä selvitetään uusinta ajatusmallia edustavaa ja suurta suosiota saavuttanutta optimointimenetelmää. Kyseessä on geneettinen algoritmi, jonka esikuva on genetiikka ja luonnossa tapahtuva evoluutio. Selvitystyössä esitetään yksityiskohtaisesti proseduurin toimintaperiaate ja muutama sovellusongelma, johon menetelmä on käytännöllinen. Geneettinen algoritmi perustuu darwinistiseen ajatteluun, ja se jäljittelee luonnossa tapahtuvan evoluution mekanismeja. Näitä mekanismeja ovat mm. yksilöiden valinta, risteytys ja mutaatio. Algoritmi on yleensä viritetty siten, että evoluutio on hyvin nopeaa ja pyrkii kehitykseen. Kehitys ilmenee ns. rakennuspalikkahypoteesina; kun yhdistellään hyviä osaratkaisuja, saadaan vieläkin parempia osaratkaisuja. Hypoteesia toistettaessa riittävän pitkään löydetään lopulta tarpeeksi hyvä loppuratkaisu. Menetelmä on varsin tehokas vaikeisiin optimointitehtäviin, jotka sisältävät paljon parametreja ja vähän tietoa. Geneettinen algoritmi on helppo hajauttaa, joten laskentateho voidaan jakaa usealle prosessorille. Menetelmää sovelletaan jatkuvasti yhä enemmän, ja se on onnistunut täyttämään tehtävänsä usealla eri alalla. Kun algoritmin osat on rakennettu hyvin, se on yksinkertainen, joustava, ja eikä se ajaudu lähimpään lokaaliin osaratkaisuun.

In this thesis an optimization method that represents the newest paradigm, which has gathered a lot of popularity, was studied. The optimization method is Genetic Algorithm, a paragon of genetics and nature’s evolution. In the report a detailed principle of the procedure was introduced. A few application problems which the algorithm can be applied to were presented. The Genetic Algorithm is based on a darwinistic perspective and it simulates mechanisms of evolution in nature. These mechanisms are, among other things, the selection of individuals, crossover, and mutation. Usually the algorithm is tuned in such a way that evolution is very rapid and aspires to development. The development appears as the socalled building block hypothesis; as a result of combining good partial solutions even better partial solutions are produced. When the hypothesis is repeated sufficiently, a fit enough final solution is found. The method is very effective for difficult optimization tasks, which contain many parameters and little information. The Genetic Algorithm is easy to decentralize in order to share computing power with many processors. The method is adapted increasingly, and it has fullfilled its position in many fields. When the parts of the algorithm are well-engineered, it is simple, flexible and will not be confined to the nearest local partial solution.