Conference Paper (published)

Deconstructing the Big Valley Search Space Hypothesis

Details

Citation

Ochoa G & Veerapen N (2016) Deconstructing the Big Valley Search Space Hypothesis. In: Chicano F, Hu B & García-Sánchez P (eds.) Evolutionary Computation in Combinatorial Optimization: 16th European Conference, EvoCOP 2016, Porto, Portugal, March 30 -- April 1, 2016, Proceedings. Lecture Notes in Computer Science, 9595. 16th European Conference on Evolutionary Computation in Combinatorial Optimisation, EvoCOP 2016, Porto, Portugal, 30.03.2016-01.04.2016. Cham, Switzerland: Springer International Publishing, pp. 58-73. http://link.springer.com/chapter/10.1007%2F978-3-319-30698-8_5; https://doi.org/10.1007/978-3-319-30698-8_5

Abstract
The big valley hypothesis suggests that, in combinatorial optimisation, local optima of good quality are clustered and surround the global optimum. We show here that the idea of a single valley does not always hold. Instead the big valley seems to de-construct into several valleys, also called ‘funnels’ in theoretical chemistry. We use the local optima networks model and propose an effective procedure for extracting the network data. We conduct a detailed study on four selected TSP instances of moderate size and observe that the big valley decomposes into a number of sub-valleys of different sizes and fitness distributions. Sometimes the global optimum is located in the largest valley, which suggests an easy to search landscape, but this is not generally the case. The global optimum might be located in a small valley, which offers a clear and visual explanation of the increased search difficulty in these cases. Our study opens up new possibilities for analysing and visualising combinatorial landscapes as complex networks.

Keywords
Fitness Landscapes; Local Optima Networks; Funnels; Traveling Salesman Problem

StatusPublished
FundersEngineering and Physical Sciences Research Council
Title of seriesLecture Notes in Computer Science
Number in series9595
Publication date15/03/2016
URLhttp://hdl.handle.net/1893/22993
Related URLshttp://hdl.handle.net/…6/cfp_evocop.php
PublisherSpringer International Publishing
Publisher URLhttp://link.springer.com/…-3-319-30698-8_5
Place of publicationCham, Switzerland
ISSN of series0302-9743
ISBN978-3-319-30697-1
Conference16th European Conference on Evolutionary Computation in Combinatorial Optimisation, EvoCOP 2016
Conference locationPorto, Portugal
Dates

People (1)

Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science

Files (1)

Research centres/groups