¿Cuáles son los casos de uso típicos de la Programación Genética?
Hoy he leído esta entrada de blog de Roger Alsingsobre cómo pintar una réplica de la Mona Lisa usando solo 50 polígonos semi transparentes.
Estoy fascinado con los resultados para ese caso en particular, así que me preguntaba (y esta es mi pregunta): ¿cómo funciona la programación genética y qué otros problemas podrían resolverse mediante la programación genética?
8 answers
Existe cierto debate sobre si el programa Mona Lisa de Roger es Programación Genética en absoluto. Parece estar más cerca de un (1 + 1) Estrategia de evolución . Ambas técnicas son ejemplos del campo más amplio de la Computación Evolutiva, que también incluye Algoritmos Genéticos.
La programación genética (GP) es el proceso de evolución de programas informáticos (generalmente en forma de árboles - a menudo programas Lisp). Si usted está preguntando específicamente acerca de GP, John Koza es ampliamente considerado como el principal experto. Su sitio web incluye muchos enlaces a más información. GP es típicamente muy intensivo computacionalmente (para problemas no triviales a menudo implica una gran red de máquinas).
Si se pregunta de manera más general, los algoritmos evolutivos (EAs) se usan típicamente para proporcionar buenas soluciones aproximadas a problemas que no se pueden resolver fácilmente usando otras técnicas (como los problemas NP-hard). Muchos problemas de optimización caen en esto categoría. Puede ser demasiado intensivo computacionalmente para encontrar una solución exacta, pero a veces una solución casi óptima es suficiente. En estas situaciones las técnicas evolutivas pueden ser efectivas. Debido a su naturaleza aleatoria, algoritmos evolutivos nunca están garantizados para encontrar una solución óptima para cualquier problema, pero a menudo encontrar una buena solución si existe.
Los algoritmos evolutivos también se pueden usar para abordar problemas que los humanos realmente no saben cómo resolver. Un EA, libre de cualquier preconcepción o sesgo humano puede generar soluciones sorprendentes que son comparables o mejores que los mejores esfuerzos generados por el ser humano. Simplemente es necesario que podamos reconocer una buena solución si se nos presenta, incluso si no sabemos cómo crear una buena solución. En otras palabras, necesitamos ser capaces de formular una función de aptitud efectiva .
Algunos Ejemplos
EDIT: El libro de libre acceso, A Field Guide to Genetic Programming, contiene ejemplos de donde GP ha producido resultados humanos competitivos.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2008-12-20 22:50:34
Curiosamente, la compañía detrás de la animación dinámica de personajes utilizada en juegos como Grand Theft Auto IV y el último juego de Star Wars (The Force Unleashed) usó programación genética para desarrollar algoritmos de movimiento. El sitio web de la compañía está aquí y los videos son muy impresionantes:
Http://www.naturalmotion.com/euphoria.htm
Creo que simularon el sistema nervioso del personaje, luego aleatorizaron las conexiones hasta cierto punto. Luego se combinaron los ' genes 'de los modelos que caminaron más lejos para crear más y más' niños ' capaces en generaciones sucesivas. Realmente fascinante trabajo de simulación.También he visto algoritmos genéticos utilizados en autómatas de búsqueda de caminos, con hormigas que buscan alimento como el ejemplo clásico.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2008-12-10 12:55:01
Los algoritmos genéticos se pueden utilizar para resolver casi cualquier problema de optimización. Sin embargo, en muchos casos, hay métodos mejores y más directos para resolverlos. Está en la clase de algoritmos de metaprogramación, lo que significa que es capaz de adaptarse a casi cualquier cosa que pueda lanzarle, dado que puede generar un método de codificación de una solución potencial, combinando/mutando soluciones y decidiendo qué soluciones son mejores que otras. GA tiene una ventaja sobre otros meta-programación algoritmos en que puede manejar máximos locales mejor que un algoritmo puro de escalada, como recocido simulado.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2008-12-10 09:33:09
Usé programación genética en mi tesis para simular la evolución de especies basada en el terreno, pero eso es, por supuesto, la aplicación A-life de algoritmos genéticos.
Los problemas en los que GA es bueno son problemas de escalada. El problema es que normalmente es más fácil resolver la mayoría de estos problemas a mano, a menos que los factores que definen el problema sean desconocidos, en otras palabras, no se puede lograr ese conocimiento de otra manera, decir cosas relacionadas con sociedades y comunidades, o en situaciones en las que tienes un buen algoritmo pero necesitas afinar los parámetros, aquí GA son muy útiles.
Una situación de ajuste fino que he hecho fue afinar varios jugadores de Othello AI basados en los mismos algoritmos, dando a cada estilo de juego diferente, haciendo que cada oponente sea único y con sus propias peculiaridades, luego los hice competir para eliminar las 16 mejores IA que usé en mi juego. La ventaja era que todos eran muy buenos jugadores de más o menos igual habilidad, por lo que fue interesante para el oponente humano porque no podían adivinar la IA tan fácilmente.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-03-11 17:43:08
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2008-12-10 09:10:41
Usted debe preguntarse: "¿Puedo (a priori) definir una función para determinar qué tan buena es una solución en particular en relación con otras soluciones?"
En el ejemplo de la mona lisa, puede determinar fácilmente si la nueva pintura se parece más a la imagen de origen que a la pintura anterior, por lo que la Programación Genética se puede aplicar "fácilmente".
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2008-12-10 09:30:21
Tengo algunos proyectos usando Algoritmos Genéticos. GA son ideales para problemas de optimización, cuando no se puede desarrollar un algoritmo totalmente secuencial y exacto para resolver un problema. Por ejemplo: ¿cuál es la mejor combinación de características de un coche para hacerlo más rápido y al mismo tiempo más económico?
En este momento estoy desarrollando un GA simple para elaborar listas de reproducción. Mi GA tiene que encontrar las mejores combinaciones de álbumes / canciones que son similares (esta similitud será "calculada" con la ayuda de last.fm) y sugiere listas de reproducción para mí.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2008-12-10 12:59:35
Hay un campo emergente en robótica llamado Robótica Evolutiva (w: Evolutionary Robotics), que utiliza algoritmos genéticos (GA) en gran medida.
Ver w: Algoritmo genético :
Algoritmo genético generacional simple pseudocódigo
- Elija la población inicial
- Evaluar la aptitud de cada individuo en la población
- Repetir hasta la terminación: (límite de tiempo o aptitud suficiente alcanzada)
- Seleccione los mejores individuos para reproducirse
- Raza nueva generación a través del cruce y / o mutación (genética operaciones) y dar a luz a descendencia
- Evaluar las características individuales de la descendencia
- Reemplazar la parte peor clasificada de la población con descendencia
La clave es la parte de reproducción, que podría ocurrir sexual o asexualmente, utilizando operadores genéticos Crossover y Mutación.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2008-12-14 22:52:13