Metaeuristiche per la costruzione degli orari dei corsi universitari

Introduzione 2Gli obiettivi del Metaheuristics Network sono di tre tipi: scientici, ingegne-ristici e di addestramento. Obiettivi scientici: il principale obiettivo scientico del MetaheuristicsNetwork è quello di migliorare la comprensione sul funzionamento dellemetaeuristiche attraverso la ricerca teorica e sperimentale. Altri obiet-tivi scientici comprendono la denizione di nuove ed ecienti metaeu-ristiche ibride, ossia, metaeuristiche che combinano componenti presedai metodi esistenti, oltre alla denizione e l'uso di una metodologiasperimentale strettamente controllata, indipendente dalla particolareinfrastruttura informatica, che permetta di eseguire dei confronti equidei risultati sperimentali. Obiettivi ingegneristici: il primo obiettivo di tipo ingegneristico consi-ste nella denizione di alcune linee guida che possano essere utili nellascelta di una particolare metaeuristica, o di una particolare componen-te, quando si aronta un nuovo problema. Un secondo obiettivo dellarete consiste nel vericare e validare le idee sviluppate su problemi presidal mondo reale. Obiettivi di addestramento: i principali obiettivi di addestramento del-la rete sono (i) far studiare ai giovani ricercatori le tecniche delle me-taeuristiche oltre che un numero di importanti problemi di ottimizza-zione, (ii) insegnare ai giovani ricercatori a progettare ed eseguire gliesperimenti in modo rigoroso, e (iii) sviluppare nei giovani ricercato-ri abilità nella gestione di progetti per mezzo della partecipazione adattività di ricerca internazionale.Durante il periodo Marzo 2002 - Marzo 2003 il Metaheuristics Network hastudiato il problema della Compilazione degli Orari dei Corsi Uni-
Introduzione 3versitari,unproblemache le università di tutto il mondo si trovano a doverfronteggiare ogni anno, e di cui ci occupiamo in questa tesi.Una formulazione generale prevede che un certo numero di eventi (lezio-ni, esercitazioni, laboratori) debba essere assegnato ad un certo numero diintervalli temporali, così che siano rispettati un insieme di vincoli. I vin-coli sono usualmente classicati in vincoli inderogabili e vincoli derogabili.I vincoli inderogabili sono vincoli che non possono essere violati in nessuncaso, ad esempio uno studente non può seguire due corsi contemporanea-mente. I vincoli derogabili sono vincoli che preferiremmo fossero soddisfatti,ma che possono essere accettati nell'orario, penalizzando ogni loro violazione,ad esempio uno studente che segue un solo evento in un giorno. Il problemagenerale della Compilazione degli Orari dei Corsi Universitari èstato dimostrato essere NP-hard, così come molti dei sottoproblemi associa-ti ai vincoli addizionali. Occorre tenere presente che istituti diversi hanno,in genere, vincoli diversi, in numero e in tipologia, in funzione delle strutturee dei corsi di studio che orono, pertanto, le soluzioni algoritmiche proposteper questo problema sono, di solito, speciche per una particolare classe divincoli.Il Metaheuristics Network ha considerato una particolare riduzione delproblema della Compilazione degli Orari dei Corsi Universitari,eha proposto il confronto delle prestazioni di cinque metaeuristiche, nelle stes-se condizioni sperimentali, su istanze di questa riduzione del problema. Lemetaeuristiche studiate includono: Ant Colony Optimization (ACO), Com-putazione Evolutiva (CE), Ricerca Locale Iterata (RLI), Simulated Annea-ling (SA) e Tabu Search (TS). Per garantire confronti equi e stesse condizionisperimentali, le implementazioni di tutti gli algoritmi fanno uso della stessarappresentazione diretta delle soluzioni e dello spazio di ricerca (tramite la
Introduzione 4
denizione di una struttura di vicinato comune e di una routine di ricercalocale comune). Inoltre, tutti gli algoritmi sono stati implementati usandolo stesso linguaggio di programmazione, facendo uso di una stessa libreria dioggetti comuni, e sono stati compilati nello stesso ambiente.Abbiamo implementato F-Race (Birattari et al., 2002), una procedura perla selezione automatica di una buona congurazione per le metaeuristiche,e l'abbiamo applicata a due algoritmi tra i quattro implementati da noi perla risoluzione del problema della Compilazione degli Orari dei CorsiUniversitari.Dunque, abbiamo lavorato ad un ciclo completo per la risoluzione di unproblema di ottimizzazione combinatoria mediante l'uso di metaeuristiche.Ci teniamo a sottolineare che, essendo lo scopo della tesi il confronto di diver-se metaeuristiche nelle stesse condizioni sperimentali, una maggiore libertànell'uso della rappresentazione delle soluzioni, nell'uso delle informazioni eu-ristiche, di un diverso linguaggio di programmazione con diverse strutturedati, potrebbe dare risultati diversi da quelli che riportiamo in questa tesi.Contributi originaliIcontributi originali sono: Il nostro algoritmo Ant Colony System è, assieme all'implementazionedi Socha et al. (2002) che segue le specicheMAX MIN Ant Sy-stem, la prima implementazione di un approccio ACO al problema dellaCompilazione degli Orari dei Corsi Universitari, apparsa inletteratura. Abbiamo implementato e testato F-Race (Birattari et al., 2002), unametodologia sperimentale ideata specicatamente per tenere conto delle
Introduzione 5
caratteristiche peculiari del problema di congurazione delle metaeuri-stiche. I risultati del confronto delle prestazioni delle cinque metaeuristiche im-plementate all'interno del Metaheuristics Network sono stati presentatialla conferenza internazionale PATAT 2002. Tale lavoro (Rossi-Doriaet al., 2002a) è stato selezionato per la pubblicazione in un prossimovolume della collana Lecture Notes in Computer Science. I risultati del confronto delle prestazioni diMAX MINAnt Systeme Ant Colony System, sono stati presentati alla conferenza internazio-nale EvoCOP 2003. Tale lavoro (Socha et al., 2003) è stato selezionatoper la pubblicazione nel volume 2611 della collana Lecture Notes inComputer Science.Struttura della tesiLa tesi è strutturata come segue: Nel Capitolo 1 si fornisce una breveintroduzione alla complessità com-putazionale e una denizione formale di problema di ottimizzazione.Successivamente si esegue una breve panoramica sul problema dellaCompilazione degli orari, no a giungere alla Compilazionedegli Orari dei Corsi Universitari, del quale sono illustrate laformulazione classica e la riduzione da noi usata per questa tesi. Nella prima parte del Capitolo 2 si introduce il concetto di metaeuristi-che, se mostra una classicazione e si illustra l'attuale Stato dell'Arte.Successivamente si descrivono le linee guida seguite per l'implementa-zione delle metaeuristiche, e si illustrano le nostre implementazioni per
Introduzione 6
la risoluzione del problema della Compilazione degli Orari deiCorsi Universitari. Nel Capitolo 3 si introduce il problema della congurazione delle me-taeuristiche, dandone una denizione formale. Si illustrano le idee ge-nerali che stanno dietro ai metodi di racing e si presenta F-Race, unmetodo ideato esplicitamente per tenere conto delle caratteristiche pe-culiari del problema di congurazione delle metaeuristiche. L'ultimaparte del capitolo descrive gli esperimenti eettuati con F-Race perla congurazione di due algoritmi tra quelli da noi implementati perrisolvere il problema della Compilazione degli Orari dei CorsiUniversitari. Nel Capitolo 4 si illustrano gli esperimenti, eettuati nelle stesse con-dizioni sperimentali, inizialmente per il confronto delle metaeuristicheimplementate all'interno del Metaheuristics Network, e successivamenteesteso alle nostre implementazioni. Nelle Conclusioni si analizzano i risultati ottenuti mediante i diversiapprocci studiati e si presentano alcuni possibili sviluppi futuri.
Capitolo 1Denizione del problemaAdottando la terminologia presente in Ausiello et al. (1999), con il termineproblema ci riferiamo informalmente ad una domanda generale a cui si deverispondere, di solito con parametri e variabili con valori non specicati. Iltermine istanza si riferisce al problema per il quale sono stati specicati ivalori dei parametri e delle variabili. In generale, si esprime il problema intermini di una qualche relazione matematica R  I  S, dove I è l'insiemedelle istanze del problema e S è l'insieme delle soluzioni del problema. Al-ternativamente, si può considerare un predicato P (x; s) che è vero se e solose (x; s) 2 R.Un problema può essere formulato in tre dierenti versioni:Problema di decisione: si vuole determinare se una istanza x 2 I soddiso meno una certa condizione, ossia, se Q(x) è vericato, dove Q è unospecico predicato (unario). In questo caso, la relazione R si riduce aduna funzione f : I ! S, dove S è l'insieme binario S = fsi; nog.Problema di ricerca: data una qualunque istanza x 2 I, si trovi unasoluzione s 2 S, tale che (x; s) 2 R è vericato;
Capitolo 1. Denizione del problema 8Problema di ottimizzazione: data un'istanza x 2 I, si trovi il valoredella migliore soluzione sopt (rispetto ad una qualche misura), tratutte le soluzioni s 2 S tali che (x; s) 2 R è vericato.In generale, siamo interessati a trovare l'algoritmo più eciente per la risolu-zione di un problema, dove per eciente si intende, in senso generale, quelloche abbisogna delle minori risorse. Poiché il tempo impiegato è spesso unfattore dominante ai ni pratici, normalmente con algoritmo più eciente siintende l'algoritmo più veloce. Di questo si occupa la teoria della complessi-tà computazionale (Garey e Johnson, 1979) ed in particolar modo, la teoriadella NP-completezza.La complessità temporale di un algoritmo è misurata da una funzioneche ritorna il massimo tempo di esecuzione di cui l'algoritmo necessita perrisolvere istanze del problema di una data dimensione,dove la dimensione diun'istanza riette la quantità di simboli necessari a descrivere l'istanza. Siassume quindi che esista un qualche schema di codica usato per descrive-re l'istanza sottoforma di stringa di caratteri su un qualche alfabeto nito.Poiché l'uso di schemi di codica diversi produce, in generale, stringhe dilunghezza diversa per la stessa istanza, si assume che ad ogni problema siaassociato un pressato schema di codica che mappa le istanze del problemanelle stringhe che le descrivono.Un algoritmo opera in tempo polinomiale, se la sua complessità temporaleè O(p(n))1 per qualche polinomio p,dove n indica la dimensione dell'istanza;nel caso in cui non sia possibile trovare una tale limitazione, si dice chel'algoritmo opera in tempo esponenziale.1Siano f e g due funzioni da N! N; scriveremo f(n)=O(g(n)) se esistono due interipositivi c e n0 tali che 8n>n0, f(n)  c 
 g(n).
Capitolo 1. Denizione del problema 9
Se il numero di passi necessari alla risoluzione dell'istanza cresce in modopiù che polinomiale, si dice che il problema è intrinsecamente dicile. Spessoci si riferisce a tali problemi come a problemi intrattabili da un punto divista pratico. Per tali problemi dobbiamo spesso limitarci a calcolare unasoluzione che, pur non essendo quella ottimale, è vicina (rispetto ad unaqualche misura) all'ottimo, e può essere determinata in tempo polinomiale.NP-completezzaLa teoria della NP-completezza formalizza la distinzione tra problemi facilie dicili. Per far questo si usa considerare la formulazione come problemadi decisione. Le conclusioni tratte non sono limitate da questo fatto poiché ilproblema di ricerca (e quindi il problema di ottimizzazione) non è più facileda risolvere del problema di decisione, e se il problema di ricerca può essererisolto grazie ad un algoritmo eciente (nel senso generale detto prima, percui abbisogna di poche risorse), allora lo stesso si può dire per il problema didecisione.La teoria dellaNP-completezza divide i problemi in due classi. La primaè la classe P dei problemi trattabili.Denizione 1.1 La classe P è la classe dei problemi di decisione che pos-sono essere risolti da un algoritmo in tempo polinomiale.La classe NP può essere denita informalmente per mezzo degli algoritminon-deterministici. Data un'istanza x 2 I, un algoritmo non-deterministicopuò essere pensato composto di una parte in cui si propone una soluzione.La soluzione è quindi controllata nella seconda parte da un algoritmo deter-ministico polinomiale. La classe NP è la classe di problemi le cui soluzionisono vericabili in tempo polinomiale.
Capitolo 1. Denizione del problema 10Denizione 1.2 LaclasseNP è la classe dei problemi di decisione che pos-sono essere risolti da un algoritmo non-deterministico in tempopolinomiale.Un problema di decisione che può essere risolto da un algoritmo determi-nistico in tempo polinomiale può essere risolto anche da un algoritmo non-deterministico in tempo polinomiale: pertanto, P  NP. Probabilmenteuna delle più importanti questioni aperte in informatica teorica è decidere seP =NP. È largamente diusa l'opinione che P 6=NP, nonostante non siastata fornita ancora alcuna provaperquesta congettura.Poiché non è possibile mostrare che NPnP è non vuoto, a meno che siafornita una prova per P 6= NP, la teoria della NP-completezza forniscerisultati in una forma debole, sotto l'ipotesi di P 6=NP.Denizione 1.3 Un problema  è riducibile in tempo polinomiale al proble-ma 0, se esiste un algoritmo che trasforma ogni istanza di  in un'istanza di0 in tempo polinomiale e che, per ogni istanza di , risponde a tale istanzasi se e solo se la risposta della corrispondente istanza di 0 è si.In modo informale questa denizione dice che se  può essere ridotto a0 in tempo polinomiale, allora il problema 0 è almeno altrettanto di-cile da risolvere quanto il problema . Usando la nozione di riducibilitàin tempo polinomiale possiamo procedere a denire la classe dei problemiNP-completi.Denizione 1.4 Un problema  è NP-completo se e solo se  2NPe 80 2NP vale che 0 è riducibile in tempo polinomiale a .La classe dei problemiNP-completi è in un certo senso la classe dei problemipiù dicili appartenenti a NP. Se un problema NP-completo può essererisolto da un algoritmo in tempo polinomiale, allora tutti i problemi in NP
Capitolo 1. Denizione del problema 11
possono essere risolti in tempo polinomiale. Comunque, ad oggi, nessun pro-blema NP-completo è stato risolto da un algoritmo in tempo polinomiale.Nonostante non sia stato provato, ad oggi, che i problemi NP-completi nonpossano essere risolti per mezzo di algoritmi che operano in tempo polinomia-le, ci sono forti indizi a favore della possibilità che tali algoritmi non esistano.Da tutto questo si può derivare che, provata l'appartenenza di  alla classedei problemi NP-completi, non esiste un modo eciente di risolvere . Adoggi molti problemi sono stati mostrati essere NP-completi: un elenco lo sitrova in Garey e Johnson (1979).Come abbiamo osservato, i concetti base della teoria della complessitàsono stati introdotti facendo riferimento ai problemi di decisione. Per quan-to detto n'ora, il problema di ottimizzazione non è più facile del proble-ma di decisione associato. Pertanto, provare che il problema di decisione èNP-completo implica che il problema di ottimizzazione sia dicile da ri-solvere. Problemi che sono dicili quanto problemi NP-completi, ma nonnecessariamente elementi di NP sono detti problemi NP-hard.Denizione 1.5 Un problema  è NP-hard se e solo se 8 0 2 NP valeche 0 è riducibile in tempo polinomiale a .Pertanto, ogni problemaNP-completo è anche un problemaNP-hard. Dal-l'altra parte, se il problema di ottimizzazione combinatoria formulato comeproblema di decisione èNP-completo, allora la formulazione come problemadi ottimizzazione è NP-hard.Diamo una denizione formale di problema di ottimizzazione.Denizione 1.6 Un problema di ottimizzazione opt è caratterizzato dallaseguente quadrupla di oggetti (I,SOL,m,goal) tale che:
Capitolo 1. Denizione del problema 12
1. I è l'insieme delle istanze di opt;2. SOL è una funzione che associa ad una qualunque istanza x 2 I,l'insieme delle soluzioni ammissibili di x;3. Data un'istanza x 2 I ed una soluzione ammissibile s 2 SOL(x),m(x; s) 2 R indica la misura di s. La funzione m è chiamata anchefunzione obiettivo.4. goal 2 {MAX,MIN} specicaseopt èunproblema di massimizzazioneo minimizzazione.Data un'istanza x, identichiamo con SOLopt(x) l'insieme di tutte le so-luzioni ottime di x. Una soluzione ottima sopt(x) 2 SOLopt(x) è tale chem(x; sopt(x)) = goal{m(x; z)jz 2 SOL(x)}. Il valore di una soluzione ottimasopt(x) in x sarà denotato con mopt(x).È importante notare che ogni problema di ottimizzazione opt ha un pro-blema di decisione associato optD . Nel caso in cui opt sia un problema diminimizzazione, optD chiede se, data un'istanza x 2 I e un qualche valo-re K > 0, esiste una soluzione ammissibile s(x) 2 SOL(x) per cui valgam(x; s(x))  K. Per i problemi di massimizzazione la denizione è analoga,con m(x; s(x))  K. Oltre al problema di decisione, opt ha associato ancheun problema di valutazione optV , il quale chiede, data un'istanza x 2 I,quale sia il valore della soluzione ottima mopt(x).Più precisamente, possiamo dire che la denizione di un problema diottimizzazione opt conduce alle formulazioni dei tre seguenti problemi: Problema di costruzione (optC): data un'istanza x 2 I, si troviuna soluzione ottima sopt(x) 2 SOLopt(x) e la sua misura mopt(x).
Capitolo 1. Denizione del problema 13
 Problema di valutazione (optV ): data un'istanza x 2 I, si trovi ilvalore della soluzione ottima mopt(x). Problema di decisione (optD): data un'istanza x 2 I e un valoreK 2 R+, si dica se mopt(x)  K (se goal = MIN) o se mopt(x)  K(se goal = MAX).Si noti che, per ogni problema di ottimizzazione opt, il corrispondente pro-blema di decisione optD non è più dicile del corrispondente problema dicostruzione optC . Infatti, data un'istanza x, per rispondere al problemaoptD è suciente eseguire un qualche algoritmo che risolva optC , ottenendoin tal modo una soluzione ottima sopt(x) e la sua misura mopt(x); è quindisuciente controllare se m(x; sopt(x))  K ( oppure  K).
Il resto del capitolo è organizzato come segue: il Paragrafo 1.1 introduceil problema della Compilazione degli Orari; il Paragrafo 1.2 introduceil problema della Compilazione degli Orari Scolastici; inne il Pa-ragrafo 1.3 introduce il problema della Compilazione degli Orari deiCorsi Universitari.1.1 La compilazione degli orariSecondo il vocabolario della lingua italiana Treccani2 con orario si intende:1. predisposizione dell'ordine in cui determinati avvenimenti, atti o ope-razioni debbono succedersi nel tempo, con indicazione dell'ora in cuihanno inizio e termine singolarmente o nel loro insieme;2. con signicato più concreto, il prospetto che illustra l'orario predisposto.2Istituto della Enciclopedia Italiana fondata da Giovanni Treccani, 1989
Capitolo 1. Denizione del problema 14Le varie tipologie di orari esistenti giocano un ruolo importante nella no-stra società: si pensi, ad esempio, ai mezzi di trasporto quali aerei, treni,navi e autobus, oppure agli istituti scolastici. Non stupisce quindi che unasempre crescente quantità di risorse sia stanziata per la loro compilazione.Questo è maggiormente vero per quelle aziende che possono operare in modopiù eciente ottimizzando la gestione temporale delle loro attività. Ancheper questo la Compilazione degli Orari è uno dei problemi storici del-la Ricerca Operativa. Nella Compilazione degli Orari devono essererispettati un certo numero di criteri, spesso identicati in letteratura co-me vincoli inderogabili, e nel contempo si deve minimizzare il numero diviolazioni a criteri di minore importanza, detti anche vincoli derogabili.3Esempi di vincoli inderogabili sono l'uso non contemporaneo da parte degliaerei di una stessa pista per l'atterraggio o il decollo, oppure, nel caso degliorari scolastici, il fatto che un docente non possa tenere più di una lezionenello stesso momento. I vincoli derogabili sono invece caratteristiche che sivorrebbe non violare: ad esempio, avere una frequenza maggiore per i tre-ni usati dai pendolari per recarsi e tornare dal lavoro, oppure assegnare unnumero basso di ore di lezione consecutive agli studenti universitari.Compilare manualmente gli orari richiede di solito un grosso dispendio ditempo. In situazioni reali, dove i vincoli inderogabili possono mutare abba-stanza di frequente (si pensi, per esempio, ad un binario, una pista oppureun'aula che diventano inagibili per un certo intervallo di tempo) è spesso im-possibile adattare il vecchio orario; pertanto, occorre compilarne uno nuovo.Per di più gli orari costruiti manualmente spesso non soddisfano alcuni criteri3La maggior parte della letteratura sulla compilazione degli orari è in lingua inglese,dove si usa indicare i criteri con i termini hard constraints e soft constraints. Da questopunto in avanti useremo in modo consistente i rispettivi termini italiani vincoli inderogabilie vincoli derogabili.
Capitolo 1. Denizione del problema 15
(si pensi a quegli orari dei corsi universitari che prevedono due insegnamen-ti in contemporanea impedendo agli studenti di seguirli entrambi). Proprioper questo, durante gli ultimi quarant'anni la compilazione automatica degliorari è stata oggetto di una sempre crescente attenzione da parte dei ricer-catori, che hanno cominciato ad applicare anche tecniche quali, ad esempio,gli Algoritmi Genetici, il Tabu Search ed il Simulated Annealing.Nel 1995 ha preso il via una serie di conferenze internazionali biennalisulle tecniche di compilazione automatica degli orari:The International Se-ries of Conferences on the Practice and Theory of Automated Timetabling4- PATAT (Burke et al., 1995; Burke e Carter, 1997; Burke e Erben, 2000;Burke e De Causmaecker, 2002). Una menzione particolare merita anchel'associazione EURO (Association of European Operational Research Socie-ties) di cui fa parte un gruppo di lavoro, EURO-WATT (EURO WorkingGroup on Automated Timetabling), che si incontra una volta all'anno, ge-stisce un bollettino via posta elettronica e mantiene un sito web5 con molteinformazioni di interesse sui problemi di creazione degli orari, quali un'estesabibliograa e molti benchmark.1.2 La compilazione degli orari scolasticiIl problema della Compilazione degli Orari Scolastici consiste neldeterminare una sequenza di eventi (incontri tra docenti e studenti) in unpressato periodo di tempo, soddisfacendo una serie di vincoli. In letteratura4Una selezione di articoli è pubblicata nella collana Lecture Notes in Computer Scienceedita dalla Springer-Verlag (Burke e Ross, 1996; Burke e Carter, 1998; Burke e Erben,2001).5http://www.asap.cs.nott.ac.uk/watt/