Genetski algoritmi (GA) temelje se na evolucijskom pristupu umjetnoj inteligenciji, gdje se metode evolucije populacije koriste za pronalaženje optimalnog rješenja za određeni problem. Predložio ih je 1975. godine John Henry Holland.
Genetski algoritmi temelje se na sljedećim idejama:
- Valjana rješenja problema mogu se predstaviti kao geni
- Kombiniranje omogućuje spajanje dvaju rješenja kako bi se dobilo novo valjano rješenje
- Selekcija se koristi za odabir optimalnijih rješenja pomoću neke funkcije prilagodbe
- Mutacije se uvode kako bi se destabilizirala optimizacija i izbjeglo lokalno minimum
Ako želite implementirati genetski algoritam, trebate sljedeće:
- Pronaći način kodiranja rješenja problema pomoću gena g∈Γ
- Na skupu gena Γ definirati funkciju prilagodbe fit: Γ→R. Manje vrijednosti funkcije odgovaraju boljim rješenjima.
- Definirati mehanizam kombiniranja za spajanje dvaju gena kako bi se dobilo novo valjano rješenje crossover: Γ2→Γ.
- Definirati mehanizam mutacije mutate: Γ→Γ.
U mnogim slučajevima, kombiniranje i mutacija su prilično jednostavni algoritmi za manipulaciju genima kao numeričkim sekvencama ili bitnim vektorima.
Specifična implementacija genetskog algoritma može se razlikovati od slučaja do slučaja, ali opća struktura je sljedeća:
- Odabrati početnu populaciju G⊂Γ
- Nasumično odabrati jednu od operacija koja će se izvesti u ovom koraku: kombiniranje ili mutacija
- Kombiniranje:
- Nasumično odabrati dva gena g1, g2 ∈ G
- Izračunati kombiniranje g=crossover(g1,g2)
- Ako fit(g)<fit(g1) ili fit(g)<fit(g2) - zamijeniti odgovarajući gen u populaciji s g.
- Mutacija - odabrati nasumični gen g∈G i zamijeniti ga s mutate(g)
- Ponavljati od koraka 2, dok ne dobijemo dovoljno malu vrijednost fit ili dok se ne dostigne ograničenje broja koraka.
Zadaci koji se obično rješavaju genetskim algoritmima uključuju:
- Optimizacija rasporeda
- Optimalno pakiranje
- Optimalno rezanje
- Ubrzavanje iscrpne pretrage
Nastavite učiti u sljedećim bilježnicama:
Idite na ovu bilježnicu kako biste vidjeli dva primjera korištenja genetskih algoritama:
- Pravedna podjela blaga
- Problem 8 kraljica
Genetski algoritmi koriste se za rješavanje mnogih problema, uključujući logističke i pretraživačke probleme. Ovo područje inspirirano je istraživanjima koja spajaju teme iz psihologije i računalnih znanosti.
"Genetski algoritmi su jednostavni za implementaciju, ali njihovo ponašanje je teško razumjeti." izvor Provedite istraživanje kako biste pronašli implementaciju genetskog algoritma, poput rješavanja Sudoku zagonetke, i objasnite kako funkcionira kao skica ili dijagram toka.
Pogledajte ovaj odličan video koji govori o tome kako računalo može naučiti igrati Super Mario koristeći neuronske mreže trenirane genetskim algoritmima. Više o učenju računala za igranje takvih igara naučit ćemo u sljedećem odjeljku.
Vaš cilj je riješiti tzv. Diofantovu jednadžbu - jednadžbu s cijelim korijenima. Na primjer, razmotrite jednadžbu a+2b+3c+4d=30. Trebate pronaći cijele korijene koji zadovoljavaju ovu jednadžbu.
Ovaj zadatak inspiriran je ovim postom.
Savjeti:
- Možete razmotriti korijene u intervalu [0;30]
- Kao gen, razmotrite korištenje popisa vrijednosti korijena
Koristite Diophantine.ipynb kao početnu točku.