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

Sujets

• Informatik
• Mathematics

Informations

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

Extrait

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