Algoritmi evolutivi

Il caso spesso ci porta a trovare soluzioni nuove e inaspettate a problemi difficilmente trattabili.

Gli algoritmi evolutivi sono delle metaeuristiche basate sulla logica del modello evoluzionistico, utilizzati per la ricerca della soluzione ottimale di un problema.

Negli algoritmi evolutivi si evolve una popolazione di individui utilizzando operatori che mimano il processo evolutivo della teoria di Darwin. Di generazione in generazione si generano nuovi individui facendo accoppiare quelli delle generazioni precedenti, ottenendo nuovi individui che sono ricombinazione delle soluzioni già esplorate.

Ogni individuo trasmette quindi parte del suo patrimonio genetico ai discendenti. La creazione dei nuovi individui è essenzialmente un processo stocastico ma, malgrado questo, permette a volte di superare le trappole del “minimo locale” in cui possono cadere i metodi deterministici.

Nonostante si tratti di ricerca non informata, in quanto si parte dal non avere alcuna conoscenza del dominio, la popolazione acquista una maggiore “consapevolezza del problema” durante il processo evolutivo. In questo caso si parla di “intelligenza emergente”.

Come la natura, gli algoritmi evolutivi sono stati capaci di generare con successo soluzioni nuove e inaspettate a problemi difficilmente trattabili.

Programmazione genetica, Algoritmi genetici

Si è soliti suddividere gli algoritmi evolutivi in “algoritmi genetici” e “programmazione genetica”.

Algoritmi evolutivi, come funzionano

Tutti i tipi di algoritmi genetici condividono la stessa struttura di base

Crea la popolazione iniziale
Calcola la fitness per ogni individuo
DO
  Seleziona gli individui per il crossover
  Applica il crossover
  Seleziona gli individui per la mutazione
  Applica la mutazione
  IF la popolazione ha superato il limite THEN
    seleziona gli individui da eliminare
    riduci la popolazione
  END
UNTIL si e` verificato un criterio di stop
RETURN l`individuo migliore della popolazione

Ognuno dei passi dell’algoritmo può essere implementato in diversi modi che creano ecosistemi che si comportano in modi differenti.

Algoritmi evolutivi, perché funzionano

L’approccio degli algoritmi evolutivi è essenzialmente empirico, esiste infatti pochissima teoria sul loro funzionamento. Un teorema che cerca di dimostrarne la convergenza alla soluzione è il famoso Teorema degli schemi di [cit. holland ], sviluppato originariamente per gli Algoritmi genetici ed esteso successivamente anche alla Programmazione Genetica [cit. poli:1997:schemaTR ].

Il teorema degli schemi ci assicura che, sotto opportune ipotesi, il meccanismo del crossover tende a far crescere il numero di individui performanti in modo esponenziale, rendendo probabile una convergenza della popolazione verso la soluzione. Il teorema si basa sul fatto che a ogni cromosoma vengono date possibilità di riprodursi in modo proporzionale alla sua fitness ( necessita quindi di selezione a fitness proporzionale). Il teorema si basa sul concetto di Schema;

Uno schema è una stringa nell’alfabeto dei cromosomi ,incluso un carattere "don’t care", che rappresenta un sottoinsieme di soluzioni.

Il teorema afferma che schemi particolari, ovvero che soddisfano determinate condizioni, ricevono un numero esponenziale di soluzioni al variare delle generazioni.

Tale risultato vale per una struttura particolare di algoritmo, che usa selezione a fitness proporzionale, crossover a singolo taglio e bit mutazione.

Algoritmi evolutivi, funzionano?

Il teorema degli Schemi dà un supporto teorico al funzionamento degli algoritmi evolutivi, ma in effetti è difficilmente applicabile a casi reali poiché richiede una popolazione infinita e una strategia di selezione a fitness proporzionale. La prova che gli algoritmi evolutivi funzionano è essenzialmente un’evidenza empirica.

Dalla loro prima introduzione gli algoritmi evolutivi, e in particolare la programmazione genetica, sono stati utilizzati con successo in un numero sorprendente di casi; in letteratura esistono più di 5000 articoli che usano la programmazione genetica per i fini più disparati.

Tipicamente gli algoritmi evolutivi si prestano a risolvere problemi in ambiti in cui non è possibile trovare per via analitica una soluzione esatta o in domini che non sono completamente conosciuti, ma in cui è possibile svolgere delle simulazioni e produrre facilmente dataset abbastanza ampi.

Malgrado l’approccio degli algoritmi evolutivi sia essenzialmente empirico ed esista pochissima teoria sul loro funzionamento, essi si sono rivelati funzionanti in molte applicazioni.

Antenne sviluppate geneticamente.

L’esempio più famoso di programmazione genetica applicata con successo è probabilmente l’antenna [cit. hornby2006automated ], che è attualmente in uso nel satelliti artificiali della missione Space Technology 5 (ST5).

Questa due applicazione è un esempio tipico dell’ambito in cui gli algoritmi evolutivi sono utilizzati con successo: problemi in domini complessi e senza soluzioni analitiche, ma in cui è possibile utilizzare dei simulatori per misurare i risultati. In altre parole, non si ha idea di come risolvere il problema ma si può riconoscere immediatamente una soluzione buona.

Oltre a queste applicazioni appena menzionate, ne esistono moltissime negli ambiti più disparati, dall’intelligenza artificiale al Trading Finanziario, dal data mining per dati biomedici al trovare un algoritmo per giocare a Ms Pac-man. Elencarle tutte è quasi impossibile, per una bibliografia dettagliata delle applicazioni rimando al testo “A field guide to genetic programming” [cit. poli2008field ]