A New Parallel Cooperative Landscape Smoothing Algorithm and Its Applications on TSP and UBQP

Combinatorial optimization problem (COP) is di ffi cult to solve because of the massive number of local optimal solutions in his solution space. V arious methods have been put forward to smooth the solution space of COPs, including homotopic convex (HC) transformation for the traveling salesman problem (TSP). This paper extends the HC transformation approach to unconstrained binary quadratic programming (UBQP) by proposing a method to construct a unimodal toy UBQP of any size. We theoretically prove the unimodality of the constructed toy UBQP . After that, we apply this unimodal toy UBQP to smooth the original UBQP by using the HC transformation framework and empirically verify the smoothing e ff ects. Subsequently, we introduce an iterative algorithmic framework incorporating HC transformation, referred as landscape smoothing iterated local search (LSILS). Our experimental analyses, conducted on various UBQP instances show the e ffectiveness of LSILS. Furthermore, this paper proposes a parallel cooperative variant of LSILS, denoted as PC-LSILS and apply it to both the UBQP and the TSP . Our experimental findings highlight that PC-LSILS improves the smoothing performance of the HC transformation, and further improves the overall performance of the algorithm. Introduction COPs are a class of problems mainly to find an optimal combination to maximize or minimize some performance metrics with limited resources or subject to some constraints. COPs are typically categorized as NP-hard, for which classical optimization methods struggle to find the optimal solution within a reasonable amount of time and become less applicable. Consequently, researchers usually use heuristics or metaheuristics to find near-optimal solutions within a reasonable amount of time. One of the key challenges associated with solving COPs is the presence of numerous local optima in the solution space, primarily attributable to the rugged and irregular nature of their fitness landscapes. It can be hypothesized that smoothing the landscapes of COPs could significantly facilitate the attainment of the global optima.