TLDR: A new paper introduces an efficient Nearest-Better Network (NBN) for visualizing and analyzing combinatorial optimization problems. It provides a theoretical basis for NBN as a maximum probability transition network and significantly speeds up its computation. Applying NBN to OneMax and Traveling Salesman Problems (TSP), the research reveals that OneMax exhibits neutrality, ruggedness, and modality, while TSP faces challenges from ruggedness, modality, and deception. The study also pinpoints limitations of state-of-the-art TSP algorithms: EAX struggles with modality (stagnation in multiple attraction basins), and LKH fails due to deceptive solutions near global optima.
Combinatorial optimization problems, which involve finding the best solution from a finite set of possibilities, are crucial in many real-world applications. A classic example is the Traveling Salesman Problem (TSP), which has wide-ranging uses from vehicle routing to DNA sequencing. Despite their importance, research into algorithms for solving these problems has faced a bottleneck, with limited significant performance improvements in recent years.
The challenge lies in understanding the complex “fitness landscapes” of these problems—a concept that describes how good a solution is and how different solutions relate to each other. Visualizing these landscapes can help researchers identify inherent difficulties in problems and pinpoint weaknesses in algorithms, paving the way for systematic improvements.
Fitness Landscape Analysis (FLA) methods aim to analyze and visualize these landscapes. Among the few visual FLA methods available for combinatorial optimization, the Nearest-Better Network (NBN) has shown promise in displaying various landscape features. However, its previous calculation was very time-consuming, and a clear theoretical understanding of its mechanisms was lacking, especially for combinatorial problems.
Advancing the Nearest-Better Network (NBN)
A recent research paper, available here, introduces significant advancements to the NBN method. The authors, Yiya Diao, Changhe Li, Sanyou Zeng, Xinye Cai, Wenjian Luo, Shengxiang Yang, and Carlos A. Coello Coello, provide a straightforward theoretical derivation, showing that NBN essentially functions as a maximum probability transition network for algorithms. This means NBN statistically models an algorithm’s behavior, simplifying the fitness landscape while preserving its crucial features that impact performance.
Crucially, the paper also presents an efficient NBN computation method. This new algorithm boasts logarithmic linear time complexity, a significant improvement over the previous quadratic time complexity, making it much faster and more practical for handling the large datasets generated by combinatorial algorithms.
New Insights into Optimization Problems and Algorithms
By applying this efficient NBN algorithm to two well-known combinatorial optimization problems—the OneMax problem and the Traveling Salesman Problem (TSP)—the researchers made several remarkable discoveries:
- OneMax Problem: For the first time, the fitness landscape of the OneMax problem was found to exhibit features like neutrality (regions where changes don’t affect fitness), ruggedness (many local peaks and valleys), and modality (multiple optimal or near-optimal solutions).
- Traveling Salesman Problem (TSP): The primary challenges for TSP problems were identified as ruggedness, modality, and deception (where algorithms are drawn to seemingly good but ultimately suboptimal solutions).
Analyzing State-of-the-Art TSP Algorithms
The study also conducted an in-depth analysis of two leading TSP algorithms: Lin-Kernighan-Helsgaun (LKH) and Edge Assembly Crossover based GA (EAX). The NBN visualization revealed their specific limitations:
- EAX: This algorithm, based on a single population, is effective at maintaining diversity. However, when multiple “attraction basins” (regions leading to different optima) exist, EAX tends to keep individuals in various basins simultaneously. This reduces the efficiency of interaction between individuals in different basins, leading to the algorithm getting stuck or stagnating. EAX struggles particularly with the “modality” challenge.
- LKH: This algorithm relies on local search operators. The analysis showed that LKH fails when deceptive solutions are present near the global optima. It tends to converge to these deceptive solutions, overlooking the true global optimum. LKH struggles with the “deception” challenge.
The NBN-assisted analysis provides a deeper understanding of why these state-of-the-art algorithms sometimes fail, even on relatively simple instances. For example, the paper explains why LKH struggles with a specific TSP instance (rue500-2) due to a deceptive funnel, while EAX struggles with another (rue500-1) due to multiple attraction basins.
Also Read:
- ECHO: A Smarter Way to Manage Complex Vehicle Fleets
- Optimizing Multiple Objectives: A New Approach with Language Models and Grid Guidance
Conclusion and Future Directions
This research not only provides a robust theoretical foundation and an efficient computational method for NBN but also offers unprecedented insights into the fitness landscapes of combinatorial optimization problems and the behaviors of algorithms designed to solve them. By revealing the underlying challenges of these problems, NBN can guide the development of new, more effective algorithms capable of adaptively learning and overcoming issues like modality and deception. This work marks a significant step towards systematically improving existing optimization algorithms.
