Performance Analysis of Multi-Objective Simulated Annealing Based on Decomposition

Abstract

Simulated annealing is a metaheuristic that balances exploration and exploitation to solve global optimization problems. However, to deal with multi- and many-objective optimization problems, this balance needs to be improved due to diverse factors such as the number of objectives. To deal with this issue, this work proposes MOSA/D, a hybrid framework for multi-objective simulated annealing based on decomposition and evolutionary perturbation functions. According to the literature, the decomposition strategy allows diversity in a population while evolutionary perturbations add convergence toward the Pareto front; however, a question should be asked: What is the effect of such components when included as part of a multi-objective simulated annealing design? Hence, this work studies the performance of the MOSA/D framework considering in its implementation two widely used perturbation operators: classical genetic operators and differential evolution. The proposed algorithms are MOSA/D-CGO, based on classical genetic operators, and MOSA/D-DE, based on differential evolution operators. The main contribution of this work is the performance analysis of MOSA/D using both perturbation operators and identifying the one most suitable for the framework. The approaches were tested using DTLZ on two and three objectives and CEC2009 benchmarks on two, three, five, and ten objectives; the performance analysis considered diversity and convergence measured through the hypervolume (HV) and inverted generational distance (IGD) indicators. The results pointed out that there is a promising improvement in performance in favor of MOSA/D-DE.

Keywords

• multi-objective
• simulated annealing
• decomposition
• differential evolution