Een inleiding tot genetische programmering:een systeem dat zichzelf programmeert?

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

GP is veelbelovend op het gebied van regeltechniek. In dit artikel bespreken we wat genetische programmering is, hoe het kan worden weergegeven en bekijken we een voorbeeldprogramma.

Dit artikel is het eerste in een reeks. Selecteer er een hieronder om naar de volgende items te gaan:

• Genetische operatoren in evolutionaire algoritmen
• Voorbeelden van genetische algoritmen:een sorteerprogramma ontwikkelen en symbolische regressie
• Toepassingen en beperkingen van genetische programmering

Genetische programmering en genetische algoritmen

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

In tegenstelling tot een GA, die doorgaans een bitstringcodering met een vaste lengte gebruikt, gebruikt GP echter een boomgebaseerde representatie van een daadwerkelijk programma met variabele grootte. Daarom levert het resultaat van een succesvolle GP-run een computerprogramma op dat, wanneer het op de juiste manier wordt ingevoerd en uitgevoerd, het gewenste resultaat oplevert.

Nichael Cramer en John Koza worden gecrediteerd voor het leggen van de basis voor GP. John Koza (die ook een patent op GP heeft) heeft een aanzienlijke hoeveelheid onderzoek gedaan naar GP en zijn baanbrekende boek, "Genetic Programming", wordt beschouwd als het baanbrekende werk over dit onderwerp. Huidig ​​onderzoek heeft enkele bemoedigende successen van GP aangetoond in een breed scala aan toepassingen, waaronder robotnavigatie, acquisitie van gamestrategieën, symbolische regressieanalyse en besturingssystemen.

Representatie van genetische programmering

De eerder genoemde boomgebaseerde weergave staat centraal in het GP-thema, aangezien vrijwel elk computerprogramma op deze manier kan worden weergegeven. In de praktijk is een functionele taal zoals LISP zeer geschikt voor deze vorm en het is gemakkelijk in te zien hoe een LISP S-expressie als een boomdiagram kan worden weergegeven (Figuur 1).

Hieronder vindt u drie afzonderlijke weergaven van dezelfde informatie:

Een eenvoudig programmafragment: BEGINNEN IF a LISP-equivalent: (progn (als (a  

 
 

 
 
Figuur 1. Boomweergave van een programma. Merk op dat (progn arg1 arg2 arg3 ... argn) elk argument sequentieel evalueert.  
 

 
 

 De interne knooppunten van de boom bestaan ​​uit functies, terwijl de bladknooppunten uit terminals bestaan. Functies moeten een aantal argumenten hebben (gewoonlijk arity genoemd) van ten minste één, zodat ze kunnen worden verbonden met andere functies of terminals, waardoor de "lijm" voor takken in de boom wordt verschaft.
 

 Terminals bevatten doorgaans zaken als constanten en variabelen. Omdat terminals de bladeren van de boom vormen, hebben ze altijd een ariteit van nul. U moet de set functies en aansluitingen kiezen voor het probleem dat u probeert op te lossen. De logische functies AND, OR en NOT en de klemmen X1 en X2, die twee booleaanse invoervariabelen vertegenwoordigen, zijn bijvoorbeeld geschikt als u probeert een programma te ontdekken dat in staat is de booleaanse functie XOR te synthetiseren. Een fitnessfunctie is ook vereist, omdat je de middelen moet bieden om het ene programma te vergelijken met het andere, in die zin dat men beter is in het oplossen van een bepaald probleem.
 

 In het XOR-geval kunnen we bijvoorbeeld de geschiktheid van een programma testen door het programma één keer uit te voeren voor elk geschiktheidsgeval dat overeenkomt met de vier mogelijke booleaanse invoer voor X1 en X2 (0 0, 0 1, 1 0, 1 1) en het optellen van het aantal juiste antwoorden (0, 1, 1, 0), respectievelijk voor elke testcase. 
 

 Het is duidelijk dat een programma dat een perfecte score van vier oplevert, wordt beschouwd als een oplossing voor het XOR-probleem, zoals weergegeven in lijst 1.
 

 
 
Een perfecte oplossing voor het XOR-probleem ontdekt door GP: (defun programma () (EN (OF X1 X2) (NIET (EN X1 X2)) ) ) 
 
Lijst 1.  XOR-resultaat 
 

 
 
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.
 

 
 
Voorgestelde lezing
 
 
Kinnear, Jr., K.E. (red.). Vooruitgang in genetische programmering . Cambridge, Massachusetts:The MIT Press, 1994.
 
Knuth, D.E. De kunst van computerprogrammeren, deel 3, sorteren en zoeken . Reading, Mass.:Addison-Wesley, 1973
 
Koza, J.R. Genetische programmering . Cambridge, Massachusetts:The MIT Press, 1992.
 
Koza, J.R. Genetische programmering II . Cambridge, Massachusetts:The MIT Press, 1994.
 
Montana, D.J. "Sterk getypeerde genetische programmering." BBN technisch rapport #7866, mei 1993.
 
Mitchell, Melanie, Een inleiding tot genetische algoritmen , The MIT Press, 1998.