genetic-algorithm - que - objetivo de los algoritmos geneticos
¿Alguna vez ha usado un algoritmo genético en aplicaciones del mundo real? (6)
Me preguntaba qué tan común es encontrar enfoques de algoritmos genéticos en el código comercial.
Siempre me pareció que algunos tipos de planificadores podrían beneficiarse de un motor de GA, como un complemento del algoritmo principal.
Si quieres encontrar un ejemplo, mira el Query Planner de Postgres. Utiliza muchas técnicas, y una resulta ser genética.
http://developer.postgresql.org/pgdocs/postgres/geqo-pg-intro.html
Utilicé GA en mi tesis de maestría, pero después de eso no encontré nada en mi trabajo diario que una GA pudiera resolver que no pudiera resolver más rápido con algún otro algoritmo.
Los algoritmos genéticos han sido ampliamente utilizados comercialmente. La optimización del enrutamiento de trenes fue una aplicación temprana. Más recientemente, los aviones de combate han utilizado GA para optimizar los diseños de las alas. He utilizado exhaustivamente GA en el trabajo para generar soluciones a problemas que tienen un espacio de búsqueda extremadamente grande.
Es poco probable que muchos problemas se beneficien de las GA. No estoy de acuerdo con Thomas en que sean demasiado difíciles de entender. Un GA es realmente muy simple. Descubrimos que hay una gran cantidad de conocimiento que se puede obtener al optimizar la GA para un problema en particular que podría ser difícil y, como siempre, la administración de grandes cantidades de cómputo paralelo sigue siendo un problema para muchos programadores.
Un problema que se beneficiaría de una GA tendrá las siguientes características:
- Una buena forma de codificar soluciones potenciales
- Una forma de calcular una puntuación numérica para evaluar la calidad de la solución
- Un gran espacio de búsqueda multidimensional donde la respuesta no es obvia
- Una buena solución es lo suficientemente buena y no se requiere una solución perfecta
Hay muchos problemas que probablemente podrían beneficiarse de las GA y en el futuro probablemente se desplieguen más ampliamente. Creo que las GA se utilizan en la ingeniería de vanguardia más de lo que la gente piensa, sin embargo, la mayoría de las personas (como mi empresa) protegen esos secretos muy de cerca. Es solo mucho después del hecho de que se revela que se usaron GA.
Sin embargo, la mayoría de las personas que se ocupan de aplicaciones "normales" probablemente no les sirvan de mucho.
No creo que sea particularmente común encontrar algoritmos genéticos en el código comercial cotidiano. Se encuentran más comúnmente en el código académico / de investigación donde la necesidad de encontrar el "mejor algoritmo" es menos importante que la necesidad de simplemente encontrar una buena solución a un problema.
No obstante, he consultado sobre un par de proyectos comerciales que usan GA (principalmente como resultado de mi participación en GAUL ). Creo que el ejemplo más interesante fue en una empresa de Biotech. Utilizaron GA para optimizar las funciones de puntuación que se utilizaron para la detección virtual, como parte de su aplicación de descubrimiento de fármacos.
A principios de este año, con mi compañía actual , agregué una nueva función a uno de nuestros productos que usa otra GA. Creo que podríamos comercializar esto a partir del próximo mes. Básicamente, la GA se usa para explorar moléculas que tienen el potencial de unirse a una proteína y, por lo tanto, podría investigarse más como fármacos dirigidos a esa proteína. Un producto competidor que también usa un GA es el inventor de EA .
Como parte de mi tesis, escribí un marco java genérico para el algoritmo de optimización multiobjetivo mPOEMS (Optimización prototipo multiobjetivo con pasos de mejora evolutiva), que es un GA que utiliza conceptos evolutivos. Es genérico de manera que todas las partes independientes del problema se han separado de las partes dependientes del problema, y se proporciona una interfaz para usar el marco con solo agregar las partes dependientes del problema. Por lo tanto, quien quiera usar el algoritmo no tiene que comenzar desde cero, y facilita mucho el trabajo.
Puedes encontrar el código aquí .
Las soluciones que puede encontrar con este algoritmo se han comparado en un trabajo científico con los algoritmos de última generación SPEA-2 y NSGA, y se ha demostrado que el algoritmo tiene un rendimiento comparable o incluso mejor, dependiendo de las métricas que tomar para medir el rendimiento, y especialmente dependiendo del problema de optimización que está buscando.
Puedes encontrarlo aquí .
También, como parte de mi tesis y prueba de trabajo, apliqué este marco al problema de selección de proyectos que se encuentra en la administración de carteras. Se trata de seleccionar los proyectos que añaden más valor a la empresa, respaldar la estrategia de la empresa o apoyar cualquier otro objetivo arbitrario. Por ejemplo, la selección de un cierto número de proyectos de una categoría específica o la maximización de las sinergias del proyecto, ...
Mi tesis que aplica este marco al problema de selección de proyectos: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf
Después de eso, trabajé en un departamento de administración de carteras en una de las Fortune 500, donde utilizaron un software comercial que también aplicó una GA al problema de selección de proyectos / optimización de la cartera.
Recursos adicionales:
La documentación del marco: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf
Documento de presentación de mPOEMS: http://portal.acm.org/citation.cfm?id=1792634.1792653
De hecho, con un poco de entusiasmo todo el mundo podría adaptar fácilmente el código del marco genérico a un problema arbitrario de optimización multiobjetivo.
No lo hice, pero he oído hablar de esta empresa (no recuerdo su nombre) que utiliza algos genéticos mutantes para calcular ubicaciones y longitudes de antenas (o algo así) de un amigo mío. Y se supone que deben (de acuerdo con mi amigo) tener un gran éxito con esto. Supongo que GA es demasiado complejo para que el "desarrollador promedio Joe" se convierta en la corriente principal. Algo así como Map Reduce: espectacularmente genial, pero WAY demasiado avanzado para llegar al "mainstream" ...