Conference Proceeding

Generating Easy and Hard Problems using the Proximate Optimality Principle

Details

Citation

McCall J, Christie LA & Brownlee A (2015) Generating Easy and Hard Problems using the Proximate Optimality Principle. In: Silva S (ed.) Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. 2015 Annual Conference on Genetic and Evolutionary Computation, Madrid, Spain, 11.07.2015-15.07.2015. New York: ACM, pp. 767-768. http://dl.acm.org/citation.cfm?id=2764890; https://doi.org/10.1145/2739482.2764890

Abstract
We present an approach to generating problems of variable difficulty based on the well-known Proximate Optimality Principle (POP), often paraphrased as "similar solutions have similar fitness". We explore definitions of this concept in terms of metrics in objective space and in representation space and define POP in terms of coherence of these metrics. We hypothesise that algorithms will perform well when the neighbourhoods they explore in representation space are coherent with the natural metric induced by fitness on objective space. We develop an explicit method of problem generation which creates bit string problems where the natural fitness metric is coherent or anti-coherent with Hamming neighbourhoods. We conduct experiments to show that coherent problems are easy whereas anti-coherent problems are hard for local hill climbers using the Hamming neighbourhoods.

Keywords
Problem Generation; Proximate Optimality; Estimation of Distribution Algorithms; Landscapes

StatusPublished
Publication date31/12/2015
Publication date online31/07/2015
Related URLshttps://openair.rgu.ac.uk/….org/gecco-2015/
PublisherACM
Publisher URLhttp://dl.acm.org/citation.cfm?id=2764890
Place of publicationNew York
ISBN978-1-4503-3488-4
Conference2015 Annual Conference on Genetic and Evolutionary Computation
Conference locationMadrid, Spain
Dates

People (1)

People

Dr Sandy Brownlee

Dr Sandy Brownlee

Senior Lecturer in Computing Science, Computing Science and Mathematics - Division