Study Of Clustering-based Mating Restriction Strategies For Multiobjective Evolutionary Algorithms

For the multiobjective optimization problems(MOPs)widely existing in different fields,it is particularly urgent to design optimization algorithm with universality and highperformance.Compared with the traditional optimization methods,the multiobjective evolutionary algorithms(MOEAs)not only have the outstanding ability of global search,good parallelism and robustness,but also are able to obtain various tradeoff solutions in a single run without consideration of problem characteristics.Accordingly,MOEAs have important application value and broad prospects for development.MOEAs perform mating selection,reproduction and environmental selection circularly.The scholars have done a lot of research on the environmental selection operator and proposed the model based reproduction operator to make up for the deficiency of directly using the single objective optimization recombination operators during the reproduction process.However,there is little research on the mating selection.In MOEAs,selecting parents from individuals satisfying some conditions based on the preference information,or performing the mating restriction,is helpful for algorithms to perform appropriate reproduction operations and improve the search capability.Additionally,as a typical unsupervised learning method,the clustering algorithm can well excavate the data information and help MOEAs discover the population distribution structure.Therefore,this paper designs several mating restriction strategies for MOEAs according to the solution distribution information excavated by the clustering algorithm.This paper's main research contents conclude:During the evolutionary process,the sub-population with good quality needs more exploitation while the sub-population with poor quality requires more exploration.As a result,there are some deficiencies of setting the same mating restriction scheme for the individuals in all sub-populations.Accordingly,two self-adaptive mating restriction strategies based on the sub-population quality are proposed.First,for the condition that each sub-population is consisted of the individuals in the same cluster,a self-adaptive mating restriction strategy based on the number of newly generated individuals in the cluster is proposed,based on which a MOEA named as SRMMEA is proposed.SRMMEA uses the K-means algorithm every few generations to cluster the population.The individuals in the same cluster share the same mating restriction probability while different clusters have distinct mating restriction probabilities.The mating restriction probability controls the source of the mating parents.At each generation,the number of newly generated individuals after the environmental selection in each cluster is calculated to measure the cluster overall quality and then update the mating restriction probability.To further improve the search capability,when performing exploitation and exploration,the differential evolution control parameter values that are fit for local search and global search are utilized,respectively.The experimental results show the effectiveness of the mating restriction strategy.However,judging the solution quality and its preferred mating restriction probability by the cluster overall quality is relatively rough.Therefore,construct each sub-population by only one individual and a self-adaptive mating restriction strategy based on the survival length is proposed for this condition.Then,a multiobjective differential evolutionary algorithm based on survival length(MDESL)is proposed.MDESL excavates the neighborhood information by the K-means algorithm,and then sets a separate mating restriction probability for each individual to control the contributions of exploitation and exploration.At each generation,the number of generations that the individual has survived over the last period of time,or the survival length,is used to measure the individual quality and update the individual's mating restriction probability.Besides,to save the computational cost,MDESL measures the difference degree between populations to judge the necessity of performing clustering in the next generation.MDESL is validated to be better than the comparison algorithms by the contrast experiments.The decomposition based MOEAs divide the multiple objective optimization problem into a series of subproblems.During the evolutionary process,the solved degree of different subproblems are distinct,so different subproblems have distinct requirements for exploitation and exploration.Moreover,the survival length proposed in MDESL is more appropriate for the decomposition based MOEAs to measure the solution quality and then judge the solved degree of the subproblem.Additionally,the neighbor solutions defined by the distance between the weight vectors may distribute far away in the decision space,which will affect the exploitation ability.Based on the above considerations,a self-adaptive mating restriction strategy based on the solved degree of the subproblem and a MOEA named as MOEA/D-OMR are proposed.MOEA/D-OMR uses the online agglomerative clustering method to excavate the neighborhood information of the population in the decision space,and accurately finds the neighbors of the individual.According to each subproblem's mating restriction probability,the mating pool is constructed by the neighbors or the whole population.MOEA/D-OMR updates the mating restriction probability by the survival length of the subproblem's solution at each generation.Because the maximum number of clusters influences the neighborhood size and then influences the search capability,MOEA/D-OMR updates the maximum number of clusters by the mean mating restriction probability every few generations.The experimental results indicate that MOEA/D-OMR has a good search capability.In the model-based MOEAs,if using the previously proposed mating restriction strategies and setting the whole population as the mating pool with some probability,the model thus built is not accurate.The performance of the algorithm will be weakened.Besides,the algorithm's requirement for the search regions varies with the evolutionary process.To solve these problems,a model based self-adaptive mating restriction strategy and a MOEA named as MMEA-sC are proposed.MMEA-sC uses the FCM algorithm to divide the population into multiple clusters.At each generation,the number of survival generations is used to select the solution with the worse quality to be evolved.During the reproduction,a separate Gaussian model is set for the current solution.To enlarge the search region,the model mean is the solution itself.To strengthen the exploitation ability,MMEA-sC multiplies the cluster covariance by a small coefficient to obtain the self-adaptive covariance and then sets the model covariance to be the cluster covariance or the self-adaptive covariance according to the mating restriction probability.Because the algorithm prefers different degree of exploitation during the evolutionary process,four coefficients used to calculate the self-adaptive covariance are predefined.Each coefficient's selected probability is determined by the history performance of the coefficient.The contrast experimental results indicate that MMEA-sC has a better search performance.Unmanned aerial vehicle(UAV)path planning problem is a typical multiobjective optimization problem.Using MOEAs to solve this kind of problem is more pragmatic.Therefore,a UAV path planning model in two flying scenarios is built.Then MOEAs that are proposed previously are used to solve the path planning problem.The experimental results show the effectiveness and deficiencies of the algorithms.Existing MOEAs for solving the path planning problem set the same mating restriction scheme for all waypoints.However,different waypoints have distinct quality and require different search regions.Besides,even though the clustering method is carried out on the paths,neighbor paths' waypoints may distribute far away.To solve the above issues,based on the mating restriction strategies given previously,a series of metric functions are proposed to measure the waypoint quality.A MOEA with the mating restriction strategy based on the metric functions and the clustering method(MFKC)is also proposed.MFKC utilizes the K-means algorithm to build the neighborhood relationship of the waypoint,rather than the path.Then,each waypoint's mating restriction probability controls the parents to be selected from the neighbor waypoints for exploitation or the global waypoints for exploration.The mating restriction probability is determined by the waypoint quality measured by the metric functions.A local search operator for further optimization on the flight height is also proposed.The experimental results show that MFKC can effectively solve the UAV path planning problem and provide various paths to the decision makers.