genetisk algoritm

(genetic algorithm, förkortas ibland GA) – program som löser problem genom att testa och förädla slumpmässigt fram­tagna lösnings­förslag. Förebilden är den bio­logiska evolutionen med naturligt urval och mutationer. – Tekniken används på problem som inte kan lösas på rimlig tid med vanlig programmering, men där det är enkelt att utvärdera en föreslagen lösning (se NP). Pro­gram för genetiska algoritmer slumpar fram miljon­tals godtyckliga lösningar som testas. De bästa får ”para sig” med varandra (man sätter ihop ena halvan av en lösning med andra halvan av en annan) och ”avkomman” testas på samma sätt. Pro­grammet gör också ”mutationer”, alltså slump­artade förändringar av existerande lösningar (detta för att förebygga sub­optimering). – Genom att köra programmet om och om igen och bearbeta de bästa lösningarna kan man till sist få fram använd­bara lösningar på problem som annnars skulle vara ohanterliga. En förut­sättning är att lösningen går att formulera i ett fast format, till exempel ett bestämt antal tecken. Tekniken har använts inom metallurgi (för att få fram legeringar med önskade egen­skaper) och för planering och optimering (där ett visst antal element ska ordnas på bästa möjliga sätt). – Jäm­för med genetisk pro­gram­mering.

[algoritmer] [forskning och experimentell teknik] [ändrad 9 januari 2018]