Selecció per torneig
 |
L'article necessita algunes millores en la redacció de la introducció. (Col·laboreu-hi!) Hi manca una introducció que presenti el concepte i expliqui de què parla l'article. Cal revisar-ne també el format, és una mica càotic |
Els mètodes de selecció proporcional requereixen de dos passos:
- Calcular l'aptitud mitjana.
- Calcular el valor esperat de còpies de cada individu.
La selecció per torneig realitza la selecció basant-se en 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 manera aleatòria i es tria el millor per a recombinar-lo (reproducció). El procés es repeteix tantes vegades com sigui necessari per a arribar al nombre desitjat de població mitjana, és a dir, el nombre d'individus que es reproduiran.
Aquest mètode te diversos avantatges: per una banda, és fàcil de codificar i, atès 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 i probabilística
Selecció per torneig determinista
Algorisme:
- Remenar els individus de la població
- Escollir un nombre p d'individus (generalment 2).
- Comparar-los sobre la base de la seva aptitud.
- El guanyador del torneig és l'individu més apte.
- Ha de remenar-se la població un total de p vegades per a seleccionar N parells.
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ó selectiva en un mètode de rank. Valors més grans corresponen a una probabilitat superior de seleccionar el millor individu en relació a la resta de la població.
Tatsuya Motoki calcula la pèrdua de diversitat esperada en la selecció per torneig de la manera següent:
<math>D_T(t,N) = \frac{1}{N} \sum_{k=0}^N \left(1-\frac{k^t-(k-1)^t}{N^t} \right)^N</math>
on N és la mida de la població i t és la mida del torneig.
Algorisme de la selecció per torneig:
- Triar t individus de la població aleatòriament
- 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 així successivament.
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à més pressió selectiva.
Complexitat
Cada competència requereix la selecció aleatòria de un nombre 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).