Problemas de optimización
En un algoritmo genético, una población de soluciones candidatas (llamadas individuos, criaturas o fenotipos) a un problema de optimización se desarrolla hacia mejores soluciones. Cada solución candidata tiene un conjunto de propiedades (sus cromosomas o genotipos) que pueden ser mutados y alterados. Tradicionalmente, las soluciones se representan en binario como cadenas de ceros y unos, pero también son posibles otras codificaciones.
La evolución suele partir de una población de individuos generados al azar, y es un proceso iterativo, con la población en cada iteración llamada generación. En cada generación, se evalúa la aptitud de cada individuo en la población. La aptitud suele ser el valor de la función objetivo en el problema de optimización que se está resolviendo. Los individuos más aptos son seleccionados estocásticamente de la población actual, y el genoma de cada individuo es modificado (recombinado "Recombinación (computación evolutiva)") y posiblemente mutado al azar) para formar una nueva generación. La nueva generación de soluciones candidatas se utiliza entonces en la siguiente iteración del algoritmo. Comúnmente, el algoritmo termina cuando se ha producido un número máximo de generaciones, o se ha alcanzado un nivel de aptitud satisfactorio para la población.
Un algoritmo genético típico requiere:.
Una representación estándar de cada solución candidata es como una matriz "Matriz (matemática)") de bits. Las matrices de otros tipos y estructuras se pueden utilizar esencialmente de la misma manera. La propiedad principal que hace convenientes estas representaciones genéticas es que sus partes son fácilmente alineadas debido a su tamaño fijo, lo que facilita las operaciones de cruce simple. También se pueden usar representaciones de longitud variable, pero la implementación del entrecruzamiento cromosómico es más compleja en este caso. Las representaciones arborescentes se exploran en la programación genética y las representaciones en forma de gráfico se exploran en la programación evolutiva. Una mezcla de ambos cromosomas lineales y árboles se explora en la programación de expresión genética.
Una vez que se define la representación genética y la función de aptitud, un AG procede a inicializar una población de soluciones y luego a mejorarla mediante la aplicación repetitiva de los operadores de mutación, entrecruzamiento cromosómico, inversión y selección.
El tamaño de la población depende de la naturaleza del problema, pero normalmente contiene varios cientos o miles de posibles soluciones. A menudo, la población inicial se genera aleatoriamente, permitiendo toda la gama de posibles soluciones (el espacio de búsqueda). Ocasionalmente, las soluciones pueden ser "sembradas" en áreas donde es probable encontrar soluciones óptimas.
Durante cada generación sucesiva, una parte de la población existente se selecciona para criar una nueva generación. Las soluciones individuales se seleccionan a través de un proceso basado en la aptitud, donde las soluciones de acondicionamiento (como medido por una función de acondicionamiento físico) son típicamente más probables de ser seleccionadas. Ciertos métodos de selección evalúan la aptitud de cada solución y preferentemente seleccionan las mejores soluciones. Otros métodos califican solo a una muestra aleatoria de la población, ya que el proceso anterior puede llevar mucho tiempo.
La función de fitness se define sobre la representación genética y mide la calidad de la solución representada. La función de acondicionamiento físico depende siempre del problema. Por ejemplo, en el problema de la mochila se quiere maximizar el valor total de los objetos que se pueden poner en una mochila de alguna capacidad fija. Una representación de una solución puede ser una matriz de bits, donde cada bit representa un objeto diferente, y el valor del bit (0 o 1) representa si el objeto está o no en la mochila. No todas las representaciones son válidas, ya que el tamaño de los objetos puede exceder la capacidad de la mochila. La aptitud de la solución es la suma de valores de todos los objetos en la mochila si la representación es válida, o 0 de lo contrario.
En algunos problemas, es difícil o incluso imposible definir la expresión de la condición física. En estos casos, se puede utilizar una simulación para determinar el valor de la función de aptitud de un fenotipo (por ejemplo, la dinámica de fluidos computacional se usa para determinar la resistencia al aire de un vehículo cuya forma se codifica como fenotipo) o incluso algoritmos genéticos interactivos.
El siguiente paso es generar una población de segunda generación, de soluciones de las seleccionadas a través de una combinación de operadores genéticos: entrecruzamiento cromosómico (también llamado crossover o recombinación) y mutación.
Para cada nueva solución que se ha producido, se ha seleccionado un par de soluciones "padre" para la cría de la agrupación seleccionada previamente. Al producir una solución de "cría" usando los métodos de entrecruzamiento cromosómico y mutación arriba mencionados, se crea una nueva solución que típicamente comparte muchas de las características de sus "padres". Se seleccionan nuevos padres para cada nueva cría, y el proceso continúa hasta que se genere una nueva población de soluciones de tamaño apropiado. Aunque los métodos de reproducción que se basan en el uso de dos padres son más "biología inspirada", algunos temas de investigación sugieren que más de dos "padres" puedan generar cromosomas de mayor calidad.
Estos procesos finalmente resultan en la siguiente generación de población de cromosomas, que es diferente a la generación inicial. En general, la aptitud física promedio se ha incrementado por este procedimiento para la población, ya que solo los mejores organismos de la primera generación son seleccionados para la cría, junto con una pequeña proporción de soluciones menos aptas. Estas soluciones menos aptas aseguran la diversidad genética dentro del grupo genético de los padres y, por lo tanto, aseguran la diversidad genética de la siguiente generación de hijos.
La opinión se divide en la importancia del cruce versus la mutación. Hay muchas referencias en Fogel (2006) que apoyan la importancia de la búsqueda basada en mutaciones.
Aunque el cruce y la mutación se conocen como los principales operadores genéticos, es posible utilizar otros operadores como el reagrupamiento, la colonización-extinción o la migración en algoritmos genéticos.
Vale la pena ajustar parámetros como la probabilidad de mutación, la probabilidad de entrecruzamiento cromosómico y el tamaño de la población para encontrar ajustes razonables para la clase de problema que se está trabajando. Una tasa de mutación muy pequeña puede conducir a la deriva genética (que es de naturaleza no ergódica). Una tasa de recombinación que es demasiado alta puede conducir a la convergencia prematura del algoritmo genético. Una tasa de mutación demasiado alta puede conducir a la pérdida de buenas soluciones, a menos que se utilice una selección elitista.
Este proceso generacional se repite hasta que se alcanza una condición de terminación. Las condiciones de terminación comunes son:.