.png){kind=icon}
.png){kind=icon}
Return
Nearest-Better Network for Visualizing and Analyzing Combinatorial Optimization Problems: A Potential Unified Tool
.png){kind=icon}
PRE
AI
DOI：10.1109/TEVC.2025.3597078.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 problem is challenging but very important for analyzing the algorithm’s behavior. This article provides a straightforward theoretical derivation showing that the NBN network essentially functions as the maximum probability transition network for algorithms. This article 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. Three state-of-the-art TSP algorithms [EAX, Lin–Kernighan-Helsgaun (LKH), and neuroLKH (NLKH)] 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 interbasin interaction efficiency and leading to algorithm’s stagnation. NLKH improves over LKH by leveraging learned edge weights to increase the chance of reaching the global basin, but it remains vulnerable to deceptive funnels due to biased learning from underrepresented complex instances.
Keywords:
combinatorial optimization problem (COP)
fitness landscape analysis (FLA)
nearest better network (NBN)
traveling salesman problem (TSP)
Journal
IF:
12
Papers:
1.8K
Citations:
2.4W
View more organizations