Geneettiset algoritmit
Geneettinen algoritmi (GA) on evoluutiolaskentaan kuuluva heuristinen optimointimenetelmä, jolla pyritään löytämään globaalinen optimi suuresta hakuavaruudesta.
Geneettiset algoritmit pyrkivät matkimaan luonnon evoluutiomekanismeja, joita kuvataan seuraavilla keskeisillä käsitteillä:
- Evoluutio toimii kromosomeissa, jotka muodostuvat vaihtoehtojen rakenteita kuvaavan koodausmekanismin kautta.
- Luonnollinen valinta on linkki kromosomien ja niistä seuraavien ilmenemismuotojen (dekoodattujen rakenteiden) hyvyyden välille. Menestyksekkäät rakenteet uusiutuvat useammin kuin huonosti sopivat rakenteet.
- Uusiutuminen perustuu mutaatioihin ja risteytyksiin. Risteytyksessä muodostuu kokonaan uudenlaisia kromosomeja. Mutaatio tuottaa satunnaisia muutoksia estämään juuttumista paikallisiin ratkaisuihin..
- Populaatio sisältää tarkastelussa olevat vaihtoehtoiset ratkaisut. Populaation tulee olla riittävä vaihtoehtojen erilaisuuksien esittämiseen optimoinnissa, mutta ei laskentaa hidastavan laaja. Populaatio muuttuu laskennan aikana. Parhaiten ratkaisujen mukana pitämiseksi tarvitaan elitismiä, sillä biologisella evoluutiolla ei ole muistia. .
Ratkaisumekanismi ei tiedä ratkaistavasta ongelmasta mitään. Koodausmekanismi ja erilaisten ratkaisuvaihtoehtojen hyvyyden arviointi. kytkevät ratkaisun ongelmaan. Rakennuspalikkahypoteesissa: hyvät parametrivektorit sisältävät osaratkaisuja, joita yhdistämällä on mahdollista löytää vielä parempia ratkaisuja. Menetelmä kykenee ratkaisemaan hyvin monimutkaisia ongelmia erittäin laajoissa hakuavaruuksissa.:
Ruokalistaan voidaan poimia mukaan useampia hyviä GA:n jalostamia vaihtoehtoja.