algorithm - que - Generación de código por algoritmos genéticos.

ejemplos de aplicaciones de algoritmos geneticos

Question

La programación evolutiva parece ser una excelente manera de resolver muchos problemas de optimización. La idea es muy fácil y la implementación no hace problemas.

Me preguntaba si hay alguna forma de crear evolutivamente un programa en el script ruby ​​/ python (o en cualquier otro idioma)?

La idea es simple:

1. Crear una población de programas.
2. Realice operaciones genéticas (selección de la ruleta o cualquier otra selección), cree nuevos programas con herencia de los mejores programas, etc.
3. Bucle punto 2 hasta encontrar el programa que satisfaga nuestra condición.

Pero todavía hay pocos problemas:

1. ¿Cómo se representarán los cromosomas? Por ejemplo, ¿una célula del cromosoma debería ser una línea de código?
2. ¿Cómo se generarán los cromosomas? Si van a ser líneas de código, ¿cómo las generamos para asegurarnos de que son correctas sintácticamente, etc.?

Ejemplo de un programa que se podría generar:

Cree un script que tome N números como entrada y devuelva su media como salida.

Si hubo algún intento de crear tales algoritmos, estaré encantado de ver los enlaces / fuentes.

Answer 1

Buena suerte con eso.

Claro, usted podría escribir un programa de "mutación" que lea un programa y agregue, elimine o cambie de forma aleatoria algunos caracteres. Luego, puede compilar el resultado y ver si la salida es mejor que el programa original. (Sin embargo, definimos y medimos "mejor"). Por supuesto, el 99.9% de las veces el resultado sería errores de compilación: errores de sintaxis, variables no definidas, etc. Y seguramente la mayoría del resto sería tremendamente incorrecto.

Probar un problema muy simple. Diga, comience con un programa que lea dos números, los sume y produzca la suma. Digamos que el objetivo es un programa que se lee en tres números y calcula la suma. El tiempo y la complejidad de un programa de este tipo depende del idioma. Digamos que tenemos un lenguaje de muy alto nivel que nos permite leer o escribir un número con solo una línea de código. Entonces el programa de inicio es solo 4 líneas:

read x
read y
total=x+y
write total

El programa más simple para alcanzar la meta deseada sería algo así como

read x
read y
read z
total=x+y+z
write total

Entonces, a través de una mutación aleatoria, tenemos que agregar "leer z" y "+ z", un total de 9 caracteres, incluyendo el espacio y la nueva línea. Hagámoslo más fácil con nuestro programa de mutación y digamos que siempre inserta exactamente 9 caracteres aleatorios, que están garantizados en los lugares correctos y que elige entre un conjunto de caracteres de solo 26 letras más 10 dígitos más 14 caracteres especiales = 50 caracteres ¿Cuáles son las probabilidades de que elija los 9 caracteres correctos? 1 en 50 ^ 9 = 1 en 2.0e15. (De acuerdo, el programa funcionaría si en lugar de "leer z" y "+ z" insertó "leer w" y "+ w", pero luego lo hago fácil asumiendo que mágicamente inserta el número correcto de caracteres y siempre los inserta en los lugares correctos. Así que creo que esta estimación es aún generosa.)

1 en 2.0e15 es una probabilidad bastante pequeña. Incluso si el programa se ejecuta mil veces por segundo, y puede probar la salida rápidamente, la probabilidad es de 1 en 2.0e12 por segundo, o 1 en 5.4e8 por hora, 1 en 2.3e7 por día. Manténgalo en funcionamiento durante un año y la probabilidad de éxito sigue siendo de solo 1 en 62,000.

Incluso un programador moderadamente competente debería poder hacer tal cambio en, ¿qué, diez minutos?

Tenga en cuenta que los cambios deben venir al menos en "paquetes" que sean correctos. Es decir, si una mutación genera "reax z", está a solo un carácter de "leer z", pero aún así produciría errores de compilación, y por lo tanto fallaría.

Del mismo modo, agregar "leer z", pero cambiar el cálculo a "total = x + y + w" no va a funcionar. Dependiendo del idioma, obtendrás errores para la variable no definida o, en el mejor de los casos, tendrá algún valor predeterminado, como cero, y dará resultados incorrectos.

Se podría, supongo, teorizar soluciones incrementales. Tal vez una mutación agregue la nueva declaración de lectura, luego una futura mutación actualiza el cálculo. Pero sin el cálculo, la lectura adicional no vale nada. ¿Cómo se evaluará el programa para determinar que la lectura adicional es "un paso en la dirección correcta"? La única manera que veo para hacerlo es hacer que un ser inteligente lea el código después de cada mutación y vea si el cambio avanza hacia la meta deseada. Y si tiene un diseñador inteligente que puede hacer eso, eso significa que él sabe cuál es el objetivo deseado y cómo lograrlo. En ese momento, sería mucho más eficiente realizar el cambio deseado en lugar de esperar a que suceda de forma aleatoria.

Y este es un programa extremadamente trivial en un lenguaje muy fácil. La mayoría de los programas son, qué, cientos o miles de líneas, todas las cuales deben trabajar juntas. Las probabilidades en contra de cualquier proceso aleatorio al escribir un programa de trabajo son astronómicas.

Puede haber formas de hacer algo que se parezca a esto en alguna aplicación muy especializada, en la que realmente no se realizan mutaciones aleatorias, sino que se realizan modificaciones incrementales a los parámetros de una solución. Como, tenemos una fórmula con algunas constantes cuyos valores no conocemos. Sabemos cuáles son los resultados correctos para un pequeño conjunto de entradas. Así que hacemos cambios aleatorios a las constantes, y si el resultado está más cerca de la respuesta correcta, cambie desde allí, si no, vuelva al valor anterior. Pero incluso con eso, creo que rara vez sería productivo hacer cambios al azar. Probablemente sería más útil intentar cambiar las constantes de acuerdo con una fórmula estricta, como comenzar por cambiar por 1000, luego por 100, luego por 10, etc.

Answer 2

Bueno, esto es muy posible y @Jivlain señala correctamente en su (buena) respuesta que la Programación genética es lo que estás buscando (y no los simples Algoritmos Genéticos).

La programación genética es un campo que aún no ha llegado a un público amplio, en parte debido a algunas de las complicaciones que @MichaelBorgwardt indica en su respuesta. Pero esas son meras complicaciones , está lejos de ser verdad que esto es imposible de hacer. La investigación sobre el tema lleva más de 20 años en marcha.

Andre Koza es uno de los principales investigadores sobre esto (eche un vistazo a su trabajo de 1992 ) y demostró citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7754 cómo la programación genética puede, en algunos casos, superar a las AG ingenuas en algunos problemas computacionales clásicos (como los programas en evolución para la sincronización de autómatas celulares). ).

Aquí hay un buen tutorial de programación genética de Koza y Poli con fecha de 2003.

Para una referencia reciente, es posible que desee echar un vistazo a Una guía de campo para la programación genética (2008).

Answer 3

Desde que se hizo esta pregunta, el campo de la programación genética ha avanzado un poco, y ha habido algunos intentos adicionales para evolucionar el código en configuraciones distintas a las estructuras de árbol de la programación genética tradicional. Estos son solo algunos de ellos:

• PushGP : diseñado con el objetivo de desarrollar funciones modulares como el uso de codificadores humanos, los programas de este sistema almacenan todas las variables y el código en diferentes pilas (una para cada tipo de variable). Los programas se escriben presionando y haciendo saltar comandos y datos fuera de las pilas.
• FINCH - un sistema que evoluciona el código de bytes de Java. Esto ha sido usado con gran efecto para evolucionar a los agentes de juego.
• Varios algoritmos han comenzado a evolucionar el código C ++, a menudo con un paso en el que se corrigen los errores del compilador. Esto ha tenido resultados mixtos, pero no del todo poco prometedores. Aquí hay un ejemplo .
• Avida : un sistema en el que los agentes desarrollan programas (en su mayoría tareas de lógica booleana) utilizando un código de ensamblaje muy simple. Basado en la Tierra más antigua (y menos versátil).

Answer 4

El idioma no es un problema. Independientemente del idioma, debe definir un nivel más alto de mutación, de lo contrario tardará una eternidad en aprender.

Por ejemplo, dado que cualquier lenguaje Ruby puede definirse en términos de una cadena de texto, podría generar cadenas de texto al azar y optimizarlas. Mejor sería generar solo programas legales de ruby. Sin embargo, también llevaría para siempre.

Si intentara construir un programa de clasificación y tuviera operaciones de alto nivel como "swap", "move", etc., tendría una probabilidad mucho mayor de éxito.

En teoría, un grupo de monos que golpean una máquina de escribir durante un tiempo infinito mostrarán todas las obras de Shakespeare. En la práctica, no es una forma práctica de escribir literatura. El hecho de que los algoritmos genéticos puedan resolver problemas de optimización no significa que sea fácil o incluso necesariamente una buena forma de hacerlo.

Answer 5

El mayor punto de venta de los algoritmos genéticos, como usted dice, es que son muy simples . No tienen el mejor rendimiento ni los antecedentes matemáticos, pero incluso si no tiene idea de cómo resolver su problema, siempre que pueda definirlo como un problema de optimización , podrá convertirlo en un GA.

Los programas no son realmente adecuados para GA precisamente porque el código no es un buen material cromosómico. He visto a alguien que hizo algo similar con el código de máquina (más simple) en lugar de Python (aunque fue más una simulación de un ecosistema que una GA en sí) y es posible que tenga más suerte si codifica sus programas usando autómatas / LISP o algo así. ese.

Por otro lado, teniendo en cuenta lo atractivos que son los GA y cómo básicamente todos los que los miran hacen la misma pregunta, estoy bastante seguro de que ya hay personas que intentaron esto en algún lugar, simplemente no tengo idea si alguno de ellos tuvo éxito.

Answer 6

Se puede hacer, pero funciona muy mal para la mayoría de las aplicaciones.

Los algoritmos genéticos solo funcionan cuando la función de adecuación es continua, es decir, puede determinar qué candidatos de su población actual están más cerca de la solución que otros, porque solo así obtendrá mejoras de una generación a otra. Aprendí esto de la manera difícil cuando tenía un algoritmo genético con un componente no continuo fuertemente ponderado en mi función de condición física. Dominó a todos los demás y, como no era continuo, no hubo un avance gradual hacia una mejor aptitud física porque los candidatos que eran casi correctos en ese aspecto no se consideraban más adecuados que los que eran completamente incorrectos.

Desafortunadamente, la corrección del programa es completamente no continua. ¿Es un programa que se detiene con el error X en la línea A mejor que uno que se detiene con el error Y en la línea B? Su programa podría estar a un carácter de ser correcto, y aun así abortar con un error, mientras que uno que devuelva un resultado codificado de manera constante puede al menos pasar una prueba.

Y eso ni siquiera se refiere a la cuestión de que el código en sí no sea continuo bajo modificaciones ...

Answer 7

Si está seguro de que desea hacer esto, desea programación genética , en lugar de un algoritmo genético. GP te permite evolucionar programas estructurados en arboles. Lo que haría sería darle un montón de operaciones primitivas (mientras que ($ registrar), leer ($ registrar), incrementar ($ registrar), disminuir ($ registrar), dividir ($ resultado $ numerador $ denominador), imprimir , progn2 (es GP hablar para "ejecutar dos comandos secuencialmente")).

Podrías producir algo como esto:

progn2(
  progn2(
    read($1)
    while($1
      progn2(
        while($1
          progn2( #add the input to the total
            increment($2)
            decrement($1)
          )
        )
        progn2( #increment number of values entered, read again
          increment($3)
          read($1)
        )
      )
    )
  )
  progn2( #calculate result
    divide($1 $2 $3)
    print($1)
  )
)  

Usaría, como función de su estado físico, lo cerca que está de la solución real. Y ahí está la trampa, que tienes que calcular eso tradicionalmente de todos modos *. Y luego tenga algo que se traduzca en código (su idioma de elección). Tenga en cuenta que, dado que tiene un bucle infinito potencial allí, tendrá que interrumpir la ejecución después de un tiempo (no hay forma de evitar el problema de la detención), y probablemente no funcionará. Shucks Tenga en cuenta también, que mi código provisto intentará dividir por cero.

* Hay formas de evitar esto, pero generalmente no demasiado lejos.

Answer 8

Solo quiero darte una sugerencia. No sé qué tan exitoso sería, pero quizás podría intentar evolucionar un robot de guerra central con programación genética. Tu función de fitness es fácil: solo deja que los bots compitan en un juego. Podría comenzar con bots bien conocidos y tal vez unos cuantos aleatorios, luego esperar y ver qué sucede.