Evoluzione

L’evoluzione in natura è  il fenomeno che contribuisce maggiormente alla sopravvivenza delle specie in quanto permette col passare delle generazioni di adattarsi in maniera sempre più perfetta all’ambiente in cui vivono.  Strategie evolutive sono state implementate anche nei computer, esse  vengono usate principalmente per risolvere problemi di ottimizzazione e prendono il nome di Algoritmi Evolutivi.
Sono stati proposti diversi tipi di questi algoritmi (Algoritmi Genetici, Programmazione Evolutiva, Strategie Evolutive, Programmazione Genetica ecc), ma tutti hanno in comune il concetto di base di evoluzione tramite la riproduzione, ricombinazione e mutazione. Col passare delle generazioni una popolazione scelta a caso, nella quale ogni individuo rappresenta una possibile soluzione al problema da risolvere,  e sulla quale vengono utilizzati degli opportuni operatori convergerà verso una soluzione ottima. Ad ogni individuo viene associato un fitness, cioè un numero che misura quanto quella soluzione è buona, e nella riproduzione si cerca di favorire gli individui che hanno fitness più alto. Dedichiamo un capitolo a parte per gli Algoritmi Genetici, mentre ora discutiamo brevemente alcune delle altre principali tecniche:

Programmazione Evolutiva
Fu inventata nel 1960 da Lawrence J. Fogel ed è una strategia di ottimizzazione stocastica simile agli Algoritmi Genetici, ma mentre questi principalmente cercano di simulare gli operatori di crossover e mutazione come avvengono in natura, la Programmazione Evolutiva si concentra sul legame esistente tra genitori e figli. Il metodo di base consiste in tre passi:

1. Scegliere una popolazione iniziale a caso. Maggiore è il numero di individui, più velocemente si arriverà alla convergenza.
2. Ogni individuo viene copiato in una nuova popolazione e a ciascun figlio viene applicata una mutazione seguendo una certa probabilità.
3. Viene calcolato il fitness di ogni individuo e tramite un torneo con selezione stocastica vengono scelte N possibili soluzioni.

E’ da notare che la principale differenza con gli Algoritmi Genetici sta nel fatto che nella Programmazione Evolutiva non si fa uso dell’operatore di crossover, ma l’evoluzione della popolazione è affidata esclusivamente alla mutazione.

Strategia Evolutiva
E’ un metodo di ottimizzazione che si basa sulla scelta di una strategia che viene poi applicata a una popolazione. Le due principali sono note come Strategia Plus (m+l) e Strategia Comma (m,l). Nel primo caso i genitori possono partecipare alla selezione  nella generazione successiva, mentre nel secondo solo i figli possono essere selezionati, mentre i genitori muoiono. m rappresenta il numero di individui nella popolazione, mentre l il numero di figli concepiti per ogni generazione. Un individuo nella popolazione consiste di un genotipo che rappresenta un punto nello spazio di ricerca (cioè lo spazio delle possibili soluzioni). A ciascun punto vengono associate:

- delle variabili oggetto xi  sulle quali verranno applicati gli operatori di ricombinazione (crossover) e mutazione fino a che non viene raggiunta una soluzione ottima del problema.
- delle  variabili di strategia Si   che determinano la “mutuabilità” di xi.. Esse rappresentano la deviazione standar di una distribuzione Gaussiana (0,Si) Con un valore di expectation uguale a zero i genitori produrranno in media dei figli simili a loro.

Questa strategia funzione perché prima o poi verranno favoriti gli individui che hanno un buon valore della funzione obiettivo (quella da ottimizzare) e che probabilmente ricombinandosi tra loro formeranno figli migliori. Il valore della funzione obiettivo f(x) rappresenta il fenotipo (fitness) di cui si terrà conto nella selezione. Nella strategia Plus i migliori m individui su (m+l) sopravvivranno e diventeranno genitori nella generazione successiva, mentre nella Comma la selezione avviene solo tra i ? figli.
 

Programmazione Genetica
Questa tecnica è simile a quella degli Algoritmi Genetici, ma in questo caso, la popolazione non è costituita da stringhe di bit, ma da programmi che quando vengono eseguiti diventano candidati come possibili soluzioni al problema. Questi programmi vengono codificati con una struttura ad albero, per esempio la codifica di un semplice programma che svolge l’operazione “ a+b*c” è:

           +
          /   \
        a     *
              /   \
            b     c
 

A causa della sua particolare struttura nella programmazione genetica viene usato principalmente il linguaggio LISP. Il crossover avviene prendenfo a caso dei sottoalberi da individui selezionati in base al loro fitness  e ricombinandoli. Da notare che  non viene usato l’operatore di mutazione.