Selecció per torneig

La selecció per torneig és una estratègia de selecció utilitzada per seleccionar els candidats més aptes d'una població en un algoritme genètic. Els candidats seleccionats passen a la següent generació.^[1][2] En una selecció de torneig de X camins, es seleccionen x individus i es realitza un torneig entre ells. Només es tria el candidat més apte entre els seleccionats i es passa a la següent generació. D'aquesta manera es realitzen molts tornejos d'aquest tipus, obtenint cada vegada una selecció de candidats que passa a la següent generació. La manera en què són seleccionats els individus és fàcilment ajustable d'acord amb la quantitat d'individus participants en el torneig. Si la quantitat d'individus que participen en el torneig és més gran, els individus febles té una probabilitat menor de ser seleccionats.

Variants

La selecció determinista per tornejos selecciona el millor individu (quan p = 1) en qualsevol torneig.

Una selecció en un torneig unidireccional ( k = 1) és equivalent a una selecció aleatòria.

Hi ha dues variants de la selecció: amb i sense reemplaçament. La variant sense reemplaçament garanteix que, en seleccionar N individus d'una població de N elements, cada individu participa exactament en k tornejos. Es proposa un algoritme a.^[3] Cal tenir en compte que, depenent del nombre d'elements seleccionats, la selecció sense reemplaçament no garanteix que cap individu sigui seleccionat més d'una vegada. Simplement garanteix que cada individu tingui la mateixa probabilitat de participar en el mateix nombre de tornejos.

Avantatges

En comparació amb el mètode de selecció proporcional per aptitud (estocàstica), la selecció per tornejos sovint s'implementa a la pràctica a causa de la seva manca de soroll estocàstic.^[4]

La selecció per tornejos té diversos avantatges respecte als mètodes de selecció alternatius per als algoritmes genètics (per exemple, la selecció proporcional a l'aptitud i la selecció basada en la recompensa: és eficient de codificar, funciona en arquitectures paral·leles i permet ajustar fàcilment la pressió de selecció.^[5] També s'ha demostrat que la selecció per tornejos és independent de l'escalat de la funció d'aptitud de l'algoritme genètic (o " funció objectiu ") en alguns sistemes classificadors.^[6][7]

Mètodes de selecció proporcional

Els mètodes de selecció proporcional requereixen dos passos:^[4]

• 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. És 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

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 amb 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:

${\displaystyle 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

• 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 d'un nombre constant d'individus de la població O(1); calen n competències per a completar una generació. Per tant, l'algoritme és O(n).