CAPITOLO 1
ALGORITMI GENETICI
1.1 Introduzione agli algoritmi genetici
Gli algoritmi genetici (Genetic Algorithm – GA) sono dei metodi stocastici di ricerca basati sui concetti di evoluzione e selezione naturale ripresi dalla teoria di Darwin e volti all’ottimizzazione di apparati e strutture caratterizzati da molti parametri [1].
I problemi di ottimizzazione elettromagnetica richiedono spesso la determinzione di un gran numero di parametri in forma discreta, continua (o entrambe) e di solito consistono nella ricerca di un massimo o di un minimo globale della funzione, in genere multimodale, caratteristica del problema.
Le tecniche locali producono risultati fortemente dipendenti dalle condizioni iniziali e al contorno e sono molto legate alla natura del dominio di soluzione, in termini di continuità e differenziabilità, che spesso non sono applicabili nella pratica.
Le tecniche globali invece, non solo sono indipendenti dallo spazio di soluzione, ma funzionano meglio quando questo contiene delle discontinuità, presenta molti massimi locali e parametri vincolanti. Tuttavia tali tecniche non sono particolarmente veloci nella convergenza ad un punto di massimo o minimo assoluto [1]. Un GA deve poter disporre di un set di dati iniziali che caratterizzano la struttura da ottimizzare: ogni possibile combinazione di dati costituisce un individuo, ogni individuo è in genere rappresentato da un cromosoma che è a sua volta composto da un insieme di geni detto genotipo. Ogni gene costituisce un parametro da ottimizzare ed il suo valore può essere rappresentato mediante un codice binario, come nella maggior parte delle applicazioni, ternario, a cifre intere, reali e così via. Sebbene i GA lavorino su variabili codificate, la soluzione migliore del problema è data dall’ insieme dei parametri codificati in valori reali che possono essere interpretati come una sorta di fenotipo di un individuo.
Una volta che è stato creato un cromosoma con tutti i suoi geni, si definisce un’ opportuna funzione di fitness mediante la quale si valuta la forma fisica di un individuo, in altre parole si valuta quanto la soluzione trovata è vicina a quella ottima.
POPOLAZIONE Set di individui
GENITORI Membri della popolazione corrente
FIGLI Membri della popolazione alla generazione successiva
GENERAZIONE Popolazione al passo i-esimo
CROMOSOMA Forma di codifica del vettore delle soluzioni possibili costituito da geni
GENE Parametro della struttura da ottimizzare
FITNESS Funzione definita positiva che misura l’ottimalità di un individuo
ALLELI Bit che costituiscono ogni singolo parametro codificato
Tabella 1: Concetti principali che fanno capo alla teoria degli algoritmi genetici
Nella tabella 1 sono sinteticamente riportati i principali concetti che sono stati introdotti precedentemente.
Riassumendo quanto esposto finora, i GA sono tecniche di ottimizzazione migliori rispetto ai metodi tradizionali per i seguenti motivi:
• conducono una ricerca su più individui in parallelo;
• non richiedono informazioni ausiliarie o derivative, la sola funzione di fitness è in grado di influenzare la direzione di ricerca;
• si basano su un metodo statistico, probabilistico; • lavorano su parametri codificati.
Gli aspetti significativi su cui si basano tali algoritmi sono:
• inizializzazione di una popolazione di partenza e relativi cromosomi; • creazione delle stringhe di geni;
• codifica dei parametri della soluzione;
• valutazione e assegnazione dei valori di fitness ad ogni individuo;
• ricombinazione e mutazione per produrre membri della popolazione successiva [4].
1.2 Funzionamento di un algoritmo genetico
Un GA si articola generalmente in più fasi: inizializzazione, riproduzione e generazione di repliche; la prima di queste consiste nel creare una popolazione iniziale (set di soluzioni) mediante un numero predeterminato di cromosomi (stringhe di parametri codificati scelti in maniera casuale).
Di ogni individuo che appartiene alla popolazione corrente viene poi valutata la funzione di fitness che misura quanto le sue caratteristiche siano vicine a quelle ottime.
La successiva fase di riproduzione consente di generare una nuova popolazione a partire dalla precedente, un paio di individui della generazione corrente vengono selezionati come genitori, subiscono crossover e mutazioni per produrre figli della nuova generazione; tali operazioni vengono ripetute finché si raggiunge un numero sufficiente di elementi per sostituire la generazione corrente con la nuova.
L’algoritmo è detto generazionale se la nuova popolazione è della stessa dimensione della precedente, altrimenti è detto steady-state ed inoltre elementi della vecchia generazione possono sovrapporsi e coesistere con quelli della nuova.
L’ ultima fase consiste essenzialmente nella sostituzione intera o parziale della vecchia popolazione con la nuova e nel calcolo dei nuovi valori di fitness che sono poi assegnati agli individui appena creati; se viene raggiunto il criterio di terminazione del processo evolutivo, l’algoritmo termina altrimenti si continua ad iterare sui cromosomi appena creati [4], [5].
1.3 Strategie di selezione
Il processo di sostituzione della popolazione viene guidato da alcune strategie di selezione che utilizzano i valori della fitness per valutare se un individuo debba sopravvivere e contribuire alla popolazione successiva o meno.
Poiché si vuol in genere mantenere una certa diversità genetica, non sempre i cromosomi peggiori devono essere eliminati subito dalla popolazione [4]; ciò deriva dal fatto che, sebbene la funzione di fitness non sia buona, per tali individui è possibile che qualche gene sia invece quello ottimo per la soluzione cercata.
Vengono ora illustrate alcune delle più comuni tecniche di selezione.
1.3.1 Decimazione di popolazione
Tale tecnica consiste nell’ ordinare gli individui dal più alto al più basso valore di fitness, si sceglie un punto di cut-off e tutti gli individui con fitness minore del valore di taglio vengono eliminati; i rimanenti sopravvissuti danno origine alla successiva popolazione mediante crossover. Il vantaggio della tecnica appena esposta è nello stabilire semplicemente quali individui possono non essere eliminati; inoltre il metodo di riaccoppiamento è del tutto casuale.
L’inconveniente risiede nel fatto che, con l’eliminazione di alcuni individui, è possibile perdere caratteristiche uniche ad essi associate che mostrerebbero i relativi effetti benefici dopo molti cicli del processo evolutivo. A tale inconveniente si può rimediare introducendo l’operatore di mutazione che apporta nuovo materiale genetico e consente l’esplorazione di più vaste porzioni del dominio di soluzione.
L’azione del GA è quindi quella di combinare individui con buone caratteristiche per cercarne di migliori sebbene non sempre questi abbiano fitness più elevata almeno nei primi stadi.
1.3.2 Selezione proporzionata
È la più popolare strategia di tipo stocastico utilizzata, gli individui sono scelti in base alla loro probabilità di essere selezionati data da:
Psel = F genitore( i)
genitore
Dove F(.) è il valore della funzione di fitness riferita al genitore i-esimo; più la probabilità di selezione Psel è elevata, maggiore è la probabilità che individui con alta fitness partecipino alle generazioni future, tuttavia è comunque possibile che individui con basse fitness sopravvivano alla selezione.
Un comune metodo di rappresentazione della tecnica appena presentata consiste in una ruota che gira divisa in spicchi: più è alta la probabilità di selezione, più grande è lo spicchio, un puntatore fisso punta l’individuo che è contenuto nello spicchio indicato e che quindi passa la selezione [4].
Per maggior chiarezza si faccia riferimento ala figura 1.1
8 % 10 % 12 % 14 % 16 % 18 % 22 %
Figura 1.1: Rappresentazione della selezione proporzionale
1.3.3 Selezione per torneo
La selezione per torneo è tra le tecniche più diffuse; da una popolazione iniziale si estraggono casualmente N individui che costituiscono una sottopopolazione; fra questi quello con fitness più alta vince e viene selezionato per generare la nuova, gli altri sono reinseriti nella popolazione d’origine dalla quale vengono estratti nuovamente N elementi, di solito N vale 2.
Il vantaggio della selezione per torneo è che non solo offre una convergenza migliore alla soluzione ottima, ma lo fa anche nel modo più veloce possibile poiché proporzionale in complessità a N (la selezione proporzionale trattata nel precedente paragrafo cresce in complessità come N2 [4]).
1.4 Operatori degli algoritmi genetici
Una volta ottenuta una coppia di genitori, questi sono in grado di creare individui della futura generazione tramite operazioni di crossover e mutazione.
1.4.1 Crossover
Uno dei più semplici operatori di questo tipo è il crossover di tipo single point che viene usato con una probabilità che va dal 60% al 90%. Il motivo per cui è così frequente il suo utilizzo sta nel fatto che non solo velocizza la convergenza, ma consente anche di mantenere le caratteristiche uniche di alcuni geni nelle generazioni successive.
Se avviene il crossover, dati due genitori A e B, in ognuno di essi si sceglie casualmente uno stesso punto di taglio del cromosoma in modo tale che i geni rimangano integri e si copia nel figlio A la prima parte del cromosoma del genitore A quindi la seconda del genitore B; analogamente il figlio B erediterà la prima parte dal genitore B la seconda da quello A (per maggior chiarezza si faccia riferimento alla figura 1.2).
GENITORE A GENITORE B
1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1
1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0
Figura 1.2: Rappresentazione del crossover di tipo single point
Quando non avviene il crossover, i cromosomi vengono copiati così come sono nei figli dai rispettivi genitori dando luogo ad una copia degli stessi nella generazione attuale.
Naturalmente tale tecnica può essere applicata anche in più punti (crossover di tipo multipoint) con la stessa procedura; infine un’astrazione del multipunto è il crossover di
tipo uniforme: si parte da due genitori e una maschera generata casualmente con cui si decide quali geni tenere nei figli a partire da quelli dei genitori, ad esempio come mostrato in figura 1.3 ciascun figlio riceve dal padre i bit in corrispondenza degli 1 della maschera [4]. GENITORE A GENITORE B 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 MASCHERA 0 0 1 1 0 1 0 1 1 0 FIGLIO A FIGLIO B 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0
Figura 1.3: Rappresentazione del crossover uniforme
1.4.2 Mutazione
Come accennato precedentemente questo operatore consente di esplorare spazi di soluzione che non sono rappresentati nell’assetto genetico della popolazione corrente. In altri termini, l’operatore di mutazione consente di sconfinare al di là della soluzione individuata dal genoma della popolazione corrente. Viene anch’esso applicato con una certa probabilità di mutazione Pmut che assume indicativamente valori tra 0.01 e 0.3; è opportuno che questo valore rimanga piuttosto basso per evitare che troppe mutazioni eliminino geni forti e facciano allontanare la soluzione dall’eventuale massimo [4].
L’operatore di mutazione semplicemente modifica uno o più alleli di un cromosoma in modo del tutto casuale; ad esempio se si usa una codifica binaria, gli zeri vengono trasformati un uno e viceversa.
1.4.3 La funzione di Fitness
La funzione di fitness associa ad ogni individuo un valore che misura il suo grado di vicinanza ad un massimo ottimo; essa è definita positiva e spesso l’algoritmo genetico fornisce il suo massimo. Se il problema richiedesse invece la ricerca del minimo, si può semplicemente invertire il segno della funzione di fitness e eventualmente traslarla per avere ancora valori maggiori di zero laddove nella trasformazione si sia perduta tale caratteristica [4].
1.5 Estensioni di un semplice GA
1.5.1 Elitismo
L’elitismo è la migliore estensione di un algoritmo genetico; esso consente di migliorare le generazioni successive osservando e prelevando cromosomi nelle precedenti; nell’elitismo semplice il miglior individuo alla k-esima generazione viene mantenuto nella successiva k+1-esima se presenta fitness maggiore del figlio, la popolazione conterrà così un maggior numero di individui; nell’elitismo globale il padre sostituisce il figlio e la popolazione non cresce [4], [5].
1.5.2 Steady-state GA
Questo tipo di algoritmo genetico prevede non la completa sostituzione delle generazioni, ma la possibile sovrapposizione di esse con il vantaggio di una maggior velocità di convergenza in molte applicazioni; una variante a tale algoritmo prevede di aggiungere la nuova alla vecchia popolazione ottenendone una che, almeno temporaneamente, è doppia quindi si passa all’eliminazione di individui per mantenere la stessa dimensione con criteri che fanno capo ai concetti di selezione visti precedentemente.
Sebbene l’uso dell’elitismo consenta di avere delle generazioni sempre migliori poiché vengono rimpiazzati cromosomi con quelli di altre, una grave conseguenza è nell’omogenizzazione delle caratteristiche di ogni individuo. In altre parole i valori di fitness sono molto simili per ogni elemento della popolazione e spesso la condizione di stallo che si raggiunge corrisponde ad una soluzione che, sebbene sia buona, non è quella ottima [4].
1.5.3 Il problema del commesso viaggiatore
Alcune comuni problematiche possono essere risolte mediante la modifica di crossover e mutazione, il problema del commesso viaggiatore, (Traveling Salesman Problem-TSP) che deve attraversare tutte le città una sola volta e tornare indietro per il percorso più breve, è una di esse.
Dal punto di vista fisico ciò si presenta sottoforma di disposizione di circuiti e reti wireless, la cui posizione ottima può essere trovata con l’aiuto del GA a crossover modificato o parzialmente adattato. In tal caso non tutta la porzione di cromosoma che segue il punto scelto è sostituita nel figlio, ma solo una parte di essa, si applica infine una mutazione modificata intesa come permutazione di due elementi scelti casualmente [4].
