Ang Genetic Algorithms (GA) ay nakabatay sa isang evolutionary approach sa AI, kung saan ginagamit ang mga pamamaraan ng ebolusyon ng isang populasyon upang makuha ang pinakamainam na solusyon para sa isang partikular na problema. Ito ay iminungkahi noong 1975 ni John Henry Holland.
Ang Genetic Algorithms ay nakabatay sa mga sumusunod na ideya:
- Ang mga wastong solusyon sa problema ay maaaring i-representa bilang genes
- Ang Crossover ay nagbibigay-daan upang pagsamahin ang dalawang solusyon upang makabuo ng bagong wastong solusyon
- Ang Selection ay ginagamit upang pumili ng mas mainam na solusyon gamit ang isang fitness function
- Ang Mutations ay ipinapasok upang ma-destabilize ang optimization at makalabas sa local minimum
Kung nais mong mag-implement ng Genetic Algorithm, kailangan mo ng mga sumusunod:
- Maghanap ng paraan upang i-code ang mga solusyon sa problema gamit ang genes g∈Γ
- Sa set ng genes Γ, kailangang magtakda ng fitness function fit: Γ→R. Ang mas mababang halaga ng function ay tumutukoy sa mas mainam na solusyon.
- Magtakda ng mekanismo ng crossover upang pagsamahin ang dalawang genes upang makabuo ng bagong wastong solusyon crossover: Γ2→Γ.
- Magtakda ng mekanismo ng mutation mutate: Γ→Γ.
Sa maraming kaso, ang crossover at mutation ay mga simpleng algorithm upang manipulahin ang genes bilang mga numeric sequence o bit vectors.
Ang partikular na implementasyon ng genetic algorithm ay maaaring magbago depende sa kaso, ngunit ang pangkalahatang istruktura ay ang mga sumusunod:
- Pumili ng panimulang populasyon G⊂Γ
- Random na pumili ng isa sa mga operasyon na isasagawa sa hakbang na ito: crossover o mutation
- Crossover:
- Random na pumili ng dalawang genes g1, g2 ∈ G
- Kalkulahin ang crossover g=crossover(g1,g2)
- Kung fit(g)<fit(g1) o fit(g)<fit(g2) - palitan ang kaukulang gene sa populasyon ng g.
- Mutation - pumili ng random na gene g∈G at palitan ito ng mutate(g)
- Ulitin mula sa hakbang 2, hanggang makuha ang sapat na maliit na halaga ng fit, o hanggang maabot ang limitasyon sa bilang ng mga hakbang.
Ang mga gawain na karaniwang nalulutas gamit ang Genetic Algorithms ay kinabibilangan ng:
- Pag-optimize ng iskedyul
- Optimal na pag-iimpake
- Optimal na pagputol
- Pagpapabilis ng exhaustive search
Ipagpatuloy ang iyong pag-aaral sa mga sumusunod na notebook:
Pumunta sa notebook na ito upang makita ang dalawang halimbawa ng paggamit ng Genetic Algorithms:
- Makatarungang paghahati ng kayamanan
- 8 Queens Problem
Ang Genetic Algorithms ay ginagamit upang malutas ang maraming problema, kabilang ang mga problema sa logistics at paghahanap. Ang larangang ito ay inspirasyon ng pananaliksik na pinagsama ang mga paksa sa Psychology at Computer Science.
"Ang genetic algorithms ay madaling i-implement, ngunit mahirap maintindihan ang kanilang kilos." source Maghanap ng isang implementasyon ng genetic algorithm tulad ng paglutas ng Sudoku puzzle, at ipaliwanag kung paano ito gumagana gamit ang isang sketch o flowchart.
Panoorin ang napakagandang video na ito na nagpapakita kung paano natututo ang computer na maglaro ng Super Mario gamit ang neural networks na sinanay ng genetic algorithms. Matututo tayo ng higit pa tungkol sa computer na natututo maglaro ng mga ganitong laro sa susunod na seksyon.
Ang iyong layunin ay lutasin ang tinatawag na Diophantine equation - isang equation na may mga integer na ugat. Halimbawa, isaalang-alang ang equation na a+2b+3c+4d=30. Kailangan mong hanapin ang mga integer na ugat na tumutugon sa equation na ito.
Ang takdang-araling ito ay inspirasyon ng post na ito.
Mga Pahiwatig:
- Maaari mong isaalang-alang ang mga ugat na nasa interval na [0;30]
- Bilang gene, isaalang-alang ang paggamit ng listahan ng mga halaga ng ugat
Gamitin ang Diophantine.ipynb bilang panimulang punto.