So it suffices to prove (24) and (25). Firstly, the conclusion holds whenk "1.

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.

Solving the Traveling Salesperson Problem (TSP) remains a persistent challenge, despite its fundamental role in numerous generalized applications in modern contexts. Heuristic solvers address the demand for finding high-quality solutions efficiently. Among these solvers, the Lin-Kernighan-Helsgaun (LKH) heuristic stands out, as it complements the performance of genetic algorithms across a diverse range of problem instances. However, frequent timeouts on challenging instances hinder the practical applicability of the solver. Within this work, we investigate a previously overlooked factor contributing to many timeouts: The use of a fixed candidate set based on a tree structure. Our investigations reveal that candidate sets based on Hamiltonian circuits contain more optimal edges. We thus propose to integrate this promising initialization strategy, in the form of POPMUSIC, within an efficient restart version of LKH. As confirmed by our experimental studies, this refined TSP heuristic is much more efficient - causing fewer timeouts and improving the performance (in terms of penalized average runtime) by an order of magnitude - and thereby challenges the state of the art in TSP solving.

Given a set of cities with certain locations, the Traveling Salesman Problem (TSP) is to find the shortest Hamiltonian route, along which a salesman travels from a city to visit all the cities exactly once and finally returns to the starting city. The TSP is one of the most famous and well-studied NP-hard combinatorial optimization problems, which is very easy to understand but very difficult to solve optimally or near-optimally. Over the years, TSP has become a touchstone for the algorithm design. Typical methods for solving the TSP are mainly exact algorithms, approximation algorithms and heuristics. The exact algorithms may be prohibitive for large instances and the approximation algorithms may suffer from weak optimal guarantees or empirical performance (Khalil et al. 2017). Heuristics are known to be the most efficient and effective approaches for solving the TSP.

The Traveling Salesperson Problem (TSP) is a classical N P-hard optimization problem of utmost relevance, e.g., in transportation logistics, bioinformatics or circuit board fabrication. The goal is to route a salesperson through a set of cities such that each city is visited exactly once and the tour is of minimal length. In the past decades tremendous progress has been made in the development of high-performing heuristic TSP solvers. The local search-based Lin-Kernigham Heuristic (LKH) [14] and the genetic algorithm Edge-Assembly-Crossover (EAX) [35], along with their respective restart versions introduced in Kotthoff et al. [25], undeniably pose the state-of-the-art in inexact TSP solving. Automated Algorithm Selection (AS), originally proposed by Rice [39] back in 1976, is a powerful framework to predict the best-performing solver(s) from a portfolio of candidate solvers by means of machine learning. It has been successfully applied to a wide spectrum of challenging optimization problems in both the combinatorial [24, 29, 30, 40, 48] and continuous domain [21, 4] with partly astonishing performance gains - see the recent survey by Kerschke et al. [19] for a comprehensive overview. In particular, the TSP was subject to several successful ASstudies [25, 20, 33, 34, 37] which exploited the complementary performance profiles of simple heuristics on the one hand and the state-of-the-art solvers LKH and EAX on classical TSP benchmark sets on the other hand.