A simulated annealing for multi-criteria optimization problem: DBMOSA

• To determine the acceptance probability, a multi-objectives evaluation measure is proposed.
• Based on the proposed evaluation measure, an offspring reproducing procedure is given.
• An equivalent relaxation approach is proposed to handle the constraints of multi-criteria optimization problems.
• Two performance metrics are proposed to assess the performance of the multi-criteria optimization evolutionary algorithms.

This paper investigates a simulated annealing (SA) for multi-criteria optimization problem (MOP) which incorporates the concept of archive in order to provide a set of tradeoff solutions for the problem under consideration. To determine the acceptance probability of a new solution, an evaluation measure of multi-criteria objective function is proposed which takes into account the dominant relation between the new and current solutions, as well as those in the archive. In addition, a mutation operator is proposed in which the constraints of MOP can be partially handled. To efficiently apply the proposed SA into constrained MOP (CMOP), an equivalent relaxation approach is proposed by which the CMOP, say primal problem, can be equivalently transformed into an unconstrained MOP, say relaxation problem. Based on such a constraints handling technique (CHT), it is theoretically proved that the primal problem and the relaxation problem have the same efficient set (ES) and the proposed CHT is then further extended into two existing multi-criteria optimization (MO) evolutionary algorithms (EA) (MOEA), say AMOSA and NSGA-II, respectively. Two performance metrics are proposed to evaluate the performance of the MOEAs. Finally, a comprehensive comparative study among AMOSA, NSGA-II and the proposed SA is performed on some popular benchmarks for MOP algorithms to show the effectiveness of the proposed SA and CHT. The comparative study shows that the overall performance of the proposed SA is generally superior to both of the AMOSA and NSGA-II, particularly, for the MOPs with three objectives the performance of the former is far better than the latter, and the proposed CHT can be very conveniently extended into any of the existing EAs for MOP such that they can be applied to solve the CMOPs.