Genetiske algoritmer (GA) er basert på en evolusjonær tilnærming til AI, der metoder for evolusjon av en populasjon brukes for å finne en optimal løsning for et gitt problem. De ble foreslått i 1975 av John Henry Holland.
Genetiske algoritmer bygger på følgende ideer:
- Gyldige løsninger på problemet kan representeres som gener
- Kryssing lar oss kombinere to løsninger for å oppnå en ny gyldig løsning
- Seleksjon brukes til å velge mer optimale løsninger ved hjelp av en fitness-funksjon
- Mutasjoner introduseres for å destabilisere optimaliseringen og få oss ut av lokale minima
Hvis du vil implementere en genetisk algoritme, trenger du følgende:
- En metode for å kode problemets løsninger ved hjelp av gener g∈Γ
- På settet av gener Γ må vi definere en fitness-funksjon fit: Γ→R. Mindre verdier av funksjonen tilsvarer bedre løsninger.
- Definere en kryssingsmekanisme for å kombinere to gener og få en ny gyldig løsning crossover: Γ2→Γ.
- Definere en mutasjonsmekanisme mutate: Γ→Γ.
I mange tilfeller er kryssing og mutasjon ganske enkle algoritmer for å manipulere gener som numeriske sekvenser eller bitvektorer.
Den spesifikke implementeringen av en genetisk algoritme kan variere fra tilfelle til tilfelle, men den generelle strukturen er som følger:
- Velg en startpopulasjon G⊂Γ
- Velg tilfeldig en av operasjonene som skal utføres i dette steget: kryssing eller mutasjon
- Kryssing:
- Velg tilfeldig to gener g1, g2 ∈ G
- Beregn kryssing g=crossover(g1,g2)
- Hvis fit(g)<fit(g1) eller fit(g)<fit(g2) - erstatt det tilsvarende genet i populasjonen med g.
- Mutasjon - velg et tilfeldig gen g∈G og erstatt det med mutate(g)
- Gjenta fra steg 2, til vi får en tilstrekkelig liten verdi av fit, eller til grensen for antall steg er nådd.
Oppgaver som typisk løses med genetiske algoritmer inkluderer:
- Optimalisering av tidsplaner
- Optimal pakking
- Optimal kutting
- Akselerering av uttømmende søk
Fortsett læringen i følgende notatbøker:
Gå til denne notatboken for å se to eksempler på bruk av genetiske algoritmer:
- Rettferdig fordeling av skatter
- 8-dronningers problemet
Genetiske algoritmer brukes til å løse mange problemer, inkludert logistikk og søkeproblemer. Feltet er inspirert av forskning som kombinerte temaer innen psykologi og informatikk.
"Genetiske algoritmer er enkle å implementere, men deres oppførsel er vanskelig å forstå." kilde Gjør litt research for å finne en implementering av en genetisk algoritme, for eksempel for å løse et Sudoku-puslespill, og forklar hvordan det fungerer som en skisse eller flytdiagram.
Se denne flotte videoen som forklarer hvordan en datamaskin kan lære å spille Super Mario ved hjelp av nevrale nettverk trent med genetiske algoritmer. Vi skal lære mer om hvordan datamaskiner lærer å spille slike spill i neste seksjon.
Målet ditt er å løse den såkalte Diofantiske likningen - en likning med heltallsrøtter. For eksempel, vurder likningen a+2b+3c+4d=30. Du må finne heltallsrøttene som tilfredsstiller denne likningen.
Denne oppgaven er inspirert av denne artikkelen.
Tips:
- Du kan vurdere røttene å være i intervallet [0;30]
- Som et gen, vurder å bruke listen over rotverdier
Bruk Diophantine.ipynb som utgangspunkt.