Le lingue
Pagine
Legale
UNIVERSITA’ DEGLI STUDI DI TRIESTE
DIPARTIMENTO DI INGEGNERIA E ARCHITETTURA
CORSO DI LAUREA MAGISTRALE IN INGEGNERIA INFORMATICA
TESI DI LAUREA
IN
MODELLI DI OTTIMIZZAZIONE
DEFINIZIONE E SVILUPPO DI UN ALGORITMO
GENETICO MULTIOBIETTIVO PER PROBLEMI DI
PROGRAMMAZIONE LINEARE E OTTIMIZZAZIONE
COMBINATORIA
Relatore Laureando Chiar.mo Prof. Lorenzo Castelli Stefano Costanzo
Correlatore Dott. Alessandro Turco
Anno accademico 2012 – 2013
1
Indice di Tesi:
1. Introduzione ...................................................................................................... 3
2. Definizioni e Concetti fondamentali .............................................................. 7
2.1. Algoritmi Genetici ...................................................................................... 7
2.2. Contesto: Problemi ingegneristici industriali ...................................... 27
3. Analisi della letteratura .................................................................................. 31
4. Progettazione dell’algoritmo ......................................................................... 40
4.1. Insiemi di vincoli lineari .......................................................................... 45
4.2. Variabili intere e binarie .......................................................................... 54
4.3. Permutazioni ............................................................................................. 57
5. Realizzazione dell’algoritmo ......................................................................... 64
5.1. Elimination of Equalities ......................................................................... 64
5.2. Preprocessing ............................................................................................ 66
5.3. GENOCOP III ........................................................................................... 68
5.4. Paradigma a oggetti ................................................................................. 71
5.5. Logica Multi obiettivo ............................................................................. 72
5.6. Fixer per le variabili intere ...................................................................... 74
5.7. Fixer per le Permutazioni ........................................................................ 75
6. Test e risultati .................................................................................................. 78
6.1. Problema vincolato singolo obiettivo .................................................... 80
6.2. Problema multiobiettivo privo di vincoli ............................................. 91
6.3. Problema vincolato multiobiettivo ........................................................ 99
2
6.4. Problema intero singolo e multi obiettivo .......................................... 106
6.5. Problema del commesso viaggiatore singolo obiettivo .................... 111
7. Conclusioni .................................................................................................... 116
8. Bibliografia e Sitografia ................................................................................ 119
3
1. Introduzione
Lo scopo di questo lavoro di tesi è lo sviluppo di un approccio meta-euristico
basato sugli algoritmi genetici per la risoluzione di problemi multiobiettivo
sia di programmazione lineare continua che di ottimizzazione combinatoria.
Inoltre l’intrinseca complessità dovuta alla natura multiobiettivo dei
problemi richiede di spostare l’attenzione dai metodi deterministici
tradizionali a quelli evolutivi euristici. Viene quindi delineato il profilo di un
algoritmo genetico capace di elaborare problemi multiobiettivo con vincoli
lineari, non lineari, variabili intere e binarie. Particolare attenzione viene
dedicata alle fasi precedenti il ciclo di ottimizzazione di un algoritmo
genetico, introducendo delle procedure di semplificazione dei sistemi di
vincoli lineari e un metodo di eliminazione delle uguaglianze, notoriamente
ostiche per gli approcci evolutivi. Risultati sperimentali, su molteplici classi
di problemi test, vengono confrontati con quelli ottenuti da algoritmi genetici
esistenti mostrando dei comportamenti sicuramente incoraggianti per un
raffinamento ulteriore della strategia delineata.
Il presente progetto di tesi è nato da una collaborazione fra il dipartimento di
Ingegneria e Architettura dell’Università degli Studi di Trieste e la società
ESTECO S.p.A.. L’azienda citata opera nel settore della produzione software
e della ricerca e sviluppo sperimentale nel campo dell’ingegneria, ed é
interessata ad uno studio di approfondimento su tematiche inerenti la
programmazione lineare e ottimizzazione combinatoria.
4
Gli obiettivi del presente lavoro di tesi sono:
definizione di una strategia per la costruzione di un algoritmo
euristico basato sugli algoritmi genetici in grado di risolvere problemi
multiobiettivo sia di programmazione lineare continua che intera;
realizzazione di un prototipo dell’algoritmo, o delle varie parti che lo
costituiscono, al fine di poter testare l’efficacia dell’approccio
individuato;
test delle caratteristiche e performance del prototipo, e una
presentazione dei risultati ottenuti confrontati con quelli di possibili
algoritmi competitori su un insieme esemplificativo delle classi di
problemi individuati.
Lo svolgimento del presente progetto di tesi ha prodotto come risultato la
delineazione di una logica di composizione per un algoritmo genetico capace
di adottare dei comportamenti adeguati all’elaborazione di precise strutture
delle variabili decisionali in ingresso. Con un leggero abuso notazionale si
farà riferimento d’ora in poi alle variabili soggette ad un insieme di vincoli,
in cui è possibile riconoscere delle caratteristiche comuni o una struttura, con
il termine di variabili strutturate (ad esempio un sistema di vincoli lineari che
definiscono la struttura di un grafo).
Il prototipo prodotto è un programma scritto in linguaggio Java
indipendente, capace di accettare un buon numero di tipologie di variabili in
input diverse. La scelta di utilizzare Java è stata influenzata dalle
caratteristiche dell’ambiente in cui esso si andrebbe a inserire in caso di una
valutazione positiva del lavoro.
Per lo svolgimento del lavoro di tesi si è usufruito di diverse piattaforme, la
cui scelta è stata strettamente influenzata dalle specifiche necessità di ogni
5
fase. Durante l’esplorazione dei metodi di risoluzione e dei comportamenti
dei diversi algoritmi sono stati impiegati principalmente due software di
ottimizzazione:
FICO® Xpress Optimization Suite – Student Edition
Programma per la risoluzione di problemi di programmazione lineare.
Esso mette a disposizione un valido linguaggio di modellazione per la
formulazione efficiente di modelli matematici.
modeFRONTIER®
Piattaforma di integrazione per l’ottimizzazione multidisciplinare
singola e multiobiettivo. Mette a disposizione dell’utilizzatore un
vasto numero di strumenti di post processing, utili per indagini
statistiche, analisi dei dati e processo decisionale.
Il secondo è stato largamente utilizzato anche nelle fasi successive, sia per
l’ispezione e la valutazione dei risultati del prototipo realizzato,
opportunamente importati, sia per l’effettiva esecuzione degli algoritmi
genetici che sono stati impiegati come competitori per la valutazione dei test
effettuati. Altri programmi utilizzati da annoverare sono Netbeans IDE 7.3 e
Notepad++, strumenti largamente conosciuti e che quindi non necessitano di
dettagli aggiuntivi. Nello specifico le tecnologie impiegate per la
realizzazione dell’algoritmo, risultato di questo lavoro di tesi, sono state:
Java Standard Edition Development Kit 7 [20]
Git Repository [21]
Inoltre si è fatto utilizzo del linguaggio Mosel [22] durante l’utilizzo del
primo programma elencato.
6
Il presente lavoro di tesi verrà esposto nel corso dei cinque capitoli a seguire:
2. Sarà esposta una estrema sintesi dei concetti fondamentali sugli
algoritmi genetici e del contesto del progetto. Particolare
attenzione verrà posta nella trattazione degli strumenti
effettivamente impiegati dall’algoritmo prodotto;
3. Nel terzo capitolo si presenterà l’analisi svolta sulla letteratura e
una rapida presentazione dello stato dell’arte inerente l’ambito in
cui si andrà ad inserire il progetto di tesi;
4. Saranno esposte le motivazioni e i ragionamenti che hanno portato
alla definizione dell’algoritmo prodotto, trattando in modo
approfondito le tre macroaree di interesse;
5. Nel corso del quinto capitolo si entrerà nel dettaglio dello sviluppo
dell’algoritmo portando in evidenza le problematiche più
importanti affrontate durante l’implementazione;
6. Infine si esporranno i risultati ottenuti nel corso dei venti test
effettuati sull’algoritmo prodotto, raffrontandoli con le prestazioni
di competitor scelti adeguatamente per le cinque categorie
affrontate.
7
2. Definizioni e Concetti fondamentali
2.1. Algoritmi Genetici
“...the metaphor underlying genetic algorithms is that of natural evolution.
In evolution, the problem each species faces is one of searching for beneficial
adaptations to a complicated and changing environment. The ‘knowledge’
that each species has gained is embodied in the makeup of the chromosomes
of its members.” [2]
Gli algoritmi genetici rientrano nella classe delle euristiche, ovvero quegli
algoritmi che non garantiscono di ottenere la soluzione ottima, ma tendono
ad essere particolarmente efficaci nell’esplorazione di varie porzioni della
regione ammissibile e nell’evolvere gradualmente verso soluzioni sempre
migliori. Questa strategia è motivata dal fatto che gli algoritmi euristici
vengono solitamente impiegati quando un metodo di risoluzione esatto non
è possibile o sarebbe proibitivo in termini di tempo computazionale,
accontentandosi così di ricercare una soluzione sub ottimale in un tempo
ragionevole. Essi sono procedure complesse, adattative, finalizzate alla
risoluzione di problemi di ottimizzazione e basate concettualmente sui
principi che regolano l’evoluzione della specie. L’idea che sta alla base è
quindi quella di selezionare le soluzioni migliori e di ricombinarle in qualche
modo fra loro, in maniera tale che essere evolvano verso una soluzione
ottima. Tale tipologia di algoritmi è stata introdotta da John Holland [3] e da
allora sono stati sviluppati e applicati ad un insieme estremamente vasto di
problemi in svariati ambiti [4]. I risultati di queste ricerche hanno mostrato
l’elevato grado di robustezza di questa metodologia rispetto a quelle già
presenti in letteratura.
8
2.1.1. Principio di funzionamento
Si imposta il discorso generale sulla metafora dell’evoluzione della specie per
renderlo più intuitivo. In natura gli individui si riproducono mescolando i
propri patrimoni genetici, cioè i loro cromosomi. I nuovi individui generati
avranno pertanto un patrimonio genetico derivato in parte da ognuno dei
genitori. La selezione naturale fa sì che riescano a sopravvivere solo gli
individui più forti, e conseguentemente anche a riprodursi. Il grado di
conformità della popolazione all’ambiente quindi tenderà, generazione dopo
generazione, a salire; portando così la specie ad evolversi nel tempo e a
migliorarsi.
Allo stesso modo negli algoritmi genetici ogni possibile soluzione, costituita
dall’insieme di tutte le variabili che la generano, viene interpretata come il
cromosoma di un individuo. In base alle caratteristiche del problema
sottomesso si otterrà una valutazione di conformità denominata fitness per
ogni individuo. Su tale valore si attuerà una selezione degli individui più
idonei alla riproduzione, in base alla quale verranno generati i figli, prodotti
da incroci e mutazioni dei cromosomi dei genitori.
I principi fondamentali su cui si basa questa teoria sono i seguenti:
Variabilità dei caratteri tra gli individui di una popolazione;
Adattamento, secondo il quale gli individui che presentano caratteri
vantaggiosi ai fini della sopravvivenza e della riproduzione sono i più
consoni all’ambiente;
Ereditarietà dei caratteri tra genitori e figli.
9
2.1.2. Passi intuitivi di un algoritmo genetico:
1. Generazione di una popolazione iniziale;
2. Creazione di una nuova popolazione:
a. selezionare una coppia di soluzioni genitori;
b. applicare con una certa probabilità gli operatori genetici
(crossover e mutazione) ai due individui estratti generando così
dei figli.
3. Calcolo del valore di fitness per tutte le soluzioni/individui;
4. Verifica che il criterio di arresto sia soddisfatto, in caso contrario
ritorno al punto 2.
Ognuno dei punti elencati può essere eseguito in più modi e le scelte migliori
sulle strategie da adottare saranno dipendenti dal problema in esame. Senza
soffermarsi ulteriormente su considerazioni troppo specifiche si procede con
una rapida vista del contenuto dei vari passi dell’algoritmo.
2.1.2.1. Generazione della popolazione iniziale
Nella maggior parte dei casi la scelta di una popolazione iniziale è effettuata
in modo del tutto casuale, senza imporre alcun tipo di vincolo e senza
pregiudicare la possibilità di convergenza dell’algoritmo. Tuttavia optando
per una generazione mirata alle zone dello spazio delle soluzioni dove è più
probabile la presenza di una soluzione ottima, si potrebbe portare ad
intraprendere una evoluzione più rapida verso tali regioni; o viceversa ad un
accumulo dannoso dei punti esplorati precludendo possibili buoni risultati
inattesi. D’altro canto una popolazione iniziale ben distribuita su tutto lo
spazio si può ottenere ricorrendo a tecniche di generazioni semi casuali,
10
come ad esempio il metodo basato sulle sequenze a bassa discrepanza di
Sobol [23].
Analoghe considerazioni valgono per la determinazione della dimensione
della popolazione iniziale. Una dimensione troppo ridotta potrebbe incorrere
nel rischio di non effettuare una adeguata esplorazione dello spazio delle
soluzioni. Per contro una popolazione troppo numerosa potrebbe
appesantire il peso computazionale di ogni singola generazione, rallentando
così la rapidità di convergenza dell’algoritmo alle soluzioni migliori.
Inizialmente gli studi avevano portato a correlare la dimensione del
problema con un andamento esponenziale della dimensione della
popolazione [26][27]. Fortunatamente lavori più recenti hanno dimostrato
che tale relazione non era vincolante, associando le dimensioni di 30, 50 o 100
individui alla maggioranza delle istanze, definendole come le dimensioni più
comuni [28]. Altri lavori mostrano come popolazioni di dimensioni molto
ridotte possono essere adeguati, almeno per GA codificati in binario [29].
2.1.2.2. Creazione di una nuova popolazione
2.1.2.2.a. Selezione
La probabilità di selezione di un individuo dipende dal valore assegnatogli
dalla funzione di fitness, ovvero l’indicatore della sua bontà per risolvere il
problema. Un valore più alto di valutazione implica una maggiore
probabilità di essere scelto come genitore per partecipare alla creazione della
nuova generazione. Uno dei criteri più utilizzati è quello di Holland [3] che
attribuisce una probabilità di scelta proporzionale al valore di fitness
dell’individuo. Grazie al meccanismo della selezione, le probabilità di
11
riprodursi vengono sbilanciate verso gli elementi migliori della popolazione
e quindi di trasmettere il loro genoma alle generazioni successive.
Sono importanti però le differenze che possono insorgere fra una scelta
diretta degli individui con alta valutazione o con lo sbilanciamento di
probabilità di selezione a favore degli stessi. Il secondo criterio, rispetto al
primo, permette di mantenere un più alto tasso di differenziazione genetica
all’interno della popolazione, dando la possibilità di riproduzione anche a
soggetti non buoni. Questa caratteristica permette all’algoritmo di esplorare
meglio lo spazio delle soluzioni, rendendo meno probabile la saturazione
della popolazione da parte di poche soluzioni molto buone ma poco distanti
fra loro. Riassumendo il criterio di selezione deve:
Favorire la riproduzione di individui con valori alti di fitness;
Preservare la diversità della popolazione in modo da esplorare lo
spazio di ricerca delle soluzioni.
Viene di seguito brevemente illustrato il funzionamento di tre tipologie
molto utilizzate di selezione:
Rank selection: la popolazione viene ordinata in ordine decrescente di fitness e
si attribuisce ad ogni individuo una probabilità in funzione della posizione in
classifica, indipendente dalle effettive differenze di valore di fitness. Tale
approccio assicura di evitare la convergenza prematura e la stagnazione
poiché nessun individuo otterrà una probabilità largamente superiore ad un
altro di essere selezionato. Per contro, questo metodo, soffre di una certa
pensantezza computazionale che porterà a un’individuazione più lenta degli
individui migliori, naturale conseguenza dei vantaggi descritti in
precedenza.
12
Roulette wheel selection: è un criterio di scelta di un individuo proporzionale al
suo valore di fitness. Se definiamo la fitness dell’individuo i-esimo, la
probabilità di essere selezionato dell’individuo i-esimo sarà definita come
, con N numero di individui della popolazione. Si veda un semplice
esempio in cui sono presenti solo quattro individui: ; con
probabilità di selezione 0.12, 0.18, 0.3, 0.4. Intuitivamente essi occupano una
porzione di roulette proporzionale alla loro probabilità di selezione. Nella
figura seguente, l’operatore genera un numero casuale e l’individuo
viene selezionato.
Tournament selection: rappresenta una evoluzione del metodo più semplice
possibile per una operazione di selezione, ovvero il pescaggio casuale a
probabilità uniforme dalla popolazione. Infatti viene definito un torneo con
essenzialmente due parametri: il numero di partecipanti e il criterio di scelta
del vincitore. Intuitivamente si procederà ad una scelta casuale dalla
popolazione di N partecipanti per il torneo da cui risulterà un vincitore che
verrà scelto per la riproduzione.
13
La scelta di un Tournament selection con N = 1 partecipanti equivale ad un
random uniforme. Un’interessante opzione invece è la possibilità di inserire
una probabilità con cui, ad ogni scontro diretto del torneo, riesca a prevalere
l’individuo peggiore. Questo per preservare la diversità all’interno delle
popolazioni senza aggiungere procedure computazionalmente pesanti, come
il riordino della intera popolazione per valore di fitness decrescente
necessario nella Rank Selection.
2.1.2.2.b. Crossover
L’operatore di crossover si può definire intuitivamente come una procedura
di incrocio dei cromosomi dei genitori selezionati per la riproduzione. Tale
composizione dà vita ai cromosomi figli e dunque a dei nuovi individui per
la popolazione in corso di formazione.
Per fornire un semplice esempio di funzionamento, prima di addentrarsi
nella visione di alcuni operatori di crossover specifici, si propone il One-
point crossover:
Definiti due cromosomi come e
appartenenti ai genitori coinvolti, si genera la seguente coppia di figli:
14
e con
punto di taglio scelto casualmente.
Si vedano velocemente alcuni tipi di crossover la cui conoscenza sarà utile
per lo svolgimento successivo del progetto di tesi, dato il loro effettivo
utilizzo nell’algoritmo sviluppato:
Simple crossover
È definito quasi allo stesso modo del già noto One-point crossover,
limitandone però l’utilizzo a punti di taglio validi (una rappresentazione in
floating point ad esempio non è divisibile in ogni punto). Esso viene
impiegato su problemi i cui vincoli definiscono un convex set come spazio
delle soluzioni. Però un incrocio semplice potrebbe dar vita a soluzioni
esterne alla zona dell’insieme convesso , perciò viene introdotto un
parametro tale che:
E conseguentemente
In diversi articoli visionati in letteratura si solleva il quesito della ricerca del
criterio di scelta più appropriato di , contrapposto al metodo effettivamente
utilizzato in questo lavoro, la generazione casuale del parametro.
15
Single arithmetical crossover
Partendo sempre dalle medesime premesse sui cromosomi dei genitori,
questo operatore viene definito come segue: (viene esplicitata la
formulazione di uno solo dei due figli, per l’altro il procedimento è analogo)
Dove è un parametro generato a caso da un dominio dinamico definito
come:
definito come limitazione valida inferiore della posizione k-esima in X
e similarmente come limitazione superiore.
Whole arithmetical crossover
Viene definito come una combinazione lineare degli interi cromosomi dei
genitori. Partendo dalle assunzioni di notazione adottate nei casi precedenti
si otterranno i seguenti cromosomi figli:
Il parametro è definito nuovamente come un numero casuale preso
dall’intervallo fra zero e uno, che garantisce di rimanere all’interno dello
spazio convesso delle soluzioni.
16
Heuristic Crossover
L’operatore di incrocio euristico sfrutta le valutazioni dei genitori per
provare a indirizzare i figli in una direzione che potrebbe essere migliore
delle altre. Ciò viene tentato sbilanciando la procedura a favore del
cromosoma del migliore dei due genitori sperando così di ereditare
caratteristiche migliori da quell’individuo.
Assumendo si definisce il figlio F ottenuto come:
2.1.2.2.c. Mutazione
Tale categoria di operatori genetici viene utilizzata per mantenere una certa
diversità nelle popolazioni. Essa viene attuata grazie a delle variazioni
pseudo casuali nella procedura di riproduzione. A parte l’intento di cercare
di migliorare il valore di fitness dei cromosomi mutati, si porta in primo
piano il ruolo fondamentale della mutazione per garantire la caratteristica di
robustezza agli algoritmi genetici. Infatti grazie a queste variazioni pseudo
casuali si potrà sperare di evitare la convergenza prematura dell’algoritmo a
punti di minimo o massimo locali.
Si vedano ora alcuni esempi di operatori genetici di mutazione che, come per
il caso precedente, verranno effettivamente utilizzati nella realizzazione
dell’algoritmo in sviluppo.
17
Uniform mutation
Viene selezionata una posizione in maniera casuale all’interno di
un cromosoma di un individuo . Il nuovo individuo mutato
verrà definito come dove viene cambiato con un
valore preso casualmente dall’intervallo
a distribuzione uniforme.
è definito come limitazione valida inferiore della posizione k-esima in X
e similarmente come limitazione superiore.
Boundary mutation
Viene definita come una mutazione che opera come la precedente, però al
posto di selezionare casualmente a distribuzione uniforme il valore di
viene assegnato un valore, per l’appunto, al limite. Ovvero
scelto con equa probabilità il valore di o di
.
Non-uniform mutation
Definito il cromosoma dell’individuo padre come , viene preso
casualmente un e dunque definito, come negli altri casi, il nuovo
individuo con
La funzione restituisce un valore nell’intervallo con una
probabilità che si avvicina a 0 all’incrementarsi del t tempo trascorso di
esecuzione dell’algoritmo. Questa caratteristica quindi impone un
andamento nel tempo estremamente adatto agli scopi di un algoritmo
genetico. Infatti causa una iniziale distribuzione uniforme sull’intervallo di
mutazione, che quindi ricercherà su tutto lo spazio delle soluzioni, per poi
18
costringere l’intervallo ad una distribuzione che comporterà una ricerca
sempre più stringente.
2.1.2.3. Funzione di Fitness
Il metodo più semplice per comprendere la funzione di fitness di un
algoritmo genetico è considerare che essa coincida con la funzione obiettivo
del problema in esame. Sono tuttavia da prendere in esame numerose
considerazioni che espandono la complessità di tale funzione, evidenziando
la sua rilevanza e il suo peso sulla qualità e sulla rapidità di convergenza
dell’esecuzione dell’algoritmo.
Nelle euristiche evolutive la considerazione della presenza di più funzioni
obiettivo e dell’effetto della violazione dei vincoli imposti dal problema nella
valutazione di una possibile soluzione è un problema sempre aperto. Questo
a causa della mancanza di uno standard de facto da adottare affrontando tali
problematiche, nonostante l’alto numero di possibili approcci definiti in
letteratura. In questo frangente è importante nominare gli algoritmi genetici
a cui si farà riferimento e che determinano l’attuale stato dell’arte:
Non-dominated Sorting Genetic Algorithm, NSGA-II [24]
Multi Objective Genetic Algorithm, MOGA-II [25]
Elitismo
A seguito di tutte le considerazioni appena affrontate si afferma che la
strategia degli algoritmi genetici può risultare poco conveniente in un ambito
di ottimizzazione. Questo perché dopo aver raggiunto una buona soluzione
si correrebbe il rischio di perderla qualora essa non rientri nel meccanismo
riproduttivo. Per ovviare a questo problema, De Jong introduce il concetto di
19
elitismo [30]. La strategia si basa sul garantire la sopravvivenza al ricambio
generazionale di un sottoinsieme di individui, identificati come i migliori. In
maniera molto intuitiva allora si può dimostrare che, per costruire un
algoritmo genetico convergente alla soluzione ottima, è sufficiente mantenere
un elite set di dimensione uno (mantenendo quindi il solo individuo migliore
della generazione). In questo modo si genera una successione non
decrescente di valori della funzione di fitness e, se questa è superiormente
limitata, allora essa è anche convergente. In letteratura è dimostrato che
l’impiego del concetto di elitismo negli algoritmi genetici migliora
sensibilmente la velocità di convergenza degli stessi [48][24].
2.1.2.4. Criteri di Arresto
Per quanto riguarda le condizioni di arresto di un algoritmo genetico
possono esserci molteplici alternative. La scelta più indicata è fortemente
influenzata dal contesto, e qui ci si limiterà a dare una rapida introduzione ai
metodi principali:
Arresto basato sul numero massimo di generazioni eseguibili;
Limitazione del tempo massimo di esecuzione dell’algoritmo;
Criterio basato sul confronto tra il valore medio del fitness dell’intera
popolazione e il valore di fitness della migliore soluzione trovata;
questa strategia permette di legare l’arresto del programma alla
saturazione della popolazione su un insieme di valori pressoché
uniformi, sintomo dell’assenza di miglioramenti per più generazioni;
Blocco dell’esecuzione in base ad un massimo di valutazioni della
funzione di fitness attuabili.
20
In questo lavoro di tesi sono state implementate solo le opzioni di controllo
sul primo e sul quarto criterio di arresto.
Come anticipato nel capitolo 2.1.2.3 per poter comprendere a pieno i discorsi
che verranno intrapresi successivamente sarà necessaria una breve
introduzione agli algoritmi genetici che determinano l’attuale stato dell’arte,
il MOGA-II e il NSGA-II.
2.1.3. NSGA-II
Il Non-dominated Sorting Genetic Algorithm [24] è definibile come un
algoritmo multiobiettivo che implementa i concetti di elitismo. Per poter
affrontare il flusso di evoluzione principale dell’NSGA-II però è necessario
introdurre preventivamente i seguenti concetti fondamentali:
Fast Nondominated Sorting
Crowding distance assignment
Constrained Crowded Comparison Operator
21
2.1.3.1. Fast Nondominated Sorting - FNS
L’obiettivo dell’approccio di ordinamento presentato è quello di suddividere
una popolazione in sottogruppi denominati fronti. Fra essi deve sussistere
una relazione di dominanza di Pareto, ovvero la valutazione di ogni
funzione obiettivo di un individuo dominante deve eguagliare o superare
quella degli individui dominati (superare almeno una volta). In tale ottica si
potranno individuare fronti dominati, dominanti e assegnare ad ognuno un
rango pari al numero di fronti che li dominano. Intuitivamente quindi il
fronte di rango minore sarà quello composto dagli individui migliori della
popolazione. L’idea dell’FNS è dunque quello di fornire una procedura
rapida per svolgere una siffatta suddivisione in fronti. Si presentano i passi
principali di funzionamento nello pseudocodice a seguire.
22
2.1.3.2. Crowding distance assignment - CDA
Si introduce ora un nuovo concetto per la valutazione dei punti interni ai
fronti. Gli algoritmi genetici infatti desiderano, oltre a mantenere gli
individui migliori tramite il concetto di dominanza per una convergenza
verso il fronte di Pareto ottimale, avere dei fronti ben distribuiti nello spazio
evitando concentrazioni di punti. Per fare ciò nell’NSGA-II propone la
somma delle spezzate destre e sinistre di ogni individuo calcolata sui vicini
ordinati per valore dell’obiettivo, mediata su tutti gli obiettivi del problema.
In questo modo si assegnerà un valore più alto di crowding distance a chi
presenterà delle distanze elevate dai punti adiacenti. Ordinando ora un
fronte per valori decrescenti di crowding distance si otterrà una lista che
aumenta l’affollamento dei punti man mano che si scorre verso il basso. Si
veda la seguente immagine per chiarire il concetto della stima di densità
delle soluzioni nell’intorno di una particolare soluzione della popolazione.
Per essa si considera come crowding distance di i la stima del perimetro del
parallelepipedo formato dai vertici delle soluzioni vicine a i.
23
Ottenuto così un ordinamento dei fronti secondo un grado di affollamento
crescente sarà possibile effettuare confronti di qualità anche fra individui
equivalenti da un punto di vista della soddisfazione del problema. Infatti se
bisognasse effettuare una scelta fra due elementi appartenenti allo stesso
fronte ora sarebbe possibile prediligere quello con valore di crowding
distance più alto, così da incentivare la dispersione delle soluzioni. Ciò è
preferibile perché risulta probabile che un gruppo di soluzioni vicine tra loro
presentino molte caratteristiche in comune, non portando così ulteriore
informazione alla popolazione. Concludendo si presenta uno pseudo codice
al fine di chiarire il metodo effettivo di calcolo della procedura di CDA.
24
2.1.3.3. Constrained Crowded Comparison Operator - CCCO
L’operatore introdotto dal lavoro in analisi [24] viene indicato generalmente
con il simbolo . Esso permette la definizione di un ordinamento fra
individui utilizzando le definizioni appena esposte di fronti dominati e di
crowding distance. Per ogni elemento della popolazione vengono richiesti tre
diversi attributi: un coefficiente che misura la violazione dei vincoli; il rango
del fronte di appartenenza e la crowding distance dell’individuo.
A questo punto si procede con l’esplorazione del funzionamento
dell’operatore in un confronto fra due soluzioni.
Se solamente una delle due è ammissibile l’operatore segnalerà quella
come preferibile;
Se entrambe sono valide si segnalerà migliore quella con un rango
inferiore, se appartengono allo stesso fronte si predilige il valore di
crowding distance più alto;
Nel caso siano ambedue non ammissibili si preferirà quella che
presenta un coefficiente di violazione inferiore;
Se l’applicazione dei tre passi precedenti non ha fornito alcuna
preferenza ne viene restituita una casuale.
Il Costrained Crowded Comparison Operator rende possibile effettuare
scelte di preferenza fra coppie di individui, permettendo così di creare un
vero e proprio ordinamento di tutta la popolazione. Si porta all’attenzione
che, con l’applicazione di questo criterio, si effettuerà un ordinamento
separato per gli individui che violano i vincoli. Infatti essi saranno gli ultimi
presi in considerazione preferendo chiaramente le soluzioni ammissibili.
25
A seguito dell’introduzione dei tre concetti fondamentali, che sono stati
appena presentati, sarà affrontabile ora la spiegazione del flusso principale
dell’algoritmo NSGA-II.
Facendo riferimento esplicito alle fasi identificate per un algoritmo genetico
nel capitolo 2.1.2, si considera di iniziare la spiegazione avendo già generato
la popolazione iniziale (il metodo non è rilevante ai fini dell’algoritmo). Si
procede alla prima valutazione di tutti gli individui che in questo caso
comprenderà anche le fasi descritte nei capitoli 2.1.3.1 e 2.1.3.2., ossia la
suddivisione per fronti e il calcolo delle crowding distance. A questo punto
verrà impiegato un binary tournament selection, descritto nel 2.1.2.2.a, e una
successiva fase di riproduzione per la creazione dei nuovi individui. Si
sottolinea che durante la selezione il criterio di vittoria degli scontri diretti
del torneo funzionerà sulla base del CCCO. A questo punto interviene il
concetto di elitismo, descritto in 2.1.2.3, combinato alla valutazione delle
nuove soluzioni che comporranno la popolazione di dimensione doppia, da
riportare alla dimensione desiderata. Per effettuare tale operazione, prima di
ricominciare il flusso dell’algoritmo, si sfruttano le considerazioni spiegate in
precedenza e si taglia semplicemente alla dimensione desiderata dopo aver
riordinato completamente la popolazione doppia con FNS e CDA.
26
2.1.4. MOGA-II
Il Multi Objective Genetic Algoritm [25] è sostanzialmente meno complicato
dal punto di vista operativo confrontato all’NSGA-II.
Per esso è sufficiente determinare l’insieme delle soluzioni non dominate,
cioè quelle che comporrebbero il fronte di rango minimo per il FNS. Tale
insieme viene chiamato Elite Set ed è memorizzato in maniera indipendente
rispetto all’evoluzione consueta della popolazione. È mantenuto aggiornato
tramite il confronto diretto con i nuovi individui in cerca di ulteriori
soluzioni non dominate, inoltre la sua dimensione massima viene fissata a
priori dall’algoritmo stesso.
Un’ulteriore importante differenza rispetto l’algoritmo di Deb, esposto nel
capitolo 2.1.3, consiste nel differente metodo di applicazione degli operatori
di selezione e di riproduzione. Infatti nell’NSGA-II tali operazioni si
eseguono in sequenza mentre nel MOGA-II si applicano in parallelo. Per
ogni individuo viene estratto un numero casuale che decreterà l’ azione da
eseguire, in base alle probabilità di applicazione degli operatori.
Per quanto riguarda la violazione dei vincoli é adottata la strategia di
penalità del valore di fitness dell’individuo per la non ammissibilità. Questo
permette all’algoritmo di operare automaticamente la preferenza per le
soluzioni ammissibili senza prevedere logiche separate per tali soluzioni.
Non si ritiene necessario scendere nei dettagli dei passi principali del
MOGA-II poiché le uniche operazioni che si scostano da una gestione
standard di un algoritmo genetico riguardano l’utilizzo e il mantenimento
dell’elite set e l’applicazione parallela degli operatori, descritte nei paragrafi
precedenti.
27
2.2. Contesto: Problemi ingegneristici industriali
Il presente lavoro di tesi è stato sviluppato in un ambito ben preciso che
inevitabilmente ne ha pilotato alcune scelte strutturali. Si procede quindi ad
una rapida panoramica dei caratteri principali del contesto che serviranno
poi a comprendere alcune decisioni concettuali e operative attuate nei
capitoli successivi.
Il progetto nasce da una collaborazione universitaria con ESTECO S.p.A. che
ricopre un ruolo di primo piano a livello internazionale nel campo
dell’ottimizzazione multidisciplinare, sia come fornitore di software per
l’ottimizzazione che come fornitore di servizi avanzati per l’ingegneria.
Il principale prodotto software offerto da tale azienda è denominato
modeFRONTIER®. È una piattaforma di integrazione che permette un
interfacciamento diretto con un gran numero di strumenti Computer-Aided
Design e Computer-Aided Engineering, dedicata all’ottimizzazione
multiobiettivo, all’automazione dei processi di progettazione ingegneristica,
all’analisi dei dati e al decision making in contesti multidisciplinari.
28
Della vasta scelta di algoritmi implementati all’interno del software appena
presentato però si prenderanno in considerazione solo gli algoritmi genetici.
Nello specifico solamente i due, già dettagliatamente spiegati, che verranno
utilizzati poi come competitori durante la fase dei test: MOGA-II [25] e
NSGA-II [24].
Nell’ottimizzazione industriale affrontata da modeFRONTIER® è importante
sottolineare che, solitamente, le variabili possono presentarsi in molteplici
forme ma generalmente hanno sempre dei vincoli stringenti sul dominio.
Infatti per ogni variabile considerata, il software richiede l’inserimento di un
limite inferiore e un limite superiore coi quali operare. Essenziale inoltre
sottolineare la numerosità delle variabili, il numero dei vincoli e della
quantità di obiettivi mediamente presenti nei problemi di ottimizzazione
industriale. Si pensi intuitivamente alla progettazione di un nuovo pezzo di
un motore di cui si vogliono ottimizzare varie caratteristiche. In tal caso il
numero di parametri liberi su cui si potrà effettivamente operare decisioni
sarà estremamente limitato poiché i parametri di progetto e i limiti fisici
imposti nei simulatori saranno estremamente stringenti. È importante
chiarire che generalmente modeFRONTIER® non ha accesso ai dettagli dei
simulatori né alle formule che genereranno gli output su cui dovrà
ottimizzare. Lo scenario risulta forse più chiaro visionando l’immagine
seguente ove è stato simbolicamente indicato il livello di valutazione degli
input con una blackbox.
29
Possiamo quindi quantificare le variabili decisionali in input come
nell’ordine delle decine (mediamente vanno dalla decina al centinaio).
Il numero degli obiettivi è solitamente inferiore alla decina, anche se
generalmente viene esplicitamente consigliato di effettuare ottimizzazioni
con al massimo due o tre obiettivi per limitare la difficoltà di gestione del
fronte di Pareto e delle decisioni successive.
I vincoli dei problemi sono anch’essi nell’ordine delle decine e solitamente in
quantità proporzionale al numero di variabili, escludendo i limiti inferiori e
superiori delle singole variabili. Inoltre si noti che la maggior parte dei
vincoli comunemente sottomessi a modeFRONTIER® saranno applicati sulle
variabili in uscita dalla black box. Questo perché eredi dello scenario e della
presenza di complesse simulazioni a livello di fitness che rendono
impossibile esplicitare i vincoli sui risultati della blackbox in funzione delle
variabili decisionali in ingresso.
Risulta immediata la congiunzione delle caratteristiche appena esposte con
una iterazione di un algoritmo genetico. Ogni individuo definito come set di
valori delle variabili di input dovrà essere valutato e questa procedura
Variabili decisionali
BlackBox
Variabili in uscita
30
richiederà tempo di computazione della blackbox che potrà essere anche
molto lungo. Una normale quantificazione del tempo di calcolo necessario ad
una singola valutazione potrà infatti variare in media dall’ordine dei minuti
a quello delle ore. Ne consegue che l’obiettivo principale di un algoritmo sarà
di riuscire a produrre buoni risultati con un numero limitato di valutazioni,
poiché tale procedura è indiscutibilmente il collo di bottiglia computazionale
dell’intero processo.
31
3. Analisi della letteratura
Lo studio dei metodi di risoluzione dei problemi, che interessano questo
lavoro di laurea, è partito da una visione dei metodi principali affrontati nei
corsi universitari di Ricerca Operativa e di Modelli di Ottimizzazione, poi
analizzati più in dettaglio attraverso vari libri di testo [31][32][36].
Allo stesso modo si è proceduto all’esplorazione delle tematiche euristiche
degli algoritmi genetici. Grazie a delle ricerche in rete e a un corso
frequentato all’interno dell’azienda ospitante, ESTECO S.p.A., si è andati a
formare delle basi più che sufficienti per poter intraprendere una ricerca
autonoma in letteratura. Come per gli argomenti inerenti la ricerca operativa
si ritiene superfluo soffermarsi nuovamente sui caratteri standard degli
algoritmi genetici; preferendo invece una presentazione delle metodologie
riscontrate in letteratura per risolvere problemi di interesse o ad essi
riconducibili.
Innanzi tutto bisogna considerare che molti problemi di ottimizzazione
interessanti non dispongono di metodi esatti e/o di risoluzione in tempo
polinomiale a causa della loro complessità computazionale. Per queste
categorie di problemi, nella pratica, ogni soluzione vicina all’ottimo è
preferibile se ottenuta in tempi computazionali ragionevoli. Tale
considerazione motiva e apre la strada all’impiego di euristiche.
Molti dei problemi computazionalmente non trattabili sfruttano metodi di
ricerca probabilistici, ma questi non dispongono di una via generale per la
gestione dei vincoli.
In generale però i vincoli sono parte integrale della formulazione di ogni
problema. In [1] gli autori esprimono esaustivamente tale concetto con le
32
seguenti parole: “Virtually all decision making situations involve constraints.
What distinguish various types of problems is the form of these constraints.
Depending on how the problem is visualized, they can arise as rules, data
dependencies, algebraic expression, or other forms. Constraint satisfaction
problems (CSPs) have been studied extensively in the operations research
(OR) and artificial intelligence (AI) literature. In OR formulations constraints
are quantitative, and the solver (such as the Simplex algorithm) optimizes
(maximizes or minimizes) the value of a specified objective function subject
to the constraints. In constrast, AI research has focused on inference-based
approaches with mostly symbolic constraints. The inference mechanism
employed include theorem provers, production rule interpreters, and various
labeling procedures such as those used in truth maintenance systems.”
L’idea alla base di questo lavoro è quindi trovare un approccio per risolvere
problemi di ottimizzazione al cui interno siano presenti degli insiemi di
vincoli lineari basandosi sugli Algoritmi Genetici. Come già detto, queste
tecniche vengono di norma utilizzate per tentare di risolvere problemi di
ottimizzazione per i quali non si conoscono altri metodi efficienti di
complessità lineare o polinomiale.
Poiché l'approccio genetico, spiegato dettagliatamente nel capitolo 2.1, è
fondamentalmente una esplorazione dell’insieme delle soluzioni ammissibili,
introdurre vincoli può essere potenzialmente vantaggioso e può migliorare il
comportamento della ricerca limitando la regione ammissibile. Tuttavia
nessuno degli approcci tradizionali degli algoritmi genetici utilizza questa
strategia ma impiega tecniche volte a minimizzare l'effetto negativo dei
vincoli. In questo modo, si ricorre ad un allargamento dello spazio di ricerca
permettendo la scelta di soluzioni non ammissibili, esterne quindi alla
regione ammissibile, durante l’evoluzione dell’algoritmo. In alcune tecniche
33
di ottimizzazione, come nel metodo del simplesso [31][32], i vincoli di
uguaglianza vengono sfruttati poiché, se esiste, l’ottimo è situato sulla
superficie dell’insieme convesso generato dall’insieme dei vincoli. Le
diseguaglianze sono convertite in uguaglianze tramite l’aggiunta di variabili
di slack, e la tecnica risolutiva procede spostandosi da vertice a vertice
spostandosi sul bordo della superficie. Bisogna inoltre aggiungere una nota
importante perché nel contesto in cui questo lavoro si pone, presentato nel
corso del capitolo 2.2, l’algoritmo non dispone di alcuna conoscenza sulla
funzione obiettivo, ma può solamente richiedere il calcolo del suo valore alla
blackbox. Questo si contrappone a metodi come quello del simplesso che
guida la ricerca grazie ai valori introdotti dalla funzione obiettivo; oppure ad
altre tecniche della ricerca operativa che sfruttano informazioni estrapolate
dai pesi della formulazione matematica di tale funzione per limitare lo spazio
delle soluzioni e direzionarsi nella ricerca del valore ottimo. Quest’ultimo
criterio considera solo funzioni obiettivo lineari, ipotesi che purtroppo nel
presente contesto applicativo non possiamo garantire. Inoltre da un punto di
vista operativo, tutti gli algoritmi che lavorano effettivamente con delle
uguaglianze sono soggetti a possibili errori di natura numerica dei
calcolatori; condizione che introduce altri parametri di funzionamento, come
gli ordini di precisione e gli intervalli di controllo dei vincoli, per i
programmi che implementano tali algoritmi.
Per contrasto al discorso sul simplesso, in dei metodi che generano soluzioni
in maniera pseudo casuale sullo spazio delle soluzioni, i vincoli di
uguaglianza risultano un problema non ignorabile. Si può notare
semplicemente che gli algoritmi genetici rientrano in questa categoria, infatti
dallo studio bibliografico e pratico effettuato sui problemi di interesse,
classici della programmazione lineare e problemi combinatori, ne è risultato
34
che l’applicazione di un algoritmo genetico standard, per tali istanze, risulta
svantaggioso rispetto ad algoritmi esatti, come il Branch and Bound.
Questo fatto risulta forse più chiaro affrontando le difficoltà di generazione
di una soluzione ammissibile all’interno del dominio del problema per
istanze con un gran numero di vincoli. In tali casi la probabilità di
generazione di candidati non ammissibili è decisamente troppo grande per
poter essere ignorata. Un ottimo esempio, anche se banale, risulta la
costruzione di un circuito hamiltoniano per la soluzione di un classico
Traveling Saleman Problem [31][32]. Ogni applicazione diretta degli
operatori genetici standard di mutazione e di crossover, genera una
soluzione chiaramente non ammissibile con probabilità estremamente alta,
ipotizzando di non eseguire delle codifiche sulle variabili decisionali.
Le metodologie in assoluto più comuni ritrovate in letteratura sono
principalmente basate sul nascondere, all’interno di operatori genetici
specializzati, la logica del problema specifico [8][7][14][15][16][33][34][35],
andando a far lavorare l’algoritmo genetico solamente sullo spazio di
soluzioni ammissibili. Inoltre questa tecnica é spesso accoppiata da delle
procedure di local improvement che analizzano il cromosoma del candidato
per migliorarlo (tali procedure sono fortemente specializzate sull’istanza del
problema). Inutile sottolineare che una procedura di miglioramento locale
può agire in molteplici modi, ma esse sono generalmente costose da un
punto di vista computazionale. Inoltre una impostazione troppo rigida degli
operatori specializzati e delle meccaniche di miglioramento locale può
portare a delle restrizioni non volute dello spazio delle soluzioni, portando
irrimediabilmente l’esecuzione dell’algoritmo a incagliarsi su dei valori
ottimi locali.
35
Un altro metodo utilizzato di frequente per impostare un’istanza di un
problema avente delle variabili strutturate, è ricorrere a dei decoder
situazionali [7][32]. Essi mascherano problemi derivanti l’utilizzo di strutture
dati non convenzionali richieste però dal problema. Al pari dei local
improvement, anche i decoder possono diventare estremamente costosi
computazionalmente. Inoltre si deve anche considerare il potenziale
svantaggio di celare informazioni logiche, che potrebbero risultare utili dal
punto di vista decisionale per l’evoluzione dell’algoritmo, all’interno della
codifica. Un esempio intuitivo potrebbe essere un problema di ricerca su
grafo del cammino minimo dove i cromosomi sono set di archi numerati.
Con una codifica del genere la vicinanza di un numero che codifica un arco
al suo successivo non avrebbe per forza un senso logico per il modello, né
tantomeno l’ordinamento delle codifiche stesse. O l’assegnazione di processi
paralleli ad un insieme di processori [37] dove ogni possibile assegnamento
viene codificato da un valore non ordinato; privando così, anche in questo
caso, i possibili significati di vicinanza e di ordinamento fra due soluzioni
codificate vicine per possibili operatori genetici.
Un altro approccio documentato è costituito dalle procedure di riparazione
che vengono operate su candidati non ammissibili per essere riportati nello
spazio di ammissibilità [9][13][17]. Tali procedure vengono progettate con un
alto grado di specificità in base alla istanza del problema e, dipendentemente
da quest’ultimo, possono anche degenerare in complessità computazionale
fino a rasentare la difficoltà di risoluzione del problema stesso. Si vuole
evidenziare il caso dei problemi di ottimizzazione delle catene di montaggio
automobilistiche, contesto nel quale sono estremamente utilizzati all’interno
degli operatori di crossover specializzati [13][38].
36
Elaborate quindi le considerazioni, estrapolate dall’analisi della letteratura, si
opta per suddividere in macroaree le caratteristiche comuni individuabili nei
problemi di interesse. Questo permette una trattazione più semplice
dell’ispezione delle possibili metodologie risolutive adottabili per i tre
contesti di interesse così suddivisi:
Insiemi di vincoli lineari;
Variabili intere e binarie;
Strutture dati: disposizioni e permutazioni.
Insiemi di vincoli lineari
Prima di procedere con l’elencazione delle opzioni individuate per affrontare
la presente macroarea si ricorda che nel contesto applicativo non si
dispongono di informazioni sulla funzione obiettivo. Data la ottimizzazione
black box quindi non sarà possibile trarre vantaggio dalle informazioni delle
eventuali strutture lineari dei vincoli sulle variabili in uscita e della funzione
obiettivo. Sotto questa ipotesi però sono disponibili varie alternative di
sfruttamento di tali strutture:
eliminazione delle variabili riducendo la dimensione del problema;
riparatori/miglioratori locali che cercano di perfezionare i risultati
inammissibili sfruttando la struttura lineare dei vincoli;
adozione di operatori genetici custom;
mantenimento degli approcci genetici standard.
37
Variabili intere e binarie
Permettere ad un algoritmo genetico di supportare problemi con variabili di
questo tipo non si concretizza in sostanziali differenze di funzionamento ma
semplicemente di prevedere un adeguato supporto operativo ad esse. Le
problematiche introdotte sono di performance, poiché le variabili discrete
introducono difficoltà di esplorazione dello spazio delle soluzioni. Inoltre la
maggior parte dei test case di questa categoria può venir modellizzata con
strutture dati più complesse che affronteremo nel prossimo paragrafo.
Si presentano comunque come alternative di sfruttamento delle variabili
intere e binarie:
integrazione di improvement local euristici tratti dalle strategie di
programmazione intera;
mantenimento della struttura generica di GA, arricchita della logica
operativa per operare con variabili intere e binarie;
inserimento di procedure di repair all’interno di una struttura classica
degli algoritmi genetici;
adozione di operatori genetici specializzati.
Strutture dati: disposizioni e permutazioni
Dall’analisi della letteratura é emersa una preferenza diffusa per le
procedure di decoder delle strutture dati estremamente vincolate. Essa si
concretizza con la definizione di uno schema di codifica di tutti gli elementi
validi del problema, andando poi ad utilizzare tali valori per riempire un
vettore di dimensione finita rappresentante una possibile soluzione. Un
esempio decisamente intuitivo può essere la codifica di una istanza del
commesso viaggiatore in cui si opera numerando tutte le città presenti nel
38
problema. Una possibile soluzione a questo punto diventa una sequenza di
numeri interi rappresentanti le città (codifica) che il commesso visita
nell’ordine in cui sono presentati all’interno del vettore, rendendo obbligato
il passo di collegamento fra l’ultima posizione della sequenza e la prima
creando così un circuito. Si ricorda che, per la formulazione del problema, il
commesso non può visitare due volte la stessa città. A questo punto si può
associare la definizione di disposizione senza ripetizione, o di permutazione,
al vettore codificato. Senza scendere ulteriormente nel dettaglio con esempi
di problemi che possono utilizzare una codifica di questo tipo si presentano i
metodi principali trovati per poter sfruttare questa struttura in un algoritmo
genetico:
definizione di operatori specializzati per le disposizioni;
adozione di un meccanismo di repair/fix, per ricostruire da un
individuo generato da un operatore una soluzione ammissibile al
problema;
inserimento congiunto dei punti precedenti in un algoritmo genetico
che utilizza anche operatori non specializzati.
Permutazioni e disposizioni su grafo
Nonostante l’esempio portato all’attenzione nel paragrafo precedente
parlasse di un problema del commesso viaggiatore, nelle considerazioni
possibili inerenti allo sfruttamento delle permutazioni non si accennano
ragionamenti in merito alla struttura del grafo, chiaramente presente in una
formulazione di un TSP. Una importante parentesi viene dunque aperta sui
problemi che coinvolgono la presenza di alberi e grafi, dato che essi
costituiscono una importante fetta dei problemi di ottimizzazione
39
combinatoria. Si è voluto differenziare la categoria dei grafi delle sole
permutazioni poiché nella seconda rientrano anche possibili codifiche di
problemi che non coinvolgono grafi o alberi, un ottimo esempio si può
ritrovare nel Knapsack (problema dello zaino).
Con l’introduzione della presente categoria si prende in considerazione di
utilizzare l’enorme insieme di vincoli, che nei modelli lineari costruiscono la
struttura del grafo, come input semplificato ad uno dei due possibili metodi
che sfruttano tale struttura ai fini evoluzionistici:
definizione di operatori specializzati che considerino i vincoli
strutturali del grafo;
adozione di una procedura di riparazione che controlli l’integrità delle
soluzioni e le ripari in base all’input rappresentante il grafo.
Nel capitolo 4 si presenteranno le motivazioni che hanno supportato il
metodo scelto e la spiegazione dello stesso. Si ricorda che l’obiettivo
delineato è la trattazione di una opportuna branca di problemi
multiobiettivo, di programmazione lineare e ottimizzazione combinatoria,
tramite l’identificazione di una strategia generica che permetta ad un
algoritmo genetico di lavorare con problemi di tali tipologie sfruttandone le
strutture. Il target viene ampliato alla costruzione di livelli di funzionamento
aggregabili, per la necessità di guardare all’ottimizzazione di problemi misti,
in cui la parte riconducibile alle singole strutture possa risultare essere solo
un sottoinsieme del problema totale.
40
4. Progettazione dell’algoritmo
Nel corso del capitolo 3 sono state analizzate e presentate le possibili
alternative che si possono adottare per affrontare le varie tipologie di
problemi rientranti nelle categorie individuate. Si ricorda quindi la presenza
di tre macro aree delineate dall’accorpamento dei caratteri simili che
definiscono i problemi di interesse:
Insiemi di vincoli lineari;
Variabili intere e binarie;
Strutture dati: permutazioni.
Bisogna quindi costruire un algoritmo genetico che possa trarre beneficio
dalla conoscenza a priori di questi possibili ingressi strutturati e lavori in
maniera standard per le altre tipologie di variabili in ingresso.
Ricapitolando si vuole costruire un GA che adotti diversi comportamenti in
base al tipo di variabili a lui sottoposte, prevedendo l’opzione di lavorare
anche con più tipologie allo stesso tempo. Viene in aiuto la struttura
particolarmente ben partizionata dei GA, la quale permette di definire delle
strategie diverse a livello degli operatori per governare in modo differente
sezioni del cromosoma di un individuo, meccanismo che favorisce una
applicazione parallela di più logiche di funzionamento. Sfruttando i concetti
introdotti nel capitolo 2 si veda il diagramma seguente proposto di
composizione:
41
1. Generazione di una popolazione iniziale;
2. Generazione nuova popolazione:
a. Selezionare una coppia di soluzioni genitori A e B;
b. Suddivisione dei cromosomi di A e B in gruppi rientranti nelle
categorie definite;
c. Applicazione del comportamento scelto ad ogni categoria
presente nella coppia di cromosomi.
3. Calcolo del valore di fitness per tutte le soluzioni/individui;
4. Verificare che il criterio di arresto sia soddisfatto, altrimenti tornare al
punto 2.
Questa struttura si può ricondurre per similitudine al funzionamento della
fase riproduttiva di un MOGA-II [25]; in cui gli operatori vengono applicati
in parallelo sul cromosoma in base ai parametri dell’algoritmo.
La domanda che può sorgere spontanea a questo punto è se ci sia qualche
indicazione teorica favorevole a questo tipo di approccio. L’obiettivo è creare
un GA generico che però assuma dei comportamenti potenzialmente più
idonei al presentarsi di determinate caratteristiche delle variabili in ingresso.
Intuitivamente possiamo presupporre che il comportamento standard in
assenza di tale condizione sarà da paragonarsi ad un qualsiasi GA blackbox
42
senza rivisitazione, ovvero che non sfrutta conoscenze a priori e che valuta
ogni punto dello spazio di ricerca al più una sola volta. Questa
generalizzazione del comportamento standard ci permette di chiamare in
causa il No Free Lunch Teorem [42]. Wolpert e Macready affermano, con tale
lavoro, che mediando sullo spazio di tutti i possibili problemi le prestazioni
di tutti gli algoritmi blackbox senza rivisitazione forniscono le medesime
prestazioni. Da esso si possono dunque ricavare due informazioni
estremamente importanti:
Se si inventa un nuovo algoritmo che pare essere il migliore per una
certa classe di problemi, il prezzo da pagare è l’esistenza di altre classi
di problemi per cui esso risulta sotto la media;
Per uno specifico problema è possibile aggirare il teorema del No Free
Lunch incorporando conoscenza specifica sul dominio nella soluzione.
Tali considerazioni giungono in risposta al quesito che ci si era posti poiché
ci permettono di dare un’impronta positiva all’approccio sopra descritto.
Esso infatti si comporterà in maniera generica per problemi che presentano
solo variabili non rientranti nelle tre categorie individuate, cosa che per il No
Free Lunch Teorem non comporta alcun tipo di svantaggio in termini di
prestazioni medie sull’intero orizzonte di problemi affrontabili. Invece per
istanze che propongono gruppi di variabili rientranti nelle categorie per cui è
previsto un raffinamento del comportamento dell’algoritmo, possiamo
affermare con ragionevole certezza che otterremo un comportamento
migliore sfruttando la conoscenza specifica a priori che esse portano. La
somma di queste due considerazioni finali ha fatto propendere il qui
presente lavoro per l’adozione di tale strategia di composizione per
l’algoritmo genetico in costruzione.
43
Prima di procedere con l’analisi effettiva dei metodi trovati per affrontare le
singole categorie di input strutturati è obbligatorio effettuare alcune
considerazioni che permetteranno di slegare le trattazioni specifiche dal
contesto globale; permettendo così una trattazione più semplice e leggibile.
Adottando la struttura di un algoritmo genetico si devono separare le
considerazioni sulle varie sue fasi, introdotte velocemente nel corso del
capitolo 2.1, e definire rigorosamente le relazioni fra le stesse. Una particolare
attenzione deve essere fatta per le relazioni con la fase di riproduzione degli
individui, ovvero quella che si sta andando a costruire. Si può suddividere il
flusso di un GA in cinque macro fasi senza tralasciare dettagli utili alle
seguenti considerazioni:
Generazione della popolazione
è una fase molto importante per una rapida convergenza
dell’algoritmo genetico, come da considerazioni già effettuate, ma non
è rilevante dal punto di vista del suo funzionamento in senso stretto.
Esso si può definire isolato dato che non ha relazioni dirette di
funzionamento con alcuna delle altre fasi;
Valutazione
Il calcolo della funzione di fitness ha un ruolo di primo piano nella
qualità delle capacità di ricerca del GA, e soprattutto sulla gestione dei
vincoli [6][7]. La letteratura è ricca di studi su tali tematiche ancora
aperte, e sulla gestione dei problemi multiobiettivo [18]. Il punto
importante però è che questa fase non è in alcun modo relazionata, in
senso di legami di struttura diretti, con l’applicazione gli operatori;
Riordino e selezione degli individui
Sono entrambe procedure che sicuramente possono influire sulla
qualità del risultato dell’applicazione degli operatori, ma ciò
44
nonostante non impongono alcun vincolo alla fase di nostro interesse.
Si lasciano dunque in secondo piano scelte inerenti: la dimensione
della popolazione, il numero di generazioni da computare, l’utilizzo
di elitismo e altre strategie velocemente introdotte nel capitolo 2.1.2 .
Controlli e Criteri di arresto
Come è intuibile essi determinano solo la durata dell’esecuzione
dell’algoritmo genetico, senza mantenere vincoli espliciti con nessuna
delle altre fasi.
Per esclusione la quinta fase risulta essere quella di nostro interesse: la
Riproduzione, ovvero dove verranno applicati gli operatori genetici e creati
quindi i nuovi individui. A seguito delle considerazioni sulle altre cinque
fasi, si può constatare che non ci sono vincoli diretti che impongano
accorgimenti particolari; nonostante la selezione e i metodi di generazione
della popolazione iniziale possano influire sul risultato degli operatori. È per
questo che nei prossimi paragrafi si procederà all’analisi dei metodi scelti per
affrontare le tre macroaree, circoscrivendo il discorso alle operazioni della
fase di riproduzione. Inoltre dalle considerazioni derivate dalla
composizione orizzontale del flusso di esecuzione, ereditate anche dalla
struttura degli operatori del MOGA-II [25], si potrà procedere a tali
spiegazioni in maniera mutuamente esclusiva e senza appesantire il discorso
con riferimenti obbligati alle tutte le altre categorie.
45
4.1. Insiemi di vincoli lineari
Questa categoria è forse quella che, anche intuitivamente, meglio si presta
all’aggiunta di metodologie specifiche e di considerazioni matematiche per la
semplificazione del problema sottoposto. Ci sono vari punti di forza che
permettono di adottare ragionamenti generali su insiemi di vincoli lineari
[31][32], ma i due principali sono:
La possibilità di avanzare deduzioni, effettuare calcoli e
semplificazioni sui vincoli stessi, cosa che negli altri casi (come di non
linearità) sarebbe impossibile;
Il punto più importante sfruttabile dalla struttura in analisi è che un
gruppo di vincoli di diseguaglianza lineari delinea sempre un insieme
convesso. Ed esso garantisce varie proprietà che possono essere
impiegate come base di partenza di calcoli nello spazio dei punti
interni all’insieme.
Oltre alle due considerazioni appena esposte si ricorda che sono disponibili
in letteratura anche molti metodi di semplificazione, eliminazione,
restringimento o aggiunta di vincoli lineari, chiamati Preprocessing [32][36],
ed hanno come obiettivo quello di rendere più efficienti i sistemi di vincoli
definiti nei problemi.
46
4.1.1.Sfruttamento della struttura lineare
In questo contesto è stato trovato, come miglior approccio aderente alle
esigenze dalla categoria in analisi, un algoritmo genetico singolo obiettivo
presentato da Michalewicz con il nome di Genetic Algorithm for Numerical
Optimization Problems, abbreviato a GENOCOP [11].
Esso prende in considerazione solo problemi che presentano in ingresso
vincoli lineari, sia di uguaglianza che di diseguaglianza. Non vengono invece
imposte limitazioni alla formulazione della funzione obiettivo. Il
funzionamento del Genocop è semplicemente riassumibile contando sul
supporto delle spiegazioni riportate nei capitoli precedenti. Si avvale di un
meccanismo matematico di riduzione del numero di variabili, esplicitandole
a partire dai vincoli di uguaglianza. Tale manovra lascia generalmente
l’istanza del problema priva di vincoli di uguaglianza e quindi solo con un
insieme di diseguaglianze. Importante sottolineare che un sistema così
composto produce per intersezione un insieme convesso. Da questa
considerazione, avvalorata dalla generazione di una popolazione iniziale
solo di individui ammissibili, si possono gestire gli operatori genetici in
maniera specializzata per sfruttare le proprietà dell’insieme convesso e
rimanere nella zona di ammissibilità del problema. Questo comporta dei
vantaggi enormi nella rapidità di esplorazione della regione ammissibile da
parte dell’algoritmo genetico. Vediamo ora in maniera sintetica il
funzionamento del nucleo logico del Genocop.
47
Algoritmo Genocop
Si definisce un problema di ottimizzazione come insieme di
Funzione obiettivo:
Dominio delle variabili:
Vincoli di uguaglianza:
Vincoli di diseguaglianza:
Si delinea la procedura di semplificazione delle uguaglianze con il nome di
“Elimination of Equalities” che opererà nel seguente modo:
preso un set di vincoli di uguaglianza si può suddividere A in
Si definisce quindi un nuovo set di diseguaglianze
Si suddivida a questo punto l’insieme di diseguaglianze di C
Il nuovo problema di ottimizzazione così delineato sarà composto da:
Funzione obiettivo:
Dominio delle variabili:
Vincoli:
48
Il mantenimento delle soluzioni all’interno della regione ammissibile è
possibile utilizzando il crossover algebrico [19]. Esso sfrutta la formulazione
della convessità per impostare il lavoro di incrocio dell’operatore, e viene
proposto anche nel corredo di operatori del GENOCOP [11].
I dettagli sulla formulazione degli operatori selezionati rientranti dell’ambito
di interesse sono già stati presentati più approfonditamente nella sezione
sugli operatori di crossover e mutazione, rispettivamente visti nel corso dei
capitoli 2.1.2.2.b e 2.1.2.2.c .
È stato dunque trovato un metodo di risoluzione che sembra adeguato ad
affrontare i problemi derivanti dalla presenza di uguaglianze per gli
algoritmi genetici, e si avvantaggia dalla struttura degli input sottoposti a
matrici di vincoli lineari senza collidere con il contesto applicativo.
Nonostante le ottime premesse però è necessario portare all’attenzione che
esso si muove esclusivamente in un ambito di ammissibilità, il che riduce
notevolmente le possibilità di applicazione generica e di automatizzazione
della procedura per istanze con input di varia natura. Fortunatamente
l’adattamento generale del GENOCOP a una generalizzazione con vincoli di
altro genere non è difficile, inoltre in letteratura si trovano altre due versioni
del sopracitato algoritmo. Il GENOCOP II sarà di scarsa utilità ai fini del
progetto, ma si è rilevato comunque utile per capire come la prima versione
dell’algoritmo potesse essere associata a meccaniche complesse quale il
Simulated Annealing [43]. Il GENOCOP III [12] invece applica una struttura
a due passi per la ricerca nello spazio delle soluzioni sull’insieme convesso
delineato dai vincoli lineari e successivamente inserisce un metodo genetico
standard per la ricerca delle soluzioni dell’intero problema, permettendo di
lavorare anche con vincoli non lineari. Questo approccio è semplice ed
efficace e viene adottato per la struttura base della soluzione ricercata in
49
questa sezione. Si veda ora in estrema sintesi il funzionamento del
GENOCOP_III facendo esplicito riferimento alla sua versione già presentata.
Esso si propone di ottimizzare un set di variabili decisionali
Lo spazio viene suddiviso nel seguente modo
search point space: regione ammissibile dei vincoli lineari
reference point space: regione ammissibile dell’intero problema
Il search point space è un politopo definito da
Aggiungendo vincoli si delimita :
Essi si dividono in quattro categorie, tipologia e linearità:
Equazioni Lineari LE Equazioni non lineari NE
Disequazioni lineari LI Disequazioni non lineari NI
L’algoritmo in esame opera normalmente su seguendo la procedura di
funzionamento della prima versione del GENOCOP, tentando di riparare le
soluzioni non appartenenti ad :
Soluzioni ammissibili
Soluzioni inammissibili
50
Esaminata dunque la struttura della terza versione dell’algoritmo si possono
notare delle peculiarità nella gestione della popolazione del reference point
space che non sono proprio in linea con le idee generali dei genetici. Inoltre
la possibilità di rimpiazzo va a modificare a mano le popolazioni all’interno
della stessa fase di riproduzione, potendo generare così delle riproduzioni di
individui nuovi; intuitivamente denominabile come balzo evolutivo. Si fa
notare che gli algoritmi appena presentati sono stati pensati solamente per le
ottimizzazioni singolo obiettivo, che non sono il target principale del
contesto di applicazione del progetto visto nel capitolo 2.2.
Siccome la struttura optata trae notevoli benefici dai domini delle variabili
contenute, dato che mantiene i valori delle stesse all’interno dei limiti
imposti, e che sfrutta meticolosamente l’insieme di vincoli lineari per
avvantaggiare l’evoluzione genetica, si rivela decisamente importante
sottoporgli istanze di problemi ben formulate. Per questo diventa
notevolmente rilevante la fase di semplificazione del sistema di vincoli e
dunque la possibile fase di preprocessing.
51
4.1.2.Preprocessing
I meccanismi rientranti sotto la nomenclatura di preprocessing hanno come
scopo generale la riduzione della dimensione dell’istanza del problema.
Infatti la complessità di risoluzione di un problema è largamente influenzata
dalla numerosità delle sue variabili e dei vincoli. Riuscire a ridurne il numero
dei secondi citati quindi può portare dei grossi benefici in termini
computazionali e di rapidità di convergenza. Importante spiegare che le
procedure rientranti nel preprocessing sono generalmente sequenze di
semplici operazioni iterate opportunamente al fine da trovare possibili
semplificazioni. A sua volta un sottoinsieme di singole procedure o
dell’intero procedimento può venir iterato per garantire una ricerca più
efficace di possibili semplificazioni multiple.
Si procede ora ad una rapida panoramica degli obiettivi esatti ricercati da
tale metodo di riduzione e quali tipi di procedure possono venir prese in
considerazione nell’ambito del lavoro attuale:
Restringimento dei vincoli sulle variabili;
Inserimento di vincoli logicamente vantaggiosi;
Rendere costanti variabili tramite assegnamento;
Rimozione di vincoli ridondanti o privi di informazione;
Rilevare casi di problemi che non ammettono soluzioni.
Per effettuare ciò esistono numerose tecniche diverse, applicabili a livelli
differenti. Risulta banale ma doveroso sottolineare l’impossibilità di avvalersi
di tutte le tecniche di preprocessing che analizzano e sfruttano la funzione
obiettivo del problema per operare, questo a causa del contesto di
applicazione in ambito di ottimizzazione industriale.
52
Sono state introdotte, nel flusso creato per il preprocessing, delle possibili
fasi aggiuntive per sfruttare ulteriormente la struttura che verrà
effettivamente sottoposta all’algoritmo in costruzione. Questi prendono in
considerazione i limiti di dominio imposti ad ogni variabile in ingresso per
renderli più stringenti, se l’insieme di vincoli ne preclude comunque la
possibilità di assegnamento totale. Si veda ora la catena di procedure che
sono state scelte, ricordando che si potrà decidere di iterarne alcune,
sottogruppi o tutte a momento debito:
Eliminazione dei Singleton
Consta semplicemente nel ricercare vincoli banali in cui compare una
singola variabile decisionale e farne assorbire l’informazione dai
rimanenti vincoli;
Aggiornamento dei limiti inferiori e superiori delle variabili
Si tratta di effettuare considerazioni sui vincoli lineari e controllare i
valori minimi e massimi assumibili dalle variabili, questo per
confrontarli poi con i vincoli specifici di dominio (limite superiore e
inferiore della variabile);
Controllo presenza di vincoli privi di significato
Può succedere che considerazioni effettuate esplicitando variabili nella
disequazione portino in evidenza vincoli che sanciscono relazioni fra
53
le variabili già presenti in altri, oppure restrizioni equivalenti ma più
permissive di altre già incluse nell’insieme;
Aggiornamento vincoli
Generalmente si effettua una modifica restrittiva dei termini noti a
seguito di considerazioni similari a quelle applicate nel restringimento
dei domini delle variabili;
Restringimento dei vincoli
Operazione che mira a effettuare delle modifiche ai coefficienti e dei
termini noti nei vincoli, senza alterare però i legami proporzionali fra
le variabili da essi sanciti;
Procedura di semplificazione logica delle diseguaglianze
Forse la procedura più complessa che è stata presa in considerazione,
essa si articola nelle tre fasi evidenziate nel diagramma: generazione
di nuove diseguaglianze con criteri logici specifici, confronto a coppie
del nuovo insieme di vincoli espansi, semplificazione.
Se ci si sofferma a riflettere sulle prime quattro fasi evidenziate, esse
acquisiscono peso se l’intero flusso viene ripetuto iterativamente. Ogni
modifica di una delle singole fasi potrebbe aprire la possibilità di
individuazione di nuove semplificazioni anche per le successive. Nel
contesto in esame è accettabile dedicare un quantità di tempo di calcolo
importante al preprocessing, data la presenza del collo di bottiglia
computazionale che si crea durante le valutazioni dei singoli design.
54
4.2. Variabili intere e binarie
La seconda categoria individuata tratta le variabili a valori interi e binari,
esse purtroppo si presentano in modo ricorrente nei problemi di
ottimizzazione reale e non esistono sempre metodi di risoluzione efficaci.
Queste categorie di problemi sono individuati dalla sola presenza di variabili
il cui dominio appartiene all’insieme dei numeri razionali o interi. Invece si
può definire un problema di ottimizzazione binaria sulla presenza di
variabili decisionali che possono assumere solo valore di zero e di uno. Si
nota che da un punto di vista operativo sarebbe possibile definire un
problema binario come intero, inserendo ad ogni variabile razionale un
dominio compreso tra zero e uno inclusi. La caratteristica fondamentale di
tali problemi è quindi quella di avere insiemi ammissibili discreti, a
differenza dei classici problemi di programmazione lineare in cui l’insieme
ammissibile è continuo. Ciò comporta la necessità di tecniche d’ispezione
dello spazio delle soluzioni che agiscano in modo differente per problemi di
ottimizzazione intera e binaria.
Il nucleo del discorso è che la restrizione intera alle variabili decisionali in
questi problemi causa un tremendo aumento della difficoltà risolutiva dei
classici metodi che cercano soluzioni ottime o quasi-ottime. Il metodo più
popolare in letteratura risulta essere il Branch and Bound. Esso è un
algoritmo di risoluzione esponenziale che procede partizionando lo spazio
delle soluzioni in sottoinsiemi più piccoli, e risolvendo il problema di
ottimizzazione su ogni sotto-insieme. Questo viene fatto ricorsivamente,
dividendo a loro volta le regioni ammissibili dei sotto-problemi in
sottoinsiemi. Se tale ricorsione venisse svolta completamente, alla fine si
enumererebbero tutte le possibili soluzioni del problema. Questo presenta
55
due problemi: prima di tutto, se il problema ha infinite soluzioni ammissibili
l’enumerazione completa non é possibile, e anche se la regione ammissibile
contenesse un numero finito di punti, tale numero potrebbe essere
esponenzialmente grande; quindi enumerarlo richiederebbe un tempo non
sostenibile se non per istanze estremamente ridotte. L’algoritmo del Branch
and Bound cerca di esplorare solo aree promettenti della regione
ammissibile, mantenendo una limitazione superiore e una inferiore del
valore ottimo della soluzione in una certa area, e cercando di utilizzare tali
vincoli per scartare a priori certi sotto-problemi. Questo permette di ridurre,
in maniera rilevante, lo spazio di ricerca delle soluzioni per istanze di
problemi che soddisfano la legge della dispersione.
D’altro canto in queste tecniche si prevede di processare in maniera isolata
l’intera esecuzione dell’algoritmo, e non ci sono garanzie di funzionamento
nel caso questo processo venga operato congiuntamente all’interno di un
ambiente che preveda più tipi di variabili strutturate. Giunge in aiuto il
contesto di applicazione del lavoro qui esposto, il quale prevede un input
medio composto da un numero di variabili relativamente limitato ed
eterogenee. Ciò permette di svicolare dai problemi che risultano intrattabili
per colpa di una crescita di ordine di grandezza del numero di variabili
decisionali, e quindi la raggiunta dei punti critici di questa categoria. In un
ambito definito da euristiche evoluzionistiche, come quello che viene scelto
per il presente lavoro di tesi, alcune interessanti opzioni specifiche vengono
messe in evidenza nell’articolo di Deb, Reddy e Singh [34] che presentano un
possibile algoritmo genetico personalizzato per i problemi in esame.
Di particolare ispirazione è stata anche la trattazione successiva di Pal e Deb
[33] in cui analizzano in maniera esaustiva più metodi differenti per
approcciare problemi interi anche di grandi dimensioni con gli algoritmi
56
genetici. In essi si introduce un raffinamento del lavoro precedente con
l’aggiunta di tre metodi decisionali su un particolare metodo di
riproduzione, presentato come vasca di ricombinazione genetica.
Anche in questi due lavori il punto fondamentale rimane però la
specializzazione degli operatori dell’algoritmo.
Se si sommano le considerazioni già formulate ai problemi applicativi legati
allo sviluppo effettivo del progetto, risulta che in tutte le opzioni evidenziate
nel capitolo 4.1, si richiederà uno strato di logica separato legato ai valori
ammissibili delle variabili. Valutazione che, congiunta alla delineazione di
una casistica a parte per permutazioni, riduce di molto l’importanza
dell’adozione di metodologie dedicate a questa categoria nel presente
progetto, almeno in un primo momento. Viene quindi deciso di valutare nel
corso dello sviluppo degli operatori specializzati, presentati nelle numerose
fonti bibliografiche elencate per migliorare le prestazioni, ma tuttavia
limitare la strategia per affrontare questa categoria alla semplice possibilità
di sottomissione di variabili in essa rientranti. Ovvero, almeno nel primo
approccio, si ritiene che uno strato logico che permetta una corretta gestione
delle variabili intere e binarie, unita alla presenza della successiva categoria
delle permutazioni, sia sufficiente per fornire le basi su cui testare le
potenzialità dell’insieme e di eventuali operatori genetici specializzati.
57
4.3. Permutazioni
L’idea di isolare le permutazioni nasce da un iniziale approfondimento sulle
strutture dati ricorrenti nei problemi affrontati dalla ottimizzazione
combinatoria [31][32][36], visti anche in un’ottica di utilizzo con gli algoritmi
genetici [44]. Esse possono venir viste come una particolare codifica di
problemi combinatori che presentano un insieme estremamente vincolato di
variabili decisionali. Si possono chiamare in causa tipologie di problemi
molto famosi quali il problema dello zaino e tutti quelli che possono essere
schematizzati tramite una rappresentazione su grafo. La rappresentazione
delle soluzioni come vettore contenente una disposizione di un numero finito
di elementi del dominio delle variabili decisionali è una scelta vastamente
utilizzata in letteratura, specialmente nelle risoluzioni euristiche evolutive
[14].
Si tiene a segnalare l’ottima trattazione di una vasta gamma di possibili
codifiche per problemi di TSP ad opera di Michalewicz [7]. Da essa è stato
possibile ponderare con una visione di insieme i benefici e gli svantaggi che
una particolare codifica porta rispetto ad un’altra. Infatti si è deciso di
adottare delle strutture che verranno denominate permutazioni.
La possibilità di altri approcci è stata vagliata ma, ad esempio, l’adozione di
decoder che operino una codifica biunivoca delle soluzioni in variabili
singole creano delle inevitabili perdite di informazioni. Alcuni esempi
possono essere lo smarrimento della nozione di vicinanza fra specifiche
soluzioni, oppure l’ordinamento delle soluzioni iniziali potrebbe non avere
senso rapportato a quello della codifica una volta inserito nei ragionamenti
che muovono gli operatori genetici. La distanza fra soluzioni però è un
dettaglio che interessa mantenere ben inquadrato anche nella definizione di
58
un metodo che sfrutti la struttura dati delle permutazioni per operare la
ricerca nello spazio delle soluzioni. A questo fine si sono studiate diverse
possibilità per l’adozione di una distanza fra le soluzioni e, in caso, per
includere queste considerazioni nella logica di funzionamento di eventuali
operatori genetici specializzati o procedure di riparazione delle soluzioni.
È stata trovata una ottima trattazione in letteratura; uno studio che mette a
confronto vari tipi di distanze sul confronto fra stringhe applicate al name-
matching [45]. Fra queste erano presenti la distanza operativa di
Levenshtein, il coefficiente di similarità di Jaccard e altri metodologie ibride.
Vengono tenute in considerazione le due esplicitamente sopra citate e la
distanza di Hamming. Ciò potrà essere utilizzato nei criteri interni di
funzionamento di riparatori, operatori o metodi di miglioramento locale per
la categoria in analisi.
Procedendo con la progettazione dell’algoritmo genetico, che si sta
delineando mediante l’approfondimento di ogni singola componente, sono
emersi dei punti importanti che hanno avuto un peso rilevante nella
definizione della soluzione di questa ultima categoria. Infatti l’unica strategia
efficace di utilizzo di una codifica effettuata in un vettore permutazione è
l’impiego di metodi per mantenersi nelle soluzioni strutturalmente valide,
per poter usufruire poi della possibilità di inserire operatori specializzati più
consoni ad una corretta esplorazione spaziale. Le motivazioni di tale scelta
sono già state ampiamente discusse nel corso del capitolo 3.
Per l’utilizzo della categoria delle permutazioni si sceglie di adottare un
sistema di riparazione per mantenere gli insiemi di variabili decisionali in
linea con i vincoli strutturali che determinano questa partizione degli input,
ad esso ci si riferirà da qui in poi con l’appellativo di “fixer”. A tal fine
verranno decise in seguito delle logiche di riparazione che limitino la
riproducibilità della medesima soluzione valida a partire da una stessa
59
configurazione errata. Inoltre si vaglierà se implementare meccaniche legate
alle nozioni di distanza fra stringhe applicate a vettori di variabili decisionali.
È stata dunque deciso di adottare l’inserimento di un metodo generico
supportato da una procedura di riparazione a valle, possibilità illustrata nel
capitolo 3. Il metodo di riproduzione degli individui sarà raffinato in
maniera incrementale, ovvero sarà impostato un primo approccio dedito
all’utilizzo di semplici operatori standard; quali il crossover a singolo punto
di taglio e la mutazione uniforme. Tale scelta è stata presa al fine di poter
valutare l’effettiva efficacia della procedura di fixing, lasciando ad un passo
successivo il compito di inserire operatori specializzati. Questo perché
l’inserimento combinato di procedure quali il fixer e operatori custom
avrebbe potuto falsare i risultati soffrendo l’imparzialità portata dalla
caratteristica efficacia decisamente dipendente dal problema degli operatori
specializzati.
L’approccio decretato di riparazione ad ogni costo delle soluzioni però
potrebbe non essere in linea con la mentalità, già ampiamente esposta, degli
algoritmi euristici evolutivi. Viene incontro a tale idea la teoria
evoluzionistica definita da Lamarckian, espressa chiaramente nell’articolo
citato [9]. Tale approccio di riparazione nei genetici viene poi ampiamente
motivato e utilizzato anche nei lavori di Michalewicz [7]. La stessa meccanica
di funzionamento del GENOCOP III potrebbe essere vista in una ottica di
riparazione delle soluzioni; dopotutto le due popolazioni utilizzate per la
ricerca delle soluzioni operano in modo indipendente. In tale scenario la
procedura analoga al fixing potrebbe essere individuata nel livello che tenta
di creare un individuo ammissibile partendo dall’ammissibilità lineare e
cercando di arrivare a quella globale. Questo perché nella procedura solo le
soluzioni effettivamente ammissibili per il problema vengono accettate per la
reale popolazione, ovvero quella della reference point space [12].
60
La strategia è stata delineata ma rimane aperto un interrogativo ereditato
dalla struttura degli algoritmi genetici, ovvero dalla utilità di esplorare
qualche soluzione non ammissibile per convergere verso soluzioni ottime:
quanto è meglio riparare?
Definita quindi l’accettabilità delle riparazioni, bisogna stimare in che
quantità sarà consono applicare il fixer alle soluzioni non ammissibili.
Intuitivamente questa percentuale di applicazione avrà sicuramente un
limite inferiore sotto il quale non avrà senso riparare meno. Anche in questo
caso si è provveduto a cercare approcci e studi similari in letteratura. Tale
operazione ha portato alla luce lo studio di Davis sull’utilizzo di algoritmi
genetici con funzioni di riparazione per problemi di ottimizzazione vincolati
[17]. Fortunatamente parte della trattazione verteva su istanze di problemi di
ottimizzazione combinatoria e giungeva alla conclusione che, in seguito a
numerosi test, fosse sempre preferibile riparare una percentuale inferiore al
cento per cento delle soluzioni. Il parametro di riferimento del lavoro di
Davis però era riferito all’applicazione di operatori specializzati e una
percentuale di riparazione del cinque per cento, conclusione che ci permette
di estrapolare informazioni importanti; ma che non può essere applicata
direttamente al metodo scelto per affrontare la categoria in analisi.
Concludendo quindi si è deciso di adottare una struttura di riproduzione
che:
Si basi su operatori standard, incrementabile in un secondo momento
con operatori specializzati;
L’impiego massivo di una procedura di fix per riportare la
maggioranza delle soluzioni non ammissibili nello spazio delle
soluzioni ammissibili con metodi che garantiscano la non univoca
riparazione;
61
L’applicazione del punto precedente verrà utilizzato su una
percentuale delle soluzioni sottoposte, maggiore di zero e minore del
cento per cento. Particolare attenzione sarà da attribuire, in una
seconda fase, nella fascia delineata dalla letteratura compresa fra il
cinque e il quindi per cento.
La trattazione specifica dei vari passi dell’algoritmo è stata completata, ora si
vuole costruire effettivamente lo schema generale di funzionamento
rimanendo in linea con le decisioni prese, il contesto evidenziato e la
struttura degli algoritmi genetici. Si presenta quindi a seguire una coppia di
diagrammi, in figura 4.1 e 4.2, che portano in luce il funzionamento globale e
i livelli di aggregazione di tutte le considerazioni fatte fino ad ora. È
importante sottolineare il fatto che il diagramma nella figura 4.2, della
schedulazione, rappresenta il flusso iterativo dell’algoritmo genetico,
approfondendo nel dettaglio la penultima componente del diagramma 4.1.
62
Fig. 4.1 - Diagramma del flusso principale
63
Fig. 4.2 - Dettaglio della fase di schedulazione
64
5. Realizzazione dell’algoritmo
Lo sviluppo effettivo dell’algoritmo delineato nel corso del capitolo 4 ha
richiesto una evoluzione del codice progressiva, in cui si può individuare
una successione di punti cardine. Essa è stata possibile poiché la struttura
evidenziata presenta molti nodi di congiunzione fra tecniche diverse che
realizzano però la stessa fase nell’algoritmo. Inoltre gli algoritmi genetici
sono particolarmente indicati per le costruzioni isolate delle varie fasi poiché
ognuna di esse può esser vista come una scatola a se stante con determinati
input e output, cosa che si è rivelata particolarmente utile dato che il
linguaggio di programmazione utilizzato è stato Java.
Viene omessa la descrizione dettagliata delle fasi preliminari alla
composizione vera e propria dell’Algoritmo Genetico MultiObiettivo per
problemi con Input Strutturati, a cui per semplicità ci si riferirà d’ora in
avanti con l’acronimo MOGASI. Tali fasi consistevano in sviluppo di codice
mirato a punti specifici o al test di varie metodologie di risoluzione andate
poi scartate, e quindi di scarso interesse per l’approfondimento nei dettagli
del progetto realizzato.
5.1. Elimination of Equalities
L’effettiva struttura del MOGASI è andata a delinearsi partendo
dall’esoscheletro dell’algoritmo di Michalewicz, il GENOCOP nella sua
prima versione. Da esso è stata prelevata la procedura dell’Elimination of
Equalities e sopratutto la struttura matriciale che veniva fabbricata, come
ingresso dell’algoritmo, in base alla combinazione dei vincoli lineari del
65
problema sottomesso. Tale matrice è stata mantenuta con il nome originale di
Final Matrix ed è composta come segue:
Che risulta essere una composizione verticale di tutti i prodotti della
procedura di Elimination of Equalities descritta in precedenza durante
l’approfondimento dell’approccio GENOCOP. Importante specificare che
tale matrice presenta righe con n cardinalità dell’insieme delle variabili
lineari appartenenti al gruppo , ovvero quelle non eliminate. Quindi nella
prima sezione della stessa, si troveranno i limiti inferiori e superiori
rispettivamente in prima e in ultima posizione, mentre al centro sarà
presente una mappa di zeri e uni che indicherà a quale variabile è riferita la
coppia di limiti della riga. Nella seconda sezione, avendo appena spiegata la
disposizione nel primo caso, i limiti inferiori e superiori saranno nuovamente
in prima e ultima posizione, mentre all’interno saranno presenti i coefficienti
degli con , ottenuti sempre dalla semplificazione a monte. Infine
nella terza parte è importante sottolineare solo l’assenza di una limitazione
inferiore, che viene imposto di default al valore minimo assumibile da una
variabile dell’ambiente di lavoro.
L’importanza di questa matrice viene messa in evidenza una volta spiegato
che ogni operazione, quando vuole agire su un valore di una qualsiasi delle
variabili decisionali lineari, estrapolerà da essa i valori dei limiti applicabili
per tale operazione. Proprio per questo motivo si è deciso di prestare molta
attenzione nella cura e nella manutenzione di tale matrice durante
l’evoluzione dell’algoritmo.
66
5.2. Preprocessing
Vista la decisione di inserire una procedura di preprocessing, si è ritenuto
opportuno applicarne i concetti direttamente all’intera matrice denominata
“Final Matrix”, dato che essa conteneva tutte e sole le informazioni di cui le
tecniche selezionate necessitano.
La prima versione della procedura di preprocessing implementata consiste in
una applicazione ciclica di sole due componenti fra le sei proposte come
candidate nel capitolo 4.1.2. Tale riduzione si è effettuata per capire le
possibilità dell’approccio di semplificazione preventiva in un contesto
applicativo di ottimizzazione nuovo, e per evitare di sviluppare da zero una
procedura di preprocessing estremamente complicata prima di scoprire se i
problemi su cui si sarebbe andati ad operare sarebbero stati efficacemente
semplificabili. Vengono dunque selezionate le sole fasi di aggiornamento dei
limiti inferiori e superiori e dei vincoli. Data la struttura particolare della
final matrix si è ampliata l’applicazione dell’aggiornamento dei vincoli
andando a ritoccare anche il vincolo fittizio introdotto solo per questioni
operative della matrice. Ad ogni iterazione viene controllato su ognuno dei
vincoli se le limitazioni attuali delle variabili decisionali applicate
opportunamente permettono un valido restringimento dei termini noti in
entrambe le direzioni. A questo viene fatto seguire un procedimento di
esplicitazione delle variabili decisionali da ogni vincolo che, applicando in
maniera simile il ragionamento coi limiti delle altre variabili decisionali,
permette di controllare la presenza di possibili restringimenti dei singoli
domini. L’insieme delle due procedure viene iterato con un criterio di stop
condizionato su due fattori: la coppia di procedure è stata già applicata per
cinquanta volte, oppure nell’ultima iterazione non è stato possibile effettuare
alcuna modifica ai vincoli del problema.
67
Si è potuto notare durante i test che anche solo l’applicazione sistematica
delle due procedure più semplici ed intuitive, ha portato comunque in
numerosi casi ad un restringimento dello spazio delle soluzioni e quindi
dell’insieme convesso su cui l’algoritmo opera la ricerca. Determinando un
buon vantaggio sul confronto prestazionale con lo stesso GENOCOP.
Nell’esecuzione della procedura di preprocessing è stata prevista la
compilazione di un file di log che tenesse traccia di ogni operazione di
semplificazione applicata per poter approfondire l’analisi. Ciò si è rilevato
determinante per individuare una possibilità di miglioramento decisamente
importante. Si presentavano con alta frequenza comportamenti di
aggiornamenti ciclici che saturavano il numero massimo di applicazioni per
modifiche di ordine irrisorio. Tale fenomeno è stato eliminato
dall’introduzione di un controllo parametrizzato con un ordine di precisione
definito a priori come input del programma. L’adozione di tale parametro di
funzionamento ha permesso di aggregare alcune ricorsioni di aggiornamento
e di ignorarne altre, velocizzando dunque il preprocessing e lasciandolo
libero di sfruttare in modo più efficace il numero massimo di iterazioni
disponibili.
68
5.3. GENOCOP III
Risultava essenziale, per la risoluzione della prima categoria individuata
degli input strutturati, l’applicazione della logica evolutiva contenuta nella
terza versione del GENOCOP per istanze con vincoli anche di tipo non
lineare. Tale implementazione non si è rivelata particolarmente semplice
poiché gli esempi di codice del GENOCOP III disponibili erano circostanziati
dalle istanze che dovevano presentare e quindi il codice non era
generalizzato. Inoltre occorre sottolineare che non era presente una istanza
esemplificativa di problemi con vincoli lineari e non lineari che richiedessero
l’ausilio della procedura di Elimination of Equalities.
Nonostante il sorgente disponibile fosse stato fornito in linguaggio C è stata
sufficiente una completa traduzione in Java del codice originale e una
progressiva integrazione dei due punti precedentemente analizzati per
ottenere una versione prototipale funzionante del blocco che serviva al
MOGASI. In tale sede si è rilevato, effettuando i test di funzionamento, il
comportamento atipico che assumeva l’aggiornamento della popolazione
della reference point space. Infatti, come si è già spiegato in dettaglio nel
corso del capitolo 4.1.1, un individuo veniva sostituito dal figlio generato
dall’incrocio di se stesso con un elemento della search population, ma solo se
la valutazione del figlio superava quella del padre. Per effettuare un
confronto del genere si sarebbe dovuti ricorrere alla valutazione del nuovo
individuo; cosa non solo delocalizzata ma addirittura improponibile nel caso
di problemi multiobiettivo con gestioni similari all’NSGA-II, descritto nel
capitolo 2.1.3 .
Dopo attente analisi si è ritenuto meglio svincolare un così rigido
comportamento e ricondursi ad una gestione delle popolazioni più classica,
69
in cui ogni nuovo elemento ammissibile viene aggiunto momentaneamente
nella popolazione. Essa verrà poi regolarmente valutata e riordinata secondo
i criteri adottati, nella fase dedicata a tale procedura, per poi venir
ridimensionata alla sua dimensione fissata dal parametro apposito in input
all’algoritmo. Questo approccio incrementa già da un punto di vista intuitivo
la capacità di evoluzione della popolazione del reference point space. Per
quantificare però anche materialmente il miglioramento si propone
l’andamento ottenuto dall’applicazione del GENOCOP III al problema di
Keane con venti variabili denominato “t02”, i cui dettagli saranno disponibili
nel capitolo 6.1. Si può vedere dal grafico seguente che la rapidità di
convergenza al valore ottimo prossimo a 0.8 cambia radicalmente
dall’utilizzo originario del GENOCOP III (in grigio) e l’impiego della
valutazione e dello sfoltimento a posteriori (in rosso).
70
Tale miglioramento verrà poi messo in luce dai risultati conseguiti durante le
fasi di test, che verranno analizzati con la dovuta cura nel capitolo 6.
Viene presentato a seguire un diagramma di flusso che esplicita in maniera
dettagliata il funzionamento del nucleo logico del GENOCOP III così come è
stato implementato.
Diagramma di funzionamento della logica GIII
71
5.4. Paradigma a oggetti
Dettaglio di secondaria importanza per i contenuti algoritmici del codice, ma
di notevole peso da un punto di vista operativo, è stata l’evoluzione del
programma da un punto di vista del paradigma di programmazione
impiegato. Si pone in evidenza che inizialmente la struttura generale era
stata ereditata da traduzioni ed evoluzioni di codici C in Java. Le modifiche
successive raccontante in dettaglio nei paragrafi precedenti del capitolo 5
erano state applicate per comodità nello stesso stile di programmazione.
Al momento di dover però stratificare e generalizzare l’algoritmo anche alle
altre categorie di variabili e modificarne i comportamenti per istanze di
problemi multi obiettivo, si è preferito effettuare una riscrittura completa del
codice. Questo ha permesso di adottare un paradigma ad oggetti che ha
valso una semplificazione davvero degna di nota. Tale miglioria è stata
possibile grazie alla gestione interna agli oggetti della casistica di
funzionamento e del mantenimento allineato delle informazioni richieste agli
individui, cosa ben più importante data la struttura.
Il secondo punto di forza dell’approccio si è concretizzato in particolare nella
creazione dell’oggetto individuo denominato “Design”, che mantiene
consistenti le informazioni degli elementi della popolazione. Le possibili
ripercussioni, di una semplificazione operativa del genere, diventano forse
più chiare se si pensa alla possibilità di lavorare su un insieme ridotto delle
variabili decisionali dopo la procedura di eliminazione delle uguaglianze.
Questo sottoinsieme deve essere reso disponibile e mantenuto allineato per
tutte le procedure che modificano i valori delle variabili; al contempo invece
altre operazioni hanno bisogno del cromosoma completo per poter essere
applicate, che deve essere ricostruito adeguatamente in base alle modifiche
più recenti apportate.
72
Inutile dire che la costruzione di un sistema ad oggetti semplifica
incredibilmente anche la difficoltà di stratificazione delle metodologie scelte
per le categorie di variabili, obiettivo principale della adozione del
paradigma. Similarmente al discorso del paragrafo precedente, il
mantenimento e la gestione vengono lasciate agli oggetti dello strato interno,
come per l’appunto il “Design”, mentre le procedure algoritmiche si
interfacciano ad esse tramite richieste e notifiche di modifica. Questo
permette di scrivere liberamente il codice delle varie categorie di variabili
senza preoccuparsi dell’intera casistica possibile in esecuzione, lasciando il
compito alle classi interne di memorizzare, mantenere allineati i dati e
preoccuparsi di aggiornarsi nel caso di richieste di dati non pronti.
5.5. Logica Multi obiettivo
Al momento di dover implementare la logica multi obiettivo dell’algoritmo
ci si è trovati di fronte a varie opzioni aperte. Come visto nel corso del
capitolo 2.1 esistono molti approcci per affrontare un problema con più
funzioni obiettivo. Allo stesso modo ne concorrono altrettante per la gestione
dei vincoli nella valutazione della funzione di fitness e nella generazione di
una classifica degli individui. A tal fine si è preferito orientarsi verso le
strategia multiobiettivo propria degli algoritmi genetici, scartando a priori
opzioni come le combinazioni lineari pesate (affrontabili comunque
sottoponendo a mano un singolo obiettivo composto e pesato all’algoritmo) o
di penalizzazione fissa delle violazioni dei vincoli.
Dopo attenta analisi delle alternative si è optato per l’adozione delle tre
procedure che individuano la metodologia proposta da Deb per la
risoluzione multi obiettivo [24]:
73
La funzione di rank degli individui
Il calcolo delle crowding distance
L’operatore di confronto fra soluzioni
Queste tre procedure sono già state esaustivamente spiegate nel capitolo
2.1.3, durante l’analisi dell’algoritmo NSGA-II, quindi si eviterà di
soffermarsi eccessivamente su dettagli di funzionamento già visti preferendo
spiegare solo alcuni dettagli implementativi. Le procedure di calcolo delle
crowding distance e l’operatore di confronto sono state implementate
attenendosi scrupolosamente a quanto riportato nell’articolo sopra citato.
L’unica differenza è sorta sviluppando autonomamente la funzione che
suddivide la popolazione in fronti. Si è preferito utilizzare una struttura a
segnaposto con liste di dominanza che permettono di effettuare i confronti di
tutti gli individui della popolazione una unica volta, per poi costruire i fronti
di dominanza a partire dalle informazioni raccolte nei segnaposto.
Si conclude questa parentesi sulla gestione multiobiettivo del MOGASI
quindi, assicurando che la logica algoritmica di tale fase non è stata
modificata e dunque eredita le caratteristiche dell’algoritmo NSGA-II.
74
5.6. Fixer per le variabili intere
La creazione di un meccanismo di riparazione per gli individui si è rilevata
semplificata in larga misura dall’adozione del paradigma ad oggetti. Viene
evidenziato dai diagrammi di flusso, che esplicano il comportamento
generale dell’intero algoritmo, l’utilizzo di tale procedura come blocco a valle
delle operazioni che possono introdurre individui invalidi. Questa
separazione semplifica notevolmente il codice che dovrà effettivamente
sapere solamente quali sono le variabili che deve controllare, verificarne la
validità dei valori e in caso negativo ripararle. Per la prima fase viene
impostata una semplice mappa binaria che mantiene le informazioni di quali
variabili siano intere per la procedura di fixing. Per quanto riguarda la
verifica sarà estremamente semplice per la categoria in questione, e non si
ritiene di dover scendere nel dettaglio del controllo dell’interezza di un
valore. Infine per la correzione effettiva dei valori non validi viene fornito
l’accesso alle informazioni contenute nei vincoli lineari e dei limiti del
dominio della variabile da riparare alla procedura di fixing. In questo modo
si potrà procedere ad una scelta del valore che soddisfi i classici criteri di
arrotondamento cercando al contempo di evitare di uscire erroneamente
dallo spazio di soluzioni del problema.
La qui presente procedura viene fusa con quella che sarà evidenziata nel
capitolo 5.7 visto il momento di applicazione all’interno della logica
dell’algoritmo, costruendo così un unico punto di riparazione degli individui
prima della valutazione dei cromosomi.
75
5.7. Fixer per le Permutazioni
L’ultimo punto saliente dei dettagli implementativi del codice dell’algoritmo
genetico prodotto in questo lavoro di tesi riguarda la procedura di
riparazione delle permutazioni.
Per come è stata definita una permutazione, essa rappresenta un vettore di
valori presi dal dominio della variabile. D’ora in poi si farà sempre
riferimento all’insieme di tutto il vettore come alla “variabile di
permutazione”.
Si definisce quindi come configurazione errata dei valori all’interno della
variabile permutazione con dominio intero, la presenza di almeno due valori
uguali. Per questo motivo l’unico metodo per individuare le variabili da
riparare è una ispezione diretta del contenuto delle stesse tramite un
confronto fra gli elementi. Però per permutazioni che accettano disposizioni
senza ripetizioni di un numero molto alto di variabili questo porterebbe ad
un tempo di calcolo proibitivo. Accorre in aiuto della possibile problematica
il contesto applicativo in cui raramente vengono sottoposte variabili in
numero superiore al centinaio. Questo permette alla procedura di
riparazione di effettuare i calcoli con la dovuta accortezza senza preoccuparsi
eccessivamente dei vincoli temporali, soprattutto grazie alle considerazioni
inerenti la natura delle funzioni di fitness che vengono richieste nello
standard dei problemi di ottimizzazione industriale. Constatato quindi di
avere la possibilità di eseguire operazioni disponendo del tempo necessario,
si tiene comunque a sottolineare che tali procedure sono semplici funzioni
matematiche di rapido svolgimento. Esse infatti si prestano facilmente ad
ottimizzazioni di prestazioni, potendo beneficiare delle strategie classiche di
ordinamento, parallelizzazione e di ottimizzazione dei tempi di calcolo.
76
Un esempio di miglioramento delle prestazioni durante l’implementazione è
stato l’utilizzo combinato di strutture dati del linguaggio Java per velocizzare
la gestione dei valori validi del dominio delle variabili permutazioni.
Il primo controllo da implementare era la presenza di valori ripetuti
all’interno della variabile. Esso è stato eseguito con la classica strategia di
confronto a coppie eseguito al più una volta, adottando l’idea di base del
celebre problema delle strette di mano, mantenendo la complessità del
controllo a sub quadratico. Questo controllo viene fatto utilizzando il vettore
come un array ciclico iniziando i confronti da un punto deciso casualmente
in modo tale che la procedura di fixing applicata a due individui uguali
difficilmente produrrà il medesimo vettore pulito. Per vettore pulito si
intende una variabile in cui i valori replicati vengono sostituiti da segnaposto
invalidi per il dominio della permutazione, lasciando ovviamente una
singola volta il valore in partenza ripetuto nella variabile.
Sfruttando come punto di partenza le strutture di Java che mantengono
l’unicità degli elementi in esso contenuti e su cui sono presenti una vasta
gamma di funzioni disponibili, si procede allo sfoltimento di un dominio
temporaneo della permutazione dai valori già presenti nell’individuo. Per
poi applicare dei mescolamenti casuali della collezione risultante da cui
pescare con probabilità uniforme un elemento per rimpiazzare i segnaposto
invalidi lasciati in precedenza. Questa è una rapida introspezione della logica
di riparazione delle permutazioni sviluppata.
La trattazione di tematiche quali la riparazione intelligente, facendo
affidamento a dei calcoli su strutture dati che portano le informazioni dei
vincoli, è un successivo passo naturale della procedura di riparazione. Essa
viene pensata inizialmente come applicazione operativa ai problemi in cui la
codifica con permutazione viene applicata a variabili decisionali
77
rappresentative di strutture a grafo o ad albero. Un ottimo metodo di lavoro
in questi casi è la definizione di una matrice quadrata di dimensione con
numerosità degli elementi del dominio della variabile. In essa vengono
definite, tramite dei valori (generalmente si utilizza una mappa binaria), le
vicinanze valide fra gli elementi. Nel caso di indifferenza dell’ordine di
accoppiamento si noterà che tale matrice risulterà speculare rispetto la
diagonale principale.
Tale sviluppo viene però viene evitato durante la prima stesura del codice.
Come per altre parti delle metodologie di risoluzione infatti, viene optato per
sviluppare inizialmente una versione base e controllarne le potenzialità coi
test che verranno presentati nel corso del capitolo 6. Per decidere in seguito
in quale direzione sarà meglio concentrare gli sforzi di ricerca e sviluppo per
il futuro evolversi dell’algoritmo.
Alcune tematiche sono state volutamente omesse per non appesantire la
trattazione specifica del codice, mentre altri aspetti non ancora affrontati
verranno inseriti nel capitolo 7 delle conclusioni come sviluppi futuri. Un
ottimo esempio riguarda la parallelizzazione del codice, nonostante fosse
largamente utilizzabile, non è stata implementata se non durante alcune delle
fasi antecedenti la costruzione effettiva del MOGASI. Questo perché si è
ritenuto di dover dare precedenza allo sviluppo della logica dell’algoritmo e
al test delle sue possibilità operative. Punto sul quale, per gli algoritmi
genetici in particolare, raramente verte su considerazioni delle prestazioni in
termini temporali. Infatti i confronti generalmente si operano a parità di
valutazioni eseguite o a numero di generazioni prodotte. Tali considerazioni
non precludono la volontà di migliorare le prestazioni anche temporali
dell’algoritmo prodotto.
78
6. Test e risultati
Nel presente capitolo verranno esposti dettagliatamente i risultati ottenuti
dai test effettuati con il MOGASI su un largo numero di istanze di problemi.
Essi sono stati selezionati principalmente dalle numerose fonti bibliografiche
citate durante le spiegazioni dei capitoli precedenti. Particolare riguardo è
stato dedicato all’insieme di problemi vincolati e non, proposti da Deb nel
[24] per verificare le prestazioni dell’algoritmo NSGA-II.
Vengono delineate delle macro aree di verifica per il MOGASI, estratte dalla
sua stessa composizione, che mirano a coprire ogni tipologia di problema
affrontabile dal suddetto algoritmo:
1. Problema vincolato singolo obiettivo;
diseguaglianze e/o uguaglianze lineari;
possibile presenza di vincoli non lineari.
2. Problema multiobiettivo privo di vincoli;
3. Problema vincolato multiobiettivo;
Nessuna limitazione alla tipologia di vincoli.
4. Problema intero singolo e multiobiettivo;
5. TSP – Problema del commesso viaggiatore singolo obiettivo;
Per ognuna delle categorie sopra citate si sottolinea la presenza obbligatoria
imposta dal MOGASI dei limiti di dominio per le variabili decisionali. Inoltre
in nessun caso vengono poste limitazioni di alcun tipo alla struttura della
funzione obiettivo, essa può essere lineare o non lineare.
Per una corretta esposizione dei problemi test si riporteranno i dettagli
essenziali di ognuno, seguendo i seguenti punti generali:
79
Nome identificativo del test;
Formulazione matematica;
Categoria di appartenenza del problema;
Competitors;
Parametri di esecuzione;
Metrica di Valutazione;
Esposizione dei risultati.
Prima di procedere all’effettiva presentazione dei risultati si ritiene
opportuno introdurre brevemente una metrica di valutazione. Essa verrà
largamente utilizzata in questo capitolo per la valutazione di bontà delle
soluzioni di problemi multiobiettivo. Viene scelta la metrica denominata
Inverted Generational Distance – IGD [49] e definita come segue:
Dato insieme dei punti di Pareto di riferimento e insieme approssimato
di tale set, si definisce:
dove è la distanza Euclidea minima fra e tutti i punti in .
I fronti valutati positivamente corrisponderanno a valori di IGD bassi, poiché
implicheranno che i punti appartenenti all’insieme in esame saranno vicini
ai punti di riferimento. E quindi che sono accurati e uniformemente
distribuiti similarmente a . Ciò impone una cura particolare nella
generazione dei fronti di riferimento, per fare ciò sono stati utilizzati infatti
dei programmi specifici. Sottoponendo ad essi i punti risultanti da lunghe
ottimizzazioni con tutti gli algoritmi è stato possibile estrarre l’insieme dei
punti migliori per generare il fronte .
80
6.1. Problema vincolato singolo obiettivo
In questa prima categoria verranno confrontati i risultati ottenuti
dall’algoritmo prodotto, il MOGASI, con vari altri algoritmi scelti come
competitor, indicati in dettaglio per ogni test. Sono in seguito presentati sette
problemi singolo obiettivo selezionati principalmente dalla libreria messa a
disposizione da Michalewicz per testare le varie versioni di GENOCOP
disponibili presso il suo sito web. Nonostante fossero disponibili oltre un
centinaio di problemi validi, è stata effettuata una selezione prendendo
solamente alcuni dei più adatti. Come sarà approfondito nelle descrizioni
specifiche dei test, sono state scelte soprattutto le istanze che presentavano
vincoli di uguaglianza, punto critico per gli algoritmi genetici standard e per
testare l’effettiva efficacia della procedura di Elimination of Equalities. Caso
per caso verranno presentati in forma tabellare i risultati ottenuti, sotto forma
di valore ottimo trovato dall’algoritmo. I valori ottimi di ogni batteria
saranno evidenziati in grossetto. I risultati esposti sono stati mediati su una
dozzina di esecuzioni, accortezza richiesta per evitare di incappare in
risultati limite. Si ricorda infatti che molti dei meccanismi interni agli
algoritmi in analisi funzionano con meccaniche di scelta casuale, rendendo
possibile quindi ampia diversità di risultati fra esecuzione ed esecuzione. Le
iterazioni del GENOCOP III sono state eseguite col codice originale di
Michalewicz. Per il MOGA-II e l’NSGA-II si è usufruito del software
modeFRONTIER®. Tutti e quattro gli algoritmi sono stati fatti eseguire con i
valori di default e gli stessi criteri di arresto, quantificati caso per caso ma
generalmente riguardanti il numero di generazioni massime eseguibili fissata
la dimensione della popolazione.
81
-32.070
-32.068
-32.066
-32.064
-32.062
-32.060
-32.058
-32.056
-32.054
-32.052
GENOCOP
MOGASI
NSGA-II
MOGA-II
Nome del test: t01
Formulazione matematica:
FO
Vincoli
Domini
Parametri di esecuzione: dimensione popolazione iniziale 70
numero di generazioni 500
Competitor: GENOCOP III, MOGA-II, NSGA-II
Metrica di Valutazione: valore ottimo
Scostamento percentuale:
GENOCOP 0.0330 %
MOGASI 0.0086 %
NSGA-II 0.0106 %
MOGA-II 0.0000 %
GENOCOP -32.0577
MOGASI -32.0655
NSGA-II -32.0649
MOGA-II -32.0683
82
0.71
0.72
0.73
0.74
0.75
0.76
0.77
0.78
0.79
GENOCOP III
MOGASI
NSGA-II
MOGA-II
Nome del test: t02
Formulazione matematica:
FO
Vincoli
Domini
Parametri di esecuzione: dimensione popolazione iniziale 70
numero di generazioni 1000
Competitor: GENOCOP III, MOGA-II, NSGA-II
Metrica di Valutazione: valore ottimo
Risultati:
GENOCOP 0.7339
MOGASI 0.7689
NSGA-II 0.7612
MOGA-II 0.7803
Scostamento percentuale:
GENOCOP 5.9469 %
MOGASI 1.4589 %
NSGA-II 2.4537 %
MOGA-II 0.0000 %
83
70000
72000
74000
76000
78000
80000
82000
84000
86000
GENOCOP III
MOGASI
NSGA-II
MOGA-II
Nome del test: t06
Formulazione matematica:
FO
Vincoli
Domini
Parametri di esecuzione: dimensione popolazione iniziale 70
numero di generazioni 500
Competitor: GENOCOP III, MOGA-II, NSGA-II
Metrica di Valutazione: valore ottimo
Risultati:
Scostamento percentuale:
GENOCOP 0.0000 %
MOGASI 0.1782 %
NSGA-II 12.164 %
MOGA-II 11.599 %
GENOCOP 75238.09
MOGASI 75372.20
NSGA-II 84390.24
MOGA-II 83965.60
84
20.00
22.00
24.00
26.00
28.00
30.00
32.00
GENOCOP III
MOGASI
NSGA-II
MOGA-II
Nome del test: t12
Formulazione matematica:
FO
Vincoli
Domini
Parametri di esecuzione: dimensione popolazione iniziale 70
numero di generazioni 500
Competitor: GENOCOP III, MOGA-II, NSGA-II
Metrica di Valutazione: valore ottimo
Risultati:
Scostamento percentuale:
GENOCOP 0.0000 %
MOGASI 0.3873 %
NSGA-II 20.966 %
MOGA-II 15.479 %
GENOCOP 30.0544
MOGASI 29.9380
NSGA-II 23.7529
MOGA-II 25.4020
85
10.00
12.00
14.00
16.00
18.00
20.00
22.00
24.00
26.00
GENOCOP III
MOGASI
NSGA-II
MOGA-II
Nome del test: t13
Formulazione matematica:
FO
Vincoli
Domini
Parametri di esecuzione: dimensione popolazione iniziale 70
numero di generazioni 500
Competitor: GENOCOP III, MOGA-II, NSGA-II
Metrica di Valutazione: valore ottimo
Risultati:
Scostamento percentuale:
GENOCOP 0.1422 %
MOGASI 0.0000 %
NSGA-II 43.704 %
MOGA-II 40.527 %
GENOCOP 24.9644
MOGASI 25.0000
NSGA-II 14.0738
MOGA-II 14.8680
86
-50.00
-48.00
-46.00
-44.00
-42.00
-40.00
-38.00
-36.00
-34.00
-32.00
-30.00
GENOCOP III
MOGASI
NSGA-II
MOGA-II
Nome del test: t17
Formulazione matematica:
FO
Vincoli
Domini
Parametri di esecuzione: dimensione popolazione iniziale 70
numero di generazioni 500
Competitor: GENOCOP III, MOGA-II, NSGA-II
Metrica di Valutazione: valore ottimo
Risultati:
Scostamento percentuale:
GENOCOP 0.0470 %
MOGASI 0.0000 %
NSGA-II 20.128 %
MOGA-II 15.572 %
GENOCOP -47.6544
MOGASI -47.6761
NSGA-II -38.0798
MOGA-II -40.2417
87
-10
-8
-6
-4
-2
0
2
GENOCOP III
MOGASI
NSGA-II
MOGA-II
Nome del test: t26
Formulazione matematica:
FO
Vincoli
Domini
Parametri di esecuzione: dimensione popolazione iniziale 70
numero di generazioni 500
Competitor: GENOCOP III, MOGA-II, NSGA-II
Metrica di Valutazione: valore ottimo
Risultati:
Scostamento percentuale:
GENOCOP 0.0000 %
MOGASI 0.0000 %
NSGA-II 825.25 %
MOGA-II 811.54 %
GENOCOP 1.2866
MOGASI 1.2866
NSGA-II -9.3385
MOGA-II -9.1545
88
Considerando singolarmente i risultati dei sette test esposti si può notare che
il MOGASI conferma tutti i ragionamenti che ne hanno decretato lo sviluppo.
Eredita infatti da entrambi i suoi genitori le caratteristiche migliori riuscendo
a portarsi sempre in un posizionamento ottimo. Ma cosa ben più importante,
in una fascia di scostamento più che accettabile dal valore migliore della
quartina di algoritmi in lizza.
Si sottolinea come l’utilizzo di operatori più adatti agli insiemi convessi
penalizzi la convergenza su t01 e t02, dove si rileva la presenza di soli vincoli
di diseguaglianza (sia lineari che non lineari). In tali problemi infatti hanno
prevalso gli algoritmi genetici standard. Si noti la prevalsa generale del
MOGA-II su questi primi due test. Comportamento presumibile data la
dipendenza intrinseca delle formulazioni fra le variabili decisionali; cosa che
tale algoritmo, a differenza del concorrente NSGA-II, sfrutta con il
directional crossover, e il MOGASI tramite un corredo di operatori lineari ed
euristici.
Un comportamento opposto si è verificato nei successivi cinque test che
erano stati selezionati proprio per la presenza di vincoli lineari del tipo
equazione. In questi è visibile un predicibile calo di prestazioni da parte degli
algoritmi genetici standard, probabilmente incagliati su dei punti di ottimo
locale. Mentre i risultati del GENOCOP III e del MOGASI tendono
stabilmente all’ottimo, addirittura raggiungendolo nel caso dell’ultimo test
presentato, il t26.
Dunque il risultato di nostro interesse è che il valore ottimo medio del
MOGASI si è posizionato sempre in una zona ristretta adiacente al risultato
ottimo trovato nella batteria. Andando poi a superare le prestazioni degli
stessi genitori nella maggior parte dei casi. Questa miglioria è stata
influenzata nei confronti del GENOCOP III, grazie all’accorgimento della
89
gestione globale della popolazione, già approfondito nel capitolo 5.3. E nei
confronti con gli algoritmi genetici tradizionali grazie all’impiego della
doppia popolazione e agli operatori specializzati ereditati dal GENOCOP III.
Si vuole ora presentare un grafico intuitivo che aiuti a visualizzare i risultati
globali dei quattro algoritmi nella presente categoria di test. Per fare ciò è
stato deciso di utilizzare un bubble chart utilizzato come medagliere per la
quartina in esame. Diversi pesi sono stati dati alle posizioni raggiunte per
migliorare la leggibilità del grafico, andando a modificare quindi l’ampiezza
delle bolle in maniera inversamente proporzionale al posto sul podio
conquistato. Sulle ordinate si possono trovare in ordine inverso le medaglie,
ovvero sulla riga più in alto saranno presenti le medaglie del primo posto.
Mentre sulle ascisse, utilizzando anche una codifica cromatica, sono disposti
i quattro algoritmi in esame.
90
Come si può osservare dal grafico, l’andamento generale del MOGASI nella
categoria dei problemi singolo obiettivo vincolati risulta estremamente
positivo. Esso infatti presenta posizionamenti solamente al primo e al
secondo posto. Si porta all’attenzione anche gli ottimi risultati ottenuti dal
MOGA-II nonostante la scelta dei test fosse sbilanciata rispetto la presenza di
vincoli di uguaglianza. È ritenuto di secondaria importanza il
comportamento negativo dell’NSGA-II evidenziato dal grafico poiché si
ricorda che il grafico presenta un confronto diretto fra i quattro algoritmi in
un ambiente a priori sfavorevole per gli algoritmi genetici, appesantendo così
il giudizio sulle performance in maniera forse eccessiva.
91
6.2. Problema multiobiettivo privo di vincoli
Nella presente categoria sono stati iscritti un insieme di sei problemi tratti
dall’articolo di Deb [24].
Essi sono stati selezionati per la loro formulazione, presentano infatti una
struttura multiobiettivo con la presenza dei soli limiti di dominio sulle
variabili decisionali. Una ulteriore caratteristica molto importante è la
tipologia di fronte di Pareto del problema, perciò nelle schede dettagliate dei
test sarà inserita anch’essa nei dettagli elencati.
A causa della natura multiobiettivo dei problemi non sarà possibile
procedere ad una elencazione tabellare efficace dei valori ottimi medi
ritrovati nelle serie di test effettuati per algoritmo. Perciò i paragoni delle
valutazioni verranno esposti con un criterio progressivo sul numero di
valutazioni della metrica adottata. Per questa categoria si adotterà l’Inverted
Generational Distance, abbreviato ad IGD [49].
Come nel caso precedente sono stati eseguiti gli algoritmi lasciando
generalmente invariati i parametri di default. Per porre un limite
all’esecuzione, rendendo pari i confronti, si è utilizzato questa volta il
numero di valutazioni effettuate, impostate ad un massimo di 20 000
esecuzioni della procedura di fitness. È importante sottolineare che nessuno
dei tre algoritmi in competizione nella presente categoria permette la
valutazione ripetuta di un individuo già valutato. In questo modo il
confronto verrà effettuato fra i primi ventimila individui diversi generati dai
vari algoritmi. Per ogni test sono state effettuate 30 esecuzioni suddivise
equamente fra i competitori in analisi.
Anche in questo caso per l’esecuzione del MOGA-II e del NSGA-II è stato
impiegato modeFRONTIER®.
92
Nome del test: SCH
Formulazione matematica:
FO
Fronte convesso
Domini
Risultati:
Valutazioni MOGA-II NSGA-II MOGASI
1 000 0.01668 0.265011 0.601215
2 000 0.01668 0.164641 0.014352
5 000 0.01668 0.164641 0.002047
10 000 0.01668 0.164641 0.000847
15 000 0.01668 0.164641 0.000535
20 000 0.01668 0.164641 0.000398
93
Nome del test: POL
Formulazione matematica:
FO
Fronte non convesso
disconnesso
Domini con
Risultati:
Valutazioni MOGA-II NSGA-II MOGASI
1 000 0.127525 0.325151 0.226833
2 000 0.106586 0.040874 0.088499
5 000 0.092199 0.016123 0.029016
10 000 0.089290 0.009145 0.015489
15 000 0.086026 0.007125 0.011444
20 000 0.081632 0.005492 0.008475
94
Nome del test: KUR
Formulazione matematica:
FO
Fronte non convesso
Domini con
Risultati:
Valutazioni MOGA-II NSGA-II MOGASI
1 000 0.275071 0.573661 0.668073
2 000 0.088247 0.370326 0.236734
5 000 0.049114 0.212946 0.050474
10 000 0.046597 0.11135 0.029561
15 000 0.045342 0.083911 0.020604
20 000 0.044632 0.079816 0.016975
95
Nome del test: ZDT1
Formulazione matematica:
FO
Fronte convesso
Domini con
Risultati:
Valutazioni MOGA-II NSGA-II MOGASI MOGASI
1 000 1.311473 0.230282 1.896624 1.651704
2 000 0.813696 0.068033 1.698832 1.311458
5 000 0.154245 0.003728 1.339286 0.627387
10 000 0.016169 0.000556 0.949141 0.257387
15 000 0.006138 0.000244 0.703280 0.113383
20 000 0.003879 0.000149 0.522568 0.071543
96
Nome del test: ZDT2
Formulazione matematica:
FO
Fronte non convesso
Domini con
Risultati:
Valutazioni MOGA-II NSGA-II MOGASI MOGASI
1 000 2.286076 0.919661 3.337117 3.158038
2 000 1.543180 0.740969 3.151066 2.578230
5 000 0.349456 0.657839 2.655752 1.611857
10 000 0.011726 0.441018 2.099000 0.871728
15 000 0.005056 0.318522 1.575959 0.302949
20 000 0.003426 0.289424 1.254041 0.184233
97
Nome del test: ZDT4
Formulazione matematica:
FO
Fronte non convesso
Domini
con
Risultati:
Valutazioni MOGA-II NSGA-II MOGASI
1 000 31.9801 20.14364 12.92377
2 000 16.37493 10.35837 11.24938
5 000 5.208431 7.220014 6.513944
10 000 3.306407 6.692788 3.594151
15 000 2.795494 5.762386 2.060945
20 000 2.663468 5.59402 1.592392
98
Nei sei test non vincolati appena presentati si può constatare l’ottimo
comportamento del MOGASI. Infatti si vede come l’algoritmo lavori
correttamente avvicinandosi con un ritmo più che ragionevole ai fronti
ottimi, eguagliando o anche superando le performance degli stessi MOGA-II
e NSGA-II.
Importante chiarire che nei problemi ZDT1 e ZDT2 si è provveduto a fare
due diverse batterie di test con il MOGASI. Questo per accertare se i risultati
scadenti fossero stati da imputare direttamente all’algoritmo o ai parametri
standard impiegati. Si è quindi presentata un’alternativa a causa della
costruzione particolare dello spazio delle soluzioni di tali istanze.
Come si può notare dall’andamento delle ottimizzazioni dell’algoritmo,
rappresentate in verde per tali test, è stato sufficiente un intuitivo
adattamento dei parametri di esecuzione per migliorare sensibilmente le
prestazioni.
Un punto importante risulta rendere più chiaro il motivo della partenza del
MOGASI da valutazioni IGD medio alte. Questo fatto non è direttamente
imputabile alla logica interna dell’algoritmo ma è principalmente causato dal
metodo di inizializzazione completamente casuale. Tale caratteristica si
riscontrerà largamente anche nella categoria di test del capitolo 6.3, i
problemi multiobiettivo vincolati.
Per concludere si rimanda al termine del prossimo gruppo di test la
valutazione globale dei posizionamenti tramite medagliere.
Si è optato per attendere la conclusione della presentazione di tutti i risultati
dei problemi tratti dall’articolo di Deb [24] per mantenere la valutazione
globale allineata all’idea che ha costituito l’insieme dei test qui presentati,
efficacemente scelti per sottoporre all’algoritmo genetico delle caratteristiche
diverse e importanti su cui controllare le proprie performance.
99
6.3. Problema vincolato multiobiettivo
In questa terza categoria sono presentati quattro test nuovamente tratti
dall’articolo di Deb [24]. Come spiega il titolo verranno sottoposti dei
problemi multiobiettivo vincolati ai tre genetici in competizione: MOGASI;
MOGA-II; NSGA-II. Al contrario della categoria del capitolo 6.2 però non si
porrà alcuna restrizione sulla presenza o sulla tipologia dei vincoli.
Similarmente al caso precedente si procederà con un totale di 30 esecuzioni,
ripartite equamente fra i tre algoritmi candidati, per ognuno dei quattro
problemi. Non verrà effettuato un aggiustamento dei parametri in ingresso
degli algoritmi lasciandoli lavorare con i valori di default. Per l’applicazione
del MOGASI verrà ovviamente impiegato il programma Java prodotto da
questo lavoro di tesi, mentre per entrambi i competitor verrà utilizzato il
software modeFRONTIER®.
Come metrica di confronto sarà nuovamente utilizzata l’Inverted
Generational Distance, e applicata nella presentazione dei risultati come per
la categoria multiobiettivo non vincolata.
I calcoli del valore IGD dei fronti ottenuti vengono eseguiti con un
programma sviluppato ad hoc in Java. Inoltre una opzione di esecuzione di
tale programma permette di fondere un numero arbitrario di fronti al fine di
costruire un fronte di riferimento ottimo equispaziato. Tale procedura ci ha
permesso di produrre i fronti di riferimento delle categorie esposte nei
capitoli 6.2 e 6.3, a seguito di numerose esecuzioni di tutti gli algoritmi con
criteri di arresto molto più ampi.
Anche in questo caso sono state impostate 20 000 valutazioni come
parametro di terminazione degli algoritmi. Si vedano ora i dettagli dei
quattro test della presente categoria.
100
Nome del test: DEB
Formulazione matematica:
FO
Vincoli
Domini
Risultati:
Valutazioni MOGA-II NSGA-II MOGASI
1 000 0.065793 0.053419 0.415566
2 000 0.058304 0.053613 0.168802
5 000 0.052841 0.040791 0.041473
10 000 0.046287 0.034485 0.009352
15 000 0.043041 0.031987 0.007652
20 000 0.037256 0.010498 0.006497
101
Nome del test: SRN
Formulazione matematica:
FO
Vincoli
Domini con
Risultati:
Valutazioni MOGA-II NSGA-II MOGASI
1 000 0.883843 1.640582 1.094851
2 000 0.521967 0.92367 0.541842
5 000 0.305973 0.607951 0.232426
10 000 0.209635 0.531319 0.128108
15 000 0.16975 0.419232 0.092720
20 000 0.147247 0.338228 0.069383
102
Nome del test: TNK
Formulazione matematica:
FO
Vincoli
Domini con
Risultati:
Valutazioni MOGA-II NSGA-II MOGASI
1 000 0.030083 0.080744 0.033525
2 000 0.018544 0.072955 0.019697
5 000 0.009038 0.055754 0.012663
10 000 0.005488 0.046824 0.010123
15 000 0.004118 0.041503 0.008919
20 000 0.003408 0.036758 0.008401
103
Nome del test: WATER
Formulazione matematica:
FO
Vincoli
Domini
con
Risultati:
Valutazioni MOGA-II NSGA-II MOGASI
1 000 0.076545 0.105142 0.11616
2 000 0.054610 0.071543 0.066334
5 000 0.037099 0.038041 0.033313
10 000 0.028802 0.022800 0.022477
15 000 0.024124 0.017298 0.018274
20 000 0.021942 0.014534 0.015857
104
Si può notare che anche nel caso dei problemi multiobiettivo vincolati il
MOGASI ha mantenuto le aspettative. Dimostrando di produrre un ritmo di
convergenza soddisfacente e in linea con le performance dei due competitor,
che determinano attualmente lo stato dell’arte degli algoritmi genetici.
Tali risultati sono sicuramente incoraggianti considerando il fatto che i
confronti sono stati effettuati su esecuzioni a profilo standard, ovvero senza
operare adattamenti ai valori dei parametri per i vari problemi.
La problematica affrontata già durante il commento della categoria di test,
del capitolo 6.2, inerente l’inizializzazione della popolazione diventa forse
più chiara visionando il grafico dei valori dell’IGD del problema denominato
DEB. Si nota infatti come, nonostante la partenza da una popolazione
estremamente distante dal fronte ottimo, il MOGASI sia riuscito a convergere
efficacemente superando addirittura i due competitor.
105
Presentati quindi i risultati di tutte e due le categorie di test multiobiettivo,
vincolati e non, si procede ad una unica valutazione del posizionamento dei
tre algoritmi a confronto. Viene proposto nuovamente un grafico a bolle
strutturato a medagliere in cui si possono vedere sulle ascisse i vari
algoritmi, e sulle ordinate il posizionamento ottenuto. Si noti che in posizione
dominante in alto a sinistra è presente la valutazione delle prime posizioni
collezionate dal MOGASI. Il raggio tale bolla domina riga indicando quindi
che l’algoritmo prodotto ha collezionato un numero maggiore di prime
posizioni rispetto gli altri competitor. Risulta conseguentemente positivo
l’andamento decrescente delle dimensioni delle bolle del MOGASI,
evidenziando una ottima distribuzione sulle posizioni guadagnate nei test.
106
6.4. Problema intero singolo e multi obiettivo
Il test utilizzato in questa è tratto da un lavoro di laurea antecedente [46].
Esso tratta la ricerca di metodi di risoluzione evoluzionistici per il problema
di posizionamento ottimale di sensori wireless. Si opta quindi per un
approccio decisamente più discorsivo dei casi precedenti data la specificità
del contesto applicativo.
Il problema mira alla definizione delle posizioni ottimali di nodi sensore e
di un nodo sincronizzatore all’interno di una griglia quadrata di dimensioni
. La mappa di dimensione viene codificata con una matrice binaria e
rappresenta lo spazio disponibile, in ogni posizione sarà possibile avere un
uno, per la presenza del sensore in tale cella, o zero altrimenti. Una variabile
discreta intera viene dedicata per la posizione del sincronizzatore sulla
mappa. È definito un Sensor Range SR che definisce il raggio di copertura
massimo dei sensori.
Gli obiettivi sono massimizzare il numero di celle coperte dalla disposizione
sulla mappa e minimizzare il consumo energetico, dipendente in maniera
diretta dalle distanze totali fra i sensori.
I vincoli riguardano il posizionamento di un singolo elemento in una cella,
questo poiché il sincronizzatore non può coesistere con un sensore. Ogni
elemento posizionato in mappa deve essere a meno di una certa distanza
massima dal suo vicino più prossimo per permettere il collegamento, tale
distanza è definita con il nome di Comunication Range CR.
L’istanza scelta per il test vede la dimensione fissata a , il Sensor
Range a 2 e il Comunication Range a un valore di 4. Per limitare
ulteriormente le aree di interesse si aggiungono dei vincoli di copertura
107
minima pari a 70 celle, una limitazione a 18 del numero massimo di sensori
posizionabili e concludendo due flag di controllo, sulla validità del
posizionamento del sincronizzatore e sulla connessione valida della
disposizione.
È importante sottolineare che il problema viene definito come ottimizzazione
multiobiettivo. Mentre l’approccio utilizzato nella fonte [46] considerava di
valutare gli obiettivi per differenza, creando così un unico obiettivo da
massimizzare. Questo poteva essere utile per la risoluzione all’ottimo tramite
strumenti di programmazione lineare. Per creare una valida base di
confronto si è provveduto ad eseguire i test con le stesse metodologie svolte
nella fonte utilizzata. Ovvero serie di 10 esecuzioni per configurazione:
dim. popolazione 100, 500 generazioni (50 000 valutazioni);
dim. popolazione 100, 1 000 generazioni (100 000 valutazioni).
La generazione della popolazione di partenza è stata scelta sempre come
completamente casuale, reputando superfluo sviluppare da zero procedure
mirate all’inizializzazione non casuale specifiche. Verranno quindi operati
confronti solamente coi risultati della fonte tratti dalle simulazioni con
generazione della popolazione iniziale dello stesso tipo.
Come parametri sono stati impostati per il MOGASI una percentuale di
applicazione del crossover di 0.75 e conseguentemente di mutazione del 0.25,
per tutte le esecuzioni.
Il MOGASI verrà eseguito in quattro serie da dieci esecuzioni in modo da
provare tutte le varie combinazioni: Singolo e multi obiettivo, a 50 000 e
100_000 valutazioni.
Vengono a seguito presentati i risultati ottenuti nalle batterie di esecuzioni su
tutti gli algoritmi in competizione, MOGASI, MOGA-II, NSGA-II, CUDIA.
108
L’ultimo elencato consiste nel risultato della tesi utilizzata come fonte [46],
tale algoritmo corrisponde ad un MOGA-II con l’aggiunta di un operatore di
mutazione specializzato che incorpora delle logiche di miglioramento locale
ad-hoc per il problema. Per esso verranno presentate due versioni (v.1 e v.2)
che consistono in una impostazione diversa per i parametri in input
dell’algoritmo. Purtroppo non è stato possibile decidere liberamente una
metrica di valutazione per la presente categoria di test, rimanendo vincolati
alla impostazione della tesi citata [46]. Tutti i risultati vengono quindi
presentati tramite il valore ottimo medio della funzione obiettivo di
massimizzazione congiunta.
Nella tabella seguente si possono vedere i valori ottimi medi di confronto dei
tre algoritmi competitori.
NGSA-II MOGA-II CUDIA v.1 CUDIA v.2
50 000 val. 60.0 63.6 64.7 64.8
100 000 val. 61.2 64.4 65.0 65.3
Conseguentemente vengono riportati nella stessa forma anche i risultati
medi ottenuti dalle quaranta esecuzioni del MOGASI ripartite equamente
sulla casistica richiesta:
MOGASI SO MOGASI MO
50 000 val 62.9 65.8
100 000 val 62.8 65.6
Si porta all’attenzione il grande dislivello di risultati che l’algoritmo oggetto
di questo lavoro di tesi ha raggiunto lavorando con il problema singolo
obiettivo rispetto alla versione multiobiettivo. Questo comportamento era
intuibile dato che il problema di posizionamento di antenne wireless è
essenzialmente del secondo tipo. Quindi una forzatura semplificativa per
109
ricondursi al caso singolo obiettivo limita certamente lo spazio delle
soluzioni che verrà effettivamente esplorato. Inoltre il nucleo logico delle fasi
di valutazione del MOGASI sono state implementate appositamente per
problemi multiobiettivo, ereditandone il funzionamento dal NSGA-II.
Per semplificare il confronto diretto fra tutte e cinque gli algoritmi a
paragone, si propone un semplice diagramma a barre.
Da esso si possono estrarre le considerazioni che si potevano intuitivamente
già formulare a priori. Ovvero che i risultati peggiori sarebbero stati
collezionati dall’NSGA-II, poiché fra i competitor standard è quello meno
adatto a lavorare con variabili discrete e binarie. Inoltre era molto probabile
che il MOGA-II collezionasse un risultato inferiore al CUDIA, questo perché
il secondo algoritmo è una specificazione per la tipologia di problema in
esame del primo. Interessante invece notare la disparità che viene a formarsi
fra il MOGASI singolo obiettivo e multiobiettivo. Passando da peggiore fra i
competitori adatti alla tipologia di problemi, lavorando a potenzialità ridotte
nel singolo obiettivo, a migliore del confronto in multiobiettivo.
110
Si vuole evidenziare inoltre che la
valutazione della funzione obiettivo
congiunta più alta registrata dal MOGASI
risulta essere di 68.4. Vetta raggiunta in una
delle esecuzioni sul problema
multiobiettivo. Tale valore è interessante se
confrontato con il valore ottimo trovato con
l’applicazione di un algoritmo esatto
lasciato libero di lavorare per un’intera ora,
dettaglio rilevante se si considera che una
esecuzione del MOGASI a 100 000 valutazioni impiega meno di quindici
minuti su computer portatile di categoria media. In figura si presentano a
scopo informativo i risultati ottenuti dalla risoluzione con l’algoritmo esatto.
Utilizzando il valore ottimo del problema si calcolano gli scostamenti
percentuali dei risultati medi evidenziati di tutti i competitor:
NGSA-
II
MOGA-
II
CUDIA
v.1
CUDIA
v.2
MOGASI
SO
MOGASI
MO
50 000
val 13.18 % 7.97 % 6.38 % 6.24 % 8.99 % 4.79 %
100 000
val 11.45 % 6.82 % 5.95 % 5.51 % 9.13 % 5.08 %
111
6.5. Problema del commesso viaggiatore singolo
obiettivo
Il problema in esame rientra nella famosa categoria dei problemi del
commesso viaggiatore, meglio conosciuti con il loro nome anglosassone di
Travelling Salesman Problem, o più semplicemente TSP [40].
Esso si può descrivere efficacemente con una semplice domanda:
Dato un insieme di città e le distanze fra ogni coppia di esse. Qual è il circuito
di lunghezza minima che permette di visitarle tutte al più una volta e tornare
alla città di partenza?
Nonostante l’apparente semplicità del problema esso non è risolvibile in
tempo polinomiale, entrando a far parte dei problemi combinatori NP
difficili. La sua formulazione matematica di programmazione lineare è
definita come segue:
FO
Vincoli
Definiti i come il costo per andare dal nodo i al nodo j, e le variabili
decisionali come variabili binarie di valore 1 se quel percorso è stato
utilizzato e 0 in caso contrario.
Per entrare nel dettaglio del test proposto, esso sarà il TSP Grötschels24,
comunemente indicato con la sigla gr24. È stato scelto da una celebre raccolta
112
di istanze, la TSPLIB [40], e perché era stato incontrato più volte nella
presentazione dei risultati durante la ricerca bibliografica [14][39].
In particolare si è deciso, nonostante la metodologia particolare di test, di
adottare come competitor i numerosi risultati esposti a pag.43 del lavoro [39].
Questi mettono in evidenza i valori ottimi medi realizzati dall’esecuzione di
30 iterazioni di un algoritmo genetico aventi degli operatori specializzati
scelti da una ampia lista. Per ogni coppia possibile sono state ripetute le
esecuzioni, lanciate con una dimensione di popolazione di 200 individui e un
limite massimo di 50 000 generazioni, tale metodo inoltre beneficia di un
criterio di arresto che blocca l’algoritmo se per 1 000 generazioni non
migliora il valore ottimo trovato. Considerando che in tale lavoro vengono
presi in considerazione 8 operatori di crossover e 6 di mutazione, si capisce
immediatamente il perché della sua scelta come fonte per i competitori.
Inoltre tale studio potrà venir utilizzato in futuro per implementare operatori
specializzati nella categoria delle Permutazioni.
Il MOGASI è stato lanciato in esecuzione con dei parametri decisamente
inferiori per una questione di tempistiche. Si è provveduto ad eseguire
comunque 30 ottimizzazioni, con parametri di esecuzione:
dimensione popolazione 50;
generazioni massime 10 000;
probabilità mutazione 0.15;
probabilità crossover 0.80.
Si ricorda che il MOGASI lavora con operatori base, quali il crossover a
singolo punto di taglio e la mutazione uniforme; sfruttando in coda alla fase
di riproduzione la procedura di Fixing per cercare di rimanere nello spazio
delle soluzioni.
113
Senza scendere nei dettagli e rimandando ogni spiegazione direttamente
all’articolo [39], si elencano di seguito tutti gli operatori competitori:
PMX – Partially Mapped Crossover;
CX – Cycle Crossover;
OX1 – Order Crossover;
OX2 – Order Based Crossover;
POS – Position Based Crossover;
ER – Genetic Edge Recombination Crossover;
VR – Voting Recombination Crossover;
AP – Alternating Position Crossover;
DM – Displacement Mutation;
EM – Exchange Mutation;
ISM – Insertion Mutation;
SIM – Simple Inversion Mutation;
IVM – Inversion Mutation;
SM – Scrubble Mutation.
A seguire i risultati medi di tutte le combinazioni degli operatori appena
elencati. Si ricorda che il TSP è un problema di minimizzazione.
AP CX ER OX1 OX2 PMX POS VR media
DM 1470 1416 1274 1305 1322 1355 1305 1777 1403
EM 1487 1474 1274 1299 1311 1416 1312 1903 1434
ISM 1406 1461 1272 1307 1316 1368 1298 1993 1428
IVM 1406 1408 1277 1303 1329 1369 1315 1904 1414
SIM 1588 1441 1276 1313 1342 1393 1329 1737 1428
SM 2996 1423 1277 1300 1367 1388 1316 1920 1623
media 1725 1437 1275 1305 1331 1382 1313 1872 1455
114
Infine si presenta il risultato ottimo medio ottenuto dalle 30 esecuzioni del
MOGASI per il gr24:
MOGASI 1460
A causa dell’elevato numero risulterà difficoltoso evidenziare con dei grafici
i confronti diretti fra ogni coppia possibile di operatori presentati nel corso
dell’articolo [39]. Perciò si opterà per porre a confronto tramite un
diagramma a barre dei valori ottimi medi ottenuti dai vari operatori singoli
considerati sull’insieme globale delle loro applicazioni. Inoltre verrà
presentato il valore medio totale di tutti gli operatori specializzati (indicato
come Media nel grafico sottostante) e il risultato del MOGASI.
Si può notare che l’applicazione di operatori specializzati produce in media
delle performance migliori, raggiungendo con il Genetic Edge
Recombination Crossover (ER) l’apice per il problema in questione. Tuttavia
il risultato ottenuto mostra eccezionalmente come il valore medio prodotto
con il MOGASI poco si discosti dalla Media complessiva di tutti gli operatori
specializzati scelti come competitori della categoria.
115
Questa caratteristica è incoraggiante per gli sviluppi futuri della logica
inerente le Permutazioni dell’algoritmo MOGASI, soprattutto se si considera
che nel corso della fase di progettazione si era aperta la direzione di
suddivisione della categoria per problemi su grafo. Considerando quindi
l’esecuzione del presente test senza ragionamenti sfruttanti tali strutture, ma
solamente quella inerente le permutazioni, e dell’adozione degli operatori
più basilari a disposizione si ritiene che il risultato ottenuto sia decisamente
positivo. Questo a dispetto del valore assoluto collezionato.
Infine si tiene ad informare il lettore del valore ottimo reale del problema del
commesso viaggiatore di Grötschels24, ovvero 1272 km. Nel corso delle
trenta esecuzioni richieste per la produzione dei risultati dalla categoria di
test il MOGASI ha trovato un valore ottimo globale di 1306 km.
In base al valore di ottimo globale del gr24 si provvede a calcolare gli
scostamenti percentuali dei risultati ottenuti:
AP CX ER OX1 OX2 PMX POS VR
35.29 % 12.71 % 0.00 % 2.35 % 4.39 % 8.39 % 2.98 % 46.82 %
DM EM ISM IVM SIM SM Media MOGASI
10.04 % 12.47 % 12.00 % 10.90 % 12.00 % 27.29 % 14.12 % 14.51 %
116
7. Conclusioni
Gli obiettivi del presente lavoro di tesi sono stati raggiunti con la creazione e
il test del Multi-Objective Genetic Algorithm for Structured Input, il cui
acronimo è MOGASI. Tale algoritmo permette di risolvere problemi
appartenenti alle classi individuate in partenza con delle ottime prestazioni,
evidenziate nel corso del capitolo 6 con la presentazione dei risultati dei test.
Esso eredita e migliora i comportamenti delle euristiche evolutive
fondendole con procedure specifiche per i casi di interesse, principalmente
derivanti da programmazione lineare e ottimizzazione combinatoria. Per
dare una idea più specifica ma intuitiva delle possibilità del programma,
senza scendere in dettagli già precedentemente approfonditi, si ricorre
all’elencazione delle caratteristiche dei problemi accettabili in ingresso:
Funzioni obiettivo, senza limiti di numero, di tipo o vincoli strutturali;
Vincoli lineari e non lineari, sia di uguaglianza che di diseguaglianza;
Variabili in input, continue, discrete e/o binarie;
Limite superiore e inferiore delle variabili (lowerbound e
upperbound);
Variabili strutturate definite come vettori permutazione;
Vincoli sugli output.
E dei parametri principali dell’algoritmo:
Probabilità dei sette operatori genetici implementati;
Flag di scelta sul tipo di selezione, probabilità uniforme o cumulativa;
Parametro di generazione della probabilità cumulativa delle
popolazioni;
Flag determinante il tipo di inizializzazione delle popolazioni iniziali;
117
Numero massimo di tentativi per la generazione dei design della
popolazione iniziale;
Ordine di precisione con cui lavora l’algoritmo;
Dimensione delle popolazioni;
Numero massimo di generazioni evolvibili in una esecuzione;
Flag di utilizzo archivio per i design già valutati;
Limite al numero di valutazioni di design operabili in una esecuzione;
Flag di eliminazione dei design ripetuti;
Abilitazione della generazione degli output file *.csv e *.des per
l’esportazione dei risultati.
Il MOGASI è innovativo per il suo approccio general purpose, infatti apre la
possibilità inesplorata di risoluzione di problemi misti, ovvero che possano
presentare caratteristiche di più tipologie note in letteratura, beneficiando
della conoscenza specifica su tutte.
Durante la progettazione sono state toccate numerose tematiche che
meriterebbero un approfondimento ulteriore, ognuna di esse potrebbe
richiedere un impegno paragonabile all’intera tesi presentata per essere
definita in maniera esaustiva.
Particolare rilevanza si pone sulla possibilità futura di approfondire tutti i
discorsi aperti nel corso del capitolo 4, ossia: l’espansione delle tecniche di
preprocessing utilizzate, l’adozione di operatori specializzati per le varie
categorie individuate laddove si è preferito un approccio minimalistico per il
primo acchito e infine ampliare le stesse categorie con l’adozione di logiche
di fixing specifiche per i problemi su albero e su grafo.
Il contesto di sviluppo che ha influenzato tutto il lavoro presentato si presta a
interessanti possibilità pratiche future. Poiché, in caso di vaglia favorevole
118
del MOGASI, potrebbe essere richiesta un’analisi approfondita
dell’algoritmo e un raffinamento necessario al suo effettivo impiego. Inoltre
saranno disponibili tematiche di integrazione dell’approccio individuato
all’interno di standard emergenti per la formalizzazione dei processi di
ottimizzazione, quale il BPMN 2.0 [47].
Il lavoro svolto ha prodotto una gran quantità di sottorisultati necessari al
raggiungimento del codice che implementasse il MOGASI. Questo perché
durante il lungo lavoro di analisi della letteratura e di progettazione, esposti
nei capitoli 3 e 4, si è esplorato l’albero di opportunità cercando anche un
riscontro pratico di tali soluzioni. Per proporre un metro di quantificazione
grossolano della complessità del MOGASI si porta all’attenzione che il solo
sorgente finale dell’algoritmo consta più di 3 700 righe di listato scritto in
linguaggio Java.
Personalmente ho trovato estremamente interessanti le tematiche affrontate
durante il presente lavoro di tesi e sono soddisfatto dei risultati ottenuti
dall’algoritmo progettato e implementato in questa sua prima versione.
Inoltre l’aver svolto un periodo di sei mesi all’interno di una azienda come
ESTECO S.p.A., ed essersi raffrontati con un panorama lavorativo
estremamente specializzato, è stato di certo un valido accrescimento
dell’esperienza e delle mie capacità personali.
119
8. Bibliografia e Sitografia
1. Dhar, V. and Ranganathan, N. - Integer programming vs. expert systems: An
experimental comparison - Commun ACM 33,3 (1990)
2. Davis, L., (Ed.) - Genetic Algorithms and Simulated Annealing - Pitman,
London, 1987
3. Holland JH. - Adaption in natural and artifical system. - The University of
Michigan press, 1975
4. De Jong, K.A. - Genetic Algorithms: A 10 Year Perspective - In [5], pp 169-177
5. Grefenstette, J.J. - Proceedings of the First International conference of Genetic
Algorithms. - Pittsburg, July 1985 Lawrence Erlbaum.
6. Michalewicz Z. - Genetic Algorithms, Numerical Optimization, and Constraints -
Morgan Kaufmann 1995, pp 151-158
7. Michalewicz Z., Fogel D.B. - How to Solve It: Modern Heuristics - Springer,
2000
8. Michalewicz Z. - Genetic Algorithms + Data Structures = Evolution Programs -
3ed., Springer,1996
9. Whitley, D. , V.S. Gordon, and K. Mathias - Lamarckian Evolution, the Baldwin
Effect and Function Optimization - In [12] , pp 6-15, 1996
10. Coveyou. R.R. and J.G. Sullivan 1961 - Permutation (71) - Communications of
the ACM, Vol A , No. 11, p A97
11. Michalewicz Z., Janikow C. - GENOCOP: A genetic algorithm for numerical
optimization problems with linear constraints - Communications of the ACM,
Vol 39 issue 12es, 1996 pp 175
12. Michalewicz Z., Nazhiyath G. - GENOCOP III: A Co evolutionary Algorithm for
Numerical Optimization Problems with Nonlinear Constraints - IEEE
International conference on Evolutional computation, 1995
120
13. Zinflou A., Gagné C., Gravel M. - Genetic Algorithm with Hybrid Integer Linear
Programming Crossover Operators for the Car-Sequencing Problem - INFOR pp
23-37, 2010
14. Ray S.S., Bandyopadhyay S., Pal S.K. - New Operators of Genetic Algorithms for
Traveling Salesman Problem - Pattern recognition, pp 497-500, 2004
15. Moon C., Kim J., Choi G,. Seo Y. - An efficient genetic algorithm for the traveling
salesman problem with precedence constraints - European Journal of Operational
Research 140, pp606-617, 2002
16. Raidl G. - An Improved Genetic Algorithm for the Multi Constrained 0–1 Knapsack
Problem - IEEE International conference on Evolutional computation, 1998
17. Orvosh D., Davis L. - Using a Genetic Algorithm to Optimize Problems with
Feasibility Constraints - IEEE International conference on Evolutional
computation, 1994
18. Zitzler E., Thiele L. - Multiobjective evolutionary algorithms: Strength Pareto -
IEEE International conference on Evolutional computation, 1999
19. Jiang Z., Liu B., Dai L.K., Wu T.J. - A Hybrid Genetic Algorithm Integrated with
Sequential Linear Programming – 2003
20. ORACLE - http://docs.oracle.com/javase/7/docs/
21. S. Chacon – Pro Git Book - http://git-scm.com/documentation
22. B. Fair, E.Isaac – FICO® - http://www.fico.com/en/Products/DMTools/...
…xpress-overview/Pages/Xpress-Documentation.aspx
23. Sobol, I.M. and Levitan, Y.L. - The production of points uniformly distributed in a
multidimensional cube - Tech. Rep. 40, Institute of Applied Mathematics, USSR
Academy of Sciences – 1976
24. Kalyanmoy Deb et al – A Fast and Elitist Multi-Objective Genetic Algoritm:
NSGA-II – Evolutionary Computation, IEEE Transaction, vol.6
25. Silvia Poles – MOGA-II: An improved Multi-Objective Genetic Algorithm –
ESTECO Technical Report 2003-06
121
26. D.E. Goldberg – Optimal Initial Population Size for Binary-coded Genetic
Algorithms – TCGA Report 85001, University of Alabama
27. D.E. Goldberg – Sizing Populations for serial and parallel genetic algorithms –
Proceedings of 3rd International Conference of Genetic algorithms, 70-79
28. D.E. Goldberg, M. Rudnick – Genetic Algorithms and the Variance of Fitness -
Complex Systems 5, 265-278
29. C.R. Reeves – Using Genetic Algorithms with Small population – Preceeding of
5th International Conference on Genetic Algorithms, 92-99
30. K.A. De Jong – An analysis of the behavior of a class of genetic adaptive systems –
1975
31. Serafini – Ricerca Operativa – Springer, 2009
32. F.S. Hillier, G.J. Lieberman – Ricerca Operativa – 8° edizione, McGraw-Hill
33. K. Deb, K. Pal – Solving Large-Scale Integer Linear Programs Using A Customized
Genetic Algorithm – KanGAL Report, 2004003
34. K. Deb, A.R. Reddy and G. Singh – Optimal Scheduling of Casting Sequence
Using genetic Algorithms – Journal of Materials and Manufacturing
35. Y. Sun, Z. Wang – The Genetic algorithm for 0-1 Programming with Linear
Constraints – Technical Report Dalian University, 116024
36. L.A. Wolsey – Integer Programming – Wiley & Sons Interscience, 1998
37. C. Silvano, W. Fornaciari, E. Villar – Multi-objective Design Space Exploration of
Multiprocessor SoC Architectures – Springer Science, 2011
38. A. Zinflou, C. Gagné, M. Gravel – Crossover Operator for the Car Sequencing
Problem – EvoWorkshop, pp. 229-239, 2007
39. P. Larranaga, C.M.H. Kuijpers, R.H. Murga I. Inza and S. Dizdarevic –
Genetic Algorithms for the Travelling Salesman Problem: A Review of
Representations and Operations – Artificial Intelligence Review 13, 129-170
40. G. Reinelt – Ruprecht Karls Universität Heidelberg
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
122
41. T. Lust – DESIR, Université Pierre et Marie Curie
https://sites.google.com/site/thibautlust/research/multiobjective-knapsack
42. D.H. Wolpert, W.G. Macready – No Free Lunch Theorems for Optimization –
IEEE Transactions on Evolutionary computation, 1997
43. Z. Michalewicz, N.F. Attia – Genetic algorithm + Simulated Annealing =
GENOCOP II: A Tool for Nonlinear Programming – International
Transaction of Operational Research, 223-240, 1994
44. S. Khuri, T. Bäck, J. Heitkötter – An Evolutionary Approach to Combinatorial
Optimization Problem – 22nd ACM Computer Science Conference, 66-73,
1994
45. W.Cohen, P. Ravikumar, S.Fienberg – A Comparison of String Distance
Metrics for Name-Matching Tasks – 2003
46. A. Cudia – Posizionamento ottimale di sensori wireless mediante algoritmi
genetici – Tesi di laurea magistrale, a.a. 2010/11
47. C. Comin, L. Onesti, C. Kavka – Towards a Standard Approach for Optimization
in Science and Engineering - ICSOFT-EA International Conference on Software
Engineering and Applications, pp. 169-177, 2013
48. T. Binh, U. Korn – Scalar Optimization with Linear and Nonlinear Constraints
Using Evolution Strategies Computational Intelligence Theory and
Application, Computer Science Volume 1226, pp. 381-392, 1997
49. E. Zitzler, L. Thiele, M. Laumanns, C.M. Fonseca, V.G. Fonseca – Performance
assessment of multiobjective optimizers: an analysis and review. – IEEE
Transactions on Evolutionary Computation, vol. 7, no. 2, pp. 117-132, 2003
Top Related