Et hurtigt eksempel på genetisk udvikling i JavaScript: Lad os lave en baby.

"Mutationsprocessen er den eneste kendte kilde til de nye materialer med genetisk variabilitet og dermed evolution." - Dobzhansky, 1957.

Genetisk evolution algoritmer er virkelig fascinerende for mig. Evnen til at programmere virtuelt DNA er bare en fænomenal bedrift ved datalogi. Evnen til at skrive i kode Darwins teori om evolution og faktisk se en overlevelse af den mest modne model i handling er bare forbløffende.

Jeg har aldrig rørt ved genetiske algoritmer før og besluttet, at det var på tide, at jeg startede. Og hvilket bedre sted at starte end det faktiske, start, ikke? I denne tutorial vil jeg oprette en 'stick', og den stick ønsker at nå en 'cirkel'. Fra det, hvad du vil, men jeg skriver familievenlige tutorials, og det vil forblive på den måde.

Jeg tager utrolig tung indflydelse fra The Coding Train: Coding Challenge # 29 som inspiration til dette. Link til det her. Han blev inspireret af Smart Rockets, så selvom jeg ikke fremstiller noget nyt eller originalt, håber jeg, at det kan fungere som et eksempel på en genetisk evolution-algoritme. Jeg bruger P5.JS-biblioteket, som jeg ville opsummere som et visuelt JavaScript-bibliotek.

Før jeg kan oprette nogen form for genetisk algoritme, skal jeg først konfigurere den aktuelle indstilling. Først opretter jeg en meget enkel HTML-side.

Jeg har to biblioteker til P5. Hoved håndterer tegningen til skærmen, øjeblikkelighed af variabler osv. En pind er den linje, der vil udvikle sig, en population er en samling af pinde, og dna er det, jeg vil overveje kernen i den genetiske algoritme. Lad os se på koden til Stick:

Så en pind har nogle grundlæggende funktioner. Den skal være i stand til at bevæge sig, så den har en bevægelsesmotor (med mangel på et bedre udtryk) i hastighed, acceleration og positionsvariabler. I øjeblikket styres al bevægelse af den mystiske DNA-funktion. Før vi kommer til DNA, lad os se på populationen:

Befolkning er virkelig ikke så interessant. Det skaber 25 pinde, som jeg mener er tilstrækkeligt for en befolkning, og derefter flytter dem på skærmen. At bryde ingen barrierer med denne funktion! DNA:

På dette tidspunkt gør DNA stort set intet. Én pind får et DNA, og en DNA har et sæt på 200 gener, hvilket er længden på en levetid for min lille pind. Bare rolig, der vil blive tilføjet mere efterhånden. Hovedfilen:

Så Main gør nogle få ting her. For det første er vi nødt til at skabe en ny generation af pinde, som er en øjeblikkelig befolkning, og så skaber vi vores cirkel, som pindene sigter mod senere ned ad linjen. Derefter trækker vi alt på skærmen med den ekstra mulighed for at dræbe og skabe en ny generation, hver gang deres livscyklus slutter.

Så hvis vi kører dette, som det for tiden er, får vi dette:

De forvirrede små pinde

På dette tidspunkt er det overhovedet ikke en genetisk algoritme. I stedet er det et sæt pinde, der bevæger sig på tilfældigt valgte vektorer, med en prik tegnet på skærmen. Så lad os tilføje den genetiske del.

Så vi ønsker, at den pind, der gør den længst, tættest på cirklen, skal være den pind, der overfører dens gener til sine børn. Dette er dybest set overlevelse af de smukkeste: Den, der overlever den længste, er den, der videregiver deres gener.

Så vi kan begynde at implementere dette ved at give hver pind en ny variabel: fitness.

var fitness = 0

Træning beregnes ud fra pindens aktuelle position i forhold til cirklens (mål) position. Vi kan implementere dette som en funktion til at beregne Fitness på hver stick.

this.calculateFitness = funktion () {
var afstand = dist (this.pos.x, this.pos.y, target.x, target.y)
this.fitness = 1 / afstand
}

Nu har vi pinde, der har en kondition, - dvs. de har bedre gener, fordi de overlevede længere. Så nu har vi brug for en måde at være i stand til at gengive disse pinde med gener i øverste niveau. Indtast poolen:

Så denne pool er relativt ligetil i koncept. Vi har allerede fundet ud af, at de mest succesrige gener er dem, der er tættest på cirklen. Jo tættere pinden er, jo flere gange bliver det genom indført i puljen, og jo mere sandsynligt er det at gengive sig. En pind, der gjorde det til 5% af vejen, vil have en 5% chance for at gengive sig, mens en pind, der gjorde det til 70% af vejen, har en 70% chance for at gengive sig. Jeg håber, jeg har forklaret det godt nok. Mere succesrig pind = bedre chance for at blive genfødt som en del af en ny pind.

Ovenstående er to nye funktioner. Selektion er, som navnet antyder, valg af overordnede gener fra genpuljen. Disse gener kombineres derefter til dannelse af et nyt DNA i crossover, som igen tildeles den nye pind! Det er stort set det, da vi ønsker at holde dette relativt enkle og rudimentære.

Temmelig sej, vores pinde er nu i stand til at tage det bedste fra forgængernes evner og bruge dem til at finde cirklen! Hvis vi nu ser på det i handling:

De stadig forvirrede, men lidt smartere pinde.

Efter flere dusin iterationer begynder det at se ud som om de er ved at dø, da der kun er nogle få linjer synlige. Men det er ikke tilfældet: jo lettere pinden betyder, at flere pinde følger nøjagtigt den samme sti. Dette kan forventes, da vi har en relativt begrænset pool af gener.

De meget smarte alfapæle.

Jo længere der bliver tilbage, jo mere vises der kun en pind på skærmen. Denne pind repræsenterer den optimale pind! Den valgte pind. Her er de kulminationen af ​​vores genetiske algoritme:

Genius stick (r)!

Så det er en genetisk evolutionsalgoritme, der er skrevet helt i browseren! Det er ikke et perfekt eksempel på genetisk evolution, men det er et fint eksempel på det på arbejdet. Vores lille pind kan nu fortsætte for at få cirklen, og hvad der følger derefter, er ikke et emne for i dag.

Som nævnt i starten er dette stærkt påvirket af The Coding Train. Link til deres repo.

Min fulde kode.