• Non ci sono risultati.

CAPITOLO 1

N/A
N/A
Protected

Academic year: 2021

Condividi "CAPITOLO 1"

Copied!
9
0
0

Testo completo

(1)

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.

(2)

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;

(3)

• 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.

(4)

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

(5)

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]).

(6)

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

(7)

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.

(8)

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.

(9)

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].

Figura

Tabella 1: Concetti principali che fanno capo alla teoria degli algoritmi genetici
Figura 1.1: Rappresentazione della selezione proporzionale
Figura 1.2: Rappresentazione del crossover di tipo single point

Riferimenti

Documenti correlati

Uno studente ` e sicuro di aver risposto correttamente a 5 domande del test di recupero, ma vuole superare la prova con almeno 8 punti.. Quale delle seguenti condizioni sulle

Un’altro tipo di selezione è la cosiddetta “Selezione per Torneo”: in tal caso, una sottopopolazione di N elementi viene scelta casualmente all’interno della generazione

 Decodifica degli individui: si visitano le città nell’ordine definito dal cromosoma, ottenendo la fitness come 1/(costo totale).  Popolazione iniziale: si generano casualmente

Fan da tutto il mondo seguono Andrea Bocelli, al concerto- evento presso il suo Teatro del Silenzio, a Lajatico 4.1. Andrea Bocelli: storia di un tenore lajatichino che ha

Nel romanzo viene usato in prevalenza dai bianchi come insulto razzista verso gli italiani, ed esempio nella scena del quarto capitolo dove Serafin e Lazzaro sono

L'offerta sottoscritta dal proprietario dell’immobile, corredata della documentazione appresso indicata, dovrà essere contenuta in un plico, sigillato e controfirmato sui lembi

Progettazione della stalla e comportamento degli animali 5.4.4. Tipologia d’impianto e

Condizioni patologiche quale emergono da un flusso di sopravvenienza che ha raggiunto punte di 55.000 ricorsi all’anno, con aumenti di ricorsi iscritti di oltre