Genetisk algoritm
En viktig del i den naturliga utvecklingen är den succesiva anpassningen till
livsbetingelserna. De bäst anpassade individerna bland alla individer i en art har störst möjlighet
att leva och fortplanta sig. Framgången för liv i alla olika former visar styrkan i denna process
Med det naturliga urvalet som förebild, har s.k. genetiska algoritmer utvecklats. Dessa kan
med framgång användas till att lösa många matematiskt svåra sökproblem - särskilt sådana där det
saknas analytiska metoder. Med hjälp av genetiska algoritmer lyckas man ofta hitta bra
lösningar där andra tekniker misslyckas.
En genetisk algoritm är...
En metod att, i en godtycklig rymd av möjliga lösningar, söka lösningar som ger så bra
måluppfyllelse som möjligt.
Några av verktygen som används i det naturliga urvalet av individer är:
- en mångfald av individer (varje "individ" är en möjlig lösning) i en population.
- en mekanism för att välja de bäst anpassade individerna.
- en mekanism för att skapa nya individer i populationen (vanligtvis med hjälp av
fortplantning).
Till vad kan man använda Genetiska Algoritmer?
Vanliga användningsområden för Genetiska Algoritmer är:
- Planeringsproblem
- Resursallokering
- Schemaläggning
- Receptproblem
- Turordningsproblem
Detta är alltså problem med många möjliga lösningar och som är svåra att angripa analytiskt.
Ett exempel på hur man gör.
Steg 1. Definiera vad en lösning skall innehålla.
Lösningen, för t.ex. ett turordningsproblem i en verktygsmaskin, måste visa i vilken ordning
artiklarna skall bearbetas. Antag att vi har 5 artiklar som skall bearbetas i maskinen.
Genom att definiera en kromosom med 5 gener där varje gen representerar en artikel och dess plats i sekvensen. Alltså gen 1 = artikel A, gen 2 = artikel B o.s.v.
Om varje gen sedan kan anta ett värde mellan 1 och 5, där 1 betyder "först i sekvensen"
och 5 sist så, har vi beskrivit vad lösningen skall innehålla.
Steg 2. Definiera vilka lösningar som är bra respektive dåliga.
Detta steg innebär att beskriva den "livsrymd" som individerna (lösningarna) skall leva i.
Det kan i exemplet innebära att vi skall ta hänsyn till hur lång tid det tar att ställa om maskinen
vid byte mellan artikel A till B, A till C eller B till E o.s.v. Det kan av andra skäl vara bättre om man
bearbetar A före D och D före C utan hänsyn till ställtid. Genom t.ex. enkla matematiska
funktioner kan värdera hur bra en lösning är. Genom att konstruera ett eller flera fiktiva
mätvärden som använder funktionerna kan den genetiska algoritmen avgöra
vilka lösningsförslag som är bra och vilka som är dåliga.
Steg 3. Att söka den bästa lösningen.
Efter de två första stegen har en genetisk algoritm den egenskapen att den kan hitta en "bra" lösning. Genom en iterativ process skapas nya "generationer" av lösningar. Med hjälp av de bästa
lösningarna i en generation skapas nästa generation av lösningar (fortplantnings-mekanismen).
Olika strategier finns för att algoritmen så effektivt som möjligt skall skapa bättre och bättre lösningar.
Till exempel kan nya lösningar skapas genom mutation. Itererandet avbryts efter att ett visst antal generationer skapats eller genom andra kriteria.
Till länksidan.
Tillbaks till förstasidan.