Evoluzione
Levoluzione 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 allambiente 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 delloperatore di crossover, ma levoluzione 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 loperazione 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 loperatore di mutazione.