An Effective Hybrid Ant Colony Optimization for the Knapsack Problem Using Multi-Directional Search

Finding a good compromise between intensification and diversification mechanisms is very challenging task when solving multi-objective optimization problems (MOPs). In this paper, we propose an Ant Colony Optimization (ACO) algorithm coupled with multi-objective local search procedure, and evolve into a multi-directional framework. The developed MD-HACO algorithm optimizes the overall quality of Pareto set approximation using different configurations of the hybrid approach by means of different directional vectors. During the construction process, Ants optimize different search directions in the objective space trying to approximate small parts of the Pareto front. Afterward, a local search phase is applied to each sub-direction to enhance the search process toward the extreme Pareto-optimal solutions with respect to the weight vector under consideration. A multi-directional set holding the non-dominated solutions according to all directional archives is maintained. MD-HACO is tested on widely used multi-objective multi-dimensional knapsack problem (MOMKP) instances and compared to well-known state-of-the-art algorithms. Experiments highlight that the use of a multi-directional paradigm as well as a hybrid schema can lead to interesting results on the MOMKP and ensure a good balance between convergence and diversity. © 2023, The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd.