【作者】 李欣；

【导师】 宋申民；

【作者基本信息】 哈尔滨工业大学 ， 控制科学与工程， 2019， 博士

【摘要】 针对不同领域中广泛存在的多目标优化问题,设计具有普适性和高性能的优化算法尤为迫切。相比于传统的优化方法,多目标演化算法不仅具有优秀的全局搜索能力、良好的并行性和鲁棒性,而且无需考虑问题的属性,单次运行即可获得多样化的折衷解,因此具有重要的应用价值与广阔的发展前景。多目标演化算法循环进行父代选择,个体重组与环境选择。学者们对环境选择算子做了大量的研究,针对个体重组时直接利用单目标优化重组算子的不足提出了基于规则模型的重组算子,但是对于交配父代选择的研究相对较少。在多目标演化算法中,基于偏好信息,从满足特定条件的个体中挑选父代,即进行交配限制,有利于算法实施恰当的重组操作,提高搜索性能。此外,聚类算法作为一类典型的无监督学习方法,可以很好地挖掘数据信息,辅助多目标演化算法发现种群分布结构。因此,本文根据聚类算法挖掘的解的分布信息,设计了多种多目标演化算法交配限制策略。本文的主要研究内容包括:演化过程中,质量较好的子种群更需要开采,而质量较差的子种群更需要勘探,对所有子种群的个体采用相同的交配限制准则存在一定不足。因此,提出了两种基于子种群质量的自适应交配限制策略。首先,针对每一子种群由同一类个体组成的情况,提出了一种基于类中新生成个体数的自适应交配限制策略和一种基于此策略的多目标演化算法SRMMEA。SRMMEA每隔几代利用K-means算法将种群聚类。同一类中的个体采用相同的交配限制概率,不同类个体采用不同的交配限制概率。由交配限制概率控制交配父代的来源。在每一代根据环境选择以后类中新产生的个体数目判断类的整体质量,进而更新类的交配限制概率。为了进一步提高算法性能,在开采与勘探时,分别采用适合于局部搜索与全局搜索的差分进化算子控制参数值。实验结果说明了交配限制策略的有效性。然而,通过类的质量推测个体的质量和需要的交配限制概率较为粗糙,因此令每一子种群仅由单一个体组成,并针对此情况设计了一种基于存活长度的自适应交配限制策略MRSL,进而提出了一种多目标差分进化算法MDESL。MDESL基于K-means算法提取邻域信息,然后为每个个体设置一个单独的交配限制概率,控制其进行开采与勘探的比例。在每一代根据个体在过去一段时间内的存活代数,即存活长度,判断个体质量,更新个体的交配限制概率。此外,MDESL根据种群差异度判断在下一代中进行聚类的必要性,从而适当地减少计算开销。通过对比实验,表明MDESL优于对比算法。基于分解的多目标演化算法将多目标优化问题分解为一系列子问题。在演化过程中,不同子问题被求解的程度不同,因此不同子问题对开采和勘探的需求是不同的。而MDESL中提出的生存长度的概念更适用于基于分解的多目标演化算法判断解的质量,进而判断子问题的求解程度。此外,根据权向量间距离定义的邻居解在决策空间中可能具有很远的分布距离,不利于开采。针对以上考虑,提出了一种基于子问题求解程度的自适应交配限制策略和一种多目标演化算法MOEA/D-OMR。MOEA/D-OMR利用在线凝聚聚类算法提取种群在决策空间中的邻域信息,准确地找到个体的邻居。然后根据每个子问题的交配限制概率,控制配对池由邻居个体还是整个种群组成。MOEA/D-OMR在每一代根据子问题的解的生存长度,自适应地更新交配限制概率。鉴于最大聚类数影响邻域大小,进而影响算法的搜索能力,MOEA/D-OMR每隔几代利用综合交配限制概率更新最大聚类数。实验结果表明MOEA/D-OMR具有很好的求解能力。在基于模型的多目标演化算法中,如果按照本课题已提出的交配限制策略,以一定概率将整个种群做为配对池,将会建立不准确的模型,不利于算法搜索。而且,随着演化的进行,算法对搜索范围的需求是不断变化的。针对此问题,提出了一种基于模型的自适应交配限制策略和一种多目标演化算法MMEA-sC。MMEA-sC利用FCM算法将种群划分为多个类。在每一代根据解的存活代数选择质量较差的个体进行演化。重组时,为当前演化个体建立单独的高斯模型。为了扩大搜索范围,模型均值即为演化个体本身。为了加强开采,将一个小于1的正系数与类协方差相乘,获得自适应协方差,然后用交配限制概率控制模型协方差为类协方差或者自适应协方差。鉴于算法在演化过程中对开采能力有不同的需求,预先定义了4个计算自适应协方差的系数,并根据系数的历史表现确定不同系数的被选概率。对比实验结果表明,MMEA-sC搜索性能更优。无人机航迹规划问题是一类典型的多目标优化问题,利用多目标演化算法求解此类问题更为实用,因此建立了两种场景下的无人机航迹规划问题模型,并利用之前提出的多目标演化算法进行求解。实验结果说明了算法的有效性以及不足。考虑到现有的求解航迹规划问题的多目标演化算法对所有路径点使用相同的交配限制准则,然而,不同路径点有不同质量,需要不同的搜索范围。而且,尽管对航迹进行了聚类,邻居航迹的某些路径点可能分布很远。为了解决上述问题,在之前给出的交配限制策略的基础上,提出了一系列评估函数测度路径点的质量,进而提出了一种基于评估函数与聚类交配限制策略的多目标演化算法MFKC。MFKC利用K-means算法为每个路径点,而非航迹,建立邻域关系。由每个路径点的交配限制概率控制交配父代来源于邻居路径点还是全局路径点,以分别加强开采和勘探。交配限制概率由评估函数测度的路径点质量决定。还提出了一种局部搜索算子进一步优化飞行高度。实验结果表明MFKC可以有效地求解无人机航迹规划问题,为决策者提供多样的航迹。更多还原

【Abstract】 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.更多还原