Algoritmi genetici per l'ottimizzazione ed il controllo dell'uso di energia elettrica

2. AlgoritmiGenetici
2.1 GlialgoritmiGenetici
2.1.1 DeVnizione
Un algoritmo genetico (comunemente chiamato GA) può essere deVnito come un metodo
euristico ed adattativo di ricerca, i suoi obiettivi sono quelli di trovare soluzioni vere o ap-
prossimative di ottimizzazione e ricerca di un problema. Gli algoritmi genetici sono ispirati
al principio della selezione naturale di Charles Darwin, che regola l’evoluzione biologica
secondoiprincipidellagenetica.
2.1.2 Storia
Lostudioelasimulazionedell’evoluzionebiologicatramitecomputerhainizionel1950,dopo
15annidiricercheRechenberg(1965,1973)introdusseilconcettodievoluzionestrategica,che
fù poi espanso grazie all’apporto di Schwefel (1975, 1977). I loro studi portarono tre studiosi
del periodo, Fogel, Owen e Walsh (1966) a sviluppare la prima tecnica di programmazione
evolutiva, anch’essa ispirata all’evoluzione naturale, ma non alla genetica. Durante questi
annimoltialtriscenziatihannolavoratosutematichequalil’apprendimentoautomaticoegli
algoritmi ispirati dall’evoluzione, tra di questi possiamo trovare Box (1957), Friedman (1959),
Bledose(1961),Bremermann(1962)eReed,ToomseBarricelli(1967). [7]Inognicasoilpadre
deglialgoritmigenetici(GA)èstatosicuramenteJohnHolland,cheliinventònel1960elisvi-
luppò nel corso degli anni insieme ad un gruppo di studenti e colleghiVno allaVne del 1970.
Laricercasuquestotipidialgoritmi,inognimodo,rimaseunostudioteoricoVnoametàdegli
anni ottanta, quando ci fù la prima conferenza internazionale sugli algoritmi genetici, David
Goldberg,fedelestudentediHolland,diedeuncontributonotevoleall’aUermazionediquesto
nuovo metodo, che viene tuttora usato in ambito informatico, ingegneristico, Vnanziario ed
ovviamente nel campo delle scienze sociali e naturali. L’obiettivo origiario di Holland, non
era quello di trovare soluzioni a speciVci problemi, piuttosto voleva studiare formalmente il
fenomeno dell’adattamento così come avviene in natura cercando di importarlo nei sistemi
informatici. Holland spiega come passare da una popolazione iniziale di cromosomi ad una
nuova, più adatta all’ambiente in cui risiede, usando un meccanismo di selezione naturale e
deglioperatorigeneticidicrossover,mutazioneedinversione.
2.1.3 ApplicazionideiGA
Gli algoritmi genetici possono trovare applicazione in un gran numero di ambienti, esempi
più comuni si possono trovare, in informatica, in ingegneria, in economia, nella chimica,
nella Vsica, nella matematica e nella statistica. Solitamente il loro utilizzo è Vnalizzato al
raggiungimentodiunodeiseguentiobiettivi
Gli algoritmi Genetici
 ottimizzazione e miglioramento delle prestazioni di un sistema, come ad esempio la
gestionedeisemafori,loscheduling,ottimizzazionicombinatorieetc..
 test e adattamento di modelli quantitativi, che consiste nel ricercare i parametri che
minimizzino la diUerenza tra un modello di dati ed i dati stessi su cui esso è costruito.
(Unesempiopuòessereilproblemadelprocessamentodelleimmagini.)
La distinzione tra queste due aree è potenzialmente la diUerenza che intercorre tra la ricerca
diunmassimoodiun minimodiundeterminatoproblema. ComenototalediUerenzarima-
ne solo una diUerente strada per raggiungere lo stesso obiettivo, in quanto la ricerca di un
massimo,puòesserefacilmentetradottanellaricercadiunminimo,eviceversa.
A diUerenza di metodi di ottimizzazione ed algoritmi che risolvono in tempi polinomiali o
lineari, gli algoritmi genetici operano in quei campi dove non vi è modo di conoscere a prio-
ri quanto l’algoritmo riesca ad avvicinarsi all’ottimo ricercato. Voler risolvere un problema,
di solito equivale a ricercare la migliore soluzione possibile. Lo spazio di tutte le soluzio-
ni possibili viene chiamato spazio di ricerca, ogni punto in questo spazio rappresenta una
soluzione fattibile. Ogni possibile soluzione può essere marcata dal suo valore di idoneità
verso il problema che stiamo aUrontando. La ricerca di una soluzione, in questo caso, è pari
dunque alla ricerca di un qualche estremo (minimo o massimo) nello spazio di ricerca. Lo
spazio di ricerca può essere esplorato completamente durante la ricerca della soluzione, ma
solitamente, si conoscono dei punti validi come possibili soluzioni e da essi se ne generano
altri avvicinandosi così, man mano, alla soluzione ottima. Il problema risulta essere che la
ricerca potrebbe complicarsi se non si è a conoscenza di dove cercare la soluzione e come
cominciare. A questo scopo nascono gli algoritmi genetici ed anche altri algoritmi che non
verranno trattati in questo contesto; in ogni modo le soluzioni trovate tramite questi metodi
vengono spesso considerate come buone soluzioni, proprio perchè non è possibile deVnire
qualesiailveroeproprioottimo.
Un esempio di problemi, che non possono essere risolti in modo tradizionale, sono i pro-
blemiNP.Davantiamoltiproblemi,siriesceadidentiVcareprestodeglialgoritmipolinomiali
ingradodirisolverli,cisonoaltriproblemiche,invece,nonpossonoessererisolvibilitramite
questi algoritmi, proprio perchè non sono risolvibili in tempo polinomiale. C’è una parti-
colare classe di problemi, inoltre, dove è diXcile trovare un metodo di risoluzione, ma se
qualcuno ci presentasse la sua soluzione, saremmo capaci di veriVcare la sua validità, questo
tipo di problemi rientrano nell’insieme dei problemi NP-completi. NP signiVca non polino-
miale, non deterministico, questo vale a dire che pur non avendo metodi di risoluzione in
tempi polinomiali, è possibile indovinare la soluzione e quindi controllare, in tempo polino-
miale la sua validità e se avessimo una macchina in grado di indovinare, saremmo quindi in
possessodellasoluzioneintemporagionevole. LostudiodeiproblemiNP-completipersem-
plicità è limitato ai problemi, dove la risposta è piuttosto semplice, gli altri, in cui le uscite
sono più complicate sono racchiusi dentro l’insieme dei problemi NP-hard. I problemi non
polinomiali potrebbero avere metodi di risoluzione anche piuttosto semplici, una di queste
potrebbeesserecercaretuttelepossibilisoluzioni,mal’algoritmochenederivarisultaessere
piuttosto lento con complessità diO(2
n
) . Oggi nessuno sà se esiste qualche algoritmo più
veloce, in ogni caso dimostrare o confutare questa ipotesi rimane una delle sVde principali
dellamatematicaedellalogicacontemporanea. Moltistudiosipensanochetalialgoritminon
esistano e sono alla ricerca di metodi alternativi, come ad esempio potrebbero risultare gli
algoritmigenetici.
Verrannoorapresentatiunaseriediproblemiclassicilogiciematematicirisolvibilitramite
l’applicazione,appunto,deglialgoritmigenetici.
8
Gli algoritmi Genetici
Il problema del commesso viaggiatore Il problema del commesso viaggiatore è uno dei
problemi classici che possono essere risolti utilizzando un algoritmo genetico. Riguarda un
commesso viaggiatore che deve visitare ogni città in una data mappa, prima di tornare al
punto di partenza. Il problema richiede che il percorso aUrontato sia il più economico in
termini di distanza, cioè un percorso chiuso che passa attraverso ciascun nodo nel grafo e
il cui costo totale sia minimo. Le sue varianti sono il disegno di linee telefoniche e circuiti
integrati, o la programmazione di robot industriali. In tutte queste applicazioni la capacità
ditrovareunpercorsoeconomiconelgrafoinquestionepotrebbeessereabbastanzacruciale.
Tale problema è un problemaNPC ovvero Non-deterministico Polinomiale a tempo completo
che è in pratica irrisolvibile con un algoritmo lineare standard se la complessità è elevata.
Nel caso di situazioni a grande complessita l’applicazione di un GA risulta essere una buona
alternativa.
Ilproblemadellozaino Unaltroproblemamoltoconosciutoenelqualesonostatiapplicati
con successo gli algoritmi genetici è il problema dello zaino. Nel problema classico, dato
uno zaino di capacità C e n oggetti ciascuno dei quali ha un peso w
i
e proVtto p
i
, si deve
cercare di riempire lo zaino con gli oggetti che danno il massimo proVtto con il vincolo di
nonsuperarelasuacapacità. Cioccuperemoquìdiunasuageneralizzazioneovverodovremo
rempirem zaini di capacitac
1
;c
2
::c
m
en oggetti ciascuno di quali ha un proVtop
i
. Nella
versione classica ciascun peso è preVssato, quì il peso dell’i-esimo oggetto prende j valori
con1<j <m. L’i-esimo oggetto pesaw
ij
quando è candidato ad entrare nel j-esimo zaino
di capacitàc
j
. Questo equivale a cercare un vettore dix componenti che rispetti il vincolo
dellecapacità:
S
i
w
ij
x
j
<C
j
;i=1:::n;j =1:::m
e che massimizzi il proVttoP(c) =S
i
x
i
p
i
. Possiamo pensare che sia un problema di alloca-
zione di risorse dove abbiamon risorse en oggetti. Ciascuna risorsa ha un proprio budget
e w
ij
rappresenta il consumo della risorsa j da parte dell’oggetto i. Si deve ovviamente
massimizzareilproVttolavorandoall’internodiuncertobudget. Lafunzioneottimadunque
risulterebbeessereunvettoreammissibilechedàilmassimoproVtto,cioèunvettorechemas-
simizza la funzione obiettivoP(c) =S
i
x
i
p
i
Il problema dovrà venire ovviamente codiVcato
peressererisoltotramiteunalgoritmogeneticomanonèinteressediquestostudio.
Per illustrare le reali capacità di applicazione degli Algoritmi Genetici vengono elencate
diverse possibili implementazioni, alcune sono state eUettivamente sviluppate e sono attual-
menteinuso,altresonomaterialediricerca.
 Ottimizzazione di funzioni numeriche Molta della ricerca fatta sui GA cade proprio
in questo settore, nello speciVco viene usato su funzioni complicate, discontinue e
disturbate.
 Processamento delle immagini Usato ad esempio nelle immagini mediche a raggi X
o da satellite, dove c’è spesso bisogno di allineare due immagini della stessa area
tra di loro, prese in istanti diversi. Comparando un campione casuale di punte nelle
due immagini, un GA può eXcacemente trovare un insieme di equazioni per adattare
un’immaginedentrol’altra.
 Ottimizzazionecombinatoriarichiedesoluzioniaproblemicheriguardanodisposizio-
nedioggetti,ilproblemapiùstudiatoèil problema del commesso viaggiatore.
 Bin packing ovvero, come disporre un certo numero di oggetti in uno spazio limitato,
haapplicazioninell’industria. UnesempioèillayoutdeicircuitiintegratiVLSI.Posso-
norientrareinquestaareaancheil job shop schedulingoil time tablingdovesidevono
9
Gli algoritmi Genetici
allocare un insieme di risorse, costituite da macchine, uomini, stanze, per portare a
termineuninsiemedicompiti.
 MachinelearningCisonomolteapplicazionipersistemidiapprendimento,ilmodello
usuale è quello del sistema classiVcatore. Il GA prova ad evolvere, imparando come
comportarsiindeterminatecasistiche. Questoèstatoapplicatoaigiochieperrisolvere
labirinti e anche per modelli economici e statistici. Una delle sue applicazioni è nel
campodelcontrollo,dovesielaboranoregolepercontrollareunsistema. Fogartyèstato
il primo ad usare tale metodo per elaborare regole per controllare il miglior rapporto
tra gas ed aria in una fornace. Goldberg ha modellato un sistema che permette di
controllare rapporti di compressione e perdite su di una rete di gas. Davis e Coombs
hanno usato tali tecnologie invece per una rete di telecomunicazione... In sostanza
questocamposembraessereilpiùVorente.
2.1.4 Successivisviluppidopoglialgoritmigenetici
Lo studio sugli algoritmi genetici è stato uno dei tanti studi eUettuati nel campo dell’intel-
ligenza artiVciale, ognuno di questi studi si può dire però, che ha contribuito all’evoluzione
degli altri, in particolare lo studio sugli algoritmi genetici ha contribuito allo sviluppo di
diversearee.
Programmazioneevolutiva nascecomeapproccioall’intelligenzaartiVciale,alternativori-
spetto alle tecniche basate sul ragionamento simbolico. Il suo scopo è quello di far evolvere,
piuttostochedeVnireapriori,comportamentiintelligenti,rappresentatipermezzodiautomi
astatiVniti. Nellaprogrammazioneevolutiva,quindi,ilproblemaoggettodeterminal’alfabe-
tod’ingressoediuscitadiunafamigliadiautomiastatiVniti,egliindividuisonoopportune
rappresentazionidiautomiastatiVniticheoperanosutalialfabeti. LadeVnizionedegliope-
ratori di mutazione e crossover, è leggermente più complessa che nel caso degli algoritmi
genticiinquantodevetenerecontodellastrutturadeglioggettichetalioperatoridevonoma-
nipolare. La Vtness di un individuo può essere calcolata mettendo alla prova su un insieme
di casi del problema l’automa che esso rappresenta: per esempio, se si desidera far evolvere
individui capaci di modellare una serie storica, si selezioneranno un certo numero di pezzi
della serie passata, li si daranno in ingresso a un individuo e se ne osserveranno i simboli
prodotti, interpretandoli come previsioni e confrontandoli con i dati eUettivi per misurarne
l’accuratezza.
Programmazione genetica Un altro metodo, nato direttamente dallo studio sugli algorit-
mi genetici, è appunto la programmazione genetica, che riguarda la generazione automati-
ca di programmi a partire da una descrizione ad alto livello del processo da svolgere. La
programmazione genetica è sostanzialmente un estensione di un algoritmo genetico dove la
popolazione risulta composta da un numero opportuno di programmi, i quali mediante le
operazioni genetiche, si riproducono e cambiano parzialmente portando il programma, dopo
un certo numero di generazioni, a risolvere al meglio il problema assegnato. I programmi
creati con tale tecnologia possono essere scritti in molti linguaggi di programmazione, dap-
primasiutlizzavanostruttureadalberoquindisipreferival’usodilinguaggicheutilizzavano
questestrutturecomeadesempioLisp,poiconl’arrivodialcuniprogrammicommercialisiè
esteso l’uso a linguaggi più popolariVno all’assembly. Negli anni novanta, il suo sviluppo è
stato piuttosto lento perchè la programmazione genetica richiedva in quanto tale una note-
volecapacitàdicomputazione,poineiprimianniduemila,conlenoteleggidiMoorelaGPha
10
Principi di funzionamento degli algoritmi genetici
cominciato a fornire risultati migliori tanto da aver avuto un formidabile sviluppo nel corso
diquestiultimianni.
2.1.5 Confrontoconaltretecniche
Gli algoritmi genetici non sono gli unici ad avere un approccio orientato alla risoluzione di
problemi di ricerca e di ottimizzazione. Ci sono ottime tecniche di ottimizzazione, alcune di
essesonoapplicabiliperòsoloadominilimitati,inquestasezioneseneillustreràalcune.
 Ricerca Casuale E’ un approccio basato sulla forza bruta che ricerca casualmente o
in maniera enumerata la funzione. Consiste nel calcolare tutte le possibili soluzioni,
questometodoèpocointelligenteedisolito,nelpossibile,vieneevitato.
 Metodo del gradiente Utile quando si studia funzioni continue, si basa sull’uso delle
informazionisulgradientedellafunzioneperricercarelesoluzioni. Sostanzialmentesi
deriva la funzione (se è possibile farlo) e si ricerca il punto dove la funzione raggiunge
il massimo con un metodo detto hillclimbing, ovvero scalata. Questo metodo è buono
per funzioni che hanno un solo picco, ma per funzioni che hanno molti picchi è meno
eXcace proprio perchè la ricerca si arresta alla raggiunta del primo picco individuato,
fermandosiquindisuunottimolocaleenonglobale.
 Ricerca Iterata E’ un pò l’unione delle due tecniche enunciate sopra, ovvero viene
usato il metodo del gradiente per raggiungere un picco, poi ci si sposta nella funzione
ricercandounaltropuntocasuale.
Aquestimetodiseneaggiungonoaltriderivatidaquesticonpiccolemigliorieapportateper
farsìchenonsiarrestinoinunasoluzionediottimolocale.
2.2 Principidifunzionamentodeglialgoritmigenetici
Un algoritmo genetico tipicamente parte da un insieme di possilbili soluzioni chiamato po-
polazione e provvede a far evolvere tale popolazione ad ogni iterazione, selezionando alcuni
tra gli individui della posizione corrente prendendoli come modello per la nascita di altri in-
dividui,cheandrannoasostituirsiadunparinumerod’inviduigiàpresenti,costituendocosì,
una nuova popolazione soggetta ad un iterazione seguente. Ad ogni iterazione la generazio-
ne evolve verso l’ottimo locale o globale ricercato. Tale evoluzione viene ottenuta attraverso
una parziale ricombinazione delle soluzioni, ogni indiviudo trasmette parte del suo geno-
ma ai propri discendendenti, che sono composti in parte dal genoma dei propri genitori ed
in parte da genoma introdotto da mutazioni casuali nella popolazione di partenza che com-
portano occasionalmente la nascita di individui con caratteristiche non comprese tra quelle
presentinelcorredogeneticodellaspecieorigianaria. Adogniiterazionelapopolazionedelle
soluzioni viene analizzata e viene tenuta solo quella parte che risulta essersi meglio adatta-
ta all’ambiene circostante, ovvero quella parte che è riuscita meglio a risolvere il problema,
tale popolazione funzionerà da base per la popolazione successiva, mentre gli individui de-
boli saranno sostitutiti. Un algoritmo genetico quindi rimpiazza la popolazione con un’altra,
ottenutatramite:
 selezione
 crossover
11
Principi di funzionamento degli algoritmi genetici
 operatoridimutamento
Si cercherà ora di fare chiarezza sui vari principi illustrati e su come questi trovino una
corrispondenza tra il mondo della biologia, dal quale nascono, e quello dell’informatica dove
sarannoapplicatinelnostrocasodistudio.
2.2.1 IgenomineiGA
Lo spazio di ricerca degli algoritmi genetici, ad ogni istanza, è riferito al genoma ed ai suoi
elementichevengonochiamatigenotipi. Igenotipiinnaturarappresentanol’interobagaglio
ereditario che un organismo mantiene codiVcato nel proprio DNA. Il DNA è una stringa di
coppie base che codiVca le caratteristiche fenotipiche della creatura a cui appartiene. Come
i loro prototipi naturali,i genomi degli algoritmi genetici sono stringhe, sequenze lineari di
dati. A causa della struttura lineare, questi genotipi sono anche spesso chiamati cromosomi.
Nell’ambitodeglialgoritmigeneticisiusaparlarediuncromosomacomestringhediunsolo
tipo di dato, ad esempio bit o numeri reali. Un cromosoma può essere una tupla a lunghezza
Vssa o variabile, nel primo caso gli indici dei geni rimangono costanti e le tuple possono
contenereelementiprovenientidasoluzionidiUerenti.
G=8(g[1];g[2];:::;g[n]):g[i]2G8i21::n
Nel secondo caso i geni potrebbero subire uno shift quando vengono eUettuate le operazioni
diriproduzione,quindituttiglielementidiungenotipodevonoaverelastessotipoG
T
G=8listsg :g[i]2G
T
80 i<len(g)
I cromosomi vengono normalmente rappresentati tramite una stringa di bit, un vettore di
interiodinumerireali. Glialgoritmigeneticiconvettorinumericinellaloronaturalerappre-
sentazionevengonochiamatireal-encoded. Icromosomirappresentatidastringhedibitsono
spessocompletaticonl’applicazionedelcodicegraydurantelamappaturagenotipo-fenotipo.
Questo viene fatto nel tentativo di rappresentare la località e far sì che i piccoli cambiamenti
nel genotipo possano essere conseguenza di piccoli cambiamenti anche nel fenotipo. Gli al-
goritmi genetici sono prototipi di algoritmi evolutivi, come tali, aderiscono pienamente alle
caratteristicheditalimetodi. Icritericoncuiavvienelaricercarispecchianoiregimidiripro-
duzione sessuata ed asessuata presenti in natura. Nella riproduzione sessuata i due genotipi
dei genitori si ricombinano creando un nuovo genotipo, in quella asessuata la riproduzione
avveneesclusivamentemediantemutazione. Nellateoriadeglialgoritmigeneticièmoltoco-
mune combinare i due fenomeni combinando prima i due genotipi dei genitori provvedendo
poi alla mutazione. Un piccolo studio in merito mi ha insegnato che in natura la vita co-
mincia con una singola cellula che, mutando, si divide di volta in volta Vno a quando non
si forma un individuo maturo, ovvero pronto a riprodursi. Questo comporta la creazione di
un fenotipo dalla rappresentazione genotipica ed in biologia questo processo viene chiama-
to chiamato embriogenesi, in ambito informatico tale fenomeno viene rappresentato dalla
mappaturagenotipo-fenotipo.
2.2.2 LafunzionediVtness
L’operatore di selezione necessita di un metodo di valutazione della popolazione corrente.
Questa valutazione viene eUettuata dalla funzione di Vtness, che assegna ad ogni cromoso-
ma della popolazione un punteggio, un valore di Vtness. Questo valore dipende da come il
particolare cromosoma risolve il problema in oggetto; potrebbe essere rappresentato da una
12
Principi di funzionamento degli algoritmi genetici
funzionematematica,daunesperimentoodaunasempliceconfrontotralafunzioneottimae
quellacontenutanelcromosoma. Nell’ipotesicheilcromosomavengaimplementatotramite
una stringa di bit ad esempio, potremmo fare un confronto bit a bit tra la stringa desiderata
elastringa risiedente nelcromosomaedattribuireunvalorerispettoaquestoconfronto. In-
siemealloschemadicodiceusato,lafunzionediVtnessèl’aspettocrucialediognialgoritmo
genetico. La funzione diVtness dorebbe risultare idealmente piatta e regolare, così che i cro-
mosomiconVtnessragionevolesianoviciniaicromosomiconVtnesssleggermentemigliore.
Per molti problemi di interesse, purtroppo, non è possibile costruirla con questo andamen-
to, inoltre perché i GA funzionino bene dovremmo trovare il modo per costruire funzioni
Vtness che attribuiscono valori che non abbiano troppi massimi locali e troppo isolati. In
generale la regola per la costruzione della funzione di Vtness, è che essa dovrebbe riWettere
il valore reale del cromosoma in qualche maniera. Come detto sopra, per molti problemi, la
costruzionepuòesereunpassoovvio,adesempioincerticasibastacalcolareilvalorediogni
cromosoma. Mailvalorerealediuncromosoma,nonsempreèunaquanitàutileperguidarci
nella ricerca genetica. In problemi di ottimizzazione combinatoria, ad esempio, ci sono molti
vincoli; molti punti nello spazio rappresentano cromosomi non validi. Secondo alcuni è più
utileconsiderarequantivincolisonoviolatipiuttostochequantisonosoddisfatti.
Problemi di Fitness Range Durante le prime generazioni generate da un GA i valori di
Vtness per ciascun gene sono casualmente distribuiti. Con l’avanzare delle generazioni par-
ticolari valori per ogni gene cominciano a predominare, mentre la popolazione converge, il
rangedelVtnesssiriduce. LavariazionenelrangedelVtnessspessoportaaproblemidicon-
vergenza prematura oVne lenta. Il problema della convergenza prematura è un problema
in cui pochi individui con un Vtness alto (ma non ottimale) possono rapidamente dominare
la popolazione, causando la convergenza della soluzione ad un massimo locale. In seguito
poi vedremo come con la mutazione si riesce parzialmente ad evitare questo problema. La
Vne lenta invece è un pò il problema opposto, cioè è quella situazione in cui, dopo molte
generazioni, la popolazione sarà convergente ma non avrà localizzato precisamente il mas-
simo locale. Il Vtness medio sarà alto, ma ci sarà poca diUerenza tra la media ed il migliori
individuo.
2.2.3 Selezione
Questoperatoreselezionaicromosomiperlariproduzione. L’ideadibaseèpiuttostosempli-
ce,infattilaselezioneèstrettamentelegataalvalorediVtnessassociatoaciascuncromosoma.
Più il valore di Vtness è alto, più alta è la probabilità che tale cromosoma sia candidato alla
riproduzione. Cisonovarimetodidiselezionedeimiglioricromosomi:
 Roulette wheel selection: (selezione proporzionale): il suo funzionamento è simile ad
una roulette dove ogni individuo della popolazione occupa uno spazio proporzionale
al suo valore diVtness (più alto è il valore di Vtness, più largo è lo spazio associato al
cromosoma quindi più alta è anche la probabilità che venga scelto). Questo può essere
simulatoconilseguentealgoritmo:
1. SicalcolalasommadituttiivaloridiVtnessdeicromosomi
2. Si genera un numero casuale compreso tra zero e la somma calcolata al passo
precedente
3. Si scorre uno ad uno tutti i numeri Vno ad arrivare al numero casuale generato,
quindicisiferma
13
Principi di funzionamento degli algoritmi genetici
Figura2.1: Roulettewheelselection
Questo metodo incontra dei problemi quando il valore di Vtness tra i cromosomi dif-
ferisce di molto. Per esempio, se il valore diVtness di un cromosoma occupa il 90% di
tuttalaroulette,glialtricromosomihannobassepossibiltàdiessereselezionati.
 Rank selecion: La rank selection prima crea una classiVca della popolazione, poi ogni
cromosomariceveunvalorediVtnesssecondolasuaposizioneinclassiVca. Ilpeggiore
ha valore diVtness uno, il penultimo due etc, il primo classiVcato avrà valore N con n
somma dei cromosomi presenti nella popolazione. Con questo modo ogni cromosoma
hapossibilitàdiesserescelto,adiscapitodellabassaconvergenza.
 TournamentSelection: questo metodo di selezione preleva casualmente una coppia di
individui e seleziona tra i due quello candidato per la riproduzione, ovvero quello con
ilvalorediVtnesspiùalto. Laproceduraselezionasolamenteungenitore,ovviamente,
sideveripeterelaproceduratantevoltequantigenitoriabbiamobisognodiselezionare
 Elitism: L’ideasibasasulfattochequandovienecreataunanuovapopolazionetramite
mutamentoecrossoverabbiamolapossibilitàdiperdereilmigliorcromosoma. Questo
metodoinvececopiaprimailmigliorcromosoma(oimigliori)sullanuovapopolazione,
poiirestantivengonocalcolaticonglialgoritmiclassicisopradescritti. Questometodo
incrementadimoltoleperformancedell’algoritmogenetico,appuntoperchènonperde
perlastradalemigliorisoluzionitrovate.
2.2.4 Crossover
Il crossover è ciò che permette di unire i genotipi dei due genitori ricombinando i geni ot-
tenenendo una vasta gamma di possibili combinazioni. Nella biologia questo meccanismo
consistenelloscambiodiporzioniomologhedimaterialegenetico,chepuòveriVcarsifradue
cromatidiappartenentiacromosomidiversidiunacoppiadiomologhi. Nell’applicazionede-
gli algoritmi genetici questo avviene stabilendo inizialmente un coeXciente, che provvederà
a cambiare alcune parti dei geni risultati migliori, nell’ipotesi che questo possa migliorare il
valorediVtnessnellasuccessivaiterazione. Cisonovarietecnichedicrossingover,unadelle
piùsemplicièla single-point crossover
Single-pointcrossover (Figura2.2)L’operatoresingle-pointcrossoversceglieunpuntoca-
suale su due cromosomi genitori, ciascun cromosoma a questo punto viene tagliato in tale
punto creando così due teste e due code. A questo punto si scambiano le teste e le code
ottenendoduenuoviVgli.
Two-pointcrossover: (Figura2.3)funzionagrossomodocomeilsingle-pointcrossoverma,
invece di fare un solo taglio sul cromosoma, questa tecnica ne fà due, in modo da poter
prenderesingolepartidiognuno.
14