Multi-objectivization Inspired Metaheuristics for the Sum-of-the-Parts Combinatorial Optimization Problems
This work addresses optimization bottlenecks in combinatorial problems like TSP and UBQP, offering incremental improvements for researchers and practitioners in operations research and AI.
The paper tackled the challenge of escaping local optima in sum-of-the-parts combinatorial optimization problems like the traveling salesman problem by decomposing the objective into correlated sub-objectives, resulting in new metaheuristics (ILS+NDS, ITS+NDS, ILK+NDE) that significantly outperformed existing methods on most test instances.
Multi-objectivization is a term used to describe strategies developed for optimizing single-objective problems by multi-objective algorithms. This paper focuses on multi-objectivizing the sum-of-the-parts combinatorial optimization problems, which include the traveling salesman problem, the unconstrained binary quadratic programming and other well-known combinatorial optimization problem. For a sum-of-the-parts combinatorial optimization problem, we propose to decompose its original objective into two sub-objectives with controllable correlation. Based on the decomposition method, two new multi-objectivization inspired single-objective optimization techniques called non-dominance search and non-dominance exploitation are developed, respectively. Non-dominance search is combined with two metaheuristics, namely iterated local search and iterated tabu search, while non-dominance exploitation is embedded within the iterated Lin-Kernighan metaheuristic. The resultant metaheuristics are called ILS+NDS, ITS+NDS and ILK+NDE, respectively. Empirical studies on some TSP and UBQP instances show that with appropriate correlation between the sub-objectives, there are more chances to escape from local optima when new starting solution is selected from the non-dominated solutions defined by the decomposed sub-objectives. Experimental results also show that ILS+NDS, ITS+NDS and ILK+NDE all significantly outperform their counterparts on most of the test instances.