Nearest-Better Network for Visualizing and Analyzing Combinatorial Optimization Problems: A Potential Unified Tool
本文提出了一种高效计算最近更好网络的方法，将其应用于OneMax和旅行商问题，揭示了适应度景观的中性、崎岖和多峰特征，并分析了三种先进TSP算法的局限性。
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. Three state-of-the-art TSP algorithms (EAX, LKH, and 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 inter-basin 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.