Nearest-Better Network for Visualizing and Analyzing Combinatorial Optimization Problems: A Potential Unified Tool

doi:10.1109/TEVC.2025.3597078

Nearest-Better Network for Visualizing and Analyzing Combinatorial Optimization Problems: A Potential Unified Tool

2025-08-08

0

PRE

AI

杨圣祥 (Shengxiang Yang)

C

Carlos A. Coello Coello

DOI：10.1109/TEVC.2025.3597078

原文链接

原文求助

摘要

En 中文

最近更好的网络（NBN）是可视化连续优化问题采样数据并保留多种景观特征的一种强大方法。然而，NBN的计算非常耗时，且该方法扩展至组合优化问题既具挑战性又对分析算法行为至关重要。本文提供了一种直接的推导理论，表明NBN网络本质上作为算法的最大概率转移网络发挥作用。本文还提出了一种具有对数线性时间复杂度的高效NBN计算方法，以解决耗时问题。通过将该高效NBN算法应用于OneMax问题和旅行商问题（TSP），我们首次发现了以下几点：OneMax的适应度景观表现出中性、粗糙和多模态特征。TSP问题的主要挑战是粗糙、多模态和欺骗性。三种最先进的TSP算法[EAX、Lin–Kernighan-Helsgaun（LKH）和neuroLKH（NLKH）]在分别应对与多模态和欺骗性相关的挑战时存在局限性。基于局部搜索算子的LKH在全局最优解附近存在欺骗性解时会失效。基于单一种群的EAX能够高效维持多样性。然而，当存在多个吸引盆时，EAX会同时保留多个盆内的个体，降低了盆地间交互效率并导致算法停滞。NLKH通过利用学习到的边权重提高了达到全局盆地的机会，但因其从代表性不足的复杂实例中存在偏差学习，仍易受欺骗性漏斗的影响。

Keyword:

combinatorial optimization problem (COP)

fitness landscape analysis (FLA)

nearest better network (NBN)

traveling salesman problem (TSP)

Nearest-Better Network for Visualizing and Analyzing Combinatorial Optimization Problems: A Potential Unified Tool

摘要

期刊

机构

引用论文