Hispanopedia Wiki
Articulo de referencia

Algoritmo genético

La antena de la nave espacial ST5 de la NASA de 2006. Esta compleja forma fue descubierta mediante un programa informático de diseño evolutivo para crear el mejor patrón de radi...

Hispanopedia WikiContenido en espanolLectura gratuita

La antena de la nave espacial ST5 de la NASA de 2006. Esta compleja forma fue descubierta mediante un programa informático de diseño evolutivo para crear el mejor patrón de radiación. Se la conoce como antena evolucionada .

Un algoritmo genético ( AG ) es una metaheurística inspirada en el proceso de selección natural que pertenece a la clase más amplia de algoritmos evolutivos (AE) en ciencias de la computación e investigación operativa . [ 1 ] Los algoritmos genéticos se utilizan comúnmente para generar soluciones de alta calidad a problemas de optimización y búsqueda mediante operadores de inspiración biológica como la selección , el cruce y la mutación . [ 2 ] Algunos ejemplos de aplicaciones de AG incluyen la optimización de árboles de decisión para un mejor rendimiento, la resolución de rompecabezas de sudoku , [ 3 ] la optimización de hiperparámetros y la inferencia causal . [ 4 ]

Metodología

Problemas de optimización

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

La evolución suele comenzar con una población de individuos generados aleatoriamente y es un proceso iterativo , donde la población en cada iteración se denomina 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 aleatoriamente) para formar una nueva generación. La nueva generación de soluciones candidatas se utiliza en la siguiente iteración del algoritmo . Generalmente, el algoritmo finaliza cuando se ha producido un número máximo de generaciones o cuando 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 ). [ 5 ] Se pueden usar matrices de otros tipos y estructuras de manera esencialmente similar. La propiedad principal que hace convenientes estas representaciones genéticas es que sus partes se alinean fácilmente debido a su tamaño fijo, lo que facilita operaciones de cruce simples . También se pueden usar representaciones de longitud variable, pero la implementación del cruce es más compleja en este caso. Las representaciones tipo árbol se exploran en la programación genética y las representaciones en forma de grafo se exploran en la programación evolutiva ; una combinación de cromosomas lineales y árboles se explora en la programación de expresión génica .

Una vez definidas la representación genética y la función de aptitud, un algoritmo genético 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 generalmente contiene cientos o miles de posibles soluciones. A menudo, la población inicial se genera aleatoriamente, lo que permite explorar todo el rango de posibles soluciones (el espacio de búsqueda ). En ocasiones, las soluciones pueden "sembrarse" en áreas donde es probable encontrar soluciones óptimas, o bien, la distribución de la probabilidad de muestreo se ajusta para centrarse en aquellas áreas de mayor interés. [ 6 ]

Selección

En cada generación sucesiva, se selecciona una parte de la población existente para reproducirse en una nueva generación. Las soluciones individuales se seleccionan mediante un proceso basado en la aptitud , donde las soluciones más aptas (medidas mediante una función de aptitud ) suelen tener mayor probabilidad de ser seleccionadas. Algunos métodos de selección evalúan la aptitud de cada solución y seleccionan preferentemente las mejores. Otros métodos evalúan solo una muestra aleatoria de la población, ya que el primer proceso puede ser muy lento.

La función de aptitud se define sobre la representación genética y mide la calidad de la solución representada. Esta función siempre depende del problema. Por ejemplo, en el problema de la mochila, se busca maximizar el valor total de los objetos que caben en una mochila de capacidad fija. Una representación de la solución podría ser una matriz de bits, donde cada bit representa un objeto diferente y su valor (0 o 1) indica 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 los valores de todos los objetos en la mochila si la representación es válida, o 0 en caso contrario.

En algunos problemas, resulta difícil o incluso imposible definir la expresión de aptitud; en estos casos, se puede utilizar una simulación para determinar el valor de la función de aptitud de un fenotipo (por ejemplo, se utiliza la dinámica de fluidos computacional para determinar la resistencia del aire de un vehículo cuya forma está codificada como fenotipo), o incluso se utilizan 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, mediante 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 "padre" del conjunto previamente seleccionado para su reproducción. Al producir una solución "hija" utilizando los métodos de cruce y mutación descritos anteriormente, se crea una nueva solución que generalmente comparte muchas de las características de sus "padres". Se seleccionan nuevos padres para cada nueva solución hija, y el proceso continúa hasta que se genera una nueva población de soluciones del tamaño adecuado. Si bien los métodos de reproducción basados ​​en el uso de dos padres están más "inspirados en la biología", algunas investigaciones [ 7 ] [ 8 ] sugieren que más de dos "padres" generan cromosomas de mayor calidad.

Estos procesos dan como resultado una población cromosómica de la siguiente generación distinta a la de la generación inicial. Generalmente, la aptitud promedio de la población aumenta gracias a este procedimiento, ya que solo se seleccionan para la reproducción los mejores organismos de la primera generación, junto con una pequeña proporción de individuos menos aptos. Estos individuos menos aptos garantizan la diversidad genética dentro del acervo genético de los progenitores y, por lo tanto, aseguran la diversidad genética de la siguiente generación de descendientes.

Existe división de opiniones sobre la importancia del entrecruzamiento frente a la mutación. En Fogel (2006) se encuentran numerosas referencias que respaldan la importancia de la búsqueda basada en mutaciones.

Conviene ajustar parámetros como la probabilidad de mutación , la probabilidad de cruce y el tamaño de la población para encontrar configuraciones adecuadas para la complejidad del problema . Una tasa de mutación muy baja puede provocar deriva genética (que es de naturaleza no ergódica ). Una tasa de recombinación demasiado alta puede llevar a la convergencia prematura del algoritmo genético. Una tasa de mutación excesiva puede conllevar la pérdida de buenas soluciones, a menos que se emplee selección elitista . Un tamaño de población adecuado garantiza la diversidad genética suficiente para el problema en cuestión, pero puede suponer un desperdicio de recursos computacionales si se establece en un valor mayor al necesario.

Heurísticas

Además de los operadores principales mencionados anteriormente, se pueden emplear otras heurísticas para acelerar o hacer más robusto el cálculo. La heurística de especiación penaliza el cruce entre soluciones candidatas demasiado similares; esto fomenta la diversidad de la población y ayuda a prevenir la convergencia prematura a una solución menos óptima. [ 9 ] [ 10 ]

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 solución mejor clasificada está alcanzando o ya ha alcanzado un punto de estancamiento, de modo que las iteraciones sucesivas ya no producen mejores resultados.
  • Inspección manual
  • Combinaciones de lo anterior

La hipótesis de los bloques de construcción

Los algoritmos genéticos son sencillos de implementar, pero su comportamiento es difícil de comprender. En particular, es difícil entender por qué estos algoritmos suelen generar soluciones de alta aptitud cuando se aplican a problemas prácticos. La hipótesis de los bloques de construcción (BBH, por sus siglas en inglés) consiste en:

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

Goldberg describe la heurística de la siguiente manera:

"Se muestrean esquemas cortos, de bajo orden y altamente adecuados, se recombinan (se cruzan) y se vuelven a muestrear para formar cadenas con una aptitud potencialmente mayor. En cierto modo, al trabajar con estos esquemas particulares (los bloques de construcción), hemos reducido la complejidad de nuestro problema; en lugar de construir cadenas de alto rendimiento probando todas las combinaciones posibles, construimos cadenas cada vez mejores a partir de las mejores soluciones parciales de muestreos anteriores".
"Dado que los esquemas altamente adecuados, de baja longitud y bajo orden, desempeñan 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 madera, un algoritmo genético busca un rendimiento casi óptimo mediante la yuxtaposición de esquemas cortos, de bajo orden y alto rendimiento, o bloques de construcción." [ 11 ]

A pesar de la falta de consenso sobre la validez de la hipótesis de los bloques de construcción, esta se ha evaluado y utilizado de forma consistente como referencia a lo largo de los años. Por ejemplo, se han propuesto muchos algoritmos de estimación de distribución en un intento de proporcionar un entorno en el que la hipótesis se cumpla. [ 12 ] [ 13 ] Si bien se han reportado 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 bloques de construcción como explicación de la eficiencia de los AG. De hecho, existe una cantidad considerable de trabajo que intenta comprender sus limitaciones desde la perspectiva de los algoritmos de estimación de distribución. [ 14 ] [ 15 ] [ 16 ]

Limitaciones

El uso práctico de un algoritmo genético tiene limitaciones, especialmente en comparación con algoritmos de optimización alternativos:

  • La evaluación repetida de la función de aptitud para problemas complejos suele ser el segmento más prohibitivo y limitante de los algoritmos evolutivos artificiales. Encontrar la solución óptima para problemas complejos, multidimensionales y multimodales a menudo requiere evaluaciones muy costosas de la función de aptitud . En problemas del mundo real, como los de optimización estructural, una sola evaluación de la función puede requerir desde varias horas hasta varios días de simulación completa. Los métodos de optimización típicos no pueden abordar este tipo de problemas. En este caso, puede ser necesario prescindir de una evaluación exacta y utilizar una función de aptitud aproximada que sea computacionalmente eficiente. Es evidente que la combinación de modelos aproximados puede ser uno de los enfoques más prometedores para utilizar de manera convincente los algoritmos genéticos en la resolución de problemas complejos de la vida real.
  • Los algoritmos genéticos no escalan bien con la complejidad. Es decir, cuando el número de elementos expuestos a mutación es grande, suele haber un aumento exponencial en el tamaño del espacio de búsqueda. Esto dificulta enormemente el uso de la técnica en problemas como el diseño de un motor, una casa o un avión . Para que estos problemas sean manejables mediante 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 de álabes de ventilador en lugar de motores, formas de edificios en lugar de planos de construcción detallados y perfiles aerodinámicos en lugar de diseños de aeronaves completas. El segundo problema de la complejidad es cómo proteger las partes que han evolucionado para representar buenas soluciones de mutaciones destructivas adicionales, particularmente cuando su evaluación de aptitud requiere que se combinen bien con otras partes.
  • La "mejor" solución solo se define en comparación con otras soluciones. Por lo tanto, el criterio de parada no está claro en todos los problemas.
  • En muchos problemas, los AG tienden a converger hacia óptimos locales o incluso puntos arbitrarios en lugar del óptimo global del problema. Esto significa que no "saben cómo" sacrificar la aptitud a corto plazo para obtener una aptitud a largo plazo. La probabilidad de que esto ocurra depende de la forma del paisaje de aptitud : ciertos problemas pueden proporcionar un ascenso fácil hacia un óptimo global, otros pueden facilitar que la función encuentre óptimos locales. Este problema puede mitigarse utilizando una función de aptitud diferente, aumentando la tasa de mutación o utilizando técnicas de selección que mantengan una población diversa de soluciones, [ 17 ] aunque el teorema de No Free Lunch [ 18 ] demuestra 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 con suficiente similitud (radio de nicho) se le añade una penalización, lo que reducirá la representación de ese grupo en generaciones posteriores, permitiendo que otros individuos (menos similares) se mantengan en la población. Sin embargo, este truco puede no ser efectivo, dependiendo del paisaje 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 la programación genética ) porque el cruce de una población homogénea no produce nuevas soluciones. En las estrategias evolutivas y la programación evolutiva , la diversidad no es esencial debido a una mayor dependencia de la mutación.
  • Trabajar con conjuntos de datos dinámicos es difícil, ya que los genomas tienden a converger rápidamente hacia soluciones que podrían dejar de ser válidas para datos posteriores. Se han propuesto varios métodos para remediar este problema, como aumentar la diversidad genética y prevenir la convergencia prematura, ya sea incrementando la probabilidad de mutación cuando la calidad de la solución disminuye ( hipermutación inducida ) o introduciendo ocasionalmente elementos completamente nuevos y generados aleatoriamente en el acervo genético ( inmigrantes aleatorios ). Asimismo, se pueden implementar estrategias evolutivas y programación evolutiva mediante una estrategia denominada "coma", en la que no se conservan los progenitores y los nuevos se seleccionan únicamente entre la descendencia. Esto puede resultar más eficaz en problemas dinámicos.
  • Los algoritmos genéticos (AG) no pueden resolver eficazmente problemas en los que la única medida de aptitud es un resultado binario de éxito/fracaso (como los problemas de decisión ), ya que no hay forma de converger hacia la solución (no hay una colina que escalar). En estos casos, una búsqueda aleatoria puede encontrar una solución tan rápidamente como un AG. Sin embargo, si la situación permite repetir el ensayo de éxito/fracaso, obteniendo resultados (posiblemente) diferentes, entonces la proporción de éxitos a fracasos proporciona una medida de aptitud adecuada.
  • Para problemas de optimización específicos e instancias de problemas concretas, otros algoritmos de optimización pueden ser más eficientes que los algoritmos genéticos en términos de velocidad de convergencia. Entre los algoritmos alternativos y complementarios se incluyen las estrategias evolutivas , la programación evolutiva , el recocido simulado , la adaptación gaussiana , el ascenso de colinas y la inteligencia de enjambre (por ejemplo, la optimización por colonia de hormigas y la optimización por enjambre de partículas ), así como los métodos basados ​​en la programación lineal entera . La idoneidad de los algoritmos genéticos depende del nivel de conocimiento del problema; para problemas bien conocidos, a menudo existen 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 con enteros , aunque también es posible usar representaciones de punto flotante . La representación de punto flotante es natural para las estrategias evolutivas y la programación evolutiva . Se ha propuesto la noción de algoritmos genéticos de valor real, pero en realidad es un nombre inapropiado, ya que no representa la teoría de bloques de construcción propuesta por John Henry Holland en la década de 1970. Sin embargo, esta teoría cuenta con respaldo, basado en resultados teóricos y experimentales (véase más adelante). El algoritmo básico realiza cruces y mutaciones a nivel de bits. 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 . Los cruces y las mutaciones se realizan respetando 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 enteros mediante cadenas de bits, se suele emplear la codificación Gray . De esta forma, pequeños cambios en el entero pueden modificarse fácilmente mediante mutaciones o recombinaciones. Se ha comprobado que esto ayuda a prevenir la convergencia prematura en los llamados muros de Hamming , donde deben producirse demasiadas mutaciones simultáneas (o recombinaciones) para que el cromosoma alcance una mejor solución.

Otros enfoques implican el uso de matrices de números reales en lugar de cadenas de bits para representar cromosomas. Los resultados de la teoría de esquemas sugieren que, en general, cuanto menor sea el alfabeto, mejor será el rendimiento, pero inicialmente sorprendió a los investigadores que se obtuvieran buenos resultados al usar cromosomas de valores reales. Esto se explicó como el conjunto de valores reales en una población finita de cromosomas que forma un alfabeto virtual (cuando la selección y la recombinación son dominantes) con una cardinalidad mucho menor de la que se esperaría de una representación de punto flotante. [ 19 ] [ 20 ]

Se puede obtener una expansión del dominio de problemas accesibles del algoritmo genético mediante una codificación más compleja de los conjuntos de soluciones, concatenando varios tipos de genes codificados heterogéneamente en un cromosoma. [ 21 ] 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 controladores 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 secciones, y es una herramienta útil para el modelado y la simulación de sistemas adaptativos complejos, especialmente procesos evolutivos.

Otra expansión importante del espacio de soluciones accesibles del Algoritmo Genético (AG) fue impulsada por la necesidad de hacer que las representaciones se adaptaran a niveles variables de conocimiento sobre los estados de la solución. Las representaciones de longitud variable se inspiraron en la observación de que, en la naturaleza, la evolución tiende a progresar de organismos más simples a otros más complejos, lo que sugiere una razón subyacente para adoptar estructuras flexibles. [ 22 ] Una segunda motivación, más pragmática, fue que la mayoría de los problemas de ingeniería y basados ​​en el conocimiento del mundo real no se ajustan naturalmente a estructuras de conocimiento rígidas. [ 23 ]

Estas innovaciones iniciales en representaciones de longitud variable sentaron las bases esenciales para el desarrollo de la programación genética , que a su vez extendió el paradigma clásico de los algoritmos genéticos. Dichas representaciones requirieron mejoras en los operadores genéticos simplistas utilizados para cromosomas de longitud fija, lo que permitió el surgimiento de modelos de algoritmos genéticos más sofisticados y adaptativos.

Elitismo

Una variante práctica del proceso general de construcción de una nueva población consiste en permitir que el o los mejores organismos de la generación actual pasen a la siguiente sin cambios. Esta estrategia se conoce como selección elitista y garantiza que la calidad de la solución obtenida por el AG no disminuya de una generación a la siguiente. [ 24 ]

Implementaciones paralelas

Las implementaciones paralelas de algoritmos genéticos se presentan en dos variantes. Los algoritmos genéticos paralelos de grano grueso asumen una población en cada nodo 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 de procesamiento que interactúa con 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 temporal o ruido en la función de aptitud.

AG adaptativos

Los algoritmos genéticos con parámetros adaptativos (algoritmos genéticos adaptativos, AGA) constituyen otra variante significativa 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 alcanzar los algoritmos genéticos. Los investigadores han analizado analíticamente la convergencia de los GA. [ 25 ] [ 26 ]

En lugar de usar valores fijos de pc y pm , los AGA utilizan la información de la población en cada generación y ajustan adaptativamente pc y pm para mantener la diversidad de la población y sostener la capacidad de convergencia. En AGA (algoritmo genético adaptativo), [ 27 ] el ajuste de pc y pm depende de los valores de aptitud de las soluciones. Hay más ejemplos de variantes de AGA: el método de zoom sucesivo es un ejemplo temprano de mejora de la convergencia. [ 28 ] En CAGA (algoritmo genético adaptativo basado en agrupamiento), [ 29 ] 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. Enfoques recientes utilizan variables más abstractas para decidir pc y pm . Ejemplos son los principios de dominancia y codominancia [ 30 ] y LIGA (algoritmo genético interpolativo nivelado), que combina un GA flexible con una búsqueda A* modificada para abordar la anisotropía del espacio de búsqueda. [ 31 ]

Combinar algoritmos genéticos (AG) con otros métodos de optimización puede ser muy eficaz. Los AG suelen ser buenos para encontrar soluciones globales generalmente buenas, pero bastante ineficientes para encontrar las últimas mutaciones necesarias para hallar 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 entre AG y ascenso de colinas puede mejorar la eficiencia de los AG y, al mismo tiempo, superar la falta de robustez de este último.

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 entrecruzamiento puede sumar varios pasos del ADN materno, añadir varios pasos del ADN paterno, y así sucesivamente. Esto es como sumar 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 inversión tiene la oportunidad de colocar los pasos en orden consecutivo o en cualquier otro orden adecuado para favorecer la supervivencia o la eficiencia. [ 32 ]

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

Se han desarrollado varias variantes 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 interactivos de sus variables. Estos algoritmos buscan aprender (antes de explotar) estas interacciones fenotípicas beneficiosas. Por lo tanto, se alinean con la Hipótesis de los Bloques de Construcción al reducir adaptativamente la recombinación disruptiva. Ejemplos destacados de este enfoque incluyen mGA, [ 33 ] GEMGA [ 34 ] y LLGA. [ 35 ]

Ámbitos problemáticos

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

Como regla general, los algoritmos genéticos pueden ser útiles en dominios de problemas con un paisaje 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 de ascenso de colinas tradicional podría quedarse atascado. Cabe señalar que los operadores de cruce comúnmente utilizados no pueden modificar una población uniforme. La mutación por sí sola puede proporcionar ergodicidad al proceso general del algoritmo genético (considerado como una cadena de Markov ).

Ejemplos de problemas resueltos por algoritmos genéticos incluyen: espejos diseñados para canalizar la luz solar hacia un colector solar, [ 37 ] antenas diseñadas para captar señales de radio en el espacio, [ 38 ] métodos de caminata para figuras de computadora, [ 39 ] diseño óptimo de cuerpos aerodinámicos en campos de flujo complejos. [ 40 ]

En su Manual de Diseño de Algoritmos , Skiena desaconseja el uso de algoritmos genéticos para cualquier tarea:

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

[...]

Nunca me he topado con ningún problema en el que los algoritmos genéticos me parecieran la solución adecuada. Además, nunca he visto resultados computacionales publicados que utilicen algoritmos genéticos que me hayan impresionado favorablemente. Para tus necesidades de búsqueda heurística, mejor utiliza el recocido simulado .

—Steven Skiena [ 41 ] : 267

Historia

En 1950, Alan Turing propuso una "máquina de aprendizaje" que sería paralela a los principios de la evolución. [ 42 ] La simulación por computadora de la evolución comenzó ya en 1954 con el trabajo de Nils Aall Barricelli , quien estaba usando la computadora en el Instituto de Estudios Avanzados en Princeton, Nueva Jersey . [ 43 ] [ 44 ] Su publicación de 1954 no tuvo mucha repercusión. A partir de 1957, [ 45 ] el genetista cuantitativo australiano Alex Fraser publicó una serie de artículos sobre la simulación de la selección artificial de organismos con múltiples loci que controlan un rasgo medible. A partir de estos inicios, la simulación por computadora de la evolución por parte de los biólogos se hizo más común a principios de la década de 1960, y los métodos fueron descritos en libros de Fraser y Burnell (1970) [ 46 ] y Crosby (1973). [ 47 ] 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 soluciones a problemas de optimización, sometidas a recombinación, mutación y selección. La investigación de Bremermann también incluyó elementos de algoritmos genéticos modernos. [ 48 ] Otros pioneros notables incluyen a Richard Friedberg, George Friedman y Michael Conrad. Muchos de los primeros artículos son reimpresos por Fogel (1998). [ 49 ]

Aunque Barricelli, en un trabajo que publicó en 1963, había simulado la evolución de la capacidad de jugar un juego simple, [ 50 ] 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 las décadas de 1960 y principios de 1970 ; el grupo de Rechenberg pudo resolver problemas de ingeniería complejos a través de estrategias evolutivas . [ 51 ] [ 52 ] [ 53 ] [ 54 ] 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 utilizó máquinas de estados finitos para predecir entornos, y utilizó variación y selección para optimizar las lógicas predictivas. Los algoritmos genéticos en particular se hicieron populares a través del trabajo de John Holland a principios de la década de 1970, y particularmente su libro Adaptació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 siguiente generación, conocido como el Teorema del Esquema de Holland . La investigación en algoritmos genéticos 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 finales 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. [ 55 ] En 1989, Axcelis, Inc. lanzó Evolver , el primer producto comercial de GA del mundo para computadoras de escritorio. El escritor de tecnología del New York Times, John Markoff, escribió [ 56 ] sobre Evolver en 1990, y siguió siendo el único algoritmo genético comercial interactivo hasta 1995. [ 57 ] Evolver fue vendido a Palisade en 1997, traducido a varios idiomas y actualmente se encuentra en su sexta versión. [ 58 ] Desde la década de 1990, MATLAB ha incorporado tres algoritmos heurísticos de optimización sin derivadas (recocido simulado, optimización por enjambre de partículas, algoritmo genético) y dos algoritmos de búsqueda directa (búsqueda simplex, búsqueda de patrones). [ 59 ]

Campos principales

Los algoritmos genéticos son un subcampo:

Algoritmos evolutivos

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

  • Las estrategias evolutivas (EE, véase Rechenberg, 1994) hacen evolucionar a los individuos mediante mutación y recombinación intermedia o discreta. Los algoritmos EE están diseñados particularmente para resolver problemas en el dominio de los valores reales. [ 60 ] Utilizan la autoadaptación para ajustar los parámetros de control de la búsqueda. La desaleatorización de la autoadaptación ha dado lugar a la estrategia evolutiva de adaptación de matriz de covarianza ( CMA-EE ) contemporánea.
  • La programación evolutiva (PE) implica poblaciones de soluciones con mutación y selección como procesos principales, y representaciones arbitrarias. Utiliza la autoadaptación para ajustar parámetros y puede incluir otras operaciones de variación, como la combinación de información de múltiples progenitores.
  • El algoritmo de estimación de distribución (EDA) sustituye los operadores de reproducción tradicionales por operadores guiados por modelos. Estos modelos se aprenden a partir de la población mediante técnicas de aprendizaje automático y se representan como modelos gráficos probabilísticos, a partir de los cuales se pueden muestrear nuevas soluciones [ 61 ] [ 62 ] o generar mediante cruce guiado [ 63 ] .
  • La programación genética (PG) es una técnica relacionada, popularizada por John Koza , en la que se optimizan programas informáticos en lugar de parámetros de funciones. La programación genética suele utilizar estructuras de datos internas basadas en árboles para representar los programas informáticos que se adaptan, en lugar de las estructuras de lista típicas de los algoritmos genéticos. Existen muchas variantes de la programación genética, entre ellas la programación genética cartesiana , la programación de expresión génica , [ 64 ] la evolución gramatical , la programación genética lineal , la programación de expresiones múltiples , etc.
  • El algoritmo genético de agrupamiento (GGA) es una evolución del GA donde el enfoque se desplaza de los elementos individuales, como en los GA clásicos, a grupos o subconjuntos de elementos. [ 65 ] La idea detrás de esta evolución del GA propuesta por Emanuel Falkenauer es que la resolución de algunos problemas complejos, también conocidos como problemas de agrupamiento o partición donde un conjunto de elementos debe dividirse en grupos disjuntos de elementos de manera óptima, se lograría mejor haciendo que las características de los grupos de elementos sean equivalentes a genes. Este tipo de problemas incluyen el empaquetamiento de contenedores , el equilibrio de líneas, el agrupamiento con respecto a una medida de distancia, pilas iguales, etc., en los que los GA clásicos demostraron tener un rendimiento 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 empaquetamiento de 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. Suelen aplicarse a ámbitos donde resulta difícil diseñar una función de aptitud computacional, por ejemplo, la evolución de imágenes, música, diseños artísticos y formas para adaptarlos 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 por colonia de hormigas ( ACO , por sus siglas en inglés) utiliza muchas hormigas (o agentes) equipadas con un modelo de feromonas para recorrer el espacio de soluciones y encontrar áreas localmente productivas.
  • Aunque se considera un algoritmo de estimación de distribución , [ 66 ] la optimización por enjambre de partículas (PSO) es un método computacional para la optimización multiparamétrica que también utiliza un enfoque basado en poblaciones. 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 mejor posición conocida como por la mejor posición conocida global 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 computacionalmente más eficiente que los GA, especialmente en problemas sin restricciones con variables continuas. [ 67 ]

Otros algoritmos de computación evolutiva

La computación evolutiva es un subcampo de los métodos metaheurísticos .

  • El algoritmo memético (AM), también conocido como algoritmo genético híbrido , es un método basado en poblaciones donde las soluciones se someten a fases de mejora local. La idea de los algoritmos meméticos proviene de los memes , que, a diferencia de los genes, pueden adaptarse. En algunos ámbitos, han demostrado ser más eficientes que los algoritmos evolutivos tradicionales.
  • Algoritmos bacteriológicos (AB) inspirados en la ecología evolutiva y, más particularmente, en la adaptación bacteriológica. La ecología evolutiva estudia 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 existe un único individuo que se adapte a todo el entorno. Por lo tanto, es necesario razonar a nivel poblacional. También se cree que los AB podrían aplicarse con éxito a problemas complejos de posicionamiento (antenas para teléfonos móviles, planificación urbana, etc.) o a la minería de datos. [ 68 ]
  • El algoritmo cultural (AC) consta de un componente poblacional casi idéntico al del algoritmo genético y, además, de un componente de conocimiento denominado espacio de creencias.
  • Evolución diferencial (ED) inspirada en la migración de superorganismos. [ 69 ]
  • 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 sistemas de procesamiento de señales. También puede utilizarse para la optimización paramétrica ordinaria. Se basa en un teorema válido para todas las regiones de aceptabilidad y todas las distribuciones gaussianas. La eficiencia de la NA se basa en la teoría de la información y en un teorema de eficiencia. Su eficiencia se define como la información dividida por el trabajo necesario para obtenerla. [ 70 ] Dado que la NA maximiza la aptitud media en lugar de la aptitud individual, el paisaje se suaviza de tal manera que los valles entre picos pueden desaparecer. Por lo tanto, tiene cierta "ambición" de evitar picos locales en el paisaje de aptitud. La NA también es buena para superar crestas pronunciadas mediante la adaptación de la matriz de momentos, ya que puede maximizar el desorden ( información media ) de la gaussiana manteniendo simultáneamente la aptitud media constante.

Otros métodos metaheurísticos

Los métodos metaheurísticos se engloban, en términos generales, dentro de los métodos de optimización estocástica .

  • El recocido simulado (SA) es una técnica de optimización global relacionada que recorre el espacio de búsqueda probando mutaciones aleatorias en una solución individual. Una mutación que aumenta la aptitud siempre se acepta. Una mutación que la disminuye se acepta probabilísticamente en función de la diferencia de aptitud y un parámetro de temperatura decreciente. En la jerga del SA, se habla de buscar la energía más baja en lugar de la aptitud máxima. El SA también se puede utilizar dentro de un algoritmo genético estándar comenzando con una tasa de mutación relativamente alta y disminuyéndola con el tiempo según un cronograma determinado.
  • La búsqueda tabú (TS) es similar al recocido simulado, ya que ambos recorren el espacio de soluciones probando mutaciones de una solución individual. Mientras que el recocido simulado genera solo una solución mutada, la búsqueda tabú genera muchas y se dirige a la solución con la energía más baja entre las generadas. Para evitar ciclos y fomentar un mayor avance en el espacio de soluciones, se mantiene una lista tabú con soluciones parciales o completas. Está prohibido moverse a una solución que contenga elementos de la lista tabú, la cual se actualiza a medida que la solución recorre el espacio de soluciones.
  • Optimización extremal (OE) A diferencia de los algoritmos genéticos (AG), que trabajan con una población de soluciones candidatas, la OE desarrolla una única solución y realiza modificaciones locales en los componentes de peor calidad. Esto requiere la selección de una representación adecuada que permita asignar una medida de calidad ("aptitud") a los componentes individuales de la solución. El principio rector de este algoritmo es la mejora emergente mediante la eliminación selectiva de componentes de baja calidad y su sustitución por un componente seleccionado aleatoriamente. Esto contrasta notablemente con un AG que selecciona buenas soluciones para intentar crear soluciones aún mejores.

Otros métodos de optimización estocástica

  • El método de entropía cruzada (CE) genera soluciones candidatas mediante una distribución de probabilidad parametrizada. Los parámetros se actualizan mediante la minimización de la entropía cruzada, con el fin de 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ólico en heurísticas de búsqueda para resolver problemas de optimización complejos. El término "reactiva" sugiere una respuesta inmediata a los eventos durante la búsqueda mediante un bucle de retroalimentación interno en línea para el autoajuste de parámetros críticos. Entre las metodologías de interés para la búsqueda reactiva se incluyen el aprendizaje automático y la estadística, en particular el aprendizaje por refuerzo , el aprendizaje activo o de consultas , las redes neuronales y las metaheurísticas .

Véase también

Referencias

  1. ↑ Pétrowski, Alain; Ben-Hamida, Sana (2017). Algoritmos evolutivos . John Wiley & Sons. pág.  30. ISBN 978-1-119-13638-5.
  2. ↑ Mitchell 1996 , pág. 2.
  3. ↑ Gerges, Firas; Zouein, Germain; Azar, Danielle (12 de marzo de 2018). «Algoritmos genéticos con manejo de óptimos locales para resolver sudokus» . Actas de la Conferencia Internacional de Computación e Inteligencia Artificial de 2018. ICCAI 2018. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 19-22 . doi : 10.1145/3194452.3194463 . ISBN  978-1-4503-6419-5. S2CID 44152535 . 
  4. ↑ Burkhart, Michael C.; Ruiz, Gabriel (2023). "Representaciones neuroevolutivas para el aprendizaje de efectos de tratamiento heterogéneos" . Journal of Computational Science . 71 102054. doi : 10.1016/j.jocs.2023.102054 . S2CID 258752823 . 
  5. 1 2 Whitley 1994 , pág. 66.
  6. ↑ Luque-Rodríguez, María; Molina-Baena, José; Jiménez-Vilchez, Alfonso; Arauzo-Azofra, Antonio (2022). "Inicialización de la búsqueda de selección de funciones para clasificación (sec. 3)" . Revista de investigación en inteligencia artificial . 75 : 953– 983. doi : 10.1613/jair.1.14015 .
  7. ↑ Eiben, AE et al (1994). "Algoritmos genéticos con recombinación multiparental". PPSN III: Actas de la Conferencia Internacional sobre Computación Evolutiva. Tercera Conferencia sobre Resolución de Problemas Paralelos inspirada en la Naturaleza: 78 – 87. ISBN 3-540-58484-6.
  8. ↑ Ting, Chuan-Kang (2005). "Sobre el tiempo medio de convergencia de algoritmos genéticos multiparentales sin selección". Avances en vida artificial: 403 – 412. ISBN 978-3-540-28848-0.
  9. ↑ Deb, Kalyanmoy; Spears, William M. (1997). "C6.2: Métodos de especiación". Manual de computación evolutiva . Institute of Physics Publishing. S2CID 3547258 . 
  10. ↑ Shir, Ofer M. (2012). "Niching in Evolutionary Algorithms". En Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (eds.). Handbook of Natural Computing . Springer Berlin Heidelberg. pp. 1035–1069 . doi : 10.1007/978-3-540-92910-9_32 . ISBN  9783540929093.
  11. ↑ Goldberg 1989 , pág. 41.
  12. ↑ Harik, Georges R.; Lobo, Fernando G.; Sastry, Kumara (1 de enero de 2006). «Aprendizaje de enlaces mediante modelado probabilístico en el algoritmo genético compacto extendido (ECGA)». Optimización escalable mediante modelado probabilístico . Estudios en inteligencia computacional. Vol. 33. págs. 39–61 . doi : 10.1007/978-3-540-34954-9_3 . ISBN   978-3-540-34953-2.
  13. ^ Pelikan, Martín; Goldberg, David E.; Cantú-Paz, Erick (1 de enero de 1999). BOA: El algoritmo de optimización bayesiano . Gecco'99. págs. 525 a 532. ISBN  9781558606111.{{cite book}}: |journal=ignorado ( ayuda )
  14. ↑ Coffin, David; Smith, Robert E. (1 de enero de 2008). «Aprendizaje de vinculación en algoritmos de estimación de distribución». Vinculación en computación evolutiva . Estudios en inteligencia computacional. Vol. 157. págs. 141–156 . doi : 10.1007/978-3-540-85068-7_7 . ISBN   978-3-540-85067-0.
  15. ↑ Echegoyen, Carlos; Mendiburu, Alexander; Santana, Roberto; Lozano, Jose A. (8 de noviembre de 2012). "Sobre la taxonomía de los problemas de optimización bajo algoritmos de estimación de distribución". Evolutionary Computation . 21 (3): 471– 495. doi : 10.1162/EVCO_a_00095 . ISSN 1063-6560 . PMID 23136917. S2CID 26585053 .   
  16. ↑ Sadowski, Krzysztof L.; Bosman, Peter AN; Thierens, Dirk (1 de enero de 2013). "Sobre la utilidad del procesamiento de enlaces para resolver MAX-SAT". Actas de la 15.ª conferencia anual sobre computación genética y evolutiva . Gecco '13. págs. 853–860 . doi : 10.1145/2463372.2463474 . hdl : 1874/290291 . ISBN  9781450319638. S2CID 9986768 . 
  17. ↑ Taherdangkoo, Mohammad; Paziresh, Mahsa; Yazdi, Mehran; Bagheri, Mohammad Hadi (19 de noviembre de 2012). "Un algoritmo eficiente para la optimización de funciones: algoritmo de células madre modificado" . Central European Journal of Engineering . 3 (1): 36– 50. doi : 10.2478/s13531-012-0047-8 .
  18. ↑ Wolpert, DH, Macready, WG, 1995. No Free Lunch Theorems for Optimisation. Santa Fe Institute, SFI-TR-05-010, Santa Fe.
  19. ↑ Goldberg, David E. (1991). «La teoría de los alfabetos virtuales». Resolución de problemas paralelos inspirada en la naturaleza . Notas de clase en informática. Vol. 496. págs. 13–22 . doi : 10.1007/BFb0029726 . ISBN   978-3-540-54148-6.{{cite book}}: |journal=ignorado ( ayuda )
  20. ↑ Janikow, CZ; Michalewicz, Z. (1991). "Una comparación experimental de representaciones binarias y de punto flotante en algoritmos genéticos" (PDF) . Actas de la Cuarta Conferencia Internacional sobre Algoritmos Genéticos : 31–36 . Archivado (PDF) del original el 9 de octubre de 2022. Recuperado el 2 de julio de 2013 .
  21. ↑ Patrascu, M.; Stancu, AF; Pop, F. (2014). "HELGA: un algoritmo genético realista de codificación heterogénea para el modelado y la simulación de la evolución de poblaciones". Soft Computing . 18 (12): 2565– 2576. doi : 10.1007/s00500-014-1401-y . S2CID 29821873 . 
  22. ↑ Goldberg, DE, Korb, B., & Deb, K. (1989). Algoritmos genéticos desordenados: motivación, análisis y primeros resultados. Complex Systems, 3(5), 493–530. ISSN 0891-2513.
  23. ↑ Davidor, Y. (1991). Algoritmos genéticos y robótica: una estrategia heurística para la optimización. World Scientific Series in Robotics and Intelligent Systems: Volumen 1.
  24. ↑ Baluja, Shumeet; Caruana, Rich (1995). Eliminando la genética del algoritmo genético estándar (PDF) . ICML . Archivado (PDF) del original el 9 de octubre de 2022.
  25. ↑ Stannat, W. (2004). "Sobre la convergencia de algoritmos genéticos: un enfoque variacional" . Probab. Theory Relat. Fields . 129 : 113–132 . doi : 10.1007/s00440-003-0330-y . S2CID 121086772 . 
  26. ↑ Sharapov, RR; Lapshin, AV (2006). "Convergencia de algoritmos genéticos". Pattern Recognit. Image Anal . 16 (3): 392– 397. doi : 10.1134/S1054661806030084 . S2CID 22890010 . 
  27. ↑ Srinivas, M.; Patnaik, L. (1994). "Probabilidades adaptativas de cruce y mutación en algoritmos genéticos" (PDF) . IEEE Transactions on Systems, Man, and Cybernetics . 24 (4): 656– 667. Bibcode : 1994ITSMC..24..656S . doi : 10.1109/21.286385 . Archivado (PDF) del original el 9 de octubre de 2022.
  28. ↑ Kwon, YD; Kwon, SB; Jin, SB; Kim, JY (2003). "Algoritmo genético de convergencia mejorada con método de zoom sucesivo para resolver problemas de optimización continua". Computers & Structures . 81 (17): 1715– 1725. doi : 10.1016/S0045-7949(03)00183-4 .
  29. ↑ Zhang, J.; Chung, H.; Lo, WL (2007). "Probabilidades de cruce y mutación adaptativas basadas en agrupamiento para algoritmos genéticos". IEEE Transactions on Evolutionary Computation . 11 (3): 326– 335. Bibcode : 2007ITEC...11..326Z . doi : 10.1109/TEVC.2006.880727 . S2CID 2625150 . 
  30. ↑ Pavai, G.; Geetha, TV (2019). "Nuevos operadores de cruce que utilizan principios de dominancia y codominancia para una convergencia más rápida de algoritmos genéticos". Soft Comput . 23 (11): 3661– 3686. doi : 10.1007/s00500-018-3016-1 . S2CID 254028984 . 
  31. ↑ Li, JCF; Zimmerle, D.; Young, P. (2022). "Electrificación rural en red flexible mediante algoritmo genético interpolativo nivelado" . Energy & AI . 10 100186. Bibcode : 2022EneAI..1000186L . doi : 10.1016/j.egyai.2022.100186 . S2CID 250972466 . 
  32. ↑ Véase, por ejemplo, Evolution-in-a-nutshell Archivado el 15 de abril de 2016 en Wayback Machine o ejemplo en el problema del viajante de comercio , en particular el uso de un operador de recombinación de bordes .
  33. ↑ Goldberg, DE; Korb, B.; Deb, K. (1989). "Algoritmos genéticos desordenados : análisis de la motivación y primeros resultados" . Sistemas complejos . 5 (3): 493– 530. 
  34. ↑ Expresión genética: El eslabón perdido en la computación evolutiva
  35. ↑ Harik, G. (1997). Aprendizaje de enlaces para resolver eficientemente problemas de dificultad limitada mediante algoritmos genéticos (Tesis doctoral). Departamento de Ciencias de la Computación, Universidad de Michigan, Ann Arbor.
  36. ↑ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. Reconfiguración óptima de Pareto de sistemas de distribución de energía mediante un algoritmo genético basado en NSGA-II. Energies. 2013; 6(3):1439-1455.
  37. ↑ Gross, Bill (2 de febrero de 2009). "Un sistema de energía solar que sigue al sol" . TED . Consultado el 20 de noviembre de 2013 .
  38. ↑ Hornby, GS; Linden, DS; Lohn, JD, Diseño automatizado de antenas con algoritmos evolutivos (PDF)
  39. ↑ "Locomoción flexible basada en músculos para criaturas bípedas" .
  40. ↑ Evans, B.; Walton, SP (diciembre de 2017). "Optimización aerodinámica de un vehículo de reentrada hipersónico basada en la solución de la ecuación de Boltzmann-BGK y optimización evolutiva" . Applied Mathematical Modelling . 52 : 215–240 . doi : 10.1016/j.apm.2017.07.024 . ISSN 0307-904X . 
  41. ↑ Skiena, Steven (2010). Manual de diseño de algoritmos (2.ª ed.). Springer Science+Business Media . ISBN  978-1-849-96720-4.
  42. ↑ Turing, Alan M. (octubre de 1950). "Máquinas de computación e inteligencia". Mind . LIX (238): 433– 460. doi : 10.1093/mind/LIX.236.433 .
  43. ^ Barricelli, Nils Aall (1954). "Ejemplos numéricos de procesos de evolución". Métodos : 45– 68.
  44. ↑ Barricelli, Nils Aall (1957). "Procesos de evolución simbiogenética realizados mediante métodos artificiales". Methodos : 143–182 .
  45. ↑ Fraser, Alex (1957). "Simulación de sistemas genéticos mediante computadoras digitales automáticas. I. Introducción" . Aust. J. Biol. Sci . 10 (4): 484– 491. Bibcode : 1957AuJBS..10..484F . doi : 10.1071/BI9570484 .
  46. ↑ Fraser, Alex ; Burnell, Donald (1970). Computer Models in Genetics . Nueva York: McGraw-Hill. ISBN 978-0-07-021904-5.
  47. ↑ Crosby, Jack L. (1973). Simulación por ordenador en genética . Londres: John Wiley & Sons. ISBN 978-0-471-18880-3.
  48. ↑ 27/02/96 - Hans Bremermann, profesor emérito de la UC Berkeley y pionero en biología matemática, falleció a los 69 años.
  49. ↑ Fogel, David B., ed. (1998). Computación evolutiva: El registro fósil . Nueva York: IEEE Press. ISBN 978-0-7803-3481-6.
  50. ↑ Barricelli, Nils Aall (1963). "Pruebas numéricas de teorías de la evolución. Parte II. Pruebas preliminares de rendimiento, simbiogénesis y vida terrestre". Acta Biotheoretica . 16 ( 3–4 ): 99–126 . doi : 10.1007/BF01556602 . S2CID 86717105 . 
  51. ^ Rechenberg, Ingo (1973). Estrategia de evoluciones . Stuttgart: Holzmann-Froboog. ISBN 978-3-7728-0373-4.
  52. ^ Schwefel, Hans-Paul (1974). Numerische Optimierung von Computer-Modellen (tesis doctoral) .
  53. ^ Schwefel, Hans-Paul (1977). Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie . Basilea; Stuttgart: Birkhäuser. ISBN  978-3-7643-0876-6.
  54. ^ Schwefel, Hans-Paul (1981). Optimización numérica de modelos informáticos (Traducción de 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie . Chichester; Nueva York: Wiley. ISBN 978-0-471-09988-8.
  55. ↑ Aldawoodi, Namir (2008). Un enfoque para el diseño de un piloto automático de helicóptero no tripulado mediante algoritmos genéticos y recocido simulado . pág. 99. ISBN  978-0549773498– vía Google Libros.
  56. ↑ Markoff, John (29 de agosto de 1990). "¿Cuál es la mejor respuesta? Es la supervivencia del más apto" . New York Times . Consultado el 13 de julio de 2016 .
  57. ↑ Ruggiero, Murray A. (1 de agosto de 2009) Quince años y contando. Archivado el 30 de enero de 2016 en Wayback Machine . Futuresmag.com. Recuperado el 7 de agosto de 2013.
  58. ↑ Evolver: Optimización sofisticada para hojas de cálculo . Palisade. Consultado el 7 de agosto de 2013.
  59. ↑ Li, Lin; Saldívar, Alfredo Alan Flores; Bai, Yun; Chen, Yi; Liu, Qunfeng; Li, Yun (2019). "Puntos de referencia para evaluar algoritmos de optimización y comparar optimizadores sin derivados de MATLAB para el acceso rápido de los profesionales" . Acceso IEEE . 7 : 79657– 79670. Código bibliográfico : 2019IEEEA...779657L . doi : 10.1109/ACCESS.2019.2923092 . S2CID 195774435 . 
  60. ↑ Cohoon, J; et al. (2002). Algoritmos evolutivos para el diseño físico de circuitos VLSI (PDF) . Springer, pp. 683-712, 2003. ISBN  978-3-540-43330-9Archivado (PDF) del original el 9 de octubre de 2022 .{{cite book}}: |journal=ignorado ( ayuda )
  61. ^ Pelikan, Martín; Goldberg, David E.; Cantú-Paz, Erick (1 de enero de 1999). BOA: El algoritmo de optimización bayesiano . Gecco'99. págs. 525 a 532. ISBN  9781558606111.{{cite book}}: |journal=ignorado ( ayuda )
  62. ↑ Pelikan, Martin (2005). Algoritmo de optimización bayesiana jerárquica : hacia una nueva generación de algoritmos evolutivos (1.ª ed.). Berlín [ua]: Springer. ISBN   978-3-540-23774-7.
  63. ↑ Thierens, Dirk (11 de septiembre de 2010). «El algoritmo genético del árbol de enlace». Resolución de problemas paralelos inspirada en la naturaleza, PPSN XI . págs. 264–273 . doi : 10.1007/978-3-642-15844-5_27 . ISBN  978-3-642-15843-8.
  64. ↑ Ferreira, C (2001). "Programación de expresión genética: un nuevo algoritmo adaptativo para resolver problemas" (PDF) . Sistemas complejos . 13 (2): 87–129 . arXiv : cs/0102027 . Bibcode : 2001cs........2027F . Archivado (PDF) del original el 9 de octubre de 2022.
  65. ↑ Falkenauer, Emanuel (1997). Algoritmos genéticos y problemas de agrupamiento . Chichester, Inglaterra: John Wiley & Sons Ltd. ISBN 978-0-471-97150-4.
  66. ↑ Zlochin, Mark; Birattari, Mauro; Meuleau, Nicolas; Dorigo, Marco (1 de octubre de 2004). "Búsqueda basada en modelos para la optimización combinatoria: una revisión crítica". Annals of Operations Research . 131 ( 1–4 ): 373–395 . CiteSeerX 10.1.1.3.427 . doi : 10.1023/B:ANOR.0000039526.52305.af . ISSN 0254-5330 . S2CID 63137 .   
  67. ↑ Rania Hassan, Babak Cohanim, Olivier de Weck, Gerhard Venter (2005) Una comparación de la optimización por enjambre de partículas y el algoritmo genético
  68. ^ Baudry, Benoit; Franck Fleurey; Jean-Marc Jézéquel ; Yves Le Traon (marzo-abril de 2005). "Optimización automática de casos de prueba: un algoritmo bacteriológico" (PDF) . Software IEEE . 22 (2): 76– 82. Código Bib : 2005ISoft..22b..76B . doi : 10.1109/MS.2005.30 . S2CID 3559602 . Archivado (PDF) desde el original el 9 de octubre de 2022 . Consultado el 9 de agosto de 2009 . 
  69. ↑ Civicioglu, P. (2012). "Transformación de coordenadas cartesianas geocéntricas a coordenadas geodésicas mediante un algoritmo de búsqueda diferencial". Computers & Geosciences . 46 : 229–247 . Bibcode : 2012CG.....46..229C . doi : 10.1016/j.cageo.2011.12.011 .
  70. ↑ Kjellström, G. (diciembre de 1991). "Sobre la eficiencia de la adaptación gaussiana". Journal of Optimization Theory and Applications . 71 (3): 589– 597. doi : 10.1007/BF00941405 . S2CID 116847975 . 

Bibliografía

  • Banzhaf, Wolfgang; Nordín, Peter; Keller, Robert; Francone, Frank (1998). Programación genética : una introducción . San Francisco, California: Morgan Kaufmann. ISBN 978-1558605107.
  • Bies, Robert R.; Muldoon, Matthew F.; Pollock, Bruce G.; Manuck, Steven; Smith, Gwenn; Sale, Mark E. (2006). "Un enfoque híbrido de aprendizaje automático basado en algoritmos genéticos para la selección de modelos". Journal of Pharmacokinetics and Pharmacodynamics . 33 (2): 196– 221. doi : 10.1007/s10928-006-9004-6 . PMID 16565924. S2CID 39571129 .  
  • Cha, Sung-Hyuk; Tappert, Charles C. (2009). "Un algoritmo genético para la construcción de árboles de decisión binarios compactos". Journal of Pattern Recognition Research . 4 (1): 1– 13. CiteSeerX 10.1.1.154.8314 . doi : 10.13176/11.44 . 
  • Eiben, Agoston; Smith, James (2003). Introducción a la computación evolutiva . Springer. ISBN 978-3540401841.
  • Fraser, Alex S. (1957). "Simulación de sistemas genéticos mediante computadoras digitales automáticas. I. Introducción" . Australian Journal of Biological Sciences . 10 (4): 484– 491. Bibcode : 1957AuJBS..10..484F . doi : 10.1071/BI9570484 .
  • Goldberg, David (1989). Algoritmos genéticos en búsqueda, optimización y aprendizaje automático . Reading, MA: Addison-Wesley Professional. ISBN 978-0201157673.
  • Goldberg, David (2002). El diseño de la innovación: lecciones de y para algoritmos genéticos competentes . Norwell, MA: Kluwer Academic Publishers. ISBN 978-1402070983.
  • Fogel, David (2006). Computación evolutiva: Hacia una nueva filosofía de la inteligencia artificial (3.ª  ed.). Piscataway, NJ: IEEE Press. ISBN 978-0471669517.
  • Hingston, Philip; Barone, Luigi; Michalewicz, Zbigniew (2008). Diseño por evolución: avances en diseño evolutivo . Springer. ISBN 978-3540741091.
  • Holland, John (1992). Adaptación en sistemas naturales y artificiales . Cambridge, MA: MIT Press. ISBN 978-0262581110.
  • Koza, John (1992). Programación genética: Sobre la programación de computadoras mediante selección natural . Cambridge, MA: MIT Press. ISBN 978-0262111706.
  • Michalewicz, Zbigniew (1996). Algoritmos genéticos + Estructuras de datos = Programas evolutivos . Springer-Verlag. ISBN 978-3540606765.
  • Mitchell, Melanie (1996). Introducción a los algoritmos genéticos . Cambridge, MA: MIT Press. ISBN 9780585030944.
  • Poli, R.; Langdon, WB; McPhee, NF (2008). Guía práctica de programación genética . Lulu.com, disponible gratuitamente en internet. ISBN 978-1-4092-0073-4.
  • Rechenberg, Ingo (1994): Evolutionsstrategie '94, Stuttgart: Fromman-Holzboog.
  • Schmitt, Lothar M.; Nehaniv, Chrystopher L.; Fujii, Robert H. (1998). "Análisis lineal de algoritmos genéticos" . Theoretical Computer Science . 208 : 111–148 .
  • Schmitt, Lothar M. (2001). "Teoría de los algoritmos genéticos" . Theoretical Computer Science . 259 ( 1–2 ): 1–61 . Bibcode : 2001TComS.259....1S . doi : 10.1016/S0304-3975(00)00406-0 .
  • Schmitt, Lothar M. (2004). "Teoría de algoritmos genéticos II: modelos para operadores genéticos sobre la representación tensorial de cadenas de poblaciones y convergencia a óptimos globales para una función de aptitud arbitraria bajo escalamiento" . Theoretical Computer Science . 310 ( 1–3 ): 181–231 . doi : 10.1016/S0304-3975(03)00393-1 .
  • Schwefel, Hans-Paul (1974): Numerische Optimierung von Computer-Modellen (tesis doctoral). Reimpreso por Birkhäuser (1977).
  • Vose, Michael (1999). El algoritmo genético simple: fundamentos y teoría . Cambridge, MA: MIT Press. ISBN 978-0262220583.
  • Whitley, Darrell (1994). " Tutorial sobre algoritmos genéticos" (PDF) . Statistics and Computing . 4 (2): 65– 85. Bibcode : 1994StCom...475354W . CiteSeerX 10.1.1.184.3999 . doi : 10.1007/BF00175354 . S2CID 3447126. Archivado (PDF) del original el 9 de octubre de 2022.  

Recursos

  • Proporciona una lista de recursos en el campo de los algoritmos genéticos.
  • Panorama general de la historia y las variantes de los algoritmos evolutivos

Tutoriales

  • Tutorial interactivo que explica los algoritmos genéticos. Utiliza ejemplos y experimentos que se ejecutan en el navegador, desde operaciones básicas hasta la resolución del problema del viajante.
  • Algoritmos genéticos: programas informáticos que "evolucionan" de forma similar a la selección natural pueden resolver problemas complejos que ni siquiera sus creadores comprenden del todo. Una excelente introducción a los algoritmos genéticos por John Holland, con una aplicación al dilema del prisionero.
  • Un tutorial interactivo en línea sobre algoritmos genéticos para que el lector practique o aprenda cómo funciona un AG : aprenda paso a paso o observe la convergencia global en lotes, cambie el tamaño de la población, las tasas/límites de cruce, las tasas/límites de mutación y los mecanismos de selección, y agregue restricciones.
  • Tutorial sobre algoritmos genéticos por Darrell Whitley, Departamento de Ciencias de la Computación, Universidad Estatal de Colorado. Un excelente tutorial con mucha teoría.
  • "Fundamentos de metaheurística" , 2009 (225 págs.). Texto libre y abierto de Sean Luke.
  • Algoritmos de optimización global : teoría y aplicación. Archivado el 11 de septiembre de 2008 en Wayback Machine.
  • Tutorial sobre algoritmos genéticos en Python : explicación de la lógica detrás de los algoritmos genéticos y su implementación en Python.
  • Los algoritmos genéticos evolucionan para resolver el dilema del prisionero. Escrito por Robert Axelrod.