The case for strategic oscillation
The case for strategic oscillation
复制标题
DOI：
10.1007/s10479-009-0597-1
复制
发表时间：
2011-03
影响因子：
4.8
通讯作者：
F. Glover;Jin-Kao Hao
中科院分区：
文献类型：
--
作者：
F. Glover;Jin-Kao Hao
我们研究元启发式搜索的“硬”优化问题，其中自然邻域（由翻转零一变量值的移动组成）面临两个局部最优，这两个局部最优值由可行空间中的最大可能移动数分开。一旦下降方法达到第一个局部最优值，所有达到第二个局部最优值（即全局最优值）的可行移动序列最终都必须通过逐渐变差的解决方案，直到达到与全局最优值相邻的最差解决方案。我们展示了某些替代邻域如何更容易地定位全局，但揭示了这些方法中的每一种都通过稍微改变问题的表述而遇到严重的困难。我们还确定了其他可能的方法，这些方法乍一看很有希望，但结果却存在缺陷。最后，我们观察到，在可行和不可行空间之间转换的战略振荡方法克服了这些困难，强化了最近发表的关于在可行性和不可行之间交替的解决方案轨迹的效用的观察。我们还概述了这种方法的特征，这些特征对未来的研究有影响。
We study a “hard” optimization problem for metaheuristic search, where a natural neighborhood (that consists of moves for flipping the values of zero-one variables) confronts two local optima, separated by a maximum possible number of moves in the feasible space. Once a descent method reaches the first local optimum, all sequences of feasible moves to reach the second, which is the global optimum, must ultimately pass through solutions that are progressively worse until reaching the worst solution of all, which is adjacent to the global optimum.We show how certain alternative neighborhoods can locate the global more readily, but disclose that each of these approaches encounters serious difficulties by slightly changing the problem formulation. We also identify other possible approaches that seem at first to be promising but turn out to have deficiencies.Finally, we observe that a strategic oscillation approach for transitioning between feasible and infeasible space overcomes these difficulties, reinforcing recent published observations about the utility of solution trajectories that alternate between feasibility and infeasibility. We also sketch features of such an approach that have implications for future research.