Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-4559
Full metadata record
DC FieldValueLanguage
dc.contributor.authorHerrmann, Sebastian
dc.date.accessioned2016-11-17T12:20:22Z
dc.date.available2016-11-17T13:20:22Z
dc.date.issued2016
dc.identifier.urihttps://openscience.ub.uni-mainz.de/handle/20.500.12030/4561-
dc.description.abstractThe concept of fitness landscapes originated from evolutionary biology and is relevant for numerous disciplines. In metaheuristics for combinatorial optimization, fitness landscapes are frequently used to study the structure of problems. A novel approach is to analyze fitness landscapes by local optima networks'' (LONs). A LON compresses the features of fitness landscapes in a complex network. The nodes are the local optima. The edges model the potential transitions between the local optima basins. Edges are directed and weighted by transition probabilities. Studies towards a deeper insight and exploitation of LONs are rare. The contribution of this thesis is to demonstrate how local optima networks can be used to study the structure and the search difficulty of combinatorial optimization problems for metaheuristics. For our experiments, we mainly used the Kauffman NK model of fitness landscapes. The thesis consists of four papers. In the first and second paper, we show that the PageRank centrality of the global optimum in LONs is a reliable predictor of search difficulty (R^2 > 90%) for local search based metaheuristics. This is possible because PageRank is a variant of Eigenvector centrality. A LON approximates the stochastic process of an algorithm in the fitness landscape. The LON graph's matrix of edge weights is equivalent to the transition matrix of a finite-state Markov chain. The Eigenvector of the transition matrix reflects the stationary distribution of a random walk across the Markov chain. Hence, the scalar value of the global optimum approximates the probability to visit this node during search.In the third paper, we applied the Markov cluster algorithm for community detection to LONs. This reveals a structure of multiple clusters and supplements the big valley hypothesis, which states that good solutions are often contained in a single, giant cluster. The existence of multiple clusters is related to search difficulty: the size of the cluster containing the global optimum is strongly correlated to the success rate of iterated local search. This offers an explanation for failures of this metaheuristic: the perturbation operator is too weak to escape from one cluster to another. Fourth, a method is introduced to represent a landscape by a coarse-grained barrier tree. Barrier trees (disconnectivity graphs) have so far been used to study the barriers which an algorithm needs to pass in order to escape from one basin to another. We present a method based on the flooding algorithm to reveal the barriers that exist between clusters of local optima. The method is useful to obtain a coarse-grained picture of a fitness landscape. Experimental results indicate that the existence of barriers between clusters is related to search difficulty for iterated local search.en_GB
dc.description.abstractDas Konzept der Fitness Landscapes stammt aus dem Bereich der Evolutionsbiologie und ist für eine Vielzahl von Disziplinen relevant. Im Bereich Metaheuristiken für kombinatorische Optimierung werden Fitness Landscapes verwendet, um die Struktur von Optimierungsproblemen zu untersuchen. Ein neuer Ansatz zur Untersuchung von Fitness Landscapes sind Local Optima Networks (LONs). Ein LON ist eine komprimierte Netzwerk-Repräsentation einer Fitness Landscape. Die Knoten sind die lokalen Optima, die Kanten modellieren potentielle Übergänge zwischen den Bassins der lokalen Optima. Die Kanten sind gerichtet und mit Übergangswahrscheinlichkeiten gewichtet. Bisher gibt es bzgl. LONs nur wenige Studien. Im Rahmen dieser Dissertation wird gezeigt, wie Local Optima Networks zur Untersuchung der Struktur von kombinatorischen Optimierungsproblemen sowie zur Beurteilung ihrer Schwierigkeit für Metaheuristiken genutzt werden können. Hierzu werden die experimentellen Ergebnisse aus vier empirischen Rechenstudien vorgestellt, in denen unter anderem die PageRank-Zentralität lokaler Optima sowie die Community-Struktur lokaler Optima untersucht wurde.de_DE
dc.language.isoeng
dc.rightsInCopyrightde_DE
dc.rights.urihttps://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc330 Wirtschaftde_DE
dc.subject.ddc330 Economicsen_GB
dc.titleComplex network analysis of fitness landscapesen_GB
dc.typeDissertationde_DE
dc.identifier.urnurn:nbn:de:hebis:77-diss-1000008017
dc.identifier.doihttp://doi.org/10.25358/openscience-4559-
jgu.type.dinitypedoctoralThesis
jgu.type.versionOriginal worken_GB
jgu.type.resourceText
jgu.description.extentxxix, 91 Seiten
jgu.organisation.departmentFB 03 Rechts- und Wirtschaftswissenschaften-
jgu.organisation.year2017
jgu.organisation.number2300-
jgu.organisation.nameJohannes Gutenberg-Universität Mainz-
jgu.rights.accessrightsopenAccess-
jgu.organisation.placeMainz-
jgu.subject.ddccode330
opus.date.accessioned2016-11-17T12:20:22Z
opus.date.modified2017-01-05T12:44:50Z
opus.date.available2016-11-17T13:20:22
opus.subject.dfgcode00-000
opus.organisation.stringFB 03: Rechts- und Wirtschaftswissenschaften: Abteilung Wirtschaftswissenschaftende_DE
opus.identifier.opusid100000801
opus.institute.number0302
opus.metadataonlyfalse
opus.type.contenttypeDissertationde_DE
opus.type.contenttypeDissertationen_GB
jgu.organisation.rorhttps://ror.org/023b0x485
Appears in collections:JGU-Publikationen

Files in This Item:
  File Description SizeFormat
Thumbnail
100000801.pdf8.8 MBAdobe PDFView/Open