stringtranslate.com

Algoritmo gené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 informática e investigación de operaciones , un algoritmo genético ( GA ) es una metaheurística inspirada en el proceso de selección natural que pertenece a la clase más amplia de algoritmos evolutivos (EA). Los algoritmos genéticos se utilizan comúnmente para generar soluciones de alta calidad a problemas de optimización y búsqueda basándose en operadores de inspiración biológica como mutación , cruce y selección . [1] Algunos ejemplos de aplicaciones GA incluyen la optimización de árboles de decisión para un mejor rendimiento, la resolución de sudokus , [2] optimización de hiperparámetros , inferencia causal , [3] , etc.

Metodología

Problemas de optimización

En un algoritmo genético, una población de soluciones candidatas (llamadas individuos, criaturas, organismos o fenotipos ) a un problema de optimización evoluciona hacia mejores soluciones. Cada solución candidata tiene un conjunto de propiedades (sus cromosomas o genotipo ) que 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.

Un algoritmo genético típico requiere:

  1. una representación genética del dominio de 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 ). [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 se exploran 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 varios 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.

En algunos problemas, es 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 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 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:

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:

  1. 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.
  2. 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:

Variantes

Representación cromosómica

El algoritmo más simple representa cada cromosoma como una cadena de bits . Normalmente, los parámetros numéricos se pueden representar mediante números enteros , aunque es posible utilizar representaciones de punto flotante . La representación 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 la década de 1970. 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 de evolución.

Elitismo

Una variante práctica del proceso general de construcción de una nueva población es permitir que los mejores organismos de la generación actual 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 de aptitud complejo , ya que la mezcla, es decir, la mutación en combinación con el cruce , está diseñada para alejar a la población de los óptimos locales en los que un algoritmo tradicional de escalada podría atascarse. pulg. Observe que los operadores 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 , que estaba usando la computadora en el Instituto de Estudios Avanzados de Princeton, Nueva Jersey . [40] [41] Su publicación de 1954 no fue muy 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 versión original. 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]

Técnicas relacionadas

Campos principales

Los algoritmos genéticos son un subcampo:

Campos relacionados

Algoritmos evolutivos

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

Inteligencia de enjambre

La inteligencia de enjambre es un subcampo de la informática evolutiva .

Otros algoritmos informáticos evolutivos

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

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 .

Otros métodos de optimización estocástica

Ver también

Referencias

  1. ^ Mitchell 1996, pág. 2.
  2. ^ 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.
  3. ^ 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.
  4. ^ ab Whitley 1994, pág. 66.
  5. ^ 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 .
  6. ^ 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 . 
  7. ^ 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 . 
  8. ^ 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.
  9. ^ Shir, Ofer M. (2012). "Nichos en algoritmos evolutivos". En Rozenberg, Grzegorz; Detrá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. ISBN 9783540929093.
  10. ^ Goldberg 1989, pag. 41.
  11. ^ 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. ISBN 978-3-540-34953-2.
  12. ^ 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. ISBN 9781558606111. {{cite book}}: |journal=ignorado ( ayuda )
  13. ^ 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. ISBN 978-3-540-85067-0.
  14. ^ 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.
  15. ^ 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. ISBN 9781450319638. S2CID  9986768.
  16. ^ 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 .
  17. ^ Wolpert, DH, Macready, WG, 1995. Teoremas de optimización sin almuerzo gratis. Instituto Santa Fe, SFI-TR-05-010, Santa Fe.
  18. ^ 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. ISBN 978-3-540-54148-6. {{cite book}}: |journal=ignorado ( ayuda )
  19. ^ 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 .
  20. ^ 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.
  21. ^ 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.
  22. ^ 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.
  23. ^ 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.
  24. ^ 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.
  25. ^ 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.
  26. ^ 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.
  27. ^ 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.
  28. ^ 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. doi : 10.1016/j.egyai.2022.100186 . S2CID  250972466.
  29. ^ Véase, por ejemplo, Evolución en pocas palabras Archivado el 15 de abril de 2016 en Wayback Machine o un ejemplo del problema del viajante , en particular el uso de un operador de recombinación de bordes .
  30. ^ 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.
  31. ^ Expresión genética: el eslabón perdido en el cálculo evolutivo
  32. ^ 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.
  33. ^ 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.
  34. ^ 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 .
  35. ^ Hornby, GS; Linden, DS; Lohn, JD, Diseño de antena automatizado con algoritmos evolutivos (PDF)
  36. ^ "Locomoción muscular flexible para criaturas bípedas".
  37. ^ 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.
  38. ^ Skiena, Steven (2010). El manual de diseño de algoritmos (2ª ed.). Springer Ciencia + Medios comerciales . ISBN 978-1-849-96720-4.
  39. ^ Turing, Alan M. (octubre de 1950). "Maquinaria informática e inteligencia". Mente . LIX (238): 433–460. doi : 10.1093/mente/LIX.236.433.
  40. ^ Barricelli, Nils Aall (1954). "Ejemplos numéricos de procesos de evolución". Métodos : 45–68.
  41. ^ Barricelli, Nils Aall (1957). "Procesos de evolución simbiogenética realizados por métodos artificiales". Métodos : 143–182.
  42. ^ 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 .
  43. ^ Fraser, Alex ; Burnell, Donald (1970). Modelos informáticos en genética . Nueva York: McGraw-Hill. ISBN 978-0-07-021904-5.
  44. ^ Crosby, Jack L. (1973). Simulación informática en genética . Londres: John Wiley & Sons. ISBN 978-0-471-18880-3.
  45. ^ 27.02.96 - Hans Bremermann de UC Berkeley, profesor emérito y pionero en biología matemática, falleció a los 69 años.
  46. ^ Fogel, David B., ed. (1998). Computación evolutiva: el registro fósil . Nueva York: IEEE Press. ISBN 978-0-7803-3481-6.
  47. ^ 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.
  48. ^ Rechenberg, Ingo (1973). Estrategia de evoluciones . Stuttgart: Holzmann-Froboog. ISBN 978-3-7728-0373-4.
  49. ^ Schwefel, Hans-Paul (1974). Numerische Optimierung von Computer-Modellen (tesis doctoral) .
  50. ^ 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.
  51. ^ 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.
  52. ^ 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.ISBN​ 978-0549773498- a través de libros de Google.
  53. ^ 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 .
  54. ↑ 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.
  55. ^ Evolver: optimización sofisticada para hojas de cálculo. Empalizada. Recuperado el 7 de agosto de 2013.
  56. ^ 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.
  57. ^ Cohoon, J; et al. (2002). Algoritmos evolutivos para el diseño físico de circuitos VLSI (PDF) . Springer, págs. 683-712, 2003. ISBN 978-3-540-43330-9. Archivado (PDF) desde el original el 9 de octubre de 2022. {{cite book}}: |journal=ignorado ( ayuda )
  58. ^ 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. ISBN 9781558606111. {{cite book}}: |journal=ignorado ( ayuda )
  59. ^ 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. ISBN 978-3-540-23774-7.
  60. ^ 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. ISBN 978-3-642-15843-8.
  61. ^ 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.
  62. ^ Falkenauer, Emanuel (1997). Algoritmos genéticos y problemas de agrupación . Chichester, Inglaterra: John Wiley & Sons Ltd. ISBN 978-0-471-97150-4.
  63. ^ 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. 
  64. ^ 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
  65. ^ 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 .
  66. ^ 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.
  67. ^ 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

enlaces externos

Recursos

Tutoriales