Research On Multiobjective Combinatorial Optimization Algorithm Based On Decomposition

Multiobjective combinatorial optimization problem is a large number of problems in the real word,it is of great pratical significance to design efficient algorithms to solve it.This paper studies the application and research on the multiobjective combinatorial optimization algorithm based on decomposition,it is divided into the following two parts:Firstly,the existing basic algorithm for solving multiobjective combinatorial optimization problems,Pareto Local Search(PLS),which has a high time and space complexity during the running time,it is easy to get into local optimality and has a poor expansibility.For these problems,in this paper,a Reference Line Guided Pareto Local Search(RLG-PLS)is proposed,RLG-PLS uses decomposition based framework,a set of predefined reference lines to guided the search direction and maintain the diversity of the population.Two populations are evolving in RLG-PLS,the external population maintains the nondominated solutions that are closest to the reference lines;and a starting population strores all the starting solutions for PLS.When there is no newly added solutions can be found in external population,new reference lines are inserted to guide the PLS and try to help the current solutions jump out of the local optimum.Secondly,by using decomposition based multiobjective evolutionary algorithm(MOEA/D),a local search method can be easily applied to a multiobjective combinatorial optimization problems.However,the commonly used decomposition methods of MOEA/D,such as Weighted Sum(WS),Tchebycheff(TCH)and Penalty-based Boundary Intersetction(PBI),may cause local search method suffer from the lack of starting solutions,due to the loss of diversity.This paper proposed a Multiobjective Memetic algorithm based on Dynamic Constrained Decomposition(DCDG-MOMA),which based on the framework of Constrained Decompostion with grid(CDG).Compared with other decomposition based algorithms,DCDG-MOMA can obtain more solutions for local search during the running process.DCDG-MOMA is compared with other excellent algorithms on two sets of benchmark multiobjective combinatorial optimization problems and device assignment problem for the avionic system.The experimental results show that DCDG-MOMA outperforms the compared algorithms.