Title :

Fitness landscapes and graphs: multimodularity, ruggedness and neutrality

Author(s) :

Verel, Sébastien [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI

Conference title :

Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference companion

City :

Philadelphia

Country :

Etats-Unis d'Amérique

Start date of the conference :

2012-07-07

Publisher :

ACM

Publication date :

2012

English keyword(s) :

fitness landscape
graph
multimodal
network
neutrality

HAL domain(s) :

Informatique [cs]/Intelligence artificielle [cs.AI]

English abstract : [en]

One of the most commonly-used metaphors to describe the process of heuristic search methods in solving combinatorial optimization problems is that of a fitness landscape. The landscape metaphor appears most commonly in ...
Show more >One of the most commonly-used metaphors to describe the process of heuristic search methods in solving combinatorial optimization problems is that of a fitness landscape. The landscape metaphor appears most commonly in work related to evolutionary algorithms, however, it can be used for search in general; the search space can be regarded as a spatial structure where each point (solution) has a height (objective function value) forming a landscape surface. In this scenario, the search process would be an adaptive-walk over a landscape that can range from having many peaks of high fitness flanked by cliffs falling to profound valleys of low fitness, to being smooth, with low hills and gentle valleys. Combinatorial landscapes can be seen as a graph whose vertices are the possible configurations. If two configurations can be transformed into each other by a suitable operator move, then we can trace an edge between them. The resulting graph, with an indication of the fitness at each vertex, is a representation of the given problem fitness landscape. The study of the fitness landscape consists in analyzing this graph or a relevant partition of it, with respect to the search dynamics or problem difficulty. This advanced tutorial will give an overview of the origins of the fitness landscape metaphor, and will cover the alternative ways to define fitness landscapes in evolutionary computation. The two main geometries: multimodal and neutral landscapes, which correspond to two different graph partitions found in combinatorial optimization, will be considered, as well as the dynamics of metaheurhistics searching on them. Furthermore, the relationship between problem hardness and fitness landscape metrics (i.e. autocorrelation, fitness distance correlation, neutral degree, etc), and the local optima network properties, studied in recent work, will be deeply analyzed. Finally, the tutorial will conclude with a brief survey of open questions and recent research directions on fitness landscapes.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL