Clustering-based Reproduction Operators For Multiobjective Evolutionary Algorithms

In engineering, there exist plenty of complicated multiobjective optimization problems(MOPs) with properties of multiple constraints, multiple variables and high nonlinearity. Since the traditional deterministic optimization techniques cannot deal with these problems well, the evolutionary algorithm(EA), which is a type of stochastic search algorithm inspired by natural evolution, has become a popular approach for solving them through approximating their Pareto sets. Since MOEA is able to obtain an approximation of Pareto set for a MOP through a single run, therefore, the MOEAs have been booming in recent years.A MOEA has two important operators, i.e., individual reproduction operator and environmental selection operator. The role of reproduction operator is generating new individuals, and the environmental selection operator is with the purpose of preserving promising individuals into next generation. At present, lots of research works focus on the environmental selection operators, and the individual reproduction operators are not given so much concentration, most of the MOEAs directly utilize the reproduction operators designed for the single objective evolutionary algorithms(SOEAs). As a matter of fact, the Pareto set of a continuous m-objective optimization problem is a(m- 1)-dimensional piecewise continuous manifold. Therefore, in the reproduction of a MOEA,if the regularity property is utilized to guide search, the MOEA should have a much higher search efficiency. In recent years, the rapid developments of both EA and machine learning techniques promote the scholars to consider their mutual promotion more actively. Since the EA is a type of data-based science, thus this thesis proposes to apply a type of representative machine learning technique, i.e., clustering algorithm(CA), into the MOEAs to discover the structures of Pareto sets of MOPs, and then utilizes the structure information to design specific reproduction operators and to guide search of the MOEAs.The works in this thesis are summarized as follows.The traditional reproduction operators for SOEAs directly take the whole populations as the mating pools to select parents for generating new solutions. At the later evolutionary stages of MOEAs, the produced new solutions are easy to deviate from the manifolds of Pareto sets of MOPs. To deal with this problem, an adaptive mating restriction strategy called AMRS is designed, and meanwhile an affinity propagation(AP) based MOEA named as APMO is proposed. AMRS applies an AP clustering algorithm to discover the distribution structures of the populations; based on the structures, with a mating restriction probability the neighboring individuals or the individuals with big differences among each other are applied to build mating pools for reproductions. To adapt the variation of the balance between exploration and exploitation during evolution, at each generation, the mating restriction probability is updated according to the reproduction utility of the two types of mating pools over the last certain generations. Comparison experiments denote that APMO has excellent solving performance. Experimental analysis indicates that the design of AMRS is scientific and appropriate, and AMRS has good adaptability.Results of path planning of cruise missile show that AMRS is able to improve the performance of MOEAs on solving complicated MOPs in engineering, and that conducting path planning of cruise missile based on MOEAs is appropriate and necessary.In the Gaussian sampling based reproduction operators of MOEAs, there usually exist some drawbacks, such as the properties of the MOPs to be solved are not adequately considered, the modeling complexity is high, the outliers are not properly addressed, and the diversity of the produced new solutions are not enough. To deal with these drawbacks, a clustering based mixture Gaussian sampling strategy named as CASS is developed.Through combing CASS and a differential evolution(DE) operator, an adaptive incremental MOEA called AMEA is presented. At each generation, AMEA firstly takes a K-means clustering algorithm to discover the population structure; based on the structure, the DE operator chooses the solutions with big differences among each other as the parents to generate new solutions, the CASS operator makes the solutions within the same cluster to share a same covariance matrix to build a Gaussian model for each solution for approximating the population structure and producing new solutions. To adapt the variation of the balance between exploration and exploitation during evolution, based on the utility that the two operators generate new solutions over the last certain generations, a strength Pareto approach is designed to adaptively control the contributions of the two operators.To decrease the number of clustering operations, a reuse scheme is also introduced in AMEA to let the later populations reuse the structure information of the earlier similar populations. Experimental analysis denotes that AMEA has excellent performance on the benchmark instances with various properties and on the practical path planning problem of cruise missile, the designed CASS sampling strategy, scheme of hybrid and adaptive control of solution generation operators, and reusing scheme of population structure are all appropriate and effective.In the evolution of APMO and AMEA, a number of entire clustering processes consisted of multiple iterations are required. To further reduce the computational cost brought by clustering operations, through fusing the iterations of CAs and the evolutions of MOEAs, an idea of designing reproduction operators based on the fusion of clustering and evolution is proposed. Preliminary experiments of using a K-means clustering algorithm for fusion prove that the proposed idea is feasible and effective. After that, through applying a self-organizing map(SOM) algorithm for fusion, a self-organizing MOEA named as SMEA is developed. In SMEA, the evolution of MOEA and the training of SOM are conducted alternately. At each generation, only the newly preserved promising solutions are taken to train the SOM model, and each solution is visited only once. Then the structure discovered until that moment is employed to guide the individuals to select their parents from the neighborhoods or the whole population for producing new solutions. Since during the evolution of SMEA, only one clustering process consisted of multiple iterations is required, so that the computational cost introduced by clustering operations can be reduced greatly. Experimental analysis presents that with a small computational cost of clustering, SMEA achieves a good solving performance on benchmark problems with various properties and on practical path planning problem of cruise missile.At present, in the data mining based MOEAs, the data mining approaches to be used usually require the data for learning meeting the independent identical distributed assumption. Since the data generated from the MOEAs are non-stationary, these data actually do not meet the independent identical distributed assumption. In order to adequately consider the property of the data produced from MOEAs, a reproduction operator based on online agglomerative clustering Add C is developed, and an incremental MOEA called OCEA is proposed. Add C is an approach designed for learning from non-stationary data.In OCEA, the evolution of the MOEA and the iterations of Add C are integrated together.Whenever a new solution is preserved, the algorithm proceeds an online clustering operation and updates the discovered structure of Pareto set. Based on the discovered structure information, with a certain probability, the neighborhoods or the solutions with big differences among each other are employed to generate new solutions, so that the balance between exploration and exploitation can be maintained. Since OCEA only visits the preserved promising solutions once for clustering, it needs small computational cost. Experimental analysis shows that OCEA not only has outstanding solving performance but also excellent clustering ability, the online clustering based reproduction operator has good adaptability for different environmental selection operators. The result of path planning of cruise missile denotes that OCEA also does well in tackling this type of complicated MOPs in engineering.