Fitness landscapes and graphs: multimodularity, ...
Type de document :
Communication dans un congrès avec actes
Titre :
Fitness landscapes and graphs: multimodularity, ruggedness and neutrality
Auteur(s) :
Verel, Sébastien [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI
Ochoa, Gabriela [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI
Ochoa, Gabriela [Auteur]
Titre de la manifestation scientifique :
IEEE WORLD CONGRESS ON COMPUTATIONAL INTELLIGENCE WCCI 2010
Ville :
Barcelona
Pays :
Espagne
Date de début de la manifestation scientifique :
2010-07-18
Titre de l’ouvrage :
IEEE WORLD CONGRESS ON COMPUTATIONAL INTELLIGENCE WCCI 2010
Éditeur :
IEEE
Date de publication :
2010-07-18
Mot(s)-clé(s) en anglais :
evolutionary computation
fitness landscapes
fitness landscapes
Discipline(s) HAL :
Informatique [cs]/Intelligence artificielle [cs.AI]
Résumé en anglais : [en]
One of the most commonly-used metaphors to describe the process of heuristic search methods in solving combinatorial optimisation problems is that of a fitness landscape. The landscape metaphor appears most commonly in ...
Lire la suite >One of the most commonly-used metaphors to describe the process of heuristic search methods in solving combinatorial optimisation 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 analysing 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 methaurhistics 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 analysed. Finally, the tutorial will conclude with a brief survey of open questions and recent research directions on fitness landscapes.Lire moins >
Lire la suite >One of the most commonly-used metaphors to describe the process of heuristic search methods in solving combinatorial optimisation 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 analysing 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 methaurhistics 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 analysed. Finally, the tutorial will conclude with a brief survey of open questions and recent research directions on fitness landscapes.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- tutorialCEC2010.pdf
- Accès libre
- Accéder au document