stringtranslate.com

Algoritmo genético

Antena de la nave espacial ST5 de la NASA de 2006. Esta forma complicada fue descubierta por 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 (AG) es una metaheurística inspirada en el proceso de selección natural que pertenece a la clase más amplia de algoritmos evolutivos (AE). [1] Los algoritmos genéticos se utilizan comúnmente para generar soluciones de alta calidad a problemas de optimización y búsqueda a través de operadores inspirados biológicamente como selección , cruce y mutación . [2] Algunos ejemplos de aplicaciones de GA incluyen la optimización de árboles de decisión para un mejor rendimiento, la resolución de sudokus , [3] la optimización de hiperparámetros y la inferencia causal . [4]

Metodología

Problemas de optimización

En un algoritmo genético, una población de soluciones candidatas (denominadas individuos, criaturas, organismos o fenotipos ) para un problema de optimización evoluciona hacia mejores soluciones. Cada solución candidata 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. [5]

La evolución suele comenzar a partir de una población de individuos generados aleatoriamente y es un proceso iterativo , en el que la población de cada iteración se denomina generación . En cada generación, se evalúa la aptitud de cada individuo de la población; la aptitud suele ser el valor de la función objetivo en el problema de optimización que se está resolviendo. Los individuos más aptos se seleccionan de forma estocástica 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 entonces en la siguiente iteración del algoritmo . Normalmente, el algoritmo finaliza cuando se ha producido un número máximo de generaciones o se ha alcanzado un nivel de aptitud satisfactorio para la población.

Un algoritmo genético típico requiere:

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

Una representación estándar de cada solución candidata es como una matriz de bits (también llamada conjunto de bits o cadena de bits ). [5] Se pueden utilizar matrices de otros tipos y estructuras esencialmente de la misma manera. La propiedad principal 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 las operaciones de cruce simples . También se pueden utilizar representaciones de longitud variable, pero la implementación del cruce 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 ; una mezcla de cromosomas lineales y árboles se explora en la programación de expresión genética .

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 a mejorarla mediante la aplicación repetitiva de los operadores de mutación, cruce, inversión y selección.

Inicialización

El tamaño de la población depende de la naturaleza del problema, pero normalmente contiene cientos o miles de posibles soluciones. A menudo, la población inicial se genera aleatoriamente, lo que permite utilizar todo el rango de posibles soluciones (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 puede ajustarse para centrarse en aquellas áreas de mayor interés. [6]

Selección

Durante cada generación sucesiva, se selecciona una parte de la población existente para reproducirse en una nueva generación. Las soluciones individuales se seleccionan mediante un proceso basado en la aptitud , donde las soluciones más aptas (medidas mediante una función de aptitud ) suelen tener más probabilidades de ser seleccionadas. Ciertos métodos de selección evalúan la aptitud de cada solución y seleccionan preferentemente las mejores soluciones. Otros métodos evalúan solo una muestra aleatoria de la población, ya que el primer proceso puede requerir 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 aptitud siempre depende del problema. Por ejemplo, en el problema de la mochila, se desea maximizar el valor total de los objetos que se pueden colocar 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 las representaciones de este tipo son válidas, ya que el tamaño de los objetos puede superar la capacidad de la mochila. La aptitud de la solución es la suma de los valores de todos los objetos en la mochila si la representación es válida, o 0 en caso contrario.

En algunos problemas, es difícil o incluso imposible definir la expresión de aptitud; en estos casos, se puede 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 segunda generación de soluciones 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 "progenitoras" para reproducirlas del conjunto seleccionado previamente. Al producir una solución "hija" utilizando los métodos de cruce y mutación antes mencionados, se crea una nueva solución que, por lo general, comparte muchas de las características de sus "progenitores". Se seleccionan nuevos progenitores para cada nueva solución hija y el proceso continúa hasta que se genera una nueva población de soluciones del tamaño adecuado. Aunque los métodos de reproducción que se basan en el uso de dos progenitores están más "inspirados en la biología", algunas investigaciones [7] [8] sugieren que más de dos "progenitores" generan cromosomas de mayor calidad.

Estos procesos dan como resultado, en última instancia, una población de cromosomas de la siguiente generación que es diferente de la generación inicial. En general, la aptitud promedio de la población habrá aumentado con este procedimiento, ya que solo se seleccionan para la reproducción los mejores organismos de la primera generación, junto con una pequeña proporción de soluciones menos aptas. Estas soluciones menos aptas garantizan la diversidad genética dentro del acervo genético de los progenitores y, por lo tanto, garantizan la diversidad genética de la siguiente generación de hijos.

Las opiniones están divididas sobre la importancia del cruce frente a la mutación. Hay muchas referencias en Fogel (2006) que respaldan la importancia de la búsqueda basada en mutaciones.

Aunque el cruce y la mutación se conocen como los principales operadores genéticos, es posible utilizar otros operadores como reagrupación, colonización-extinción o migración en algoritmos genéticos. [ cita requerida ]

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 valores 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 conducir a 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 conducir a un desperdicio de recursos computacionales si se establece en un valor mayor que el requerido.

Heurística

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

Terminación

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

La hipótesis del bloque de construcción

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

  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, longitud de definición baja y aptitud superior al promedio.
  2. Una hipótesis de que un algoritmo genético realiza la adaptación implementando implícita y eficientemente esta heurística.

Goldberg describe la heurística de la siguiente manera:

"Se toman muestras de esquemas cortos, de orden bajo y de gran ajuste, se los recombina [se los cruza] y se los vuelve a muestrear para formar cadenas de aptitud potencialmente superior. En cierto modo, al trabajar con estos esquemas particulares [los bloques de construcción], hemos reducido la complejidad de nuestro problema; en lugar de construir cadenas de alto rendimiento probando todas las combinaciones imaginables, construimos cadenas cada vez mejores a partir de las mejores soluciones parciales de muestreos anteriores.
"Dado que los esquemas de gran ajuste, de longitud de definición reducida y orden bajo desempeñan un papel tan importante en la acción de los algoritmos genéticos, ya les hemos dado un nombre especial: bloques de construcción. Así como un niño crea magníficas fortalezas mediante la disposición de simples bloques de madera, un algoritmo genético busca un rendimiento casi óptimo mediante la yuxtaposición de esquemas cortos, de orden bajo y alto rendimiento, o bloques de construcción". [11]

A pesar de la falta de consenso sobre la validez de la hipótesis de los bloques de construcción, se ha evaluado y utilizado de manera consistente como referencia a lo largo de los años. Por ejemplo, se han propuesto muchos algoritmos de estimación de distribución en un intento de proporcionar un entorno en el que se mantuviera la hipótesis. [12] [13] Aunque se han informado buenos resultados para algunas clases de problemas, aún persiste el escepticismo sobre la generalidad y/o viabilidad de la hipótesis de los bloques de construcción 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. [14] [15] [16]

Limitaciones

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

Variantes

Representación cromosómica

El algoritmo más simple representa cada cromosoma como una cadena de bits . Normalmente, los parámetros numéricos se pueden representar con números enteros , aunque es posible utilizar representaciones de punto flotante . La representación de punto flotante es natural en 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 bloques de construcción que propuso John Henry Holland en la década de 1970. Sin embargo, esta teoría no carece de apoyo, según los resultados teóricos y experimentales (ver a continuación). El algoritmo básico realiza cruces y mutaciones a nivel de bits. Otras variantes tratan el cromosoma como una lista de números que son índices en una tabla de instrucciones, nodos en una lista enlazada , hashes , objetos o cualquier otra estructura de datos imaginable . Los cruces y las mutaciones se realizan de modo que se respeten los límites de los elementos de datos. Para la mayoría de los tipos de datos, se pueden diseñar operadores de variación específicos. Diferentes tipos de datos cromosómicos parecen funcionar mejor o peor para diferentes dominios de problemas específicos.

Cuando se utilizan representaciones de números enteros en cadenas de bits, se suele emplear la codificación Gray . De esta manera, se pueden producir fácilmente pequeños cambios en el número entero mediante mutaciones o cruces. Se ha descubierto que esto ayuda a prevenir la convergencia prematura en los llamados muros de Hamming , en los que deben producirse 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 de valor real en lugar de cadenas de bits para representar cromosomas. Los resultados de la teoría de esquemas sugieren que, en general, cuanto más pequeño es el alfabeto, mejor es el rendimiento, pero inicialmente fue sorprendente para los investigadores que se obtuvieran buenos resultados al usar cromosomas de valor real. Esto se explicó como el conjunto de valores reales en una población finita de cromosomas que forma un alfabeto virtual (cuando la selección y la recombinación son dominantes) con una cardinalidad mucho menor que la que se esperaría de una representación de punto flotante. [19] [20]

Se puede obtener una expansión del dominio de problemas accesibles del Algoritmo Genético a través de una codificación más compleja de los grupos de soluciones mediante la concatenación de varios tipos de genes codificados de manera heterogénea en un cromosoma. [21] Este enfoque particular permite resolver problemas de optimización que requieren dominios de definición muy dispares para los parámetros del problema. Por ejemplo, en problemas de ajuste de controladores en cascada, la estructura del controlador de bucle interno puede pertenecer a un regulador convencional de tres parámetros, mientras que el bucle externo podría implementar un controlador lingüístico (como un sistema difuso) que tiene una descripción inherentemente diferente. Esta forma particular de codificación requiere un mecanismo de cruce especializado que recombina el cromosoma por 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 sin sufrir modificaciones. Esta estrategia se conoce como selección elitista y garantiza que la calidad de la solución obtenida por el AG no disminuya de una generación a la siguiente. [22]

Implementaciones paralelas

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

AGs adaptativos

Los algoritmos genéticos con parámetros adaptativos (algoritmos genéticos adaptativos, AGA) son otra variante significativa y prometedora de los algoritmos genéticos. Las probabilidades de cruce (pc) y mutación (pm) determinan en gran medida el grado de precisión de la solución y la velocidad de convergencia que pueden obtener los algoritmos genéticos. Los investigadores han analizado la convergencia de GA analíticamente. [23] [24]

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), [25] 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. [26] En CAGA (algoritmo genético adaptativo basado en agrupamiento), [27] a través del uso del 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 [28] y LIGA (algoritmo genético interpolativo nivelado), que combina un AG flexible con una búsqueda A* modificada para abordar la anisotropicidad del espacio de búsqueda. [29]

Puede resultar bastante eficaz combinar AG 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 escalada de colinas simple ) son bastante eficientes para encontrar el óptimo absoluto en una región limitada. Alternar AG y escalada de colinas puede mejorar la eficiencia de GA [ cita requerida ] al tiempo que supera la falta de robustez de la escalada de colinas.

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

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

Se han desarrollado varias variaciones para intentar mejorar el rendimiento de los AG en problemas con un alto grado de epistasis de aptitud, es decir, donde la aptitud de una solución consiste en subconjuntos interactuantes de sus variables. Dichos algoritmos apuntan a aprender (antes de explotar) estas interacciones fenotípicas beneficiosas. Como tales, están alineados con la Hipótesis del Bloque de Construcción en la reducción adaptativa de la recombinación disruptiva. Ejemplos destacados de este enfoque incluyen el mGA, [31] GEMGA [32] y LLGA. [33]

Dominios problemáticos

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

Como regla general, los algoritmos genéticos pueden ser útiles en dominios 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 de escalada tradicional podría quedarse atascado. 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 ).

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

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

Resulta bastante antinatural modelar aplicaciones en términos de operadores genéticos como 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 tiempo en resolver problemas no triviales. [...] La analogía con la evolución —donde un progreso significativo requiere millones de años— puede ser bastante apropiada.

[...]

Nunca me he encontrado con ningún problema en el que los algoritmos genéticos me parecieran la forma correcta de abordarlo. Además, nunca he visto ningún resultado computacional informado utilizando algoritmos genéticos que me haya impresionado favorablemente. Limítese al recocido simulado para sus necesidades de búsqueda heurística.

—  Steven Skiena [39] : 267 

Historia

En 1950, Alan Turing propuso una "máquina de aprendizaje" que sería paralela a los principios de la evolución. [40] La simulación por computadora de la evolución comenzó ya en 1954 con el trabajo de Nils Aall Barricelli , que estaba utilizando la computadora en el Instituto de Estudios Avanzados de Princeton, Nueva Jersey . [41] [42] Su publicación de 1954 no fue ampliamente notada. A partir de 1957, [43] el genetista cuantitativo australiano Alex Fraser publicó una serie de artículos sobre simulación de selección artificial de organismos con múltiples loci que controlan un rasgo medible. A partir de estos comienzos, la simulación por computadora de la evolución por parte de 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) [44] y Crosby (1973). [45] 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ó los elementos de los algoritmos genéticos modernos. [46] Otros pioneros notables incluyen a Richard Friedberg, George Friedman y Michael Conrad. Muchos de los primeros artículos fueron reimpresos por Fogel (1998). [47]

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

Productos comerciales

A finales de los años 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. [53] [ 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ó [54] sobre Evolver en 1990, y siguió siendo el único algoritmo genético comercial interactivo hasta 1995. [55] Evolver se vendió a Palisade en 1997, se tradujo a varios idiomas y actualmente se encuentra en su sexta versión. [56] Desde los años 1990, MATLAB ha incorporado tres algoritmos heurísticos de optimización sin derivadas (recocido simulado, optimización de enjambre de partículas, algoritmo genético) y dos algoritmos de búsqueda directa (búsqueda simplex, búsqueda de patrones). [57]

Técnicas relacionadas

Campos padre

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 computación evolutiva .

Otros algoritmos de computación evolutiva

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

Otros métodos metaheurísticos

Los métodos metaheurísticos en general se incluyen dentro de los métodos de optimización estocástica .

Otros métodos de optimización estocástica

Véase también

Referencias

  1. ^ Pétrowski, Alain; Ben-Hamida, Sana (2017). Algoritmos evolutivos. John Wiley & Sons. pág. 30.
  2. ^ Mitchell 1996, pág. 2.
  3. ^ Gerges, Firas; Zouein, Germain; Azar, Danielle (12 de marzo de 2018). "Algoritmos genéticos con manejo de óptimos locales para resolver sudokus". Actas de la Conferencia internacional de 2018 sobre informática e inteligencia artificial . 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.S2CID44152535  .​
  4. ^ Burkhart, Michael C.; Ruiz, Gabriel (2023). "Representaciones neuroevolutivas para el aprendizaje de efectos de tratamientos heterogéneos". Journal of Computational Science . 71 : 102054. doi : 10.1016/j.jocs.2023.102054 . S2CID  258752823.
  5. ^ desde Whitley 1994, pág. 66.
  6. ^ Luque-Rodriguez, Maria; Molina-Baena, Jose; Jimenez-Vilchez, Alfonso; Arauzo-Azofra, Antonio (2022). "Inicialización de la búsqueda de selección de características para clasificación (sec. 3)". Revista de investigación en inteligencia artificial . 75 : 953–983. doi : 10.1613/jair.1.14015 .
  7. ^ Eiben, AE et al (1994). "Algoritmos genéticos con recombinación multiparental". PPSN III: Actas de la Conferencia Internacional sobre Computación Evolutiva. Tercera Conferencia sobre Resolución de Problemas Paralelos de la Naturaleza: 78–87. ISBN 3-540-58484-6 . 
  8. ^ Ting, Chuan-Kang (2005). "Sobre el tiempo de convergencia medio de algoritmos genéticos multiparentales sin selección". Avances en vida artificial: 403–412. ISBN 978-3-540-28848-0 . 
  9. ^ Deb, Kalyanmoy; Spears, William M. (1997). "C6.2: Métodos de especiación". Manual de computación evolutiva . Instituto de publicaciones de física. S2CID  3547258.
  10. ^ Shir, Ofer M. (2012). "Niching in Evolutionary Algorithms". En Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (eds.). Handbook of Natural Computing . Springer Berlin Heidelberg. págs. 1035–1069. doi :10.1007/978-3-540-92910-9_32. ISBN 9783540929093.
  11. ^ Goldberg 1989, pág. 41.
  12. ^ Harik, Georges R.; Lobo, Fernando G.; Sastry, Kumara (1 de enero de 2006). "Aprendizaje de ligamiento mediante modelado probabilístico en el algoritmo genético compacto extendido (ECGA)". Optimización escalable mediante modelado probabilístico . Estudios en inteligencia computacional. Vol. 33. págs. 39–61. doi :10.1007/978-3-540-34954-9_3. ISBN 978-3-540-34953-2.
  13. ^ Pelikan, Martín; Goldberg, David E.; Cantú-Paz, Erick (1 de enero de 1999). BOA: El algoritmo de optimización bayesiano. Gecco'99. págs. 525–532. ISBN 9781558606111. {{cite book}}: |journal=ignorado ( ayuda )
  14. ^ Coffin, David; Smith, Robert E. (1 de enero de 2008). "Aprendizaje de ligamiento en la estimación de algoritmos de distribución". Ligamiento en computación evolutiva . Estudios en inteligencia computacional. Vol. 157. págs. 141–156. doi :10.1007/978-3-540-85068-7_7. ISBN 978-3-540-85067-0.
  15. ^ Echegoyen, Carlos; Mendiburu, Alexander; Santana, Roberto; Lozano, Jose A. (8 de noviembre de 2012). "Sobre la taxonomía de 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.
  16. ^ Sadowski, Krzysztof L.; Bosman, Peter AN; Thierens, Dirk (1 de enero de 2013). "Sobre la utilidad del procesamiento de ligamiento para resolver MAX-SAT". Actas de la 15.ª conferencia anual sobre computación genética y evolutiva . Gecco '13. págs. 853–860. doi :10.1145/2463372.2463474. hdl :1874/290291. ISBN . 9781450319638.S2CID 9986768  .
  17. ^ Taherdangkoo, Mohammad; Paziresh, Mahsa; Yazdi, Mehran; Bagheri, Mohammad Hadi (19 de noviembre de 2012). "Un algoritmo eficiente para la optimización de funciones: algoritmo de células madre modificado". Revista Central Europea de Ingeniería . 3 (1): 36–50. doi : 10.2478/s13531-012-0047-8 .
  18. ^ Wolpert, DH, Macready, WG, 1995. No hay teoremas gratuitos para la optimización. Santa Fe Institute, SFI-TR-05-010, Santa Fe.
  19. ^ Goldberg, David E. (1991). "La teoría de los alfabetos virtuales". Resolución de problemas paralelos a partir de la naturaleza . Apuntes de clase en informática. Vol. 496. págs. 13-22. doi :10.1007/BFb0029726. ISBN. 978-3-540-54148-6. {{cite book}}: |journal=ignorado ( ayuda )
  20. ^ Janikow, CZ; Michalewicz, Z. (1991). "An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms" (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 .
  21. ^ Patrascu, M.; Stancu, AF; Pop, F. (2014). "HELGA: un algoritmo genético de codificación heterogénea similar a la vida real para el modelado y simulación de la evolución de poblaciones". Soft Computing . 18 (12): 2565–2576. doi :10.1007/s00500-014-1401-y. S2CID  29821873.
  22. ^ Baluja, Shumeet; Caruana, Rich (1995). Eliminación de la genética del algoritmo genético estándar (PDF) . ICML . Archivado (PDF) del original el 9 de octubre de 2022.
  23. ^ Stannat, W. (2004). "Sobre la convergencia de algoritmos genéticos: un enfoque variacional". Probab. Theory Relat. Fields . 129 : 113–132. doi : 10.1007/s00440-003-0330-y . S2CID  121086772.
  24. ^ Sharapov, RR; Lapshin, AV (2006). "Convergencia de algoritmos genéticos". Reconocimiento de patrones. Análisis de imágenes . 16 (3): 392–397. doi :10.1134/S1054661806030084. S2CID  22890010.
  25. ^ Srinivas, M.; Patnaik, L. (1994). "Probabilidades adaptativas de cruce y mutación en algoritmos genéticos" (PDF) . IEEE Transactions on Systems, Man, and Cybernetics . 24 (4): 656–667. doi :10.1109/21.286385. Archivado (PDF) desde el original el 9 de octubre de 2022.
  26. ^ Kwon, YD; Kwon, SB; Jin, SB; Kim, JY (2003). "Algoritmo genético mejorado por convergencia con método de zoom sucesivo para resolver problemas de optimización continua". Computers & Structures . 81 (17): 1715–1725. doi :10.1016/S0045-7949(03)00183-4.
  27. ^ Zhang, J.; Chung, H.; Lo, WL (2007). "Probabilidades de mutación y cruce adaptativo basadas en agrupamiento para algoritmos genéticos". IEEE Transactions on Evolutionary Computation . 11 (3): 326–335. doi :10.1109/TEVC.2006.880727. S2CID  2625150.
  28. ^ Pavai, G.; Geetha, TV (2019). "Nuevos operadores de cruce que utilizan principios de dominancia y codominancia para una convergencia más rápida de algoritmos genéticos". Soft Comput . 23 (11): 3661–3686. doi :10.1007/s00500-018-3016-1. S2CID  254028984.
  29. ^ Li, JCF; Zimmerle, D.; Young, P. (2022). "Electrificación rural en red flexible utilizando un algoritmo genético interpolativo nivelado". Energía e IA . 10 : 100186. Bibcode :2022EneAI..1000186L. doi : 10.1016/j.egyai.2022.100186 . S2CID  250972466.
  30. ^ Véase, por ejemplo, Evolution-in-a-nutshell Archivado el 15 de abril de 2016 en Wayback Machine o el ejemplo del problema del viajante , en particular el uso de un operador de recombinación de aristas .
  31. ^ 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.
  32. ^ Expresión genética: el eslabón perdido en la computación evolutiva
  33. ^ Harik, G. (1997). Aprendizaje en cadena para resolver de manera eficiente problemas de dificultad limitada utilizando algoritmos genéticos (PhD). Departamento de Ciencias de la Computación, Universidad de Michigan, Ann Arbour.
  34. ^ 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 utilizando un algoritmo genético basado en NSGA-II. Energías. 2013; 6(3):1439-1455.
  35. ^ 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 .
  36. ^ Hornby, GS; Linden, DS; Lohn, JD, Diseño automatizado de antenas con algoritmos evolutivos (PDF)
  37. ^ "Locomoción muscular flexible para criaturas bípedas".
  38. ^ Evans, B.; Walton, SP (diciembre de 2017). "Optimización aerodinámica de un vehículo de reentrada hipersónica 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.
  39. ^ Skiena, Steven (2010). Manual de diseño de algoritmos (2.ª edición). Springer Science+Business Media . ISBN 978-1-849-96720-4.
  40. ^ Turing, Alan M. (octubre de 1950). «Maquinaria informática e inteligencia». Mind . LIX (238): 433–460. doi :10.1093/mind/LIX.236.433.
  41. ^ Barricelli, Nils Aall (1954). "Ejemplos numéricos de procesos de evolución". Métodos : 45–68.
  42. ^ Barricelli, Nils Aall (1957). "Procesos de evolución simbiogenética realizados mediante métodos artificiales". Methodos : 143–182.
  43. ^ Fraser, Alex (1957). "Simulación de sistemas genéticos mediante computadoras digitales automáticas. I. Introducción". Aust. J. Biol. Sci . 10 (4): 484–491. doi : 10.1071/BI9570484 .
  44. ^ Fraser, Alex ; Burnell, Donald (1970). Modelos informáticos en genética . Nueva York: McGraw-Hill. ISBN 978-0-07-021904-5.
  45. ^ Crosby, Jack L. (1973). Simulación por ordenador en genética . Londres: John Wiley & Sons. ISBN 978-0-471-18880-3.
  46. ^ 27.02.96 - Hans Bremermann, profesor emérito y pionero en biología matemática de la Universidad de California en Berkeley, falleció a los 69 años
  47. ^ Fogel, David B., ed. (1998). Computación evolutiva: el registro fósil . Nueva York: IEEE Press. ISBN 978-0-7803-3481-6.
  48. ^ Barricelli, Nils Aall (1963). "Pruebas numéricas de teorías de la evolución. Parte II. Pruebas preliminares de rendimiento, simbiogénesis y vida terrestre". Acta Biotheoretica . 16 (3–4): 99–126. doi :10.1007/BF01556602. S2CID  86717105.
  49. ^ Rechenberg, Ingo (1973). Estrategia de evoluciones . Stuttgart: Holzmann-Froboog. ISBN 978-3-7728-0373-4.
  50. ^ Schwefel, Hans-Paul (1974). Numerische Optimierung von Computer-Modellen (tesis doctoral) .
  51. ^ 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.
  52. ^ 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.
  53. ^ Aldawoodi, Namir (2008). Un enfoque para diseñar un piloto automático de helicóptero no tripulado utilizando algoritmos genéticos y recocido simulado. pág. 99. ISBN 978-0549773498– a través de Google Books.
  54. ^ 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 .
  55. ^ 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. Consultado el 7 de agosto de 2013.
  56. ^ Evolver: Optimización sofisticada para hojas de cálculo. Palisade. Consultado el 7 de agosto de 2013.
  57. ^ Li, Lin; Saldivar, Alfredo Alan Flores; Bai, Yun; Chen, Yi; Liu, Qunfeng; Li, Yun (2019). "Puntos de referencia para evaluar algoritmos de optimización y evaluación comparativa de optimizadores sin derivadas de MATLAB para acceso rápido de profesionales". IEEE Access . 7 : 79657–79670. Bibcode :2019IEEEA...779657L. doi : 10.1109/ACCESS.2019.2923092 . S2CID  195774435.
  58. ^ 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) del original el 9 de octubre de 2022. {{cite book}}: |journal=ignorado ( ayuda )
  59. ^ 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 )
  60. ^ Pelikan, Martin (2005). Algoritmo de optimización bayesiana jerárquica: hacia una nueva generación de algoritmos evolutivos (1.ª ed.). Berlín [ua]: Springer. ISBN 978-3-540-23774-7.
  61. ^ Thierens, Dirk (11 de septiembre de 2010). "El algoritmo genético del árbol de ligamiento". Resolución de problemas paralelos de la naturaleza, PPSN XI . pp. 264–273. doi :10.1007/978-3-642-15844-5_27. ISBN 978-3-642-15843-8.
  62. ^ Ferreira, C (2001). "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems" (PDF) . Sistemas complejos . 13 (2): 87–129. arXiv : cs/0102027 . Código bibliográfico :2001cs........2027F. Archivado (PDF) desde el original el 9 de octubre de 2022.
  63. ^ Falkenauer, Emanuel (1997). Algoritmos genéticos y problemas de agrupamiento . Chichester, Inglaterra: John Wiley & Sons Ltd. ISBN 978-0-471-97150-4.
  64. ^ Zlochin, Mark; Birattari, Mauro; Meuleau, Nicolas; Dorigo, Marco (1 de octubre de 2004). "Búsqueda basada en modelos para optimización combinatoria: un estudio crítico". 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. 
  65. ^ 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
  66. ^ 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) . IEEE Software . 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 .
  67. ^ Civicioglu, P. (2012). "Transformación de coordenadas cartesianas geocéntricas en coordenadas geodésicas mediante el uso de un algoritmo de búsqueda diferencial". Computers & Geosciences . 46 : 229–247. Bibcode :2012CG.....46..229C. doi :10.1016/j.cageo.2011.12.011.
  68. ^ Kjellström, G. (diciembre de 1991). "Sobre la eficiencia de la adaptación gaussiana". Revista de teoría y aplicaciones de la optimización . 71 (3): 589–597. doi :10.1007/BF00941405. S2CID  116847975.

Bibliografía

Enlaces externos

Recursos

Tutoriales