Utvikling av en liten bil

Dette var en utrolig fascinerende animasjon av en genetisk algoritme for å lage en bil, og klart det kuleste jeg har funnet på nettet på en stund. Prøv å åpne flere vinduer med den og se hvor den beste bilen utvikler seg. (Det går gjerne noen generasjoner før den kommer noen vei i det hele tatt).

Programmereren sier:

This is a GA I wrote to design a little car for a specific terrain. It runs in real-time in Flash.

The fitness function is the distance travelled before the red circles hit the ground, or time runs out. The degrees of freedom are the size and inital positions of the four circles, and length, spring constant and damping of the eight springs. The graph shows the "mean" and "best" fitness.

Ben "could watch this for hours" Murphy

Kult! Utrolig stilig å vise resultatet underveis på denne måten.

Kult! Men vekter den de forskjellige generasjonene? For det ser ut som at den muterer seg frem til noe som fungerer bra, med lavt tyngdepunkt og god avstand mellom hjulene, så muterer den til noe dårligere neste generasjon. Det virker ikke som at den sjekker tendensen for hver parameterendring. Eller gjør den det? Jeg må se mer på den.

Stilig! Darwinisme i praksis.

Esme skrev:

Kult! Men vekter den de forskjellige generasjonene? For det ser ut som at den muterer seg frem til noe som fungerer bra, med lavt tyngdepunkt og god avstand mellom hjulene, så muterer den til noe dårligere neste generasjon. Det virker ikke som at den sjekker tendensen for hver parameterendring. Eller gjør den det? Jeg må se mer på den.

Begynner den ikke på nytt hver gang? Den muterer frem til den får funksjonene til en bil, og så starter den på nytt. Noen av bilene lignet på min, desverre.

Nå har den gått til nå, og det er klart at den stegvis (hva nå sjargongen blant evolusjonister er) utvikler seg i riktig retning ja. Så den må vekte mellom de forskjellige "grenene" i treet, og så teste ut kombinasjoner i en gren. Tenker jeg. Eller kanskje finner jeg på.

Jeg kjeder meg.

Den ene bilen min er en sprettball, men de andre 4 har mutert veldig fint utover kvelden.

Kult.
Jeg laget en gang en demo hvor et ord evolverer i sammenligning med tilfeldig valgte bokstaver for å vise forskjellen på evolusjon og "tilfeldighet" i kreasjonistsjargong, men denne var mer visuell. Skulle ønske han hadde lagt ut litt mer om prosessen, det føles som det er noe som mangler ennå.

Jeg hatt en kjørende på jobb siden jeg fant den, og den har blitt ganske flink nå altså. Jeg håper virkelig han faktisk lager en versjon der man kan fikle med parameterene, eller aller helst legger ut kildekoden så man kan fikle med alt sammen.

Ben "Mount Improbable Grand Prix" Murphy

Jeg skulle gjerne visst mer om løsningsrepresentasjonen, og hva slags crossover- og seleksjonstyper som er brukt. Står det mer info noe sted? :har lett sånn passe:

Benmurphy skrev:

Jeg hatt en kjørende på jobb siden jeg fant den, og den har blitt ganske flink nå altså. Jeg håper virkelig han faktisk lager en versjon der man kan fikle med parameterene, eller aller helst legger ut kildekoden så man kan fikle med alt sammen.
Ben "Mount Improbable Grand Prix" Murphy

Yep. Unweaving the source code in no way diminishes its beauty.

Den regner vel ut den beste løsningen etter et bestemt antall forsøk, så beholder den det beste, og tester "villt" utifra denne et bestemt antall forsøk til, for så å beholde den beste igjen, som blir bedre enn den forrige beste osv?? Etterhvert vil algoritmen har større sammenligningsgrunnlag og progresjonen øker i tempo. Eller? :gjetter:

Sånn virker det i allefall logisk for meg, men vet ikke om dette stemmer. Eneste sammenligningsgrunnlag for meg er algoritmene som brukes ved vekting av kostnader i nettverk, noen som ikke er helt det samme..

Joika skrev:

Den regner vel ut den beste løsningen etter et bestemt antall forsøk, så beholder den det beste, og tester "villt" utifra denne et bestemt antall forsøk til, for så å beholde den beste igjen, som blir bedre enn den forrige beste osv?? Etterhvert vil algoritmen har større sammenligningsgrunnlag og progresjonen øker i tempo. Eller? :gjetter:

En genetisk algoritme jobber på «individer», som er representasjoner av mulig løsninger. I starten (generasjon #0) er disse løsningene tilfeldig generert. Alle individene (kalt populasjonen) blir testet på problemet som skal løses, og blir tildelt en score utfra hvor godt de løser dette problemet. Funksjonen som regner ut denne scoren kalles fitness-funksjonen, og en korrekt beregning av fitness er viktig for at algoritmen skal lykkes.

Når alle individer/løsniner er vurdert, får disse «parre seg» for å lage en ny generasjon løsninger, ved at biter fra en løsning kombineres med biter fra en annen. Funksjonen som gjør denne parringen kalles vanligvis for en crossover-funksjon (siden den typisk krysser to løsninger). Utvalget av hvem som får parre seg er slik at individer som scoret høyt har større sjanse til å få formert seg, men alle har en viss sjanse. Noen GA-er viderefører også for eksempel de 5 beste individene direkte til neste generasjon for å ikke miste gode løsninger.

Til slutt utsettes noen av individene for mutasjon ved å tilfeldig endre på noen løsninger, dette for å forsikre en viss diversitet i populasjonen og dermed forsøke å unngå for tidlig stagnasjon. En god mutasjonsfunksjon er dermed også viktig for et godt resultat.

En genetisk algoritme vil typisk stagnere etter en god del generasjoner, og jeg syns egentlig denne ser ut til å gjøre det ganske fort. Men det er lenge siden jeg drev med dette, kjenner jeg. :gammel:

Kult! Dette var en veldig god illustrasjon på noe jeg av og til har behov for (men gjerne sliter med) å forklare overfor for eksempel familien.

torsk skrev:

En genetisk algoritme jobber på «individer», som er representasjoner av mulig løsninger. I starten (generasjon #0) er disse løsningene tilfeldig generert. Alle individene (kalt populasjonen) blir testet på problemet som skal løses, og blir tildelt en score utfra hvor godt de løser dette problemet. Funksjonen som regner ut denne scoren kalles fitness-funksjonen, og en korrekt beregning av fitness er viktig for at algoritmen skal lykkes.

Når alle individer/løsniner er vurdert, får disse «parre seg» for å lage en ny generasjon løsninger, ved at biter fra en løsning kombineres med biter fra en annen. Funksjonen som gjør denne parringen kalles vanligvis for en crossover-funksjon (siden den typisk krysser to løsninger). Utvalget av hvem som får parre seg er slik at individer som scoret høyt har større sjanse til å få formert seg, men alle har en viss sjanse. Noen GA-er viderefører også for eksempel de 5 beste individene direkte til neste generasjon for å ikke miste gode løsninger.

Til slutt utsettes noen av individene for mutasjon ved å tilfeldig endre på noen løsninger, dette for å forsikre en viss diversitet i populasjonen og dermed forsøke å unngå for tidlig stagnasjon. En god mutasjonsfunksjon er dermed også viktig for et godt resultat.

En genetisk algoritme vil typisk stagnere etter en god del generasjoner, og jeg syns egentlig denne ser ut til å gjøre det ganske fort. Men det er lenge siden jeg drev med dette, kjenner jeg. :gammel:

Hm. Morsomt.

Bortsett fra den tilfeldige genereringen innledningsvis og muteringen, så er prinsippene mye det samme som jeg lærer på skolen nå.