Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di programmazione...

“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: 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

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

Documents

Transcript of Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi di programmazione...