# Programmazione genetica

La programmazione genetica, dall'inglese genetic programming (GP), è una metodologia di programmazione automatizzata, ispirata dall'evoluzione biologica, per scoprire programmi informatici che svolgano in maniera ottimale un determinato compito. È una particolare tecnica di apprendimento automatico che usa un algoritmo evolutivo per ottimizzare una popolazione di programmi di computer secondo un paesaggio adattativo determinato dall'abilità del programma di arrivare a un risultato computazionalmente valido (ovvero di saper svolgere il compito dato).

## Storia

I primi esperimenti con la GP sono stati eseguiti da Stephen F. Smith (1980) e Nichael L. Cramer (1985), come descritto nel famoso libro Genetic Programming: On the Programming of Computers by Means of Natural Selection di John Koza (1992).
Sino agli anni '90, a causa delle grandi risorse di calcolo necessarie, il ricorso alla GP era limitato a problemi relativamente semplici. In seguito, col rapido migliorare delle prestazioni dei processori e grazie a sviluppi nella tecnologia GP, si sono ottenuti interessanti risultati in numerose aree. Al momento della scrittura di questo articolo, sono stati ottenuti almeno sessanta risultati competitivi con gli esseri umani, in aree quali gli algoritmi quantistici, il design di componenti elettronici e controller, i giochi, gli algoritmi di ordinamento / ricerca, l'hardware evolutivo e gli stessi programmi per computer. Questi risultati includono la replicazione di molte invenzioni fatte dopo l'anno 2000 e la produzione di alcune invenzioni brevettabili.

## Teoria

Lo sviluppo di una teoria per la programmazione genetica fu compito arduo, cosa per cui, negli anni '90, fu considerata una sorta di paria tra le varie tecniche di ricerca. Tuttavia, dopo una serie di risultati positivi nei primi anni dopo il 2000, la teoria della GP ha avuto un formidabile e rapido sviluppo; così rapido che è stato possibile costruire modelli probabilistici esatti della GP (teorie, diagrammi e modelli tramite catene di Markov) e mostrare che la GP è più generale e come tale include gli algoritmi genetici.

## Struttura dei programmi

I programmi creati con la GP possono essere scritti in molti linguaggi di programmazione. Nelle prime e tradizionali implementazioni della GP le istruzioni e i dati erano organizzati in strutture ad albero, quindi si preferiva l'uso di linguaggi che avessero queste strutture come tipo di dato primitivo; un esempio importante di linguaggio utilizzato da Koza è il Lisp. Sono state suggerite e implementate con successo anche altre forme di GP, come la più semplice rappresentazione lineare che ben si adatta ai normali linguaggi imperativi (vedere al riguardo, Banzhaf e al. (1998)). Il software commerciale che implementa la GP Discipulus, ad esempio, usa la programmazione genetica lineare combinata coi linguaggi in codice macchina per ottenere migliori prestazioni. In maniera diversa il MicroGP usa una rappresentazione interna simile alla programmazione genetica lineare per generare programmi che utilizzino pienamente la sintassi di un dato linguaggio assembly.

## Programmazione meta-genetica

La programmazione meta-genetica è la tecnica utilizzata per fare evolvere un sistema di programmazione genetica utilizzando la stessa programmazione genetica. Nella meta-programmazione genetica, cromosomi, operatori di incrocio e mutazione evolvono essi stessi.