Autoren:	Herrmann, Sebastian
Titel:	Complex network analysis of fitness landscapes
Online-Publikationsdatum:	17-Nov-2016
Erscheinungsdatum:	2016
Sprache des Dokuments:	Englisch
Zusammenfassung/Abstract:	The 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. Das 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.
DDC-Sachgruppe:	330 Wirtschaft 330 Economics
Veröffentlichende Institution:	Johannes Gutenberg-Universität Mainz
Organisationseinheit:	FB 03 Rechts- und Wirtschaftswissenschaften
Veröffentlichungsort:	Mainz
ROR:	https://ror.org/023b0x485
DOI:	http://doi.org/10.25358/openscience-4559
URN:	urn:nbn:de:hebis:77-diss-1000008017
Version:	Original work
Publikationstyp:	Dissertation
Nutzungsrechte:	Urheberrechtsschutz
Informationen zu den Nutzungsrechten:	https://rightsstatements.org/vocab/InC/1.0/
Umfang:	xxix, 91 Seiten
Enthalten in den Sammlungen:	JGU-Publikationen