¿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?
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?
Respuestas:
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.
fuente
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.
fuente
La NASA creó un algoritmo genético para el diseño de la antena .
La prueba de aptitud es la siguiente:
fuente
A menudo se usan en finanzas, especialmente para problemas de optimización de cartera. Hay muchos documentos sobre este tema, pero vea, por ejemplo, Algoritmos genéticos en la optimización de la cartera .
fuente
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
fuente
No puedo resistirme, pero señalo el trabajo de Roger Alsing:
http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/
Representa la imagen de Mona Lisa usando solo 50 triángulos semitransparentes.
fuente
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.
fuente
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]
[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?
fuente
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.
fuente
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
fuente
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
fuente
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:
fuente