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

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

• understanding_phase_transitions_LON_NPP.pdf