Genetisch Programmeren Uitgelegd: Hoe Machines Leren Hun Eigen Code te Schrijven

Misschien is de "Heilige Graal" van de informatica ontdekt de dag dat onze machines hun eigen programma's kunnen schrijven. Genetisch programmeren (GP) is een relatief nieuw machine learning-paradigma dat een stap in die richting vertegenwoordigt.

GP houdt veel beloften in voor het domein van regeltechniek. In dit artikel zullen we bespreken wat genetisch programmeren is, hoe het vertegenwoordigd kan worden, en kijken naar een voorbeeldprogramma.

Dit artikel is de eerste in een serie. Om naar de volgende artikelen te springen, selecteer er een hieronder:

• Genetische Operatoren in Evolutionaire Algoritmen
• Genetische Algoritme Voorbeelden: Een Sorteerprogramma en Symbolische Regressie Evolueren
• Toepassingen en Beperkingen van Genetisch Programmeren

Genetisch Programmeren en Genetische Algoritmen

GP is essentieel een variatie van het genetische algoritme (GA) oorspronkelijk bedacht door John Holland. Net als een GA, is GP een evolutionair algoritme dat vertrouwt op genetische operatoren zoals fitness-proportionele reproductie, crossover, en mutatie om een populatie van gecodeerde programma's, of "individuen", door opeenvolgende generaties te drijven naar een oplossing.

Echter, in tegenstelling tot een GA, dat typisch een fixed-length bit-string encoding gebruikt, gebruikt GP een variabele-grootte, boom-gebaseerde representatie van een echt programma. Daarom levert het resultaat van een succesvolle GP-run een computerprogramma op dat, wanneer gegeven de juiste invoer en uitgevoerd, het gewenste resultaat oplevert.

Nichael Cramer en John Koza worden gecrediteerd voor het leggen van de funderingen van GP. John Koza (die ook een octrooi op GP houdt) heeft een aanzienlijk onderzoek gedaan op GP en zijn werk "Genetic Programming" wordt beschouwd als het standaardwerk over het onderwerp. Huidig onderzoek heeft enkele moedige successen van GP gedemonstreerd in een wijd bereik van toepassingen, inclusief robotnavigatie, spelstrategie-verwerving, symbolische regressie-analyse, en controlsystemen.

Genetisch Programmeren Representatie

De boom-gebaseerde representatie die eerder vermeld werd, is centraal aan het GP-thema omdat vrijwel elk computerprogramma op deze manier vertegenwoordigd kan worden. In de praktijk is een functionele taal zoals LISP goed geschikt voor deze vorm en het is gemakkelijk te zien hoe een LISP S-expressie als een boom kan worden gediagrammeerd (Figuur 1).

Hieronder vindt u drie afzonderlijke representaties van dezelfde informatie:

Een simpel programmafragment:
BEGIN
IF a < b THEN a := a + 1 ELSE b := b * b
c := a * b * 2;

END


LISP equivalent:
(progn (if (a < b)
(setq a (+ a 1))
(setq b (* b b))
)
(setq c (* (* a b) 2))
)

De interne knopen van de boom bestaan uit functies, terwijl de bladknopen uit terminals bestaan. Functies moeten een argumenttelling (gemeenschappelijk aangeduid als ariteit) van minstens één hebben, wat hen laat verbinden met andere functies of terminals, wat de "lijm" voor takken binnen de boom biedt.

Terminals omvatten typisch zaken als constanten en variabelen. Aangezien terminals de bladeren van de boom vormen, hebben ze altijd een ariteit van nul. U bent verplicht de set van functies en terminals te kiezen voor het probleem dat u probeert op te lossen. Bijvoorbeeld, de logische functies AND, OR, en NOT en de terminals X1 en X2, die twee booleaanse invoervariabelen vertegenwoordigen, zijn geschikt als u probeert een programma te ontdekken dat in staat is de XOR-booleaanse functie te synthetiseren. Een fitness-functie is ook vereist aangezien u de middelen moet bieden voor het meten van het ene programma tegen het andere in de zin dat het beter is in het oplossen van een gegeven probleem.

Bijvoorbeeld, in het XOR-geval, kunnen we de fitness van een testen door het programma één keer uit te voeren voor elk fitness-case corresponderend met de vier mogelijke booleaanse invoeren voor X1 en X2 (0 0, 0 1, 1 0, 1 1) en het aantal correcte reacties (0, 1, 1, 0) respectievelijk, voor elke testcase op te tellen.

Onduidelijk, wordt een programma dat een perfecte score van vier haalt, beschouwd als een oplossing voor het XOR-probleem, zoals getoond in Listing 1.

Een perfecte oplossing voor het XOR-probleem ontdekt door GP:
(defun program ()
(AND (OR X1 X2)
(NOT (AND X1 X2) )
)
)

Volgende: Genetische Operatoren

In het volgende artikel zullen we kijken naar de genetische operatoren die evolutionaire algoritmen mogelijk maken. We zullen ze ook gebruiken in een complexer voorbeeldalgoritme.

Aanbevolen Lezing

• Kinnear, Jr., K. E. (ed.). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press, 1994.
• Knuth, D. E. The Art of Computer Programming, Volume 3, Sorting and Searching. Reading, Mass.: Addison-Wesley, 1973
• Koza, J. R. Genetic Programming. Cambridge, Mass.: The MIT Press, 1992.
• Koza, J. R. Genetic Programming II. Cambridge, Mass.: The MIT Press, 1994.
• Montana, D. J. "Strongly Typed Genetic Programming." BBN Technical Report #7866, May 1993.
• Mitchell, Melanie, An Introduction to Genetic Algorithms, The MIT Press, 1998.