Turneringsurval
Turneringsurval är en metod för att välja en individ från en population av individer i en genetisk algoritm . Turneringsurval innebär att köra flera "turneringar" bland ett fåtal individer (eller " kromosomer ") utvalda slumpmässigt från befolkningen. Vinnaren av varje turnering (den med bäst kondition) utses för crossover . Urvalstryck , ett probabilistiskt mått på en kromosoms sannolikhet att delta i turneringen baserat på storleken på deltagarevalspoolen, justeras enkelt genom att ändra turneringsstorleken. Anledningen är att om turneringsstorleken är större så har svaga individer en mindre chans att bli utvalda, eftersom om en svag individ väljs ut för att vara med i en turnering är det större sannolikhet att en starkare individ också är med i den turneringen.
Metoden för val av turnering kan beskrivas i pseudokod:
välj k (turneringsstorleken) individer från befolkningen slumpmässigt välj den bästa individen från turneringen med sannolikhet p välj den näst bästa individen med sannolikhet p*(1-p) välj den tredje bästa individen med sannolikhet p*((1- p)^2) och så vidare
Deterministiskt turneringsval väljer den bästa individen (när p = 1) i någon turnering. Ett 1-vägs turneringsval ( k = 1) motsvarar slumpmässigt urval. Det finns två varianter av urvalet: med och utan ersättning. Varianten utan ersättning garanterar att när man väljer N individer från en population av N element, deltar varje individ i exakt k turneringar. En algoritm föreslås i. Observera att beroende på antalet valda element inte urval utan ersättning att ingen individ väljs mer än en gång. Det garanterar bara att varje individ har lika stor chans att delta i samma antal turneringar.
I jämförelse med den (stokastiska) fitnessproportionella urvalsmetoden , implementeras turneringsval ofta i praktiken på grund av dess brist på stokastiskt brus.
Turneringsurval har flera fördelar jämfört med alternativa urvalsmetoder för genetiska algoritmer (till exempel fitnessproportionellt urval och belöningsbaserat urval ): det är effektivt att koda, fungerar på parallella arkitekturer och gör att urvalstrycket enkelt kan justeras. Turneringsurval har också visat sig vara oberoende av skalningen av den genetiska algoritmens fitnessfunktion (eller " objektiv funktion" ) i vissa klassificeringssystem.