La selección proporcional a la aptitud , también conocida como selección de la ruleta , es un operador genético utilizado en algoritmos genéticos para seleccionar soluciones potencialmente útiles para la recombinación.
En la selección proporcional de aptitud, como en todos los métodos de selección, la función de aptitud asigna una aptitud a posibles soluciones o cromosomas . Este nivel de aptitud se utiliza para asociar una probabilidad de selección con cada cromosoma individual. Si es la aptitud del individuo en la población, su probabilidad de ser seleccionado es
dónde es el número de individuos de la población.
Esto podría imaginarse similar a una rueda de ruleta en un casino. Por lo general, se asigna una proporción de la rueda a cada una de las posibles selecciones en función de su valor de aptitud. Esto podría lograrse dividiendo la aptitud de una selección por la aptitud total de todas las selecciones, normalizándolas así a 1. Luego se hace una selección aleatoria similar a cómo se gira la rueda de la ruleta.
Si bien es menos probable que se eliminen las soluciones candidatas con una mayor adecuación, aún existe la posibilidad de que se eliminen porque su probabilidad de selección es menor que 1 (o 100%). Compare esto con un algoritmo de selección menos sofisticado, como la selección de truncamiento , que eliminará un porcentaje fijo de los candidatos más débiles. Con la selección proporcional a la aptitud, existe la posibilidad de que algunas soluciones más débiles sobrevivan al proceso de selección. Esto se debe a que, aunque la probabilidad de que las soluciones más débiles sobrevivan es baja, no es cero, lo que significa que es posible que sobrevivan; esto es una ventaja, porque existe la posibilidad de que incluso las soluciones débiles puedan tener algunas características o características que podrían resultar útiles después del proceso de recombinación.
La analogía con una rueda de ruleta se puede imaginar imaginando una rueda de ruleta en la que cada solución candidata representa un hueco en la rueda; el tamaño de los bolsillos es proporcional a la probabilidad de selección de la solución. [ cita requerida ] Seleccionar N cromosomas de la población es equivalente a jugar N juegos en la rueda de la ruleta, ya que cada candidato se dibuja de forma independiente.
En la práctica, a menudo se utilizan otras técnicas de selección, como el muestreo universal estocástico [1] o la selección de torneos . Esto se debe a que tienen menos ruido estocástico, o son rápidos, fáciles de implementar y tienen una presión de selección constante. [2]
La implementación ingenua se lleva a cabo generando primero la distribución de probabilidad acumulada (CDF) sobre la lista de individuos usando una probabilidad proporcional a la aptitud del individuo. Se elige un número aleatorio uniforme del rango [0,1) y la inversa de la CDF para ese número da un individuo. Esto corresponde a la bola de la ruleta que cae en el contenedor de un individuo con una probabilidad proporcional a su ancho. El "bin" correspondiente a la inversa del número aleatorio uniforme se puede encontrar más rápidamente mediante una búsqueda binaria sobre los elementos de la CDF. Se necesita el tiempo O (log n) para elegir un individuo. Una alternativa más rápida que genera individuos en tiempo O (1) será utilizar el método de alias .
Recientemente, se introdujo un algoritmo muy simple que se basa en la "aceptación estocástica". [3] El algoritmo selecciona aleatoriamente a un individuo (digamos) y acepta la selección con probabilidad , dónde es la aptitud máxima de la población. Ciertos análisis indican que la versión de aceptación estocástica tiene un rendimiento considerablemente mejor que las versiones basadas en búsqueda lineal o binaria, especialmente en aplicaciones donde los valores de aptitud pueden cambiar durante la ejecución. [4] Si bien el comportamiento de este algoritmo suele ser rápido, algunas distribuciones de aptitud (como las distribuciones exponenciales) pueden requeririteraciones en el peor de los casos. Este algoritmo también requiere más números aleatorios que la búsqueda binaria.
Pseudocódigo
Por ejemplo, si tiene una población con aptitud [1, 2, 3, 4], entonces la suma es (1 + 2 + 3 + 4 = 10). Por lo tanto, querrá que las probabilidades o posibilidades sean [1/10, 2/10, 3/10, 4/10] o [0.1, 0.2, 0.3, 0.4]. Si tuviera que normalizar visualmente esto entre 0.0 y 1.0, se agruparía como se muestra a continuación con [rojo = 1/10, verde = 2/10, azul = 3/10, negro = 4/10]:
0,1]0,2 \0,3 /0.4 \0,5 |0,6 /0,7 \0,8 |0,9 |1.0 /
Usando los números de ejemplo anteriores, así es como se determinan las probabilidades:
sum_of_fitness = 10probabilidad_anterior = 0.0[1] = probabilidad_anterior + (aptitud / suma_de_capacidad) = 0.0 + (1/10) = 0.1probabilidad_anterior = 0.1[2] = probabilidad_anterior + (aptitud / suma_de_capacidad) = 0,1 + (2/10) = 0,3anterior_probabilidad = 0.3[3] = probabilidad_anterior + (aptitud / suma_de_capacidad) = 0.3 + (3/10) = 0.6probabilidad_anterior = 0.6[4] = probabilidad_anterior + (aptitud / suma_de_capacidad) = 0,6 + (4/10) = 1,0
El último índice siempre debe ser 1.0 o cercano a él. Entonces esta es la forma de seleccionar aleatoriamente a un individuo:
número_aleatorio # Entre 0.0 y 1.0si número_aleatorio <0.1 seleccione 1 más si número_aleatorio <0.3 # 0.3 - 0.1 = 0.2 probabilidad seleccione 2 de lo contrario si número_aleatorio <0,6 # 0,6 - 0,3 = 0,3 probabilidad seleccione 3 de lo contrario si número_aleatorio <1.0 # 1.0 - 0.6 = 0.4 probabilidad seleccione 4 finalice si
Ver también
Referencias
- ^ Bäck, Thomas, Algoritmos evolutivos en teoría y práctica (1996), p. 120, Universidad de Oxford. prensa
- ^ Blickle, Tobías; Thiele, Lothar (1996). "Una comparación de los esquemas de selección utilizados en algoritmos evolutivos". Computación evolutiva . 4 (4): 361–394. doi : 10.1162 / evco.1996.4.4.361 . ISSN 1063-6560 . S2CID 42718510 .
- ^ A. Lipowski, selección de la rueda de la ruleta mediante aceptación estocástica (arXiv: 1109.3627) [1]
- ^ Selección proporcional rápida
enlaces externos
- Implementación de C (.tar.gz; ver selector.cxx) WBL
- Ejemplo de selección de la rueda de la ruleta
- Un esquema de implementación de la versión O (1)