La selección proporcional a la aptitud , también conocida como selección de 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 a la aptitud, como en todos los métodos de selección, la función de aptitud asigna una aptitud a las 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 de un individuo en la población, su probabilidad de ser seleccionado es
¿Dónde está el número de individuos en la población?
Esto podría imaginarse de forma similar a una ruleta en un casino. Por lo general, se asigna una proporción de la rueda a cada una de las selecciones posibles 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 realiza una selección aleatoria de forma similar a cómo se hace girar la ruleta.
Si bien las soluciones candidatas con una aptitud más alta tendrán menos probabilidades de ser eliminadas, aún existe la posibilidad de que puedan ser eliminadas porque su probabilidad de selección es menor que 1 (o 100%). Comparemos esto con un algoritmo de selección menos sofisticado, como la selección por 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 aún es posible que sobrevivan; esto es una ventaja, porque existe la posibilidad de que incluso las soluciones débiles puedan tener algunas características que podrían resultar útiles después del proceso de recombinación.
La analogía con una ruleta se puede imaginar imaginando una ruleta en la que cada solución candidata representa un bolsillo 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 ruleta, ya que cada candidato se extrae de forma independiente.
En la práctica, se suelen utilizar otras técnicas de selección, como el muestreo universal estocástico [1] o la selección por torneo , ya que tienen menos ruido estocástico o son rápidas, 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 acumulativa (CDF) sobre la lista de individuos utilizando 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 "contenedor" correspondiente a la inversa del número aleatorio uniforme se puede encontrar más rápidamente utilizando una búsqueda binaria sobre los elementos de la CDF. Se tarda en 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 .
En 2011, se introdujo un algoritmo muy simple que se basa en la "aceptación estocástica". [3] El algoritmo selecciona aleatoriamente a un individuo (por ejemplo ) y acepta la selección con probabilidad , donde es la aptitud máxima en 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 la 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 requerir iteraciones en el peor de los casos. Este algoritmo también requiere más números aleatorios que la búsqueda binaria.
Por ejemplo, si tienes una población con aptitudes [1, 2, 3, 4], entonces la suma es (1 + 2 + 3 + 4 = 10). Por lo tanto, querrás que las probabilidades sean [1/10, 2/10, 3/10, 4/10] o [0,1, 0,2, 0,3, 0,4]. Si tuvieras 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 /
Utilizando los números de ejemplo anteriores, así es como se determinan las probabilidades:
suma_de_aptitud = 10probabilidad_anterior = 0.0[1] = probabilidad_anterior + (aptitud / suma_de_aptitud) = 0,0 + (1 / 10) = 0,1probabilidad_anterior = 0.1[2] = probabilidad_anterior + (aptitud / suma_de_aptitud) = 0,1 + (2 / 10) = 0,3probabilidad_anterior = 0.3[3] = probabilidad_anterior + (aptitud / suma_de_aptitud) = 0,3 + (3 / 10) = 0,6probabilidad_anterior = 0.6[4] = probabilidad_anterior + (aptitud / suma_de_aptitud) = 0,6 + (4 / 10) = 1,0
El último índice siempre debe ser 1,0 o cercano a ese valor. A continuación, se muestra cómo seleccionar un individuo al azar:
random_number # Entre 0,0 y 1,0si numero_aleatorio < 0,1 seleccione 1 de lo contrario 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 random_number < 1.0 # 1.0 − 0.6 = 0.4 probabilidad seleccione 4 final si
