Genetisch algoritme

Een genetisch algoritme (GA) is een algoritme ontstaan in de kunstmatige intelligentie, dat gebruikt wordt om oplossingen te vinden voor optimalisatie- en zoekproblemen. Genetische algoritmen zijn een klasse binnen de evolutionaire algoritmen.

Geschiedenis

John Holland was de grondlegger van veel van het hedendaags werk in GA's. In het begin was het een puur theoretisch onderwerp (gebaseerd op computer modelling). Tegenwoordig richt het onderzoek zich op het ontwikkelen van methodes die gebruikt kunnen worden voor het oplossen van problemen.

Terminologie

De invloeden van de evolutietheorie zijn terug te vinden in de gebruikte terminologie. Zo wordt een parameter die geoptimaliseerd moet worden een gen genoemd en de waarde van een gen een allel. Alle genen samen zijn een chromosoom, de abstracte representatie van een oplossing. De oplossing zelf wordt een individu genoemd. Alle individuen zijn samen een populatie. De populatie wordt bij iedere iteratie van het algoritme vernieuwd. De populatie van een bepaalde iteratie wordt een generatie genoemd. (Belangrijk: het genoom zijn alle chromosomen van een organisme, op een chromosoom liggen de allelen.)

Werking

Een genetisch algoritme doorloopt de volgende stappen om tot een oplossing te komen:

Initialisatie

Initieel worden verschillende oplossingen gegenereerd. Deze oplossingen zijn, afhankelijk van het probleem, één of meerdere getallen die aanvankelijk meestal willekeurig gekozen zijn. In de loop van het gesimuleerde evolutieproces ontstaan uit deze willekeurige oplossingen betere oplossingen. De programmeur kan ook zelf een aantal redelijke oplossingen toevoegen als beginpopulatie.

Selectie

Voor elk van de oplossingen in de populatie wordt een bepaalde waarde bepaald, de zogeheten fitness waarde met behulp van een fitnessfunctie. Deze waarde geeft aan hoe goed de oplossing is in vergelijking met de andere en (indien bekend) met een beoogde optimale oplossing. Net zoals in de evolutietheorie is het idee dat de betere oplossingen overleven. Op basis van deze fitnesswaarden wordt de grootte van de populatie verminderd. Dit kan gebeuren door de beste 25 of 50 procent van de oplossingen te nemen om mee door te rekenen en de andere weg te gooien of door onderling telkens twee oplossingen met elkaar te vergelijken en de beste van die twee te nemen.

Reproductie

Een voorbeeld van cross-over

Om de populatie te doen groeien, dienen de oplossingen zich te reproduceren. Dit kan met behulp van mutatie en recombinatie. Bij recombinatie worden twee oplossingen gecombineerd om twee nieuwe oplossingen te maken. Dit kan bijvoorbeeld door crossover, waarbij delen van de ene oplossing in de andere oplossing worden ingevuld. Bij mutatie worden bij een aantal willekeurig gekozen oplossingen in de populatie één of meerdere getallen gemuteerd. Hierdoor kunnen oplossingen (lichtelijk) veranderen in vergelijking met de populatie in de vorige generatie. Soms worden de beste oplossingen uitgesloten van crossover en mutatie; zij gaan onveranderd door naar de volgende generatie. Deze strategie heet de elite selectie strategie. Dit proces wordt herhaald tot de populatie even groot is als de vorige generatie.

Stopconditie

Het stoppen van de evolutie kan op verschillende manieren. Enkele veelgebruikte stopcondities zijn:

Na het berekenen van een vooraf vastgesteld aantal generaties
Na een toegewezen computertijd of geldverbruik (vanwege het budget)
Na het lang gelijk blijven van de beste fitness waarde of het convergeren naar een bepaalde waarde toe
Een combinatie van de bovenstaande condities

Samengevat ziet de werking van een genetisch algoritme in pseudocode er als volgt uit:

Kies initiële populatie

Bepaal voor elk individu de fitness

Herhaal tot de stop-conditie vervuld is:

Selecteer de individuen uit de huidige populatie

Reproductie beste individuen

Bepaal voor elk individu de fitness

Opmerkingen

Voordelen

GAs kunnen snel goede oplossingen leveren, zelfs voor moeilijke oplossingsruimten.
GAs zijn makkelijk aan te passen voor gedistribueerde computing omgevingen. Een methode behandelt elke knoop als een parallelle populatie. Organismen worden dan van de ene naar de andere genenpoel verhuisd. Hiervoor zijn er een aantal verhuisstrategieën. Een andere methode, de boer/werker architectuur, heeft een knoop die als boer optreedt en de andere als werkers. De boer is verantwoordelijk voor de selectie en de bepaling van de fitness. De werkers zijn verantwoordelijk voor recombinatie, mutatie en functieevaluatie.

Nadelen

GAs vinden niet gegarandeerd de optimale oplossing: ze hebben de neiging te convergeren naar een lokale oplossing in plaats van een globale oplossing van het op te lossen probleem.
Het toepassen van GAs op dynamische data set is moeilijk, omdat genomen al vroeg kunnen convergeren naar een oplossing die later niet meer geldig is. Er is een aantal methoden voorgesteld om dit probleem tegen te gaan. Deze methoden vergroten op de een of andere manier de genetische diversiteit en stellen de convergentie uit door of de kans op mutatie te vergroten wanneer de kwaliteit van de oplossing verslechtert ('aangestuurde hypermutatie') of door regelmatig nieuwe oplossingen toe te voegen aan de populatie ('willekeurige immigranten').

Zie ook

Externe link

(en) Genetic Algorithms in Ruby

Bronnen, noten en/of referenties

Goldberg, David E (1989), Genetic Algorithms in Search, Optimization and Machine Learning
Mitchell, Melanie, (1996), An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA Addison-Wesley
Harvey, Inman (1992), Species Adaptation Genetic Algorithms: A basis for a continuing SAGA, in 'Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life', F.J. Varela and P. Bourgine (eds.), MIT Press/Bradford Books, Cambridge, MA, pp. 346-354.
Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, freely available via Lulu.com, ISBN 978-1-4092-0073-4
PGAPack Genetisch Algoritme pakket