基于聚类的多目标演化算法交配限制策略研究

发布时间：2020-06-16 19:00

【摘要】：针对不同领域中广泛存在的多目标优化问题,设计具有普适性和高性能的优化算法尤为迫切。相比于传统的优化方法,多目标演化算法不仅具有优秀的全局搜索能力、良好的并行性和鲁棒性,而且无需考虑问题的属性,单次运行即可获得多样化的折衷解,因此具有重要的应用价值与广阔的发展前景。多目标演化算法循环进行父代选择,个体重组与环境选择。学者们对环境选择算子做了大量的研究,针对个体重组时直接利用单目标优化重组算子的不足提出了基于规则模型的重组算子,但是对于交配父代选择的研究相对较少。在多目标演化算法中,基于偏好信息,从满足特定条件的个体中挑选父代,即进行交配限制,有利于算法实施恰当的重组操作,提高搜索性能。此外,聚类算法作为一类典型的无监督学习方法,可以很好地挖掘数据信息,辅助多目标演化算法发现种群分布结构。因此,本文根据聚类算法挖掘的解的分布信息,设计了多种多目标演化算法交配限制策略。本文的主要研究内容包括:演化过程中,质量较好的子种群更需要开采,而质量较差的子种群更需要勘探,对所有子种群的个体采用相同的交配限制准则存在一定不足。因此,提出了两种基于子种群质量的自适应交配限制策略。首先,针对每一子种群由同一类个体组成的情况,提出了一种基于类中新生成个体数的自适应交配限制策略和一种基于此策略的多目标演化算法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可以有效地求解无人机航迹规划问题,为决策者提供多样的航迹。
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2019
【分类号】：TP18

【参考文献】