¿Qué está frenando la programación genética?

La parte 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 much mucho más difícil que escribir una suite de prueba. El algoritmo puede adaptarse a cualquier peculiaridad de su función de puntuación y optimizarla. Tratando de evolucionar strcmp? En su lugar, su algoritmo puede descubrir un patrón matemático para las longitudes de su prueba de aprobado / reprobado caso.

• 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 la"escalada de colinas". 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 producir verdadero/falso, entonces está buscando aleatoriamente, no genéticamente.

Si lo intentas descubrirás que la programación genética es lo último en pensamiento lateral: Tu el programa tenderá a resolver el problema de todas las maneras que no se le ocurrió, la mayoría de ellos inesperados y (para aplicaciones serias) probablemente inútiles. Un caso famoso involucró un intento de desarrollar un oscilador utilizando componentes electrónicos básicos. Se juzgó en 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:

[1] 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

Sé que llego tarde a esta fiesta, pero me gustaría hacer un par de puntos. Tuve la increíble suerte de trabajar con John Koza en su libro Genetic Programming 4.

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

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

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

Lo que Tom Castle dijo aquí sobre los programas imperativos no es exactamente cierto. El ejemplo seminal de esto de John and company es la ejecución de diseño de antena. Es más o menos un programa de dibujo 3d con comandos como el lenguaje de dibujo del LOGOTIPO que diseña una antena. Tiene comandos de tipo moveto, lineto para empujar y hacer estallar matrices en una pila. El paquete GP que acabo de ver la semana pasada, jgap, tiene soporte directo: un contenedor tipo nterminal que puede contener sentencias void return y luego tiene una sentencia return al final. Creo que incluso tiene algo como variables locales aunque no miré muy de cerca.

El diseño original de LISP que se ejecuta en los primeros GP es una especie de dolor de vez en cuando, eso es ciertamente cierto. Es algo así como un rito de paso Creo que estar molesto por traducir la salida de una carrera de GP en código más utilizable.

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

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 llegar a una función de destino adecuada y verificar que esto conduce a la solución correcta o aceptable (¿cómo sabe que un algoritmo derivado de la programación genética funciona como se espera ?)

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

Tres cosas:

1. Como dice Andre, es muy difícil escribir una función de aptitud que sea suficiente. Esta es la versión definitiva del Desarrollo impulsado por Pruebas. Tendría que escribir pruebas unitarias que proporcionen una cobertura del 100% de un programa aún no escrito. Incluso entonces, es poco probable que la cobertura del 100% por sí sola sea suficiente. Cuando hemos resuelto el problema de especificar formalmente el comportamiento preciso de todos los aspectos de un sistema complejo, y luego verificar que un programa dado satisface esa especificación, entonces podríamos tener una oportunidad.
2. La programación genética no es determinista y es más adecuada para generar soluciones aproximadas en lugar de soluciones exactas.
3. La programación genética, cuando se aplica a cualquier problema de complejidad razonable, es fenomenalmente costosa computacionalmente. En 1999, Genetic Programming Inc estaba utilizando un clúster de 1.000 nodos para su trabajo en el campo.

GP no puede resolver rápidamente nuevos problemas que están más allá del conocimiento de la persona que crea la función de fitness. Por lo tanto, solo se puede utilizar actualmente para resolver problemas que ya sabemos resolver, pero no son ideales para resolver completamente, debido al espacio de búsqueda. Como el Vendedor Ambulante. Que se puede resolver más rápidamente con un GA.

La razón es en realidad bastante simple. Para resolver problemas novedosos, las herramientas que le dé al GP deben ser lo suficientemente simples, o lo suficientemente completas, para que el GP busque el espacio se convierte en un verdadero análogo a la genética real.

La programación genética, como la genética real, está sujeta al mismo patrón de crecimiento que todos los sistemas de crecimiento de plataformas. Lo que significa que un GP progresará hasta un punto en el que las utilidades principales incluidas golpean una plataforma, se nivela y luego tarda mucho tiempo antes de que tropiece con un nuevo paradigma para construir una nueva plataforma.

Este video pro-evolution ilustra el crecimiento de la plataforma patrón. http://www.youtube.com/watch?v=mcAq9bmCeR0 Se necesita mucho tiempo para desarrollar una nueva mano, y una vez que lo hace, una mano adicional se convierte en la cosa nueva y rápidamente avanza a un ejemplo óptimo de más manos. (Debo mencionar que este video es más probable que use una GA, no GP, pero la genética es genética)

Se trata de la misma lógica que entra en la Teoría de la Singularidad, por cierto.

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

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

Supongamos que tiene una potencia de cálculo infinita descartando el tamaño del espacio de búsqueda y los problemas de lentitud y otras cosas de 'velocidad'. Ahora sólo te enfrentas a dos problemas : - ¿Se detendrá el programa generado ? - ¿ Cómo estar seguro de que el programa generado se comporta de la manera que yo quiero ?

El primer problema es una cuestión central en la teoría de la computabilidad y se llama la detención problema . Turing demostró en 1936 que este problema es indecidible para todos los pares programa-entrada. 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. Así que para esto, no se puede hacer mucho;)

El segundo problema se refería a la corrección del programa. En la programación genética, la validación se realiza generalmente a través de valores de ejemplo que no constituyen en absoluto ninguna prueba de corrección. Esto es comparable a la unidad pruebas, da ok para una serie de ejemplos, pero no ninguna prueba general. Por ejemplo, si escribo un comprobador de números primos, lo pruebo solo con 3 5 7 y 11, entonces un programa que devuelve true para cada número impar pasaría la prueba.

Ir un paso más allá sería utilizar pruebas automatizadas. La prueba automatizada de corrección para algoritmos está de hecho profundamente relacionada con la demostración automática de teoremas matemáticos. Describes tu programa usando un sistema axiomatizado e intentas probar automáticamente el corrección de su declaración. Aquí de nuevo se enfrentan 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 aritmética sobre números naturales, no hay ningún 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 probada, el uso de casos de prueba de muestra para validar el programa genético es muy propenso a la sobreespecialización, el fenómeno conocido como sobreajuste en el aprendizaje automático. Es decir, el programa aprendido hará bien en los casos de prueba proporcionados, pero puede ir totalmente balístico para algunas otras entradas.

Tal vez que la mayoría de los programadores son programadores, y no científicos de la computación?

La programación genética requiere una inteligencia seria. Usted necesita ser capaz de romper el problema de manera adecuada, y necesita un problema apropiado para empezar. Y necesitas saber lo suficiente para saber que los algoritmos genéticos son una opción. Y el problema necesita no tener ya una solución bien conocida.

No todo necesita un algoritmo sofisticado. De todo el código que está escrito en el mundo, aplicaciones web 'estándar', OSs, programación de dispositivos, ¿realmente necesitan algoritmos genéticos?

Y cuando se trata de ello, la mayor parte del esfuerzo de programación se dedica a resolver problemas simples donde no se necesita un enfoque complicado.

Creo que una gran parte de la razón es la gestión de riesgos. Tengan paciencia: cuando un programador se sienta a escribir un programa, tiene al menos alguna idea de cuánto tiempo tomará 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 por el techo: no está claro cuánto tiempo tomará 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.

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

Mi punto de vista personal después de un par de años en la investigación de GP en la universidad y siguiendo el campo después: GP falla a escala.

Los problemas simples representados por funciones simples de fitness GP pueden resolver todos los derechos. Pero como se mencionó antes, formular una función de acondicionamiento físico que describa la tarea de evolucionar strcmp o una calculadora o incluso un simple editor de texto es casi imposible utilizando enfoques clásicos.

Me gusta la noción de que la función GP fitness es TDD en perfección, sin embargo :-) Tal vez alguna mente brillante llegará con una mejor manera 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 implícitas de fitness donde actualmente estoy haciendo algo de 'investigación privada'. ¡Veremos hasta dónde llega!

Saludos, Jay

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

Hoy en día la programación está definiendo la especificación fina de una manera legible por máquina. Le dices al programa qué es exactamente lo que quieres que haga y cómo debería ser el resultado. Ya no es mucho más. Eso significa que si desea generar el resultado, por ejemplo, mediante programación genética, todavía tiene que hacer esta especificación fina legible por máquina en forma de una función de aptitud. Esto conduciría a por lo menos la misma pero probablemente mayor cantidad de trabajo. Así que es el campo equivocado para la genética programación que está hecha para problemas con una especificación fácil de definir pero difícil de alcanzar.

Editar: ahora se podría decir que en la mayoría de los proyectos esta especificación fina se hace de todos modos en forma de pruebas. yo diría que para un enfoque de programación genética las pruebas son una forma de imprecisión para especificar sus necesidades. Se basan en ejemplos y no como la programación basada en un lenguaje de especificación formal. La programación genética probablemente produciría resultados que se adapten a los casos de prueba y se comporten mal en situaciones reales con nuevos inputs. Así que para obtener un nivel de especificación con pruebas que es tan exacto como una especificación con un lenguaje de programación que se necesita una gran cantidad de casos de prueba para cada eventualidad. Así que finalmente terminarías haciendo mucho más trabajo que programar esas cosas.

GP y GA, o en general los Algoritmos Evolutivos son más como pasatiempos. No se utilizan 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 de trabajo de investigación por debajo del par, porque es fácil de entender e implementar en comparación con otras técnicas matemáticamente intensas. Así que los estudiantes sólo encuentran un objetivo para optimizar en alguna ingeniería o aplicación de la ciencia y usted tiene un nuevo trabajo-para ser publicado.

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

Pero es un área de investigación, y depende de nosotros hacer que funcione. En la actualidad es solo un hobby!