Selecció per torneig (algorisme genètic)
De Viquipèdia
Selecció per Torneig
Els mètodes de selecció proporcional requereixen de dos passos
- Calcular l’aptitut mitjana.
- Calcular el valor esperat de còpies de cada individu.
La selecció per torneig realitza la selecció en base a comparacions directes dels individus. Es fácil de paral·lelitzar.
En aquest mètode, es trien grups d'individus de la població total, i els membres de cada grup competeixen entre ells. L'individu guanyador de cada torneig es reprodueix. Donada una població, s'agafen uniformement t individus de forma aleatòria i es tria el millor per a recombinar-lo (reproducció). El procés es repeteix tantes vegades com sigui necessari per arribar al nombre desitjat de població mitjana, és a dir, el nombre d'individus que es reproduiran.
Aquest mètode te varis avantatges: per una banda, és fàcil de codificar. A més, donat que els diferents tornejos són independents, es poden dur a terme de manera paral·lela (obtenint el màxim rendiment en arquitectures paral•leles). També cal destacar que permet ajustar fàcilment la pressió de selecció.
Hi ha dos tipus de selecció per torneig
- Determinista
- Probabilística
[edita] Selecció per torneig Determinista
Algorisme
1-Remenar els individus de la població 2-Escollir un nombre p d'individus (generalment 2). 3-Comparar-los sobre la base de la seva aptitud. 4-El guanyador del “torneig” és l'individu més apte. 5-Ha de remenar-se la població un total de p vegades per a seleccionar N pares.
[edita] Selecció per torneig Probabilística
El nombre d'individus que es tria (t) afecta la distribució de probabilitats d'una manera semblant a la pressió sel·lectiva en un mètode de rank. Valors més grans corresponen a una probabilitat major de sel·leccionar el millor individu en relació a la resta de la població. En Tatsuya Motoki calcula la pèrdua de diversitat esperada en la sel·lecció per torneig de la següent forma:
on N és el tamany de la població i t és el tamany del torneig.
Algorisme de la sel·lecció per torneig:
Triar ''t'' individus de la població aleatoriament Triar el millor individu del torneig amb probabilitat ''p'' Triar el segon millor individu amb probabilitat p*(1-p) Triar el tercer millor individu amb probabilitat p*((1-p)^2) i seguir ...
[edita] Anàlisi de la Selecció per Torneig
- La versió determinística garanteix que el millor individu serà seleccionat p vegades (sent p la grandària del torneig).
- És eficient i fàcil d'implementar.
- Pot introduir una pressió selectiva molt alta en la versió determinística ja que els individus dolents no tenen oportunitat de sobreviure.
- Pot regular-se la pressió selectiva variant la grandària del torneig. A mesura que s'augmenti la grandària del torneig es realitzarà major pressió selectiva.
Complexitat:
Cada competència requereix la selecció aleatòria de u número constant d’individus de la població O(1) Es requereixen n competències per a completar una generació. Per tant l’algoritme és O(n).
