La selección de torneo es un método para seleccionar un individuo de una población de individuos en un algoritmo genético . [1] La selección de un torneo implica la realización de varios "torneos" entre unos pocos individuos (o " cromosomas ") elegidos al azar de la población. El ganador de cada torneo (el que tiene la mejor condición física) es seleccionado para el cruce . Presión de selección, una medida probabilística de la probabilidad de participación de un cromosoma en el torneo basada en el tamaño del grupo de selección de participantes, se ajusta fácilmente cambiando el tamaño del torneo, la razón es que si el tamaño del torneo es mayor, los individuos débiles tienen menos posibilidades de ser seleccionados , porque, si se selecciona a un individuo débil para participar en un torneo, existe una mayor probabilidad de que un individuo más fuerte también esté en ese torneo.
El método de selección del torneo se puede describir en pseudocódigo:
elegir k (el tamaño del torneo) individuos de la población al azarelegir al mejor individuo del torneo con probabilidad pelegir el segundo mejor individuo con probabilidad p * (1-p)elija el tercer mejor individuo con probabilidad p * ((1-p) ^ 2)y así
La selección de torneo determinista selecciona al mejor individuo (cuando p = 1) en cualquier torneo. Una selección de torneo de ida ( k = 1) es equivalente a una selección aleatoria. Hay dos variantes de la selección: con y sin recambio. La variante sin reemplazo garantiza que al seleccionar N individuos de una población de N elementos, cada individuo participa en exactamente k torneos. Se propone un algoritmo en. [2] Tenga en cuenta que, dependiendo del número de elementos seleccionados, la selección sin reemplazo no garantiza que ningún individuo sea seleccionado más de una vez. Simplemente garantiza que cada individuo tiene las mismas posibilidades de participar en el mismo número de torneos.
En comparación con el método de selección proporcional de aptitud (estocástica) , la selección de torneos a menudo se implementa en la práctica debido a su falta de ruido estocástico. [3]
La selección de torneos tiene varios beneficios sobre los métodos de selección alternativos para algoritmos genéticos (por ejemplo, selección proporcional a la aptitud y selección basada en recompensas ): es eficiente para codificar, funciona en arquitecturas paralelas y permite que la presión de selección se ajuste fácilmente. [1] También se ha demostrado que la selección del torneo es independiente de la escala de la función de aptitud del algoritmo genético (o " función objetiva ") en algunos sistemas de clasificación. [4] [5]
Ver también
Referencias
- ^ a b Miller, Brad; Goldberg, David (1995). "Algoritmos genéticos, selección de torneos y efectos del ruido" (PDF) . Sistemas complejos . 9 : 193–212. S2CID 6491320 . Archivado desde el original (PDF) el 31 de agosto de 2019.
- ^ Goldberg, David E .; Korb, Bradley; Deb, Kalyanmoy (1989). "Algoritmos genéticos desordenados: motivación, análisis y primeros resultados" (PDF) . Sistemas complejos . 3 (5): 493–530.
- ^ Blickle, Tobias; Thiele, Lothar (diciembre de 1996). "Una comparación de los esquemas de selección utilizados en algoritmos evolutivos". Computación evolutiva . 4 (4): 361–394. CiteSeerX 10.1.1.15.9584 . doi : 10.1162 / evco.1996.4.4.361 . S2CID 42718510 .
- ^ Miller, editado por 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). Computación Genética y Evolutiva GECCO 2003 00 Conferencia de Computación Genética y Evolutiva Chicago, IL, EE. UU., Julio 1216, Actas de 2003, Parte II . Berlín: Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-45110-5.CS1 maint: texto adicional: lista de autores ( enlace )
- ^ Goldberg, David; Deb, Kalyanmoy (1991). "Un análisis comparativo de los esquemas de selección utilizados en algoritmos genéticos" (PDF) . Fundamentos de los algoritmos genéticos . 1 : 69–93. doi : 10.1016 / b978-0-08-050684-5.50008-2 . ISBN 9780080506845. S2CID 938257 . Archivado desde el original (PDF) el 17 de julio de 2018.