�ݺ�ߣ

“Definizione e sviluppo di un algoritmo genetico
multiobiettivo per problemi di programmazione
lineare e ottimizzazione combinatoria”
Anno accademico 2012-2013
Relatore Laureando
Chiar.mo Prof. Lorenzo Castelli Stefano Costanzo
Correlatore
Dott. Alessandro Turco
TESI DI LAUREA
IN
MODELLI DI OTTIMIZZAZIONE
Dipartimento di Ingegneria e Architettura
Università degli Studi di Trieste

Problema
Risolvere problemi rientranti in:
 Programmazione lineare
 Ottimizzazione combinatoria
 Programmazione intera
Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di
programmazione lineare e ottimizzazione combinatoria
min 𝑓(𝑥)
𝑔 𝑥 ≥ 𝑏
ℎ 𝑥 = 0
𝑙𝑖 ≤ 𝑥𝑖 ≤ 𝑢𝑖 ∀𝑥 ∈ 𝑋

Problema (2)
 Presenza di variabili continue, intere e binarie
 Vincoli lineari e non lineari
 Limitazioni di dominio
min 𝑓(𝑥)
𝑔 𝑥 ≥ 𝑏
ℎ 𝑥 = 0
𝑙𝑖 ≤ 𝑥𝑖 ≤ 𝑢𝑖 ∀𝑥 ∈ 𝑋

Obiettivi
Definizione di un algoritmo genetico:
 Multiobiettivo
 General Purpose
Implementazione
Test comparativo

Motivazioni
Interesse diretto di Esteco S.p.A.
Richiesta di risoluzione dei problemi target
Assenza di standard de facto

Contesto Applicativo
 Ottimizzazione Ingegneristica Industriale
 Dimensione ridotte dei problemi
 Black Box
 Tempi di calcolo

Analisi dei problemi target
 Definizione categorie di problemi
 Metodi risolutivi non evoluzionistici
 Euristiche evolutive
 Individuazione gruppi con caratteristiche comuni
 Variabili decisionali
 Vincoli

Categorie individuate
 Insiemi di vincoli lineari
 Variabili intere e binarie
 Definizione di variabile strutturata
 Struttura dati: Permutazioni

Categorie: vincoli lineari
 Eliminazione delle uguaglianze
 Semplificazione del sistema
 Preprocessing
 Sfruttamento proprietà dell’insieme convesso
 Operatori specializzati: es. Crossover Algebrico
bAX 
bXAXA  2211
22
1
1
1
11 XAAbAX 


Preprocessing
 Individuazione procedure possibili
 Contesto Applicativo
 Ha senso impiegare tempo per tentare di semplificare?

Categorie: variabili intere
 Inserimento nel contesto:
 Presenza dei domini
 Creazione di un gestore a posteriori di riparazione
 Possibilità di operatori specializzati

Categorie: permutazioni
 Adozione codifica
 Vettore di variabili strutturate
Variabile permutazione
 Inserimento procedura di riparazione
 Possibilità di operatori specializzati
Travelling salesman problem

MOGASI
Multi-Objective Genetic Algorithm for Structured Input

Mogasi

Doppia popolazione

Test e Risultati
Necessarie molte tipologie di problemi test:
1. Problema vincolato singolo obiettivo
2. Problema multiobiettivo libero e vincolato
3. Problema intero singolo e multiobiettivo
4. TSP – Problema del commesso viaggiatore

Competitors
 GENOCOP III
 Non-dominated Sorting Genetic Algorithm, NSGA-II
 Multi-Objective Genetic Algorithm, MOGA-II
 MOGA-II con operatore specializzato, CUDIA

Problema vincolato Singolo Obiettivo
Nome del test t13
Funzione Obiettivo:
Vincoli:
Domini:
Valori ottimi trovati Scostamento
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
10.00
12.00
14.00
16.00
18.00
20.00
22.00
24.00
26.00
Genocop
MOGASI
NSGA-II
MOGA-II

Problema vincolato Singolo Obiettivo (2)

Problema Multiobiettivo
Nome del test SRN
Funzione Obiettivo:
Vincoli:
Domini:
Valutazione dei fronti tramite IGD:
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

Problema Multiobiettivo (2)

Problema Intero

TSP – Commesso viaggiatore: Grötschels24

Conclusioni
Definizione di un algoritmo:
 Sfrutta delle conoscenze specifiche
 Composizione verticale
 General Purpose
Sviluppata prima versione MOGASI
 Risultati positivi
 Ottime possibilità di evoluzione

Conclusioni (2)
Sviluppi futuri:
 Raffinamento e test approfondito MOGASI
 Sviluppo operatori specializzati
 Espansione tecniche preprocessing
 Introduzione delle riparazioni su albero/grafo
 Formalizzazione del processo di ottimizzazione

Grazie per l’attenzione
Stefano Costanzo

�ݺ�ߣ

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di programmazione lineare e ottimizzazione combinatoria

More Related Content

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di programmazione lineare e ottimizzazione combinatoria