Generating Easy and Hard Problems using the Proximate Optimality Principle
Generating Easy and Hard Problems using the Proximate Optimality Principle
复制标题
DOI：
10.1145/2739482.2764890
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
J. Mccall;Lee A. Christie;A. Brownlee
中科院分区：
文献类型：
--
作者：
J. Mccall;Lee A. Christie;A. Brownlee
我们提出了一种基于众所周知的近似最佳原理（POP）的方法来产生可变难度问题的方法，通常以“类似的解决方案具有相似的适应性”来解释。我们根据目标空间和表示空间中的指标来探讨此概念的定义，并根据这些指标的连贯性来定义POP。我们假设，当其在表示空间中探索的邻里与适应性在客观空间上引起的自然度量相一致时，算法将表现良好。我们开发了一种明确的问题产生方法，该方法会引起位弦问题，其中自然健身指标与锤子社区相干或反协调。我们进行实验，以表明连贯的问题很容易，而使用锤子社区的当地攀岩者很难进行抗增密问题。
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.