De kracht en grenzen van genetische algoritmen verkennen

Op dit punt in de genetische programmering (GP) serie, hebben we geleerd wat genetische programmering is en hoe het informatie vertegenwoordigt, hoe genetische operatoren werken in evolutionaire algoritmen, en een sorteringsprogramma ontwikkeld door symbolische regressie.

Hier zullen we een hoog-niveau kijk nemen naar wat deze technologie kan bereiken naarmate het zich ontwikkelt.

Praktische Overwegingen van Genetische Programmering

Om dit laatste hoofdstuk van onze serie te begrijpen, laten we ons herinneren aan een XOR voorbeeld dat we in het eerste deel van deze serie bespraken:

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

Laten we ook terugkijken naar het symbolische regressie voorbeeld uit het vorige artikel:

Een polynomiale benadering van sin(x) in het interval (0 <= x <= pi/2)

(defun program ()
  (+ (* (* (* X X) X)
  (* 0.2283 -0.6535))
  X)
)

Vereenvoudiging van het bovenstaande programma levert de volgende equivalente vergelijking op:

polysin(x) = -.1492 x3 + x

Resultaten:

Let op dat zowel het XOR- als het symbolische regressie voorbeeld hier gepresenteerd een enkele waarde retourneren wanneer geëvalueerd.

Deze karakteristiek hoeft geen beperking te zijn, aangezien het zeker mogelijk is voor een functie of terminal een neveneffect te hebben wanneer uitgevoerd. Dit is vaak het geval voor het sorteringsprogramma, dat een functie bevat met het potentieel neveneffect van het uitwisselen van een paar elementen in een vector. In de praktijk is het gebruikelijk dat neveneffecten aanwezig zijn. Enkele additionele voorbeelden van nuttige neveneffecten zijn het toewijzen van de ene variabele aan de andere of het veranderen van de richting waarin een robot kijkt.

Onze functieset mag conditionele functies bevatten die de geëvolueerde programma's de mogelijkheid geven om beslissingen te nemen. Conditionele functies evalueren hun argumenten selectief. Als voorbeeld, overweeg een functie, met een ariteit van drie, zoals (if arg1 arg2 arg3). De functie wordt geëvalueerd door het eerste argument te evalueren en als het resultaat waar is, het tweede argument te evalueren; anders wordt het derde argument geëvalueerd. Iteratieve constructies zijn ook mogelijk, aangezien een functie een van zijn argumenten meerdere keren kan evalueren. Additionele complexiteit wordt geïntroduceerd, echter, door de noodzaak om het aantal iteraties en nestingsniveau te beperken om een situatie te vermijden waar de evaluatie van een individu excessief lang kan duren. Er is werk gedaan om recursieve formuleringen toe te staan, hoewel de succes in dit gebied enigszins beperkt is gebleven.

Hoewel de resultaten van GP-systemen neigen tot LISP-achtige programma's, hoeft een GP-systeem niet in LISP geïmplementeerd te zijn. Veel systemen zijn geïmplementeerd in C of C++. Een gelineariseerde vertegenwoordiging van de programbome kan worden gebruikt en de overhead van dynamisch geheugen samen met dure garbage collection kan worden vermeden. De efficiëntie van de fitnessfunctie verdient speciale aandacht omdat het vaak een knelpunt is door het grote aantal keren dat het tijdens elke generatie wordt aangeroepen. Een uitstekend papier dat verschillende implementatietechnieken bespreekt, kan worden gevonden in Advances in Genetic Programming (gciteerd in de Aanbevolen Lezing sectie hieronder).

Zoals in andere machine-learning paradigma's, zoals neurale netwerken, bestaat de potentie om de trainingsdata (GP testcases) te overfitten. Overfitting kan optreden wanneer de oplossing effectief de data "onthoudt", wat weinig meer dan een uitgebreide lookup-tabel oplevert. Een eenvoudige manier om dit effect te beperken is door het gebruik van een zuinigheidsfactor. Een zuinigheidsfactor is typisch een kleine fractie vermenigvuldigd met het aantal knopen binnen de programbome, het resultaat waarvan in de fitnessfunctie wordt geïncorporeerd. Het idee is om kleinere, waarschijnlijk meer algemene oplossingen te belonen. Daarnaast wordt u aangemoedigd om geschikte experimentele ontwerptechnieken te gebruiken. Bijvoorbeeld, als u probeert een model voor voorspelling te ontwikkelen, is het een goed idee om de fitness-evaluatie te beperken tot een subset van de beschikbare data. Op deze manier kan de overige data de voorspellende prestaties van het resulterende model meten.

Zoals het geval is met evolutionaire algoritmen, biedt GP geen garantie voor het vinden van een exacte oplossing of zelfs een acceptabele oplossing. Resultaten kunnen sterk variëren van de ene run naar de andere. Vaak convergeert het proces te vroeg op een lokaal minimum. Prestaties zijn zeer afhankelijk van de complexiteit van het probleem, zijn vertegenwoordiging gekenmerkt door de keuze van functies en terminalen, en de eigenschappen van de fitnessfunctie.

Toepassingen voor Genetische Programmering

Genetische programmering is met succes toegepast op problemen die voorkomen in dergelijke gebieden als:

• Schakelingontwerp
• Combinatorische optimalisatie
• Regelsystemen
• Curve fitting/regressieanalyse
• Datacompressie
• Economische voorspelling/financiële modellering
• Spelstrategie verwerving
• Wiskundige rij inductie
• Neurale netwerk ontwerp
• Patroonherkenning en classificatie
• Willekeurige getal generatie
• Robotnavigatie
• Symbolische integratie en differentiatie
• Driedimensionaal ontwerp

Toekomstige Richtingen voor Genetische Programmering

Afhankelijk van de complexiteit van het probleem, kunnen meerdere GP-runs vereist zijn om een acceptabele oplossing te vinden, als er überhaupt een gevonden kan worden. Ideaal zouden we willen dat GP "opschaalt" naarmate de complexiteit van het probleem toeneemt. Goede manieren om dit doel te bereiken vinden is een actief onderzoeksgebied. Zoals in conventionele programmering, is het concept van het bouwen van hogere-niveau vertegenwoordigingen door subroutines een manier om dit probleem aan te pakken. In Genetic Programming II, bespreekt Koza methoden die herbruikbare subroutines kunnen ontdekken en presenteert resultaten die de capaciteit van hiërarchische, modulaire programma's steunen om complexere problemen op te lossen.

Zoals we hebben gezien, koppelt GP de zelf-organiserende kenmerken van het genetisch algoritme met de vertegenwoordigingskracht en generaliteit van S-expressies. De elegantie van deze benadering vereenvoudigt probleemspecificatie tot het leveren van een domeinspecifieke fitnessfunctie en een geschikte functie- en terminalenset. Toepasbaar op een diverse reeks problemen, blijft GP een vruchtbare grond voor onderzoek.

Nog in de kinderschoenen, kunnen toekomstige doorbraken ons een stap dichter brengen bij die Heilige Graal van systemen die in staat zijn hun eigen programma's te schrijven.

Aanbevolen Lezing

• Kinnear, Jr., K. E. (red.). 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 Technisch Rapport #7866, Mei 1993.
• Mitchell, Melanie, An Introduction to Genetic Algorithms, The MIT Press, 1998.