Page 185 - 《软件学报》2021年第10期

肖辉辉 等:基于多策略的改进花授粉算法 3157

15. Generate a new candidate x i t 1 according to Eq.(7);
16. else
17. Generate a new candidate x i t 1 according to Eq.(8);
18. endif
19. endif
20. Evaluate the newly generated solution x t 1 ;
i
21. FEs=FEs+1;
t
22. if fun (x t 1 )  fun ( )x
i
i
t
23. replace x by x i t 1 ;
i
24. else
25. Generate a new candidate x i t 1 according to Eq.(9);
26. Evaluate the newly generated solution x t 1 ;
i
27. FEs=FEs+1;
t
28. if fun (x t 1 )  fun ( )x
i
i
t
29. replace x by x i t 1 ;
i
30. endif
31. endif
32. endfor
33. Update the current best solution x best ;
34. endwhile
MIFPA 算法与基本 FPA 算法的框架基本类似,但其中主要有 4 个不同之处:① 转换概率 p 采用自适应调整
策略,详见第 8 行;② 增加了两组随机个体的差异矢量到全局搜索(全局授粉)中,详见第 10 行、第 11 行;③ 采
用一个线性递减概率规则融合两种变异机制进行局部搜索(局部授粉),详见第 14 行~第 18 行;④ 利用余弦函数
搜索因子对算法中的劣解进行改进,详见第 25 行.
2.5 MIFPA算法的复杂度分析
衡量改进算法的有效性和可行性,一是算法的寻优性能要有较大的提高,二是算法的时间复杂度也不能比
原算法高太多.在群智能优化算法中,时间复杂度是指通过优化算法求解优化问题的最优解或次优解所需要的
进化次数.下面对 MIFPA 算法的复杂度进行分析.
假设目标函数设为 f(x),算法的种群规模设为 n,求解问题的维数设为 D,f(D)为计算给定解的目标函数的执
行时间与求解问题维数 D 有关的函数,则依据算法的描述和符号 O(时间复杂度符号)的计算规则为:
 在初始化种群并计算得到最优值和最优解阶段的时间复杂度为 O(n(r 1 D+f(D)))=O(D+f(D)),其中,r 1 为
产生均匀分布随机数的执行时间;
 全局优化部分的时间复杂度为 O(n(r 2 D))=O(D),其中,r 2 为式(1)生成新解时一维变量的执行时间;
 局部优化部分的时间复杂度为 O(n(r 3 D))=O(D),其中,r 3 为式(5)生成新解时一维变量的执行时间;
 更新全局最优值和全局最优解部分的时间复杂度为 O(n(r 4 +r 5 D+f(D)))=O(D+f(D)),其中,r 4 、r 5 分别为
比较新解与旧解和替换一维旧解变量的执行时间.
所以,FPA 算法的时间复杂度 [20] 表示为 T(FPA)=2O(D+f(D))+2O(D)=O(D+f(D)).从第 2.4 节的算法流程可知:
公式(6)~公式(9)是改进算法修改之处,即包括新的全局搜索策略、新的局部搜索策略和对质量不好的解的改进
方法.依据上述对算法公式的描述和符号 O 的计算规则,可推导出 MIFPA 的时间复杂度为
T(MIFPA)=T(FPA)+T(公式(6))+T(公式(7))+T(公式(8))+T(公式(9))
=O(D+f(D))+O(n(r 6 D))+O(n(r 7 D))+O(n(r 8 D))+O(n(r 9 D))