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

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

t 2
14. if ⩽ γ then //自适应选择算子
T 2
15. 同时使用轮盘赌选择和精英保留策略进行选择操作;
16. else
17. 仅使用精英保留策略进行选择操作;
p 2 ; //自适应交叉算子
18. 将种群中所有染色体任意两个随机组合构成一对父本染色体 p 1 和母本染色体
f pavg ;
19. 计算父本染色体
p 1 和母本染色体
p 2 适应度平均值
t 2
20. if ⩽ γ then
T 2
P c = P b +(1− P b )×(1− f pavg ) ;
21.
22. else
23. P c = P b −(1− P b )× f pavg ;
24. 随机生成 0 到 1 之间的一个随机数 r ;
25. if P c > r then
′ ′ ′ ′ p 2 ;
26. 采用多点交叉的方式产生子代 p 和 p 并用子代 p 和 p 替换父本 p 1 和母本
1
2
1
2
27. else
28. 父本 p 1 和母本 p 2 之间不进行交叉操作;
t 2
29. if ⩽ γ then //自适应大变异算子
T 2
30. 设置密集因子 δ 为较大值;
31. else
32. 设置密集因子 δ 为较小值;
33. 计算当前种群最大适应度 F max 与平均适应度 F avg ;
F avg
34. if > δ then
F max
35. 变异概率 P m = P mbig ;
36. else
37. 变异概率 P m = P msmall ;
38. 对种群中染色体随机生成 0 到 1 之间的一个随机数 r ;

39. if P m > r then
′
40. 采用随机单点变异的方式对染色体 p 进行变异, 产生新个体 p ;
′
41. if f(p) > f(p ) then
′
42. 种群中保留 p , 将 p 舍弃;
43. else
′ p ;
44. 用 p 替换掉种群中的
45. else
46. 不进行变异操作;
47. t 2 = t 2 +1 ;
48. 输出当前种群中最优染色体即为所求的问题求解层;
49. end while
对于两阶段自适应遗传算法, 在算法的一次迭代过程中, 对于每个染色体在计算其适应度函数时需要计算分
2
类精度, 时间复杂度为 O(m×|U| ×|C|) , 其中 m 为视角的个数, 即染色体的长度, |U| 为视角中对象个数, |C| 为视角
2
中属性个数, 所以计算种群中所有染色体适应度函数的时间复杂度为 O(m×|U| ×|C|× N) , 其中 N 为种群规模. 选
择算子的时间复杂度均为 O(N) . 交叉算子采用多点交叉, 时间复杂度为 O(N ×m) . 变异算子采用单点变异, 时间