Genetisk programmering

Genetisk programmering är en teknik där maskiner kan programmera sig själva genom en form av trial and error. Metoden används till exempel för programmering av artificiell intelligens i robotar och datorer, bildtolkning samt för att hitta mönster i stora datamängder (informationsutvinning).

Metod

Genetisk programmering är inspirerad av den biologiska evolutionen. Målet med metoden är att automatiskt generera en eller flera programsnuttar, algoritmer, som löser ett väl definierat problem så bra som möjligt. Problemet kan till exempel bestå i att lära en robothund att gå. Algoritmens förmåga att lösa problemet beräknas med hjälp av en fitness-funktion.

Processen som genererar algoritmer, träningen, baseras på att man låter en eller flera populationer av algoritmer utvecklas över flera generationer. Varje generation består av ett antal algoritmer, individer, med olika god förmåga att lösa det aktuella problemet. En efterföljande generation skapas genom att man väljer och kombinerar individer från den nuvarande generationen baserat på deras fitness. Individer med högre fitness, dvs en bättre algoritm, har större sannolikhet att väljas ut som föräldrar för skapandet av nästa generation.

För att bättre individer ska skapas applicerar metoden genetiska operatorer på de utvalda föräldrarna. De vanligaste operatorerna är sexuell reproduktion, där två föräldrar kombineras till ett eller flera barn, mutation, där en förälder förändras slumpmässigt, samt asexuell reproduktion, där en förälder förs vidare oförändrad till den efterföljande generationen. På detta vis förs god arvsmassa, källkod, vidare genom generationerna medan dålig sådan dör ut. De bästa individerna i respektive generation blir med tiden bättre på att lösa det givna problemet.

Metoden är en stokastisk process som använder slumptal flitigt. Den initiala populationen består ofta av slumpmässigt genererade individer, valet av genetisk operator är slumpmässigt och de flesta operatorer innefattar i sig själva slumpmässiga element. Metoden avslutas typiskt efter att en på förhand angiven fitness har uppnåtts, ett angivet antal generationer har passerat eller att ett angivet antal generationer har passerat utan vidare förbättring.

Exempel

Ett exempel på applikation är att lära en robothund att gå. Roboten har en sensor som registrerar huruvida robothunden rör sig i den tänkta färdriktningen.

Den första generationen innehåller individer som i bästa fall får hunden att sprattla okontrollerbart med benen. I denna generation är dock några individer bättre än andra och får sannolikt föra sin arvsmassa vidare. Efter några generationer så lyckas en algoritm att få hunden att röra sig en obetydlig sträcka i den tänka färdriktningen, dock inte nödvändigtvis med ett effektivt gångmönster. Detta registreras av sensorn som positivt, vilket ger individen högre fitness och ökar dess sannolikhet att bli förälder. Över flera generationer lär sig hunden att förflytta sig längre och effektivare.

Ett experiment liknande exemplet genomfördes på Chalmers. Efter 21 timmar hittade roboten ett effektivt rörelsemönster för att förflytta sig ^[1].

Genetisk algoritm

Genetiska algoritmer är en metod som i allt väsentligt liknar genetisk programmering, förutom att man genererar datasekvenser istället för algoritmer. Ett exempel är att lösa handelsresandeproblemet genom att låta varje individ representeras av en serie siffror, där varje siffra representerar en stad att besöka. Fitness-funktionen kan här till exempel vara inversen av resans totala sträcka.

Referenser

Noter

Källor

• Goldberg, D. E. Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley, New York, 1989.
• Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, freely available via Lulu.com.

Externa länkar

• Flash-applikation som genererar ett fordon med hjälp av genetiska algoritmer.