A Genetikus Algoritmusok (GA) az AI egy evolúciós megközelítésén alapulnak, amelyben egy populáció evolúciós módszereit használjuk egy adott probléma optimális megoldásának megtalálására. Az algoritmusokat 1975-ben John Henry Holland javasolta.
A Genetikus Algoritmusok az alábbi ötleteken alapulnak:
- A probléma érvényes megoldásai génekként reprezentálhatók
- A keresztezés lehetővé teszi két megoldás kombinálását, hogy új érvényes megoldást kapjunk
- A szelekció segítségével a fitness függvény alapján kiválaszthatjuk az optimálisabb megoldásokat
- Mutációkat vezetünk be, hogy destabilizáljuk az optimalizálást és elkerüljük a lokális minimumot
Ha Genetikus Algoritmust szeretnél implementálni, az alábbiakra van szükséged:
- Meg kell találnod egy módszert, amellyel a probléma megoldásait génekként kódolhatod g∈Γ
- A gének halmazán Γ definiálnod kell egy fitness függvényt fit: Γ→R. A kisebb függvényértékek jobb megoldásokat jelentenek.
- Definiálnod kell egy keresztezési mechanizmust, amely két gént kombinálva új érvényes megoldást hoz létre crossover: Γ2→Γ.
- Definiálnod kell egy mutációs mechanizmust mutate: Γ→Γ.
Sok esetben a keresztezés és a mutáció egyszerű algoritmusok, amelyek numerikus sorozatokkal vagy bitvektorokkal manipulálnak.
A genetikus algoritmus konkrét implementációja esetről esetre változhat, de az általános struktúra a következő:
- Válassz egy kezdeti populációt G⊂Γ
- Véletlenszerűen válassz egy műveletet, amelyet ebben a lépésben végrehajtasz: keresztezés vagy mutáció
- Keresztezés:
- Véletlenszerűen válassz két gént g1, g2 ∈ G
- Számítsd ki a keresztezést g=crossover(g1,g2)
- Ha fit(g)<fit(g1) vagy fit(g)<fit(g2) - cseréld ki a megfelelő gént a populációban g-re.
- Mutáció - válassz véletlenszerűen egy gént g∈G és cseréld ki mutate(g)-re
- Ismételd a 2. lépéstől, amíg el nem érünk egy elég kicsi fit értéket, vagy amíg el nem érjük a lépések számának korlátját.
A Genetikus Algoritmusokkal általában megoldott feladatok:
- Ütemezés optimalizálása
- Optimális csomagolás
- Optimális vágás
- Kimerítő keresés felgyorsítása
Folytasd a tanulást az alábbi jegyzetfüzetekben:
Látogass el ebbe a jegyzetfüzetbe, hogy két példát láss a Genetikus Algoritmusok használatára:
- Kincsek igazságos elosztása
- 8 Királynő probléma
A Genetikus Algoritmusokat számos probléma megoldására használják, beleértve a logisztikai és keresési problémákat. A területet a Pszichológia és Számítástechnika témáinak összeolvadása ihlette.
"A genetikus algoritmusok egyszerűen implementálhatók, de viselkedésük nehezen érthető." forrás Kutass utána egy genetikus algoritmus implementációjának, például egy Sudoku rejtvény megoldásának, és magyarázd el, hogyan működik vázlat vagy folyamatábra formájában.
Nézd meg ezt a remek videót, amely arról szól, hogyan tanulhatnak a számítógépek Super Mario-t játszani genetikus algoritmusokkal tanított neurális hálózatok segítségével. A következő szekcióban többet fogunk tanulni az ilyen típusú játékok tanulásáról.
A célod az úgynevezett Diofantoszi egyenlet megoldása - egy egyenlet, amelynek egész számú gyökei vannak. Például, tekintsük az a+2b+3c+4d=30 egyenletet. Meg kell találnod azokat az egész számú gyököket, amelyek kielégítik ezt az egyenletet.
Ezt a feladatot ez a bejegyzés ihlette.
Tippek:
- Tekintsd a gyököket a [0;30] intervallumban
- Génként használj egy listát a gyökértékekről
Használd Diophantine.ipynb kiindulópontként.