0 引言

仿生优化算法一般是从群体社会行为、物理现象或者生物自组织行为抽象出来的随机搜索算法.该算法具有以下3个优势: 1)针对目标函数, 不需要复杂的灵敏度公式推导; 2)优化过程中的搜索方向可根据适应度函数进行闭环自反馈调整, 其优化结果与初始值选择关联度不高; 3)算法结构紧凑性强, 易于程序集成化.自Holland开创遗传算法以来, 仿生优化算法呈现出百花齐放的局面.目前, 常用的仿生智能优化算法有:粒子群算法(particle swarm optimization, PSO)^[1]、遗传算法(genetic algorithm, GA)^[2]、蚁群算法(ant colony algorithm, ACO)^[3]、模拟退火算法(simulated annealing, SA)^[4]、蜂群算法(artificial bee colony, ABC)^[5]、萤火虫算法(glowworm swarm optimization, GSO和firefly algorithm, FA)^[6-7]等.

离子运动算法(ions motion algorithm, IMO)是由Javidy等^[8]从自然界中阴、阳离子相互吸引和相互排斥的基本特征中得到启发并提出的一种新的群智能仿生优化算法.该算法是一种元启发式(meta-heuristics)的随机搜索算法^[9], 与其他算法相比, 该算法能够在相同的时间内找到更加精确的最优值.目前, 已有学者将该算法运用到实际工程应用中, 如: Yang等^[10-11]将IMO算法运用到人类DNA基因段分布和乳腺癌预测中; 文献[12]将离子运动算法运用到支持向量机参数优化上, 并通过压阻式压力传感器温度补偿的实例验证了该方法可以提高分类效果; Das等^[13]将IMO算法运用于短期调度问题, 通过算例表明了该方法优化效果良好.

离子运动算法结构简单且高效, 但在空间探索和开发能力^[14]上仍有不足之处: IMO算法更新机制中两个最优的离子, 若它们出现在求解域空间中两个对立的极值峰上, 则可能引导离子群体的社团分化, 这种现象将会影响算法的空间探索效率; 此外, 该算法的晶态更新机制过于简单, 这种机制用来解决复杂的多峰优化问题时, 算法早熟收敛现象依然存在.目前, 已有学者对离子运动算法做了一些改进, 如在IMO算法结构中适当添加了混沌初始化^[12]、反向学习初始化^[13]等简单机制, 但是他们更注重算法自身的工程应用, 并未就改进算法的性能做系统性的分析.

值得注意的是, Wang等^[15]全面考察了离子运动的物理现象, 将同性离子的排斥力、异性离子的吸引力和液态离子的随机移动等特征行为考虑到IMO中, 提出了一种混合策略的改进离子运动算法(improved ions motion algorithm, IIMO).该算法在结构上的改进具体描述为:在IMO液态阶段的离子更新中, 添加了同类离子的排斥力特征项, 并对该特征项乘以一个随机扰动权重; 在固态阶段中, 该算法又根据离子适应度对应的排序, 定制不同的更新公式.通过测试函数验证, 该算法具有较强的鲁棒性.

与IIMO的方案不同, 本文设计一种基于多样性全局引导和动态反向学习的离子运动优化算法.首先在算法的液态阶段中, 借助于离子群的位置更新公式, 对离子更新加入全局引导耦合项; 然后, 为有效平衡该阶段的优化早熟行为, 引入基于群多样性的自适应反馈机制; 最后, 利用动态反向学习机制代替晶态阶段中的随机初始化过程.

就算法改进的机制而言, 全局最优引导一般用于提高全局的收敛性^[16-17], 反向学习则多用于跳出局部最优^[18].若一个算法同时拥有这两种机制, 则如何有效协调它们之间的配合, 将是该算法提高其优化性能的关键之处^[14].与大多数meta-heuristic算法相比, IMO在算法结构上, 将进化过程分为两个阶段:液态和晶态阶段.而在这种串联式的进化结构中, 分别引入全局最优引导和反向学习, 恰好有效避开了这两种机制的“对立”. IMO液态阶段的进化效果体现在初期, 在此阶段引入全局最优机制, 可以加速离子群体的聚集程度, 从而进一步加速进化过程; 晶态阶段的寻优机制大多体现在后期, 此时, IMO算法是利用离子群体的拥挤度来随机“搅动”部分离子.然而, 相对于这种随机性的重置, 采用反向学习机制可以使得离子“跑动”更具有方向性和目的性, 进而提高离子群体朝多样性发展的效率.

1 离子运动算法

离子运动的物理现象表现为:同性电荷离子排斥, 异性电荷离子吸引. 2015年, Javidy等^[8]根据这类现象抽象出一种新的优化算法——离子运动算法.算法的核心思想是:将每个离子视为求解空间中的候选解, 根据离子带电性把候选解集分成阴离子组和阳离子组.将搜索过程分为液态和晶态两个阶段:液态阶段, 在求解域中, 利用同性相斥或异性相吸的方式激发所有离子进行最优搜索, 搜索步长与离子之间的物理力(吸引力或排斥力)相对应; 晶态阶段, 有条件地引入外界能量摄动, 破坏部分晶体离子键, 使其进行由固态到液态的逆变换, 从而达到缓解过早收敛的效果.

在液态阶段中, 离子比较分散, 自由能偏多, 因此该阶段仅考虑异性吸引力作用.其离子位置的更新过程可抽象为

(1)

其中: A_i^t={A_{i, 1}^t, A_{i, 2}^t, …, A_{i, D}^t}为t时刻阴离子i的位置; C_i^t={C_{i, 1}^t, C_{i, 2}^t, …, C_{i, D}^t}为t时刻阳离子i的位置; A_best^t={A_{best, 1}^t, A_{best, 2}^t, …, A_{best, D}^t}和C_best^t={C_{best, 1}^t, C_{best, 2}^t, …, C_{best, D}}^t分别为整个群体t时刻最优阴离子和最优阳离子; D为变量的维度; AF_i^t={AF₁^t, AF₂^t, …, AF_D^t}和CF_i^t={CF₁^t, CF₂^t, …, CF_D^t}分别为阴离子吸引力和阳离子吸引力, 具体计算公式如下:

(2)

这里AD_i^t=|A_i^t-C_best^t|, CD_i^t=|C_i^t-A_best^t|.

经过液态阶段的运动更新, 离子逐渐靠拢, 又因物理条件, 离子由液态向晶态催化.这种现象类似于优化算法中候选解的聚集或收敛.晶态阶段中的物理条件定义为P_Cbest^t≥ P_Cworst^t/2, 并且P_Abest^t≥ P_Aworst^t/2.此时, 离子位置更新公式可描述为

(3)

其中: P_Abest^t和P_Aworst^t分别为t时刻阳离子的最优和最差适应度; Φ₁和Φ₂为在[-1, 1]内随机生成r₁和r₂的随机数.

值得注意的是, 部分晶体离子键因受外界能力干扰而进行了由固态到液态的转换, 这种物理现象恰好与优化算法中候选解的“变异”相似, 其数学公式为

(4)

其中: A_{up, d}和C_{up, d}分别为阴、阳离子第d维的上界限; A_{down, d}和C_{down, d}分别为阴、阳离子第d维的下界限; P_mut为离子键破坏系数; r为0-1的随机数.

将上述所有步骤整理, 可得到IMO算法的伪代码如下.

IMO伪代码.

输入:离子群体总规模N, 最大进化次数T_max.

1) 随机初始化种群

2) for i =1 to K_max do

3) 进入液态阶段

4)   for j=1 to N/2 do

5)   计算阴(阳)离子适应度

6)  end for

7)  找出最优阴离子和最优阳离子

8)  根据式(1)更新所有阴(阳)离子位置

9) 进入晶态阶段

10)  for j=1 to N/2 do

11)   计算阴(阳)离子适应度

12)   end for

13)  统计最优和最差阴阳离子

14)  if晶态下离子固化do

15)    for j=1 to N/2 do

16)   根据式(3)更新该阴(阳)离子位置

17)     if rand() < P_mut

18)    随机初始化该阴(阳)离子

19)     end if

20)   end for

21)   end if

22) end for

输出:历史最优离子, 并绘出相关统计图.

2 改进的离子运动算法 2.1 多样性全局最优引导

IMO液态阶段寻优策略, 就本质而言, 是两组解集的“双群落”寻优策略, 这种多群落算法有利于提高算法的开发能力^[19].然而, 从算法结构上, 在液态过程中的两组群落的耦合程度仍然过低, 算法并没有明确给出两组群落之间的协作关系, 阴阳离子的行为仅仅是朝着各自对面的最优值靠近.因此, 液态阶段中, IMO算法的全局空间探索还需要进一步改善.

值得一提的是, 受粒子群算法的基本公式启发, 人们通过对某些仿生算法加入全局引导项来增加算法的全局空间探索能力^[16-17].同理, 本文在离子运动算法的液态阶段中, 引入一个全局性引导的离子耦合项.因此, 式(1)的改造形式如下:

(5)

其中G_{best, t}为t时刻离子的全局最优解.

一般而言, 进化过快容易导致算法早熟收敛, 为平衡这一矛盾, 对式(5)添加动态多样性反馈控制的惯性权重^[20-21].于是, 液态阶段的离子更新公式可确定为

(6)

其中阴离子的惯性权重表示为

(7)

将ω_A(t)相关的阴离子改为阳离子, 即可得到式(6)中的ω_C(t).式(7)中, T_max为最大进化代数, Dν(t)为多样性测度, 可通过下式计算:

(8)

这里: popsize为阴离子的种群规模, Dim为变量维度, A_j^t为t时刻阴离子第j维上的均值, L为搜索域的最长对角线长度

(9)

X_{up, i}和X_{down, i}分别为搜索域第i维的上下限.

就式(6)而言, ω_A(ω_C)越小, 表示整个阴(阳)离子群体向当前全局最优点进化的趋势越大.其中:在进化初期, 式(6)对Dν的数值较为敏感, 若群体稍微收敛, 则会引起ω_A(ω_C)呈幂指数放大, 这使得整个群体会向全局最优点收敛, 而当前收敛的结果又必然在下一进化代中提高Dν的数值, 如此往复, 形成了类似于马太效应^[22]的全局进化效果; 在进化中后期, 当前代数t的影响程度显著提高, 其数值导致ω_A(ω_C)呈线性下降, 而此时的式(6), 更多是引导群体向各自对立的最优阴(阳)离子进化, 这有利于群体跳出局部最优解.

2.2 反向学习机制

反向学习(opposition based learning, OBL)由Tizhooshti^[18]提出, 其核心思想是:在优化过程中, 将候选解与其对应的反向个体同时考虑, 增强群体的多样性, 从而避免算法过早收敛.目前, 部分文献已将该思想融入粒子群、差分进化等智能算法中, 并取得了良好的效果^[23-26].

借鉴反向学习的思想, 本文将IMO算法晶态阶段中的“变异”随机化过程, 利用动态反向学习策略^[27]进行替换, 具体公式如下:

(10)

其中: A_j^t和C_j^t分别为t时刻阴、阳离子第j维上的数值; k∈[0, 1]为反向学习放缩参数, 其数值大小可生成不同的方向个体.若数值过小, 则使得被学习的离子呈镜像变换; 而数值过大, 则使得离子过分依赖于当前群体解, 也不利于群体多样化生成.此外, 鉴于优化前期以收敛速度为主, 后期以增加多样性为主, 整个优化过程应呈现“变异”频次由少变多的趋势.因此, 对于离子键破坏系数P_mut, 应采用动态惯性改变方式, 具体公式描述为

(11)

其中:相关系数均取正数; P_{mut, 0}为初始变异系数; λ为变异系数增量, 其数值表示离子键破坏系数的变化幅度, 数值过大会影响算法的收敛程度, 数值过小会降低整个晶态阶段离子群的活性, 不利于跳出局部最优; μ为进化代数放大系数, 该数值可以动态调整进化过程中的“变异”程度, 取值过大, 会影响进化中“变异”频次的增量, 相反, 则使得进化中“变异”频次固化.

综合上述方案, 本文提出改进离子运动算法, 具体流程见图 1.

3 仿真实验

本文选取23个国际常用优化测试函数^[28-31]作为测试集, 包含7个单峰测试函数、6个多峰测试函数以及10个固定维度下的复杂测试函数, 具体函数见表 1~表 3.优化算法对比方面, 除了选取标准的粒子群算法(particle swarm optimization, PSO)^[1]、IMO算法以及文献[15]提出的IIMO算法, 还引入了近期比较流行的樽海鞘群算法(salp swarm algorithm, SSA)^[30]、蝗虫优化算法(grasshopper optimisation algorithm, GOA)^[31]、正弦余弦优化算法(sine cosine algorithm, SCA)^[32]进行比较.

3.1 实验参数设置

为体现公正性, 每一种算法均在同一个实验环境中测试:本文所用编程软件为Matlab R2018a, 其计算机配置为Windows 7系统, CPU为Intel Core TM 4.0 GHz, 内存32 GB.优化算法中的共同参数为:最大评估次数maxFEs取值5 000×dim^[27], 种群规模N均取50, 其中IIMO算法中的其他参数可参考文献[15].通过测试, 本文涉及到的特定参数设置为: k=0.01, P_{mut, 0}=0.01, λ=0.09, μ=1.4.此外, 每个优化算法均对测试函数做30次独立运行, 并统计10维、30维和50维下对应的相关结果.

3.2 性能评价指标

传统的性能评价对比中, 优化算法最后的收敛平均值和相应的方差是衡量优化算法性能的一个基本指标:前者表示算法的收敛精度值, 后者表示算法的稳定性.两者数值越小, 算法性能越好.

为进一步比较算法性能, 本文引入Wilcoxon符号秩检验^[32], 该方法可在有限样本次数下评估两种算法的优劣性.具体过程为:首先针对某个测试函数, 将两种算法下的收敛值配对并相减, 这里定义差值最小精度为1e^-5; 其次进行Wilcoxon符号秩排序, 对差值为正数和负数的秩索引分别累加, 并标记为R+和R-; 最后进行比较, 若R+大于R-, 则认为后者算法更好, 反之亦然.通常, 信息置信水平默认设置为0.05.

一般情况下, 若优化算法获得的最优收敛值与理论最优值差值小于1e^-5, 则认为该算法已成功获得最优值.因此, 多样本统计中, 优化算法获得测试函数最优值的概率——收敛成功率, 也是一个值得考虑的评价指标^[14].

此外, 本文算法的时间计算复杂度主要取决于最大进化代数T_max、群体规模N、变量维度dim以及进入晶态阶段的频次T_c等.具体表示为

其中: O(Liq)=N×dim表示每代液态离子的位置更新的时间复杂度; O(min)和O(max)分别表示寻找最优和最差离子的时间复杂度, 具体数值均为N; T_c=log T_max, 而O(Cr)=N×dim为晶态离子的位置更新的时间复杂度.将上述数据整理, 可得

值得注意的是, 每个离子(粒子)的目标函数求解是算法中最耗时的部分, 因此, 本文涉及到的停机条件均采用相同的评价次数maxFEs.然而, 需要指出的是, 种群在每次迭代中的其他操作都不尽相同.如IMO算法晶态阶段的小概率初始化过程、IIMO算法液态阶段中的排斥力统计和本文算法中的多样性反馈测度计算等.这些复杂的操作或多或少会影响着整个算法的运算时间, 因此, 本文有必要进行分析与对比.

有趣的是, 这些操作频次又往往与随机数以及测试函数本身有关, 如IMO算法过程的初始化次数、本文算法中的反向学习频次等.因此, 通过伪代码理论分析运算时间的方法并不精确.

为有效统计算法的运算时间, 本文引入最优值收敛时间概念, 它指的是算法寻优到最优值的最短时间.其具体描述为:在规定的maxFEs下, 对特定测试函数进行多样本统计, 该算法成功获得最优值时的平均收敛时间.

3.3 仿真结果分析

表 4和表 5分别给出了各算法对单峰和多峰测试函数的平局收敛值(优化值减去理论最优值)、方差、Wilcoxon符号秩检验、最优收敛时间及收敛成功率的相关统计结果.其中: “+”、“ = ”、“-”分别表示本文算法优于、等于和劣于被比较算法; gm表示符号“+”与“-”的总数差值; 黑体字表示最优.通过观察可知:本文对函数f₁、f₂、f₃、f₄、f₆、f₁₀和f₁₃的寻优结果均达到了最优值, 且收敛率均为100 %; 对于这些函数, 本文算法的寻优精度并没有因维度增加而明显下降.此外, 对于f₄、f₅和f₁₁, 本文算法的平均收敛值均优于其他算法.值得注意的是:随着维度变大, 本文算法对f₁、f₂和f₁₁函数的寻优效果越好; 而对于函数f₅和f₉, 尽管本文算法的平均收敛率没有达到要求, 但是维度越大, 本文的收敛成功率却越大.另外, 在高维度的函数f₁₂中, 本文算法的相关指标依然高于其他算法.就收敛时间而言, 若本文算法找到了最优值(与理论最优解的误差小于1e^-5), 则对应的最优收敛时间必然低于其他算法, 且数值大小总体上都会小于其他算法一个数量级.最后, 关于Wilcoxon符号秩检验方面, 本文算法的总体性能均高于其他算法, 且测试函数维度越大, 本文算法的分数(gm)越高.

为便于观察各个算法对测试函数的收敛情况, 图 2~图 7分别给出了不同维度的测试函数收敛曲线.可以看出:对于函数f₃, 本文算法的收敛速度明显快于其他算法; 在30维度以上, 本文算法对f₁、f₂和f₄依然拥有较高的收敛速度; 对于函数f₆, 本文算法是最快到达最优值的算法; 对于函数f₅, 本文算法虽然没有找到最优值, 但其得到的最终收敛值比大部分算法都小, 且进化速度快而稳定.

从形态上看, 这些曲线大多数是高倾角或垂直下降, 且没有出现过阶梯型, 这说明本文算法在单峰函数具有快速性、持续性收敛到全局最优解的能力.这些能力主要得益于本文算法中的全局引导项G_best^t, 该项的引入可加速算法的收敛能力.针对高维度(30维以上)下的多峰函数f₉、f₁₀和f₁₂, 本文算法的曲线基本是梯田式收敛, 这说明本文算法在寻优阶段经历过几个局部最优解, 但始终可以进行不断进化.这种曲线形态是由本文算法自身特性决定的:本文算法考虑了群体的多样性, 引入的自适应动态多样性反馈惯性权重可有效缓解离子群体的聚集和踩踏; 固态阶段的反向学习初始化过程有助于离子群体的疏散.这些算法构造, 从整体上增强了本文算法跳出局部最优解的能力.一旦全局引导项G_best^t跳出并到达某个更好的最优解“坑”中, 整个曲线又受G_best^t引导, 再次进行断崖式的收敛, 从而使算法快速找到当前最优解.此外, 对于高维下的函数f₁₁, 本文算法的收敛曲线还没达到最大评估次数便快速收敛到数值0;而对于多峰函数f₁₃, 本文算法的进化收敛曲线依然呈现出高倾角的下降.

为进一步考察本文算法的性能, 表 6又给出了10个固定维度下的复杂多峰测试函数统计结果.可以看出:本文算法的收敛值和方差性能最优的频次仍然最高; 本文算法的Wilcoxon符号秩检验总体分数依然高于其他算法.

综合上述性能指标可以得出, 虽然本文算法对于单峰函数f₇、多峰函数f₈和固定维度下的多峰复杂函数f₁₄表现不佳, 但是总体而言, 本文所提出的算法性能更加优越.

最后, 为体现本文算法性能是多样性全局引导和动态反向学习机制的综合结果, 本文就单独使用多样性全局引导或动态反向学习机制的IMO算法进行了仿真, 相关对比结果见表 7.可以看出, 本文算法明显优于其他两种单独机制下的IMO算法.

4 结论

针对离子运动优化算法的不足, 本文引入全局引导项来增强算法的空间探索能力, 又加入多样性权重反馈和动态反向学习策略来提高算法的局部开发能力.为全面比较算法性能, 本文从平均收敛值、方差、Wilcoxon符号秩检验、收敛成功率以及最优收敛时间等几个方面进行了考察, 实验表明, 本文所提出的算法无论对于单峰还是多峰函数, 都具有快速收敛性和跳出局部解的能力.

此外, 本文还存在不足:针对本文算法涉及到的非策略参数, 如初始变异系数、变异系数增量以及反向学习放缩参数等, 文中并没有定量讨论.这些参数对优化性能是否有影响, 影响多大, 是否能构造出与具体优化函数关联的自适应形式变化, 这些都是值得研究的问题.

值得一提的是, 关于离子运动算法的离散型优化问题目前还没有涉及.如何将离子运动算法从连续型优化过渡到离散型优化, 也是一个值得研究的方向.