Selección (algoritmo genético)

La selección es la etapa de un algoritmo genético o un algoritmo evolutivo más general en el que se eligen genomas individuales de una población para su posterior reproducción (p. ej., utilizando el operador de cruce ). También se utilizan mecanismos de selección para elegir soluciones candidatas (individuos) para la siguiente generación. Retener a los mejores individuos de una generación sin cambios en la siguiente generación se denomina elitismo o selección elitista . Es una variante exitosa (leve) del proceso general de construcción de una nueva población.

Un procedimiento de selección para la cría utilizada en etapas tempranas ^[1] puede implementarse de la siguiente manera:

Los valores de aptitud que se han calculado ( función de aptitud ) se normalizan, de modo que la suma de todos los valores de aptitud resultantes es igual a 1.
Se calculan los valores de aptitud normalizados acumulados: el valor de aptitud acumulado de un individuo es la suma de su propio valor de aptitud más los valores de aptitud de todos los individuos anteriores; la aptitud acumulada del último individuo debe ser 1, de lo contrario, algo salió mal en el paso de normalización.
Se elige un número aleatorio R entre 0 y 1.
El individuo seleccionado es el primero cuyo valor normalizado acumulado sea mayor o igual a R.

Para muchos problemas, el algoritmo anterior puede resultar muy exigente en términos computacionales. Una alternativa más simple y rápida utiliza la denominada aceptación estocástica.

Si este procedimiento se repite hasta que haya suficientes individuos seleccionados, este método de selección se denomina selección proporcional a la aptitud o selección de ruleta . Si en lugar de un solo puntero que gira varias veces, hay varios punteros igualmente espaciados en una rueda que gira una vez, se denomina muestreo universal estocástico . Seleccionar repetidamente al mejor individuo de un subconjunto elegido al azar es selección de torneo . Tomar la mejor mitad, tercio u otra proporción de los individuos es selección por truncamiento .

Existen otros algoritmos de selección que no tienen en cuenta a todos los individuos para la selección, sino solo a aquellos con un valor de aptitud superior a una constante dada (arbitraria). Otros algoritmos seleccionan de un grupo restringido en el que solo se permite un cierto porcentaje de los individuos, en función del valor de aptitud.

Métodos de selección (algoritmo evolutivo)

Los métodos enumerados difieren principalmente en la presión de selección, ^[2]^[3] que se puede establecer mediante un parámetro de estrategia en la selección de rango que se describe a continuación. Cuanto mayor sea la presión de selección, más rápido convergerá una población hacia una determinada solución y es posible que el espacio de búsqueda no se explore lo suficiente. Para conocer más métodos de selección y más detalles, consulte ^[4]^{[5] .}

Selección de la rueda de la ruleta

En la selección de la ruleta , la probabilidad de elegir un individuo para la reproducción de la siguiente generación es proporcional a su aptitud; cuanto mejor sea la aptitud, mayor será la probabilidad de que ese individuo sea elegido. La elección de individuos se puede representar como girar una ruleta que tiene tantos bolsillos como individuos en la generación actual, con tamaños que dependen de su probabilidad. La probabilidad de elegir un individuo es igual a , donde es la aptitud de y es el tamaño de la generación actual (tenga en cuenta que en este método un individuo puede ser extraído varias veces). ${\estilo de visualización i}$ $p_{i}={\frac {f_{i}}{\Sigma _{j=1}^{N}f_{j}}}$ $estilo de visualización f_{i}}$ ${\estilo de visualización i}$ ${\estilo de visualización N}$

Selección de rango

En la selección por rangos, la probabilidad de selección no depende directamente de la aptitud, sino del rango de aptitud de un individuo dentro de la población. Esto permite ver las grandes diferencias de aptitud en perspectiva; además, no es necesario disponer de los valores exactos de aptitud, sino solo de una clasificación de los individuos según su calidad.

A menudo se utiliza la clasificación lineal, que se remonta a Baker, ^[6]^[7] . Permite establecer la presión de selección mediante el parámetro , que puede tomar valores entre 1,0 (sin presión de selección) y 2,0 (alta presión de selección). La probabilidad de las posiciones de clasificación se obtiene de la siguiente manera: ${\estilo de visualización sp}$ ${\estilo de visualización P}$ $R_{i}$

P(R_{i})={\frac {1}{n}}{\Bigl (}sp-(2sp-2){\frac {i-1}{n-1}}{\Bigr )}\quad \quad 1\leq i\leq n,\quad 1\leq sp\leq 2\quad {\mathsf {con}}\quad P(R_{i})\geq 0,\quad \sum _{i=1}^{n}P(R_{i})=1

Además de la presión de selección ajustable, una ventaja de la selección basada en rangos se puede ver adicionalmente en el hecho de que también da a los peores individuos la oportunidad de reproducirse y, por lo tanto, mejorar. ^[8] Esto puede ser particularmente útil en aplicaciones con restricciones, ya que facilita la superación de una restricción en varios pasos intermedios, es decir, a través de una secuencia de varios individuos calificados mal debido a violaciones de restricciones.

Selección de estado estacionario

En cada generación se seleccionan unos pocos cromosomas (buenos, con alta aptitud) para crear una nueva descendencia. Luego se eliminan algunos cromosomas (malos, con baja aptitud) y se coloca la nueva descendencia en su lugar. El resto de la población sobrevive hasta la nueva generación.

Selección de torneos

La selección por torneo es un método de elección de un individuo de un conjunto de individuos. El ganador de cada torneo es seleccionado para realizar el crossover.

Selección elitista

A menudo, para obtener mejores resultados, se utilizan estrategias de reproducción parcial. Una de ellas es el elitismo, en el que una pequeña parte de los mejores individuos de la última generación se transfiere (sin cambios) a la siguiente.

Selección de Boltzmann

En la selección de Boltzmann, una temperatura que varía continuamente controla la tasa de selección según un cronograma preestablecido. La temperatura comienza alta, lo que significa que la presión de selección es baja. La temperatura se reduce gradualmente, lo que aumenta gradualmente la presión de selección, lo que permite que el AG se reduzca más a la mejor parte del espacio de búsqueda mientras mantiene el grado apropiado de diversidad. ^[9]

Véase también

Referencias

^ Holland, John H. (1992). Adaptación en sistemas naturales y artificiales . Tesis doctoral, Universidad de Michigan, 1975. Cambridge, Mass.: MIT Press. ISBN 0-585-03844-9.OCLC 42854623 .
^ Back, T. (1994). "Presión selectiva en algoritmos evolutivos: una caracterización de los mecanismos de selección". Actas de la Primera Conferencia IEEE sobre Computación Evolutiva. Congreso Mundial IEEE sobre Inteligencia Computacional . Orlando, FL, EE. UU.: IEEE. págs. 57–62. doi :10.1109/ICEC.1994.350042. ISBN . 978-0-7803-1899-1.S2CID 195867383 .
^ Goldberg, David E.; Deb, Kalyanmoy (1991), "Un análisis comparativo de los esquemas de selección utilizados en algoritmos genéticos", Fundamentos de algoritmos genéticos , vol. 1, Elsevier, págs. 69-93, CiteSeerX 10.1.1.101.9494 , doi :10.1016/b978-0-08-050684-5.50008-2, ISBN 978-0-08-050684-5, S2CID 938257 , consultado el 9 de enero de 2023
^ Eiben, AE; Smith, JE (2015). "Fitness, Selection, and Population Management". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 79–98. doi :10.1007/978-3-662-44874-8. ISBN. 978-3-662-44873-1. Número de identificación del sujeto 20912932.
^ De Jong, Kenneth A. (2006). Computación evolutiva: un enfoque unificado. Cambridge, Mass.: MIT Press. ISBN 978-0-262-25598-1.OCLC 69652176 .
^ Baker, James E. (1985), Grefenstette, John J. (ed.), "Métodos de selección adaptativa para algoritmos genéticos", Actas de la 1.ª Conferencia internacional sobre algoritmos genéticos y sus aplicaciones (ICGA) , Hillsdale, Nueva Jersey: L. Erlbaum Associates, págs. 101-111, ISBN 0-8058-0426-9
^ Baker, James E. (1987), Grefenstette, John J. (ed.), "Reducción del sesgo y la ineficiencia en el algoritmo de selección", Actas de la 2.ª Conferencia Internacional sobre Algoritmos Genéticos y sus Aplicaciones (ICGA) , Hillsdale, Nueva Jersey: L. Erlbaum Associates, págs. 14-21, ISBN 0-8058-0158-8
^ Whitley, Darrell (1989), Schaffer, JD (ed.), "El algoritmo GENITOR y la presión de selección: por qué la asignación basada en rangos de los ensayos reproductivos es la mejor", Actas de la Tercera Conferencia Internacional sobre Algoritmos Genéticos (ICGA) , San Francisco, CA, EE. UU.: Morgan Kaufmann Publishers Inc., págs. 116-121, ISBN 978-1-55860-066-9
^ Sivanandam, SN (2013). Principios de la informática blanda. Deepa, SN Nueva Delhi: Wiley. ISBN 978-1-118-54680-2.OCLC 891566849 .

Enlaces externos

Introducción a los algoritmos genéticos
Esquema de implementación de la versión de aceptación estocástica