Algoritmo genético

En informática e investigación de operaciones, un algoritmo genético es una metaheurística inspirada en el proceso de selección natural que pertenece a la clase más amplia de algoritmos evolutivos (EA). Los algoritmos genéticos se utilizan comúnmente para generar soluciones de alta calidad para problemas de optimización y búsqueda basándose en operadores inspirados en la biología, como la mutación, el cruce y la selección. Algunos ejemplos de aplicaciones de GA incluyen la optimización de árboles de decisión para un mejor rendimiento, la resolución de sudokus, la optimización de hiperparámetros, etc.

Metodología

Problemas de optimización

En un algoritmo genético, una población de soluciones candidatas (llamadas individuos, criaturas, organismos o fenotipos) a un problema de optimización evoluciona hacia mejores soluciones. Cada solución candidata tiene un conjunto de propiedades (sus cromosomas o genotipo) que se pueden mutar y alterar; tradicionalmente, las soluciones se representan en binario como cadenas de 0 y 1, pero también son posibles otras codificaciones.

La evolución generalmente comienza a partir de una población de individuos generados aleatoriamente 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 de 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 se seleccionan estocásticamente de la población actual y el genoma de cada individuo se modifica (se recombina y posiblemente se muta al azar) para formar una nueva generación. La nueva generación de soluciones candidatas se utiliza luego 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:

1. una representación genética del dominio de la solución,
2. una función de aptitud para evaluar el dominio de la solución.

Una representación estándar de cada solución candidata es como una matriz de bits (también llamada conjunto de bits o cadena de bits). Las matrices de otros tipos y estructuras se pueden usar esencialmente de la misma manera. La principal propiedad que hace que estas representaciones genéticas sean convenientes es que sus partes se alinean fácilmente debido a su tamaño fijo, lo que facilita operaciones simples de cruce. También se pueden usar representaciones de longitud variable, pero la implementación cruzada es más compleja en este caso. Las representaciones en forma de árbol se exploran en la programación genética y las representaciones en forma de gráfico se exploran en la programación evolutiva; se explora una combinación de cromosomas lineales y árboles en la programación de la expresión génica.

Una vez que se definen 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, cruce, inversión y selección.

Inicializació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, lo que permite toda la gama de posibles soluciones (el espacio de búsqueda). Ocasionalmente, las soluciones pueden "sembrarse" en áreas donde es probable que se encuentren soluciones óptimas.

Selección

Durante cada generación sucesiva, se selecciona una parte de la población existente para criar una nueva generación. Las soluciones individuales se seleccionan a través de un proceso basado en la aptitud, donde las soluciones más adecuadas (medidas por una función de aptitud) suelen tener más probabilidades de ser seleccionadas. Ciertos métodos de selección califican la aptitud de cada solución y seleccionan preferentemente las mejores soluciones. Otros métodos califican solo una muestra aleatoria de la población, ya que el primer proceso puede llevar mucho tiempo.

La función de aptitud se define sobre la representación genética y mide la calidad de la solución representada. La función de fitness siempre depende 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 cierta capacidad fija. Una representación de una solución podría 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 estas 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 los valores de todos los objetos en la mochila si la representación es válida, o 0 en caso contrario.

En algunos problemas, es difícil o incluso imposible definir la expresión de aptitud; en estos casos, se puede usar una simulación para determinar el valor de la función de aptitud de un fenotipo (por ejemplo, se usa la dinámica de fluidos computacional para determinar la resistencia del aire de un vehículo cuya forma está codificada como el fenotipo), o incluso se usan algoritmos genéticos interactivos.

Operadores genéticos

El siguiente paso es generar una población de soluciones de segunda generación a partir de las seleccionadas, a través de una combinación de operadores genéticos: cruce (también llamado recombinación) y mutación.

Para cada nueva solución que se va a producir, se selecciona un par de soluciones "padres" para reproducirlas del grupo seleccionado previamente. Al producir una solución "hija" utilizando los métodos anteriores de cruce y mutación, se crea una nueva solución que normalmente comparte muchas de las características de sus "padres". Se seleccionan nuevos padres para cada nuevo niño y el proceso continúa hasta que se genera 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 están más "inspirados en la biología", algunas investigaciones sugieren que más de dos "padres" generan cromosomas de mayor calidad.

Estos procesos finalmente dan como resultado la población de cromosomas de la próxima generación que es diferente de la generación inicial. Generalmente, la aptitud promedio habrá aumentado con este procedimiento para la población, ya que solo los mejores organismos de la primera generación son seleccionados para reproducción, junto con una pequeña proporción de soluciones menos aptas. Estas soluciones menos aptas aseguran la diversidad genética dentro del acervo genético de los padres y, por lo tanto, aseguran la diversidad genética de la siguiente generación de niños.

La opinión está dividida sobre la importancia del cruce frente a la mutación. Hay muchas referencias en Fogel (2006) que respaldan 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 los algoritmos genéticos.

Vale la pena ajustar parámetros como la probabilidad de mutación, la probabilidad de cruce y el tamaño de la población para encontrar configuraciones razonables para la clase de problema en la que se trabaja. 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 demasiado alta puede conducir a una 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 emplee una selección elitista. Un tamaño de población adecuado asegura suficiente diversidad genética para el problema en cuestión, pero puede conducir a un desperdicio de recursos computacionales si se establece en un valor mayor que el requerido.

Heurística

Además de los operadores principales anteriores, se pueden emplear otras heurísticas para hacer que el cálculo sea más rápido o más sólido. La heurística de especiación penaliza el cruce entre soluciones candidatas que son demasiado similares; esto fomenta la diversidad de la población y ayuda a prevenir la convergencia prematura hacia una solución menos óptima.

Terminación

Este proceso generacional se repite hasta que se alcanza una condición de terminación. Las condiciones de terminación comunes son:

• Se encuentra una solución que satisface los criterios mínimos.
• Número fijo de generaciones alcanzadas
• Presupuesto asignado (tiempo de cálculo/dinero) alcanzado
• La idoneidad de la solución con la clasificación más alta está alcanzando o ha alcanzado un nivel tal que las iteraciones sucesivas ya no producen mejores resultados
• Inspección manual
• Combinaciones de lo anterior

La hipótesis del bloque de construcción

Los algoritmos genéticos son simples de implementar, pero su comportamiento es difícil de entender. En particular, es difícil entender por qué estos algoritmos frecuentemente logran generar soluciones de alta aptitud cuando se aplican a problemas prácticos. La hipótesis del bloque de construcción (BBH) consiste en:

1. Una descripción de una heurística que lleva a cabo la adaptación mediante la identificación y recombinación de "bloques de construcción", es decir, esquemas de bajo orden y longitud de definición baja con una aptitud superior a la media.
2. Una hipótesis de que un algoritmo genético realiza la adaptación implementando implícita y eficientemente esta heurística.

Goldberg describe la heurística de la siguiente manera:"Los esquemas cortos, de bajo orden y altamente ajustados se muestrean, se recombinan [se cruzan] y se vuelven a muestrear para formar cadenas de mayor aptitud potencial. En cierto modo, al trabajar con estos esquemas particulares [los componentes básicos], hemos reducido la complejidad de nuestro problema; en lugar de construir cadenas de alto rendimiento probando todas las combinaciones imaginables, construimos cadenas cada vez mejores a partir de las mejores soluciones parciales de muestreos anteriores."Debido a que los esquemas altamente ajustados de baja longitud definitoria y bajo orden juegan un papel tan importante en la acción de los algoritmos genéticos, ya les hemos dado un nombre especial: bloques de construcción. Así como un niño crea magníficas fortalezas mediante la disposición de simples bloques de Wood, también un algoritmo genético busca un rendimiento casi óptimo a través de la yuxtaposición de esquemas o bloques de construcción cortos, de bajo orden y de alto rendimiento".

A pesar de la falta de consenso con respecto a la validez de la hipótesis del bloque de construcción, ha sido evaluada y utilizada como referencia consistentemente a lo largo de los años. Se han propuesto muchos algoritmos de estimación de distribución, por ejemplo, en un intento de proporcionar un entorno en el que se mantendría la hipótesis. Aunque se han informado buenos resultados para algunas clases de problemas, aún persiste el escepticismo con respecto a la generalidad y/o practicidad de la hipótesis de los componentes básicos como explicación de la eficiencia de los AG. De hecho, existe una cantidad razonable de trabajo que intenta comprender sus limitaciones desde la perspectiva de la estimación de algoritmos de distribución.

Limitaciones

Existen limitaciones en el uso de un algoritmo genético en comparación con algoritmos de optimización alternativos:

• La evaluación repetida de funciones de aptitud para problemas complejos suele ser el segmento más prohibitivo y limitante de los algoritmos evolutivos artificiales. Encontrar la solución óptima a problemas multimodales complejos de alta dimensión a menudo requiere evaluaciones de función de aptitud muy costosas. En problemas del mundo real, como los problemas de optimización estructural, la evaluación de una sola función puede requerir de varias horas a varios días de simulación completa. Los métodos típicos de optimización no pueden tratar este tipo de problemas. En este caso, puede ser necesario renunciar a una evaluación exacta y utilizar una aptitud aproximada que sea computacionalmente eficiente. Es evidente que la fusión de modelos aproximados puede ser uno de los enfoques más prometedores para utilizar AG de manera convincente para resolver problemas complejos de la vida real.
• Los algoritmos genéticos no escalan bien con la complejidad. Es decir, cuando el número de elementos que están expuestos a la mutación es grande, a menudo hay un aumento exponencial en el tamaño del espacio de búsqueda. Esto hace que sea extremadamente difícil usar la técnica en problemas como el diseño de un motor, una casa o un avión.. Para que tales problemas sean manejables para la búsqueda evolutiva, deben descomponerse en la representación más simple posible. Por lo tanto, normalmente vemos algoritmos evolutivos que codifican diseños para aspas de ventiladores en lugar de motores, formas de construcción en lugar de planos de construcción detallados y perfiles aerodinámicos en lugar de diseños de aviones completos. El segundo problema de la complejidad es la cuestión de cómo proteger las partes que han evolucionado para representar buenas soluciones de una mutación destructiva adicional, particularmente cuando su evaluación de la aptitud requiere que se combinen bien con otras partes.
• La solución "mejor" es solo en comparación con otras soluciones. Como resultado, el criterio de parada no está claro en todos los problemas.
• En muchos problemas, los AG tienen una tendencia a converger hacia óptimos locales o incluso puntos arbitrarios en lugar del óptimo global del problema. Esto significa que no "sabe cómo" sacrificar la condición física a corto plazo para obtener una condición física a largo plazo. La probabilidad de que esto ocurra depende de la forma del panorama de aptitud: ciertos problemas pueden proporcionar un ascenso fácil hacia un óptimo global, otros pueden facilitar que la función encuentre los óptimos locales. Este problema se puede aliviar usando una función de aptitud diferente, aumentando la tasa de mutación o usando técnicas de selección que mantienen una población diversa de soluciones.aunque el teorema No Free Lunch prueba que no existe una solución general para este problema. Una técnica común para mantener la diversidad es imponer una "penalización de nicho", en la que a cualquier grupo de individuos de suficiente similitud (radio de nicho) se le agrega una penalización, que reducirá la representación de ese grupo en las generaciones posteriores, permitiendo que otros (menos similares)) individuos a mantener en la población. Este truco, sin embargo, puede no ser efectivo, dependiendo del panorama del problema. Otra técnica posible sería simplemente reemplazar parte de la población con individuos generados aleatoriamente, cuando la mayoría de la población es demasiado similar entre sí. La diversidad es importante en los algoritmos genéticos (y en la programación genética) porque cruzar una población homogénea no produce nuevas soluciones.
• Operar con conjuntos de datos dinámicos es difícil, ya que los genomas comienzan a converger desde el principio hacia soluciones que pueden no ser válidas para datos posteriores. Se han propuesto varios métodos para remediar esto aumentando la diversidad genética de alguna manera y evitando la convergencia temprana, ya sea aumentando la probabilidad de mutación cuando la calidad de la solución cae (llamada hipermutación desencadenada), o introduciendo ocasionalmente elementos completamente nuevos generados aleatoriamente en el acervo genético. (llamados inmigrantes aleatorios). Nuevamente, las estrategias de evolución y la programación evolutiva se pueden implementar con la llamada "estrategia de coma" en la que los padres no se mantienen y los nuevos padres se seleccionan solo de la descendencia. Esto puede ser más efectivo en problemas dinámicos.
• Los GA no pueden resolver de manera efectiva problemas en los que la única medida de aptitud es una sola medida correcta/incorrecta (como los problemas de decisión), ya que no hay forma de converger en la solución (no hay colina que escalar). En estos casos, una búsqueda aleatoria puede encontrar una solución tan rápido como un GA. Sin embargo, si la situación permite que la prueba de éxito/fracaso se repita dando (posiblemente) resultados diferentes, entonces la proporción de éxitos y fracasos proporciona una medida de aptitud adecuada.
• Para problemas de optimización e instancias de problemas específicos, otros algoritmos de optimización pueden ser más eficientes que los algoritmos genéticos en términos de velocidad de convergencia. Los algoritmos alternativos y complementarios incluyen estrategias de evolución, programación evolutiva, recocido simulado, adaptación gaussiana, escalada de colinas e inteligencia de enjambre (p. ej., optimización de colonias de hormigas, optimización de enjambres de partículas) y métodos basados ​​en programación lineal entera. La idoneidad de los algoritmos genéticos depende de la cantidad de conocimiento del problema; los problemas bien conocidos a menudo tienen enfoques mejores y más especializados.

Variantes

Representación cromosómica

El algoritmo más simple representa cada cromosoma como una cadena de bits. Normalmente, los parámetros numéricos se pueden representar mediante números enteros, aunque es posible utilizar representaciones de punto flotante. La representación de punto flotante es natural para las estrategias de evolución y la programación evolutiva. Se ha ofrecido la noción de algoritmos genéticos de valor real, pero en realidad es un nombre inapropiado porque en realidad no representa la teoría de los bloques de construcción propuesta por John Henry Holland en la década de 1970. Sin embargo, esta teoría no carece de apoyo, basada en resultados teóricos y experimentales (ver más abajo). El algoritmo básico realiza el cruce y la mutación a nivel de bit. Otras variantes tratan el cromosoma como una lista de números que son índices en una tabla de instrucciones, nodos en una lista enlazada, hashes, objetos o cualquier otra estructura de datos imaginable. El cruce y la mutación se realizan para respetar los límites de los elementos de datos. Para la mayoría de los tipos de datos, se pueden diseñar operadores de variación específicos. Diferentes tipos de datos cromosómicos parecen funcionar mejor o peor para diferentes dominios de problemas específicos.

Cuando se utilizan representaciones de cadenas de bits de enteros, a menudo se emplea la codificación Gray. De esta forma, pequeños cambios en el número entero pueden verse fácilmente afectados por mutaciones o entrecruzamientos. Se ha descubierto que esto ayuda a prevenir la convergencia prematura en las llamadas paredes de Hamming, en las que deben ocurrir demasiadas mutaciones simultáneas (o eventos cruzados) para cambiar el cromosoma a una solución mejor.

Otros enfoques implican el uso de matrices de números con valores reales en lugar de cadenas de bits para representar los cromosomas. Los resultados de la teoría de los esquemas sugieren que, en general, cuanto más pequeño es el alfabeto, mejor es el rendimiento, pero al principio sorprendió a los investigadores que se obtuvieran buenos resultados utilizando cromosomas con valores reales. Esto se explicó como el conjunto de valores reales en una población finita de cromosomas formando un alfabeto virtual (cuando la selección y la recombinación son dominantes) con una cardinalidad mucho más baja de lo que se esperaría de una representación de punto flotante.

Se puede obtener una expansión del dominio del problema accesible del algoritmo genético a través de una codificación más compleja de los conjuntos de soluciones al concatenar varios tipos de genes codificados heterogéneamente en un cromosoma.Este enfoque particular permite resolver problemas de optimización que requieren dominios de definición muy dispares para los parámetros del problema. Por ejemplo, en problemas de ajuste de controlador en cascada, la estructura del controlador de bucle interno puede pertenecer a un regulador convencional de tres parámetros, mientras que el bucle externo podría implementar un controlador lingüístico (como un sistema difuso) que tiene una descripción inherentemente diferente. Esta forma particular de codificación requiere un mecanismo de cruce especializado que recombina el cromosoma por sección, y es una herramienta útil para el modelado y simulación de sistemas adaptativos complejos, especialmente procesos de evolución.

Elitismo

Una variante práctica del proceso general de construcción de una nueva población es permitir que los mejores organismos de la generación actual se trasladen a la siguiente, sin alteraciones. Esta estrategia se conoce como selección elitista y garantiza que la calidad de la solución obtenida por el AG no disminuirá de una generación a la siguiente.

Implementaciones paralelas

Las implementaciones paralelas de algoritmos genéticos vienen en dos sabores. Los algoritmos genéticos paralelos de grano grueso asumen una población en cada uno de los nodos de la computadora y la migración de individuos entre los nodos. Los algoritmos genéticos paralelos de grano fino asumen un individuo en cada nodo del procesador que actúa con los individuos vecinos para la selección y reproducción. Otras variantes, como los algoritmos genéticos para problemas de optimización en línea, introducen dependencia del tiempo o ruido en la función de aptitud.

GA adaptables

Los algoritmos genéticos con parámetros adaptativos (algoritmos genéticos adaptativos, AGA) son otra variante importante y prometedora de los algoritmos genéticos. Las probabilidades de cruce (pc) y mutación (pm) determinan en gran medida el grado de precisión de la solución y la velocidad de convergencia que pueden obtener los algoritmos genéticos. En lugar de utilizar valores fijos de pc y pm, los AGA utilizan la información de población en cada generación y ajustan de forma adaptativa pc y pm para mantener la diversidad de la población y la capacidad de convergencia. En AGA (algoritmo genético adaptativo), el ajuste de pc y pm depende de los valores de aptitud de las soluciones. EnCAGA (algoritmo genético adaptativo basado en agrupamiento), mediante el uso de análisis de agrupamiento para juzgar los estados de optimización de la población, el ajuste de pc y pm depende de estos estados de optimización. Puede ser bastante efectivo combinar GA con otros métodos de optimización. Un AG tiende a ser bastante bueno para encontrar buenas soluciones globales en general, pero bastante ineficiente para encontrar las últimas mutaciones para encontrar el óptimo absoluto. Otras técnicas (como el simple ascenso de colinas) son bastante eficientes para encontrar el óptimo absoluto en una región limitada. La alternancia de GA y escalada puede mejorar la eficiencia de GA mientras se supera la falta de robustez de la escalada.

Esto significa que las reglas de variación genética pueden tener un significado diferente en el caso natural. Por ejemplo, siempre que los pasos se almacenen en orden consecutivo, el cruce puede sumar una cantidad de pasos del ADN materno, agregar una cantidad de pasos del ADN paterno y así sucesivamente. Esto es como agregar vectores que probablemente sigan una cresta en el paisaje fenotípico. Por lo tanto, la eficiencia del proceso puede incrementarse en muchos órdenes de magnitud. Además, el operador de la inversión tiene la oportunidad de colocar los pasos en orden consecutivo o en cualquier otro orden adecuado a favor de la supervivencia o la eficiencia.

Una variación, en la que la población en su conjunto evoluciona en lugar de sus miembros individuales, se conoce como recombinación del acervo genético.

Se han desarrollado una serie de variaciones para intentar mejorar el rendimiento de los AG en problemas con un alto grado de epistasis de aptitud, es decir, donde la aptitud de una solución consiste en subconjuntos de sus variables que interactúan. Dichos algoritmos tienen como objetivo aprender (antes de explotar) estas interacciones fenotípicas beneficiosas. Como tales, están alineados con la hipótesis del bloque de construcción en la reducción adaptativa de la recombinación disruptiva. Los ejemplos destacados de este enfoque incluyen mGA, GEMGA y LLGA.

Dominios problemáticos

Los problemas que parecen ser particularmente apropiados para la solución mediante algoritmos genéticos incluyen problemas de cronograma y programación, y muchos paquetes de software de programación se basan en AG. Los GA también se han aplicado a la ingeniería. Los algoritmos genéticos a menudo se aplican como un enfoque para resolver problemas de optimización global.

Como regla general, los algoritmos genéticos pueden ser útiles en dominios problemáticos que tienen un panorama de aptitud complejo, ya que la mezcla, es decir, la mutación en combinación con el cruce, está diseñada para alejar a la población de los óptimos locales en los que un algoritmo tradicional de escalada podría atascarse. pulg. Observe que los operadores cruzados de uso común no pueden cambiar ninguna población uniforme. La mutación por sí sola puede proporcionar ergodicidad del proceso de algoritmo genético general (visto como una cadena de Markov).

Los ejemplos de problemas resueltos por algoritmos genéticos incluyen: espejos diseñados para canalizar la luz del sol hacia un colector solar, antenas diseñadas para captar señales de radio en el espacio, métodos de caminar para figuras de computadora, diseño óptimo de cuerpos aerodinámicos en campos de flujo complejos

En su Manual de diseño de algoritmos, Skiena desaconseja los algoritmos genéticos para cualquier tarea:

[E]s bastante antinatural modelar aplicaciones en términos de operadores genéticos como mutación y cruce en cadenas de bits. La pseudobiología agrega otro nivel de complejidad entre usted y su problema. En segundo lugar, los algoritmos genéticos tardan mucho en resolver problemas no triviales. [...] [L] a analogía con la evolución, donde un progreso significativo requiere [sic] millones de años, puede ser bastante apropiada.

[...]

Nunca me he encontrado con ningún problema en el que los algoritmos genéticos me pareciera la forma correcta de atacarlo. Además, nunca he visto resultados computacionales informados utilizando algoritmos genéticos que me hayan impresionado favorablemente. Apéguese al recocido simulado para sus necesidades de vudú de búsqueda heurística.

—Steven Skiena 

Historia

En 1950, Alan Turing propuso una "máquina de aprendizaje" que sería paralela a los principios de la evolución. La simulación por computadora de la evolución comenzó en 1954 con el trabajo de Nils Aall Barricelli, quien estaba usando la computadora en el Instituto de Estudios Avanzados en Princeton, Nueva Jersey. Su publicación de 1954 no fue muy notada. A partir de 1957, el genetista cuantitativo australiano Alex Fraser publicó una serie de artículos sobre simulación de selección artificial de organismos con múltiples loci que controlan un rasgo medible. A partir de estos comienzos, la simulación por computadora de la evolución realizada por biólogos se hizo más común a principios de la década de 1960, y los métodos se describieron en libros de Fraser y Burnell (1970) y Crosby (1973).Las simulaciones de Fraser incluían todos los elementos esenciales de los algoritmos genéticos modernos. Además, Hans-Joachim Bremermann publicó una serie de artículos en la década de 1960 que también adoptaron una población de solución a problemas de optimización, experimentando recombinación, mutación y selección. La investigación de Bremermann también incluyó los elementos de los algoritmos genéticos modernos. Otros pioneros notables incluyen a Richard Friedberg, George Friedman y Michael Conrad. Fogel (1998) reimprime muchos de los primeros artículos.

Aunque Barricelli, en un trabajo que informó en 1963, había simulado la evolución de la capacidad de jugar un juego simple, la evolución artificial solo se convirtió en un método de optimización ampliamente reconocido como resultado del trabajo de Ingo Rechenberg y Hans-Paul Schwefel en la década de 1960 y principios. Década de 1970: el grupo de Rechenberg pudo resolver problemas de ingeniería complejos a través de estrategias de evolución. Otro enfoque fue la técnica de programación evolutiva de Lawrence J. Fogel, que se propuso para generar inteligencia artificial. La programación evolutiva originalmente usó máquinas de estados finitos para predecir entornos y usó variación y selección para optimizar la lógica predictiva. Los algoritmos genéticos en particular se hicieron populares gracias al trabajo de John Holland a principios de la década de 1970, y en particular a su libroAdaptación en Sistemas Naturales y Artificiales (1975). Su trabajo se originó con estudios de autómatas celulares, realizados por Holland y sus estudiantes en la Universidad de Michigan. Holland introdujo un marco formalizado para predecir la calidad de la próxima generación, conocido como el Teorema del Esquema de Holland. La investigación en AG siguió siendo en gran medida teórica hasta mediados de la década de 1980, cuando se celebró la Primera Conferencia Internacional sobre Algoritmos Genéticos en Pittsburgh, Pensilvania.

Productos comerciales

A fines de la década de 1980, General Electric comenzó a vender el primer producto de algoritmo genético del mundo, un conjunto de herramientas basado en mainframe diseñado para procesos industriales. En 1989, Axcelis, Inc. lanzó Evolver, el primer producto GA comercial del mundo para computadoras de escritorio. El escritor de tecnología del New York Times, John Markoff, escribió sobre Evolver en 1990, y siguió siendo el único algoritmo genético comercial interactivo hasta 1995. Evolver se vendió a Palisade en 1997, se tradujo a varios idiomas y actualmente se encuentra en su sexta versión. Desde la década de 1990, MATLAB ha incorporado tres algoritmos heurísticos de optimización sin derivados (recocido simulado, optimización de enjambre de partículas, algoritmo genético) y dos algoritmos de búsqueda directa (búsqueda simplex, búsqueda de patrones).

Técnicas relacionadas

Campos principales

Los algoritmos genéticos son un subcampo:

• Algoritmos evolutivos
• Computación evolutiva
• Metaheurísticas
• Optimización estocástica
• Mejoramiento

Campos relacionados

Algoritmos evolutivos

Los algoritmos evolutivos son un subcampo de la computación evolutiva.

• Las estrategias de evolución (ES, véase Rechenberg, 1994) hacen evolucionar a los individuos mediante mutación y recombinación intermedia o discreta. Los algoritmos ES están diseñados especialmente para resolver problemas en el dominio del valor real. Utilizan la autoadaptación para ajustar los parámetros de control de la búsqueda. La des-aleatorización de la autoadaptación ha llevado a la actual Estrategia de Evolución de Adaptación de Matriz de Covarianza (CMA-ES).
• La programación evolutiva (PE) involucra poblaciones de soluciones con principalmente mutación y selección y representaciones arbitrarias. Utilizan la autoadaptación para ajustar los parámetros y pueden incluir otras operaciones de variación, como combinar información de varios padres.
• El algoritmo de estimación de distribución (EDA) sustituye a los operadores de reproducción tradicionales por operadores guiados por modelos. Dichos modelos se aprenden de la población mediante el empleo de técnicas de aprendizaje automático y se representan como modelos gráficos probabilísticos, a partir de los cuales se pueden muestrear o generar nuevas soluciones a partir de un cruce guiado.
• La programación genética (GP) es una técnica relacionada popularizada por John Koza en la que se optimizan los programas informáticos, en lugar de los parámetros de función. La programación genética a menudo utiliza estructuras de datos internas basadas en árboles para representar los programas informáticos para la adaptación en lugar de las estructuras de lista típicas de los algoritmos genéticos. Hay muchas variantes de la programación genética, incluida la programación genética cartesiana, la programación de expresión génica, la evolución gramatical, la programación genética lineal, la programación de expresiones múltiples, etc.
• El algoritmo genético de agrupación (GGA) es una evolución del GA donde el enfoque se cambia de elementos individuales, como en los GA clásicos, a grupos o subconjuntos de elementos. La idea detrás de esta evolución de GA propuesta por Emanuel Falkenauer es que resolver algunos problemas complejos, también conocidos como agrupamiento o particiónLos problemas en los que un conjunto de elementos debe dividirse en un grupo disjunto de elementos de una manera óptima, se resolverían mejor haciendo que las características de los grupos de elementos fueran equivalentes a los genes. Este tipo de problemas incluyen el empaquetamiento de contenedores, el equilibrio de líneas, la agrupación con respecto a una medida de distancia, pilas iguales, etc., en los que los GA clásicos demostraron tener un desempeño deficiente. Hacer que los genes sean equivalentes a grupos implica cromosomas que son, en general, de longitud variable y operadores genéticos especiales que manipulan grupos completos de elementos. Para el empaque en contenedores en particular, un GGA hibridado con el Criterio de Dominancia de Martello y Toth, es posiblemente la mejor técnica hasta la fecha.
• Los algoritmos evolutivos interactivos son algoritmos evolutivos que utilizan la evaluación humana. Por lo general, se aplican a dominios en los que es difícil diseñar una función de aptitud computacional, por ejemplo, imágenes, música, diseños artísticos y formas en evolución para adaptarse a las preferencias estéticas de los usuarios.

Inteligencia de enjambre

La inteligencia de enjambre es un subcampo de la computación evolutiva.

• La optimización de colonias de hormigas (ACO) utiliza muchas hormigas (o agentes) equipadas con un modelo de feromonas para atravesar el espacio de la solución y encontrar áreas productivas localmente.
• Aunque se considera un algoritmo de estimación de distribución, la optimización de enjambre de partículas (PSO) es un método computacional para la optimización de parámetros múltiples que también utiliza un enfoque basado en la población. Una población (enjambre) de soluciones candidatas (partículas) se mueve en el espacio de búsqueda, y el movimiento de las partículas está influenciado tanto por su propia posición mejor conocida como por la posición global mejor conocida del enjambre. Al igual que los algoritmos genéticos, el método PSO depende del intercambio de información entre los miembros de la población. En algunos problemas, el PSO suele ser más eficiente desde el punto de vista computacional que los AG, especialmente en problemas sin restricciones con variables continuas.

Otros algoritmos de computación evolutiva

El cálculo evolutivo es un subcampo de los métodos metaheurísticos.

• El algoritmo memético (MA), a menudo llamado algoritmo genético híbrido entre otros, es un método basado en la población en el que las soluciones también están sujetas a fases de mejora locales. La idea de los algoritmos meméticos proviene de los memes, que a diferencia de los genes, pueden adaptarse. En algunas áreas problemáticas, se muestra que son más eficientes que los algoritmos evolutivos tradicionales.
• Algoritmos bacteriológicos (BA) inspirados en la ecología evolutiva y, más concretamente, en la adaptación bacteriológica. La ecología evolutiva es el estudio de los organismos vivos en el contexto de su entorno, con el objetivo de descubrir cómo se adaptan. Su concepto básico es que en un entorno heterogéneo, no hay un individuo que encaje en todo el entorno. Entonces, uno necesita razonar a nivel de población. También se cree que los BA podrían aplicarse con éxito a problemas complejos de posicionamiento (antenas para teléfonos móviles, planificación urbana, etc.) o minería de datos.
• El algoritmo cultural (CA) consta de un componente de población casi idéntico al del algoritmo genético y, además, un componente de conocimiento denominado espacio de creencias.
• Evolución diferencial (DE) inspirada en la migración de superorganismos.
• La adaptación gaussiana (adaptación normal o natural, abreviada NA para evitar confusiones con GA) está destinada a maximizar el rendimiento de fabricación de los sistemas de procesamiento de señales. También se puede utilizar para la optimización paramétrica ordinaria. Se basa en cierto teorema válido para todas las regiones de aceptabilidad y todas las distribuciones gaussianas. La eficiencia de NA se basa en la teoría de la información y en cierto teorema de eficiencia. Su eficiencia se define como la información dividida por el trabajo necesario para obtener la información.Debido a que NA maximiza la aptitud media en lugar de la aptitud del individuo, el paisaje se suaviza de tal manera que los valles entre los picos pueden desaparecer. Por lo tanto, tiene cierta "ambición" de evitar picos locales en el panorama del fitness. NA también es bueno para escalar crestas afiladas mediante la adaptación de la matriz de momentos, porque NA puede maximizar el desorden (información promedio) de la Gaussiana al mismo tiempo que mantiene constante la aptitud media.

Otros métodos metaheurísticos

Los métodos metaheurísticos caen ampliamente dentro de los métodos de optimización estocástica.

• El recocido simulado (SA) es una técnica de optimización global relacionada que atraviesa el espacio de búsqueda probando mutaciones aleatorias en una solución individual. Siempre se acepta una mutación que aumenta la aptitud. Una mutación que reduce la aptitud se acepta probabilísticamente en función de la diferencia de aptitud y un parámetro de temperatura decreciente. En la jerga de SA, se habla de buscar la energía más baja en lugar de la máxima forma física. SA también se puede usar dentro de un algoritmo GA estándar comenzando con una tasa de mutación relativamente alta y disminuyéndola con el tiempo a lo largo de un programa determinado.
• La búsqueda tabú (TS) es similar al recocido simulado en que ambos atraviesan el espacio de la solución probando mutaciones de una solución individual. Mientras que el recocido simulado genera solo una solución mutada, la búsqueda tabú genera muchas soluciones mutadas y pasa a la solución con la energía más baja de las generadas. Para evitar ciclos y fomentar un mayor movimiento a través del espacio de soluciones, se mantiene una lista tabú de soluciones parciales o completas. Está prohibido pasar a una solución que contenga elementos de la lista tabú, que se actualiza a medida que la solución atraviesa el espacio de solución.
• Optimización extrema (EO) A diferencia de los AG, que funcionan con una población de soluciones candidatas, la EO desarrolla una única solución y realiza modificaciones locales a los peores componentes. Esto requiere que se seleccione una representación adecuada que permita asignar a los componentes individuales de la solución una medida de calidad ("fitness"). El principio rector detrás de este algoritmo es el de la mejora emergente mediante la eliminación selectiva de componentes de baja calidad y su sustitución por un componente seleccionado al azar. Esto está decididamente en desacuerdo con un GA que selecciona buenas soluciones en un intento de hacer mejores soluciones.

Otros métodos de optimización estocástica

• El método de entropía cruzada (CE) genera soluciones candidatas a través de una distribución de probabilidad parametrizada. Los parámetros se actualizan a través de la minimización de entropía cruzada, para generar mejores muestras en la siguiente iteración.
• La optimización de búsqueda reactiva (RSO) aboga por la integración de técnicas de aprendizaje automático subsimbólicas en la heurística de búsqueda para resolver problemas complejos de optimización. La palabra reactivo sugiere una respuesta lista a los eventos durante la búsqueda a través de un circuito interno de retroalimentación en línea para el autoajuste de parámetros críticos. Las metodologías de interés para la búsqueda reactiva incluyen el aprendizaje automático y las estadísticas, en particular el aprendizaje por refuerzo, el aprendizaje activo o de consulta, las redes neuronales y las metaheurísticas.