Page 374 - 《软件学报》2024年第4期

1952 软件学报 2024 年第 35 卷第 4 期

伪代码 2. 自适应交叉算子.
1. 初始化最大迭代次数 T, 当前迭代次数 t , 阈值 γ , 交叉概率分界值为 P b , 父本染色体 p 1 和母本染色体 p 2 ;

2. 计算父本染色体 p 1 和母本染色体 p 2 适应度平均值 f pavg ;
t
3. if ⩽ γ then
T
4. P c = P b +(1− P b )×(1− f pavg ) ;
5. else
P c = P b −(1− P b )× f pavg ;
6.
7. 随机生成 0 到 1 之间的一个随机数 r ;
8. if P c > r then
′ ′ ′ ′
9. 采用多点交叉的方式产生子代 p 和 p 并用子代 p 和 p 替换父本 p 1 和母本 p 2 ;
1 2 1 2
10. else
11. 父本 p 1 和母本 p 2 之间不进行交叉操作;
自适应交叉算子, 能够保证在种群进化的前期, 采用较大的交叉概率, 提高算法的收敛速度. 在种群进化的后
期, 采用较小的交叉概率, 降低适应度值高的染色体被破坏的可能性. 同时适应度值较小的染色体能够取较高的交
叉概率来优化其基因型, 适应度值较大的染色体能够取较低的交叉概率来保留其基因型.
2.5 自适应大变异算子
变异操作用于帮助遗传算法跳出局部最优解. 但是, 传统变异算子会将变异概率设置的极小, 这样就会造成变
异操作被执行的可能性很小, 再加上变异操作并不一定能生成更优秀的个体, 所以单靠传统的变异算子很难帮助
算法跳出局部最优解. 因此本文基于大变异操作, 同时考虑到在进化前期, 种群多样性较高且种群内优秀个体较
少, 此时需要减小变异概率来防止优良基因被破坏. 在进化后期, 种群多样性较低, 此时需要增大变异概率来跳出
局部最优解. 为此, 本文提出一种随当前种群进化迭代次数动态变化的自适应大变异算子. 大变异操作 [36] 是当某

一代的最大适应度 F max 与平均适应度 F avg 满足:
F avg
> δ (6)
F max
则认为当前种群的适应度值较为集中, 将该代中所有个体的变异概率设置为比通常变异概率大 4 倍以上的概率
0.5 ⩽ δ < 1 , 被称为密集因子, 决定大变异操作被执行的概率, 越接近 0.5, 种群被判断为适应度集中
δ
P mbig . 其中
的可能性越高, 大变异操作被执行的概率就越大.
同第 2.3 节一样, 通过设置阈值将种群进化过程分为前期与后期. 在进化前期将 δ 设置为一个较大的值, 在进
化后期将 δ 设置为一个较小的值.
由于当变异概率过大时算法接近随机搜索, 为了防止种群发散, 本文引入一个条件来判断大变异操作是否可
行. 若某个体变异后的适应度值小于变异前个体的适应度值, 将本次变异取消, 种群中仍然保留变异前个体; 否则
我们用变异后个体替换种群中的原个体. 本文采用随机单点变异的方式进行变异操作, 即随机将染色体中的一个
基因位从当前值变为值域内的一个可行值.
自适应大变异算子的伪代码描述如下.

伪代码 3. 自适应大变异算子.
1. 初始化最大迭代次数 T, 当前迭代次数 t , 阈值 γ , 种群染色体 p , 常规变异概率 P msmall , 大变异概率 P mbig ;
t
2. if ⩽ γ then
T
3. 设置密集因子 δ 为较大值;
4. else