genetic-programming - que - programacion evolutiva
¿Cuáles son los casos de uso típicos de la Programación Genética? (8)
Hoy leí esta entrada en el blog de Roger Alsing sobre cómo pintar una réplica de la Mona Lisa utilizando 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?
Tengo algunos proyectos que usan Algoritmos Genéticos. Los GA son ideales para problemas de optimización, cuando no se puede desarrollar un algoritmo exacto, completamente secuencial, resuelve un problema. Por ejemplo: ¿cuál es la mejor combinación de características de un automóvil para hacerlo más rápido y al mismo tiempo más económico?
En este momento estoy desarrollando una 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í.
Hay un campo emergente en robótica llamado Evolutionary Robotics ( w: Evolutionary Robotics ), que utiliza algoritmos genéticos (GA) en gran medida.
Ver w: Algoritmo genético :
Seudocódigo de algoritmo genético generacional simple
- Elige la población inicial
- Evaluar la aptitud de cada individuo en la población
- Repetir hasta la finalización: (límite de tiempo o aptitud física suficiente)
- Seleccionar individuos de mejor clasificación para reproducirse
- Criar nueva generación a través de cruce y / o mutación (operaciones genéticas) y dar a luz a la descendencia
- Evaluar las aptitudes 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 suceder sexual o asexualmente, utilizando los operadores genéticos Crossover y Mutation .
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) utilizó la 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 combinaron los "genes" de los modelos que caminaron más lejos para crear más y más "niños" en sucesivas generaciones. Un trabajo de simulación realmente fascinante.
También he visto algoritmos genéticos utilizados en la búsqueda de autómatas camino, con hormigas buscando comida es el ejemplo clásico.
Debería preguntarse a sí mismo: "¿Puedo (a priori) definir una función para determinar qué tan buena es una solución particular en relación con otras soluciones?"
En el ejemplo de mona lisa, puede determinar fácilmente si la nueva pintura se parece más a la imagen de origen que la pintura anterior, por lo que la Programación genética se puede aplicar "fácilmente".
Los algoritmos genéticos se pueden usar para resolver la mayoría de los problemas de optimización. Sin embargo, en muchos casos, existen 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 prácticamente todo lo que pueda arrojar, dado que puede generar un método de codificación de una solución potencial, combinar soluciones de mutación y decidir qué las soluciones son mejores que otras GA tiene una ventaja sobre otros algoritmos de meta-programación en que puede manejar máximos locales mejor que un algoritmo de escalada pura, como el recocido simulado.
Existe cierto debate sobre si el programa Mona Lisa de Roger es Programación Genética en absoluto. Parece estar más cerca de una (1 + 1) Estrategia de Evolución . Ambas técnicas son ejemplos del campo más amplio de Computación Evolutiva, que también incluye Algoritmos Genéticos .
La Programación Genética (GP) es el proceso de evolución de los programas informáticos (generalmente en forma de árboles, a menudo programas Lisp). Si está preguntando específicamente sobre GP, John Koza es ampliamente considerado como el principal experto. Su sitio web incluye muchos enlaces a más información. GP suele ser muy intensivo en términos computacionales (para problemas no triviales a menudo implica una gran red de máquinas).
Si se lo pregunta de manera más general, los algoritmos evolutivos (EA) se suelen usar para proporcionar soluciones aproximadas a problemas que no se pueden resolver fácilmente con otras técnicas (como los problemas NP-hard). Muchos problemas de optimización entran en esta 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, nunca se garantiza que los algoritmos evolutivos encuentren una solución óptima para cualquier problema, pero a menudo encontrarán 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 preconceptos o prejuicios humanos, puede generar soluciones sorprendentes que son comparables o mejores que los mejores esfuerzos generados por los seres humanos. Simplemente es necesario que podamos reconocer una buena solución si nos la presentan, incluso si no sabemos cómo crear una buena solución. En otras palabras, debemos ser capaces de formular una función de aptitud física efectiva.
Algunos ejemplos
EDITAR: El libro de libre acceso, Una guía de campo para la programación genética , contiene ejemplos de dónde GP ha producido resultados competitivos para los seres humanos .
Utilicé la programación genética en mi tesis para simular la evolución de las especies en función del terreno, pero esa es, por supuesto, la aplicación A-life de los 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 alguna otra manera, decir cosas relacionadas con sociedades y comunidades, o en situaciones donde tienes un buen algoritmo pero necesitas ajustar 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, lo que hace que cada oponente sea único y con sus propias peculiaridades, luego los hice competir para eliminar la parte superior 16 IA que utilicé en mi juego. La ventaja era que todos eran muy buenos jugadores con más o menos la misma habilidad, por lo que era interesante para el oponente humano porque no podían adivinar la IA tan fácilmente.