Selecció per torneig

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 té 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[modifica | modifica el codi]

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[modifica | modifica el codi]

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:

D_T(t,N) = \frac{1}{N} \sum_{k=0}^N \left(1-\frac{k^t-(k-1)^t}{N^t} \right)^N

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[modifica | modifica el codi]

  • 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[modifica | modifica el codi]

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).