“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

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

min 𝑓(𝑥)

𝑔 𝑥 ≥ 𝑏

ℎ 𝑥 = 0

𝑙𝑖 ≤ 𝑥𝑖 ≤ 𝑢𝑖 ∀𝑥 ∈ 𝑋

Obiettivi

Definizione di un algoritmo genetico:

Multiobiettivo

General Purpose

Implementazione

Test comparativo

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Motivazioni

Interesse diretto di Esteco S.p.A.

Richiesta di risoluzione dei problemi target

Assenza di standard de facto

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Contesto Applicativo

Ottimizzazione Ingegneristica Industriale

Dimensione ridotte dei problemi

Black Box

Tempi di calcolo

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Analisi dei problemi target

Definizione categorie di problemi

Metodi risolutivi non evoluzionistici

Euristiche evolutive

Individuazione gruppi con caratteristiche comuni

Variabili decisionali

Vincoli

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Categorie individuate

Insiemi di vincoli lineari

Variabili intere e binarie

Definizione di variabile strutturata

Struttura dati: Permutazioni

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Categorie: vincoli lineari

Eliminazione delle uguaglianze

Semplificazione del sistema

Preprocessing

Sfruttamento proprietà dell’insieme convesso

Operatori specializzati: es. Crossover Algebrico

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

bAX

bXAXA 2211

22

1

1

1

11 XAAbAX

Preprocessing

Individuazione procedure possibili

Contesto Applicativo

Ha senso impiegare tempo per tentare di semplificare?

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Categorie: vincoli lineari

Eliminazione delle uguaglianze

Semplificazione del sistema

Preprocessing

Sfruttamento proprietà dell’insieme convesso

Operatori specializzati: es. Crossover Algebrico

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

bAX

bXAXA 2211

22

1

1

1

11 XAAbAX

Categorie: variabili intere

Inserimento nel contesto:

Presenza dei domini

Creazione di un gestore a posteriori di riparazione

Possibilità di operatori specializzati

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Categorie: permutazioni

Adozione codifica

Vettore di variabili strutturate

Variabile permutazione

Inserimento procedura di riparazione

Possibilità di operatori specializzati

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Travelling salesman problem

MOGASI Multi-Objective Genetic Algorithm for Structured Input

Mogasi

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Mogasi

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Doppia popolazione

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Test e Risultati

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

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

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

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

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

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)

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Problema Multiobiettivo

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

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)

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Problema Intero

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

TSP – Commesso viaggiatore: Grötschels24

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Conclusioni

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Definizione di un algoritmo:

Sfrutta delle conoscenze specifiche

Composizione verticale

General Purpose

Sviluppata prima versione MOGASI

Risultati positivi

Ottime possibilità di evoluzione

Conclusioni (2)

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Sviluppi futuri:

Raffinamento e test approfondito MOGASI

Sviluppo operatori specializzati

Espansione tecniche preprocessing

Introduzione delle riparazioni su albero/grafo

Formalizzazione del processo di ottimizzazione

Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di

programmazione lineare e ottimizzazione combinatoria

Grazie per l’attenzione Stefano Costanzo