IV. Algoritmo genetico

Descripcion basica

Los algoritmos geneticos se inspiran en la teoria de la evolucion de Darwin. La solucion a un problema evoluciona en lugar de diseniarse directamente.

El algoritmo comienza con un conjunto de soluciones (representadas por cromosomas) llamado poblacion. Se seleccionan soluciones de una poblacion y se utilizan para formar una nueva poblacion. La idea es que la nueva poblacion sera mejor que la anterior. Las soluciones seleccionadas para crear nuevas soluciones (descendencia) se eligen segun su aptitud: cuanto mas adecuadas sean, mayor sera su probabilidad de reproducirse.

Este proceso se repite hasta que se cumpla alguna condicion, por ejemplo que se alcance un numero maximo de generaciones o que la mejor solucion deje de mejorar.

Ejemplo
Como ya sabe por el capitulo sobre el espacio de busqueda, la resolucion de problemas a menudo puede expresarse como la busqueda del extremo de una funcion. Ese es exactamente el tipo de problema que se muestra aqui. Se da una funcion, y el AG intenta encontrar su minimo.
Puede probar el algoritmo genetico en la demostracion de abajo presionando el boton Start. La grafica representa un espacio de busqueda, y las lineas verticales representan soluciones (puntos en el espacio de busqueda). La linea roja es la mejor solucion; las lineas verdes son las otras.
Start inicia el algoritmo, Step realiza un paso (es decir, crea una nueva generacion), Stop detiene el algoritmo y Reset restaura la poblacion original.

Esquema del algoritmo genetico basico

  1. [Start] Genere una poblacion aleatoria de n cromosomas (soluciones adecuadas para el problema)
  2. [Fitness] Evalua la aptitud f(x) de cada cromosoma x en la poblacion
  3. [New population] Crea una nueva poblacion repitiendo los siguientes pasos hasta que la nueva poblacion este completa
    1. [Selection] Selecciona dos cromosomas progenitores de la poblacion de acuerdo con su aptitud (cuanto mejor sea la aptitud, mayor sera la probabilidad de ser seleccionados)
    2. [Crossover] Con una tasa de cruce, cruza los progenitores para formar nueva descendencia. Si no se realiza cruce, la descendencia es una copia exacta de los progenitores.
    3. [Mutation] Con una tasa de mutacion, muta la nueva descendencia en cada locus (posicion en el cromosoma).
    4. [Accepting] Coloca la nueva descendencia en la nueva poblacion
  4. [Replace] Usa la poblacion recien generada para la siguiente ejecucion del algoritmo
  5. [Test] Si se satisface la condicion de parada, deten y devuelve la mejor solucion de la poblacion actual
  6. [Loop] Ve al paso 2

Algunos comentarios

Como puede ver, el esquema del AG basico es muy general. Hay muchas cosas que pueden implementarse de forma distinta en diversos problemas.

La primera pregunta es como crear cromosomas y que tipo de codificacion elegir. Muy relacionados con esto estan el cruce y la mutacion, los dos operadores basicos de un AG. La codificacion, el cruce y la mutacion se introducen en el siguiente capitulo.

La siguiente pregunta es como seleccionar progenitores para el cruce. Esto puede hacerse de muchas formas, pero la idea principal es favorecer a los mejores progenitores con la esperanza de que produzcan mejor descendencia. Tambien puede notar que crear una nueva poblacion usando solo descendencia puede provocar la perdida del mejor cromosoma de la poblacion anterior. Esto es cierto, por lo que a menudo se utiliza el llamado elitismo. Esto significa que al menos una mejor solucion se copia sin cambios en la nueva poblacion, permitiendo que la mejor solucion encontrada sobreviva hasta el final de la ejecucion.

Algunas de estas cuestiones se discutiran mas adelante.

Tambien puede preguntarse por que funcionan los algoritmos geneticos. Esto puede explicarse en parte por el teorema del esquema de Holland, aunque el teorema tambien ha sido criticado en los ultimos anios. Si quiere saber mas, consulte otras fuentes.

·