Local Optima Networks of NK Landscapes ...
Document type :
Compte-rendu et recension critique d'ouvrage
Title :
Local Optima Networks of NK Landscapes with Neutrality
Author(s) :
Verel, Sébastien [Auteur]
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Ochoa, Gabriela [Auteur]
Tomassini, Marco [Auteur]
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Ochoa, Gabriela [Auteur]
Tomassini, Marco [Auteur]
Journal title :
IEEE Transactions on Evolutionary Computation
Pages :
783 - 797
Publisher :
Institute of Electrical and Electronics Engineers
Publication date :
2010-11-01
ISSN :
1089-778X
HAL domain(s) :
Informatique [cs]/Intelligence artificielle [cs.AI]
English abstract : [en]
In previous work we have introduced a network-based model that abstracts many details of the underlying landscape and compresses the landscape information into a weighted, oriented graph which we call the local optima ...
Show more >In previous work we have introduced a network-based model that abstracts many details of the underlying landscape and compresses the landscape information into a weighted, oriented graph which we call the local optima network. The vertices of this graph are the local optima of the given fitness landscape, while the arcs are transition probabilities between local optima basins. Here we extend this formalism to neutral fitness landscapes, which are common in difficult combinatorial search spaces. By using two known neutral variants of the NK family (i.e. NKp and NKq) in which the amount of neutrality can be tuned by a parameter, we show that our new definitions of the optima networks and the associated basins are consistent with the previous definitions for the non-neutral case. Moreover, our empirical study and statistical analysis show that the features of neutral landscapes interpolate smoothly between landscapes with maximum neutrality and non-neutral ones. We found some unknown structural differences between the two studied families of neutral landscapes. But overall, the network features studied confirmed that neutrality, in landscapes with percolating neutral networks, may enhance heuristic search. Our current methodology requires the exhaustive enumeration of the underlying search space. Therefore, sampling techniques should be developed before this analysis can have practical implications. We argue, however, that the proposed model offers a new perspective into the problem difficulty of combinatorial optimization problems and may inspire the design of more effective search heuristics.Show less >
Show more >In previous work we have introduced a network-based model that abstracts many details of the underlying landscape and compresses the landscape information into a weighted, oriented graph which we call the local optima network. The vertices of this graph are the local optima of the given fitness landscape, while the arcs are transition probabilities between local optima basins. Here we extend this formalism to neutral fitness landscapes, which are common in difficult combinatorial search spaces. By using two known neutral variants of the NK family (i.e. NKp and NKq) in which the amount of neutrality can be tuned by a parameter, we show that our new definitions of the optima networks and the associated basins are consistent with the previous definitions for the non-neutral case. Moreover, our empirical study and statistical analysis show that the features of neutral landscapes interpolate smoothly between landscapes with maximum neutrality and non-neutral ones. We found some unknown structural differences between the two studied families of neutral landscapes. But overall, the network features studied confirmed that neutrality, in landscapes with percolating neutral networks, may enhance heuristic search. Our current methodology requires the exhaustive enumeration of the underlying search space. Therefore, sampling techniques should be developed before this analysis can have practical implications. We argue, however, that the proposed model offers a new perspective into the problem difficulty of combinatorial optimization problems and may inspire the design of more effective search heuristics.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- https://hal.archives-ouvertes.fr/hal-00488637/document
- Open access
- Access the document
- http://arxiv.org/pdf/1107.4162
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-00488637/document
- Open access
- Access the document
- document
- Open access
- Access the document
- NKneutral.pdf
- Open access
- Access the document
- 1107.4162
- Open access
- Access the document