Algoritmo competitivo para buscar un espacio problemático.
La antena de la nave espacial ST5 de la NASA de 2006 . Esta forma complicada fue encontrada mediante un programa de diseño informático evolutivo para crear el mejor patrón de radiación. Se la conoce como antena evolucionada .
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 pueden mutarse y alterarse; Tradicionalmente, las soluciones se representan en binario como cadenas de 0 y 1, pero también son posibles otras codificaciones. [4]
La evolución generalmente comienza a partir de 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 resuelve. 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 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.
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 ). [4] Se pueden utilizar matrices de otros tipos y estructuras 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 de cruce simples. También se pueden utilizar 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 en la programación evolutiva ; En la programación de la expresión genética se explora una combinación de cromosomas lineales y árboles .
Una vez definidas la representación genética y la función de aptitud, un AG procede a inicializar una población de soluciones y luego 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 cientos o miles de posibles soluciones. A menudo, la población inicial se genera aleatoriamente, permitiendo todo el rango de soluciones posibles (el espacio de búsqueda ). Ocasionalmente, las soluciones pueden "sembrarse" en áreas donde es probable que se encuentren soluciones óptimas o la distribución de la probabilidad de muestreo se puede ajustar para centrarse en aquellas áreas de mayor interés. [5]
Selección
Durante cada generación sucesiva, una porción de la población existente es seleccionada para reproducirse en una nueva generación. Las soluciones individuales se seleccionan mediante un proceso basado en la aptitud , donde normalmente es más probable que se seleccionen soluciones más ajustadas (medidas por una función de aptitud ). Ciertos métodos de selección califican la idoneidad de cada solución y seleccionan preferentemente las mejores soluciones. Otros métodos califican sólo 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 idoneidad 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.
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 produzca, se selecciona un par de soluciones "parentales" para su reproducción a partir del conjunto seleccionado previamente. Al producir una solución "secundaria" utilizando los métodos de cruce y mutación anteriores, 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 [6] [7] sugieren que más de dos "padres" generan cromosomas de mayor calidad.
Estos procesos, en última instancia, dan como resultado una población de cromosomas de la próxima generación que es diferente de la generación inicial. Generalmente, la aptitud promedio habrá aumentado mediante este procedimiento para la población, ya que sólo se seleccionan para la reproducción los mejores organismos de la primera generación, junto con una pequeña proporción de soluciones menos aptas. Estas soluciones menos adecuadas garantizan la diversidad genética dentro del acervo genético de los padres y, por tanto, garantizan la diversidad genética de la siguiente generación de hijos.
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 son conocidos como los principales operadores genéticos, es posible utilizar otros operadores como reagrupación, colonización-extinción o migración en algoritmos genéticos. [ cita necesaria ]
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 está trabajando. Una tasa de mutación muy pequeña puede conducir a una deriva genética (que no es de naturaleza 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 provocar la pérdida de buenas soluciones, a menos que se emplee una selección elitista. Un tamaño de población adecuado garantiza una diversidad genética suficiente para el problema en cuestión, pero puede provocar un desperdicio de recursos computacionales si se establece en un valor mayor al requerido.
Heurística
Además de los operadores principales anteriores, se pueden emplear otras heurísticas para hacer el cálculo 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 una convergencia prematura hacia una solución menos óptima. [8] [9]
Terminación
Este proceso generacional se repite hasta alcanzar 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 alcanzado.
Se alcanzó el presupuesto asignado (tiempo de cálculo/dinero)
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 sencillos 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) consta de:
Una descripción de una heurística que realiza la adaptación identificando y recombinando "bloques de construcción", es decir, esquemas de orden bajo y longitud de definición baja con una aptitud superior a la media.
Una hipótesis de que un algoritmo genético realiza una adaptación implementando implícita y eficientemente esta heurística.
Goldberg describe la heurística de la siguiente manera:
"Se muestrean, recombinan [cruzan] y remuestrean esquemas cortos, de orden bajo y de alto ajuste para formar cadenas de aptitud potencialmente mayor. 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 de definición 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, también lo hace un algoritmo genético que 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". [10]
A pesar de la falta de consenso con respecto a la validez de la hipótesis básica, ésta ha sido evaluada y utilizada consistentemente 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 se mantenga la hipótesis. [11] [12] Aunque se han reportado buenos resultados para algunas clases de problemas, aún persiste el escepticismo respecto de la generalidad y/o viabilidad de la hipótesis básica 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. [13] [14] [15]
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 es a menudo 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 funciones 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 de optimización típicos no pueden abordar 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 GA de manera convincente para resolver problemas complejos de la vida real. [ cita necesaria ]
Los algoritmos genéticos no se adaptan bien a la complejidad. Es decir, cuando el número de elementos que están expuestos a la mutación es grande, suele haber un aumento exponencial en el tamaño del espacio de búsqueda. Esto hace que sea extremadamente difícil utilizar la técnica en problemas como el diseño de un motor, una casa o un avión [ cita requerida ] . 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 de aspas de ventiladores en lugar de motores, formas de edificios en lugar de planos de construcción detallados y perfiles aerodinámicos en lugar de diseños completos de aviones. El segundo problema de complejidad es la cuestión de cómo proteger las partes que han evolucionado para representar buenas soluciones de futuras mutaciones destructivas, particularmente cuando su evaluación de idoneidad requiere que se combinen bien con otras partes. [ cita necesaria ]
La "mejor" solución sólo existe en comparación con otras soluciones. Como resultado, el criterio de parada no está claro en todos los problemas. [ cita necesaria ]
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 aptitud a corto plazo para ganar aptitud a largo plazo. La probabilidad de que esto ocurra depende de la forma del panorama de aptitud : ciertos problemas pueden proporcionar un fácil ascenso hacia un óptimo global, otros pueden facilitar que la función encuentre los óptimos locales. Este problema puede aliviarse usando una función de aptitud diferente, aumentando la tasa de mutación o usando técnicas de selección que mantengan una población diversa de soluciones, [16] aunque el teorema No Free Lunch [17] demuestra que no existe una solución general. a 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 agrega una penalización que reducirá la representación de ese grupo en generaciones posteriores, permitiendo que otros (menos similares) ) individuos que se mantendrán en la población. Sin embargo, este truco puede no ser eficaz, dependiendo del panorama del problema. Otra posible técnica 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. En las estrategias de evolución y la programación evolutiva , la diversidad no es esencial debido a una mayor dependencia de la mutación. [ cita necesaria ]
Operar con conjuntos de datos dinámicos es difícil, ya que los genomas comienzan a converger desde el principio hacia soluciones que pueden ya no ser válidas para datos posteriores. Se han propuesto varios métodos para remediar esto aumentando de alguna manera la diversidad genética y evitando la convergencia temprana, ya sea aumentando la probabilidad de mutación cuando la calidad de la solución disminuye (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 sólo entre los descendientes. Esto puede ser más efectivo en problemas dinámicos. [ cita necesaria ]
Los AG no pueden resolver eficazmente problemas en los que la única medida de idoneidad es un resultado binario de aprobación/rechazo (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ápidamente como una AG. 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. [ cita necesaria ]
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 en coma flotante es natural para las estrategias de evolución 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 porque en realidad no representa la teoría de los componentes básicos propuesta por John Henry Holland en los años setenta. Sin embargo, esta teoría tiene apoyo, ya que se basa en resultados teóricos y experimentales (ver más abajo). El algoritmo básico realiza cruce y mutación 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 . 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. Los 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 números enteros, a menudo se emplea la codificación Gray . De esta manera, pequeños cambios en el número entero pueden verse afectados fácilmente mediante mutaciones o cruces. 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 de cruce) para cambiar el cromosoma a una mejor solución.
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 inicialmente sorprendió a los investigadores que se obtuvieran buenos resultados utilizando cromosomas de valor real. Esto se explicó como el conjunto de valores reales en una población finita de cromosomas que forman 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. [18] [19]
Se puede obtener una expansión del dominio del problema accesible del algoritmo genético mediante una codificación más compleja de los conjuntos de soluciones concatenando varios tipos de genes codificados de forma heterogénea en un cromosoma. [20] 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 sintonización 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 (tal 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 evolutivos.
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 pasen a la siguiente, inalterados. 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. [21]
Implementaciones paralelas
Las implementaciones paralelas de algoritmos genéticos son de dos tipos. Los algoritmos genéticos paralelos de grano grueso suponen una población en cada uno de los nodos de la computadora y una migración de individuos entre los nodos. Los algoritmos genéticos paralelos de grano fino suponen que un individuo en cada nodo del procesador actúa con los individuos vecinos para la selección y la 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 adaptativos
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. Los investigadores han analizado analíticamente la convergencia de GA. [22] [23]
En lugar de utilizar valores fijos de pc y pm , los AGA utilizan la información de la población en cada generación y ajustan de forma adaptativa pc y pm para mantener la diversidad de la población y sostener la capacidad de convergencia. En AGA (algoritmo genético adaptativo), [24] 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. [25] En CAGA (algoritmo genético adaptativo basado en agrupamiento), [26] 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. Los enfoques recientes utilizan variables más abstractas para decidir pc y pm . Algunos ejemplos son los principios de dominancia y codominancia [27] y LIGA (algoritmo genético interpolativo nivelado), que combina un GA flexible con una búsqueda A* modificada para abordar la anisotropicidad del espacio de búsqueda. [28]
Puede resultar bastante eficaz combinar GA con otros métodos de optimización. Un AG tiende a ser bastante bueno para encontrar soluciones globales generalmente buenas, pero bastante ineficiente para encontrar las últimas mutaciones para encontrar el óptimo absoluto. Otras técnicas (como la simple escalada de colinas ) son bastante eficaces para encontrar el óptimo absoluto en una región limitada. Alternar GA y escalada puede mejorar la eficiencia de GA [ cita necesaria ] al tiempo que se supera la falta de solidez de la escalada.
Esto significa que las reglas de la 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 un número de pasos del ADN materno, sumando un número de pasos del ADN paterno, etc. Esto es como agregar vectores que probablemente sigan una cresta en el paisaje fenotípico. Por tanto, la eficiencia del proceso puede incrementarse en muchos órdenes de magnitud. Además, el operador de inversión tiene la oportunidad de colocar pasos en orden consecutivo o cualquier otro orden adecuado a favor de la supervivencia o la eficiencia. [29]
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 la interacción de subconjuntos de sus variables. 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 para reducir de forma adaptativa la recombinación disruptiva. Ejemplos destacados de este enfoque incluyen mGA, [30] GEMGA [31] y LLGA. [32]
Dominios problemáticos
Los problemas que parecen ser particularmente apropiados para ser resueltos mediante algoritmos genéticos incluyen problemas de horarios y programación , y muchos paquetes de software de programación se basan en AG [ cita requerida ] . Los AG también se han aplicado a la ingeniería . [33] 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 podrían ser útiles en dominios problemáticos que tienen un panorama complejo de aptitud, 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 de cruce de uso común no pueden cambiar ninguna población uniforme. La mutación por sí sola puede proporcionar ergodicidad al proceso general del algoritmo genético (visto 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, [34] antenas diseñadas para captar señales de radio en el espacio, [35] métodos de caminata para figuras de computadora, [36] diseño óptimo de cuerpos aerodinámicos en campos de flujo complejos [37]
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 añade 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 ningún resultado computacional informado utilizando algoritmos genéticos que me haya impresionado favorablemente. Cíñete al recocido simulado para tus necesidades de vudú de búsqueda heurística.
—Steven Skiena [38] : 267
Historia
En 1950, Alan Turing propuso una "máquina de aprendizaje" que sería paralela a los principios de la evolución. [39] 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 . [40] [41] Su publicación de 1954 no fue ampliamente notada. A partir de 1957, [42] 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 mensurable. A partir de estos inicios, la simulación por computadora de la evolución realizada por biólogos se volvió 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) [43] y Crosby (1973). [44] Las simulaciones de Fraser incluyeron 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 los algoritmos genéticos modernos. [45] Otros pioneros notables incluyen a Richard Friedberg, George Friedman y Michael Conrad. Fogel (1998) reimprime muchos de los primeros artículos . [46]
Aunque Barricelli, en un trabajo que informó en 1963, había simulado la evolución de la capacidad para jugar un juego simple, [47] la evolución artificial sólo se convirtió en un método de optimización ampliamente reconocido como resultado del trabajo de Ingo Rechenberg y Hans-Paul Schwefel en el Década de 1960 y principios de la de 1970: el grupo de Rechenberg pudo resolver problemas de ingeniería complejos mediante estrategias de evolución . [48] [49] [50] [51] 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 utilizó originalmente máquinas de estados finitos para predecir entornos y utilizó 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 libro Adaptation in Natural and Artificial Systems (1975). Su trabajo se originó con estudios sobre 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 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 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. [52] [ referencia circular ]
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ó [53] sobre Evolver en 1990, y siguió siendo el único algoritmo genético comercial interactivo hasta 1995. [54] Evolver se vendió a Palisade en 1997, se tradujo a varios idiomas y actualmente se encuentra en su 6ta versión. [55] 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 simple, búsqueda de patrones). [56]
Las estrategias de evolución (ES, ver Rechenberg, 1994) evolucionan a los individuos mediante mutación y recombinación intermedia o discreta. Los algoritmos ES están diseñados particularmente para resolver problemas en el dominio del valor real. [57] Utilizan la autoadaptación para ajustar los parámetros de control de la búsqueda. La desaleatorización de la autoadaptación ha llevado a la contemporánea Estrategia de Evolución de Adaptación de la Matriz de Covarianza ( CMA-ES ).
La programación evolutiva (PE) involucra poblaciones de soluciones principalmente con 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 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 nuevas soluciones [58] [59] o generarse a partir de un cruce guiado. [60]
El algoritmo genético de agrupación (GGA) es una evolución del AG donde el enfoque se desplaza de elementos individuales, como en los AG clásicos, a grupos o subconjuntos de elementos. [62] La idea detrás de esta evolución de GA propuesta por Emanuel Falkenauer es que la solución de algunos problemas complejos, también conocidos como problemas de agrupamiento o partición en los que un conjunto de elementos debe dividirse en un grupo disjunto de elementos de manera óptima, se lograría mejor haciendo que las características de los grupos de elementos equivalentes a genes. Este tipo de problemas incluyen el embalaje de contenedores , el equilibrio de líneas, la agrupación con respecto a una medida de distancia, pilas iguales, etc., en los que los AG clásicos demostraron tener un mal desempeño. Hacer que los genes sean equivalentes a grupos implica cromosomas que en general son de longitud variable y operadores genéticos especiales que manipulan grupos enteros de elementos. Para el embalaje 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. Por lo general, se aplican a dominios en los que es 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 adaptarse a las preferencias estéticas de los usuarios.
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 , [63] la optimización de enjambre de partículas (PSO) es un método computacional para la optimización multiparamétrica 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 mejor 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 AG, especialmente en problemas sin restricciones con variables continuas. [64]
Otros algoritmos informáticos evolutivos
La computación evolutiva 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 poblaciones en el que las soluciones también están sujetas a fases de mejora local. La idea de los algoritmos meméticos proviene de los memes , que a diferencia de los genes, pueden adaptarse por sí mismos. En algunas áreas problemáticas se ha demostrado que son más eficientes que los algoritmos evolutivos tradicionales.
Algoritmos bacteriológicos (BA) inspirados en la ecología evolutiva y, más particularmente, 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 se adapte a todo el entorno. Por tanto, es necesario 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 extracción de datos. [65]
El algoritmo cultural (CA) consta de un componente poblacional casi idéntico al del algoritmo genético y, además, de un componente de conocimiento llamado espacio de creencias.
La adaptación gaussiana (adaptación normal o natural, abreviada NA para evitar confusión con GA) tiene como objetivo maximizar el rendimiento de fabricación de los sistemas de procesamiento de señales. También se puede utilizar para optimización paramétrica ordinaria. Se basa en un determinado 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 un determinado teorema de eficiencia. Su eficiencia se define como la información dividida por el trabajo necesario para obtenerla. [67] 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 los picos locales en el panorama del fitness. NA también es bueno para escalar crestas pronunciadas mediante la adaptación de la matriz de momento, porque NA puede maximizar el desorden ( información promedio ) del gaussiano manteniendo simultáneamente la aptitud media constante.
Otros métodos metaheurísticos
Los métodos metaheurísticos se incluyen 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 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 en la aptitud y un parámetro de temperatura decreciente. En el lenguaje de Sudáfrica, se habla de buscar la menor energía en lugar de la máxima aptitud física. SA también se puede utilizar 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 menor energía de las generadas. Para evitar el ciclo 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 la solución.
Optimización extrema (EO) A diferencia de los GA, que trabajan con una población de soluciones candidatas, EO desarrolla una única solución y realiza modificaciones locales en los peores componentes. Para ello es necesario elegir una representación adecuada que permita asignar a cada componente 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 una Asamblea General que selecciona buenas soluciones en un intento de crear mejores soluciones.
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 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ólico en heurísticas de búsqueda para resolver problemas de optimización complejos. La palabra reactivo sugiere una respuesta preparada 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 por consulta , las redes neuronales y las metaheurísticas .
^ Gerges, Firas; Zouein, Germain; Azar, Danielle (12 de marzo de 2018). "Algoritmos genéticos con manejo óptimo local para resolver sudokus". Actas de la Conferencia Internacional sobre 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.
^ Burkhart, Michael C.; Ruiz, Gabriel (2023). "Representaciones neuroevolutivas para aprender efectos de tratamientos heterogéneos". Revista de ciencia computacional . 71 : 102054. doi : 10.1016/j.jocs.2023.102054 . S2CID 258752823.
^ ab Whitley 1994, pág. 66.
^ 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 (sección 3)". Revista de investigación en inteligencia artificial . 75 : 953–983. doi : 10.1613/jair.1.14015 .
^ Eiben, AE y otros (1994). "Algoritmos genéticos con recombinación multiparental". PPSN III: Actas de la Conferencia Internacional sobre Computación Evolutiva. La Tercera Conferencia sobre Resolución de Problemas Paralelos a partir de la Naturaleza: 78–87. ISBN 3-540-58484-6 .
^ Ting, Chuan-Kang (2005). "Sobre el tiempo medio de convergencia de algoritmos genéticos multiparentales sin selección". Avances en la vida artificial: 403–412. ISBN 978-3-540-28848-0 .
^ Deb, Kalyanmoy; Lanzas, William M. (1997). "C6.2: Métodos de especiación". Manual de Computación Evolutiva . Instituto de Publicaciones de Física. S2CID 3547258.
^ Shir, Ofer M. (2012). "Nichos en algoritmos evolutivos". En Rozenberg, Grzegorz; Atrás, Thomas; Kok, Joost N. (eds.). Manual de Computación Natural . Springer Berlín Heidelberg. págs. 1035-1069. doi :10.1007/978-3-540-92910-9_32. ISBN9783540929093.
^ Goldberg 1989, pag. 41.
^ Harik, Georges R.; Lobo, Fernando G.; Sastry, Kumara (1 de enero de 2006). "Aprendizaje vinculante 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. ISBN978-3-540-34953-2.
^ 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–532. ISBN9781558606111. {{cite book}}: |journal=ignorado ( ayuda )
^ Ataúd, David; Smith, Robert E. (1 de enero de 2008). "Aprendizaje de vinculación en la estimación de algoritmos de distribución". Vinculación en la Computación Evolutiva . Estudios en Inteligencia Computacional. vol. 157, págs. 141-156. doi :10.1007/978-3-540-85068-7_7. ISBN978-3-540-85067-0.
^ Echegoyen, Carlos; Mendiburu, Alejandro; Santana, Roberto; Lozano, José A. (8 de noviembre de 2012). "Sobre la taxonomía de problemas de optimización bajo estimación de algoritmos de distribución". Computación Evolutiva . 21 (3): 471–495. doi :10.1162/EVCO_a_00095. ISSN 1063-6560. PMID 23136917. S2CID 26585053.
^ Sadowski, Krzysztof L.; Bosman, Peter AN; Thierens, Dirk (1 de enero de 2013). "Sobre la utilidad del procesamiento de enlaces para la resolución de MAX-SAT". Actas de la 15ª conferencia anual sobre computación genética y evolutiva . Geco '13. págs. 853–860. doi :10.1145/2463372.2463474. hdl :1874/290291. ISBN9781450319638. S2CID 9986768.
^ 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 modificadas". Revista Centroeuropea de Ingeniería . 3 (1): 36–50. doi : 10.2478/s13531-012-0047-8 .
^ Wolpert, DH, Macready, WG, 1995. Teoremas de optimización sin almuerzo gratis. Instituto Santa Fe, SFI-TR-05-010, Santa Fe.
^ Goldberg, David E. (1991). "La teoría de los alfabetos virtuales". Resolución de problemas paralelos desde la naturaleza . Apuntes de conferencias sobre informática. vol. 496, págs. 13-22. doi :10.1007/BFb0029726. ISBN978-3-540-54148-6. {{cite book}}: |journal=ignorado ( ayuda )
^ Janików, CZ; Michalewicz, Z. (1991). "Una comparación experimental de representaciones binarias y de coma flotante en algoritmos genéticos" (PDF) . Actas de la Cuarta Conferencia Internacional sobre Algoritmos Genéticos : 31–36. Archivado (PDF) desde el original el 9 de octubre de 2022 . Consultado el 2 de julio de 2013 .
^ Patrascu, M.; Stancu, AF; Pop, F. (2014). "HELGA: un algoritmo genético realista de codificación heterogénea para modelado y simulación de la evolución de la población". Computación blanda . 18 (12): 2565–2576. doi :10.1007/s00500-014-1401-y. S2CID 29821873.
^ Baluja, Shumeet; Caruana, rico (1995). Eliminación de la genética del algoritmo genético estándar (PDF) . ICML . Archivado (PDF) desde el original el 9 de octubre de 2022.
^ Stannat, W. (2004). "Sobre la convergencia de algoritmos genéticos: un enfoque variacional". Probablemente. Relación teórica. Campos . 129 : 113-132. doi : 10.1007/s00440-003-0330-y . S2CID 121086772.
^ Sharapov, RR; Lapshin, AV (2006). "Convergencia de algoritmos genéticos". Reconocimiento de patrones. Imagen Anal . 16 (3): 392–397. doi :10.1134/S1054661806030084. S2CID 22890010.
^ Srinivas, M.; Patnaik, L. (1994). "Probabilidades adaptativas de cruce y mutación en algoritmos genéticos" (PDF) . Transacciones IEEE sobre sistemas, hombre y cibernética . 24 (4): 656–667. doi : 10.1109/21.286385. Archivado (PDF) desde el original el 9 de octubre de 2022.
^ Kwon, YD; Kwon, SB; Jin, SB; Kim, JY (2003). "Algoritmo genético mejorado de convergencia con método de zoom sucesivo para resolver problemas de optimización continua". Computadoras y estructuras . 81 (17): 1715-1725. doi :10.1016/S0045-7949(03)00183-4.
^ Zhang, J.; Chung, H.; Lo, WL (2007). "Probabilidades de mutación y cruce adaptativo basado en agrupaciones para algoritmos genéticos". Transacciones IEEE sobre computación evolutiva . 11 (3): 326–335. doi :10.1109/TEVC.2006.880727. S2CID 2625150.
^ Pavai, G.; Geetha, televisión (2019). "Nuevos operadores cruzados que utilizan principios de dominancia y codominancia para una convergencia más rápida de algoritmos genéticos". Computación blanda . 23 (11): 3661–3686. doi :10.1007/s00500-018-3016-1. S2CID 254028984.
^ Li, JCF; Zimmerle, D.; Joven, P. (2022). "Electrificación rural en red flexible mediante algoritmo genético interpolativo nivelado". Energía e IA . 10 : 100186. Código bibliográfico : 2022EneAI..1000186L. doi : 10.1016/j.egyai.2022.100186 . S2CID 250972466.
^ 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.
^ Expresión genética: el eslabón perdido en el cálculo evolutivo
^ Harik, G. (1997). Vinculación del aprendizaje para resolver eficientemente problemas de dificultad acotada utilizando algoritmos genéticos (Doctor). Departamento de Ciencias de la Computación, Universidad de Michigan, Ann Arbour.
^ 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. Energías. 2013; 6(3):1439-1455.
^ 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 .
^ Hornby, GS; Linden, DS; Lohn, JD, Diseño de antena automatizado con algoritmos evolutivos (PDF)
^ "Locomoción muscular flexible para criaturas bípedas".
^ 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". Modelado Matemático Aplicado . 52 : 215–240. doi : 10.1016/j.apm.2017.07.024 . ISSN 0307-904X.
^ Turing, Alan M. (octubre de 1950). "Maquinaria informática e inteligencia". Mente . LIX (238): 433–460. doi : 10.1093/mente/LIX.236.433.
^ Barricelli, Nils Aall (1954). "Ejemplos numéricos de procesos de evolución". Métodos : 45–68.
^ Barricelli, Nils Aall (1957). "Procesos de evolución simbiogenética realizados por métodos artificiales". Métodos : 143–182.
^ Fraser, Alex (1957). "Simulación de sistemas genéticos mediante ordenadores digitales automáticos. I. Introducción". Agosto. J. Biol. Ciencia . 10 (4): 484–491. doi : 10.1071/BI9570484 .
^ Fraser, Alex ; Burnell, Donald (1970). Modelos informáticos en genética . Nueva York: McGraw-Hill. ISBN978-0-07-021904-5.
^ Crosby, Jack L. (1973). Simulación informática en genética . Londres: John Wiley & Sons. ISBN978-0-471-18880-3.
^ 27.02.96 - Hans Bremermann de UC Berkeley, profesor emérito y pionero en biología matemática, falleció a los 69 años.
^ Fogel, David B., ed. (1998). Computación evolutiva: el registro fósil . Nueva York: IEEE Press. ISBN978-0-7803-3481-6.
^ Barricelli, Nils Aall (1963). "Pruebas numéricas de las teorías de la evolución. Parte II. Pruebas preliminares de desempeño, simbiogénesis y vida terrestre". Acta Bioteórica . 16 (3–4): 99–126. doi :10.1007/BF01556602. S2CID 86717105.
^ 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. ISBN978-3-7643-0876-6.
^ 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. ISBN978-0-471-09988-8.
^ Aldawoodi, Namir (2008). Un enfoque para diseñar el piloto automático de un helicóptero no tripulado utilizando algoritmos genéticos y recocido simulado. pag. 99.ISBN978-0549773498- a través de libros de Google.
^ 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 .
↑ 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.
^ Evolver: optimización sofisticada para hojas de cálculo. Empalizada. Recuperado el 7 de agosto de 2013.
^ 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 Bib : 2019IEEEA...779657L. doi : 10.1109/ACCESS.2019.2923092 . S2CID 195774435.
^ Cohoon, J; et al. (2002). Algoritmos evolutivos para el diseño físico de circuitos VLSI (PDF) . Springer, págs. 683-712, 2003. ISBN978-3-540-43330-9. Archivado (PDF) desde el original el 9 de octubre de 2022. {{cite book}}: |journal=ignorado ( ayuda )
^ 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–532. ISBN9781558606111. {{cite book}}: |journal=ignorado ( ayuda )
^ Pelikan, Martín (2005). Algoritmo de optimización bayesiano jerárquico: hacia una nueva generación de algoritmos evolutivos (1ª ed.). Berlín [ua]: Springer. ISBN978-3-540-23774-7.
^ Thierens, Dirk (11 de septiembre de 2010). "El algoritmo genético del árbol de vinculación". Resolución de problemas paralelos desde la naturaleza, PPSN XI . págs. 264-273. doi :10.1007/978-3-642-15844-5_27. ISBN978-3-642-15843-8.
^ 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 . Código Bib : 2001cs.......2027F. Archivado (PDF) desde el original el 9 de octubre de 2022.
^ Falkenauer, Emanuel (1997). Algoritmos genéticos y problemas de agrupación . Chichester, Inglaterra: John Wiley & Sons Ltd. ISBN978-0-471-97150-4.
^ Zlochin, Marcos; Birattari, Mauro; Meuleau, Nicolás; Dorigo, Marco (1 de octubre de 2004). "Búsqueda basada en modelos para optimización combinatoria: una encuesta crítica". Anales de investigación de operaciones . 131 (1–4): 373–395. CiteSeerX 10.1.1.3.427 . doi :10.1023/B:ANOR.0000039526.52305.af. ISSN 0254-5330. S2CID 63137.
^ Rania Hassan, Babak Cohanim, Olivier de Weck, Gerhard Vente r (2005) Una comparación de la optimización del enjambre de partículas y el algoritmo genético
^ 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. 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 .
^ Cívicioglu, P. (2012). "Transformación de coordenadas cartesianas geocéntricas en coordenadas geodésicas mediante el uso de un algoritmo de búsqueda diferencial". Computadoras y Geociencias . 46 : 229–247. Código Bib : 2012CG.....46..229C. doi :10.1016/j.cageo.2011.12.011.
^ Kjellström, G. (diciembre de 1991). "Sobre la eficiencia de la adaptación gaussiana". Revista de teoría y aplicaciones de optimización . 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, Mateo F.; Pollock, Bruce G.; Manuck, Steven; Smith, Gwenn; Venta, Mark E. (2006). "Un enfoque de aprendizaje automático híbrido basado en algoritmos genéticos para la selección de modelos". Revista de farmacocinética y farmacodinamia . 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". Revista de investigación de reconocimiento de patrones . 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 . Saltador. ISBN 978-3540401841.
Fraser, Alex S. (1957). "Simulación de sistemas genéticos mediante ordenadores digitales automáticos. I. Introducción". Revista Australiana de Ciencias Biológicas . 10 (4): 484–491. doi : 10.1071/BI9570484 .
Goldberg, David (1989). Algoritmos genéticos en búsqueda, optimización y aprendizaje automático . Reading, MA: Addison-Wesley Profesional. ISBN 978-0201157673.
Goldberg, David (2002). El diseño de la innovación: lecciones de y para algoritmos genéticos competentes . Norwell, MA: Editores académicos de Kluwer. ISBN 978-1402070983.
Fogel, David (2006). Computación evolutiva: hacia una nueva filosofía de la inteligencia artificial (3ª ed.). Piscataway, Nueva Jersey: IEEE Press. ISBN 978-0471669517.
Hingston, Felipe; Barón, Luigi; Michalewicz, Zbigniew (2008). Diseño por evolución: avances en el diseño evolutivo . Saltador. ISBN 978-3540741091.
Holanda, John (1992). Adaptación en Sistemas Naturales y Artificiales . Cambridge, MA: MIT Press. ISBN 978-0262581110.
Koza, Juan (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 de Evolución . 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). Una guía de campo para la programación genética . Lulu.com, disponible gratuitamente en Internet. ISBN 978-1-4092-0073-4.[ fuente autoeditada? ]
Schmitt, Lothar M.; Nehaniv, Chrystopher L.; Fujii, Robert H. (1998). "Análisis lineal de algoritmos genéticos". Informática Teórica . 208 : 111-148.
Schmitt, Lothar M. (2001). "Teoría de los algoritmos genéticos". Informática Teórica . 259 (1–2): 1–61. 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 de poblaciones con tensor de cuerdas y convergencia a óptimos globales para funciones de aptitud arbitrarias bajo escala". Informática Teórica . 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). "Un tutorial de algoritmo genético" (PDF) . Estadística y Computación . 4 (2): 65–85. CiteSeerX 10.1.1.184.3999 . doi :10.1007/BF00175354. S2CID 3447126. Archivado (PDF) desde el original el 9 de octubre de 2022.
Enlaces externos
Recursos
[1] Proporciona una lista de recursos en el campo de los algoritmos genéticos.
Una descripción general de la historia y las variantes de los algoritmos evolutivos
Tutoriales
Algoritmos genéticos: los programas de computadora que "evolucionan" de manera que se asemejan a la selección natural pueden resolver problemas complejos que incluso sus creadores no entienden completamente. Una excelente introducción a GA por John Holland y 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 .
Un tutorial de algoritmo genético por Darrell Whitley Departamento de Ciencias de la Computación Universidad Estatal de Colorado Un excelente tutorial con mucha teoría
"Fundamentos de la metaheurística", 2009 (225 p). Texto abierto gratuito de Sean Luke.
Algoritmos de optimización global: teoría y aplicación Archivado el 11 de septiembre de 2008 en Wayback Machine.
Tutorial de algoritmos genéticos en Python con la intuición detrás de la implementación de GA y Python.
Los algoritmos genéticos evolucionan para resolver el dilema del prisionero. Escrito por Robert Axelrod.