Algoritmos genéticos - Guía rápida
El algoritmo genético (GA) es una técnica de optimización basada en búsquedas basada en los principios de Genetics and Natural Selection. Se utiliza con frecuencia para encontrar soluciones óptimas o casi óptimas a problemas difíciles que, de otro modo, llevaría toda una vida resolverlos. Se utiliza con frecuencia para resolver problemas de optimización, en investigación y en aprendizaje automático.
Introducción a la optimización
La optimización es el proceso de making something better. En cualquier proceso, tenemos un conjunto de entradas y un conjunto de salidas como se muestra en la siguiente figura.
La optimización se refiere a encontrar los valores de las entradas de tal manera que obtengamos los "mejores" valores de salida. La definición de "mejor" varía de un problema a otro, pero en términos matemáticos, se refiere a maximizar o minimizar una o más funciones objetivas, variando los parámetros de entrada.
El conjunto de todas las posibles soluciones o valores que pueden tomar las entradas conforma el espacio de búsqueda. En este espacio de búsqueda, se encuentra un punto o un conjunto de puntos que dan la solución óptima. El objetivo de la optimización es encontrar ese punto o conjunto de puntos en el espacio de búsqueda.
¿Qué son los algoritmos genéticos?
La naturaleza siempre ha sido una gran fuente de inspiración para toda la humanidad. Los algoritmos genéticos (GA) son algoritmos basados en búsquedas que se basan en los conceptos de selección natural y genética. Los GA son un subconjunto de una rama mucho mayor de la computación conocida comoEvolutionary Computation.
Los GA fueron desarrollados por John Holland y sus estudiantes y colegas de la Universidad de Michigan, sobre todo David E. Goldberg y desde entonces se han probado en varios problemas de optimización con un alto grado de éxito.
En GA, tenemos un pool or a population of possible solutionsal problema dado. Estas soluciones luego se someten a recombinación y mutación (como en la genética natural), produciendo nuevos hijos, y el proceso se repite durante varias generaciones. A cada individuo (o solución candidata) se le asigna un valor de aptitud (basado en su valor de función objetivo) y los individuos más aptos tienen una mayor probabilidad de aparearse y producir más individuos “más aptos”. Esto está en consonancia con la teoría darwiniana de la "supervivencia del más apto".
De esta manera, seguimos “evolucionando” mejores personas o soluciones a lo largo de generaciones, hasta alcanzar un criterio de parada.
Los algoritmos genéticos son de naturaleza suficientemente aleatoria, pero funcionan mucho mejor que la búsqueda local aleatoria (en la que solo probamos varias soluciones aleatorias, realizando un seguimiento de las mejores hasta ahora), ya que también explotan información histórica.
Ventajas de los GA
Los GA tienen varias ventajas que los han hecho inmensamente populares. Estos incluyen:
No requiere ninguna información derivada (que puede no estar disponible para muchos problemas del mundo real).
Es más rápido y eficiente en comparación con los métodos tradicionales.
Tiene muy buenas capacidades en paralelo.
Optimiza tanto funciones continuas como discretas y también problemas multiobjetivo.
Proporciona una lista de "buenas" soluciones y no una única solución.
Siempre obtiene una respuesta al problema, que mejora con el tiempo.
Útil cuando el espacio de búsqueda es muy grande y hay una gran cantidad de parámetros involucrados.
Limitaciones de los GA
Como cualquier técnica, los AG también adolecen de algunas limitaciones. Estos incluyen:
Los GA no son adecuados para todos los problemas, especialmente los problemas que son simples y para los que se dispone de información derivada.
El valor de aptitud se calcula repetidamente, lo que puede resultar computacionalmente costoso para algunos problemas.
Al ser estocástico, no existen garantías sobre la optimalidad o la calidad de la solución.
Si no se implementa correctamente, es posible que la GA no converja hacia la solución óptima.
GA - Motivación
Los algoritmos genéticos tienen la capacidad de ofrecer una solución "suficientemente buena" y "suficientemente rápida". Esto hace que los algoritmos genéticos sean atractivos para su uso en la resolución de problemas de optimización. Las razones por las que se necesitan AG son las siguientes:
Resolver problemas difíciles
En informática, existe un gran conjunto de problemas, que son NP-Hard. Lo que esto significa esencialmente es que, incluso los sistemas informáticos más potentes, tardan mucho tiempo (¡incluso años!) En resolver ese problema. En tal escenario, los GA demuestran ser una herramienta eficiente para proporcionarusable near-optimal solutions en poco tiempo.
Fracaso de los métodos basados en gradientes
Los métodos tradicionales basados en cálculo funcionan comenzando en un punto aleatorio y moviéndose en la dirección del gradiente, hasta llegar a la cima de la colina. Esta técnica es eficiente y funciona muy bien para funciones de objetivo de un solo pico como la función de costo en regresión lineal. Pero, en la mayoría de las situaciones del mundo real, tenemos un problema muy complejo llamado paisajes, que están formados por muchos picos y muchos valles, lo que hace que esos métodos fallen, ya que sufren una tendencia inherente a quedarse atascados en los óptimos locales. como se muestra en la siguiente figura.
Obtener una buena solución rápidamente
Algunos problemas difíciles, como el problema del vendedor ambulante (TSP), tienen aplicaciones del mundo real, como la búsqueda de rutas y el diseño VLSI. Ahora imagine que está utilizando su sistema de navegación GPS y que se necesitan unos minutos (o incluso algunas horas) para calcular la ruta "óptima" desde el origen hasta el destino. El retraso en tales aplicaciones del mundo real no es aceptable y, por lo tanto, lo que se requiere es una solución "suficientemente buena", que se entregue "rápido".
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 en 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). UNA0 at position x representa eso xthse 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 generarse 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
Una de las decisiones más importantes a tomar al implementar un algoritmo genético es decidir la representación que usaremos para representar nuestras soluciones. Se ha observado que una representación inadecuada puede conducir a un desempeño deficiente de la AG.
Por lo tanto, elegir una representación adecuada, tener una definición adecuada de los mapeos entre los espacios de fenotipo y genotipo es esencial para el éxito de una AG.
En esta sección, presentamos algunas de las representaciones más utilizadas para algoritmos genéticos. Sin embargo, la representación es muy específica del problema y el lector puede encontrar que otra representación o una combinación de las representaciones mencionadas aquí podría adaptarse mejor a su problema.
Representación binaria
Esta es una de las representaciones más simples y más utilizadas en los GA. En este tipo de representación, el genotipo consta de cadenas de bits.
Para algunos problemas en los que el espacio de solución consta de variables de decisión booleanas, sí o no, la representación binaria es natural. Tomemos, por ejemplo, el problema de la mochila 0/1. Si hay n elementos, podemos representar una solución mediante una cadena binaria de n elementos, donde el x- ésimo elemento indica si el elemento x se selecciona (1) o no (0).
Para otros problemas, específicamente los relacionados con números, podemos representar los números con su representación binaria. El problema con este tipo de codificación es que los diferentes bits tienen un significado diferente y, por lo tanto, los operadores de mutación y cruce pueden tener consecuencias no deseadas. Esto se puede resolver hasta cierto punto utilizandoGray Coding, ya que un cambio en un bit no tiene un efecto masivo en la solución.
Representación de valor real
Para los problemas en los que queremos definir los genes utilizando variables continuas en lugar de discretas, la representación de valor real es la más natural. Sin embargo, la precisión de estos números de coma flotante o de valor real se limita a la computadora.
Representación de números enteros
Para genes de valores discretos, no siempre podemos limitar el espacio de la solución a un "sí" o "no" binario. Por ejemplo, si queremos codificar las cuatro distancias: norte, sur, este y oeste, podemos codificarlas como{0,1,2,3}. En tales casos, es deseable la representación de números enteros.
Representación de permutación
En muchos problemas, la solución está representada por un orden de elementos. En tales casos, la representación por permutación es la más adecuada.
Un ejemplo clásico de esta representación es el problema del viajante de comercio (TSP). En esto, el vendedor tiene que hacer un recorrido por todas las ciudades, visitar cada ciudad exactamente una vez y regresar a la ciudad de partida. La distancia total del recorrido debe minimizarse. La solución a este TSP es, naturalmente, un ordenamiento o permutación de todas las ciudades y, por lo tanto, el uso de una representación de permutación tiene sentido para este problema.
La población es un subconjunto de soluciones en la generación actual. También se puede definir como un conjunto de cromosomas. Hay varias cosas que se deben tener en cuenta al tratar con la población de GA:
La diversidad de la población debe mantenerse, de lo contrario podría conducir a una convergencia prematura.
El tamaño de la población no debe mantenerse muy grande, ya que puede hacer que una GA se desacelere, mientras que una población más pequeña podría no ser suficiente para un buen grupo de apareamiento. Por lo tanto, el tamaño óptimo de la población debe decidirse mediante ensayo y error.
La población generalmente se define como una matriz bidimensional de: size population, size x, chromosome size.
Inicialización de población
Hay dos métodos principales para inicializar una población en un GA. Ellos son -
Random Initialization - Poblar la población inicial con soluciones completamente aleatorias.
Heuristic initialization - Complete la población inicial utilizando una heurística conocida para el problema.
Se ha observado que no se debe inicializar toda la población usando una heurística, ya que puede resultar en que la población tenga soluciones similares y muy poca diversidad. Se ha observado experimentalmente que las soluciones aleatorias son las que llevan a la población a la optimización. Por lo tanto, con la inicialización heurística, simplemente sembramos la población con un par de buenas soluciones, llenando el resto con soluciones aleatorias en lugar de llenar toda la población con soluciones basadas en heurísticas.
También se ha observado que la inicialización heurística en algunos casos, solo afecta la aptitud inicial de la población, pero al final, es la diversidad de las soluciones la que conduce a la optimización.
Modelos de población
Hay dos modelos de población ampliamente utilizados:
Estado estable
En estado estacionario GA, generamos uno o dos brotes en cada iteración y reemplazan a uno o dos individuos de la población. Una GA en estado estable también se conoce comoIncremental GA.
Generacional
En un modelo generacional, generamos 'n' descendencias, donde n es el tamaño de la población, y toda la población se reemplaza por la nueva al final de la iteración.
La función de aptitud simplemente definida es una función que toma un candidate solution to the problem as input and produces as output cuán “encaja” nuestro cuán “buena” es la solución con respecto al problema en consideración.
El cálculo del valor de aptitud se realiza repetidamente en un GA y, por lo tanto, debería ser lo suficientemente rápido. Un cálculo lento del valor de aptitud puede afectar negativamente a un GA y hacerlo excepcionalmente lento.
En la mayoría de los casos, la función de aptitud y la función objetivo son las mismas que el objetivo es maximizar o minimizar la función objetivo dada. Sin embargo, para problemas más complejos con múltiples objetivos y limitaciones,Algorithm Designer podría optar por tener una función de fitness diferente.
Una función de aptitud debe poseer las siguientes características:
La función de aptitud debe ser lo suficientemente rápida para calcular.
Debe medir cuantitativamente qué tan apta es una solución dada o qué tan aptos se pueden producir los individuos a partir de la solución dada.
En algunos casos, es posible que no sea posible calcular directamente la función de aptitud debido a las complejidades inherentes del problema en cuestión. En tales casos, hacemos una aproximación de aptitud para satisfacer nuestras necesidades.
La siguiente imagen muestra el cálculo de aptitud para una solución de la mochila 0/1. Es una función de aptitud simple que simplemente suma los valores de ganancia de los artículos que se recogen (que tienen un 1), escaneando los elementos de izquierda a derecha hasta que la mochila está llena.
La selección de los padres es el proceso de seleccionar a los padres que se aparean y se recombinan para crear descendientes para la próxima generación. La selección de los padres es muy crucial para la tasa de convergencia de la AG, ya que los buenos padres llevan a las personas a soluciones mejores y más adecuadas.
Sin embargo, se debe tener cuidado para evitar que una solución extremadamente adecuada se apodere de toda la población en unas pocas generaciones, ya que esto lleva a que las soluciones estén cerca unas de otras en el espacio de soluciones, lo que conduce a una pérdida de diversidad. Maintaining good diversityen la población es extremadamente crucial para el éxito de una AG. Esta toma de toda la población por una solución extremadamente adecuada se conoce comopremature convergence y es una condición indeseable en un GA.
Selección proporcional al fitness
La selección proporcional a la condición física es una de las formas más populares de selección de los padres. En esto, cada individuo puede convertirse en padre con una probabilidad proporcional a su aptitud. Por lo tanto, las personas más en forma tienen una mayor probabilidad de aparearse y propagar sus características a la próxima generación. Por lo tanto, tal estrategia de selección aplica una presión de selección a los individuos más aptos de la población, evolucionando mejores individuos con el tiempo.
Considere una rueda circular. La rueda se divide enn pies, donde n es el número de individuos de la población. Cada individuo obtiene una parte del círculo que es proporcional a su valor de aptitud.
Son posibles dos implementaciones de la selección proporcional a la aptitud:
Selección de la rueda de la ruleta
En una selección de rueda de ruleta, la rueda circular se divide como se describió anteriormente. Se elige un punto fijo en la circunferencia de la rueda como se muestra y se gira la rueda. La región de la rueda que viene delante del punto fijo se elige como padre. Para el segundo padre, se repite el mismo proceso.
Está claro que un individuo más en forma tiene un pastel mayor en la rueda y, por lo tanto, una mayor probabilidad de aterrizar frente al punto fijo cuando se gira la rueda. Por tanto, la probabilidad de elegir un individuo depende directamente de su aptitud.
En cuanto a la implementación, utilizamos los siguientes pasos:
Calcule S = la suma de las sutilezas.
Genere un número aleatorio entre 0 y S.
Comenzando desde la parte superior de la población, siga agregando las sutilezas a la suma parcial P, hasta que P <S.
El individuo para el que P excede a S es el individuo elegido.
Muestreo universal estocástico (SUS)
El muestreo universal estocástico es bastante similar a la selección de la rueda de la ruleta, sin embargo, en lugar de tener un solo punto fijo, tenemos múltiples puntos fijos como se muestra en la siguiente imagen. Por lo tanto, todos los padres se eligen en un solo giro de la rueda. Además, tal configuración anima a las personas altamente aptas a ser elegidas al menos una vez.
Cabe señalar que los métodos de selección proporcionales a la aptitud no funcionan para los casos en los que la aptitud puede tomar un valor negativo.
Selección del torneo
En la selección del torneo K-Way, seleccionamos K individuos de la población al azar y seleccionamos al mejor de ellos para convertirse en padre. El mismo proceso se repite para seleccionar el siguiente padre. La selección de torneos también es extremadamente popular en la literatura, ya que incluso puede funcionar con valores de aptitud negativos.
Selección de rango
La selección de rango también funciona con valores de aptitud negativos y se utiliza principalmente cuando los individuos de la población tienen valores de aptitud muy cercanos (esto suele ocurrir al final de la carrera). Esto lleva a que cada individuo tenga una parte casi igual del pastel (como en el caso de la selección proporcional a la aptitud) como se muestra en la siguiente imagen y, por lo tanto, cada individuo, sin importar cuán ajustado entre sí, tiene aproximadamente la misma probabilidad de ser seleccionado como un padre. Esto, a su vez, conduce a una pérdida en la presión de selección hacia los individuos más en forma, lo que hace que el GA haga malas selecciones de los padres en tales situaciones.
En esto, eliminamos el concepto de valor de aptitud al seleccionar un padre. Sin embargo, cada individuo de la población se clasifica según su estado físico. La selección de los padres depende del rango de cada individuo y no de la aptitud. Se prefiere más a los individuos de mayor rango que los de menor rango.
Cromosoma | Valor de aptitud | Rango |
---|---|---|
UNA | 8.1 | 1 |
segundo | 8.0 | 4 |
C | 8.05 | 2 |
re | 7,95 | 6 |
mi | 8.02 | 3 |
F | 7,99 | 5 |
Selección aleatoria
En esta estrategia seleccionamos al azar a los padres de la población existente. No hay presión de selección hacia personas más en forma y, por lo tanto, esta estrategia generalmente se evita.
En este capítulo, analizaremos qué es un operador de cruce junto con sus otros módulos, sus usos y beneficios.
Introducción a Crossover
El operador de cruce es análogo a la reproducción y el cruce biológico. En este se selecciona más de un progenitor y uno o más descendientes se producen utilizando el material genético de los progenitores. El cruce generalmente se aplica en un GA con una alta probabilidad:pc .
Operadores cruzados
En esta sección analizaremos algunos de los operadores de cruce más utilizados. Cabe señalar que estos operadores cruzados son muy genéricos y el GA Designer podría optar por implementar también un operador cruzado específico del problema.
Cruce de un punto
En este cruce de un punto, se selecciona un punto de cruce aleatorio y las colas de sus dos padres se intercambian para obtener nuevos resortes.
Cruce multipunto
El cruce de múltiples puntos es una generalización del cruce de un punto en el que los segmentos alternos se intercambian para obtener nuevos resortes.
Cruce uniforme
En un cruce uniforme, no dividimos el cromosoma en segmentos, sino que tratamos cada gen por separado. En esto, básicamente lanzamos una moneda por cada cromosoma para decidir si se incluirá o no en la descendencia. También podemos sesgar la moneda a uno de los padres, para tener más material genético en el hijo de ese padre.
Recombinación aritmética completa
Esto se usa comúnmente para representaciones de números enteros y funciona tomando el promedio ponderado de los dos padres usando las siguientes fórmulas:
- Niño1 = α.x + (1-α) .y
- Niño2 = α.x + (1-α) .y
Obviamente, si α = 0.5, entonces ambos hijos serán idénticos como se muestra en la siguiente imagen.
Cruce de órdenes de Davis (OX1)
OX1 se utiliza para cruces basados en permutación con la intención de transmitir información sobre el orden relativo a los resortes. Funciona de la siguiente manera:
Cree dos puntos de cruce aleatorios en el padre y copie el segmento entre ellos desde el primer padre hasta la primera descendencia.
Ahora, a partir del segundo punto de cruce en el segundo padre, copie los números restantes no utilizados del segundo padre al primer hijo, ajustando la lista.
Repita para el segundo hijo con el papel de los padres invertido.
Existen muchos otros crossovers como Crossover parcialmente mapeado (PMX), Crossover basado en órdenes (OX2), Crossover aleatorio, Crossover de anillo, etc.
Introducción a la mutación
En términos simples, la mutación puede definirse como un pequeño ajuste aleatorio en el cromosoma para obtener una nueva solución. Se usa para mantener e introducir diversidad en la población genética y generalmente se aplica con baja probabilidad -pm. Si la probabilidad es muy alta, la GA se reduce a una búsqueda aleatoria.
La mutación es la parte de la AG que está relacionada con la "exploración" del espacio de búsqueda. Se ha observado que la mutación es esencial para la convergencia del GA mientras que el cruce no lo es.
Operadores de mutación
En esta sección, describimos algunos de los operadores de mutación más utilizados. Al igual que los operadores cruzados, esta no es una lista exhaustiva y el diseñador de GA podría encontrar más útil una combinación de estos enfoques o un operador de mutación específico del problema.
Mutación Bit Flip
En esta mutación de cambio de bits, seleccionamos uno o más bits aleatorios y los volteamos. Se utiliza para GA codificados en binario.
Restablecimiento aleatorio
El restablecimiento aleatorio es una extensión del cambio de bits para la representación de números enteros. En este, se asigna un valor aleatorio del conjunto de valores permitidos a un gen elegido al azar.
Mutación de intercambio
En la mutación de intercambio, seleccionamos dos posiciones en el cromosoma al azar e intercambiamos los valores. Esto es común en codificaciones basadas en permutación.
Mutación Scramble
La mutación Scramble también es popular entre las representaciones de permutación. En esto, de todo el cromosoma, se elige un subconjunto de genes y sus valores se mezclan o se mezclan aleatoriamente.
Mutación de inversión
En la mutación de inversión, seleccionamos un subconjunto de genes como en la mutación scramble, pero en lugar de barajar el subconjunto, simplemente invertimos la cadena completa en el subconjunto.
La Política de selección de sobrevivientes determina qué individuos serán expulsados y cuáles permanecerán en la próxima generación. Es fundamental, ya que debe garantizar que las personas en mejor forma física no sean expulsadas de la población, mientras que al mismo tiempo se debe mantener la diversidad en la población.
Algunos GA emplean Elitism. En términos simples, significa que el miembro más apto actual de la población siempre se propaga a la siguiente generación. Por tanto, bajo ninguna circunstancia se podrá sustituir al miembro más apto de la población actual.
La política más sencilla es expulsar a miembros aleatorios de la población, pero este enfoque con frecuencia tiene problemas de convergencia, por lo que las siguientes estrategias se utilizan ampliamente.
Selección basada en la edad
En la selección basada en la edad, no tenemos la noción de aptitud. Se basa en la premisa de que a cada individuo se le permite en la población durante una generación finita donde se le permite reproducirse, después de eso, se le echa de la población sin importar cuán buena sea su aptitud.
Por ejemplo, en el siguiente ejemplo, la edad es el número de generaciones durante las cuales el individuo ha estado en la población. Los miembros de mayor edad de la población, es decir, P4 y P7, son expulsados de la población y las edades del resto de los miembros se incrementan en uno.
Selección basada en fitness
En esta selección basada en la aptitud, los niños tienden a reemplazar a los individuos menos aptos de la población. La selección de los individuos menos aptos se puede realizar mediante una variación de cualquiera de las políticas de selección descritas anteriormente: selección de torneo, selección proporcional a la aptitud, etc.
Por ejemplo, en la siguiente imagen, los niños reemplazan a los individuos P1 y P10 menos aptos de la población. Cabe señalar que, dado que P1 y P9 tienen el mismo valor de aptitud, la decisión de eliminar a qué individuo de la población es arbitraria.
La condición de terminación de un algoritmo genético es importante para determinar cuándo terminará una ejecución de GA. Se ha observado que inicialmente, el GA progresa muy rápido con mejores soluciones en cada pocas iteraciones, pero esto tiende a saturarse en las últimas etapas donde las mejoras son muy pequeñas. Por lo general, queremos una condición de terminación tal que nuestra solución esté cerca de la óptima, al final de la ejecución.
Por lo general, mantenemos una de las siguientes condiciones de terminación:
- Cuando no ha habido mejora en la población para X iteraciones.
- Cuando llegamos a un número absoluto de generaciones.
- Cuando el valor de la función objetivo ha alcanzado un cierto valor predefinido.
Por ejemplo, en un algoritmo genético mantenemos un contador que realiza un seguimiento de las generaciones para las que no ha habido ninguna mejora en la población. Inicialmente, ponemos este contador a cero. Cada vez que no generamos descendientes que sean mejores que los individuos de la población, incrementamos el contador.
Sin embargo, si la aptitud de alguno de los resortes es mejor, restablecemos el contador a cero. El algoritmo termina cuando el contador alcanza un valor predeterminado.
Al igual que otros parámetros de una GA, la condición de terminación también es muy específica del problema y el diseñador de GA debería probar varias opciones para ver cuál se adapta mejor a su problema particular.
Hasta ahora en este tutorial, todo lo que hemos discutido corresponde al modelo darwiniano de evolución: selección natural y variación genética a través de recombinación y mutación. En la naturaleza, solo la información contenida en el genotipo del individuo puede transmitirse a la siguiente generación. Este es el enfoque que hemos estado siguiendo en el tutorial hasta ahora.
Sin embargo, otros modelos de adaptación de por vida: Lamarckian Model y Baldwinian Modeltambién existen. Cabe señalar que cualquiera que sea el mejor modelo, está abierto a debate y los resultados obtenidos por los investigadores muestran que la elección de la adaptación de por vida es muy específica del problema.
A menudo, hibridamos un GA con búsqueda local, como en los algoritmos meméticos. En tales casos, uno podría optar por ir con el Modelo Lamarckiano o Baldwiniano para decidir qué hacer con los individuos generados después de la búsqueda local.
Modelo Lamarckiano
El modelo lamarckiano esencialmente dice que los rasgos que un individuo adquiere durante su vida pueden transmitirse a su descendencia. Lleva el nombre del biólogo francés Jean-Baptiste Lamarck.
Sin embargo, la biología natural ha ignorado por completo el lamarckismo, ya que todos sabemos que solo se puede transmitir la información del genotipo. Sin embargo, desde el punto de vista de la computación, se ha demostrado que la adopción del modelo lamarckiano da buenos resultados para algunos de los problemas.
En el modelo lamarckiano, un operador de búsqueda local examina el vecindario (adquiriendo nuevos rasgos) y, si se encuentra un mejor cromosoma, se convierte en la descendencia.
Modelo Baldwiniano
El modelo baldwiniano es una idea intermedia que lleva el nombre de James Mark Baldwin (1896). En el modelo de Baldwin, los cromosomas pueden codificar una tendencia a aprender comportamientos beneficiosos. Esto significa que, a diferencia del modelo lamarckiano, no transmitimos los rasgos adquiridos a la siguiente generación, ni ignoramos por completo los rasgos adquiridos como en el modelo darwiniano.
El modelo Baldwin se encuentra en el medio de estos dos extremos, en los que la tendencia de un individuo a adquirir ciertos rasgos está codificada en lugar de los rasgos en sí mismos.
En este modelo baldwiniano, un operador de búsqueda local examina el vecindario (adquiriendo nuevos rasgos) y, si se encuentra un mejor cromosoma, solo asigna la aptitud mejorada al cromosoma y no modifica el cromosoma en sí. El cambio en la aptitud significa la capacidad de los cromosomas para "adquirir el rasgo", aunque no se transmita directamente a las generaciones futuras.
Los GA son de naturaleza muy general y su simple aplicación a cualquier problema de optimización no daría buenos resultados. En esta sección, describimos algunos puntos que ayudarían y ayudarían a un diseñador o implementador de AG en su trabajo.
Introducir el conocimiento del dominio específico del problema
Se ha observado que el conocimiento del dominio más específico del problema que incorporamos en la AG; los mejores valores objetivos que obtengamos. Se puede agregar información específica del problema mediante el uso de operadores de mutación o de cruce específicos del problema, representaciones personalizadas, etc.
La siguiente imagen muestra la vista de Michalewicz (1990) del EA:
Reducir el hacinamiento
El hacinamiento ocurre cuando un cromosoma altamente adaptado se reproduce mucho y, en unas pocas generaciones, toda la población se llena de soluciones similares que tienen una aptitud similar. Esto reduce la diversidad, que es un elemento crucial para asegurar el éxito de una AG. Existen numerosas formas de limitar el hacinamiento. Algunos de ellos son ...
Mutation para introducir la diversidad.
Cambiar a rank selection y tournament selection que tienen más presión de selección que la selección proporcional de aptitud para individuos con aptitud similar.
Fitness Sharing - En esto, la aptitud de un individuo se reduce si la población ya contiene individuos similares.
¡La aleatorización ayuda!
Se ha observado experimentalmente que las mejores soluciones son impulsadas por cromosomas aleatorios, ya que imparten diversidad a la población. El implementador de AG debe tener cuidado de mantener una cantidad suficiente de aleatorización y diversidad en la población para obtener los mejores resultados.
Hibridación de GA con búsqueda local
La búsqueda local se refiere a verificar las soluciones cercanas a una solución dada para buscar mejores valores objetivos.
A veces puede resultar útil hibridar la GA con la búsqueda local. La siguiente imagen muestra los distintos lugares en los que se puede introducir la búsqueda local en un GA.
Variación de parámetros y técnicas
En los algoritmos genéticos, no existe una "talla única" o una fórmula mágica que funcione para todos los problemas. Incluso después de que el GA inicial esté listo, se necesita mucho tiempo y esfuerzo para jugar con los parámetros como el tamaño de la población, la mutación y la probabilidad de cruce, etc. para encontrar los que se adapten al problema particular.
En esta sección, presentamos algunos temas avanzados en algoritmos genéticos. Un lector que busque solo una introducción a los GA puede optar por saltarse esta sección.
Problemas de optimización restringida
Los problemas de optimización restringida son aquellos problemas de optimización en los que tenemos que maximizar o minimizar un valor de función objetivo dado que está sujeto a ciertas restricciones. Por lo tanto, no todos los resultados en el espacio de la solución son factibles y el espacio de la solución contiene regiones factibles como se muestra en la siguiente imagen.
En tal escenario, los operadores de cruce y mutación podrían darnos soluciones que son inviables. Por lo tanto, se deben emplear mecanismos adicionales en el GA cuando se trata de problemas de optimización restringidos.
Algunos de los métodos más comunes son:
Utilizando penalty functions lo que reduce la idoneidad de las soluciones inviables, preferiblemente de modo que la idoneidad se reduzca en proporción al número de restricciones violadas o la distancia de la región factible.
Utilizando repair functions que toman una solución inviable y la modifican para que se satisfagan las restricciones violadas.
Not allowing infeasible solutions entrar en la población en absoluto.
Utilizar una special representation or decoder functions que asegura la viabilidad de las soluciones.
Antecedentes teóricos básicos
En esta sección, analizaremos el teorema del esquema y la NFL junto con la hipótesis de los bloques de construcción.
Teorema del esquema
Los investigadores han estado tratando de descubrir las matemáticas detrás del funcionamiento de los algoritmos genéticos, y el teorema del esquema de Holland es un paso en esa dirección. Durante el año, se han realizado varias mejoras y sugerencias al Teorema del esquema para hacerlo más general.
En esta sección, no profundizamos en las matemáticas del Teorema de esquema, sino que intentamos desarrollar una comprensión básica de qué es el Teorema de esquema. La terminología básica que debe conocer es la siguiente:
UNA Schemaes una "plantilla". Formalmente, es una cadena sobre el alfabeto = {0,1, *},
donde * es no importa y puede tomar cualquier valor.
Por lo tanto, * 10 * 1 podría significar 01001, 01011, 11001 o 11011
Geométricamente, un esquema es un hiperplano en el espacio de búsqueda de soluciones.
Order de un esquema es el número de posiciones fijas especificadas en un gen.
Defining length es la distancia entre los dos símbolos fijos más lejanos del gen.
El teorema del esquema establece que este esquema con aptitud superior a la media, longitud de definición corta y orden inferior tiene más probabilidades de sobrevivir al cruce y la mutación.
Hipótesis de bloques de construcción
Los Building Blocks son esquemas de longitud de baja definición y orden bajo con la aptitud promedio dada anteriormente. La hipótesis de los bloques de construcción dice que dichos bloques de construcción sirven como base para el éxito y la adaptación de los AG a medida que avanza identificando y recombinando sucesivamente dichos "bloques de construcción".
Teorema de no almuerzo gratis (NFL)
Wolpert y Macready en 1997 publicaron un artículo titulado "No hay teoremas de almuerzo gratis para la optimización". Básicamente, establece que si promediamos el espacio de todos los problemas posibles, entonces todos los algoritmos de caja negra que no revisen exhibirán el mismo rendimiento.
Significa que cuanto más entendemos un problema, nuestra GA se vuelve más específica del problema y ofrece un mejor rendimiento, pero lo compensa con un mal rendimiento para otros problemas.
Aprendizaje automático basado en GA
Los algoritmos genéticos también encuentran aplicación en el aprendizaje automático. Classifier systems son una forma de genetics-based machine learning(GBML) que se utilizan con frecuencia en el campo del aprendizaje automático. Los métodos GBML son un enfoque de nicho para el aprendizaje automático.
Hay dos categorías de sistemas GBML:
The Pittsburg Approach - En este enfoque, un cromosoma codifica una solución, por lo que se asigna aptitud a las soluciones.
The Michigan Approach - una solución suele estar representada por muchos cromosomas y, por tanto, se asigna aptitud a las soluciones parciales.
Debe tenerse en cuenta que el tema estándar como crossover, mutación, lamarckiano o darwiniano, etc. también está presente en los sistemas GBML.
Los algoritmos genéticos se utilizan principalmente en problemas de optimización de varios tipos, pero también se utilizan con frecuencia en otras áreas de aplicación.
En esta sección, enumeramos algunas de las áreas en las que se utilizan con frecuencia los algoritmos genéticos. Estos son ...
Optimization- Los algoritmos genéticos se utilizan más comúnmente en problemas de optimización en los que tenemos que maximizar o minimizar un valor de función objetivo dado bajo un conjunto dado de restricciones. El enfoque para resolver problemas de optimización se ha destacado a lo largo del tutorial.
Economics - Los GA también se utilizan para caracterizar varios modelos económicos como el modelo de telaraña, la resolución de equilibrio de la teoría de juegos, el precio de los activos, etc.
Neural Networks - Los GA también se utilizan para entrenar redes neuronales, particularmente redes neuronales recurrentes.
Parallelization - Los GA también tienen muy buenas capacidades paralelas y demuestran ser un medio muy eficaz para resolver ciertos problemas, y también proporcionan una buena área para la investigación.
Image Processing - Los GA se utilizan para diversas tareas de procesamiento de imágenes digitales (DIP), así como para la coincidencia de píxeles densos.
Vehicle routing problems - Con múltiples ventanas de tiempo suave, múltiples depósitos y una flota heterogénea.
Scheduling applications - Los GA también se utilizan para resolver varios problemas de programación, en particular el problema de la tabla de tiempos.
Machine Learning - Como ya se ha comentado, el aprendizaje automático basado en la genética (GBML) es un área de nicho en el aprendizaje automático.
Robot Trajectory Generation - Los GA se han utilizado para planificar la ruta que toma un brazo robótico al moverse de un punto a otro.
Parametric Design of Aircraft - Los GA se han utilizado para diseñar aviones variando los parámetros y desarrollando mejores soluciones.
DNA Analysis - Los GA se han utilizado para determinar la estructura del ADN utilizando datos espectrométricos sobre la muestra.
Multimodal Optimization - Los GA son obviamente enfoques muy buenos para la optimización multimodal en los que tenemos que encontrar múltiples soluciones óptimas.
Traveling salesman problem and its applications - Se han utilizado GA para resolver el TSP, que es un problema combinatorio bien conocido que utiliza estrategias novedosas de cruzamiento y empaquetado.
Se pueden consultar los siguientes libros para mejorar aún más el conocimiento del lector sobre algoritmos genéticos y computación evolutiva en general:
Algoritmos genéticos en búsqueda, optimización y aprendizaje automático por David E. Goldberg.
Algoritmos genéticos + Estructuras de datos = Programas evolutivos por Zbigniew Michalewicz.
Algoritmos genéticos prácticos por Randy L. Haupt y Sue Ellen Haupt.
Optimización multiobjetivo usando algoritmos evolutivos por Kalyanmoy Deb.