Research And Application Of Combinatorial Multi-objective Optimization Based On Coevolution

In real world,optimization problems with multiple conflicting objective functions have widespread applications.Multi-objective optimization problems(MOPs)generally have a set of solutions to the tradeoff of each function.The solutions' projection in the objective domain is generally called the Paretooptimum front(PF).The multi-objective evolutionary algorithm based on decomposition(MOEA/D)divides a MOP into a number of single-objective subproblems and solves them in a collaborative way.As common methods for combinatorial optimization problems,local search can be naturally extended in the MOEA/D framework for combinatorial multi-objective optimization problems(CMOPs).This thesis aims to solve CMOPs by combining the framework of MOEA/D and coevollutionary local search.The main contributions of the thesis can be summarized as follows:1.The PF may have a long tail and a sharp peak in CMOPs,which significantly degrades the performance of MOEA/D.Aiming at the aforementioned problems,this paper designs a uniform reference points based local search with multiple populations(URPLS-MP).URPLS-MP generates a set of uniformly-distributed reference points through the normal boundary intersection(NBI)in the convex hull of individual minima(CHIM)which drives from m small evolutionary populations.A direction vector that points from the nadir point to the ideal point constructs a new population with reference points to obtain the final result.Comparative experiments show the effectiveness of URPLSMP.2.MOEA/D decomposes a MOP into a number of scalar optimization subproblems based on a predefined set of direction vectors and the ideal point.Considerable works have shown that MOEA/D only works well on some specific shapes of PF.In this paper,a dual-population paradigm is proposed which coevolves two populations with two sets of direction vectors for balancing convergence and diversity.Therefore,a coevolutionary multi-objective local search based on decomposition(CoMOLS/D)is proposed to address CMOPs.In CoMOLS/D,the goal of the first population with the predefined direction vectors aims to achieve fast convergence;while the secondary population with the dynamic direction vectors aims for the complementarily diverse solutions based on the first population.The effectiveness of the proposed algorithm is verified by comparing the experimental results of different multi-objective evolutionary algorithms(MOEAs).