programmazione evolutiva

Question

Ho appena visto un piuttosto fresco ted talk da Danny Hillis datato 1994.

A un certo punto del video, si parla di "programmazione evolutiva", cioè chiede al computer per generare centinaia di programmi per la generazione casuale sequenze di comandi, quindi prove per vedere quanto bene ogni programma ordina i numeri. Mantiene il 10% dei programmi che ordina i numeri al meglio, quindi genera un prossimo ciclo di programmi basato sul 10% che ha funzionato bene e si ripete tutte le volte che vuole, per generare infine il massimo programma di ordinamento.

Ci sono strumenti/linguaggi di programmazione là fuori che lo fanno? Per esempio. dati alcuni vincoli, genera codice C che meglio soddisfa tali vincoli.

Ho visitato alcuni articoli di Wikipedia relativi a "Programmazione evolutiva"; sembra che ci sia molta teoria lì, ma non sembra facile trovare qualcosa con cui puoi giocare.

Answer 1

Una fonte di download gratuito molto semplice e generale è TinyGP implementata in Java. A proposito .. per maggiori dettagli su questo si dovrebbe cercare informazioni su "programmazione genetica" invece di "programmazione evolutiva". è tutto un po 'confuso perché ci sono così tanti sottocampi di computazione evolutiva con piccole diffrenze nei nomi come "algoritmi genetici", "strategie evolutive", "programmazione evolutiva", "programmazione genetica" ... ma penso a quello che tu Stiamo parlando della programmazione genetica

Answer 2

Questo libro/esercitazione utilizza Ruby per la programmazione evolutiva.

http://www.cleveralgorithms.com/nature-inspired/index.html

Answer 3

Un esempio pratico:

Csmith è uno strumento in grado di generare programmi C casuali che staticamente e dinamicamente conformi allo standard C99. È utile per i compilatori di stress test, analizzatori statici e altri strumenti che elaborano il codice C. Csmith ha rilevato bug in tutti gli strumenti che ha testato e l'abbiamo usato per trovare e segnalare più di 400 bug del compilatore precedentemente sconosciuti.

Answer 4

Gli esempi classici sono Tierra e Avida.

Un'area rilevante è l'evoluzione dell'hardware e la robotica evolutiva, vedere ad esempio this page.

C'è anche un bel book sull'informatica evolutiva in Mathematica.

Answer 5

Odio essere un nay sayer, ma abbiamo fatto qualche test con la programmazione evolutiva e abbiamo scoperto che su molti problemi, la ricerca esaustiva era più veloce.

Ci sono campi strettamente correlati come Algoritmi genetici, che ho usato per far camminare i robot, ecc. Ho usato GALIB per questo. È probabilmente antico ora.

Mentre l'idea è "cool", l'approccio migliore potrebbe essere quello di utilizzare una combinazione di tecniche evolutive più apprendimento (cioè apprendimento di rinforzo).

Questo è più simile a come gli umani imparano comunque. C'è un'evoluzione a lungo termine che fa esperimenti graduali, oltre all'apprendimento che aggiusta le cose e adatta il sistema all'ambiente.

Ma l'evoluzione richiede troppo tempo per essere efficiente.

Answer 6

Probabilmente il programma più versatile per la creazione di programmi evolutivi sarebbe Assembler. Questo è l'unico linguaggio che conosco che ha la capacità di sovrascrivere altri programmi e modificare il proprio codice. Potresti dare un'occhiata ai vecchi programmi di Core Wars: una versione diversa o più aggiornata di uno di questi programmi potrebbe essere in grado di evolversi e battere la concorrenza. Inoltre, hai la possibilità di sopravvivenza del più adatto, nella misura in cui ci sono un numero limitato di directory.

Answer 7

Il campo del calcolo evolutivo che genera i programmi si chiama Genetic Programming (GP). GP simula l'evoluzione biologica di una popolazione di individui, attraverso molte generazioni. Di solito, un individuo è un programma (o la sua rappresentazione, tipicamente come una struttura dati dell'albero) e le sue possibilità di sopravvivere e riprodursi sono misurate in termini delle sue prestazioni nel risolvere un compito.

Al giorno d'oggi non è possibile generare codice di produzione pratico per le attività quotidiane, onestamente. Piuttosto, GP e molte altre tecniche di Machine Learning sono investigate nella ricerca moderna e sono utilizzate da aziende molto grandi (ad esempio Google, Facebook, ecc.). In effetti, l'approccio GP è molto utile quando sai cosa vuoi fare il programma obiettivo (cioè conosci l'output dato l'input) ma non hai idea di come (o semplicemente sia difficile per te) scrivere codice da solo.

Per comprendere correttamente l'argomento, è consigliabile scrivere da zero il motore evolutivo e giocare con esso. È perfettamente corretto scrivere il codice a partire da una descrizione teorica. Questo è il modo migliore per imparare come funzionano queste cose, piuttosto che usare un "software pre-costruito", imho. Inoltre, ti suggerisco di iniziare con Genetic Algorithms (GA), perché sono generalmente più semplici. Di fatto, in GA tu di solito valuti il ​​genotipo degli individui, cioè i bit che li compongono, mentre in GP potresti voler trasformare gli alberi in programmi, eseguirli, guardare l'output e infine misurare le loro prestazioni (non così direttamente, uh ?). Date un'occhiata a questo: http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3.

Il laboratorio dove ho svolto la tesi del mio Master sta dimostrando che GP ha ottime prestazioni nel generare espressioni regolari da esempi di estrazione del testo. Costruiscono una GUI per giocare con il loro motore: http://regex.inginf.units.it/demo.html. Hanno anche condiviso il codice del motore su github: https://github.com/MaLeLabTs/RegexGenerator. Infine, un mio amico ha codificato alcuni divertenti esperimenti visivi usando GP e GA (Algoritmi genetici) nel suo blog. Date un'occhiata: http://www.nicassio.it/daniele/gp/enviroment/, http://www.nicassio.it/daniele/gp/santaclaus/.