introductie
Enige tijd geleden was er een collega die een probleem had en vroeg of er mensen ideeën hadden om dit op te lossen. Nou is een probleem oplossen net 1 van de dingen wat ik maar al te graag doe!
Het probleem was een zogenaamd “combinatorial problem” en was zodanig lastig dat er enorm veel combinaties mogelijk zijn dat het vrijwel onpraktisch was om alle opties na te gaan en daar de beste uit te kiezen. Het probleem leek een klein beetje op het “0-1 Knapsack” probleem (maar was het overigens niet helemaal)
Voor wie het Knapsack probleem niet kent: “Stel je eens voor dat er een reeks producten voor je liggen. Ieder product heeft een bepaald gewicht en een prijs. Je kunt maar een beperkt aantal kilo’s meenemen. Welke producten moet je meenemen om een zo hoog mogelijke waarde mee te nemen zonder over het maximale gewicht te gaan?”
In het geval van het Knapsack probleem zijn er inmiddels wel slimme algoritmes bedacht, maar we hebben het, in dit geval, niet echt over het knapsack probleem, maar ik wil het knapsack probleem alleen gebruiken om een oplossingsrichting te toetsen en het concept van een genetisch algoritme op een zo eenvoudig mogelijke manier uit te leggen.
Dit artikel gaat dus over wat een genetisch algoritme is en hoe dit gebruikt kan worden om een zogenaamd “combinatorial problem” op te lossen.
HET GENETISCH ALGORITME ALS OPLOSSING VOOR HET KNAPSACK PROBLEEM
Als we los laten dat we niet de beste combinatie kunnen vinden en genoegen nemen met een ‘best effort’ dan kan een genetisch algoritme een goede oplossing bieden. Het algoritme is heel erg gebaseerd op de evolutie theorie.
Beeld je eens in dat je oplossing in de vorm van een chromosoom gerepresenteerd kan worden. Een chromosoom bestaat uit X aantal genen. Iedere gen stelt een keuze voor van een oplossing.
In dit voorbeeld is iedere gen een boolean en is deze gekoppeld aan een specifiek product. Staat de boolean op true dan betekent dat we in deze oplossing het product mee nemen en staat de boolean op false, niet.
Voorbeeld:
We hebben product A, B, C en D.
| Product | Prijs (EU) | Gewicht (KG) |
|---|---|---|
| A | 1 | 2 |
| B | 3 | 5 |
| C | 2 | 10 |
| D | 7 | 5 |
Er zijn verschillende mogelijke oplossingen mogelijk. Zie bijvoorbeeld:
| A | B | C | D | … |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | … |
| 1 | 1 | 0 | 1 | … |
| 1 | 1 | 1 | 1 | … |
| 1 | 1 | 0 | 1 | … |
- DE 1E OPTIE GEEFT EEN OPLOSSING WAARBIJ WE A, C EN D MEENEMEN.
- DE 2E OPTIE GEEFT EEN OPLOSSING WAARBIJ WE A, B EN D MEENEMEN.
- DE 3E OPTIE GEEFT EEN OPLOSSING WAARBIJ WE A, B, C EN D MEENEMEN.
- DE 4E OPTIE GEEFT EEN OPLOSSING WAARBIJ WE A EN D MEENEMEN.
Wat heel simpel gezegd een genetisch algoritme doet is de mogelijke populatie/ oplossingen laten evolueren om zo tot een steeds betere oplossing te komen. Dit doen we door de beste “oplossingen” te pakken en samen te voegen waarna er kinderen ontstaan(Crossover). Deze kinderen kunnen na de “geboorte” wel enigzins veranderen (Mutatie). Vervolgens is er een nieuwe generatie die we gaan beoordelen. Daarna gaan we weer dezelfde stappen doorlopen totdat we een oplossing hebben waarmee we tevreden zijn. Het idee is dus dat iedere generatie beter wordt.
Dit klinkt wellicht nog een beetje vreemd, maar dit zal zometeen duidelijk worden.
POPULATIE
We zullen ergens moeten beginnen dus gaan we zorgen voor een initiele populatie aan mogelijke oplossingen.
Hier zijn verschillende keuzes: Je zou random bits op true kunnen zetten, je zou bewust alles op false kunnen zetten en het algoritme verderop dit te laten oplossen (mutaties), etc.
FITNESS SCORE
Vervolgens hebben we code nodig die voor elke mogelijke oplossing een score bepaald. De score noemen we een Fitness Score. Hoe hoger de waarde, hoe beter het resultaat. In dit voorbeeld zal de Fitness Score de totale prijswaarde van alle gekozen producten zijn. Echter is er wel 1 voorwaarde: Het totale gewicht mag niet over het maximale gewicht gaan! Is dit wel het geval? Dan zetten we de score op 0.
Alle mogelijke oplossingen binnen onze populatie krijgt een Fitness Score toegekend:
De oplossing met alleen product D doet het, uit deze reeks, het beste. De slechtste oplossing is die waar zowel A,B,C en D meegenomen worden, omdat deze over het maximale gewicht heen gaat.
ELITE SELECTIE
Nu we een reeks aan mogelijke oplossingen hebben en hier zo mee verder gaan is het vaak wel praktisch om bijvoorbeeld de “beste” oplossing apart te zetten zodat we deze niet “kwijt” raken wanneer we oplossingen gaan “mengen” en “muteren”.
In dit voorbeeld pakken we de oplossing met alleen product D aangezien deze de hoogste score heeft.
CROSSOVER
Omdat we typisch nooit random een goede oplossing zullen genereren zullen we nieuwe oplossingen moeten gaan genereren. Hoe doen we dit? Wat hier typisch gedaan zal worden is een top X aantal oplossingen kiezen aan de hand van de beste fitness scores. We gaan deze als “ouders” benoemen, omdat we deze oplossingen gaan gebruiken om nieuwe “kinderen” te maken.
Wanneer je 2 verschillende ouders hebt kun je deze gaan mengen. Één van de manieren om dit te doen is bijvoorbeeld een willekeurig punt binnen de genen te kiezen en 2 kinderen te maken.
- KIND 1 KRIJGT HET LINKER DEEL VAN OUDER 1 EN HET RECHTER DEEL VAN OUDER 2.
- KIND 2 KRIJGT HET LINKER DEEL VAN OUDER 2 EN HET RECHTER DEEL VAN OUDER 1.
Dit noemen ze een “Single Point Crossover”. Dit doen we voor een X aantal ouders.
Voorbeeld waarbij positie 1 is gekozen:
MUTATIES
Om wat meer variatie in de mogelijke opties te krijgen in de hoop een betere oplossing te gaan vinden gaan we zorgen voor mutaties. Alle kinderen krijgen de kans dat er 1 of meerdere genen muteren. Een veel gebruikte mutatie is een “Flip Bit Mutation” en dat betekent dat er genen willekeurig van false naar true gaan en andersom. Hier wordt met een soort kans berekening gewerkt wat aangeeft wat de kans van muteren is.
DE VOLGENDE GENERATIE
We hebben nu d.m.v. elite selectie een chromosome apart gehouden en we hebben X aantal nieuwe opties (gemuteerde kinderen). Dit zal de populatie zijn voor de volgende generatie.
Door elke generatie met alleen de beste ouders verder te gaan en de allerbeste oplossing apart te houden zorgen we voor het concept van “survival of the fittest”. De slechte keuzes vallen weg en de betere worden gebruikt voor de volgende generatie.
FITNESS SCORE
Aangezien we nu weer een vernieuwde populatie hebben moeten we, waar dat nog niet bekend is, de fitness score gaan uitrekenen.
TERMINATION
Er is nu een nieuwe fitness score bekend voor de nieuwe populatie, maar willen we hierna nog een volgende generatie? Gaan we nog een keer nieuwe kinderen genereren en deze laten muteren? Of hebben we al een goede oplossing?
Hier zijn ook weer meerdere keuzes die gemaakt kunnen worden. Je kunt er voor kiezen om altijd X aantal generaties te laten draaien, je kunt kijken of de fitness score stil staat en niet meer verbeterd, etc.
In ieder geval komt hier een ja of een nee uit. Ja, dan we gaan verder en dan gaan we weer alle stappen doorlopen. Nee, dan stoppen we en pakken we de optie met de hoogste fitness score als oplossing.
FLOW
Dit gehele plaatje ziet er als volgt uit:
conclusie
Hopelijk is het concept duidelijk. Het geeft een relatief simpele oplossing voor een soms complex probleem. Wil je wat meer zien hoe je dit moet doen? Ik heb een c#/ demo applicatie in elkaar gezet waarbij het bovenstaand concept gedemonstreerd wordt.
Je kunt de demo applicatie hier vinden:
https://github.com/vhendriks81/geneticalgorithm
Er zijn verder genoeg open source libraries in diverse talen/ ontwikkelomgevingen die verschillende vormen qua crossover functies, mutatie functies, etc aanbieden.
