Selección por torneos

La selección por torneos es un método que se utiliza para seleccionar un individuo de una población de individuos en un algoritmo genético.[1]​ La selección por torneos implica realizar varios "torneos" entre algunos individuos (o 'cromosomas') escogidos al azar de la población. El ganador de cada torneo (el de mayor aptitud) es seleccionado para el cruzamiento (crossover). La manera en que son seleccionados los individuos es fácilmente ajustable acorde con la cantidad de individuos participantes en el torneo. Si la cantidad de individuos que participan en el torneo es mayor, los individuos débiles tiene una probabilidad menor de ser seleccionados.

Introducción

Un torneo puede ser representado a través del modelo visual de una gráfica dirigida, de tal manera que los vértices representarán los diferentes tipos de individuos de una población, mientras que las aristas entre cualesquiera dos vértices indicarán una relación competitiva entre dos tipos de individuos de la población, de modo tal que, entre cada pareja de individuos en competencia podemos elegir un ganador. Es decir, dados dos individuos x, y, tales que x → y, diremos que x gana sobre y. Estos modelos, con las cuales podemos establecer  relaciones de  competencia provienen de  la Teoría de Gráficas.

Metodología básica de una selección por torneos.
Selección por Torneos : Caricaturización del algoritmo de selección por torneos. Idea General.

Metodología.

El método de selección por torneos puede ser descrito con el siguiente pseudo código:

  • Escoger k (la cantidad de individuos participantes en el torneo) individuos de la población aleatoriamente.
  • Escoger el individuo más apto del torneo con probabilidad p
  • Escoger el segundo individuo más apto con probabilidad p(1-p)
  • Escoger el k-esimo individuo más apto con probabilidad p(1-p)^k

La selección por torneo determinista selecciona al mejor individuo (cuándo p = 1) en cualquier torneo. Un torneo con k=1 es equivalente a una selección aleatoria. El individuo escogido puede ser eliminado de la población si se desea, al no realizarse dicha acción un individuo puede ser seleccionado varias veces. En comparación con el método de selección proporcional, la selección de torneo es frecuentemente preferida para ser implementada en la práctica debido a su carencia de ruido estocástico.[2]​

La selección por torneos tiene varios beneficios sobre métodos de selección alternativos para algoritmos genéticos (por ejemplo, la selección basada en aptitud y la basada en recompensa): es eficiente, funciona en arquitecturas paralelas y permite que la presión de selección sea fácilmente ajustable.Se ha demostrado que la selección por torneos es independiente de la escala de la función de aptitud o función objetivo de un algoritmo genético en algunos sistemas clasificadores.[3]​[4]​

Referencias

  1. ↑ Miller, Brad; Goldberg, David (1995). «Genetic Algorithms, Tournament Selection, and the Effects of Noise». Complex Systems 9: 193-212. 
  2. ↑ Blickle, Tobias; Thiele, Lothar (diciembre de 1996). «A Comparison of Selection Schemes Used in Evolutionary Algorithms». Evolutionary Computation 4 (4): 361-394. doi:10.1162/evco.1996.4.4.361. 
  3. ↑ Miller, edited by Erick Cant-Paz, James A. Foster, Kalyanmoy Deb, Lawrence David Davis, Rajkumar Roy, Una-May OReilly, Hans-Georg Beyer, Russell Standish, Graham Kendall, Stewart Wilson, Mark Harman, Joachim Wegener, Dipankar Dasgupta, Mitch A. Potter, Alan C. Schultz, Kathryn A. Dowsland, Natasha Jonoska, Julian (2003). Genetic and Evolutionary Computation GECCO 2003 00 Genetic and Evolutionary Computation Conference Chicago, IL, USA, July 1216, 2003 Proceedings, Part II. Berlin: Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-45110-5. 
  4. ↑ Goldberg, David; Deb, Kalyanmoy (1991). «A comparative analysis of selection schemes used in genetic algorithms». Foundations of Genetic Algorithms: 69-93.