Genetisch algoritme

Wat is het

Natuurlijke evolutie kan worden gemodelleerd als een spel, waarin de beloningen voor een organisme dat een goed levensspel speelt bestaan uit het doorgeven van zijn genetisch materiaal aan zijn opvolgers en zijn voortdurende overleving. ^[2] In natuurlijke evolutie hangt hoe goed een individu presteert af van met wie het samenwerkt en met wie het concurreert, en van de omgeving. Genetische algoritmen zijn een simulatie van natuurlijke selectie op een populatie van kandidaat-oplossingen voor een optimalisatieprobleem (chromosomen, individuen, wezens, of fenotypen).

Kandidaten worden geëvalueerd en gekruist in een poging om goede oplossingen te maken. Dergelijke oplossingen kunnen veel tijd in beslag nemen en zijn voor een mens niet voor de hand liggend. Een evolutionaire fase wordt gestart met een populatie van willekeurig gegenereerde wezens. In elke generatie wordt de fitness van elk individu in de populatie geëvalueerd. Sommige worden willekeurig uit de huidige populatie geselecteerd (op basis van hun fitness) en gewijzigd (gerecombineerd en eventueel willekeurig gemuteerd) om een nieuwe populatie te vormen. De cyclus herhaalt zich met deze nieuwe populatie. Het algoritme eindigt ofwel nadat een bepaald aantal generaties is verstreken, ofwel nadat een goed fitnessniveau voor de populatie is bereikt. Als het algoritme is beëindigd omdat een maximum aantal generaties is bereikt, betekent dit niet noodzakelijkerwijs dat een goed fitnessniveau is bereikt.

Programmeer dit op een computer

De pseudocode is:

1. Initialisatie: Er worden enkele mogelijke oplossingen gecreëerd; heel vaak zullen deze willekeurige waarden hebben
2. Evaluatie: Een fitness-functie geeft een score aan elke oplossing; de score is een getal dat aangeeft hoe goed deze oplossing het probleem oplost.
3. De volgende stappen worden uitgevoerd totdat aan de eis om te stoppen is voldaan:
1. Selectie: Kies de oplossingen/individuen voor de volgende iteratie
2. Recombinatie: Combineer de gekozen oplossingen
3. Mutatie: Verander willekeurig de nieuw gecreëerde oplossingen
4. Evaluatie: Pas de fitnessfunctie toe, zie stap 2.
5. Als niet aan de eis om te stoppen is voldaan, begint u opnieuw met de selectiestap.

Voorbeeld

De bovenstaande beschrijving is abstract. Een concreet voorbeeld helpt.

Toepassingen

In het algemeen

Genetische algoritmen zijn goed in het oplossen van problemen als roosters en planningen. Zij zijn ook toegepast in de machinebouw. Zij worden vaak gebruikt om globale optimalisatieproblemen op te lossen.

Als vuistregel geldt dat genetische algoritmen nuttig kunnen zijn in probleemdomeinen met een complex fitness-landschap, omdat vermenging is ontworpen om de populatie weg te krijgen van lokale optima waarin een traditioneel heuvelklim-algoritme zou kunnen blijven steken. Veelgebruikte crossover operatoren kunnen geen uniforme populatie veranderen. Mutatie alleen kan zorgen voor ergodiciteit van het totale genetische algoritme-proces (gezien als een Markov-keten).

Voorbeelden van problemen die met genetische algoritmen zijn opgelost zijn: spiegels die zijn ontworpen om zonlicht naar een zonnecollector te leiden, antennes die zijn ontworpen om radiosignalen in de ruimte op te pikken, loopmethoden voor computerfiguren, optimaal ontwerp van aërodynamische lichamen in complexe stromingsvelden

In zijn Algorithm Design Manual raadt Skiena genetische algoritmen voor elke taak af: "Het is nogal onnatuurlijk om toepassingen te modelleren in termen van genetische operatoren zoals mutatie en crossover op bit strings. De pseudobiologie voegt een extra niveau van complexiteit toe tussen u en uw probleem. Ten tweede duren genetische algoritmen erg lang voor niet-triviale problemen. De analogie met evolutie - waar significante vooruitgang miljoenen jaren vergt - kan heel toepasselijk zijn. Ik ben nog nooit een probleem tegengekomen waarbij genetische algoritmen mij de juiste manier leken om het aan te pakken. Verder heb ik nog nooit berekeningsresultaten gezien waarbij genetische algoritmen werden gebruikt die een gunstige indruk op mij maakten. Blijf bij gesimuleerde annealing voor je heuristische zoek voodoo behoeften."

Bordspellen

Bordspellen vormen een zeer relevant onderdeel van het gebied van genetische algoritmen zoals toegepast op speltheoretische problemen. Veel van het vroege werk op het gebied van computationele intelligentie en spellen was gericht op klassieke bordspellen, zoals tic-tac-toe,^[3] schaken, en dammen. ^[4] Bordspellen kunnen nu, in de meeste gevallen, door een computer op een hoger niveau worden gespeeld dan de beste mensen, zelfs met blinde uitputtende zoektechnieken. Go is een bekende uitzondering op deze tendens en heeft tot nu toe weerstand geboden aan een aanval door machines. De beste Go-computerspelers spelen nu op het niveau van een goede beginner. ^{[5][6] Er} wordt gezegd dat de strategie van Go sterk steunt op patroonherkenning, en niet alleen op logische analyse zoals bij schaken en andere meer stuk-onafhankelijke spelen. De enorme effectieve vertakkingsfactor die nodig is voor het vinden van oplossingen van hoge kwaliteit beperkt in hoge mate de look-ahead die kan worden gebruikt bij het zoeken naar zettenreeksen.

Computerspelletjes

Het genetisch algoritme kan in computerspelletjes worden gebruikt om kunstmatige intelligentie te creëren (de computer speelt tegen jou). Dit maakt een realistischer spelervaring mogelijk; als een menselijke speler een opeenvolging van stappen kan vinden die altijd tot succes leiden, zelfs bij herhaling in verschillende spellen, kan er geen uitdaging meer zijn. Omgekeerd, als een leertechniek zoals een genetisch algoritme voor een strateeg kan voorkomen dat fouten uit het verleden worden herhaald, zal het spel meer speelbaarheid hebben.

Genetische algoritmen hebben de volgende onderdelen nodig:

• Een methode om de uitdaging voor te stellen in termen van de oplossing (b.v. het leiden van soldaten bij een aanval in een strategiespel)
• Een fitness- of evaluatiefunctie om de kwaliteit van een instantie te bepalen (b.v. een meting van de schade die bij een dergelijke aanval aan een tegenstander wordt toegebracht).

De fitness-functie accepteert een gemuteerde instantiatie van een entiteit en meet de kwaliteit ervan. Deze functie wordt aangepast aan het probleemdomein. In veel gevallen, met name bij code-optimalisatie, kan de fitness-functie gewoon een systeem-timing-functie zijn. Zodra een genetische representatie en een fitness-functie zijn gedefinieerd, zal een genetisch algoritme initiële kandidaten instantiëren zoals hierboven beschreven, en vervolgens verbeteren door herhaalde toepassing van mutatie-, crossover-, inversie- en selectieoperatoren (zoals gedefinieerd overeenkomstig het probleemdomein).

Beperkingen

Er zijn beperkingen aan het gebruik van een genetisch algoritme in vergelijking met alternatieve optimalisatie-algoritmen:

• Herhaalde fitness functie-evaluatie voor complexe problemen is vaak het meest beperkende segment van kunstmatige evolutionaire algoritmen. Het vinden van de optimale oplossing voor complexe problemen vereist vaak zeer dure fitness functie-evaluaties. In echte wereld problemen, zoals structurele optimalisatie problemen, kan een enkele functie-evaluatie meerdere uren tot meerdere dagen van volledige simulatie vereisen. Typische optimalisatiemethoden kunnen dergelijke soorten problemen niet aan. Vaak is het nodig benaderingen te gebruiken, omdat het berekenen van de exacte oplossing te lang duurt. Genetische algoritmen combineren soms verschillende benaderingsmodellen om complexe reële problemen op te lossen.
• Genetische algoritmen zijn niet goed schaalbaar. Dat wil zeggen, wanneer het aantal elementen dat aan mutatie wordt blootgesteld groot is, neemt de omvang van de zoekruimte vaak exponentieel toe. Dit maakt het uiterst moeilijk de techniek toe te passen op problemen zoals het ontwerpen van een motor, een huis of een vliegtuig. Om genetische algoritmen bij dergelijke problemen te kunnen gebruiken, moeten ze worden opgesplitst in een zo eenvoudig mogelijke voorstelling. Om deze reden zien we dat evolutionaire algoritmen ontwerpen coderen voor ventilatorbladen in plaats van motoren, bouwvormen in plaats van gedetailleerde bouwplannen, en draagvleugels in plaats van volledige vliegtuigontwerpen. Het tweede probleem van complexiteit is de vraag hoe onderdelen die geëvolueerd zijn om goede oplossingen te representeren, beschermd kunnen worden tegen verdere destructieve mutatie, vooral wanneer hun fitness assessment vereist dat ze goed combineren met andere onderdelen.
• De "betere" oplossing is alleen in vergelijking met andere oplossingen. Als gevolg daarvan is het stopcriterium niet bij elk probleem duidelijk.
• Bij veel problemen hebben genetische algoritmen de neiging om te convergeren naar lokale optima of zelfs willekeurige punten in plaats van naar het globale optimum van het probleem. Dit betekent dat het algoritme niet "weet" hoe het de fitness op korte termijn moet opofferen om fitness op langere termijn te verkrijgen. De waarschijnlijkheid dat dit gebeurt hangt af van de vorm van de fitnessfunctie: bepaalde problemen maken het gemakkelijk om het globale optimum te vinden, andere maken het gemakkelijker voor de functie om de lokale optima te vinden. Dit probleem kan worden verminderd door een andere fitness-functie te gebruiken, de mutatiesnelheid te verhogen, of door selectietechnieken te gebruiken die een gevarieerde populatie van oplossingen in stand houden. Een veelgebruikte techniek om diversiteit in stand te houden is het gebruik van een "niche penalty": aan elke groep individuen die voldoende gelijkenis vertoont (niche radius) wordt een penalty toegevoegd, waardoor de vertegenwoordiging van die groep in de volgende generaties wordt verminderd, zodat andere (minder gelijkende) individuen in de populatie kunnen worden gehouden. Deze truc kan echter ondoeltreffend zijn, afhankelijk van het landschap van het probleem. Een andere mogelijke techniek zou zijn een deel van de populatie eenvoudigweg te vervangen door willekeurig gegenereerde individuen, wanneer het grootste deel van de populatie te veel op elkaar lijkt. Diversiteit is belangrijk in genetische algoritmen (en genetisch programmeren) omdat het kruisen van een homogene populatie geen nieuwe oplossingen oplevert. Bij evolutiestrategieën en evolutionair programmeren is diversiteit niet van essentieel belang omdat men meer op mutatie is aangewezen.
• Het werken met dynamische gegevensverzamelingen is moeilijk, omdat genomen al in een vroeg stadium beginnen te convergeren naar oplossingen die voor latere gegevens misschien niet meer geldig zijn. Er zijn verschillende methoden voorgesteld om dit te verhelpen door de genetische diversiteit op de een of andere manier te vergroten en vroegtijdige convergentie te voorkomen, hetzij door de kans op mutatie te vergroten wanneer de kwaliteit van de oplossing daalt (getriggerde hypermutatie genoemd), hetzij door af en toe geheel nieuwe, willekeurig gegenereerde elementen in de genenpool te introduceren (willekeurige immigranten genoemd). Ook hier kunnen evolutiestrategieën en evolutionair programmeren worden geïmplementeerd met een zogenaamde "komma-strategie", waarbij de ouders niet worden gehandhaafd en nieuwe ouders alleen worden geselecteerd uit de nakomelingen. Dit kan doeltreffender zijn bij dynamische problemen.
• Genetische algoritmen kunnen geen problemen oplossen waarbij de enige maatstaf voor fitness een enkele maatstaf voor goed/fout is (zoals beslissingsproblemen), omdat er geen manier is om naar de oplossing te convergeren (geen heuvel om te beklimmen). In deze gevallen kan een willekeurige zoekactie even snel een oplossing vinden als een GA. Als de situatie echter toelaat dat de succes/failure-proef wordt herhaald, wat (mogelijk) verschillende resultaten oplevert, dan is de verhouding successen/ mislukkingen een geschikte fitness-maatstaf.
• Voor specifieke optimalisatieproblemen en probleemgevallen kunnen andere optimalisatiealgoritmen efficiënter zijn dan genetische algoritmen wat de snelheid van convergentie betreft. Alternatieve en aanvullende algoritmen zijn onder meer evolutiestrategieën, evolutionair programmeren, gesimuleerde annealing, Gaussian adaptation, hill climbing, en zwermintelligentie (b.v.: ant colony optimization, particle swarm optimization) en methoden op basis van integer lineair programmeren. De geschiktheid van genetische algoritmen is afhankelijk van de hoeveelheid kennis van het probleem; voor bekende problemen bestaan vaak betere, meer gespecialiseerde benaderingen.

Geschiedenis

In 1950 stelde Alan Turing een "leermachine" voor die parallel zou lopen met de principes van de evolutie. Computersimulatie van evolutie begon al in 1954 met het werk van Nils Aall Barricelli, die de computer gebruikte aan het Institute for Advanced Study in Princeton, New Jersey. Zijn publicatie uit 1954 werd niet algemeen opgemerkt. Vanaf 1957 publiceerde de Australische kwantitatieve geneticus Alex Fraser een reeks artikelen over de simulatie van kunstmatige selectie van organismen met meerdere loci die een meetbare eigenschap controleren. Vanaf dit begin werden computersimulaties van evolutie door biologen steeds gebruikelijker in het begin van de jaren 1960, en de methoden werden beschreven in boeken van Fraser en Burnell (1970) en Crosby (1973). De simulaties van Fraser omvatten alle essentiële elementen van de moderne genetische algoritmen. Daarnaast publiceerde Hans-Joachim Bremermann in de jaren zestig een reeks papers waarin eveneens werd uitgegaan van een populatie van oplossingen voor optimalisatieproblemen, die recombinatie, mutatie en selectie ondergingen. Bremermann's onderzoek omvatte ook de elementen van moderne genetische algoritmen. Andere opmerkelijke vroege pioniers zijn Richard Friedberg, George Friedman, en Michael Conrad. Veel vroege papers zijn herdrukt door Fogel (1998).

Hoewel Barricelli in 1963 de evolutie van het vermogen om een eenvoudig spel te spelen had gesimuleerd, werd kunstmatige evolutie een algemeen erkende optimalisatiemethode als gevolg van het werk van Ingo Rechenberg en Hans-Paul Schwefel in de jaren zestig en het begin van de jaren zeventig - de groep van Rechenberg was in staat om complexe technische problemen op te lossen met behulp van evolutiestrategieën. Een andere benadering was de evolutionaire programmeertechniek van Lawrence J. Fogel, die werd voorgesteld voor het genereren van kunstmatige intelligentie. Evolutionair programmeren maakte oorspronkelijk gebruik van eindige toestandsmachines voor het voorspellen van omgevingen, en gebruikte variatie en selectie om de voorspellende logica's te optimaliseren. Genetische algoritmen in het bijzonder werden populair door het werk van John Holland in het begin van de jaren 1970, en met name zijn boek Adaptation in Natural and Artificial Systems (1975). Zijn werk vindt zijn oorsprong in studies van cellulaire automaten, uitgevoerd door Holland en zijn studenten aan de Universiteit van Michigan. Holland introduceerde een geformaliseerd kader voor het voorspellen van de kwaliteit van de volgende generatie, bekend als Holland's schema theorema. Onderzoek naar GA's bleef grotendeels theoretisch tot het midden van de jaren tachtig, toen de eerste internationale conferentie over genetische algoritmen werd gehouden in Pittsburgh, Pennsylvania.