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

徐怡 等: 基于遗传算法的划分序乘积空间问题求解层选择 1951

2.3 自适应选择算子
选择算子用于对群体进行优胜劣汰操作, 轮盘赌选择 [28] 和精英保留策略 [32] 是两种常用的选择算子. 轮盘赌选
择能增大优秀个体被选中的概率, 但无法保证最优秀个体一定能被保留到下一代. 精英保留策略能保证最优秀个
体能被保留到下一代, 但无法对种群其他个体进行控制. 由于轮盘赌选择和精英保留策略都是通过牺牲种群的多
样性来获得更快的收敛速度, 因此在种群进化的前期, 种群多样性较高, 为了使算法尽快收敛, 将轮盘赌选择和精
英保留策略结合使用, 在保证最优个体得以保留的同时加快收敛速度 [33] . 在种群进化的后期, 种群的多样性逐渐
降低, 仅使用精英保留策略, 在保留最优个体的同时降低对种群多样性的破坏. 为此, 本文提出一种随种群进化迭
代次数动态变化的自适应选择算子.
首先通过设置阈值将种群进化过程分为前期与后期. 假设遗传算法的最大迭代次数为 T, 当前迭代次数为 t ,
t t
t
t
0 ⩽ t ⩽ T . 给定阈值 0 ⩽ γ ⩽ 1 , 则当 ⩽ γ 时, 第 次迭代属于进化前期, 当 > γ 时, 第 次迭代属于进化后期. 通
T T
γ 的值可以设置为 0.5.
常
自适应选择算子的伪代码描述如下.
伪代码 1. 自适应选择算子.
1. 初始化最大迭代次数 T, 当前迭代次数 t , 阈值 γ ;
t
2. if ⩽ γ then
T
3. 选择算子同时使用轮盘赌选择和精英保留策略;
4. else
5. 选择算子仅使用精英保留策略;

自适应选择算子, 在种群进化的前期, 能够保证最优个体得以保留的同时加快算法收敛速度. 在种群进化的后
期, 能够在保留最优个体的同时降低对种群多样性的破坏.
2.4 自适应交叉算子
交叉算子用于维持种群的多样性 [34] , 交叉算子以交叉概率为基础, 较高的交叉概率能增加交叉操作发生频率,
加快搜索过程, 但可能会破坏适应度值高的染色体. 较低的交叉概率能降低适应度值高的染色体被破坏的可能性,
但会使得进化速度变慢 [35] . 因此, 在种群进化的前期, 我们希望设置较大的交叉概率, 在种群进化的后期, 设置较
小的交叉概率. 同时, 在进化过程中, 适应度值较小的个体应该获得较大的交叉概率来优化其基因型, 适应度值较
大的个体应该获得较小的交叉概率来保留其基因型. 为此, 本文提出一种交叉概率随当前种群进化迭代次数以及
交叉个体适应度值动态变化的自适应交叉算子. 和第 2.3 节一样, 通过设置阈值 γ 将种群进化过程分为前期与后
期. 自适应交叉概率定义如下.
定义 11. 给定当前进行交叉的父本染色体 p 1 和母本染色体 p 2 , 假设 T 是遗传算法的最大迭代次数, t 是当前
迭代次数, 0 ⩽ t ⩽ T , f(p 1 ) 和 f(p 2 ) 是 p 1 和 p 2 的适应度值, f pavg = avg( f(p 1 ), f(p 2 )) 是 f(p 1 ) 和 f(p 2 ) 的平均值, P b
是给定的交叉概率分界值, 0.5 ⩽ P b ⩽ 1 . 则 p 1 和 p 2 的自适应交叉概率 P c 定义为:
 t
 P b +(1− P b )×(1− f pavg ), ⩽ γ


 T


(5)
P c = 
 t

 P b −(1− P b )× f pavg , > γ


T
t t
t
t
其中, ⩽ γ 表示第 次迭代属于进化前期, > γ 表示第 次迭代属于进化后期.
T T
由定义 11 可以看出, 进化前期的交叉概率大于进化后期的交叉概率. 此外, 不论在进化前期还是进化后期, 适
应度值较小的染色体会获得较高的交叉概率, 适应度值较大的染色体则会获得较低的交叉概率.
本文采用多点交叉的方式进行交叉操作 [35] . 自适应交叉算子的伪代码描述如下.