混沌映射与动态学习的自适应樽海鞘群算法

卓 然，王未卿

(1.浙江特殊教育职业学院 基础教学部，浙江 杭州 310023；2.北京科技大学 东凌经济管理学院，北京 100083)

0 引 言

樽海鞘群算法SSA是一种全新智能优化算法[1]，其思想源于樽海鞘的聚集行为。该生物通过吸收海水的推动力移动，并以链式结构顺次跟随。樽海鞘可划分为两个群组：领导者和追随者。链首为领导者，在搜索食物源中具备最优判断，主导种群移动。其它称为追随者，追随者相互跟随，相互领导。每次迭代中，樽海鞘按适应性排序，个体相互跟随，而非所有个体只向当前最优个体移动，降低了搜索过程陷入局部最优的概率，其寻优精度和收敛性能优于传统粒子群算法、遗传算法、蚁群算法、灰狼优化算法。此外，SSA的控制参数相对更少，大大减少了算法对控制参数的依赖。同时，其模型更为简单，已广泛应用于光伏系统功率控制[2]、无源时差定位[3]、网络学习[4]、频谱分配[5]、工程优化[6]和图像分割[7]等领域。然而，传统SSA依然存在寻优精度不高、易于陷入局部最优的不足，主要体现在：①随机种群初始化无法确保初始种群在空间中的均匀分布；②执行全局搜索的领导者只受目标位置引导，虽然收敛较快，但搜索不充分，遍历性不足。而执行局部开发的追随者会在领导者已知最优区域内做精细搜索，但跨度不足，在领导者无法获得全局最优时无法跳出局部区域，开辟新空间，寻优精度受到影响；③传统SSA中领导者和追随者规模的固定划分模式无法实现局部开发和全局勘探、搜索速度与遍历、精度及扰动的均衡，使得搜索过程无法稳定获取目标精度和收敛速度。

1 相关工作

针对SSA的不足，文献[8]引入混沌映射到SSA中，以混沌序列替代位置更新的随机变量，融合动态特性提升算法搜索能力。文献[9]则将单纯形法引入SSA中，在确定种群多样性的同时，可以有效提高个体的局部开发能力。文献[10]在领导者和追随者更新阶段分别引入衰减因子和动态学习机制对SSA进行改进，有效增强了局部开发和全局搜索能力。文献[11]在食物源和追随者的位置更新方式中分别引入疯狂算子和自适应惯性权重，在提升种群多样性的同时，使SSA具有更优更均衡的局部开发和全局搜索能力，寻优精度和收敛速度均有所增强。文献[12]调整了领导者和追随者位置更新中的随机参数，使领导者个体能够更好的趋向最优解，提升SSA的寻优精度。文献[13]将粒子群算法与SSA进行融合，利用粒子寻优的灵活性和多样性提升算法的全局寻优能力。文献[14]则将模拟退火的思路引入SSA中，在多目标优化问题上进一步提升的算法的寻优效率。

以上对于樽海鞘群算法的改进虽然可以在某一方面作出优化，但在局部开发和全局勘探的均衡、收敛速度、如何避免陷入局部最优及提升寻优精度等综合性能方面仍然具有许多不足。尤其，在实际问题优化中，求解的问题往往是高维度单峰、高维度多峰式的复杂优化问题，解决这类优化问题，樽海鞘群算法SSA的寻优精度和求解效率需要进一步全面提升。为了进一步提高SSA的寻优精度和收敛速度，尽可能避免局部收敛与个体早熟，以更加均衡的方式协调樽海鞘个体的局部开发和全局勘探过程，本文主要改进工作体现如下：

(1)设计了基于改进混沌Tent映射机制的种群初始化方法，使个体尽可能均匀分布于搜索空间内；

(2)设计了基于Logistic映射的领导者更新机制，有效增强种群多样性；

(3)设计了基于动态学习机制的追随者更新机制，使算法跳出局部最优，扩大搜索范围，提升全局搜索能力；

(4)设计了领导者/追随者种群规模的自适应调整机制，有效均衡个体的局部开发和全局勘探能力。

2 樽海鞘群算法SSA

SSA算法中，个体位置矢量X用于在n维空间中搜索，n相当于决策变量数量。樽海鞘种群由N个维度为n的个体构成。因此，樽海鞘种群由以下矩阵构成

(1)

对于SSA，追踪食物源是所有樽海鞘个体的目标。因此，领导者位置更新方式为

(2)

其中，x1,j表示领导者的j维位置，Fj表示食物源的j维位置，ubj和lbj分别为搜索维度j的上限和下限，c2、c3为[0,1]间的随机数，决定j维更新位置的移动方向(正向或反向)及移动步长。c1为收敛因子，用于均衡方法迭代过程中樽海鞘个体的局部开发和全局勘探能力。式(2)表明，领导者的位置更新主要由食物源的位置决定。收敛因子c1定义为

c1=2e-(4t/Tmax)2

(3)

其中，t为当前迭代，Tmax为最大迭代。

追随者位置的更新方式为

(4)

其中，i≥2，xi,j表示追随者的j维位置，Δt表示时间，v0表示追随者的初始速率，加速度a=(vfinal-v0)/Δt， 其中，vfinal=(xi-1,j-xi,j)/Δt，xi-1,j表示第i-1个樽海鞘在j维的位置。由于时间是迭代次数之差，故Δt=1。而每次迭代开始时，追随者初始速度v0=0，故追随者位置更新可表示为

xi,j=xi,j+xi-1,j/2

(5)

式(5)表明：追随者i的j维位置更新等于上一迭代中该樽海鞘对应的位置与追随者i-1的j维位置之和的一半。

3 改进樽海鞘群算法CDSSA

3.1 基于改进Tent映射的种群初始化

初始种群直接影响群体智能算法的收敛速度和寻优精度。传统的SSA的种群初始化主要以随机方式生成。而随机化初始化种群无法确保种群在搜索空间中的均匀分布。混沌序列呈现规律性、随机性和遍历性等特点。比较完全随机化，融合混沌序列的樽海鞘群初始种群具有更好的多样性。混沌序列的主要思想是通过在区间[0,1]间的映射关系产生混沌序列，并将其转换至种群的搜索空间中。混沌序列的生成方式有多种，以Tent映射生成序列均匀性更好。但Tent映射生成的混沌序列存在小周期和不确定周期点的不足。综合考虑以上问题，结合完全随机化特点，将传统Tent混沌映射中添加随机变量r/N，得到Tent映射为

(6)

式中：i表示种群规模，i=1,2,…,N，j表示混沌序号，j=1,2,…,d，r表示[0,1]间的随机数，μ表示混沌参数，μ∈[0,2]，μ值越大，混沌性能越优，式(6)即为一种混沌系统。对式(6)取相应初始值后，即可得到d个混沌序列di,j。 然后对混沌序列进行逆映射，即可生成种群个体的位置变量xi,j， 表示为

xi,j=lbj+yi,j×(ubj-lbj)

(7)

式中： [lbj,ubj] 表示个体位置xi,j的搜索范围。

3.2 基于Logistic映射的领导者更新

SSA中，领导者以食物源为目标进行全局搜索。然而，以食物源为牵引的领导者更新可以加速算法收敛，但其全局勘探不够充分，遍历性不足，且受初始种群影响较大，易于陷入局部最优。由式(2)可知，领导者更新主要受收敛因子c1和缩放因子c2的影响，c1随迭代数变化，而c2是均匀分布的随机量，决定算法全局勘探范围。然而，完全随机搜索存在盲目性，会导致全局勘探阶段中的领导者位置准确性较低。本文引入混沌Losgitic映射提升领导者搜索的有效性，在每一次迭代中生成伪随机分布状态值，扩展SSA搜索过程的随机性以及遍历性，实现比完全均匀分布更为合理的搜索过程。

如前文所述，混沌是一种非线性的动态随机非重复决策系统，表征对初始条件的敏感性，是一种无限非稳定的周期运动。由于混沌的可遍历性及非重复性，它可以更有效实现比随机搜索(由随机值c2决定)更为广泛的搜索过程。将混沌系统融入SSA的领导者位置更新中可以增强算法的搜索能力，更好预防陷入局部最优解。算法利用Logistic 混沌映射生成混沌序列，形式化为

Ch(t+1)=β×Ch(t)×(1-Ch(t))

(8)

其中，Ch即为生成的[0,1]间的混沌值，迭代初始时的混沌初值Ch0在每次独立运行过程中随机生成，但不可取值为0、0.25、0.5、0.75和1，这是由Logistic混沌映射的非周期性决定的。β取值为4，在迭代趋向无穷时，用于控制混沌值的行为。对于可变的β取值的Logistic映射行为如图1所示。对于较小的β取值，即β<3，混沌值Ch始终收敛在单一量上。当β=3时，混沌值Ch开始在两个取值间振荡，这一特征行为改变称为分歧点。对于β>3时，Ch进一步出现分歧，并导致最终的混沌行为。

图1 Logistic映射

基于Logistic映射的领导者位置更新方式如下

(9)

3.3 基于动态学习的追随者更新

SSA中，追随者完成局部开发过程。由式(5)可知，SSA的追随者位置更新不受任意随机参数的影响，完全取决于樽海鞘个体的前次迭代位置和紧邻的前一个体位置的影响，与领导者位置不发生直接作用。这种首尾相连机制可以使算法进行充分的局部开发过程。若领导者未陷入局部最优，可以寻得全局最优，追随者顺势可以在最优解区域进一步做精细搜索，可以避免全局最优区域内的小范围局部最优解，寻优精度更极致。然而，当领导者陷入局部最优时，追随者在局部最优区域的精细搜索会导致搜索无法跳出局部最优，寻优精度和整体稳定性都会受影响。为了增强领导者精英个体对于追随者的影响，引入动态学习机制的追随者更新机制。具体方法是：首先，比较前次迭代中个体位置xi,j和相邻个体位置xi-1,j的适应度，在适应度较大的位置上(即离最优值距离较远的位置)引入惯性权重w，降低适应度较差个体位置的影响权重，而增加适应度较优的个体位置的影响权重。基于动态学习自适应惯性权重的追随者位置更新方式为

(10)

式中：w表示学习权重，随迭代次数发生改变，定义为

w=(Tmax-t)/Tmax

(11)

3.4 种群自适应划分机制

SSA中，若樽海鞘种群规模为N，领导者是樽海鞘种群中链首位置的个体，数量为1，剩余个体均为追随者个体，故数量为N-1。极少的领导者导致算法迭代早期进行全局勘探的领导者数量极度不足，追随者数量过高，全局勘探不充分，局部开发过于精细，易于陷入局部最优；而在迭代晚期则正好相反，局部开发过程缺乏，寻优精度过低。为了解决这一问题，引入种群自适应划分机制，利用正切三解函数的非线性控制方法，将樽海鞘种群中领导者和追随者数量做自适应调整，使领导的规模随迭代次数自适应递减趋势，追随者数量相应随迭代次数自适应递增，使SSA在迭代早期侧重于多领导者的全局勘探，提升收敛速度，而晚期侧重于多追随者的局部开发，提升寻优精度。具体数量计算如下：

种群中领导者数量为N×P，追随者数量为 (1-P)×N，P表示比例因子，定义为

(12)

式中：Pini表示比例初值，Pfinal表示比例终值，ξ表示调节系数，ξ>0。可知，比例因子P随着迭代数呈非线性改变，可以动态变更种群中领导者和追随者的配比，从而均衡算法的局部开发和全局勘探能力。

3.5 算法步骤

CDSSA算法的执行步骤如下：

步骤1 参数初始化，具体包括：种群规模N、最大迭代Tmax、收敛因子c1、随机变量r和c3、混沌值Ch、调节系数ξ、比例因子初值Pini、比例因子终值Pfinal、惯性权重w、位置上限值ub和位置下限值lb。

步骤2 利用3.1节改进Tent映射机制实现樽海鞘群中个体位置的初始化操作。

步骤3 根据基准函数计算初始樽海鞘群中所有N个樽海鞘个体的适应度。

步骤4 确定食物源位置。根据初始种群中个体的适应度，对所有樽海鞘个体进行降序排列，将适应度值最小即最优调度解的樽海鞘个体作为当前种群中的食物源位置。

步骤5 确定领导者和追随者。除食物源之外，将种群中剩余排序的N-1个樽海鞘个体作为领导者和追随者。具体地，根据种群自适应划分机制计算比例因子P，根据3.4节中的方法确定领导者数量和追随者数量。

步骤6 领导者位置更新。根据式(8)计算混沌值Ch，根据式(9)更新领导者位置。

步骤7 追随者位置更新。根据式(11)计算惯性权重w，根据式(10)更新领导者位置。

步骤8 重新计算个体适应度。重新计算领导者和追随者更新后的适应度，从中选择适应度最小的个体，将其适应度与食物源位置适应度比较，若该适应度小于原食物源适应度，则将该个体作为新食物源位置；否则，保留原食物源位置。同时，根据步骤6和步骤7中的方法更新领导者个体和追随者个体位置。

步骤9 若未达到预设最大迭代次数，则返回步骤5执行；否则，结束迭代，输出食物源代表的最优解。

图2是CDSSA算法的完整执行流程。

图2 CDSSA算法流程

4 数值仿真实验

4.1 实验环境及测试函数

搭建数值仿真验证算法有效性，测试过程侧重关注对于SSA中领导者和追随者的更新机制。将基于混沌Logistic映射的领导者更新的樽海鞘群算法命名为CLSSA，将基于动态学习权重的追随者更新的樽海鞘群算法命名为DWSSA，CDSSA算法则是本文设计的全面改进算法，3种算法在种群初始化和领导者与追随者规模更新方面均采用本文在3.1节和3.4节中设计的方法。选取典型的10个标准测试函数进行数值仿真，相关属性见表1，包括函数表达式、搜索区间、函数维度、理论最优值及搜索的目标精度等要素。测试函数中，单峰值函数f1(x)～f5(x) 可测试寻优精度，多峰值函数f6(x)～f10(x) 可测试全局寻优能力和收敛速度。对于连续多峰值函数，随着函数维度递增，其局部极值点会呈现指数级增长。

表1 标准测试函数

表2给出改进樽海鞘群算法的相关参数配置。仿真实验执行环境为Intel(R) Core i7 CPU 3.0 G，内存4 GB，64位微软操作系统WIN10，数值仿真软件为Matlab 2014a。

表2 SSA算法的参数

4.2 实验结果分析

实验一观察CLSSA算法、DWSSA算法、CDSSA算法以及基本SSA算法的性能，通过设置固定的算法迭代次数，观测算法的收敛速度和寻优精度变化。如图3所示是4种算法在10个基准函数测试下的收敛曲线，此时测试函数维度为30维。可以看出，CLSSA算法、DWSSA算法和CDSSA算法都可以在若干次的迭代过程之后逐步接近于目标函数的理论最优解，且3种算法的无论寻优精度还是收敛速度都要优于SSA。同时可以观测到，迭代约220次后，CLSSA算法曲线的下降趋势变得逐步明显起来，说明CLSSA收敛速度明显加快。在多峰值函数测试结果中，可以看到该算法在避免局部最优以及迭代晚期的收敛速度方面要明显优于SSA。DWSSA则明显不同，其早期迭代时的下降速度更快，迭代后期逐步变得稳定，在部分测试函数上其寻优精度和收敛速度也是明显优于SSA的。综合10个基准函数的测试结果来看，在领导者、追随者位置更新方式以及种群自适应划分优化机制下的CDSSA算法基本具有最佳的寻优精度和最快的收敛速度。

图3 算法的收敛情况

表3是算法在10个基准函数下测试得到的收敛精度结果，包括适应度的最大值、最小值、均值和标准方差。可以看出，CLSSA和DWSSA两种算法的收敛精度较传统SSA的基础均得到了提高，个体基准函数的测试上CDSSA与寻优精度与CLSSA相当，但多数基准函数(单峰值函数和多峰值函数)的测试中CDSSA拥有最佳的精度表现。对于多峰值基准函数而言，CDSSA的寻优精度远远高于传统的樽海鞘群算法SSA，这说明本文所采取的四方面的改进机制是有效可行的。

表3 算法的寻优结果

实验二观察本文涉及的CLSSA算法、DWSSA算法、CDSSA算法以及基本SSA算法在固定目标收敛精度的同时，算法达到该寻优精度时所需要进行算法迭代次数和寻优成功率。寻优成功率[11]表示计算成功次数与实验求解次数之比，求解是否成功的判定标准为

(13)

式中：FA为实际求解最优解，FT为基准函数理论最优解。

表4是测试结果，函数维度为30，最大迭代数为500，取30次独立运行的实验结果均值进行比较。若达到最大迭代次算法运行结果仍然没有达到所需的寻优精度，则将迭代次数定义为最大迭代次数。从表中结果可以看到，未作任何优化的传统SSA在前500次迭代中基本无法达到目标寻优精度，其成功率基本为0，说明该算法在处理复杂优化问题时仍然存在寻优精度低的问题，性能有待提升。此外，在处理多峰值基准函数时，DWSSA算法的寻优成功率平均高于65%以上，说明该算法处理多峰函数优化时性能表现较好。CLSSA的寻优成功率基本稳定在100%，说明领导者位置更新主导了樽海鞘群算法中种群的寻优方向，对于该部分的优化可以加速传统SSA的收敛速度。而本文的综合算法CDSSA的寻优成功率不仅稳定在100%，且其得到目标寻优精度时所需要的迭代次数也是远小于另外两种算法的，说明处理复杂优化问题时，该算法能够有效提升寻优精度和收敛速度。

表4 寻优成功率及收敛迭代数

实验三观察本文算法与同类型的SSA改进算法、较新的灰狼优化算法的性能对比情况。SSA的改进算法选取文献[10]的RDSSA、文献[11]的CASSA和文献[12]的ESSA进行性能对比研究，灰狼优化算法选取文献[15]中的基于精英对立学习与混沌扰动融合的混合灰狼优化算法HGWO、文献[16]中的混合差分进化策略的灰狼优化算法DEGWO进行性能对比。测试过程中，种群规模、迭代最大次数和函数维度设置相同。表5是6种算法在10个基准函数中计算得到的适应度的平均值和标准方差，前者可以衡量算法的寻优精度，后者可以衡量算法寻优稳定性。从结果可以看出，在绝大多数的单峰值函数和多峰值函数测试下，CDSSA算法在寻优精度和稳定性上均要优于同类型的改进SSA算法和灰狼优化算法。基于灰狼优化算法的改进算法与樽海鞘群算法的改进表现上各有不同，总体来说SSA的平均性能要好于灰狼算法，这取决于改进机制。较为全面的改进算法CDSSA的性能明显优于两种灰狼优化算法的改进，而ESSA改进较为局部性，其性能不如融合了差分进化的灰狼优化算法。

表5 同类算法的对比结果

进一步引入平均绝对误差MAE指标[17]辅证对比算法的性能，该指标是在所有10个基准函数的基础上计算得到。MAE指标的计算公式为

(14)

其中，mi为测试算法在基准函数测试中产生的最优解的均值，oi为基准函数的理论最优解，Nf为测试基准函数的数量，本实验取值为10。表6是6种算法的MAE指标表现，明显地，本文的CDSSA算法表现是最佳的，验证了算法的有效性。

表6 MAE指标表现

5 结束语

提出一种基于混沌映射与动态学习机制的自适应樽海鞘群算法CDSSA。算法采用了改进混沌Tent映射进行种群初始化，利用Logistic映射的领导者更新机制，提升种群多样性；同时，设计了动态学习追随者更新机制，使算法跳出局部最优，提升全局搜索能力，并利用领导者/追随者种群规模的自适应调整机制，有效均衡局部开发和全局勘探能力。大规模数值仿真实验的结果验证，改进樽海鞘群算法在寻优精度和收敛速度上均有较大提升，符合算法设计的性能改进初衷。