Wat is Genetic Algorithm?

Wat is een genetic algorithm eigenlijk?

Stel je voor dat je de perfecte recept voor chocolate chip cookies zoekt, maar je weet niet precies hoeveel boter, suiker en chocolade je nodig hebt. Je zou duizenden combinaties kunnen proberen — of je doet het slim: je bakt tien varianten, proeft welke het lekkerst zijn, combineert de beste eigenschappen van die recepten, en bakt opnieuw. Na een paar rondes kom je vanzelf bij een fantastisch recept uit.

Zo werkt een genetic algorithm. Het is een computertruc die geïnspireerd is op natuurlijke evolutie. In plaats van één oplossing te bedenken, maakt het algoritme een hele groep mogelijke oplossingen (een 'populatie'), test welke het beste werken, laat die 'voortplanten' door hun eigenschappen te mixen, gooit er wat willekeurige mutaties doorheen, en herhaalt dat proces.

Na tientallen of honderden 'generaties' blijven alleen de sterkste oplossingen over — net zoals in de natuur alleen de best aangepaste dieren overleven.

Hoe werkt het stapje voor stapje?

Een genetic algorithm volgt altijd hetzelfde recept:

1. Maak een startpopulatie — Begin met een willekeurige groep mogelijke oplossingen. Bijvoorbeeld: twintig verschillende routes voor een pakketbezorger.

2. Test de fitness — Elk individu krijgt een score. Bij de pakketroutes: hoe kort is de route? Hoe weinig benzine kost het?

3. Selecteer de winnaars — De beste oplossingen krijgen een grotere kans om door te gaan naar de volgende ronde. De slechtste vallen af.

4. Crossover (voortplanting) — Neem twee goede oplossingen en combineer ze. Route A heeft een slim begin, route B een slim einde? Maak een nieuwe route die beide slimme stukken combineert.

5. Mutatie — Verander af en toe iets willekeurigs in een oplossing. Misschien ontdek je daardoor een totaal nieuwe snelweg die niemand bedacht had.

6. Herhaal — Ga terug naar stap 2 en doe dit tientallen keren. Elke generatie wordt gemiddeld een beetje beter.

Waar kom je het tegen?

Genetic algorithms worden vooral ingezet bij problemen waar je niet precies weet hoe de ideale oplossing eruitziet, maar wel kunt testen of een oplossing goed of slecht is:

• Routeplanning — Bedrijven als DHL en PostNL optimaliseren bezorgroutes. Met honderden stops per dag zijn er zoveel mogelijke routes dat je ze niet allemaal kunt uitrekenen.

• Ontwerpen van onderdelen — NASA gebruikt genetic algorithms om lichtgewicht satellietonderdelen te ontwerpen. Het algoritme 'evolueert' vormen die sterk genoeg zijn maar minimaal materiaal gebruiken.

• Financiële modellen — Beleggingsfondsen zoeken naar de optimale mix van aandelen, obligaties en andere investeringen.

• Machine learning — Bij het trainen van neural networks kun je genetic algorithms gebruiken om de beste architectuur te vinden: hoeveel lagen, hoeveel neuronen per laag?

• Gameontwikkeling — AI-tegenstanders in games evolueren strategieën door tegen elkaar te spelen. De beste tactieken overleven.

Genetic algorithms zijn niet per se de snelste methode, maar ze zijn breed inzetbaar en vinden vaak verrassend creatieve oplossingen die mensen niet hadden bedacht.

Waarom geen standaard berekeningsmethode?

Voor sommige problemen kun je gewoon uitrekenen wat de beste oplossing is. Maar bij het Traveling Salesman Problem — een handelsreiziger moet twintig steden bezoeken via de kortste route — zijn er meer dan 100.000.000.000.000.000 mogelijke routes. Zelfs de krachtigste computer kan die niet allemaal checken.

Dan helpt evolutie: je hoeft niet álle routes te proberen, je laat gewoon de goede routes overleven en zich vermenigvuldigen. Na een paar duizend generaties heb je een route die misschien niet perfect is, maar wel verdomd goed.

Een voorbeeld uit de praktijk

Een energiebedrijf wil windturbines plaatsen in een windpark. Te dicht bij elkaar: ze stelen elkaars wind. Te ver uit elkaar: je hebt te veel kabels nodig. Er zijn duizenden mogelijke opstellingen.

Een genetic algorithm start met vijftig willekeurige opstellingen. Het berekent voor elke opstelling hoeveel stroom het oplevert minus de kabelkosten. De tien beste opstellingen 'paren': turbine-posities worden gecombineerd. Af en toe verschuift een turbine willekeurig een paar meter (mutatie). Na tweehonderd generaties heb je een opstelling die 15% meer oplevert dan het oorspronkelijke handmatige ontwerp.

Beperkingen en nadelen

Genetic algorithms zijn geen wondermiddel. Ze vereisen veel rekenkracht omdat je elke generatie tientallen of honderden oplossingen moet testen. Ze garanderen ook geen perfecte oplossing — alleen een goede. En je moet zelf bedenken hoe je een oplossing 'scoort' (de fitness-functie), wat niet altijd makkelijk is.

Bij problemen waar wél een exacte berekeningsmethode bestaat, gebruik je die gewoon. Genetic algorithms zijn voor de lastige gevallen.

Wat kun je ermee?

Als je voor een complex probleem staat zonder duidelijke formule — routeplanning, roosters maken, ontwerpen optimaliseren — kan een genetic algorithm je helpen. Je hoeft geen AI-expert te zijn: er zijn bibliotheken zoals DEAP (Python) of jenetics (Java) die het zware werk doen. Jij definieert alleen wat een 'goede' oplossing is, de rest doet evolutie.

Zelfs als je zelf geen genetic algorithms bouwt, is het handig te weten dat veel optimalisatiesoftware er intern mee werkt. Als je logistiek-software gebruikt die 'slimme routes' belooft, draait er waarschijnlijk een vorm van evolutionaire optimalisatie onder de motorkap.