IX. Seleccion
Introduccion
Como ya sabe por el esquema del AG, los cromosomas se seleccionan de la poblacion para ser progenitores del cruce. La cuestion es como seleccionar esos cromosomas. Segun la teoria de la evolucion de Darwin, los individuos mas aptos deberian sobrevivir y crear nueva descendencia. Hay muchas formas de seleccionar los mejores cromosomas, como la seleccion por ruleta, la seleccion de Boltzmann, la seleccion por torneo, la seleccion por rango, la seleccion de estado estacionario y otras.
Algunos de esos metodos se describiran en este capitulo.
Seleccion por ruleta
Los progenitores se seleccionan de acuerdo con su aptitud. Cuanto mejores sean los cromosomas, mayor sera su probabilidad de ser seleccionados. Imagine una ruleta en la que se colocan todos los cromosomas de la poblacion, ocupando cada uno un espacio proporcional a su aptitud, como se muestra en la figura siguiente.
Luego se lanza una bola sobre la rueda y esta selecciona un cromosoma. Los cromosomas con mayor aptitud seran seleccionados con mas frecuencia.
Esto puede simularse con el siguiente algoritmo.
- [Sum] Calcule la suma de todos los valores de aptitud de los cromosomas de la poblacion - suma S.
- [Select] Genere un numero aleatorio del intervalo (0,S) - r.
- [Loop] Recorra la poblacion y mantenga una suma acumulada de valores de aptitud desde 0 - suma s. Cuando la suma s sea mayor que r, detengase y devuelva el cromosoma de esa posicion.
Por supuesto, el paso 1 se realiza solo una vez por cada poblacion.
Seleccion por rango
El metodo anterior puede causar problemas cuando los valores de aptitud difieren demasiado. Por ejemplo, si el mejor cromosoma ocupa el 90% de la ruleta, los otros cromosomas tendran muy pocas posibilidades de ser seleccionados.
La seleccion por rango primero ordena la poblacion y luego cada cromosoma recibe un valor de aptitud basado en ese orden. El peor cromosoma obtiene aptitud 1, el segundo peor obtiene 2, y asi sucesivamente, mientras que el mejor cromosoma obtiene aptitud N (el numero de cromosomas de la poblacion).
Puede ver en las siguientes figuras como cambia la situacion cuando la aptitud se sustituye por el rango.
Situacion antes del ordenamiento por rango (grafica de aptitudes)
Situacion despues del ordenamiento por rango (grafica de numeros de orden)
Despues de esto, todos los cromosomas tienen probabilidad de ser seleccionados. Sin embargo, este metodo puede conducir a una convergencia mas lenta porque los mejores cromosomas ya no difieren tanto de los demas.
Seleccion de estado estacionario
Este no es un metodo particular para seleccionar progenitores. La idea principal de este enfoque es que una gran parte de la poblacion deberia sobrevivir a la siguiente generacion.
El AG funciona entonces de la siguiente manera. En cada generacion, unos pocos buenos cromosomas (los que tienen alta aptitud) se seleccionan para crear nueva descendencia. Luego se eliminan algunos cromosomas malos (los que tienen baja aptitud), y la nueva descendencia se coloca en sus posiciones. El resto de la poblacion sobrevive a la nueva generacion.
Elitismo
La idea del elitismo ya se introdujo antes. Al crear una nueva poblacion mediante cruce y mutacion, existe una probabilidad considerable de perder el mejor cromosoma.
Elitismo es el nombre de un metodo que primero copia el mejor cromosoma (o unos pocos mejores cromosomas) en la nueva poblacion. El resto se crea luego de la forma habitual. El elitismo puede mejorar significativamente el rendimiento de un AG porque evita la perdida de la mejor solucion encontrada.
·