Il settore scientifico di maggior interesse per Vittorio Maniezzo è
l'algoritmica computazionale. In questo ambito, i principali temi
di ricerca di mio interesse corrente sono:
1) metodi di programmazione matematica per lo sviluppo di tecniche
mateuristiche.
Sono convinto dell'opportunità di inserire elementi di
programmazione matematica all'interno di framework metaeuristici,
sia degli attuali che di nuovi da progettare specificamente. Gli
elementi che ritengo di maggior interesse sono i bound al costo
della soluzione ottima e dati sulla soluzione duale. In accordo a
questa linea, ho prima sviluppato una variante specifica per la
metaeuristics Ant Colony Optimizaton (ACO, un approccio che ho
contribuito a originare), poi dato vita a una serie di workshop
internazionali, chiamati matheuristics, dedicati
appunto alle possibilità di utilizzo di elementi di programmazione
matematica in contesti metaeuristici.
2) Sistemi di Supporto alle Decisioni e Sistemi Informativi
Geografici
Sono estremamente intressato al ciclo completo del processo
ottimizzativo: analisi di problemi reali, modellizzazone del
problema, studio di tecniche risolutive, validazione dei risultati
computazionali. Il settore in cui maggiormante ho trovato modo di
sviluppare sistemi di ottimizzazione validati su problemi reali
(quindi sistemi di supporto alle decisioni) è quello della
logistica computazionale. I Sistemi Informatici Geografici sono una
precondizione alla possibilità di lavorare computazionalmente in
logistica distributiva. L'analisi di questo settore mi ha portato
alla definizione di un sistema open-source personalizzato, chiamato
Ertha.
Altre mie linee di ricerca sono o sono state:
- algoritmi a ispirazione naturale, ant colony optimization
(ACO);
- production scheduling, project scheduling;
- modellizzazione cognitiva, apprendimento psicogenetico;
- automi cellulari per simulazione di processi dinamici (flussi di
traffico, dinamiche di inquinanti).
Durante la mia carriera scientifica e tecnica, ho
maturato particolari competenze nelle seguenti aree:
·
Algoritmi di ottimizzazione (ottimizzazione
combinatoria, algoritmi metaeuristici);
·
Sistemi di Supporto alle Decisioni e Sistemi Informativi Territoriali;
Altre linee di ricerca, in particolare su modellistica
e simulazione con automi cellulari e su modelli
cognitivi per l'apprendimento automatico verranno nel seguito
introdotte anche se costituiscono filoni secondari di
interesse.
1. Algoritmi metaeuristici ad ispirazione
naturale
Sono
sempre stato interessato all'identificazione, modellizzazione e
soluzione pratica dei problemi di ottimizzazione che sottostanno a
tematiche teoriche o applicative, anche molto differenziate fra
loro. A questo fine, ho approfondito lo studio di algoritmi
metaeuristici ad ispirazione naturale, quali gli algoritmi
genetici, le strategie evolutive, ecc. Applicazioni da me
affrontate riguardano la logistica computazionale, l'apprendimento
in reti neurali, la definizione di orari di scuole superiori, la
schedulazione di task su macchine parallele, la progettazione
logica di Data Warehouse, la definizione della topologia di reti
peer-to-peer, ecc.
Queste competenze hanno portato allo sviluppo di un algoritmo
originale, il sistema formiche (ant system, ACO) di cui sono uno dei tre ideatori
originari, assieme a M.Dorigo e A.Colorni. Riguardo all'impatto che
questa nostra proposta ha avuto sulla comunità di ricerca
internazionale, tengo a sottolineare che:
·
negli anni 1998, 2000, 2002 e 2004 si è tenuta a Bruxelles una
conferenza internazionale interamente dedicata al sistema formiche
e alle sue applicazioni (ANTS'98, ANTS'2000, ANTS'2002, ANTS'2004).
Numerose altre conferenze internazionali ospitano sessioni
interamente dedicate a questo approccio, così come ci sono stati
libri e special issues di riviste di ricerca internazionali
dedicate all'argomento.
·
secondo l'ISI (Institute for Scientific Information), l'articolo
(A9) che presentava il sistema è quello che a oggi ha avuto più
citazioni (195) fra tutti quelli che avevano autori affiliati al
Politecnico di Milano.
·
secondo CiteSeer (citeseer.ist.psu.edu) attualmente i miei lavori
nel complesso hanno avuto 615 citazioni, il che mi pone nella
classifica generale per autori (Most cited authors in
Computer Science - May 2005) in posizione assoluta 3280, cioè
fra i 70 informatici italiani più citati.
Più
in dettaglio, i miei lavori hanno trattato dei seguenti temi.
1.1 Metaeuristiche, stato dell'arte
Ho approfondito lo studio di algoritmi di ottimizzazione ad
ispirazione naturale, quali gli algoritmi genetici, le strategie
evolutive, ecc. Il lavoro, con particolare ma non esclusivo
riferimento alle applicazioni a problemi di ottimizzazione
combinatoria, ha portato poi allo sviluppo di estensioni e nuove
applicazioni di algoritmi noti. Ho anche approfondito lo studio e
l'implementazione degli algoritmi già presentati in letteratura in
ambiente parallelo, e quello della reimplementazione uniforme dei
principali approcci su uno stesso testset di istanze, che ha
permesso di valutare, in un momento in cui studi di questo genere
non erano ancora comuni, l'efficacia relativa delle varie tecniche
e quindi di dominanze fra loro.
Ricerca svolta in collaborazione con: A.Colorni, Politecnico di Milano, M.Dorigo, Univ.
Libre de Bruxelles, D.Vigo, Univ. di Bologna.
Pubblicazioni inerenti:A6, A10, A17, B1, B2, B9, E3.
1.2 ANTS
Di particolare rilievo è un nuovo algoritmo di ottimizzazione ad
ispirazione naturale, il Sistema formiche (Ant System, ACO, ANTS). Il processo naturale
ispiratore riguarda le modalità con cui le formiche di una colonia
riescono ad identificare un cammino efficiente fra la colonia
stessa e sorgenti di cibo. Le caratteristiche di distribuzione
massiccia su agenti computazionalmente semplici, e con meccanismi
di comunicazione globali molto efficienti che si riscontrano nel
fenomeno naturale in esame, ci hanno suggerito meccanismi
riutilizzabili in un algoritmo distribuito di ottimizzazione che ha
trovato molte applicazioni pratiche e si è dimostrato
concorrenziale con i migliori algoritmi metaeuristici finora
proposti in letteratura.
Ricerca svolta in collaborazione con: A.Colorni, Politecnico di Milano, M.Dorigo, Univ.
Libre de Bruxelles, R.Hartl,Univ. Vienna,
M.Reimann, ETH, Zurigo.
Pubblicazioni inerenti: A9, A19, A20, A22, B7, B9,
B10, B11, B12, E2, G13, G15, G17, G18, G19, G20.
1.3 Reti
neurali
Partendo dalle applicazioni di algoritmi noti, ho utilizzato un
algoritmo genetico opportunamente adattato come algoritmo di
apprendimento per reti neurali feedforward a livelli. I risultati
ottenuti, in particolare quelli derivanti da una implementazione
parallela del mio algoritmo, sono stati interessanti, anche quando
confrontati con quelli ottenibili con l'algoritmo più utilizzato
per questo tipo di applicazione, cioè Backpropagation. In seguito
il mio modello è stato anche valutato per l'apprendimento di
strategie di controllo di agenti che affrontano compiti che
richiedono cooperazione.
Pubblicazioni inerenti: A5.
1.4 Orario
scolastico
Una seconda applicazione di un algoritmo genetico opportunamente
modificato che ha portato a risultati interessanti riguarda la
definizione di orari scolastici, in particolare per scuole medie
superiori italiane. Abbiamo infatti tenuto conto di tutti i vincoli
e i desiderata tipici di questo tipo di applicazione e abbiamo
sviluppato un sistema basato su algoritmi genetici, tabu search e
simulated annealing che definisce in modo automatico, con
possibilità di aggiustamenti da parte dell'utente, orari di scuole
superiori.
Ricerca svolta in collaborazione con: A.Colorni, Politecnico di Milano, M.Dorigo, Univ.
Libre de Bruxelles.
Pubblicazioni inerenti: A14, E1, G3, G8.
1.5 Schedulazione
In questa area ho lavorato sia con algoritmi metaeuristici che di
ottimizzazione più tradizionali. Con algoritmi metaeuristici ho
sviluppato un'applicazione di un algoritmo genetico ibrido, in
questo caso integrato con algoritmo di tipo tabu search a soglia,
riguarda lo scheduling di processi su una macchina parallela. I
risultati, anche comparativi, raggiunti permettono di giudicare con
interesse la tecnica in esame. Con tecniche più matematiche ho
affrontato il problema del supporto alla gestione di progetti
complessi. I lavori su problemi di schedulazione affrontati con
algoritmi ACO sono già stati riportati nella sezione 1.4.
Ricerca svolta in collaborazione con: A.Mingozzi,
D.Vigo, Università di Bologna.
Pubblicazioni inerenti: A12, A13, A21, B4.
2. Sistemi di supporto alle
decisioni
Ho approfondito i
sistemi di supporto alle decisioni (DSS) e i particolare i sistemi
informativi territoriali (SIT, GIS) essenzialmente per definire
ambienti efficienti in cui validare gli algoritmi di cui al punto
1. Questo mi ha comunque permesso di fornire alcuni risultati di
ricerca di interesse per la comunità internazionale.
2.1 Analisi multicriteriale, sistemi distribuiti,
In questi anni ho collaborato con il settore DSS della DG XIII
della Commissione Europea nella definizione di architetture
distribuite per sistemi di supporto alle decisioni e studi di casi
reali, con particolare riferimento (per quanto riguarda la mia
partecipazione) agli aspetti architetturali ed algoritmici del
supporto. Questo ha portato a contributi alla realizzazione di vari
sistemi di analisi di politiche ambientali, quali quelli per la
gestione di rifiuti tossici, di rifiuti urbani e di risorse
idriche.
In collaborazione con: P.Haastrup, M.Paruccini,
I.Mendes, M.Mattarelli (Centro Comune di Ricerca della Commissione
Europea), R.Wolfler (Univ. de Troyes, France).
Pubblicazioni inerenti: A1, A4, A15, A16, A18, B8,
I1, I2.
2.2 Logistica computazionale
Una particolare tematica, inizialmente sempre inquadrata nelle
attività appena descritte ma che ha avuto un particolare successo
sono algoritmi per logistica computazionale. Mi sono interessato
sia al trasporto merci (percorsi di veicoli, localizzazione di
magazzini) che di persone (soprattutto car pooling,
un servizio di mobilità alternativa basato sulla condivisione di
veicoli privati). Gli approcci seguiti sono di ottimizzazione sia
euristica che metauristica.
In collaborazione con: R.Baldacci (Univ. Modena e
Reggio Emilia), A.Mingozzi (Univ. Bologna), R.Wolfler (Univ.
Troyes).
Pubblicazioni inerenti: A23, A24, A25, B5 (e
B5bis), B8, B13, E5, G16, H1, H2, H3.
3.Apprendimento automatico,
modelli cognitivi
I lavori sviluppati in questo ambito erano inquadrati nel mio
programma di studi, presso il Politecnico di Milano, per ottenere
il dottorato di ricerca. Al termine del dottorato, ho avuto
occasioni solo saltuarie di portare avanti ricerche in questo
settore. Mi sono interessato alla definizione di algoritmi di
apprendimento automatico traendo ispirazione da modelli cognitivi
dell'apprendimento umano. In accordo con questo criterio, ho
sviluppato due algoritmi.
Il primo ha come teoria cognitiva di riferimento la teoria
psicogenetica di J.Piaget. L'obiettivo è quello di definire un
algoritmo di apprendimento non supervisionato cognitivamente ben
fondato, inquadrabile nel contesto degli agenti autonomi e in
particolare tale da permettere ad un decisore autonomo di
sviluppare piani d'azione specificati a livello sensomotorio per
ottenere obiettivi dati.
Pubblicazioni inerenti: A27, G12, G14.
Il secondo algoritmo, ora non più investigato, ha come teoria di
riferimento la teoria di concettualizzazione basata su prototipi
sviluppata da E.Rosch, e ha portato alla definizione di un
algoritmo di classificazione induttiva che ha come caratteristica
saliente la possibilità di calcolare un livello di appartenenza di
ogni entità ad ogni classe di interesse. Questo risultato può
essere visto sia come il calcolo di una funzione di appartenenza
per insiemi fuzzy corrispondenti alle classi, sia come
identificazione di un'appartenenza graduata multipla alle classi di
riferimento.
Pubblicazioni inerenti: E4, F1, G1, G2, G7, G9,
G10.
4. Modellistica e
simulazione
I lavori sviluppati in questo ambito erano inquadrati nel mio
programma di studi, presso il Politecnico di Milano, per ottenere
il dottorato di ricerca. Al termine del dottorato, ho avuto
occasioni solo saltuarie di portare avanti ricerche in questo
settore. Ho seguito due progetti di ricerca che studiavano
metodologie atipiche di simulazione, in particolare utilizzavano la
fisica qualitativa e gli automi cellulari.
La linea di ricerca basata su automi cellulari vuole valutare le
possibilità di utilizzo di questo approccio come alternativa ai
metodi di simulazione numerica basati su equazioni differenziali.
Abbiamo prima usato come un problema di confronto la diffusione dei
inquinanti nell'atmosfera e abbiamo sviluppato un codice di
simulazione che considera eventi definiti su una granularità
spaziale più grossa. Abbiamo verificato come l'identificazione dei
fenomeni in esame era grandemente semplificata seguendo questo
approccio, che era possibile ricondurre anche formalmente le
relazioni da noi identificate ai risultati teorici già noti, e che
il codice di simulazione era sia molto efficiente che molto
facilmente parallelizzabile. Più recentemente abbiamo applicato le
stesse tecniche alla simulazione del traffico stradale in rotonde
urbane.
Ricerca svolta in collaborazione con: G.Guariso, Politecnico di Milano, P.Salomoni,
Università di Bologna, E.Campari, Università di Bologna.
Pubblicazioni inerenti: A3, A11, G4, G22.
Le ricerche centrate sui metodi di fisica qualitativa, ora non più
attive, avevano come obiettivo la costruzione di un sistema di
simulazione di sistemi reali non banali, per i quali non fosse
possibile identificare o simulare in modo preciso tutte le
variabili rilevanti. I sistemi di questo genere normalmente hanno
comunque elementi costitutivi per i quali è possibile effettuare
simulazioni numeriche e quindi per i quali una simulazioni
qualitativa farebbe perdere molta informazione. Il nostro lavoro si
è concentrato sullo studio di metodologie di integrazione fra
simulazione qualitativa e numerica, sviluppando un sistema che
comprendesse questa possibilità.
Ricerca svolta in collaborazione con: A.Bonarini,
Politecnico di Milano.
Pubblicazioni inerenti: A2, G5.
Una terza linea di ricerca che può venire inquadrata in questo
gruppo, ora non più attiva, riguarda la simulazione dello studente
in un sistema di insegnamento assistito. Ho contribuito alla
realizzazione di un sistema che aveva come obiettivo l'insegnamento
di semplici conoscenze di geometria piana ad uno studente. Era
necessario definire un modello dello studente con cui il sistema
interagiva sulla base del quale prendere decisioni relative alle
modalità dell'interazione futura. Questo è stato realizzato con
tecniche di apprendimento automatico.
Ricerca svolta in collaborazione con: A.Carbonaro, G.Casadei, M.Roccetti, P.Salomoni,
Università di Bologna.
Pubblicazioni inerenti: A7, B3.
