Genetikai programozás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. október 24-én felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A gépi tanulásban a genetikai programozás (GP) a programok automatikus létrehozása vagy módosítása genetikai algoritmusok segítségével . Ennek a módszernek a segítségével olyan programokat „nőnek ki”, amelyek egyre jobban (egy kromoszómára vonatkozó fitnesz függvénynek megfelelően) megoldják a beállított számítási problémát.

Történelem

Kódolási algoritmus

Egy program genetikai algoritmusban való kódolásának megválasztása a genetikai programozás egyik fő kérdése. A programot úgy kell kódolni, hogy könnyen lehessen véletlenszerű változtatásokat végrehajtani (mutációs operátor) és két algoritmust egyesíteni (crossover operátor).

A kódolási módszerek két csoportra oszthatók:

Neurális hálózatok

Treelike

A fa kódolásánál minden fa csomópont tartalmaz egy függvényt, és minden levél egy operandust. A faként ábrázolt kifejezés könnyen rekurzív módon kiértékelhető. A hagyományos GPU-k könnyebben használhatók olyan nyelveken írt programok fejlesztéséhez, amelyek természetesen fastruktúrát testesítenek meg: Lisp , Haskell , F# és más funkcionális programozási nyelvek.

A programok nem faábrázolásait is javasolták és sikeresen implementálták, például a hagyományos imperatív nyelvekhez alkalmas lineáris genetikai programozást.

Crossover operátor

Egy faábrázolásban a keresztezési operátort két fa közötti cserével valósítják meg bármely csomópont, azok leszármazottaival (részfáival) együtt.

Példa:

egyéni . Gyermekek [ randomChildIndex ] = egyéb Egyén . Gyermekek [ randomChildIndex ] ; Mutációs operátor

A crossover operátorral ellentétben a mutációs operátor csak egy kromoszómát érint. Fanézetben egy csomópont információinak megváltoztatásával, vagy egy csomópont vagy egy teljes részfa hozzáadásával/eltávolításával valósítható meg. Ebben az esetben ellenőrizni kell az üzemeltető eredményeinek helyességét.

Példa:

egyéni . Információ = randomInformation ();

vagy

egyéni = generálNewIndividual ();

Metagenetikus programozás

A metagenetikus programozás olyan háziorvos, amelyben nem csak egy adott számítógépes programot változtatnak meg, és így "nőnek", hanem magukat az alkalmazott keresztezési és mutációs operátorokat is.

Linkek

Irodalom

  • Banzhaf, W., Nordin, P., Keller, RE, Francone, FD (1997), Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and its Applications , Morgan Kaufmann
  • Cramer, Nichael Lynn (1985), " A reprezentáció az egyszerű szekvenciális programok adaptív generálásához " in Proceedings of an International Conference on Genetic Algorithms and the Applications , Grefenstette, John J. (szerk.), CMU
  • Koza, JR (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems , Stanford University Computer Science Department technikai jelentés STAN-CS-90-1314 . Egy alapos jelentés, amelyet valószínűleg 1992-es könyvének piszkozataként használnak.
  • 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. és Keane, MA (1999), Genetic Programming III: Darwini Invention and Problem Solving , Morgan Kaufmann
  • Koza, JR, Keane, MA, Streeter, MJ, Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Rutinine Human-Competitive Machine Intelligence , Kluwer Academic Publishers
  • Langdon, WB, Poli, R. (2002), Foundations of Genetic Programming , Springer-Verlag
  • Poli, R., Langdon, WB, McPhee, NF (2008), A Field Guide to Genetic Programming , Lulu.com, szabadon elérhető az internetről ISBN 978-1-4092-0073-4
  • Smith, SF (1980), Genetikai adaptív algoritmusokon alapuló tanulási rendszer , PhD disszertáció ( Pittsburghi Egyetem )
  • Sopov E.A. (2004), Evolúciós algoritmusok komplex rendszerek modellezésére és optimalizálására, értekezés a műszaki tudományok kandidátusáért, Krasznojarszk

.