S-114.240 Laskennallisen tekniikan seminaari

Evoluutiolaskenta ja keinoelämä


JOHDATUS EVOLUUTIOLASKENTAAN JA GENEETTISIIN ALGORITMEIHIN



Pekka Simula, Teknillinen korkeakoulu

sposti: psimula@cc.hut.fi




Sisällys:

1. Johdanto

2. Evoluutiolaskennan taustaa

    2.1 Yksilön ja populaation kuvaus

    2.2 Evoluution kuvauksen perusfunktiot

      2.2.1 Epigenesis

      2.2.2 Luonnonvalinta

      2.2.3 Genotyyppien selviytyminen

      2.2.4 Mutaatio

3. Evoluutiolaskennan soveltaminen ongelmanratkaisuun

    3.1 Evoluutiolaskennan vaikeuksia

      3.1.1 Lokaalit optimit

      3.1.2 Genotyyppien luonteen merkitys

      3.1.3 Luonnon evoluution herättämiä kysymyksiä

4. Geneettiset algoritmit

    4.1 Yksinkertainen geneettinen algoritmi

5. GA:n kehittyneempiä ajatuksia

    5.1 Ongelman kuvaus

    5.2 Heikoimpien yksilöiden karsiminen

    5.3 Populaatioiden koko ja määrä

    5.4 Algoritmin sopeuttaminen

    5.4.1 Operaattorien todennäköisyyksien optimoiminen

    5.4.2 Parametrien dynaaminen koodaus

    5.5 GA:n soveltamisesta

6. Esimerkki: GA:n soveltaminen Bin Packing -ongelmaan

    6.1 Ratkaisuavaruuden kuvaus genomeina

    6.2 Alkupopulaation luominen

    6.3 Geneettiset operaatiot

    6.4 Algoritmin kulku

    6.5 Tulokset

7. Yhteenveto

8. Lähdeluettelo