Algoritmos genéticos: fundamentos

Esta sección presenta la terminología básica necesaria para comprender los AG. Además, se presenta una estructura genérica de GA en ambospseudo-code and graphical forms. Se recomienda al lector que comprenda correctamente todos los conceptos presentados en esta sección y que los tenga en cuenta al leer otras secciones de este tutorial también.

Terminología básica

Antes de comenzar una discusión sobre algoritmos genéticos, es esencial estar familiarizado con la terminología básica que se utilizará a lo largo de este tutorial.

• Population- Es un subconjunto de todas las posibles soluciones (codificadas) al problema dado. La población de un GA es análoga a la población de seres humanos, excepto que en lugar de seres humanos, tenemos Candidate Solutions que representan a los seres humanos.

• Chromosomes - Un cromosoma es una de esas soluciones al problema dado.

• Gene - Un gen es la posición de un elemento de un cromosoma.

• Allele - Es el valor que toma un gen para un cromosoma en particular.

• Genotype- El genotipo es la población en el espacio de cálculo. En el espacio de la computación, las soluciones se representan de una manera que se puede entender y manipular fácilmente mediante un sistema de computación.

• Phenotype - El fenotipo es la población en el espacio real de soluciones del mundo real en el que las soluciones se representan de una manera que se representan en situaciones del mundo real.

• Decoding and Encoding - Para problemas simples, el phenotype and genotypelos espacios son los mismos. Sin embargo, en la mayoría de los casos, los espacios de fenotipo y genotipo son diferentes. La decodificación es un proceso de transformación de una solución del genotipo al espacio del fenotipo, mientras que la codificación es un proceso de transformación del fenotipo al espacio del genotipo. La decodificación debe ser rápida, ya que se lleva a cabo repetidamente en un GA durante el cálculo del valor de aptitud.

  Por ejemplo, considere el problema de la mochila 0/1. El espacio de fenotipo consta de soluciones que solo contienen los números de artículo de los artículos a recoger.

  Sin embargo, en el espacio del genotipo se puede representar como una cadena binaria de longitud n (donde n es el número de elementos). UN0 at position x representa eso x^thse elige el artículo mientras que un 1 representa lo contrario. Este es un caso en el que los espacios de genotipo y fenotipo son diferentes.

• Fitness Function- Una función de aptitud simplemente definida es una función que toma la solución como entrada y produce la idoneidad de la solución como salida. En algunos casos, la función de aptitud y la función objetivo pueden ser las mismas, mientras que en otros puede ser diferente según el problema.

• Genetic Operators- Estos alteran la composición genética de la descendencia. Estos incluyen cruzamiento, mutación, selección, etc.

Estructura basica

La estructura básica de un GA es la siguiente:

Comenzamos con una población inicial (que puede ser generada al azar o sembrada por otras heurísticas), seleccionamos padres de esta población para el apareamiento. Aplique operadores de cruce y mutación en los padres para generar nuevos resortes. Y finalmente estos vástagos reemplazan a los individuos existentes en la población y el proceso se repite. De esta manera, los algoritmos genéticos realmente intentan imitar la evolución humana hasta cierto punto.

Cada uno de los siguientes pasos se cubre como un capítulo separado más adelante en este tutorial.

Un pseudocódigo generalizado para un GA se explica en el siguiente programa:

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best