¿Cuáles son algunas aplicaciones del mundo real para algoritmos genéticos?

13

¿Cuáles son algunos problemas del mundo real que se han resuelto utilizando un algoritmo genético? ¿Cuál es el problema? ¿Cuál es la prueba de aptitud utilizada para resolver este problema?

La torre
fuente
1
Esto debería ser wiki comunitario (suponiendo que esté en el tema).
Shane el
44
No estoy seguro de que los algoritmos genéticos estén dentro del alcance. Deberíamos discutirlo aquí: meta.cstheory.stackexchange.com/questions/73/…
Suresh Venkat
77
Esto está fuera de tema.
Marcos Villagra
55
Una pregunta interesante podría haber sido: ¿hay escenarios que admitan garantías comprobables para GAs?
Suresh Venkat
2
Pero esto no se trata de una aplicación de la teoría. Se trata de una aplicación de práctica.
Jeffε

Respuestas:

11

El optimizador en bases de datos relacionales. Ejemplos son PostgreSQL y H2 ; otras bases de datos probablemente también usan un algoritmo genético. El problema es: seleccionar el mejor plan de consulta (el que tiene el costo estimado más bajo) es NP-hard. La prueba de aptitud es el costo estimado.

Thomas Mueller
fuente
8

El algoritmo genético lamarckiano se utiliza en quimioinformática para detectar posibles nuevos compuestos farmacológicos que puedan unirse a un receptor particular.

El problema computacional es buscar en una base de datos químicos candidatos que puedan orientarse correctamente (wrt las posibles orientaciones de la molécula que contiene el receptor), y combinar eso con una búsqueda conformacional (es decir, una que considere las posibles torsiones rotativas de la molécula , que puede afectar fuertemente la reacción ).

Anteriormente, era factible realizar una búsqueda de orientación o una búsqueda de conformación, pero no ambas. LGA aprovecha la aceleración de la computadora y combina la búsqueda global de un algoritmo genético con una búsqueda local.

Aaron Sterling
fuente
6

La NASA creó un algoritmo genético para el diseño de la antena .

La prueba de aptitud es la siguiente:

La función de aptitud utilizada para evaluar las antenas es una función de la relación de onda estacionaria de voltaje (VSWR) y los valores de ganancia en las frecuencias de transmisión y recepción. VSWR es una forma de cuantificar la interferencia de onda reflejada y, por lo tanto, la cantidad de desajuste de impedancia en la unión. VSWR es la relación entre el voltaje más alto y el voltaje más bajo en la envolvente de señal a lo largo de una línea de transmisión.

La torre
fuente
6

He usado GA para resolver problemas de programación en fabricación y educación. La función de aptitud física en el primer caso fue la cantidad de artículos solicitados que se fabricaron en el período de tiempo determinado, mientras que en el segundo caso la aptitud física se basó en penalizar los horarios con conflictos.

Si está interesado en las aplicaciones, aquí hay un enlace a más de 20,000 artículos sobre citeseerx

Steven A. Lowe
fuente
4

El diseño de la antena ya se ha mencionado, y es un dominio extremadamente rico. (Es, muy directamente, lo que comenzó mi movimiento de la ingeniería eléctrica a la informática (a fines de los 90) y más específicamente a la computación bioinspirada y la inteligencia artificial (en los últimos cinco años más o menos).

En la misma línea, agregaré la optimización de la matriz de antenas , especialmente para la optimización de la matriz en fases, que es todo el dolor de cabeza del diseño de la antena, y más. Hay oportunidades en todo el campo del diseño de dispositivos electromagnéticos, realmente: antenas, conjuntos de antenas, filtros de microondas, rejillas ópticas, diseño de dispositivos metamateriales, todo fuera de mi cabeza. Una encuesta con fecha es Optimización electromagnética por algoritmos genéticos , y una encuesta más reciente es Algoritmos genéticos en electromagnetismo . (Realmente debería comprar ese segundo.

También he visto muchos documentos buenos sobre diseño de circuitos no electromagnéticos: GAs que vienen con amplificadores operacionales u otros diseños de circuitos integrados competitivos, GAs "aprendiendo" a aprovechar las imperfecciones analógicas en FPGAs para implementar funciones analógicas como relojes, etc. Incluso algo tan simple como un diseño de filtro de elementos discretos puede ser un objetivo para los GA: he visto uno que tiene en cuenta los factores q, las tolerancias, los valores discretos y la soldadura de modelos parásitos para obtener buenos filtros fabricables del partes que tienes a mano.

Estos a menudo implican algunas representaciones de circuitos novedosas (para mí, de todos modos) para que los operadores genéticos se ajusten al paradigma, así como cromosomas de tamaño variable.

Novak
fuente
Sí, se ha demostrado que el ejemplo de diseño de circuitos redescubre o incluso supera los diseños patentados. Heres un artículo temprano a lo largo de esta línea, mucho más tarde la investigación. Diseño de un amplificador operacional de alta ganancia y otros circuitos mediante programación genética por Koza et al 1997
vzn
3

Recientemente hubo una pregunta sobre el uso de GA para desarrollar diseños de palas de turbinas eólicas utilizando simulaciones de dinámica de fluidos de la potencia física generada como la función de aptitud. [1]

Este video muestra el uso de un algoritmo genético para desarrollar palas de turbina eólica VAWT. Una de las cuchillas resultantes es bastante diferente y parece simular bien. El software de reproducción se escribió en Perl, el software de visualización Java y el software CFD fue OpenFoam. Se hicieron más de 672 horas de CPU en la realización de este video. Nota: desde entonces descubrí que utilicé la viscosidad incorrecta para el aire en este experimento, por lo que los resultados no son válidos para su uso en la tierra. (Quizás Júpiter)

[1] "Palas de turbina eólica en evolución" en youtube por "sjh7132". Citado por / de la pregunta TCS.se: ¿En qué medida es posible utilizar algoritmos genéticos para hacer que las palas de las turbinas de los molinos de viento sean más eficientes?

vzn
fuente
3

Hay algunas investigaciones sobre el uso de AG para la clasificación de vinos. clasifica con precisión la variedad de vino y el lugar de producción ("denominación de origen"). [1] Este es un subconjunto de uso de GA en sistemas agrícolas del cual existen muchas aplicaciones. [2]

[1] Algoritmos de selección de características que utilizan cromatogramas de vinos chilenos como ejemplos de NHBeltran et al.

[2] Estado del arte en algoritmos genéticos para sistemas agrícolas por Bolboaca et al.

vzn
fuente
1

Hay muchos documentos sobre el uso de GA para el control de vuelo en el campo aeroespacial. muchos de estos son publicados o buscables por el explorador IEEE . la función de aptitud generalmente mide qué tan bien / efectivamente el algoritmo controla el vuelo.

[1] Diseño y optimización del sistema de control de vuelo con un algoritmo genético de Fantinutto et al.

[2] Aplicación de algoritmos genéticos para el control de vuelo hipersónico. Austin, Jacobs.

[3] Implementación multinúcleo del sistema de control de superficie de vuelo F-16 utilizando algoritmo de control adaptativo basado en algoritmo genético, Xiaoru Wang

[4] Control de lógica difusa basado en algoritmo genético para control de vuelo integrado para vehículos hipersónicos. por Wang Jian

vzn
fuente
1

Koza fue pionera en el uso notable, incluso extraordinario o cambiante de paradigma de las AG, muy citado en encuestas posteriores, para resolver un "problema" de los videojuegos, es decir, Pac Man como prueba de principio, pero el concepto probablemente se puede aplicar a casi cualquier videojuego, y los resultados están definitivamente lejos de ser triviales o "de juguete".

es decir, desarrolló algoritmos que implementan un comportamiento real para ganar jugando el juego durante largos períodos de tiempo. Los resultados están en el nivel de rendimiento de los jugadores humanos aficionados o incluso avanzados . una función de aptitud puede ser puntos obtenidos por el algoritmo o tiempo de juego (el último evolucionará probablemente algoritmos que sobrevivan sin obtener puntos, como un caso clásico de naves espaciales de "caza" en el juego Asteroides). el comportamiento se implementa con "primitivas" (p. ej., monstruos sensoriales / acto girando, etc.) y árboles que representan las combinaciones de estrategias primitivas.

[1] Diversos agentes en desarrollo de la Sra. Pac-Man usando programación genética por Atif M. Alhejali y Simon M. Lucas

[2] Aprendiendo a jugar Pac-Man: un enfoque evolutivo basado en reglas por Gallagher y Ryan

[3] Aprendiendo a jugar usando políticas basadas en reglas de baja complejidad: ilustraciones a través de la Sra. Pac-Man por István Szita András L ~ orincz

vzn
fuente
Para ser muy quisquilloso, haría una distinción entre programación genética y algoritmos genéticos. Ciertamente, están estrechamente relacionados, sin embargo.
Novak
@novak estuvo de acuerdo y gracias por sacar la distinción que estaba borrosa aquí. más o menos, GP es el uso de GA para descubrir algoritmos, ¿verdad? sí, el comportamiento encontrado / construido es básicamente equivalente a un algoritmo ... y, por supuesto, la técnica probablemente sea ampliamente aplicable fuera de los videojuegos, aunque no conozca muchos ejemplos hasta ahora ... su uso muy avanzado ... (aunque me acuerdo de otro ejemplo de koza que todavía usa árboles de una manera inteligente! necesita publicar eso).
vzn
1

La conferencia anual de GECCO (más o menos el lugar principal para la investigación de la computación evolutiva) tiene una pista de "Aplicaciones del mundo real".

Vea también esta presentación reciente:

NietzscheanAI
fuente