Generația
Au atins ținta
Cea mai rapidă sosire
Cea mai mică distanță
  • În zbor
  • Au atins ținta
  • Prăbușite
  • Cel mai bun zbor din ultima generație
  • Au atins ținta
  • Prăbușite

Mai multe despre algoritmii genetici

Laborator de algoritmi genetici

Un algoritm genetic rezolvă o problemă așa cum evoluția modelează ființele vii: încearcă multe răspunsuri aleatorii, le păstrează pe cele mai bune, le amestecă, schimbă câteva bucăți la întâmplare și repetă. Aici răspunsurile sunt rachete. Fiecare urmează o listă de impulsuri aleatorii și nimic altceva, iar la început se rostogolesc fără țintă. Apăsați Pornește și urmăriți cum populația se îmbunătățește din generație în generație, până când majoritatea rachetelor ocolesc pereții în arc și ajung la țintă, fără ca cineva să le spună încotro să zboare. Apasă Pornește și urmărește cum o populație de rachete încearcă să atingă ținta verde. Fiecare rachetă urmează doar genele sale, o listă de mici impulsuri, câte unul pentru fiecare moment al zborului. După fiecare zbor, rachetele care au ajuns cel mai aproape și, mai ales, cele care au ajuns la țintă au cele mai mari șanse să devină părinții generației următoare; genele lor sunt amestecate, iar câteva sunt schimbate la întâmplare. Generația următoare sare peste restul unui zbor. Trage pe câmp ca să desenezi un perete și dă clic pe un perete ca să-l elimini.

Cum funcționează

  1. Alegeți obstacolele sau trageți pe câmp pentru a vă desena propriii pereți și setați populația, rata de mutație și durata de viață.
  2. Apăsați Pornește și urmăriți zborul fiecărei generații; Generația următoare sare peste restul unui zbor.
  3. Urmăriți în casete și în grafic proporția care atinge ținta și încercați alte rate de mutație și alte metode de selecție.

Cum evoluează rachetele

Fiecare rachetă poartă gene: câte un mic impuls pentru fiecare moment al zborului. Genele primei generații sunt aleatorii. După zbor, fiecare rachetă primește un scor de fitness: cel mai mare pentru o sosire timpurie, apoi cu atât mai mare cu cât a terminat mai aproape de țintă, și împărțit la zece după o prăbușire. Părinții generației următoare sunt aleși la întâmplare, dar rachetele mai adaptate au șanse mai mari să fie alese. Fiecare copil preia prima parte a genelor de la un părinte și restul de la celălalt, iar câteva gene sunt înlocuite cu impulsuri aleatorii: mutații. De-a lungul generațiilor, planurile de zbor bune se răspândesc și se îmbunătățesc.

Ce schimbă setările

O populație mai mare explorează simultan mai multe planuri de zbor și riscă mai puțin să se blocheze, dar fiecare generație durează mai mult. Rata de mutație echilibrează explorarea și păstrarea a ceea ce funcționează: fără mutație, populația rămâne repede fără idei noi, iar cu prea multă uită zborurile bune mai repede decât le poate găsi. Selecția prin ruletă alege părinții proporțional cu fitnessul, în timp ce un turneu o alege pe cea mai bună dintre trei rachete aleatorii, ceea ce este mai puțin sensibil la modul în care este scalat fitnessul. Elitismul copiază cea mai bună rachetă neschimbată în generația următoare, astfel încât cel mai bun rezultat nu se înrăutățește niciodată.

Întrebări frecvente

De ce se blochează rachetele în spatele pereților decalați?

Fitnessul lor măsoară distanța în linie dreaptă până la țintă, așa că o rachetă care zboară în peretele de sub țintă obține un scor mai bun decât una care se îndepărtează ca să găsească deschiderea. Populația se îngrămădește în acea fundătură, un optim local. Populațiile mai mari, mai multă mutație sau selecția prin turneu o ajută să scape, iar un fitness care ar măsura drumul real în jurul pereților ar evita capcana. Alegerea unei funcții de fitness bune este partea cea mai grea a folosirii unui algoritm genetic.

Așa funcționează evoluția în natură?

În linii mari, da: variația prin mutație și recombinare, moștenirea genelor și selecția celor mai adaptați sunt ingredientele lui Darwin. Diferențele sunt însă mari. Natura nu are nicio țintă și nicio formulă de fitness, doar supraviețuire și reproducere, iar genomurile reale construiesc corpuri prin dezvoltare, în loc să enumere acțiuni.

La ce se folosesc algoritmii genetici?

La probleme cu un spațiu uriaș de răspunsuri posibile și o modalitate simplă de a evalua un candidat: modelarea antenelor, aripilor și pieselor auto, întocmirea orarelor, reglarea setărilor altor algoritmi, proiectarea rețelelor neuronale și crearea de artă și de strategii de joc. Antena evoluată de NASA pentru sateliții ST5 din 2006 este un exemplu celebru.

De ce cea mai bună rachetă zboară uneori mai prost în generația următoare?

Fără elitism, cea mai bună rachetă nu este copiată: genele ei supraviețuiesc doar amestecate cu altele și, eventual, mutate, așa că generația următoare îi poate pierde zborul exact. Cu elitismul activat, cea mai bună rachetă este păstrată neschimbată și cel mai bun rezultat nu se înrăutățește niciodată.

Se trimite ceva către un server?

Nu. Rachetele zboară și evoluează în browserul dumneavoastră, iar pereții pe care îi desenați rămân în stocarea locală a acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor