Skip to main content

Research Repository

Advanced Search

Generating easy and hard problems using the proximate optimality principle.

McCall, John A.W.; Christie, Lee A.; Brownlee, Alexander E.I.

Authors

John A.W. McCall

Alexander E.I. Brownlee



Contributors

Sara Silva
Editor

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.

Citation

MCCALL, J.A.W., CHRISTIE, L.A. and BROWNLEE, A.E.I. 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 (GECCO Companion '15), 11-15 July 2015, Madrid, Spain. New York: ACM [online], pages 767-768. Available from: https://doi.org/10.1145/2739482.2764890

Conference Name 2015 annual conference on genetic and evolutionary computation (GECCO '15)
Conference Location Madrid, Spain
Start Date Jul 11, 2015
End Date Jul 15, 2015
Acceptance Date Mar 20, 2015
Online Publication Date Jul 11, 2015
Publication Date Jul 31, 2015
Deposit Date Mar 3, 2016
Publicly Available Date Mar 3, 2016
Publisher Association for Computing Machinery
Pages 767-768
DOI https://doi.org/10.1145/2739482.2764890
Keywords Problem generation; Proximate optimality; Estimation of distribution algorithms; Landscapes
Public URL http://hdl.handle.net/10059/1406
Related Public URLs http://hdl.handle.net/10059/1384 ; http://hdl.handle.net/10059/1407 ; http://hdl.handle.net/10059/1567 ; http://hdl.handle.net/10059/1585

Files





You might also like



Downloadable Citations