Conference Proceeding

Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study

Details

Citation

Ochoa G, Veerapen N, Daolio F & Tomassini M (2017) Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study. In: Bin H & Lopez-Ibanez M (eds.) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017. Lecture Notes in Computer Science, 10197. 17th European Conference on Evolutionary Computation in Combinatorial Optimisation (EvoCOP), Amsterdam, The Netherlands, 19.04.2017-21.04.2017. Cham, Switzerland: Springer. https://doi.org/10.1007/978-3-319-55453-2_16

Abstract
Phase transitions play an important role in understanding search difficulty in combinatorial optimisation. However, previous attempts have not revealed a clear link between fitness landscape properties and the phase transition. We explore whether the global landscape structure of the number partitioning problem changes with the phase transition. Using the local optima network model, we analyse a number of instances before, during, and after the phase transition. We compute relevant network and neutrality metrics; and importantly, identify and visualise the funnel structure with an approach (monotonic sequences) inspired by theoretical chemistry. While most metrics remain oblivious to the phase transition, our results reveal that the funnel structure clearly changes. Easy instances feature a single or a small number of dominant funnels leading to global optima; hard instances have a large number of suboptimal funnels attracting the search. Our study brings new insights and tools to the study of phase transitions in combinatorial optimisation.

Keywords
phase transition; fitness landscape; local optima network; combinatorial optimisation; number partitioning problem

StatusPublished
FundersEngineering and Physical Sciences Research Council and The Leverhulme Trust
Title of seriesLecture Notes in Computer Science
Number in series10197
Publication date09/03/2017
Publication date online30/04/2017
URLhttp://hdl.handle.net/1893/24819
Related URLshttp://hdl.handle.net/…7/cfp_evocop.php
PublisherSpringer
Place of publicationCham, Switzerland
ISSN of series0302-9743
ISBN978-3-319-55452-5
eISBN978-3-319-55453-2
Conference17th European Conference on Evolutionary Computation in Combinatorial Optimisation (EvoCOP)
Conference locationAmsterdam, The Netherlands
Dates

People (1)

People

Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science

Research centres/groups