Algoritmos genéticos: selección de los padres
La selección de los padres es el proceso de seleccionar a los padres que se aparean y se recombinan para crear descendientes para la próxima generación. La selección de los padres es muy importante para la tasa de convergencia de la AG, ya que los buenos padres llevan a las personas a soluciones mejores y más adecuadas.
Sin embargo, se debe tener cuidado para evitar que una solución extremadamente adecuada se apodere de toda la población en unas pocas generaciones, ya que esto lleva a que las soluciones estén cerca unas de otras en el espacio de soluciones, lo que conduce a una pérdida de diversidad. Maintaining good diversityen la población es extremadamente crucial para el éxito de una AG. Esta toma de toda la población por una solución extremadamente adecuada se conoce comopremature convergence y es una condición indeseable en un GA.
Selección proporcional al fitness
La selección proporcional a la condición física es una de las formas más populares de selección de los padres. En esto, cada individuo puede convertirse en padre con una probabilidad proporcional a su aptitud. Por lo tanto, las personas más en forma tienen una mayor probabilidad de aparearse y propagar sus características a la próxima generación. Por lo tanto, tal estrategia de selección aplica una presión de selección a los individuos más aptos de la población, evolucionando mejores individuos con el tiempo.
Considere una rueda circular. La rueda se divide enn pies, donde n es el número de individuos de la población. Cada individuo obtiene una parte del círculo que es proporcional a su valor de aptitud.
Son posibles dos implementaciones de la selección proporcional a la aptitud:
Selección de la rueda de la ruleta
En una selección de rueda de ruleta, la rueda circular se divide como se describió anteriormente. Se elige un punto fijo en la circunferencia de la rueda como se muestra y se gira la rueda. La región de la rueda que viene delante del punto fijo se elige como padre. Para el segundo padre, se repite el mismo proceso.
Está claro que un individuo más en forma tiene un pastel más grande en la rueda y, por lo tanto, una mayor probabilidad de aterrizar frente al punto fijo cuando se gira la rueda. Por tanto, la probabilidad de elegir un individuo depende directamente de su aptitud.
En cuanto a la implementación, utilizamos los siguientes pasos:
Calcule S = la suma de las sutilezas.
Genere un número aleatorio entre 0 y S.
Comenzando desde la parte superior de la población, siga agregando las sutilezas a la suma parcial P, hasta que P <S.
El individuo para el que P excede a S es el individuo elegido.
Muestreo universal estocástico (SUS)
El muestreo universal estocástico es bastante similar a la selección de la rueda de la ruleta, sin embargo, en lugar de tener un solo punto fijo, tenemos múltiples puntos fijos como se muestra en la siguiente imagen. Por lo tanto, todos los padres se eligen en un solo giro de la rueda. Además, tal configuración anima a las personas altamente aptas a ser elegidas al menos una vez.
Cabe señalar que los métodos de selección proporcionales a la aptitud no funcionan para los casos en los que la aptitud puede tomar un valor negativo.
Selección del torneo
En la selección del torneo K-Way, seleccionamos K individuos de la población al azar y seleccionamos al mejor de ellos para convertirse en padre. El mismo proceso se repite para seleccionar el siguiente padre. La selección de torneos también es extremadamente popular en la literatura, ya que incluso puede funcionar con valores de aptitud negativos.
Selección de rango
La selección de rango también funciona con valores de aptitud negativos y se utiliza principalmente cuando los individuos de la población tienen valores de aptitud muy cercanos (esto suele ocurrir al final de la carrera). Esto lleva a que cada individuo tenga una parte casi igual del pastel (como en el caso de la selección proporcional a la aptitud) como se muestra en la siguiente imagen y, por lo tanto, cada individuo, sin importar qué tan ajustado entre sí tenga aproximadamente la misma probabilidad de ser seleccionado como padre. Esto, a su vez, conduce a una pérdida en la presión de selección hacia los individuos más en forma, lo que hace que el GA haga malas selecciones de padres en tales situaciones.
En esto, eliminamos el concepto de valor de aptitud al seleccionar un padre. Sin embargo, cada individuo de la población se clasifica según su estado físico. La selección de los padres depende del rango de cada individuo y no de la aptitud. Se prefiere más a los individuos de mayor rango que los de menor rango.
| Cromosoma | Valor de aptitud | Rango |
|---|---|---|
| UN | 8.1 | 1 |
| segundo | 8.0 | 4 |
| C | 8.05 | 2 |
| re | 7,95 | 6 |
| mi | 8.02 | 3 |
| F | 7,99 | 5 |
Selección aleatoria
En esta estrategia, seleccionamos al azar a los padres de la población existente. No hay presión de selección hacia personas más en forma y, por lo tanto, esta estrategia generalmente se evita.