Page 74 - 《软件学报》2020年第12期

3740 Journal of Software 软件学报 Vol.31, No.12, December 2020

时,就会采取相应的重启策略,包括重新初始化该种群的分布协方差矩阵 C,并将其分布均值 m 向最优种群的分
布均值转移.算法采用这种重启机制来使种群跳出局部最优解,不断将表现差的种群向表现好的种群方向转移,
并使其在当前最优解附近进行新的探索.之后的实验中也验证了这种方式的有效性.
种群性能评价函数定义为
(
(
Fp i g ) = (1 β − ) f p∇ ( i g ) β + Fp i g− 1 ) (12)
其中, f p∇ ( i g ) 表示种群 p i 在第 g 次迭代时的适应度变化量(使用当前样本适应度均值和上一代样本适应度均值
之差表示),β为超参数表示历史信息的利用率.这种设定是为了综合考虑种群的历史累积表现.同时,种群重启概
率设计如下:
⎧ 10⋅ g − 1
⎪ e ϖ
+
⎨ True, 0.01 0.99⋅ e − > rand (13)
10
⎪ 1
⎩ false, otherwise
其中, g 表示当前迭代次数与上一次策略重启时迭代次数之差;ϖ是一个超参数,当种群 p i 使用公式(13)返回为
True 并且其性能 (Fp g ) 在所有种群中最小时,种群 p i 就会进行重启,并将 g 重置为 0.
i
公式(13)的概率曲线如图 3 所示.

Fig.3 Restart probability curve
图 3 种群重启概率曲线

由于使用多种群竞争进化提供了更多的探索性,所以极大地提升了算法的探索能力,之后的实验中也验证
了这一观点.
2.5 MCC-NES算法伪代码
基于以上分析,MCC-NES 的伪代码在算法 2 中给出.其中:第 1 行~第 3 行是关于算法参数、适应度函数以
及适应度塑造方法的初始化过程;第 5 行完成每个种群中的 3 个最优全局特征序列和 1 个随机全局特征序列的
初始化工作;第 6 行是将原始特征集合根据设定的大小进行划分;第 7 行~第 9 行初始化每个种群中每个亚种群
的分布参数;第 12 行开始算法的迭代过程;第 14 行~第 37 行表示每个种群的进化过程,具体的,第 15 行~第 36
行是每个亚种群的进化操作,其中包括分布采样(第 16 行、第 17 行)、生成种群随机特征序列(第 18 行)、评估
每个样本适应度(第 19 行~第 31 行)、实现亚种群的更新操作,使用样本的搜索梯度来更新分布参数(第 32 行~
第 35 行).第 38 行~41 行检测是否有种群满足重启条件,如果存在满足条件的种群,就对该种群进行重启操作.
算法 2. MCC-NES.
1: Input: The number of population σ, the size of subpopulation m, the number of individuals
insubpopulation λ, the number of iterations τ, the Initialization parameters α, restart threshold ϖ,
historical utilization β;
2: Initialize: fitnessfunction f(⋅) as equation 10, fitnessfunction u(⋅) as equation11, set g to 0