algorithm - keywords - ¿Qué está reteniendo la programación genética?

meta tags seo 2018 (14)

Creo que una gran parte de la razón es la gestión de riesgos. Tenga paciencia conmigo: cuando un programador se sienta a escribir un programa, tiene al menos alguna idea de cuánto tiempo llevará y de lo que puede hacer.

Cuando en cambio un programador se sienta a escribir un programa que generará un programa (usando programación genética), la incertidumbre se dispara: no está claro cuánto durará el proceso, y no está claro qué tan bueno puede ser el programa final.

También hay incertidumbre en otros lugares: ¿qué tan fácil será ajustar el programa más tarde o corregir errores? El código generado puede ser casi imposible de depurar.

He realizado una gran cantidad de trabajo con algoritmos genéticos con bastante éxito y hasta ahora ignoré la programación genética. Por lo que yo sé, la mayoría de los programas siguen escritos por programadores, y tengo curiosidad por saber qué es lo que detiene la programación genética.

Algunas explicaciones posibles en las que pensé son:

El espacio de búsqueda es demasiado grande para encontrar programas útiles entre el ruido
La mayoría de las aplicaciones reales no pueden proporcionar datos suficientes para permitir la evaluación de la aptitud de dicho espacio.
Es difícil reducir la eficacia de muchas aplicaciones reales hasta una única medida de aptitud. En otras palabras, escribir una función de aptitud física adecuada implicaría probablemente la misma cantidad de trabajo que escribir el programa real.

¿Algunas ideas?

Es simplemente porque se ha demostrado que es teóricamente imposible (al menos para los programas correctos).

Supongamos que tiene una potencia informática infinita que descarta los problemas de tamaño y lentitud del espacio de búsqueda y otras cuestiones de "velocidad". Ahora solo enfrenta dos problemas: - ¿Se detendrá el programa generado? - ¿Cómo puedo asegurarme de que el programa generado se comporte como yo quiero?

El primer problema es una pregunta central en la teoría de computabilidad y se llama el problema de detención . Turing demostró en 1936 que este problema es indecidible para todos los pares de entrada de programa. Esto significa que es posible en algunos casos, pero no para todos. No hay un proceso automatizado que pueda determinar si un programa se detiene o no. Entonces para esto, no puedes hacer mucho;)

El segundo problema relacionado con la corrección del programa. En la programación genética, la validación generalmente se realiza a través de valores de ejemplo que no constituyen en absoluto ninguna prueba de corrección. Esto es comparable a la prueba unitaria, da buenos resultados para varios ejemplos, pero no prueba general. Por ejemplo, si escribo un corrector de número principal, lo prueba solo con 3 5 7 y 11, luego un programa que devuelve verdadero para cada número impar pasaría la prueba.

Dar un paso más sería utilizar pruebas automatizadas. La prueba automatizada de la corrección de los algoritmos está, de hecho, profundamente relacionada con la demostración automática de teoremas matemáticos. Usted describe su programa usando un sistema axiomatizado y trata de probar automáticamente la exactitud de su declaración. Aquí nuevamente te enfrentas a fuertes barreras teóricas, que son los teoremas de Incompletitud de Gödel . Estos teoremas establecen, entre otras cosas, que incluso para sistemas axiomatizados muy simples, capaces de realizar operaciones aritméticas sobre números naturales, no existe un algoritmo (llamado procedimiento efectivo) capaz de probar todos los teoremas con respecto a estos números naturales. Concretamente, esto significa que incluso para programas simples, no podrá probar su corrección.

Incluso sin una corrección comprobada, el uso de casos de prueba de muestra para validar el programa genético es muy propenso a la especialización excesiva, el fenómeno conocido como sobreajuste en el aprendizaje automático. Es decir, el programa aprendido funcionará bien en los casos de prueba proporcionados, pero puede ser totalmente balístico para otras entradas.

Esto es algo que he estado considerando en mi propia investigación, y diría que hay muchas razones:

La gran mayoría de las investigaciones en el campo GP se han centrado en producir fórmulas en lugar del tipo de software que produce la mayoría de los programadores. Hay muchos científicos informáticos en el campo, pero muy pocos se concentran en producir el tipo de programas que usted esperaría, por lo que los avances han sido lentos en esa área.
Hay un énfasis excesivo significativo en el uso de LISP porque puede producir estructuras de árbol agradables que son fáciles de manipular y desafortunadamente los programas imperativos han sido descuidados porque implican la solución de algunos problemas complicados. Para que un GP sea tomado en serio por los programadores, tiene que producir programas imperativos.
Los programas reales contienen construcciones de bucle, pero los bucles son difíciles de implementar en GP sin todo tipo de restricciones desagradables para evitar el bucle infinito.
La Programación Genética no escala bien. Está bien para problemas pequeños, con un lenguaje pequeño disponible, pero como dices en tu primer punto, el espacio de búsqueda se vuelve demasiado grande muy rápidamente.
Comparado con un programador humano, GP puede ser muy lento. Sin embargo, es muy paralelable, por lo que es probable que se beneficie sustancialmente a medida que un mayor número de núcleos de procesador se convierta en la norma.

Otra respuesta válida sería que es difícil confiar en que el código se haya generado automáticamente. Esto es cierto, pero en la práctica, dudo que esto tenga mucho impacto porque GP no es capaz de producir el tipo correcto de programas en primer lugar.

GP no puede resolver rápidamente problemas nuevos que están más allá del conocimiento de la persona que crea la función de aptitud física. Por lo tanto, solo se puede usar actualmente para resolver problemas que ya sabemos cómo resolver, pero no son ideales para resolver completamente, debido al espacio de búsqueda. Tales como Traveling Salesman. Que se puede resolver más rápidamente con un GA.

La razón es bastante simple. Para resolver problemas novedosos, las herramientas que le da al GP deben ser lo suficientemente simples o completas como para que el espacio de búsqueda de GP se convierta en un verdadero análogo de la genética real.

La Programación Genética, al igual que la genética real, está sujeta al mismo patrón de crecimiento que todos los sistemas de crecimiento de plataforma. Lo que significa que un médico de cabecera progresará hasta el punto en que los servicios básicos incluidos lleguen a una plataforma, se nivele, y luego tome mucho tiempo antes de que tropiece con un nuevo paradigma para construir una nueva plataforma.

Este video favorable a la evolución ilustra estos patrones de crecimiento de la plataforma. http://www.youtube.com/watch?v=mcAq9bmCeR0 Lleva mucho tiempo desarrollar una nueva mano, y una vez que lo hace, una mano adicional se convierte en lo nuevo y avanza rápidamente a un ejemplo óptimo de más manos. (Debo mencionar que este video es muy probable que use un GA, no GP, pero la genética es genética)

Esto es todo sobre la misma lógica que entra en Singularity Theory, BTW.

Pero lo que esto significa para los médicos de cabecera es que es muy bueno, solo es bueno para la investigación, no para la aplicación práctica dentro de un programa. Con unas simples excepciones donde los requisitos son un poco más profundos de lo que un GA puede resolver. Como algunos programas de programador. Donde el espacio de búsqueda de programación es bastante pequeño, y donde se comprenden bien las herramientas necesarias para resolverlo, y donde puede haber una función de aptitud física bien definida.

GP y GA, o en general, algoritmos evolutivos son más como pasatiempos. No se usan para aplicaciones de la vida real, salvo excepciones. La razón es que estos algoritmos se basan en la aleatoriedad. No hay certeza de obtener una buena respuesta.

Además, esta área está inundada con un trabajo de investigación por debajo de la verdad, porque es fácil de comprender e implementar en comparación con otras técnicas matemáticamente intensas. Entonces los estudiantes solo encuentran un objetivo para optimizar en alguna aplicación de ingeniería o ciencia y tienen un nuevo trabajo: para ser publicados.

Simplemente compare los patrocinadores de sus conferencias con los de otras conferencias de IA / ML / Optimización. Será claro sobre su importancia "actual" en la industria.

Pero es un área de investigación, y depende de nosotros para que funcione. ¡En este momento es solo un hobby!

Hay algunos proyectos que abordan los problemas mencionados anteriormente en GP. Un ejemplo sería el opencog MOSES

Hoy en día, la programación está definiendo la especificación fina de una manera legible por máquina. Usted le dice al programa qué es exactamente lo que quiere que haga y cómo debería verse el resultado. Ya no es mucho más. Eso significa que si desea generar el resultado por ejemplo, la programación genética, usted todavía tiene que hacer esta especificación fina legible por máquina en forma de una función de acondicionamiento físico. Esto llevaría al menos a la misma pero probablemente mayor cantidad de trabajo. Por lo tanto, es un campo equivocado para la programación genética que está hecho para problemas con una especificación fácil de definir pero difícil de alcanzar.

editar: ahora puede decir que en la mayoría de los proyectos esta fina especificación se hace de todos modos en forma de pruebas. Diría que para un enfoque de programación genética las pruebas son imprecisas para especificar sus necesidades. Se basan en ejemplos y no en la programación basada en un lenguaje de especificación formal. La programación genética probablemente produzca resultados que se adapten a los casos de prueba y se comporten mal en situaciones reales con nuevas entradas. Entonces, para obtener un nivel de especificación con pruebas tan exactas como una especificación con un lenguaje de programación, necesitaría una gran cantidad de casos de prueba para cada eventualidad. Así que finalmente terminarías haciendo mucho más trabajo que programando eso.

La parte más difícil de la programación genética es escribir una buena función de puntuación:

La función de puntuación debe juzgar correctamente si el algoritmo tiene las propiedades deseadas. Esto es más difícil de lo que parece, mucho más difícil que escribir un banco de pruebas. El algoritmo puede adaptarse a cualquier peculiaridad de su función de puntuación y optimizarla. ¿Intentando evolucionar strcmp ? En su lugar, el algoritmo puede descubrir un patrón matemático para las longitudes de los casos de prueba de aprobación / falla.
La función de puntuación debe ser capaz de juzgar si el algoritmo bajo prueba está funcionando parcialmente. La programación genética se basa en "escalar montañas". Una pequeña mutación beneficiosa necesita causar una pequeña mejora incremental en la puntuación. Si su función de puntuación solo puede mostrar verdadero / falso, entonces está buscando al azar, no genéticamente.

Si pruebas tu mano, descubrirás que la programación genética es lo último en pensamiento lateral: tu programa tenderá a resolver el problema de todas las formas en que no pensaste, la mayoría de ellos inesperados y (para aplicaciones serias) probablemente inútil. Un caso famoso involucró un intento de desarrollar un oscilador usando componentes electrónicos básicos. Fue juzgado por la simplicidad del circuito y si la salida oscilaba. Produjo algo tan simple que los investigadores estaban seguros de que no podía funcionar, pero lo hizo: estaba captando y amplificando las ondas de radio del entorno.

Editar para citar:

Graham-Rowe, Duncan. "La radio emerge de la sopa electrónica". New Scientist, vol.175, no.2358, p.19 (31 de agosto de 2002). Disponible en línea en http://www.newscientist.com/news/news.jsp?id=ns99992732

Sin embargo, el enlace ahora parece estar roto.

El nuevo enlace es http://www.newscientist.com/article/dn2732-radio-emerges-from-the-electronic-soup.html

La sopa primordial es sospechosa y poco apetecible. Para mi código de producción prefiero el Diseño Inteligente.

Mi opinión personal después de un par de años en la investigación de GP en la universidad y después del campo: GP no escala.

Problemas simples representados por simples funciones de aptitud que GP puede resolver bien. Pero como se mencionó anteriormente, la formulación de una función de aptitud física que describa la tarea de desarrollar strcmp o una calculadora o incluso un editor de texto simple es casi imposible con los enfoques clásicos.

Sin embargo, me gusta la idea de que la función de fitness GP sea TDD a la perfección :-) Tal vez alguna mente brillante presente una forma mejor de dirigir la evolución simulada algún día, pero eso todavía tiene que suceder.

Tengo algunas esperanzas para GP en el área de funciones físicas implícitas en las que actualmente estoy haciendo una "investigación privada". ¡Veremos qué tan lejos llegará!

Saludos, Jay

Sé que llego tarde a esta fiesta, pero me gustaría mencionar un par de puntos. Tuve la increíble buena suerte de trabajar con John Koza en su libro de Programación Genética 4.

El tipo de programación que la mayoría de nosotros hacemos día a día, conectar eventos de GUI, empujar píxeles, bases de datos, etc., ciertamente no es el tipo de programas que GP pretende construir.

Lo que John Koza hace con su grupo de alrededor de cien máquinas (si mal no recuerdo) es buscar soluciones a problemas interesantes (piense en NP-hard). Es triste, pero la mayoría de los problemas con los que los programadores trabajamos día a día no son problemas muy interesantes o difíciles, en su mayoría simplemente irritantes y lentos.

Lo que dijo Ben Jackson sobre un oscilador electrónico de ingeniería genética es lo más parecido a lo que hacen en realidad el Dr. Koza y el equipo. Hubo muchos ejemplos de circuitos en la serie GP de libros.

Lo que Tom Castle dijo aquí acerca de los programas imperativos no es exactamente cierto. El ejemplo seminal de esto de John y compañía es la ejecución del diseño de la antena. Es más o menos un programa de dibujo en 3D con comandos como el lenguaje de dibujo LOGO que diseña una antena. Tiene comandos moveto, lineto type para empujar y explotar matrices en una pila. El paquete de GP que acabo de ver la semana pasada, jgap, tiene soporte directo: un tipo de contenedor no terminal que puede contener declaraciones de devolución nulas y luego tiene una declaración de devolución al final. Creo que incluso tiene algo así como variables locales, aunque no me fijé demasiado.

El diseño original de LISP en el que se centran las primeras carreras de GP es una especie de dolor de vez en cuando, eso es cierto. Es algo así como un rito de transición, creo que me molesta la traducción de la salida de un GP en un código más útil.

TL; DR: GP no es realmente un sistema de programación automática. Es un sistema de invención automatizado.

Tal vez la mayoría de los programadores son programadores, y no informáticos?

La programación genética requiere una gran inteligencia. Debe poder resolver el problema adecuadamente y para empezar necesita un problema apropiado. Y necesita saber lo suficiente como para saber que los algoritmos genéticos son una opción. Y el problema no necesita tener una solución conocida.

No todo necesita un algoritmo elegante. De todo el código que está escrito en el mundo, ¿los webapps "estándar", los sistemas operativos, la programación de dispositivos realmente necesitan algoritmos genéticos?

Y a fin de cuentas, la mayoría del esfuerzo de programación está dedicado a resolver problemas simples donde no se necesita un enfoque complicado.

Tres cosas:

Como dice Andre , es muy difícil escribir una función de acondicionamiento físico que sea suficiente. Esta es la última versión de Test Driven Development. Tendría que escribir pruebas unitarias que brinden una cobertura del 100% de un programa aún no escrito. Incluso entonces, una cobertura del 100% en sí misma es poco probable que sea suficiente. Cuando hayamos resuelto el problema de especificar formalmente el comportamiento preciso de todos los aspectos de un sistema complejo, y luego verifiquemos que un programa determinado cumpla con esa especificación, entonces podríamos tener una oportunidad.
La Programación Genética no es determinista y es más adecuada para generar soluciones aproximadas en lugar de soluciones exactas.
La Programación Genética, cuando se aplica a cualquier problema de complejidad razonable, es fenomenalmente computacionalmente costosa. En 1999, Genetic Programming Inc utilizaba un clúster de 1.000 nodos para su trabajo en el campo.

Yo diría 1. y 3.

En particular, con respecto al punto 3, diría que en la mayoría de los casos es incluso más fácil escribir el programa real que idear una función objetivo adecuada y verificar que esto conduzca a la solución correcta o aceptable (¿cómo se sabe? un algoritmo derivado de la programación genética funciona como se esperaba?)

Con respecto al punto 1, diría que el espacio de búsqueda tiene un número infinito de dimensiones.