Genetiska algoritmer (GA) bygger på en evolutionär metod inom AI, där metoder för att utveckla en population används för att hitta en optimal lösning för ett givet problem. De föreslogs 1975 av John Henry Holland.
Genetiska algoritmer baseras på följande idéer:
- Giltiga lösningar på problemet kan representeras som gener
- Korsning gör det möjligt att kombinera två lösningar för att få en ny giltig lösning
- Urval används för att välja mer optimala lösningar med hjälp av en fitnessfunktion
- Mutationer introduceras för att destabilisera optimeringen och ta oss ur lokala minima
Om du vill implementera en genetisk algoritm behöver du följande:
- Hitta ett sätt att koda våra problemlösningar med hjälp av gener g∈Γ
- På mängden gener Γ behöver vi definiera en fitnessfunktion fit: Γ→R. Mindre funktionsvärden motsvarar bättre lösningar.
- Definiera en korsningsmekanism för att kombinera två gener och få en ny giltig lösning crossover: Γ2→Γ.
- Definiera en mutationsmekanism mutate: Γ→Γ.
I många fall är korsning och mutation ganska enkla algoritmer för att manipulera gener som numeriska sekvenser eller bitvektorer.
Den specifika implementeringen av en genetisk algoritm kan variera från fall till fall, men den övergripande strukturen är följande:
- Välj en initial population G⊂Γ
- Välj slumpmässigt en av de operationer som ska utföras vid detta steg: korsning eller mutation
- Korsning:
- Välj slumpmässigt två gener g1, g2 ∈ G
- Beräkna korsning g=crossover(g1,g2)
- Om fit(g)<fit(g1) eller fit(g)<fit(g2) - ersätt motsvarande gen i populationen med g.
- Mutation - välj en slumpmässig gen g∈G och ersätt den med mutate(g)
- Upprepa från steg 2 tills vi får ett tillräckligt litet värde på fit, eller tills gränsen för antalet steg har nåtts.
Uppgifter som vanligtvis löses med genetiska algoritmer inkluderar:
- Optimering av scheman
- Optimal packning
- Optimal skärning
- Snabba upp uttömmande sökningar
Fortsätt ditt lärande i följande anteckningsböcker:
Gå till denna anteckningsbok för att se två exempel på användning av genetiska algoritmer:
- Rättvis fördelning av skatt
- 8 drottningars problem
Genetiska algoritmer används för att lösa många problem, inklusive logistik och sökproblem. Fältet är inspirerat av forskning som kombinerade ämnen inom psykologi och datavetenskap.
"Genetiska algoritmer är enkla att implementera, men deras beteende är svårt att förstå." källa Gör lite forskning för att hitta en implementering av en genetisk algoritm, som att lösa ett Sudoku-pussel, och förklara hur det fungerar som en skiss eller flödesschema.
Titta på denna fantastiska video som handlar om hur datorer kan lära sig spela Super Mario med hjälp av neurala nätverk tränade av genetiska algoritmer. Vi kommer att lära oss mer om hur datorer lär sig spela sådana spel i nästa avsnitt.
Ditt mål är att lösa den så kallade Diofantiska ekvationen - en ekvation med heltalsrötter. Till exempel, överväg ekvationen a+2b+3c+4d=30. Du behöver hitta heltalsrötterna som uppfyller denna ekvation.
Denna uppgift är inspirerad av detta inlägg.
Tips:
- Du kan överväga rötterna att vara i intervallet [0;30]
- Som en gen kan du använda listan över rotvärden
Använd Diophantine.ipynb som startpunkt.