Toepassingen en beperkingen van genetische algoritmen

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

Hier zullen we op hoog niveau bekijken wat deze technologie kan bereiken terwijl deze zich ontwikkelt.

Praktische overwegingen bij genetische programmering

Laten we, om dit laatste hoofdstuk van onze serie te begrijpen, een XOR-voorbeeld onthouden dat we in het eerste deel van deze serie hebben besproken:

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

Lijst 1. XOR-resultaat.

Laten we ook nog eens terugkijken naar het symbolische regressievoorbeeld uit het vorige artikel:

Een polynoombenadering van sin(x) in het interval (0 <=x <=pi/2) (defun programma () (+ (* (* (* X X) X) (* 0.2283 -0.6535)) X) ) Vereenvoudiging van het bovenstaande programma levert de volgende equivalente vergelijking op:polysin(x) =-.1492 x
3
 + x Resultaten:

Lijst 4. Symbolische regressie.

Merk op dat zowel de XOR- als de symbolische regressievoorbeelden die hier worden gepresenteerd een enkele waarde retourneren bij evaluatie.

Dit kenmerk hoeft geen beperking te zijn, aangezien het zeker mogelijk is dat een functie of terminal een bijwerking heeft wanneer deze wordt uitgevoerd. Dit is vaak het geval voor het sorteerprogramma, dat een functie bevat met het mogelijke neveneffect van het uitwisselen van een paar elementen in een vector. In de praktijk komt het vaak voor dat er bijwerkingen optreden. Enkele aanvullende voorbeelden van nuttige bijwerkingen zijn het toewijzen van de ene variabele aan de andere of het veranderen van de richting waarin een robot kijkt.

Onze functieset kan voorwaardelijke functies bevatten die de ontwikkelde programma's de mogelijkheid bieden om beslissingen te nemen. Voorwaardelijke functies evalueren selectief hun argumenten. Beschouw als voorbeeld 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, wordt het tweede argument geëvalueerd; anders wordt het derde argument geëvalueerd. Iteratieve constructies zijn ook mogelijk, omdat een functie een van zijn argumenten meerdere keren kan evalueren. Extra complexiteit wordt echter geïntroduceerd door de noodzaak om het aantal iteraties en het nestingniveau te beperken om een ​​situatie te vermijden waarin de evaluatie van een individu te lang kan duren. Er is enig werk gedaan om recursieve formuleringen mogelijk te maken, hoewel het succes op dit gebied enigszins beperkt is.

Hoewel de resultaten van GP-systemen meestal LISP-achtige programma's zijn, hoeft een GP-systeem niet in LISP te worden geïmplementeerd. Veel systemen zijn geïmplementeerd in C of C++. Een gelineariseerde weergave van de programmaboom kan worden gebruikt en de overhead van dynamisch geheugen samen met dure afvalverzameling kan worden vermeden. De efficiëntie van de fitnessfunctie verdient speciale aandacht, omdat het vaak een knelpunt is vanwege het grote aantal keren dat het tijdens elke generatie wordt ingeroepen. Een uitstekend artikel waarin verschillende implementatietechnieken worden besproken, is te vinden in Advances in Genetic Programming (geciteerd in het gedeelte Aanbevolen literatuur hieronder).

Net als in andere paradigma's voor machine learning, zoals neurale netwerken, bestaat het potentieel om de trainingsgegevens (GP-testgevallen) te overfitten. Overfitting kan optreden wanneer de oplossing de gegevens effectief "onthoudt", en dus weinig meer biedt dan een uitgebreide opzoektabel. Een eenvoudige manier om dit effect te verminderen, is door een spaarzaamheidsfactor te gebruiken. Een spaarfactor is typisch een kleine fractie vermenigvuldigd met het aantal knooppunten in de programmaboom, waarvan het resultaat wordt opgenomen in de fitnessfunctie. Het idee is om kleinere, vermoedelijk meer algemene oplossingen te belonen. Daarnaast wordt u aangemoedigd om geschikte experimentele ontwerptechnieken te gebruiken. Als u bijvoorbeeld probeert een model voor voorspelling te ontwikkelen, is het een goed idee om de fitnessevaluatie te beperken tot een subset van de beschikbare gegevens. Op deze manier kunnen de resterende gegevens 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 voortijdig naar een lokaal minima. Prestaties zijn sterk afhankelijk van de complexiteit van het probleem, de representatie ervan zoals gekenmerkt door de keuze van functies en terminals, en de eigenschappen van de fitnessfunctie.

Toepassingen voor genetische programmering

Genetische programmering is met succes toegepast op problemen die zich voordoen op gebieden als:

• Circuitontwerp
• Combinatorische optimalisatie
• Besturingssystemen
• Curvefitting/regressieanalyse
• Gegevenscompressie
• Economische prognoses/financiële modellering
• Acquisitie van gamestrategie
• Wiskundige rij-inductie
• Neuraal netwerkontwerp
• Patroonherkenning en classificatie
• Willekeurige nummergeneratie
• Robotnavigatie
• Symbolische integratie en differentiatie
• Driedimensionaal ontwerp

Toekomstige aanwijzingen voor genetische programmering

Afhankelijk van de complexiteit van het probleem, kunnen meerdere GP-runs nodig zijn om een ​​acceptabele oplossing te vinden, als die al kan worden gevonden. Idealiter zouden we graag zien dat GP "opschaalt" naarmate de complexiteit van het probleem toeneemt. Het vinden van goede manieren om dit doel te bereiken is een actief onderzoeksgebied. Net als bij conventioneel programmeren, is het idee om representaties op een hoger niveau te bouwen door middel van subroutines een manier om dit probleem aan te pakken. In Genetische programmering II , bespreekt Koza methoden die herbruikbare subroutines kunnen ontdekken en presenteert resultaten die het vermogen van hiërarchische, modulaire programma's ondersteunen om complexere problemen op te lossen.

Zoals we hebben gezien, koppelt GP de zelforganiserende kenmerken van het genetische algoritme aan de representatieve kracht en algemeenheid van S-expressies. De elegantie van deze benadering vereenvoudigt de probleemspecificatie tot het verschaffen van een domeinspecifieke fitnessfunctie en een geschikte functie- en terminalset. De huisarts is toepasbaar op een breed scala aan problemen en blijft een vruchtbare voedingsbodem voor onderzoek.

Nog in de kinderschoenen, kunnen toekomstige doorbraken ons een stap verder brengen naar die heilige graal van systemen die in staat zijn om hun eigen programma's te schrijven.

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.