How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes
How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes
复制标题
扰动强度如何塑造 TSP 适应度景观的全局结构
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
G. Ochoa
中科院分区：
文献类型：
--
作者：
P. McMenemy;Nadarajen Veerapen;G. Ochoa
本地最佳网络是一种有价值的工具，用于分析和可视化组合搜索空间的全局结构；在一组随机生成的（均匀和聚类）实例上搜索TSP。我们的定量分析表明，几个漏斗指标与链式LK成功率的相关性比本地Optima的数量更强，这表明全球结构清楚地影响了搜索性能。
Local optima networks are a valuable tool used to analyse and visualise the global structure of combinatorial search spaces; in particular, the existence and distribution of multiple funnels in the landscape. We extract and analyse the networks induced by Chained-LK, a powerful iterated local search for the TSP, on a large set of randomly generated (Uniform and Clustered) instances. Results indicate that increasing the perturbation strength employed by Chained-LK modifies the landscape’s global structure, with the effect being markedly different for the two classes of instances. Our quantitative analysis shows that several funnel metrics have stronger correlations with Chained-LK success rate than the number of local optima, indicating that global structure clearly impacts search performance.