NLJUG – Nederlandse Java User Group NLJUG – de Nederlandse Java User Group – is opgericht in 2003. De NLJUG verenigt software ontwikkelaars, architecten, ICT managers, studenten, new media developers en haar businesspartners met algemene interesse in alle aspecten van Java Technology.
De natuur is altijd al een grote bron van inspiratie geweest voor (software) engineers. Er zijn al snel twee grote inspiratiebronnen te noemen: het menselijk brein, dat het wiel heeft uitgevonden, Rome heeft gesticht en Java heeft bedacht, en de evolutie, die onder andere weer verantwoordelijk is voor de totstandkoming van het menselijk brein. Evolutie komt voort uit een aantal zeer krachtige mechanismen, die je als software engineer ook kunt gebruiken. Het doel van dit artikel is om een nieuwe tool toe te voegen aan de krachtige toolset, die je je al eigen hebt gemaakt: Evolutionaire Algoritmen.
Evolutie
Voordat we dieper ingaan op de werking van Evolutionaire Algoritmen is het handig om even stil te staan bij de basis van evolutie en waarom het werkt zoals het werkt. Natuurlijke selectie is één van de drijfveren achter evolutie en vindt plaats op het moment, dat een groep levensvormen met de drang tot reproductie moet concurreren om een beperkte hoeveelheid resources in dezelfde omgeving. Natuurlijke selectie houdt (simpel gezegd) in dat de individuen, die het best concurreren voor de resources in de omgeving lang genoeg overleven om te kunnen reproduceren. Tijdens dat reproduceren vindt recombinatie plaats. Dit houdt in dat beide ouders de helft van hun DNA doorgeven, dat vervolgens gecombineerd wordt en het DNA vormt van het kind. De combinatie van eigenschappen van de ouders kan ervoor zorgen dat het kind beter of minder kan concurreren voor de resources dan de ouders. Tijdens het recombinatie-proces kan ook een "foutje" optreden (mutatie), waardoor er een ander stuk DNA wordt doorgegeven dan één van de ouders gaf. Dit kan desastreuze gevolgen hebben voor het kind, omdat het ervoor zorgt dat het kind niet meer levensvatbaar is. Anderzijds kan het ook het ontstaan van een positieve, nieuwe eigenschap betekenen.
Door de combinatie van deze mechanismen zorgt evolutie over tijd ervoor dat individuen steeds beter aangepast zijn aan de omgeving. Zie de omgeving als het probleem en het individu als een (suboptimale) oplossing voor dat probleem. Evolutie kan dan gebruikt worden om de populatie (en dus de individuen) te laten evolueren naar betere oplossingen. Vanwege de sterk toegenomen rekenkracht in de afgelopen jaren is het mogelijk voor computers om het evolutieproces na te bootsen door duizenden generaties te simuleren in soms luttele seconden. De natuur zou daar duizenden jaren voor nodig hebben. Als gevolg van de computerkracht van tegenwoordig, de prestaties die talen als Java eruit weten te halen en het relatief lage prijskaartje, wordt het steeds aantrekkelijker voor software engineers om evolutie aan te wenden om complexe problemen op te (laten) lossen. Een voorbeeld van zo’n complex probleem is het Traveling Salesman Problem.
Use case: Traveling Salesman Problem
Het Traveling Salesman Problem behoeft enige vorm van verbeelding. Stel je voor dat je een verkoper (salesman) bent, die een aantal steden moet aandoen binnen een bepaalde tijd. Je gaat 's ochtends van huis, wilt verschillende steden aandoen om zaken te doen en op tijd weer thuis zijn voor het avondeten. Je wilt dus graag de kortste route nemen, die al die steden aandoet. Als je n steden moet bezoeken, dan zijn er (n-1)! mogelijke routes, die je kunt nemen. Bij vier steden valt dit nog mee ( 3 x 2 x 1 = 6), maar bij 31 steden heb je het al over ongeveer 100.000.000.000.000.000.000.000.000.000.000 mogelijke routes! Om daar de (sub)optimale route tussen te vinden met een brute-force algoritme wens je je schoonmoeder nog niet toe.
In dit artikel wordt niet beweerd dat een Evolutionair Algoritme de beste oplossing is voor het Traveling Salesman Problem. Deze use case kan echter mooi worden gebruikt om je te laten zien hoe je een Evolutionair Algoritme kunt implementeren voor een specifiek probleem en het toont tegelijkertijd de eenvoud en de kracht van de implementatie.
Uitwerken van het Evolutionair Algoritme
Aan de basis van het toepassen van een Evolutionair Algoritme staat het in Listing 1 in pseudo-code uitgedrukte algoritme.
INITIALISEER populatie met willekeurige kandidaat oplossingen
EVALUEER elke kandidaat
WHILE ( TERMINATIE CONDITIE niet bereikt) {
1. SELECTEER ouders
2. RECOMBINEER ouderparen
3. MUTEER kinderen (met een bepaalde kans)
4. EVALUEER nieuwe kandidaten
5. SELECTEER kandidaten voor de volgende generatie
}
Listing 1: Basis van een Evolutionair Algoritme in Pseudo-code [1]
Initialisatie willekeurige kandidaten
Het algoritme begint met het initialiseren van de populatie met willekeurige kandidaat oplossingen. Dit zijn mogelijke oplossingen voor het probleem, die op een dusdanige manier zijn gerepresenteerd, dat je kunt evalueren hoe goed (fit) ze zijn. In het geval van het Traveling Salesman Problem kun je bijvoorbeeld de steden die je wilt bezoeken nummeren en de route (onze kandidaat oplossing) uitdrukken, zoals afgebeeld in Figuur 1.
Figuur 1. Representatie van route (n=6). Je eindigt in je eigen stad.
Met deze representatie kun je alle mogelijke routes uitdrukken en kun je de vervolgstappen van het algoritme goed implementeren.
Terminatie conditie
Nu je een populatie hebt, die gevuld is met willekeurige kandidaten, is het handig om te kunnen bepalen hoe goed een kandidaat het probleem oplost, de “fitness”. De functie, die de fitness berekent, wordt ook wel de fitness functie of evaluatie functie genoemd. Wat je per kandidaat oplossing wilt weten in het geval van het Traveling Salesman Problem is de totale afstand die de kandidaat oplevert. Die wil je minimaliseren! De afstand is gemakkelijk te berekenen door de som van de afstanden tussen de steden te nemen (zie Listing 2).
private void calculateFitness() {
double totalDistance = 0;
/*
* For all Cities in the route (except the last one) get the distance between this
* City and the next and add it to the totalDistance
*/
for (int i = 0; i < route.size() - 1; i++) {
City city = route.get(i);
City nextCity = route.get(i + 1);
totalDistance += city.calculateDistance(nextCity);
}
this.fitness = totalDistance;
}
Listing 2. Voorbeeld implementatie van de fitness functie
Nu je een populatie hebt en de fitness van de kandidaten kunt berekenen, is het tijd voor het uitvoeren van een cyclus, die pas ophoudt als de gekozen beëindigingsconditie is bereikt. Er zijn meerdere condities denkbaar, waaronder: aantal generaties, doorlooptijd en bereikte fitness. Het is aan te bevelen om een combinatie te gebruiken van een conditie, die daadwerkelijk termineert, zoals doorlooptijd of aantal generaties, en een conditie die je eigenlijk wilt behalen, maar die wellicht nooit termineert, zoals een bereikte fitness (fitness threshold). Op die manier blijf je niet zitten met een ‘'run'', die nooit termineert.
Selectie ouders
Het selecteren van ouders is erg belangrijk binnen de evolutie en het Evolutionair Algoritme. De selectie bepaalt namelijk welke ouders mogen gaan paren en daarmee hun genetisch materiaal door mogen geven aan de volgende generatie. Intuïtief zou je denken dat je altijd de kandidaten met de beste fitness moet nemen om te reproduceren. Vanwege redenen die buiten de scope van dit artikel liggen, is het goed om er een element van willekeur in te houden [1]. Je kunt bijvoorbeeld een selectie implementeren door de beste x aantal kandidaten uit een selectie van y willekeurig gekozen kandidaten te selecteren (zie Listing 3 voor een implementatie).
private List<CandidateSolution> parentSelection() {
List<CandidateSolution> tempPopulation = new ArrayList<>(population);
List<CandidateSolution> randomCandidates = new ArrayList<>();
/* create parent pool */
for(int i = 0; i < parentPoolSize; i++) {
/* select a random candidate solution from the temp population */
int randomlySelectedIndex = random.nextInt(tempPopulation.size());
CandidateSolution randomSelection = tempPopulation.get(randomlySelectedIndex);
randomCandidates.add(randomSelection);
/* delete the candidate from the temp population, so we can't pick it again */
tempPopulation.remove(randomlySelectedIndex);
}
/* Sort the population so that the best candidates are up front */
Collections.sort(randomCandidates);
/* return a list with size parentSelectionSize with the best CandidateSolutions */
return randomCandidates.subList(0, parentSelectionSize);
}
Listing 3. Voorbeeld implementatie van de ouderselectie.
Recombineer
De ouders, die gaan recombineren, zijn geselecteerd. Hoe implementeer je recombinatie? Bij mensen is het "simpel". Pak de helft van het DNA van de moeder en de helft van het DNA van de vader en plak het aan elkaar. Eitje (letterlijk). In het geval van het Traveling Salesman Problem is het helaas niet zo gemakkelijk. Een van de regels is dat je maar één keer langs een stad mag komen. Als je het materiaal van de ouders 50/50 gebruikt, dan is de kans groot dat je die regel breekt. Het concept dat hiervoor als oplossing wordt gebruikt, heet ''cut-and- crossfill'' en is uitgelegd in code in Listing 4-1 en Listing 4-2. Je genereert twee kinderen uit twee ouders door voor elk kind één van de ouders te pakken en de steden van index 0 tot een willekeurige index (cutIndex) te kopiëren in het eerste kind. Bij de andere ouder begin je vanaf dezelfde cutIndex, loop je de route door en bij elke stad, die nog niet in het nieuwe kind voorkomt, neem je de stad over in het kind. Bij het tweede kind begin je bij de andere ouder. Ingewikkeld mechanisme, maar de code spreekt voor zich en is relatief eenvoudig.
public List<CandidateSolution> recombine(CandidateSolution otherParent) {
List<City> parentRoute1 = getRoute();
List<City> parentRoute2 = otherParent.getRoute();
List<City> childRoute1 = new ArrayList<City>();
List<City> childRoute2 = new ArrayList<City>();
/* randomize cutIndex for "cross-and-fill point" */
int cutIndex = new Random().nextInt(parentRoute1.size());
/* copy the first part of the parents cut into the children */
childRoute1.addAll(parentRoute1.subList(0, cutIndex));
childRoute2.addAll(parentRoute2.subList(0, cutIndex));
/* perform crossfill for both children (See Listing 4-2 for method implementation) */
crossFill(childRoute1, parentRoute2, cutIndex);
crossFill(childRoute2, parentRoute1, cutIndex);
/* create new children using the new children routes */
CandidateSolution child1 = new CandidateSolution(childRoute1);
CandidateSolution child2 = new CandidateSolution(childRoute2);
/* put the children in a list and return it (omitted for layout reasons) */
}
Listing 4-1. Voorbeeld implementatie van de recombineertechniek “cut-and-crossfill” (deel 1)
/**
* Check the rest of the route in the crossing parent and add the cities
* that are not yet in the child (in the order of the route of the crossing
* parent)
*/
private void crossFill(List<City> childRoute, List<City> parentRoute, int cutIndex) {
/* traverse the parent route from the cut index on and add every city not yet in the child to the child */
for (int i = cutIndex; i < parentRoute.size(); i++) {
City nextCityOnRoute = parentRoute.get(i);
if (!childRoute.contains(nextCityOnRoute)) {
childRoute.add(nextCityOnRoute);
}
}
/* traverse the parent route from the start of the route and add every city not yet in the child to the child */
for (int i = 0; i < cutIndex; i++) {
City nextCityOnRoute = parentRoute.get(i);
if (!childRoute.contains(nextCityOnRoute)) {
childRoute.add(nextCityOnRoute);
}
}
}
Listing 4-2. Voorbeeld implementatie van de recombineertechniek “cut-and-crossfill” (deel 2)
Muteer
Voor het toepassen van mutatie geldt eigenlijk hetzelfde als voor recombinatie. Instinctief zou je zeggen dat het willekeurig aanpassen van één van de steden in de route een mooie implementatie van mutatie zou zijn. Daarmee breek je echter de één-keer-elke-stad-regel. Kies in plaats daarvan twee willekeurige steden in de route en verwissel ze. Zie Figuur 2-1 en 2-2 voor een uitbeelding en Listing 5 voor een voorbeeld implementatie.
Figuur 2-1. Voor mutatie
Figuur 2-2. Na mutatie
public void mutate() {
Random random = new Random();
/* randomly select two indices */
int indexFirstCity = random.nextInt(route.size());
int indexSecondCity = random.nextInt(route.size());
/* Make sure they are different */
while (indexFirstCity == indexSecondCity) {
indexSecondCity = random.nextInt(route.size());
}
/* retrieve the Cities on the given indices */
City firstCity = route.get(indexFirstCity);
City secondCity = route.get(indexSecondCity);
/* Changer! */
route.set(indexFirstCity, secondCity);
route.set(indexSecondCity, firstCity);
}
Listing 5. Voorbeeld implementatie van mutatie
Evalueer
Vervolgens is het belangrijk om de nieuw gegenereerde kinderen te evalueren en hun fitness te berekenen. Nu heb je een pool van ouders van de vorige generatie, plus de gegenereerde nakomelingen.
Selecteer
Tijd voor natuurlijke selectie! Welke kandidaten worden doorgelaten naar de volgende generatie? Er zijn legio aan mogelijkheden, maar om het artikel enigszins kort en bondig te houden worden de "slechtste" kandidaten verwijderd uit de populatie. Zie Listing 6 voor een voorbeeld implementatie.
private void selectSurvivors() {
Collections.sort(population); // CandidateSolution implements Comparable using fitness
population = population.subList(0, populationSize);
}
Listing 6. Voorbeeld implementatie van natuurlijk selectie / survivor selection
Er is een nieuwe generatie! En als de terminatie conditie nog niet is bereikt, begint het verhaal van voren af aan. Te beginnen met het selecteren van de ouders voor de volgende generatie…
Dit algoritme en de uitwerking voor de use case, die hier is aangegeven geeft daadwerkelijk een goede oplossing voor het Traveling Salesman probleem. Er zijn een aantal onderdelen binnen het algoritme (en deze uitwerking), die je kunt ''tweaken'': mutatie kans, populatiegrootte, aantal kinderen die gegenereerd worden, terminatie conditie, ouderselectie, overlevingsselectie. Het is dus handig om deze op te nemen als variabelen in je code.
Demo & Praktijk
Op de Github repository (vermeld in de bio) is een demo beschikbaar van het in dit artikel uitgewerkte algoritme. Als je de gehele code wilt zien of wilt kijken hoe de demo werkt (zie Figuur 3) kun je daar terecht. Ook is er een YouTube-video (http://bit.ly/evo-algo) beschikbaar van de J-Fall presentatie van afgelopen jaar, waarin de demo aan bod komt.
Figuur 3. Demo: Evolutionair Algoritme oplossing voor het Traveling Salesman Problem
Een aansprekend praktijkvoorbeeld van het gebruik van Evolutionaire Algoritmen is dat van de NASA. In 2006 heeft de NASA de "Space Technology 5" missie uitgevoerd. Het doel van deze missie is op zich niet van belang in deze context, maar interessant is dat de NASA voor deze missie drie uitzonderlijk kleine ruimtemodules gebruikte. Deze ruimtemodules waren zó klein, dat er extreem kleine antennes nodig waren, die wel voldeden aan de hoge eisen. Het ontwerp hiervan bleek een lastige taak te zijn voor de engineers van de NASA, dus besloten ze een Evolutionair Algoritme te implementeren, dat het ontwerpen van deze antenne voor ze deed. Het resultaat had niemand verwacht en werkte (zie Figuur 4 voor één van de resultaten). Bekijk mijn YouTube video (http://bit.ly/evo-algo) voor een uitgebreidere uitleg.
Figuur 4. NASA Space Technology 5 Mission: Antenne ontwikkeld door Evolutionair Algoritme (Bron: nasa.gov)
Conclusie
Aan de hand van de Traveling Salesman use case is er uitgelegd hoe je een simpel Evolutionair Algoritme kunt implementeren, waar je over moet nadenken als je zelf een Evolutionair Algoritme wil implementeren en welke onderdelen te tweaken zijn. Mocht het doel om je interesse te wekken bereikt zijn, dan kun je altijd kijken op mijn Github repo, één van de frameworks aangegeven in Figuur 5 downloaden en uitproberen, de YouTube video van de presentatie op J-Fall bekijken of er meer over lezen. [1] is een aanrader, maar Google biedt ook meer dan genoeg interessante zoekresultaten. Succes en vooral veel plezier met het oplossen van complexe problemen met Evolutionaire Algoritmen!
Figuur 5. Aan te raden Java frameworks voor Evolutionaire Algoritmen