Geneettinen algoritmi ja sen sovellukset

Abstract

Geneettinen algoritmi on evoluutioalgoritmi, joka käyttää hyväksi evoluutiobiologiasta tuttuja prosesseja. Geneettistä algoritmia käytetään usein optimointimenetelmänä joko suoraan ongelmien ratkaisemiseksi tai toisten algoritmien tukena. Geneettisen algoritmin pitkän historian takia siihen liittyvää kirjallisuutta on paljon, ja sitä on mahdollista tarkastella monesta eri näkökulmasta. Tässä tutkielmassa syvennyn geneettiseen algoritmiin, sekä sen sovellusalueisiin kahden nykypäivän sovelluksiin hyvin oleellisesti liittyvän ongelman kautta. Geneettisen algoritmin rakenne muovautuu hyvin paljon käsillä olevan ongelman mukaan, jonka takia geneettistä algoritmia esitellessäni käytän yksinkertaisen geneettisen algoritmin (simple GA, SGA) rakennetta. Työn tavoite on pyrkiä vastaamaan nykypäivän kirjallisuuden pohjalta, että millaisten ongelmien kanssa geneettistä algoritmia voidaan hyödyntää ja kuinka se käytännössä tapahtuu. Tutkielma on kirjallisuuskatsaus geneettiseen algoritmiin ja sen sovelluksiin ja aineisto koostuu suurimmaksi osaksi tuoreista artikkeleista. Vanhempia artikkeleita käytän pääosin aiheen taustoittamiseen ja käsitteiden määrittelyyn. Tutkielmassa tarkastellaan geneettisen algoritmin soveltamista kauppamatkustajan ongelmaan sekä reppuongelmaan. Kauppamatkustajan ongelmassa keskeiseksi nousi oikean risteytysmenetelmän määrittely, minkä takia tutkielmassa käydään läpi erilaisia tapoja suorittaa risteytys. Reppuongelmassa sovelletaan yksinkertaista geneettistä algoritmia, sekä syvennytään nykypäivän kirjallisuuden avulla erilaisiin tapoihin muokata geneettistä algoritmia kyseisen ongelman ratkaisemisen optimoimiseksi.