Stochastic local search methods for highly constrained combinatorial optimisation problems [Elektronische Ressource] : graph colouring, generalisations, and applications / von Marco Chiarandini
337 pages
Deutsch
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Stochastic local search methods for highly constrained combinatorial optimisation problems [Elektronische Ressource] : graph colouring, generalisations, and applications / von Marco Chiarandini

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
337 pages
Deutsch

Description

StochasticLocalSearchMethodsforHighlyConstrainedCombinatorialOptimisationProblemsGraphColouring,Generalisations,andApplicationsDissertationsschriftzurErlangungdesakademischenGradeseinesDoktorsderNaturwissenschaften(Dr.rer.nat.)vonDipl. Ing.MarcoChiarandiniausUdine,ItalienReferent:Prof.Dr.WolfgangBibelKorreferent:Dr.habil.ThomasStützleTagderEinreichung:6.Mai2005TagdermündlichenPrüfung:8.Juli2005GenehmigteDissertationvomFachbereichInformatikDarmstadt2005HochschulkennzifferD17ThisthesisisaboutadvancesintheapplicationofStochasticLocalSearchmethodsforsolvinggraphcolouringproblemsandhighlyconstrainedcombinatorialoptimisationproblemsthatarisefromrealworldsystems.ZusammenfassungDas Graphenfärbeproblem besteht darin, die Knoten eines Graphen so zu färben, dasskeine zwei durch eine Kante verbundenen die gleiche Farbe erhalten. Zusam men mit Verallgemeinerungen dieser Problemstellung taucht es als Kern vieler Proble me des täglichen Lebens wie der Frequenzzuweisung in Mobilfunknetzen oder bei derErstellung eines Stundenplans für Vorlesungen an einer Universität auf. Ihre einfacheFormulierung als Graphenfärbungsprobleme erlaubt eine systematische Untersuchungdurch Reduktion auf den harten Kern dieser Probleme. All diese Probleme sind kombi natorischeOptimierungsprobleme,diedurcheineReihevonBedingungenanLösungenunddurcheinOptimierungskriteriumcharakterisiertwerden.

Sujets

Informations

Publié par
Publié le 01 janvier 2005
Nombre de lectures 73
Langue Deutsch
Poids de l'ouvrage 5 Mo

Exrait

StochasticLocalSearchMethods
forHighlyConstrained
CombinatorialOptimisationProblems
GraphColouring,Generalisations,andApplications
Dissertationsschrift
zurErlangungdesakademischenGradeseines
DoktorsderNaturwissenschaften(Dr.rer.nat.)
von
Dipl. Ing.MarcoChiarandini
ausUdine,Italien
Referent:Prof.Dr.WolfgangBibel
Korreferent:Dr.habil.ThomasStützle
TagderEinreichung:6.Mai2005
TagdermündlichenPrüfung:8.Juli2005
GenehmigteDissertationvomFachbereichInformatik
Darmstadt2005
HochschulkennzifferD17ThisthesisisaboutadvancesintheapplicationofStochasticLocalSearch
methodsforsolvinggraphcolouringproblemsandhighlyconstrained
combinatorialoptimisationproblemsthatarisefromrealworldsystems.Zusammenfassung
Das Graphenfärbeproblem besteht darin, die Knoten eines Graphen so zu färben, dass
keine zwei durch eine Kante verbundenen die gleiche Farbe erhalten. Zusam
men mit Verallgemeinerungen dieser Problemstellung taucht es als Kern vieler Proble
me des täglichen Lebens wie der Frequenzzuweisung in Mobilfunknetzen oder bei der
Erstellung eines Stundenplans für Vorlesungen an einer Universität auf. Ihre einfache
Formulierung als Graphenfärbungsprobleme erlaubt eine systematische Untersuchung
durch Reduktion auf den harten Kern dieser Probleme. All diese Probleme sind kombi
natorischeOptimierungsprobleme,diedurcheineReihevonBedingungenanLösungen
unddurcheinOptimierungskriteriumcharakterisiertwerden.
Die Lösung komplexer Graphenfärbeprobleme kann in effizienter Weise durch Me
thoden der stochastisch lokalen Suche (SLS) erfolgen. Abstrakt gesehen bestehen vie
le SLS Methoden aus mehreren Komponenten, nämlich einem Konstruktionsalgorith
mus, einem iterativen Verbesserungsalgorithmus und einer Metakomponente, genannt
Metaheuristik, die die beiden ersteren Komponenten steuert. Diese ersten beiden Kom
ponenten sind stark problemabhängig und erfordern das Ausnutzen problemspezifi
scher Kenntnisse, während die Metaheuristik allgemeiner gehalten ist. Konkrete SLS
Algorithmen enstehen durch die Kombination verschiedener konkreter Komponenten,
die wiederum jeweils weiter parametrisiert werden können. Die Konfiguration konkre
ter SLS Algorithmen als Auswahl konkreter Komponenten und deren Parametrisierung
ist eine komplexe Aufgabe, weil viele verschiedene Variationen konkreter Komponen
tenmitvielenParameternunddementsprechendvieleKombinationendenkbarsind.Die
KonfigurationsaufgabemußaufempirischenTestsberuhen,datheoretischeErkenntnisse
indiesemKontextschwerundnurgrobzuerhaltensind.DerganzeProzeßvonDesign,
Entwicklung und Konfiguration von SLS Methoden und Algorithmen kann tatsächlich
als ein Ingenieursprozess mit dem Ziel der systematischen Implementierung von SLS
Algorithmenaufgefasstwerden.
DerAusgangspunktdieserArbeitistdieDefinitionstatistischerVerfahrenfürdieAna
lysevonSLS AlgorithmenundallgemeinervonbeliebigenstochastischenOptimierungs
algorithmen. Es wird gezeigt, dass die Annahmen bei der Anwendung parametrischer
statistischer Tests oft verletzt sind, und dass deshalb oft zwei alternative Methoden,
sogenannte Permutationstests und rangbasierte Tests, verwendet werden müssen. Im
Rahmen dieser Dissertation werden Permutationstests weiterentwickelt und als weit
ere Möglichkeit zur Analyse von stochastischen Optimierungsalgorithmen eingeführt.
Darüberhinaus wird aus der parametrischen Statistik eine graphische Darstellung der
Resultate durch simultane Konfidenzintervalle übernommen und hier für nichtparame
trische Testverfahren adaptiert. Der Vorteil dieser graphischen Darstellung ist die Ver-
einigung von Informationen der beschreibenden mit denen der schließenden Statistik
in einer einzigen Graphik. Die entwickelten statistischen Methoden werden beispielhaft
zurAnalysevonSLS–AlgorithmenfürdasGraphenfärbungsproblemunddasMengen–
T Färbungsproblem,einerwichtigenVerallgemeinerungdesGraphenfärbungsproblems,
angewendet.
vVerschiedeneSLS AlgorithmensindinderLiteraturzurLösungdesGraphenfärbungs
problemsvorgeschlagenworden,abereinunvoreingenommener,systematischerVergleich
zwischen diesen wurde bisher nicht unternommen. Eine ähnliche Situation gilt für das
Mengen T Färbungsproblem. In beiden Fällen werden im Rahmen dieser Dissertation
sowohl die bekanntesten Algorithmen reimplementiert als auch neue Algorithmen ent
wickeltundanschließendmittelseinesstriktenexperimentellenDesignsverglichen.Da
durchkönnenHinweisedarauferhaltenwerden,welchesdiebestenLösungsansätzezur
LösungderzweibetrachtetenProblemesindundderbesteAlgorithmusinAb
hängigkeitvonbestimmenCharakteristikenderkonkretenInstanzenist.
In einem letzten Schritt wird untersucht, wie verschiedene allgemeine SLS Methoden
zurLösungeinerUniversitätsvorlesungsplanung(engl.coursetimetabling)angewendet
undkombiniertwerdenkönnen.DasDesignvonKomponentenfürabgeleiteteAlgorith
men beruht einerseits auf Einsichten, die für die beiden Färbungsprobleme gewonnen
wurden,undandererseitsaufAnforderungeneinesAlgorithmenwettbewerbs,indessen
Rahmen die Algorithmen entwickelt wurden. Aus diesem Grunde wird ein spezieller
FocusaufdiesystematischeEntwicklungeinesAlgorithmusgelegt.DieEntwicklungvon
Algorithmuskomponenten und die Kombination zu einem kontreten SLS–Algorithmus
wird als ein ingenieurmäßiger Prozess dargestellt, der aus der Wechselwirkung von Al
gorithmusdesignundexperimentellenTestsbesteht.DiesesVerfahrenwirdalsangemes
sen für die Anwendung von beliebigen SLS Methoden auf komplexe Probleme aus der
realenWelterachtetundbegründet.
DieHauptergebnissedieserDissertationsinddiefolgenden:
1. Beim Graphenfärbungsproblem bleibt die einfache Tabu–Suche mit einer Einer-
austauschnachbarschafteinsehrkonkurrenzfähigerAnsatz;dieAnwendungeiner
sehrgroßenNachbarschaftistnichtnutzbringend.
2. Beim Mengen–T–Färbungsproblem gibt es zwei gute Algorithmen, die auf der Ei
neraustauschnachbarschaft beruhen und jeweils auf einzelnen Instanzklassen die
bestenAlgorithmensind:einadaptiver,iterativergreedy AlgorithmusfürGraphen
undeinTabu–Suchalgorithmus,derdurcheineeingeschränkte,exakteZuweisung
vonFarbenanKnotenerweitertwurde.DiesezweiAlgorithmenkönnenauchkom
biniertwerden.
3. Der Einsatz eines ingenieurmäßigen Prozesses zur Entwicklung von Algorithmen,
deraufsequentiellemTestsberuhen,istbesondersgeeignetfürdieerfolgreicheAn
wendungvonSLS Methoden.DerEinsatzeinessolchenProzesseshatdieEntwick
lung eines Algorithmus für die Universitätsvorlesungsplanung erleichtert, der bei
eineminternationalenWettbewerbunter24eingereichtenLösungenderbestewar.
viSummary
Graphcolouringisacombinatorialoptimisationproblemconsistingincolouringthever-
tices of a graph such that no vertices connected by an edge receive the same colour. The
minimal number of colours for which such a colouring exists is an intrinsic property of
thegraphandiscalledchromaticnumber. Manyreallifesituations,suchasthefrequency
assignmentinmobilenetworksortheschedulingofcoursesatauniversity,canbemod
elled in this way. Colouring planar graphs, such as maps can be easy, and four colours
suffice, but real life systems are much more complex. When modelled by graph colour-
ing, they entail general graphs of large size and include more sophisticated constraints
thanthoserepresentablebysimpleunweightededges.
StochasticLocalSearch(SLS)methodsareapproximatetechniquesforefficientlysolv
ingcomplexcombinatorialoptimisationproblems. Theytypicallyconsistofconstruction
algorithms, iterative improvement algorithms, and meta components, better known as
metaheuristics. The first two are strongly problem dependent and require the exploita
tionofproblem specificknowledge,whilethelastaremoregeneralconceptstoguidethe
first two components. The instantiation of SLS algorithms arises from the combination
of concrete algorithmic components. The task of combining these concrete components
in an effective algorithm is complex due to their many possible combinations and the
need of determining a certain number of parameters. This task must necessarily rely on
empirical tests and the whole process of designing, developing, and configuring an SLS
algorithmisactuallyanengineeringprocess.
The starting point of this work is the definition of the statistical methods that are ap
propriate for the analysis of stochastic algorithms for optimisation. We argue that the
assumptions for the application of parametric statistical tests are often violated and opt
for two alternative methods: permutation and rank based tests. Our work contributes
to the development of permutation tests and to their introduction into the analysis of
algorithms for optimisation. Moreover, we transfer a graphical representation of results
through simultaneous confidence intervals from the parametric to the non parametric
cases. This representation has the advantage of conveying in one single graph both
descriptiveandinferentialstatistics.
ThedevelopedstatisticalmethodsservefortheanalysisofSLSalgorithmsonthegraph
colouring problem and one of its many possible generalisations, the set T colouring
problem. Several SLS algorithms have been proposed in the literature for the graph
colouring problem but no “unbiased” comparison has been attempted. A similar situ
ation holds for the set T colouring problem. In both cases, we design new algorithms,
re implement the most prominent methods, and finally compare them in a rigorous ex
perimental analysis. We gain indications on which are the best solution approaches for
these problems and which are the best algorithms in relation to some characteristics of
theinstances.
As the final step, we study SLS algorithms for solving a university course timetabling
problem. Thedesignofalgorithmcomponentsstemsfromtheknowledgegainedonthe
graph colouring problems but the assemblage and configuration of these components is
carriedoutwithasystematicmethodology. Thefocusinthiscontextwasontheselection
viiof one single algorithm to submit to an algorithm competition on the same considered
problem. The methodology is presented as an engineering process characterised by the
interaction of SLS components design and empirical tests. We deem that this method
ological approach is appropriate for the application of SLS methods to complex real life
problems.
Themainresultsarethefollowing:
1. onthegraphcolouringproblem,thesimpleTabuSearchwithone exchangeneigh
bourhood remains a very competitive approach and the use of a very large scale
neighbourhoodisnotprofitable;
2. on the setT colouring problem, the best overall algorithm is an Adaptive Iterated
GreedyalsobasedonTabuSearchwithone exchangeneighbourhoodwhich,under
certain circumstances, can be further improved by a restricted exact reassignment
ofcolours;
3. the use of an engineering methodology based on sequential testing is particularly
suitable for the application of SLS methods, as it led us to devise the algorithm
whose solutions for course timetabling ranked the best out of 24 feasible submis
sionsattheInternationalTimetablingCompetitionheldin2003.
viiiAcknowledgements
Thisworkwasfinanciallysupportedbythe“MetaheuristicsNetwork”,aResearchTrain
ingNetworkfundedbytheImprovingHumanPotentialprogrammeoftheCommission
of the European Community. I also acknowledge support by the Frankfurt Center for
Scientific Computing for providing access to their computer cluster where part of the
experimentsdescribedinthethesiswhererun.
I express deep gratitude to Dr. habil. T. Stützle for his supervision. His advice, sup
portedbytheexpertiseinanygorydetailoftheStochasticLocalSearchtechniquesguided
me from the very beginning of my research activity and his invaluable comments con
tributed toimprove considerably thiswork of mine. Iam convincedthat the impressive
availability that he always showed to everybody of our research group is a rare gift for
thosewillingtolearn. Besideshim,IexpressgratitudetoProf.Dr.W.Bibelforcomments
on drafts of this thesis and for leading an excellent and heterogeneous research group,
though,Iregretnottohavetakenthechancetolearnmoreaboutthedeductiveapproach
of Intellectics. I am also grateful to Prof. A. Schaerf who first supervised me on timeta
bling problems and local search techniques during my Master’s thesis and introduced
metotheMetaheuristicNetwork.
I am deeply indebted for patience and generosity in the transmission of knowledge
with all the colleagues with whom I shared the office in these three years and a half of
research: Luis Paquete, in particular for bringing to my attention the permutation tests
and inspiring the whole research thereafter, Tommaso Schiavinotto, for solving every
practical problem that I brought to his attention, and Dr. Marco Pranzo, for increasing
myinterestontheproblemsofOperationsResearch.
A person who definitely showed me the pleasure and the goals of doing research is
Dr. Mauro Birattari. The discussions I had with him during his stay at the Intellectics
groupatthebeginningofmyresearchcareerinfluencedandinspiredmywholeactivity
thereafter. His reasoning is present throughout all the pages of this work. I owe a lot
also to Dr. Irina Dumitrescu with whom I carried out part of the research on the graph
colouringproblem. Aboveall,Itriedtograspfromhertheprecisenessandrigourofthe
mathematicalformalism.
I am also grateful to Prof. Carlos Fonseca for providing me the code to compute the
empirical attainment function and to Dario Basso for his consultancy on all the issues
concernedwithStatisticsreportedinthiswork.
A special thank goes to the scientists who, besides Thomas, coordinated the activities
of the Metaheuristic Network: Prof. Marco Dorigo, Prof. Ben Paetcher, and Prof. Luca
M. Garmbardella, and to all young scientists, Dr. Monaldo Mastrolilli, Leonora Bianchi,
Max Manfrin, Dr. Olivia Rossi Doria, Krzysztof Socha, with whom I had the pleasure to
work.
My thanks goes also to all the other members of the Intellectics group: Dr. Matthijs
denBesten,Dr.GunterGrieser,Dr.HeshamKhalil,Dr.PeterGrigoriev,Dr.UlirchScholz,
Maria Tiedmann, Dr. Klaus Varrentrapp, and Dr. Sergey Yevtuschenko. A perfect group
thatmademystayattheIntellecticsGroupspeciallycomfortable.
On a more personal basis I wish to express my sincerest gratitude to all the people
ixmet in Darmstadt with whom I felt the rare relief of talking to a friend: Alessandro Er-
coli, Mariana Forberg, Giuseppe Galluzzo, Cinzia Pagliuca, Alice Rosini, Hamid Soley
mani,andEmanuelaTrifan. AsimilardebtIowetomyflat matesThomasRoth,Thomas
KhünerandDeniseDenterandtoDenisDusso.
Still the first as the ultimate, unfailing love and support over the years was provided
bymyfamily. Tothem,myparentsandmygrandmothergoesmywarmestthanks.
M.C.
7thJuly2005
Ahnãosereutodaagenteetodaaparte!
Odetriunfal,FernandoPessoa
x