一种应用动态区域划分的多种群异构进化算法*

时间：2024-05-04

沈丹萍

（苏州信息职业技术学院计算机科学与技术系苏州 215200）

1 引言

当前，进化算法被大量应用在对各类复杂问题的优化分析，同时还可以使用多种群策略方法来实现子种群对解空间各区域实现进化的过程，也可以利用迁移等方式为不同子种群间构建信息传输通道，通常将这种算法称作多种群进化算法［1～7］。随着研究的不断深入，一些学者利用个体相似性、分布特征来完成进化，并选择聚类方法对种群与搜索空间实施分类。有学者在文献［8］中利用聚类算法对搜索区域实施分类获得不同等级，同时重点搜索高等级区域以实现缩小搜索空间的目的，由此显著提升收敛速率以及减小复杂度。还有学者［9］创建了一种高效的多种群遗传算法，通过新的相似性函数来判断二个点是否在相同集群内，由此实现把种群分成N个小集群的目标。文献［10］构建得到一种可以对多个子种群进行参数自适应差分处理的进化算法，并使子种群完成信息的循环共享，利用上级子种群最优个体为本种群进化提供引导作用。

文献［11］针对不同差分进化模型的具体特征来为子种群构建动态分配方法，由此实现不同策略的相互协同过程，之后对算法进行了测试发现利用该算法能够实现性能的明显优化。文献［12］通过以并行差分的进化策略对种群聚类进行优化，使子种群获得更强的通信迁移性能。文献［13］主要研究了不同策略在协同进化过程中存在的贡献度差异性，引入多种群协同的方式降低算法搜索范围，从而更快速计算出全局最优解。

通过分析以上研究结果可知，引入多种群策略可以使进化算法获得更高效的求解性能，这为利用进化算法来求解各类复杂优化问题创建了新思路［14～15］。但是，现阶段利用多种群策略来实现的进化算法还存在如下不足之处：首先，通过拓扑结构来进行区间分类时无法判断各区间重要性，也不能获得子种群差异性；其次，通过异构方法来划分区域时只能完成特定空间的处理；第三，关于如何对种群进行分类未建立统一标准，同时缺乏可靠的理论基础，无法确保划分得到的区域可以获得比原先区域存在更大概率的最优解［16～17］。根据以上分析，本文构建了一种可以实现区域动态分类的高效率多种群进化算法，可以实现在原问题中融入云模型的分析方法再对原问题进行重新估计，再划分经过估计处理得到的新问题对应的解空间，通过这种方式建立得到一套划分子种群的参考体系，并使种群搜索范围获得有效缩小，实现问题求解难度的明显减小。

2 应用动态区域划分的多种群异构进化算法

运用差分进化算法（differential evolution algorithm，DE）和遗传算法（genetic algorithm，GA）进行动态区域划分搜索，多种群异构策略见图1。

图1 多种群异构策略

应用动态区域划分的多种群异构进化算法见下式：

在分析实际优化问题时，需先构建合适的云模型再重新实施估计，按照估计得到的新问题来分类解空间，分别包括期望区域和违背区域共两类，再对划分形成的子区域运用特定搜索方法来降低搜索区域范围，减小问题的求解难度，由此实现简化问题求解过程的目标。针对以上分析结果，本文构建得到一种通过动态区域划分来实现的多种群进化算法（DD-MEA），可将其分为如下几个步骤：

第1步：对种群实施初始化，以t表示进化代数，Pt表示初始化种群。

第2步：通过问题适应值曲面对算子评估后建立云模型Ct=［Ex（t），En（t），He（t）］。

第3步：利用区域划分算子把解空间分成期望区域EAt以及违背区域BAt，由此获得代表个体｛b1，b2，…，bn｝。

第4步：统计适应值。计算y1=fg（Pt），y2=fc（Pt），通过评价算子来估计适应值，将其表示为fitness（Pt）=max（y1，y2）。

第5步：替换种群内具有低适应值的个体，得到｛b1，b2，…，bn｝。

第6步：完成各项遗传操作之后对种群实施更新。

第7步：对算子进行评价并更新评价集。

第8步：条件判断结束。如果t>tmax，整个算法完成并将结果输出，反之跳至第2步。

搜索当前最优个体也采用同样的方法。

3 实验结果分析

本文从CEC2015函数库内选择5个函数作为测试对象再对各算法进行了性能测试，对应的种群规模是200。采用上述测试函数对各算法分别以不同维度单独运行30次，同时将进化代数设定在500。综合分析了本文算法和其它算法的寻优性能，新增了5个测试函数，最后以DD-MEA算法对算法各项性能指标进行了测试。

表1 CEC2015函数库

从表2中可以看到函数测试所得的结果，f代表算法平均寻优结果，是对30次寻优处理得到的目标值进行取平均计算所得的结果；s表示平均收敛代数，是算法收敛获得全局最优解的进化代数平均值；t代表平均收敛时间，是在符合收敛条件的情况下需要达到的平均时间，其单位是s；“+”代表相同条件下采用本文算法计算得到的结果，跟其它算法存在明显区别，同时对结果进行T检验，设定显著性水平等于0.05。结果显示，本文算法达到了最优的性能指标。

表2 CEC2015函数库测试结果

通过分析表2结果可知，采用二维F1与F5函数进行优化处理后发现上述各算法都可以获得最优解。在同样的种群规模下时，DD-MEA可以获得最小的平均收敛代数并显著降低收敛时间，由此可以推断DD-MEA的寻优速率明显优于其它算法。F2函数是一种单峰的不可分离函数，随着F2函数到达30维数时，CA与DE基本不能获得全局最优解；CGA可以获得接近最优解的结果，并且需要花费很长的进化时间；DD-MEA除了可以求解出全局最优解之外，还可以实现比CGA更小的进化代数并降低寻优时间，总体性能比其余各算法更优异。F3函数是一种多模态函数，并存在一个窄峡谷，F4函数是一种包含多峰结构的非均匀函数，导致算法函数值更易产生局部最优解。运用F3与F4函数时，CA、DE以及DD-MEA处于低维条件下可以求得最优解，不过性能指标和其它各算法相比具有较大差异，当维数超过5之后，CA、DE与CGA无法计算出最优解，得到的结果已经发生了大幅波动，DD-MEA计算结果出现于最优解附近，可以计算出跟最优解相近的结果。F5函数表现出明显的非对称与旋转特征，同时存在很多的局部最优解，当CA测试的维度不断提高后，算法稳定性也会不断降低；处于低纬度条件下，DE可以获得最优解；对于DD-MEA来说，除了可以在低维条件下获得最优解以外，还可以有效缩短处理时间，并在高维求解过程中得到跟全局最优解相近的结果。F5是一个可分离与不对称的函数，处于低维数状态下时，上述各算法都可以计算出最优解。如果按照时间进行评价，CGA与DD-MEA具备CA与DE更优的性能且存在显著差异性。

根据上述结果可知，在所有维度下DD-MEA都具备更优异的性能指标，并且表现出更高的通用性以及稳定性。