Genetische Algoritmen (GA) zijn gebaseerd op een evolutionaire benadering van AI, waarbij methoden van populatie-evolutie worden gebruikt om een optimale oplossing voor een bepaald probleem te vinden. Ze werden in 1975 voorgesteld door John Henry Holland.
Genetische Algoritmen zijn gebaseerd op de volgende ideeën:
- Geldige oplossingen voor het probleem kunnen worden weergegeven als genen
- Crossover stelt ons in staat om twee oplossingen te combineren tot een nieuwe geldige oplossing
- Selectie wordt gebruikt om meer optimale oplossingen te kiezen met behulp van een fitnessfunctie
- Mutaties worden geïntroduceerd om de optimalisatie te verstoren en ons uit een lokaal minimum te halen
Als je een Genetisch Algoritme wilt implementeren, heb je het volgende nodig:
- Een methode om de oplossingen van ons probleem te coderen met behulp van genen g∈Γ
- Op de verzameling genen Γ moeten we een fitnessfunctie definiëren fit: Γ→R. Lagere functiewaarden komen overeen met betere oplossingen.
- Een crossover-mechanisme definiëren om twee genen te combineren tot een nieuwe geldige oplossing crossover: Γ2→Γ.
- Een mutatie-mechanisme definiëren mutate: Γ→Γ.
In veel gevallen zijn crossover en mutatie vrij eenvoudige algoritmen om genen te manipuleren als numerieke reeksen of bitvectoren.
De specifieke implementatie van een genetisch algoritme kan per geval verschillen, maar de algemene structuur is als volgt:
- Selecteer een initiële populatie G⊂Γ
- Selecteer willekeurig een van de operaties die in deze stap zullen worden uitgevoerd: crossover of mutatie
- Crossover:
- Selecteer willekeurig twee genen g1, g2 ∈ G
- Bereken crossover g=crossover(g1,g2)
- Als fit(g)<fit(g1) of fit(g)<fit(g2) - vervang het overeenkomstige gen in de populatie door g.
- Mutatie - selecteer een willekeurig gen g∈G en vervang het door mutate(g)
- Herhaal vanaf stap 2, totdat we een voldoende kleine waarde van fit hebben bereikt, of totdat de limiet op het aantal stappen is bereikt.
Taken die typisch worden opgelost door Genetische Algoritmen zijn onder andere:
- Optimalisatie van planningen
- Optimale verpakkingen
- Optimale snijpatronen
- Versnellen van uitputtende zoekmethoden
Ga verder met leren in de volgende notebooks:
Ga naar dit notebook om twee voorbeelden te zien van het gebruik van Genetische Algoritmen:
- Eerlijke verdeling van schatten
- 8-Damesprobleem
Genetische Algoritmen worden gebruikt om veel problemen op te lossen, waaronder logistieke en zoekproblemen. Het vakgebied is geïnspireerd door onderzoek dat onderwerpen in de psychologie en informatica combineerde.
"Genetische algoritmen zijn eenvoudig te implementeren, maar hun gedrag is moeilijk te begrijpen." bron Doe wat onderzoek om een implementatie van een genetisch algoritme te vinden, zoals het oplossen van een Sudoku-puzzel, en leg uit hoe het werkt in de vorm van een schets of stroomdiagram.
Bekijk deze geweldige video waarin wordt uitgelegd hoe een computer kan leren Super Mario te spelen met behulp van neurale netwerken die zijn getraind door genetische algoritmen. We zullen meer leren over hoe computers leren om dit soort spellen te spelen in de volgende sectie.
Je doel is om de zogenaamde Diofantische vergelijking op te lossen - een vergelijking met gehele wortels. Overweeg bijvoorbeeld de vergelijking a+2b+3c+4d=30. Je moet de gehele wortels vinden die aan deze vergelijking voldoen.
Deze opdracht is geïnspireerd door dit artikel.
Hints:
- Je kunt wortels beschouwen in het interval [0;30]
- Gebruik als gen de lijst van wortelwaarden
Gebruik Diophantine.ipynb als startpunt.