Selección

Introducción
Base biológica
Espacio de busqueda
Algoritmo genético (AG)
Estructura básica
Ejemplo Máximo Función
Operadores de un AG
Parámetros de un AG
Selección
Representación Genotipo
Ejemplos AG
Comentarios
Transparencias
Enlaces

Como ya se ha visto los individuos se seleccionan para reproducirse, ahora bien el problema está en cómo seleccionar. De acuerdo con la teoría de la evolución de Darwin, sólo los mejores individuos se reproducen. Basándose en esto existen varios métodos que son utilizados por los genéticos: Selección por la Regla de la Ruleta ,Selección por Ranking, Selección de Estado Fijo por citar algunos de los más utilizados.

Selección por la Regla de la Ruleta

Los padres se seleccionan de acuerdo a su fitness. Los individuos mejores (con mayor fitness) son los que tienen mayores posibilidades de ser elegidos. Intuitivamente el proceso construye una ruleta o un "tarta" en la que cada uno de las porciones representa a un individuo. La porción de tarta que le toca a cada individuo es proporcional a su fitness. Así los individuos buenos se llevarán las mayores porciones y al revés ocurrirá con los peores. El siguiente ejemplo clarifica el proceso:

Ahora, al igual que en un casino se lanza a la ruleta una canica. En el lugar que pare dicha canica, será un lugar ocupado por un cromosoma que será elegido. Resulta claro que los individuos con mayor fitness son los que más a menudo son elegidos.

Existe un algoritmo para realizar este proceso:

  1. [SumaTotal] Calcular la suma total acumulada de los fitness de todos los individuos de la población actual.
  2. [Elegir un número aleatorio r] Generar un número aleatorio entre 0 y la SumaTotal.
  3. [Recorrer] Recorrer la población acumulando nuevamente los fitness. Cuando la suma que se lleve sea mayor o igual a r seleccionamos el individuo donde se vaya recorriendo.

Selección por Ranking

El anterior tipo de selección funciona mal cuando existan grandes diferencias entre los fitness de los individuos de la población. Por ejemplo si un cromosoma ocupa el 90% de la ruleta el resto de los cromosomas tienen muy pocas posibilidades de ser elegidos. La selección por ranking da solución a este problema.

Los individuos son ordenados de acuerdo a su ranking de fitness. De esta manera si tenemos n cromosomas el individuo con peor fitness se le asignará un 1 y el que tenga el mejor fitness se le asignará la n.

Véase en las dos siguientes figuras cómo cambia la situación antes y después del ranking.

Situación antes del Ranking (Ruleta)

Situación después del Ranking

Ahora todos los cromosomas tienen la oportunidad de ser seleccionados. Sin embargo este método puede hacer que el genético converja lentamente a la solución, ya que los mejores individuos no se diferencian apenas de los peores.

A este esquema se le pueden aplicar otros criterios; por ejemplo, se crea la descendencia de uno de los paladines/amazonas, y esta sustituye al más parecido entre los perdedores. Esto se denomina crowding, y fue introducido por DeJong. Una variante de este es el muestreado estocástico universal, que trata de evitar que los individuos con más fitness copen la población; en vez de dar la vuelta a una ruleta con una ranura, da la vuelta a la ruleta con N ranuras, tantas como la población; de esta forma, la distribución estadística de descendientes en la nueva población es más parecida a la real.


Selección por Torneo K/L

La selección por Torneo K/L consiste en seleccionar K individuos de la población aleatoriamente y de estos K individuos se seleccionan los L que tengan mejor fitness. Este proceso se repite todas las veces necesarias hasta formar la nueva población.

Este es uno de los métodos de selección mas utilizados actualmente. Se utiliza también en algunos algorítmos en el momento de la aceptación.


Elitismo

Este concepto expresa la idea de que el mejor individuo de la actual generación pase sin modificar a la siguiente generación. De esta forma no se perderá el mejor cromosoma. Al resto de la población se le aplica la reproducción normalmente.

Por otra parte existen algoritmos genéticos llamados elitistas debido a que convergen muy rápidamente a la solución. Esto se debe al tipo de problema que se trate. Más adelante se verá un caso concreto El problema del coloreamiento de un grafo.