提出高效NBN方法,首次揭示组合优化问题的复杂景观特征。
Nearest-Better Network for Visualizing and Analyzing Combinatorial Optimization Problems: A Unified Tool
- 基于概率转移重构网络,实现对组合优化景观的高效可视化
- 发现OneMax具中性、崎岖与多模态特征,TSP主要挑战为崎岖与欺骗性
- 揭示主流算法EAX和LKH在多吸引子与欺骗解上的局限性
最近更优网络(Nearest-Better Network, NBN)是一种强大的连续优化问题数据可视化方法,能保留多种景观特征。然而,其计算耗时严重,且拓展至组合优化问题极具挑战性,对分析算法行为至关重要。本文通过直接理论推导表明,NBN本质上是算法的最大概率转移网络。为此,提出一种时间复杂度为对数线性级别的高效计算方法,显著提升效率。将该方法应用于OneMax问题与旅行商问题(TSP),首次发现:OneMax的适应度景观具有中性、崎岖性和多模态特征;TSP的主要挑战为崎岖性、多模态性及欺骗性。两种先进TSP算法(EAX与LKH)分别存在局限:基于局部搜索的LKH在全局最优附近存在欺骗解时失效;而基于单种群的EAX虽能保持多样性,但当存在多个吸引盆地时,会同时滞留个体于多个盆地,降低跨盆地交互效率,导致算法停滞。
原文摘要 · Abstract (English)
The Nearest-Better Network (NBN) is a powerful method to visualize sampled data for continuous optimization problems while preserving multiple landscape features. However, the calculation of NBN is very time-consuming, and the extension of the method to combinatorial optimization problems is challenging but very important for analyzing the algorithm's behavior. This paper provides a straightforward theoretical derivation showing that the NBN network essentially functions as the maximum probability transition network for algorithms. This paper also presents an efficient NBN computation method with logarithmic linear time complexity to address the time-consuming issue. By applying this efficient NBN algorithm to the OneMax problem and the Traveling Salesman Problem (TSP), we have made several remarkable discoveries for the first time: The fitness landscape of OneMax exhibits neutrality, ruggedness, and modality features. The primary challenges of TSP problems are ruggedness, modality, and deception. Two state-of-the-art TSP algorithms (i.e., EAX and LKH) have limitations when addressing challenges related to modality and deception, respectively. LKH, based on local search operators, fails when there are deceptive solutions near global optima. EAX, which is based on a single population, can efficiently maintain diversity. However, when multiple attraction basins exist, EAX retains individuals within multiple basins simultaneously, reducing inter-basin interaction efficiency and leading to algorithm's stagnation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。