Algoritmos Evolutivos y Genéticos: Conceptos Clave y Aplicaciones

Algoritmos Evolutivos y Genéticos: Una Introducción

Los algoritmos evolutivos y genéticos son sistemas de resolución de problemas de optimización o búsqueda, inspirados en la evolución biológica. Se basan en principios como la selección natural y la herencia genética.

Historia y Orígenes

Fueron introducidos por John Holland y sus colegas en la Universidad de Michigan en los años 70. Sus objetivos principales eran:

• Abstraer y explicar el proceso adaptativo de los sistemas naturales.
• Diseñar sistemas artificiales que emulasen los mecanismos esenciales de los sistemas naturales.

Conceptos Clave: Lo Natural vs. Lo Artificial

Lo Natural

• Entorno / Ecosistema
• Individuo / Fenotipo
• Cromosoma / Genotipo
• Grado de adaptación al entorno
• Supervivencia / Reproducción / Mutación

Lo Artificial

• Problema
• Solución potencial del problema
• Cadena de símbolos
• Fitness o calidad de la solución
• Operadores de selección / aceptación / cruce / mutación

Funcionamiento de los Algoritmos Evolutivos

Los algoritmos evolutivos trabajan con una población de individuos que representan posibles soluciones a un problema. Esta población se somete a transformaciones y a un proceso de selección que favorece a los mejores. Cada ciclo de transformación y selección constituye una generación (población, selección, muestra).

Tipos de Selección

Selección por Ruleta

A cada individuo de la población se le asigna una parte proporcional a su ajuste en una ruleta, de tal forma que la suma de todos los porcentajes sea la unidad. Los mejores individuos recibirán una porción de la ruleta mayor que la recibida por los peores. Generalmente, la población está ordenada en base al ajuste, por lo que las porciones más grandes se encuentran al inicio de la ruleta.

Selección por Torneo

La idea principal de este método consiste en realizar la selección en base a comparaciones directas entre individuos. Existen dos versiones de selección mediante torneo: Determinística y Probabilística.

Escalamiento

Al incrementarse la aptitud media de la población, la fuerza de la presión selectiva también aumenta y la función de aptitud se hace más discriminadora.

Selección Elitista

En ciertas ocasiones, puede suceder que tras el cruce y la mutación, se pierda el cromosoma con mejor adaptación. Este método de selección copia el mejor cromosoma o alguno de los mejores en la nueva población.

Selección Aleatoria

En esta técnica, cada miembro de la población tiene la misma probabilidad de ser seleccionado como sujeto. Todo el proceso de toma de muestras se realiza en un paso, en donde cada sujeto es seleccionado independientemente de los otros miembros de la población.

Proceso General de un Algoritmo Evolutivo

El algoritmo evolutivo se inicia con la definición de una población. Esta población se somete a criterios de selección (edad, altura, peso, etc.). Se obtiene una muestra de los indicadores que satisfacen el criterio de selección. Se evalúa la selección (fitness) para determinar si maximizar o minimizar el resultado. En caso de no satisfacción, se aplica cruce y mutación, de forma que, después de cierto número de generaciones, se espera que el mejor individuo de la población esté cerca de la solución. Los algoritmos evolutivos combinan la búsqueda aleatoria dada por las transformaciones de la población con una búsqueda dirigida dada por la selección.

Componentes Esenciales de un Algoritmo Evolutivo (AE)

• Un método de codificación de los individuos a soluciones potenciales del problema, por ejemplo, una cadena de bits (codificación binaria).
• Una función de evaluación o fitness.
• Una forma de generar la población inicial.
• Operadores genéticos: selección, cruce, mutación.
• Parámetros: tamaño de la población, número de generaciones.

Representación y Operadores Genéticos

Representación Binaria

La representación de un individuo se puede hacer mediante una codificación binaria (cromosoma).

Operadores de Cruce

• Cruce en un punto (el cruce se traza en el índice que se compare).
• Genera 2 hijos a partir de 2 padres.
• Cada hijo hereda características de los 2 padres.
• Es la componente de explotación.

Operadores de Mutación

• La mutación altera de forma aleatoria cada bit.
• La probabilidad de aplicación debe ser baja.
• Introduce características aleatorias en los cromosomas.
• Es la componente de exploración del AG.

Pseudocódigo del Algoritmo Evolutivo

leer parámetros (pc, pm, nro gen,..);
t <- 0;
iniciar P(t);
evaluar P(t);
mientras (no ultima generación) {
  P'(t) = selección(P(t-1));
  P''(t) = alternar(P'(t));
  evaluar P''(t);
  P(t) = aceptar(P'(t), P''(t));
  t = t + 1;
}