基于种群的随机优化算法是求解优化问题的重要方法之一, 也是求解全局优化问题的有效方法, 受到了国内外众多学者的关注, 在图像处理、数据处理、工程应用等领域得到了广泛应用[1-2].通常对于一组随机产生的初始种群, 利用不同的数学方法或随机操作在解搜索空间内对其进行演化更新, 在优化过程中实现信息互换, 能方便地从不同搜索空间获取信息, 兼顾了算法的全局搜索能力和局部开发能力.基于种群的优化算法随机地寻找优化问题的最优解, 不能保证一次运行便能找到解, 但是, 随着种群规模和迭代次数的增加, 找到全局最优解的概率会增大.近年来, 有效的群智能优化算法有粒子群优化算法[1](particle swarm optimization, PSO)和灰狼优化算法[2](grey wolf optimization, GWO)等.
正余弦算法[3](sine cosine algorithm, SCA)于2016年提出, 利用正余弦函数的数学模型使解震荡性地趋于最优解, 算法中随机性参数和自适应参数较好地平衡了算法的开发和探索能力. SCA具有参数少、易实现、结构简单、收敛速度快等优点, 但也存在着计算精度低、易早熟收敛等缺点.
为了改进SCA的性能, 文献[4]将反向学习策略融入SCA的初始化过程和更新过程, 提出了基于反向学习的SCA(OBSCA), 提高了SCA的精度和性能.为了改进SCA的计算精度, 本文对SCA作了以下3个方面的改进: 1)采用非线性对数曲线参数调整策略, 平衡算法的开发与探索能力; 2)利用混沌序列的随机性、遍历性以及规律性特点, 设计一种基于精英个体的混沌搜索策略, 增强算法的局部搜索能力; 3)采用基于精英混沌搜索策略的SCA与反向策略交替进行的方法增强解的多样性, 降低算法的复杂度, 减少算法运行时间. 23个基准测试函数的实验结果表明, 改进的SCA能够有效地协调探索和开发能力, 并且在收敛精度与收敛速度上优于对比算法.
1 正弦余弦算法对于n维最小化问题
其中: xi为优化变量, ai、bi为其上下界.
SCA的求解思路是, 设种群规模为N, 首先在n维解空间中随机产生N个个体x1, x2, ..., xN, 第i个个体的位置表示为xi=(xi1, xi2, ..., xin), i=1, 2, ..., N.通过目标函数计算个体的适应度值f(xi), 记录种群中最优个体位置x*:x*=argminf(xi), i = 1, 2, ..., N.种群中第i个个体第j维按下式进行更新:
(1) |
其中: r2∈(0, 2π), r3∈(0, 2), r4∈(0, 1)为均匀分布的随机数; x*t为当前最优个体位置; r1为控制参数, 表示为
(2) |
a为常数; t、tmax分别为当前迭代次数和最大化迭代次数, 利用贪婪搜索更新种群最优个体位置.
2 基于精英混沌搜索策略的交替正余弦算法 2.1 控制参数的非线性调整策略在SCA中, 参数r1起着平衡全局探索能力和局部搜索能力的重要作用.当r1 < 1时使下一代的解位于当前解与目标解之间, 强调算法的开发能力; 当r1>1时解位于当前解和目标解之外, 强调算法的探索能力.由式(2)可以看出, r1随迭代次数的增加线性递减, 在算法迭代初期, r1的值较大, 使算法具有较强的全局探索能力, 在算法迭代后期, r1的值较小, 增加了算法的开发能力.但是, 线性变化方式不能有效地增加SCA的寻优精度, 本文通过非线性函数[5]对r1进行改进.利用自然对数在[1, e]上非线性递增的特性, r1的调整策略为
(3) |
其中: astart、aend为控制参数a的初始值和最终值, astart>aend≥0;η>0为调节系数.由式(3)可以看出, r1随着迭代次数的增加非线性变化, 可以有效地平衡SCA的探索和开发能力, 提高算法的寻优能力和收敛速度.
2.2 反向学习策略略反向学习(OBL)[6]是增强随机优化算法性能的重要方法, 通过贪婪选择目标函数在当前解和反向解种群的适应度值, 增强了种群的多样性, 提高了算法接近全局最优解的能力.文献[4]提出的OBSCA在基本SCA中加入反向学习策略, 提高了SCA的求解精度.本文旨在将SCA与反向学习策略交替进行, 以降低算法的复杂性, 从而在改进种群多样性的同时提高算法的收敛速度.
定义1 反向解.设第t代种群中第i个个体为xit=(xi1t, xi2t, ..., xint), 记aj、bj为搜索空间中第j维的下界和上界, 令
(4) |
称xit=(xi1t, xi2t, ..., xint)为其反向解.
由式(4)可知, 反向学习算法通过反向策略产生N个反向解, 使算法在2N个个体中挑选优秀个体进入下一代, 增强了种群的多样性和全局探索能力, 同时贪婪选择策略又增加了算法的收敛速度.
2.3 精英混沌搜索策略群智能算法的优劣在于有效地平衡算法的探索与开发能力, 为了提高算法的开发能力, 利用混沌的随机性、遍历性和规律性的特点, 对精英个体[7]进行混沌变异.对种群中N个个体按适应度值升序排序, 选择前m=pr· N个个体作为精英个体, pr∈[0, 1]为选择比例, 记精英个体为{ex1t, ex2t, ..., exmt}⊂{x1t, x2t, ..., xNt}, exit=(exi1t, exi2t, ..., exint), i= 1, 2, ..., m.其第j(j=1, 2, ..., n)维的上下界[8]分别为
(5) |
将精英个体exit由解空间按式(6)映射到[0, 1], 得到混沌变量Cit=(Ci1t, Ci2t, ..., Cint), 有
(6) |
利用式(7)对Cijt进行混沌迭代, 有
(7) |
其中: μ为常数, 取值为4; k为混沌迭代次数, 0≤ k≤ceil(t/10), ceil(x)表示对x向上取整.
当k达到最大迭代次数kmax时, 得到第i个精英个体对应的混沌变量Cikmax, 利用下式将其映射至[eajt, ebjt]内, 得到对应混沌个体xCit, 有
(8) |
对混沌个体xCit与原个体exit, 由下式生成候选解:
(9) |
其中λ为收缩因子, 其值为
(10) |
在得到的候选解xit(λ)与对应精英个体exit之间采用贪婪选择策略, 选择优秀的个体exit'取代当前个体exit, 即
(11) |
由式(10)可以看出, 设计的收缩因子λ随着迭代次数的增加逐渐减小.式(9)表明, λ越小, exit对候选解xit(λ)的影响越小.因此, 算法随着迭代次数的增加, 精英个体的上下界范围逐渐缩小至目标解附近, 候选解xit(λ)越侧重随机性、多样性较强的混沌个体xCit, 局部搜索能力越强.精英个体的混沌变异策略所控制的混沌搜索范围随算法迭代次数的增加逐渐缩小, 实验验证该策略具有较强的局部搜索能力.
2.4 算法描述反向学习算法能增加种群的多样性, 增强算法的探索能力, 精英混沌搜索策略可以增强算法的开发能力, 将融入精英混沌搜索策略的SCA与融入精英混沌搜索策略的OBL交替执行, 可以很好地降低算法的复杂度, 减少算法的运行时间.因此, 基于精英混沌搜索策略的交替正余弦算法(COSCA)步骤如下.
Step 1:算法参数设置.种群规模N, 控制参数a的初始值astart和最终值aend, 最大化迭代次数tmax, 调节系数η>0, 精英选择比例pr.
Step 2:初始化.令t=0, 随机在解搜索空中产生N个个体, 组成种群G.
Step 3:对G中的个体执行式(4)的反向策略, 形成种群G, 计算G∪G中个体的函数值, 按从小到大排序, 选择前N个个体组成初始种群Gt, 并记录最优个体x*t.
Step 4:若t为奇数, 则执行Step 4.1;若t为偶数, 则执行Step 4.2:
Step 4.1:对Gt中的个体执行SCA算法, 其中控制参数r1如式(3)所示, 对个体按适应度值由小到大排序得到种群Gzt+1;
Step 4.2:对Gt中的个体进行式(4)的OBL策略更新得到Gt, 对G∪G中的个体按函数值从小到大排序, 选择前N个个体组成种群Gzt+1.
Step 5:对Gzt+1中的前m个精英个体进行式(5) ~ (11)所示的精英混沌搜索, 其余N-m个个体不变, 形成种群Gt+1.
Step 6:记录Gt+1中最优个体x*t+1, 若f(x*t) < f(x*t+1), 则x*t+1=x*t.
Step 7:判断算法是否满足结束条件, 若满足, 输出最优值f(x*t+1), 否则令t=t+1, 转至Step 4.
2.5 算法收敛性分析文献[9]利用鞅论给出了由最优值引导的算法收敛性分析, 文献[10-11]给出了混沌搜索和反向学习引导的算法的收敛性分析.由COSCA过程可以看出, 个体的演化是基于随机过程的马尔可夫链.由文献[9-11]的收敛性分析过程可得到, COSCA随迭代次数的增加, 依概率收敛到全局最优解.
3 数值实验与分析为了验证COSCA的性能, 本文选取文献[12-15]中由F1 ~ F7表示的单峰函数, F8 ~ F13表示的多峰函数和F14 ~ F23表示的固定维函数的23个标准测试函数进行仿真实验.
3.1 与SCA, OBSCA, GWO, PSO算法的比较为了测试COSCA的性能, 将COSCA与SCA、OBSCA、PSO算法及其改进算法OBPSO[16]算法、GWO算法进行实验比较.此外, 对比实验中加入了未修改参数r1的COSCA (简记为COrSCA)以验证非线性参数调整策略的有效性.在对比实验中, 为了公平起见, 所有算法均使用相同的种群规模N=30, 算法的最大迭代次数tmax=500.对于每个测试函数, 各算法均独立运行20次(runs), 记录其平均精度Ave, 标准差STD和CPU时间, 利用显著性水平α=0.05的Wilcoxon秩和检验[17]评价两种算法的优劣.平均精度、标准差的计算公式为
(12) |
(13) |
其中valuei表示算法第i次的运行结果.
COSCA中, r1取值见式(3), η=1, astart=1, aend=0, 精英个体比例pr=0.1, 其他算法的参数设置如表 1所示.
表 2给出了7种算法在维数n=30时独立运行20次的平均精度和标准差, “+/=/-”分别表示用Wilcoxon秩和检验时对比算法“优于/相当/劣于”COSCA函数的个数, 加粗数据表示计算效果好的函数.表 3给出了COSCA与对比算法进行Wilcoxon秩和检测时的概率值P以及运行20次的CPU时间, 加粗数据表示对比算法与COSCA算法计算结果差异较小.
为了更直观地反映各算法的性能, 图 1给出了7种算法对6个测试函数的收敛曲线. F1, F2, F9, F10的收敛曲线以log10(f(x))作为纵坐标.
由表 2和图 1可以看出, COSCA的性能明显优于SCA与OBSCA.通过Wilcoxon秩和检验可知, COSCA对20个函数的结果优于SCA, 19个函数的结果优于OBSCA, 尤其对函数F9与F11, COSCA可收敛到理论最优值0, 且标准差为0.
由表 2可知, COSCA对14个测试函数的结果优于COrSCA, 说明式(3)非线性策略对提高算法精度有显著影响.对函数F1~ F7和F14~ F23, COrSCA标准差数值较大, 说明COrSCA稳定性较弱, COSCA标准差较小, 说明COSCA鲁棒性较强.
由表 2可看出:与GWO、PSO、OBPSO算法相比, COSCA均获得了较好的收敛结果, 函数F1~ F4, F7中COSCA的精度远高于GWO、PSO、OBPSO算法, 同时COSCA标准差相对较小; COSCA算法对F9和F10结果较优, 对F11~ F13结果较差, 说明COSCA在求解多峰优化问题时性能上仍需加强.此外, COSCA对函数F15~ F23的结果较优, 在F21~ F23上获得的结果接近理论最优解.统计表 2中7种算法表现结果, COSCA在16个函数中结果最优, 在18个函数中标准差最小.在α=0.05的显著性水平下, 由Wilcoxon秩和检验结果可知, GWO、PSO、OBPSO对应结果分别为6/2/15、5/2/16、6/0/17.由表 3可知, COSCA的CPU时间优于OBSCA、GWO、OBPSO算法, 与SCA算法相当, 不及PSO算法.
综上所述, COSCA性能优于6种对比算法, 且COSCA具有收敛速度快、精度高、计算量小、鲁棒性较强等特点, 同时有效地协调了算法探索与开发能力, 能够很好地处理大部分问题.
3.2 精英个体比例分析精英个体比例pr的选取是精英混沌搜索策略的关键所在.由第2.3节可知, 精英混沌搜索策略可以增强算法的局部开发能力, 较大的pr会使算法产生早熟, 而pr取值过小则对算法的影响甚微, 因此本节通过仿真实验来检测pr取值对算法性能的影响.单峰函数可以很好地检验算法的局部搜索能力, 而多峰函数因其拥有大量局部极值被认为是最具挑战性的问题, 故选取函数F1~ F12进行实验, pr在[0, 0.4]区间内以0.1的间隔取5个值, r1策略见式(3), 其他参数不变, 用Friedman检验[18]实验结果的差异性.表 4给出了测试函数为30维时的平均精度、标准差、排序(Rank)以及检验的概率值P.由表 4可见, 测试函数对应的Friedman检测值P均小于0.05, 表明5种pr取值对应的算法结果之间存在显著差异.当参数pr取不同值时, COSCA在测试函数中结果相差较大, 因此精英混沌搜索策略对pr的取值较为敏感.在本文中, 当pr=0.1时, COSCA性能最优.
SCA中, 控制参数r1起着平衡算法开发与探索能力的作用, 较大的参数r1利于探索, 较小的参数r1利于开发.式(3)中, r1∈[aend, astart]非线性递减, 非线性调节系数η和astart、aend起着重要的作用, 本小节通过仿真实验对η和astart、aend取不同值时的算法性能进行分析.测试函数与3.2节相同, 精英个体比例pr=0.1, 其他参数不变, 实验结果通过Friedman进行检验.不同的η值对COSCA性能的影响结果比较如表 5所示, 4组不同astart、aend仿真结果如表 6所示.由表 5可知, η=1时, 效果最好.由表 6可知, astart=1, aend=0对应算法性能最优.
本节给出COSCA的时间复杂度.为了简化表达式, 在计算时间复杂度时, 将精英混沌策略中的混沌迭代部分记为Citer, 种群规模为N. COSCA的实验阶段使用了快排算法Qs, 最优条件下快排N个个体算法的时间复杂度为O(Nlog N), 最差条件下其时间复杂度为O(N2).
SCA时间复杂度为
(14) |
OBSCA时间复杂度为
(15) |
COSCA时间复杂度为
(16) |
(17) |
其中: n表示搜索空间维数, tmax表示最大迭代次数. COSCA与SCA时间复杂度差值为O((0.1N· n+OQS)·tmax+Citer), OBSCA与SCA时间复杂度差值为O((N· n+OQS)·tmax), Citer时间复杂度较低, 因此COSCA复杂度低于OBSCA.
仿真实验计算机配置: Intel(R) Core(TM) i5-6 200U CPU @2.30 GHz 2.40 GHz, 8 GB内存.算法CPU时间可从侧面反映该算法的时间复杂度, 将表 3中各算法的CPU时间累积, 得到PSO算法CPU时间最短(108.79 s), SCA的CPU时间次之(141.23 s), OBPSO算法与COSCA的CPU时间相仿, 分别为141.65 s和147.44 s, GWO算法CPU时间为149.43 s, OBSCA的CPU时间最长, 为223.71 s.
COSCA时间复杂度低于OBSCA、GWO算法, 与SCA、OBPSO算法时间复杂度相仿, 复杂度高于PSO算法. OBPSO作为PSO的改进算法, 复杂度与COSCA相仿, 而COSCA计算精度与稳定性均优于OBPSO, 因此COSCA优于PSO算法.
4 结论本文提出了一种基于对数非线性参数调整和精英混沌搜索策略的交替正余弦算法, 既拓展了算法的全局搜索能力, 又增强了算法的局部开发能力. 23个基准测试函数的实验结果表明: COSCA收敛性和稳定性方面优于SCA、OBSCA、GWO以及PSO算法; COSCA时间复杂度优于OBSCA, 与SCA、GWO相仿; PSO算法在时间复杂度上优于COSCA, 但收敛精度与稳定性方面劣于COSCA, 综合实验结果表明COSCA优于PSO算法.
[1] |
Kenndy J, Eberhart R C. Particle swarm optimization[C]. Proc of IEEE Int Conf on Neural Networks. Perth: IEEE, 1995: 1942–1948. https://ieeexplore.ieee.org/document/488968
|
[2] |
Mirjalili S, Mirjalili S M, Lewis A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69(7): 46-61. |
[3] |
Mirjalili S. SCA: A sine cosine algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016, 96: 120-133. DOI:10.1016/j.knosys.2015.12.022 |
[4] |
Elaziz M A, Oliva D, Xiong S. An improved opposition-based sine cosine algorithm for global optimization[J]. Expert Systems with Applications, 2017, 90: 484-500. DOI:10.1016/j.eswa.2017.07.043 |
[5] |
龙文, 伍铁斌. 协调探索和开发能力的改进灰狼优化算法[J]. 控制与决策, 2017, 32(10): 1749-1758. (Long W, Wu T B. Improved grey wolf optimization algorithm coordinating the ability of exploration and exploitation[J]. Control and Decision, 2017, 32(10): 1749-1758.) |
[6] |
Tizhoosh H R. Opposition-based learning: A new scheme for machine intelligence[C]. Proc of Int Conf on Computational Intelligence for Modeling Control and Automation. Vienna: IEEE, 2005: 695-701. https://www.researchgate.net/publication/4242497_Opposition-Based_Learning_A_New_Scheme_for_Machine_Intelligence
|
[7] |
龙文, 蔡绍洪, 焦建军, 等. 求解高维优化问题的混合灰狼优化算法[J]. 控制与决策, 2016, 31(11): 1991-1997. (Long W, Cai S H, Jiao J J, et al. Hybrid grey wolf optimization algorithm for high-dimensional optimization[J]. Control and Decision, 2016, 31(11): 1991-1997.) |
[8] |
Wang H, Wu Z, Rahnamayan S, et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences, 2011, 181(20): 4699-4714. DOI:10.1016/j.ins.2011.03.016 |
[9] |
Xu G, Yu G S. On convergence analysis of particle swarm optimization algorithm[J]. J of Computational and Applied Mathematics, 2018, 333: 65-73. DOI:10.1016/j.cam.2017.10.026 |
[10] |
Seif Z, Ahmadi M B. An opposition-based algorithm for function optimization[J]. Engineering Applications of Artificial Intelligence, 2015, 37: 293-306. DOI:10.1016/j.engappai.2014.09.009 |
[11] |
Gandomi A H, Yun G J, Yang X S, et al. Chaos-enhanced accelerated particle swarm optimization[J]. Commun Nonlinear Sci Numer Simulat, 2013, 18(2): 327-340. DOI:10.1016/j.cnsns.2012.07.017 |
[12] |
Yao X, Liu Y, Lin G. Evolutionary programming made faster[J]. IEEE Trans on Evolutionary Computation, 1999, 3(2): 82-102. DOI:10.1109/4235.771163 |
[13] |
Digalakis J, Margaritis K. On benchmarking functions for genetic algorithms[J]. Int J of Computational Mathematics, 2001, 77(4): 481-506. DOI:10.1080/00207160108805080 |
[14] |
Mirjalili S, Lewis A. S-shaped versus V-shaped transfer functions for binary particle swarm optimization[J]. Swarm & Evolutionary Computation, 2013, 9: 1-14. |
[15] |
Mirjalili S, Mirjalili S M, Yang X S. Binary bat algorithm[J]. Neural Computing & Applications, 2014, 25(3/4): 663-681. |
[16] |
Wang H, Liu H, Zeng S Y. Opposition-based particle swarm algorithm with Cauchy mutation[C]. IEEE Congress on Evolutionary Computation. Singapore: IEEE, 2007: 4750-4756. https://ieeexplore.ieee.org/document/4425095
|
[17] |
Zhou J, Yao X. Multi-population parallel self-adaptive differential artificial bee colony algorithm with application in large-scale service composition for cloud manufacturing[J]. Applied Soft Computing, 2017, 56: 179-397. |
[18] |
Pahnehkolaei S M A, Alfi A, Sadollah A, et al. Gradient-based water cycle algorithm with evaporation rate applied to chaos suppression[J]. Applied Soft Computing, 2016, 53: 420-440. |