Capitolo 6:
Descrizione dell’ottimizzatore
6.1
Generalità
In questo capitolo, ci occupiamo della ricerca dei coefficienti mediante i quali è possibile ottimizzare la forma della superficie del riflettore utilizzando un algoritmo genetico (GA) (crf. capitolo 2).
Gli algoritmi genetici sono metodi adattativi che possono essere usati per risolvere problemi di ricerca e di ottimizzazione. Gli algoritmi genetici sfruttano alcune analogie con i processi genetici degli organismi biologici. Dopo molte generazioni, le popolazioni si evolvono secondo i principi della selezione naturale e della sopravvivenza del migliore, come teorizzato per la prima volta da Charles Darwin nella sua opera "L'origine delle specie" [13]. Imitando questi processi, gli algoritmi genetici, se opportunamente codificati, possono essere utilizzati per determinare soluzioni di problemi reali.
I principi di base dei GA simulano quei processi che nelle popolazioni naturali sono essenziali per l'evoluzione.
I GA usano una diretta analogia con il comportamento della natura. Lavorano con una popolazione di individui, ciascuno dei quali rappresenta una possibile soluzione del problema posto. Ad ogni individuo è associato un punteggio di adattamento detto "fitness". Tale valore viene assegnato in relazione alla bontà della soluzione del
problema. L’analogia con quello che accade in natura è espressa dalla capacità del singolo individuo di riuscire a competere per la propria sopravvivenza. Gli individui migliori hanno la possibilità di riprodursi incrociandosi con altri individui della popolazione. Questo produce nuovi individui discendenti che condividono alcune caratteristiche di ciascun genitore. Gli individui meno adattati hanno meno probabilità di riprodursi e quindi si estinguono. Una intera nuova popolazione di possibili soluzioni è così prodotta dalla selezione degli individui migliori della generazione corrente che accoppiandosi tra loro producono un nuovo insieme di individui. Questa nuova generazione contiene una proporzione più alta delle caratteristiche possedute dagli individui buoni della precedente generazione. In questo modo dopo molte generazioni le buone caratteristiche vengono propagate a tutta la popolazione, essendo mischiate e scambiate con altre buone caratteristiche.
La potenza degli Algoritmi Genetici è legata alla loro robustezza e alla loro applicabilità in molti settori. I GA non garantiscono di trovare una soluzione ottima per un problema, ma generalmente trovano una soluzione sufficientemente buona e in tempi sufficientemente rapidi.
Con riferimento alla trattazione svolta nei precedenti capitoli ed in particolare nel capitolo 2, possiamo dire che gli individui sono rappresentati dai coefficienti cij per i polinomi rettangolari e per le B-Splines e dai coefficienti (Amn,φmn) nel caso dei polinomi di Zernike. Quindi una possibile soluzione del nostro problema viene rappresentata come un insieme di coefficienti “geni” i quali sono uniti insieme per formare una stringa di valori “cromosoma”, la quale costituisce un individuo della popolazione.
Continuando l’analogia con la genetica possiamo dire che, l’insieme dei parametri rappresentati da un particolare cromosoma è chiamato
genotipo. Il genotipo contiene le informazioni richieste per costruire un
organismo che è chiamato fenotipo.
Il funzionamento degli algoritmi genetici si basa su quattro procedimenti principali:
1) Selezione
La selezione naturale favorisce, attraverso la riproduzione degli individui migliori (cioè quelli con un migliore valore di fitness), quelle particolari combinazioni genetiche che danno vita ad un organismo più efficiente.
2) Crossover
Il crossover è il procedimento mediante il quale viene eseguita una ricombinazione genetica tra due individui, in questo modo ciascuno dei
figli erediterà alcuni geni da entrambi i genitori. 3) Mutazione
Attraverso la mutazione viene alterato in modo casuale (seguendo una distribuzione di probabilità uniforme) ogni gene. L’utilizzo di tale metodo aumenta la probabilità di esplorare un numero maggiore di configurazioni.
4) Elitismo
Quando creiamo una nuova popolazione con crossover e mutazione abbiamo una alta probabilità di perdere il miglior cromosoma della precedente. L’elitismo è un metodo che copia il miglior cromosoma nella nuova popolazione. Questo può far crescere rapidamente le
performance del GA, perché evita la perdita della migliore soluzione trovata.
A seconda di come un cromosoma viene codificato si possono avere algoritmi genetici di tipo:
• binario, nel caso in cui i coefficienti che formano il cromosoma siano codificati in modo binario.
• reale, nel caso in cui i coefficienti che formano il cromosoma non siano codificati.
Negli algoritmi genetici, comunque scelto il tipo di codifica per il cromosoma, svolge un ruolo fondamentale la cosiddetta funzione di
Fitness che serve per giudicare la bontà di ciascun cromosoma rispetto al
problema che si vuole risolvere.
Per maggiori chiarimenti sugli algoritmi genetici e sul loro funzionamento rimandiamo il lettore a [13].
Analizziamo ora come sono stati implementati mediante l’utilizzo dell’algoritmo genetico i tre metodi di deformazione definiti nel capitolo 2.
6.2 Algoritmo genetico mediante polinomi rettangolari
Analizziamo come vengono ottimizzati, mediante l’utilizzo degli algoritmi genetici, i coefficienti di deformazione della superficie descritta mediante polinomi rettangolari .
L’ottimizzazione può essere eseguita, sia utilizzando un algoritmo
6.2.1 Ottimizzazione mediante algoritmo genetico binario
L’ottimizzazione mediante GA binario può essere riassunta mediante il diagramma di flusso di figura 6.1.
Come possiamo notare inizialmente viene generata una “popolazione
iniziale”, per la generazione della quale sono richiesti:
• Il numero Npop di individui di una singola generazione.
• I gradi gmx e gmy del polinomio di deformazione del riflettore. • Il numero Nbit di bit su cui deve essere codificato ogni singolo
coefficiente di deformazione.
• Il range di variabilità (cmin,cmax) all’interno del quale possono variare i coefficienti di deformazione da ottimizzare.
Riassumiamo quanto indicato sopra nella tabella di figura 6.2.
Il singolo individuo di una generazione sarà quindi rappresentato da una matrice di ordine [(gmx+1)x(gmy+1)] di coefficienti appartenenti al range (cmin;cmax).
Una volta nota la popolazione iniziale viene eseguita la prima simulazione, cioè per ogni individuo viene chiamato il simulatore e valutato il diagramma di irradiazione dell’antenna con riflettore deformato.
Noto il diagramma di irradiazione viene calcolato il valore della funzione di fitness facendo un confronto, tra il diagramma di irradiazione richiesto dalle specifiche e quello ottenuto mediante il simulatore.
Se il valore della funzione di fitness supera un valore soglia fissato a priori si decide di continuare il processo di simulazione.
In tal caso occorre generare una nuova popolazione, per fare ciò viene utilizzato il GA e quindi vengono eseguite le fasi di selezione, crossover, mutazione e elitismo.
Nota la nuova popolazione viene eseguita la simulazione, anche in questo caso viene chiamato il simulatore e per ogni nuovo individuo si determina il diagramma di irradiazione e il valore del suo fitness.
Dai valori del fitness ottenuto confrontati con la soglia, si decide come in precedenza se continuare la simulazione.
Quando viene raggiunto un valore del fitness da noi ritenuto soddisfacente per il problema, si termina il processo iterativo di simulazione e vengono resi disponibili i coefficienti di deformazione ottimi.
Come possiamo notare dal diagramma di flusso di figura 6.1 per il calcolo della funzione di fitness sono necessarie delle maschere e dei pesi.
Le maschere rappresentano i diagrammi di irradiazione che sono richiesti dalle specifiche di progetto, mentre i pesi stabiliscono quanto deve essere pesato lo scostamento tra l’andamento richiesto e l’andamento ottenuto durante il confronto per la valutazione della funzione di fitness.
I pesi svolgono un ruolo molto importante nel processo di simulazione. Infatti ad ogni iterazione la funzione di fitness viene aggiornata in relazione al risultato ottenuto e in funzione di un miglioramento del passo successivo.
Più precisamente sia :
Fitness(k)= ik n i k i S, 1 ,
∑
= α (6.1)la funzione di fitness al passo k, dove n indica il numero dei punti
campione, αi ,k è il peso associato all’i-esimo punto campione e Si,k è lo
scostamento in corrispondenza dell’iesimo punto campione.
Allora noti i valori Si,k si decide di aggiornare il valore di αi ,k secondo
il seguente schema: (6.2) S se se 1 , , , 1 , , , , ⎩ ⎨ ⎧ ≥ + < = − − k i k i k k i k i k i k i k i S S S ϑ α α α essendo ϑk >0.
6.2.2 Ottimizzazione mediante algoritmo genetico reale
L’ottimizzazione mediante GA reale può essere implementata in modo analogo al caso binario salvo per alcune modifiche alle fasi di crossover e mutazione. Si veda la tabella in figura 6.2.
6.3 Algoritmo genetico mediante polinomi di Zernike
Analizziamo adesso come vengono ottimizzati, mediante l’utilizzo dei GA, i coefficienti di deformazione della superficie descritta mediante polinomi di Zernike.
Anche in questo caso l’ottimizzazione può essere eseguita sia utilizzando un GA binario che un GA reale.
6.3.1 Ottimizzazione mediante algoritmo genetico
L’ottimizzazione mediante GA può essere riassunta attraverso il
diagramma di flusso di figura 6.1.
Come nel caso dei polinomi rettangolari viene inizialmente generata
una “popolazione iniziale”, per la generazione della quale sono
richiesti:
• Il numero Npop di individui di una singola generazione. • Il numero dei modi Np di Zernike.
• Il range di variabilità (Amin,Amax) all’interno del quale può variare l’ampiezza di ogni singolo modo.
• Il range di variabilità (φmin,φmax) all’interno del quale può variare la fase di ogni singolo modo.
Riassumiamo quanto indicato sopra nella tabella di figura 6.2.
In questo caso il singolo individuo di una generazione è rappresentato da una matrice di ordine [Npx2], dove la generica riga è composta dall’ampiezza Anm e dalla fase φnm di ogni singolo modo (n,m).
A questo punto l’implementazione del GA mediante polinomi di Zernike procede attraverso le fasi descritte nella sezione 6.2.1.
Come indicato nella sezione 6.2.2 anche in questo caso l’ottimizzazione binaria e reale si distinguono unicamente per le fasi di selezione e mutazione per la necessità di fornire come dato di input il numero di bit nel caso di ottimizzazione binaria
6.4 Algoritmo genetico mediante funzioni B-Splines
Infine analizziamo come vengono ottimizzati, sempre mediante l’utilizzo dei GA, i coefficienti di deformazione della superficie descritta mediante funzioni B-Splines.
Come per i casi precedenti l’ottimizzazione può essere eseguita mediante un GA binario oppure mediante un GA reale.
6.4.1 Ottimizzazione mediante algoritmo genetico
L’ottimizzazione mediante GA può essere riassunta attraverso il diagramma di flusso di figura 6.1.
Anche in questo caso viene inizialmente generata una “popolazione
iniziale”, per la generazione della quale sono richiesti:
• Il numero Npop di individui di una singola generazione.
• Il numero di elementi m della partizione dell’intervallo dei parametri.
• Il range di variabilità (cmin,cmax) all’interno del quale possono variare i coefficienti di deformazione da ottimizzare.
Riassumiamo quanto indicato sopra nella tabella 6.2.
Il singolo individuo di una generazione è quindi rappresentato da una matrice di ordine [(m+1)x(m+1)] di coefficienti appartenenti al range (cmin,cmax).
Per le successive fasi dell’ottimizzazione si seguano i passi indicati nella sezione 6.2.1.
Generazione Popolazione Input
Iniziale
Figura 6.1: Diagramma di flusso del GA Generazione Iniziale Selezione Crossover Mutazione Valutazione Fitness Elitismo Simulatore SI Obiettivo Raggiunto Coefficienti Ottimi NO Maschere Pesi NO SI
BINARIO REALE Polinomio rettangolare • Npop • gmx,gmy • Nbit • (cmin,cmax) • Npop • gmx,gmy • (cmin,cmax) Polinomio Zernike • Npop • Np • Nbit • (Amin,Amx) • (φmin,φmax) • Npop • Np • (Amin,Amx) • (φmin,φmax) Funzioni B-Splines • Npop • m • Nbit • (cmin,cmax) • Npop • m • (cmin,cmax)
