Genetisk algoritme

En genetisk algoritme (GA) er en søkeheuristikk som etterligner prosessen ved naturlig evolusjon. Genetiske algoritmer tilhører den større klassen evolusjonære algoritmer (EA), som genererer løsninger på optimaliserings problemer ved hjelp av teknikker inspirert av naturlige evolusjon, slik som arv, mutasjon, utvalg, og paring ("crossover").

Gjennomgang

Genetiske algoritmer begynner med et sett av k tilfeldig genererte tilstander kalt populasjon. Hver tilstand, eller individ, er representert som en tekststreng - mest vanlig er bruk av 0 og 1, men andre løsninger er også mulig. Evolusjonen starter med populasjonen og skjer i generasjoner. For hver generasjon blir hvert individ vurdert basert på en fitness funksjon. Individer blir valgt fra populasjonen (basert på deres fitness) og modifisert for å lage en ny populasjon. Den nye populasjonen blir så brukt i neste iterasjon av algoritmen. Vanligvis avslutter algoritmen enten når den har nådd et gitt antall generasjoner har blitt produsert, eller en tilfredstillende fitness nivå har blitt oppnådd for populasjonen. Hvis algoritmen har avsluttet på grunn av et maksimum antall generasjoner, er det ikke sikkert at en tilfredstillende løsning har blitt oppnådd.