Local Optima Networks: Current Results and ...
Document type :
Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes
Title :
Local Optima Networks: Current Results and Perspectives
Author(s) :
Ochoa, Gabriela [Auteur]
University of Nottingham, UK [UON]
Verel, Sébastien [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI
Daolio, Fabio [Auteur]
Université de Lausanne = University of Lausanne [UNIL]
Tomassini, Marco [Auteur]
Université de Lausanne = University of Lausanne [UNIL]
University of Nottingham, UK [UON]
Verel, Sébastien [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI
Daolio, Fabio [Auteur]
Université de Lausanne = University of Lausanne [UNIL]
Tomassini, Marco [Auteur]
Université de Lausanne = University of Lausanne [UNIL]
Conference title :
ThRaSH 2010 - 4th Workshop on Theory of Randomized Search Heuristics
City :
Paris
Country :
France
Start date of the conference :
2010-03-24
English keyword(s) :
fitness landscapes
local optima
networks
local search
evolutionary computation
local optima
networks
local search
evolutionary computation
HAL domain(s) :
Informatique [cs]/Intelligence artificielle [cs.AI]
English abstract : [en]
In a series of papers we introduced a novel model for combinatorial landscapes that we called Local Optima Networks. This is a view of landscapesderived from the previously proposed notion of ’inherent network’ of potential ...
Show more >In a series of papers we introduced a novel model for combinatorial landscapes that we called Local Optima Networks. This is a view of landscapesderived from the previously proposed notion of ’inherent network’ of potential (continuous) energy surfaces in physical-chemistry, but it has been modifiedand adapted to work for the configuration spaces generated by discrete combinatorial problems. It is based on the idea of aggregating the information given by the whole problem configuration space into a smaller mathematical object which is the graph having as vertexes the optima configurations of the probem, and as edges the possible weighted transitions between these optima. The model has proved useful for describing combinatorial landscapes (some measures on the optima networks have been found to be related with problem difficulty). However, we would like to focus now in using this model for understanding the dynamics of local search heuristics in combinatorial problems, which in turn may lead to suggestions to improve their design. This talk will summarise our main findings using the local optima network model on NK landscapes with and without neutrality, and the quadratic assignment problem (QAP). We will also present the differences between the first-improvement and best-improvement local search heuristics, when used for extracting the networks. More importantly, we would like to discuss the perspectives of this line of work for understanding the dynamics of local search. For example, the potential uses of the local optima networks for (i) exploring the trade off between exploration and exploitation; and (ii) deducing approximatebounds of the running times of local searchShow less >
Show more >In a series of papers we introduced a novel model for combinatorial landscapes that we called Local Optima Networks. This is a view of landscapesderived from the previously proposed notion of ’inherent network’ of potential (continuous) energy surfaces in physical-chemistry, but it has been modifiedand adapted to work for the configuration spaces generated by discrete combinatorial problems. It is based on the idea of aggregating the information given by the whole problem configuration space into a smaller mathematical object which is the graph having as vertexes the optima configurations of the probem, and as edges the possible weighted transitions between these optima. The model has proved useful for describing combinatorial landscapes (some measures on the optima networks have been found to be related with problem difficulty). However, we would like to focus now in using this model for understanding the dynamics of local search heuristics in combinatorial problems, which in turn may lead to suggestions to improve their design. This talk will summarise our main findings using the local optima network model on NK landscapes with and without neutrality, and the quadratic assignment problem (QAP). We will also present the differences between the first-improvement and best-improvement local search heuristics, when used for extracting the networks. More importantly, we would like to discuss the perspectives of this line of work for understanding the dynamics of local search. For example, the potential uses of the local optima networks for (i) exploring the trade off between exploration and exploitation; and (ii) deducing approximatebounds of the running times of local searchShow less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Non spécifiée
Popular science :
Non
Collections :
Source :
Files
- abstract.pdf
- Open access
- Access the document