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

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

5. 设置密集因子 δ 为较小值;
6. 计算当前种群最大适应度 F max 与平均适应度 F avg ;
F avg
7. if > δ then
F max
8. 变异概率 P m = P mbig ;
9. else
10. 变异概率 P m = P msmall ;
11. 随机生成 0 到 1 之间的一个随机数 r ;
P m > r then
12. if
′
13. 采用随机单点变异的方式对染色体 p 进行变异, 产生新个体 p ;
′
14. if f(p) > f(p ) then
′
15. 种群中保留 p , 将 p 舍弃;
16. else
′
17. 用 p 替换掉种群中的 p ;
18. else
19. 不进行变异操作;

自适应大变异算子, 基于大变异操作, 能够保证在种群进化的前期, 采用较小的变异概率来防止优良基因被破
坏. 在种群进化的后期, 采用较大的变异概率来增强算法跳出局部最优解的能力.
2.6 算法流程
基于上述实数编码、适应度函数、自适应选择算子、自适应交叉算子以及自适应大变异算子的介绍, 本节给
出两阶段自适应遗传算法, 如算法 1 所示.
算法 1. 两阶段自适应遗传算法 (TSAGA).

输入: 划分序乘积空间 POPS m = (×P i ,≼ P ) , 阈值 γ , 第 1 阶段遗传算法最大迭代次数 T 1 , 第 1 阶段遗传算法当前迭
t 1 , 第 T 2 , 第
代次数 2 阶段遗传算法最大迭代次数 2 阶段遗传算法最大迭代次数 t 2 , 染色体 p , 交叉概率分界值 P b ,
P mbig ;
常规变异概率 P msmall , 大变异概率
输出: 问题求解层.
1. 随机生成实数编码的染色体表示问题求解层, 构成第 1 阶段初始种群 //开始第 1 阶段遗传算法
2. 生成一个空集合 POP ;
3. t 1 = 1 ;
4. while t 1 ⩽ T 1 do
5. 根据定义 10 计算种群中染色体的适应度值;

6. 将当前种群中最优染色体保存到集合 POP 中;
7. 按照经典的选择、交叉、变异算子进行选择、交叉、变异操作;

8. t 1 = t 1 +1 ;
9. end while
POP 作为第 2 阶段初始种群的一部分, 种群中其余染色体随机产生; //开始第 2 阶段遗传算法
10. 将
11. t 2 = 1 ;
t 2 ⩽ T 2 do
12. while
13. 根据定义 10 计算种群中染色体的适应度值;