The Study Of Selection And Reproduction In Decomposition Based Multiobjective Optimization Algorithms

Multiobjective optimization is of theoretical significance and practical value in many fields,such as science,engineering and economy.A multiobjective optimization problem(MOP)has several conflicting objectives to be optimized simultaneously.Very often,no single solution can optimize these objectives at the same time.A representative approximation of all the Pareto optimal solutions are of very practical interest to decision makers.As a population-based stochastic search technique,multiobjective optimization evolutionary algorithms(MOEAs)have become a widely used approach for MOPs,since MOEAs can provide a set of representative Pareto optimal solutions in a single run.As a major class of MOEAs,decomposition based MOEAs(MOEA/D)have attracted a lot of attention in recent years.These algorithms decompose an MOP into a number of subproblems and optimize them in a collaborative manner.Some important components of MOEA/D,including replacement,the setting of reference point and reproduction,are studied in this thesis.The main contribution of this thesis can be summarized as follows:1.Replacement is a key component in MOEA/D algorithms.Existing MOEA/D algorithms may mismatch solutions with subproblems in their replacement and then deteriorate the algorithm performance.To overcome this shortcoming,a global replacement scheme which can assign a new solution to its most suitable subproblems is proposed.The experimental studies on three sets of test problems with different characteristics show that MOEA/D with global replacement scheme is more effective than the original one.It is also shown that the replacement neighborhood size can be used for adjusting the allocation of search effort on population diversity and convergence.Moreover,the studies show that different problems need different trade-offs between diversity and convergence.2.It is well known that a small replacement neighborhood in global replacement can promote diversity,whereas a large one can encourage convergence.Different problems require different replacement neighborhood sizes.Thus,one should carefully set this size if a fixed replacement neighborhood size is used during the whole search process.To ease this burden,an adaptive global replacement is proposed.By controlling the sizes of replacement neighborhood,this adaptive replacement make an algorithm maintain a good population diversity to do more exploration at the early search stage,and improve the convergence speed at the late search stage to save the computational resource.This adaptive replacement strategy is implemented in the steady state MOEA/D and a generational MOEA/D.The experimental results show that the proposed algorithms outperform some other algorithms on a number of test problems.3.To study the setting of reference point,a generational version of MOEA/D is presented as a base algorithm.A set of continuous multiobjective optimization test instances with rug landscapes are constructed.These instances have different features compared with most existing continuous test instances.The population diversity should be carefully maintained in order to solve these test problems.Four commonly used and one newly proposed reference point setting schemes are investigated on these problems.The results show that the setting of reference point can significantly impact the performance of MOEA/D,and the ideal point is not always the best choice.The setting of reference point is worthy investigating when designing a decomposition based MOEA.Moreover,some other state-of-the-art MOEAs are also tested on these new test problems for comparison.The test results show that this set of test problems brings great challenge to these MOEAs.4.The search behavior of MOEA/D will be changed if its reference point is changed to the nadir point from the ideal point.By analyzing the major benefits of these two search behaviors,this thesis finds that these two reference point settings can complement each other.Based on the observation,a new MOEA/D version which uses both the ideal point and the nadir point as the reference points is designed.The proposed algorithm is compared with four other state-of-the-art MOEAs on a set of newly designed test instances.The comparison results showed that our proposed algorithm works well and is competitive.5.In addition,this thesis studies the use of different reproduction operators in MOEA/D in order to keep the balance between convergence and diversity.Two groups of reproduction operators are introduced and their search behaviors are analyzed.A greedy strategy is adopted in the cooperation of two operators.Moreover,a new global replacement scheme is firstly proposed to ensure diverse solutions for mating selection.A new algorithm is proposed based on this reproduction strategy and the new global replacement.The experimental results show that the proposed algorithm is promising.