Gao Wanru, Nallaperuma Samadhi, Neumann Frank
School of Information Engineering, Zhengzhou University, Zhengzhou, Henan, China
University of Cambridge, Cambridge, UK
Evol Comput. 2021 Spring;29(1):107-128. doi: 10.1162/evco_a_00274. Epub 2020 Jun 17.
Understanding the behaviour of heuristic search methods is a challenge. This even holds for simple local search methods such as 2-OPT for the Travelling Salesperson Problem (TSP). In this article, we present a general framework that is able to construct a diverse set of instances which are hard or easy for a given search heuristic. Such a diverse set is obtained by using an evolutionary algorithm for constructing hard or easy instances which are diverse with respect to different features of the underlying problem. Examining the constructed instance sets, we show that many combinations of two or three features give a good classification of the TSP instances in terms of whether they are hard to be solved by 2-OPT.
理解启发式搜索方法的行为是一项挑战。对于诸如旅行商问题（TSP）的2-OPT等简单局部搜索方法而言亦是如此。在本文中，我们提出了一个通用框架，该框架能够构建出对于给定搜索启发式算法而言有难有易的各种实例。通过使用进化算法来构建关于基础问题不同特征具有多样性的难或易实例，从而获得这样一个多样集。通过检查构建出的实例集，我们表明，就2-OPT求解难度而言，两到三个特征的许多组合能对TSP实例进行良好分类。
