Abstract
Combinatorial optimization problems often suffer from the "local optimum trap," where search algorithms become stuck in sub-optimal solutions. This paper presents a novel framework for "multi-objectivization" through Random Objective Decomposition. By splitting a single "sum-of-the-parts" objective into two correlated sub-objectives, the authors introduce two techniques: Non-dominance Search (NDS) and Non-dominance Exploitation (NDE). These methods allow metaheuristics to navigate local optima more effectively by identifying promising "non-dominated" neighbors in a multi-objective space. Experimental results on Traveling Salesman Problem (TSP) and Unconstrained Binary Quadratic Programming (UBQP) benchmarks demonstrate that this approach significantly improves search efficiency and solution quality compared to traditional single-objective metaheuristics.
Introduction
In the field of combinatorial optimization, the primary challenge is navigating complex fitness landscapes to find a global optimum. Standard metaheuristics, such as Iterated Local Search (ILS), typically employ a "perturbation" or "kick" to escape local optima—valleys in the landscape where no immediate neighbor offers a better solution. However, these perturbations are often random and uninformed, leading to inefficient searches that may fail to find the global minimum in high-dimensional spaces.
This research addresses the need for a more "informed" escape mechanism. The authors propose leveraging the principles of multi-objective optimization to solve single-objective problems. Specifically, they target "sum-of-the-parts" problems, where the total cost is the sum of individual components, such as edge weights in a graph or bit-pair costs in a binary problem.
Methodology: Random Objective Decomposition
The core of the proposed framework is Random Objective Decomposition. This process transforms a single-objective problem into a multi-objective one to provide better guidance for the search algorithm.
1. Decomposition Strategy
The original objective function $f(x)$ is decomposed into two sub-objectives, $f_1(x)$ and $f_2(x)$, such that: $$f(x) = f_1(x) + f_2(x)$$ This is achieved by randomly splitting the cost of every individual unit (e.g., every edge in a TSP graph) into two parts based on a specific probability distribution.
2. Correlation Control
The authors found that the relationship between $f_1$ and $f_2$ is critical. By adjusting the shape of the probability distribution (e.g., moving from a "bell-shaped" to a "valley-shaped" distribution), they can control the Pearson correlation ($\rho$) between the two new objectives. This correlation acts as a tuning knob for the search's exploratory behavior.
3. Search Enhancements
The paper introduces two primary algorithmic enhancements:
- Non-dominance Search (NDS): Tailored for algorithms with fixed neighborhood structures. When a local optimum is reached, NDS identifies neighbors that are "non-dominated" in the $(f_1, f_2)$ space. These neighbors are hypothesized to be the most promising "gateways" to better regions of the search space.
- Non-dominance Exploitation (NDE): Designed for algorithms with varying neighborhood structures, such as the Lin-Kernighan heuristic. It identifies local optima that are non-dominated relative to the current best solution and targets those regions for intensive exploitation.
These techniques were integrated into three enhanced metaheuristics: ILS+NDS, ITS+NDS (Iterated Tabu Search), and ILK+NDE (Iterated Lin-Kernighan).
Experimental Evaluation
The effectiveness of the decomposition framework was tested on two classic benchmark sets:
- TSPLIB: A standard library for the Traveling Salesman Problem, featuring instances ranging from 51 to over 18,000 cities.
- OR-Library: Used for Unconstrained Binary Quadratic Programming (UBQP) instances, with variables ranging from 1,000 to 5,000.
Key Results
The experimental data revealed several significant findings:
- Performance Gains: The NDS and NDE-enhanced versions consistently outperformed their standard counterparts across nearly all test instances.
- Convergence: In specific TSP instances like
rat99andrd100, the enhanced algorithms found the global optimum reliably, whereas standard ILS frequently stalled at higher cost values. - Search Efficiency: The authors quantified the "expected number of function evaluations" required to find an improvement. NDS was shown to reduce this metric by orders of magnitude compared to exhaustive neighborhood searches.
Discussion and Insights
The Neighborhood Non-dominance Hypothesis
A central insight of this work is that solutions which are non-dominated in the decomposed sub-objective space are statistically more likely to lead to global improvements. By viewing the problem through a multi-objective lens, the algorithm can identify lateral moves that are invisible to a single-objective search.
The "Goldilocks" Correlation
The search performance is highly sensitive to the correlation ($\rho$) between sub-objectives. If $\rho = 1$, the sub-objectives are identical to the original, and no new information is gained. If the correlation is negative, the search becomes too chaotic. A moderate positive correlation provides the "Goldilocks" zone—enough diversity to escape traps without losing the signal of the original objective.
Conclusion and Future Work
Random Objective Decomposition provides a powerful new tool for combinatorial optimization. By creating a "plateau" in the fitness landscape where there used to be a sharp peak, it allows algorithms to move laterally to find hidden paths toward the global optimum.
While the method introduces some computational overhead due to the calculation of non-dominance, the resulting search is significantly more intelligent. Future research will focus on applying this logic to non-linear objective functions where costs are not easily separable, as well as testing the framework on other complex problems like the Quadratic Assignment Problem (QAP) and the Vehicle Routing Problem (VRP).
Summary updated