Geneettinen ohjelmointi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24. lokakuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Koneoppimisessa geneettinen ohjelmointi (GP) on ohjelmien automaattista luomista tai muokkaamista geneettisten algoritmien avulla . Tämän metodologian avulla ”kasvatetaan” ohjelmia, jotka ovat yhä parempia (tietyn kromosomien kuntofunktion mukaisesti) ratkaisemaan asetetun laskennallisen ongelman.

Historia

Koodausalgoritmi

Valinta, kuinka ohjelma koodataan geneettisessä algoritmissa, on yksi geneettisen ohjelmoinnin pääkysymyksistä. Ohjelma tulee koodata siten, että siinä on helppo tehdä satunnaisia ​​muutoksia automaattisesti (mutaatiooperaattori) ja yhdistää kaksi algoritmia yhdeksi (crossover-operaattori).

Koodausmenetelmät voidaan jakaa kahteen luokkaan:

Hermoverkot

Treelike

Puukoodauksessa jokainen puusolmu sisältää funktion ja jokainen lehti operandin. Puuna esitetty lauseke voidaan helposti arvioida rekursiivisesti. Perinteisiä GPU:ita on helpompi käyttää ohjelmien kasvattamiseen, jotka on kirjoitettu kielillä, jotka luonnollisesti ilmentävät puurakennetta: Lisp , Haskell , F# ja muut toiminnalliset ohjelmointikielet.

On myös ehdotettu ja onnistuneesti toteutettu ohjelmien ei-puuesityksiä, kuten perinteisille imperatiivisille kielille sopiva lineaarinen geneettinen ohjelmointi.

Crossover-operaattori

Puuesityksessä crossover-operaattori toteutetaan vaihtamalla kahden puun välillä mikä tahansa solmu yhdessä niiden jälkeläisten (alipuiden) kanssa.

Esimerkki:

yksilöllinen . Lapset [ randomChildIndex ] = muu Yksilö . Lapset [ randomChildIndex ] ; Mutaatiooperaattori

Toisin kuin crossover-operaattori, mutaatiooperaattori vaikuttaa vain yhteen kromosomiin. Puunäkymässä se voidaan toteuttaa muuttamalla solmun tietoja tai lisäämällä/poistamalla solmu tai koko alipuu. Tässä tapauksessa on tarpeen seurata operaattorin tulosten oikeellisuutta.

Esimerkki:

yksilöllinen . Tiedot = satunnainenTiedot ();

tai

yksilö = generoiUusiYksilö ();

Metageneettinen ohjelmointi

Metageneettinen ohjelmointi on GP, ​​jossa paitsi tiettyä tietokoneohjelmaa muutetaan ja sitä kautta "kasvatetaan", vaan myös itse sovelletut risteytys- ja mutaatiooperaattorit.

Linkit

Kirjallisuus

  • Banzhaf, W., Nordin, P., Keller, RE, Francone, FD (1997), Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programmes and its Applications , Morgan Kaufmann
  • Cramer, Nichael Lynn (1985), " Edustus yksinkertaisten peräkkäisten ohjelmien mukautuvalle sukupolvelle " julkaisussa Proceedings of an International Conference on Genetic Algorithms and the Applications , Grefenstette, John J. (toim.), CMU
  • Koza, JR (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programmes to Solve Problems , Stanfordin yliopiston tietojenkäsittelytieteen osaston tekninen raportti STAN-CS-90-1314 . Perusteellinen raportti, jota mahdollisesti käytetään luonnoksena hänen vuoden 1992 kirjaansa.
  • Koza, JR (1992), Genetic Programming: On the Programming of Computers Means of Natural Selection , MIT Press
  • Koza, JR (1994), Genetic Programming II: Automatic Discovery of Reusable Programs , MIT Press
  • Koza, JR, Bennett, FH, Andre, D. ja Keane, MA (1999), Genetic Programming III: Darwinian Invention and Problem Solving , Morgan Kaufmann
  • Koza, JR, Keane, MA, Streeter, MJ, Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Rutine Human-Competitive Machine Intelligence , Kluwer Academic Publishers
  • Langdon, WB, Poli, R. (2002), Geneettisen ohjelmoinnin perusteet, Springer-Verlag
  • Poli, R., Langdon, WB, McPhee, NF (2008), A Field Guide to Genetic Programming , Lulu.com, vapaasti saatavilla Internetistä ISBN 978-1-4092-0073-4
  • Smith, SF (1980), A Learning System Based on Genetic Adaptive Algorithms , PhD-väitöskirja ( Pittsburghin yliopisto )
  • Sopov E.A. (2004), Evoluutioalgoritmit monimutkaisten järjestelmien mallintamiseen ja optimointiin, väitöskirja teknisten tieteiden kandidaatin tutkintoa varten, Krasnojarsk

.