算法贪婪bt

收稿日期:20190923;修回日期:20191105基金项目:贵州省科技计划项目重大专项项目(黔科合重大专项字[2018]3002,黔科合重大专项字[2016]3022);贵州省公共大数据重点实验室开放课题(2017BDKFJJ004);贵州省教育厅青年科技人才成长项目(黔科合KY字[2016]124);贵州大学培育项目(黔科合平台人才[2017]5788)作者简介:林杰(1995),女,贵州毕节人,硕士研究生,主要研究方向为进化计算、数据挖掘;何庆(1982),男(通信作者),贵州黔南人,副教授,博士,主要研究方向为大数据应用、进化计算(qhe@gzu.
edu.
cn).
混合策略改进正弦余弦算法林杰a,b,何庆a,b(贵州大学a.
大数据与信息工程学院;b.
贵州省公共大数据重点实验室,贵阳550025)摘要:为提高正弦余弦算法在求解函数优化问题的性能,提出混合策略改进正弦余弦算法.
首先,利用正切函数作为调节因子代替原本线性变化的参数,用于平衡算法的全局探索和局部开发;然后,引入权重系数,用于控制位置更新处个体上一代位置的影响力,有效提高算法开发能力和寻优速度;最后,构建逐维交叉学习策略,克服最优解无更新的缺点,对最优个体进行扰动更新,跳出局部最优,避免早熟收敛.
在不同维数的八个基准函数上进行仿真实验.
实验表明,该算法相对于其他群智能优化算法具有更高的寻优精度和收敛速度,相比于最新的正弦余弦改进算法,也表现出更好的收敛性能和稳定性.
关键词:正弦余弦算法;调节因子;权重系数;逐维交叉学习中图分类号:TP301文献标志码:A文章编号:10013695(2020)12019361206doi:10.
19734/j.
issn.
10013695.
2019.
09.
0542MixedstrategytoimprovesinecosinealgorithmLinJiea,b,HeQinga,b(a.
CollegeofBigData&InformationEngineering,b.
GuizhouProvincialKeyLaboratoryofPublicBigData,GuizhouUniversity,Guiyang550025,China)Abstract:Inordertoimprovetheperformanceofthesinecosinealgorithminsolvingthefunctionoptimizationproblem,thispaperproposedanimprovedsinecosinealgorithmformixedstrategy(MISCA).
Firstly,inordertobalancetheglobalexplorationandlocalexploitationofthealgorithm,itusedthetangentfunctionastheadjustmentfactorinsteadoftheoriginallinearvariationparameter.
Then,itintroducedtheweightcoefficienttocontroltheinfluenceofthepreviousgenerationpositionofthelocationupdate,andimprovedthealgorithmexploitationandoptimizationspeedeffectively.
Finally,itconstructedacrossdimensionalcrosslearningstrategytoovercometheshortcomingsoftheoptimalsolutionwithoutupdating,perturbtheoptimalindividual,avoidfallingintothelocaloptimum,andavoidprematureconvergence.
Thispapercarriedsimulationexperimentsoutoneightbenchmarkfunctionswithdifferentdimensions.
Theexperimentalresultsshowthattheproposedalgorithmhashigheroptimizationprecisionandconvergencespeedthanthecomparisonalgorithm,andshowsbetterconvergenceperformanceandstability.
Keywords:sinecosinealgorithm(SCA);adjustmentfactor;weightcoefficient;crossdimensionalcrosslearningcurvefunction0引言近年来,国内外学者已经提出了大量的群智能优化算法,如遗传算法[1]、蚁群算法[2]、粒子群算法[3]等经典算法,以及萤火虫算法(fireflyalgorithm,FA)[4]、蚁狮算法(antlionoptimizer,ALO)[5]、人工蜂群算法(artificialbeecolony,ABC)[6]、樽海鞘算法(slapswarmalgorithm,SSA)[7]等新型智能优化算法,为解决优化问题提供了新的解决思路,并且被广泛应用于多个相关领域,如旅行商问题(TSP)、二次分配问题、图像处理以及作业车间调度问题等.
正弦余弦算法(SCA)是2016年由Mirjalili[8]提出的新型元启发式优化算法.
SCA原理简单易于实现,利用正弦余弦函数的性质,通过迭代对算法进行全局搜索和局部开发,以达到寻优目的.
研究发现,在对基准函数优化时,SCA已被证明在收敛精度和速度方面优于粒子群算法、蝙蝠算法、萤火虫算法等[8],但与其他群智能优化算法相似,仍存在后期收敛速度慢、收敛精度较差、易陷入局部最优等问题.
针对以上问题,国内外学者展开了研究,提出一些改进算法.
比如Nenavath等人[9]将PSO算法的局部开发能力和SCA的全局探索能力相结合,提出新型混合算法SCAPSO,实验表明改进算法在对单峰测试函数寻优时,具有很高的开发能力和探索能力;文献[10]提出一种mSCA,首先通过反向学习策略生成反向解以跳出局部最优,再增加自适应系数,利用历史位置搜索扩大搜索空间并增加种群多样性;文献[11]将正弦余弦算法与差分算法融合,提出的SCADE使算法跳出局部最优的能力得到改善,在23个基准测试函数中进行了测试,验证了其收敛速度比SCA和DE更快,并将其应用到视觉跟踪;Gupta等人[12]提出ISCA,其关键是将交叉机制与贪婪选择融合以及个体反思学习策略和全局探索的整合,增强对搜索空间的开发力度,提供个体最优解,为种群最优解提供方向,并在CEC2014和CEC2017函数上验证了算法的鲁棒性和有效性;刘生建等人[13]提出一种具有学习机制的正弦余弦算法,引入精英反向学习策略和个体反思学习能力,改善算法早熟收敛现象.
然而,尽管现有研究对原始SCA的寻优效果有所提高,但SCA提出时间较短,目前对该算法的研究还较少,针对SCA易陷入局部最优、易早熟收敛、收敛精度较差等问题,还没有得到最有效的解决.
因此,本文提出混合策略改进正弦余弦算法.
首先为了使SCA的全局探索和局部开发得到更好的平衡,将第37卷第12期2020年12月计算机应用研究ApplicationResearchofComputersVol.
37No.
12Dec.
2020控制探索和开发的参数R1替换为非线性递减的调节因子;其次引入权重系数,使算法开发能力和寻优速度得到提高;最后提出逐维交叉学习策略对全局最优位置进行扰动更新,使算法避免陷入早熟收敛,增加种群多样性.
1正弦余弦算法正弦余弦算法[8]是近两年提出的基于正弦和余弦函数的数学特征的元启发式算法,通过正弦和余弦函数的变化来实现个体的更新,这与群智能优化算法有明显的不同.
在SCA中,假设在d维空间中,种群规模为N,在每次迭代中,第i个个体的位置更新方式为Xdi(t+1)=Xdi(t)+R1*sin(R2)*|R3Pdbest(t)-Xdi(t)|R41时,加大了最优解对当前解的影响力,反之,则减弱最优解对当前解的影响;R4是在正弦和余弦之间平均切换的概率.
R1sin(R2)或R1cos(R2)的绝对值在[1,2]时,算法进行全局探索;绝对值在[0,1]时算法进行局部开发.
为了能够平衡探索和开发,以此探索更多的空间,最终寻到全局最优,式(1)中正弦和余弦的范围使用式(2)通过迭代次数自适应地改变,表达式为R1=a-taT(2)其中:a是常数;t是当前迭代次数;T是最大迭代次数.
基本的SCA主要实现步骤如下:a)随机初始化N个种群的随机位置X,初始化种群规模N,最大迭代次数T,控制参数a;b)计算个体适应度,保存当前最优值;c)根据式(2)更新R1的值;d)若R4crvdotherwise(6)其中,cr是交叉概率,随着迭代次数的增加,自适应地调整交叉概率的大小.
算法前期交叉概率较大,有利于全局探索,后期交叉概率较小,有利于局部开发,加快寻优速度,表达式为cr=1-0.
5*lg(tT)(7)本文针对最优个体位置提出逐维交叉学习策略,虽然有效避免了各维度间信息相互干扰的情况,能够摆脱局部最优,防止算法早熟收敛,但是不能保证更新后的位置优于原最优位置,所以随后利用了贪婪原则判断是否更新最优个体位置,即当更新后的位置优于原位置,才进行位置更新,否则保留原位置.
vd=pdf(pd)24MISCA的实现综上所述,混合策略改进正弦余弦算法在原始SCA的基础上进行改进,通过引入调节因子代替原本线性变化的参数R1,同时利用权重系数,用于平衡算法的全局探索和局部开发,在增强种群多样性的同时,有效提高算法开发能力;最后,构建逐维交叉学习策略,克服最优解无更新的缺点,对最优个体进行扰动更新,利用最优个体的引导作用跳出局部最优,有效提高算法的收敛速度和收敛精度.
结合2.
1~2.
3节的步骤和结论,本文算法的主要流程如图1所示.
25MISCA时间复杂度分析时间复杂度可以间接反映算法的运行效率.
在原始SCA中,假设参数初始化(种群规模N、空间维度n、控制常数a)所需执行时间为ε1,产生均匀分布随机数的时间为ε2,适应度函数的时间为f(n),保存最优位置的时间为ε3,则算法初始化的时间复杂度为·3163·第12期林杰,等:混合策略改进正弦余弦算法O(ε1+N(n*ε2+f(n))+ε3)=O(n+f(n))(9)设更新控制参数R1的时间为ε4,产生随机数R2、R3和R4的时间均为ε5,个体每一维选择位置更新方式的时间为ε6,个体每一维位置更新方式的时间为ε7,所以主循环部分的时间复杂度为O(ε3+ε4+N*n(3ε5+ε6+ε7)+Nf(n))=O(n+f(n))(10)原始SCA的求解每一代最优解的时间复杂度为T(n)=O(n+f(n))+O(n+f(n))=O(n+f(n))(11)同理,在MISCA中,算法的初始化部分和原始SCA一致,所以MISCA在初始化阶段的时间复杂度与原始SCA相同,其时间复杂度为O(ε1+N(n*ε2+f(n))+ε3)=O(n+f(n))(12)由图1可知,在主循环部分,设更新调节因子和自适应权重系数的时间分别为δ1和δ2,选择位置更新方式的时间为δ3,每个个体每一维的位置更新执行时间为δ4,交叉概率更新的时间为δ5,每一维随机产生新位置的时间为δ6,比较新旧个体适应度值的时间为δ7,保存最优个体维度的时间为δ8,所以MISCA循环部分的时间复杂度为O(δ1+δ2+N*n(3ε5+δ3+δ4)+Nf(n)+Nε3+n(δ5+δ6+δ7)+f(n)+δ7+δ8)=O(n+f(n))(13)基于上述分析,本文改进算法MISCA求解每一代最优解的时间复杂度为T(n)=O(n+f(n))+O(n+f(n))=O(n+f(n))(14)综上所述,MISCA与原始SCA相比,时间复杂度没有发生改变,算法运行效率没有降低,本文算法的改进没有对最终的复杂度有负面影响.
MISCA和原始SCA的时间复杂度取决于计算适应度函数的时间复杂度f(n),当f(n)比n高阶时,算法执行O(f(n)),当f(n)与n同阶或低阶时,算法复杂度为O(n).
3实验仿真与分析31实验环境和参数设置本文采用MATLABR2014a进行实验,运行环境为64位Windows10操作系统,处理器类型为IntelCorei57500.
仿真程序中种群规模N=30,最大迭代次数T=500,调节系数β=0.
05,权重因子μ=0.
5,常数a=2.
为降低偶然性,对每个测试函数均进行30次独立实验.
为验证本文算法的有效性,引入八个经典基准测试函数进行测试,如表1所示,其中F1~F5是连续单峰函数,局部最优即全局最优,常用来检测算法的收敛速度和收敛精度;F6~F8是多峰函数,具有多个局部最优点,可评估算法跳出局部最优并寻到全局最优的能力.
同时,测试函数的维度对算法性能有明显影响,所以表1中测试函数维度从10维到200维,从低维、高维过渡到超高维,以更加全面地验证算法性能.
本文对算法的实验仿真主要包括三个部分:a)将蚁狮算法(ALO)[5]、樽海鞘算法(SSA)[7]、原始SCA[8]与MISCA作比较,验证本文改进算法的有效性,其中ALO、SSA、SCA、MISCA的共有参数统一设置,ALO和SSA的其他参数设置与提出文献一致.
b)对不同改进策略的改进算法进行独立运行测试,证明不同改进策略的有效性以及不同改进策略对算法寻优的影响.
c)通过与参考文献中的改进SCA比较,证明MISCA相对于其他新的改进SCA仍具竞争性.
表1测试函数Tab.
1Testfunctions编号函数名维度定义域理论值F1sphere30[-100,100]0F2Schwefel2.
2250[-10,10]0F3Schwefel1.
2200[-100,100]0F4Schwefel2.
2110[-100,100]0F5Rosenbrock30[-30,30]0F6Rastrigin50[-5.
12,5.
12]0F7Ackley30[-30,30]0F8Griewank100[-600,600]032验证本文算法的有效性为验证MISCA的有效性,从最大值、最小值、平均值和标准差四个方面来衡量算法的优劣,测试结果如表2所示.
为了更直观地反映MISCA的性能,图2(a)~(h)给出了算法对八个测试函数的平均收敛曲线.
为便于观察,对适应度值取10的对数.
表2算法寻优性能对比Tab.
2Algorithmoptimizationperformancecomparison函数算法最大值最小值平均值标准差F1ALO6.
07E-031.
22E-032.
35E-039.
99E-04SSA8.
51E-082.
13E-085.
38E-081.
76E-08SCA4.
59E+027.
33E+004.
32E+018.
42E+01MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F2ALO2.
75E+031.
59E+022.
83E+024.
67E+02SSA1.
91E+019.
59E+001.
27E+012.
65E+00SCA1.
79E-015.
17E-031.
08E-016.
09E-02MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F3ALO6.
88E+053.
39E+054.
27E+058.
34E+04SSA5.
84E+052.
22E+053.
15E+059.
35E+04SCA1.
60E+061.
05E+061.
22E+061.
47E+05MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F4ALO2.
36E-021.
64E-035.
44E-035.
66E-03SSA4.
91E-042.
27E-054.
54E-058.
50E-05SCA1.
73E-027.
16E-042.
53E-033.
03E-03MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F5ALO1.
65E-021.
61E-035.
20E-033.
81E-03SSA9.
29E-036.
14E-043.
01E-032.
41E-03SCA2.
73E-031.
32E-049.
30E-047.
36E-04MISCA6.
43E-053.
10E-062.
71E-052.
01E-05F6ALO2.
83E+021.
51E+021.
75E+023.
04E+01SSA1.
70E+029.
65E+011.
19E+021.
67E+01SCA2.
42E+021.
16E+021.
51E+023.
05E+01MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F7ALO1.
13E+014.
55E+007.
30E+002.
03E+00SSA5.
68E+002.
81E+003.
45E+007.
33E-01SCA2.
04E+012.
02E+012.
03E+013.
55E-02MISCA8.
88E-168.
88E-168.
88E-161.
00E-31F8ALO8.
77E+013.
83E+015.
35E+011.
18E+01SSA2.
98E+011.
48E+011.
83E+013.
33E+00SCA2.
80E+021.
32E+021.
81E+023.
74E+01MISCA0.
00E+000.
00E+000.
00E+000.
00E+00·4163·计算机应用研究第37卷从表2可知,MISCA在不同维度下针对测试函数的寻优精度相较于原始SCA均有明显提高.
在不同维度下的函数F1~F4、F6和F8均寻到了理论值0;对于没有寻到理论值的函数F5和F7,求解的结果精度相对于SCA也有所提高,例如在求解Ackley函数时,MISCA和SCA标准差相差29个数量级.
另外,ALO和SSA在八个测试函数中均未找到最优解,而MISCA即便是寻优结果较差的函数也比ALO和SSA要好.
例如函数F5,ALO和SSA与本文算法的最优值分别相差1E-03和1E-02;对F7寻优时,ALO和SSA与本文算法的最优值均相差16个数量级,表明与另外两种算法相比MISCA性能较优越.
为更加全面分析算法性能,下面将从MISCA算法寻优结果的稳定性和多样性两个方面进行讨论.
首先从算法的稳定性分析,由表2标准差可知,无论是在低高维(F1)、中高维(F2)还是超高维(F3)的条件下,MISCA的寻优结果都很稳定,而且均寻到理论最优值;对于多峰高维函数,例如函数F6和F8,标准差均为0;对于函数F5和F7,相对于ALO、SSA、SCA三种算法,MISCA虽然没有寻到理论值,但算法的标准差与其他算法最小相差1E-32,证明了MISCA具有较强的鲁棒性.
其次,从多样性的角度分析,ALO、SSA、SCA和MISCA的平均收敛曲线分布如图2所示.
以图2(a)(c)(f)(h)为例,由图可知ALO、SSA和SCA在算法迭代到300次左右,解的分布仍过于局限,多样性较差,随着迭代次数增加,解的分布仍保持在较小的范围,且解的质量较差;而MISCA在整个迭代期间,解的分布范围较广,保持着较好的多样性,表明MISCA改进策略的有效性.
33验证改进策略的有效性为方便比较,算法参数设置与3.
2节相同,为比较不同改进策略的有效性和不同改进策略对MISCA的影响,将MISCA与将参数R1改进为曲线调节因子的正弦余弦算法(ASCA)、引入自适应权重系数的正弦余弦算法(WSCA),以及加入逐维交叉学习策略的正弦余弦算法(CSCA)作比较测试,结果如表3所示.
表3不同改进策略的算法的比较Tab.
3Comparisonofalgorithmsfordifferentstrategies函数算法最大值最小值平均值标准差F1WSCA0.
00E+000.
00E+000.
00E+000.
00E+00ASCA5.
21E-091.
64E-121.
93E-091.
83E-09CSCA0.
00E+000.
00E+000.
00E+000.
00E+00MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F2WSCA0.
00E+000.
00E+000.
00E+000.
00E+00ASCA1.
68E-051.
80E-076.
75E-064.
73E-06CSCA0.
00E+000.
00E+000.
00E+000.
00E+00MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F3WSCA0.
00E+000.
00E+000.
00E+000.
00E+00ASCA1.
16E+067.
57E+051.
06E+069.
53E+04CSCA0.
00E+000.
00E+000.
00E+000.
00E+00MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F4WSCA0.
00E+000.
00E+000.
00E+000.
00E+00ASCA1.
26E-141.
56E-173.
29E-154.
13E-15CSCA0.
00E+000.
00E+000.
00E+000.
00E+00MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F5WSCA9.
40E-051.
25E-055.
95E-052.
51E-05ASCA8.
08E-043.
62E-053.
00E-042.
07E-04CSCA2.
43E-041.
99E-059.
88E-054.
53E-05MISCA6.
43E-053.
10E-062.
71E-052.
01E-05F6WSCA0.
00E+000.
00E+000.
00E+000.
00E+00ASCA5.
58E+012.
22E-041.
81E+012.
07E+01CSCA0.
00E+000.
00E+000.
00E+000.
00E+00MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F7WSCA8.
88E-168.
88E-168.
88E-161.
00E-31ASCA9.
92E-061.
43E-074.
65E-063.
17E-06CSCA8.
88E-168.
88E-168.
88E-161.
00E-31MISCA8.
88E-168.
88E-168.
88E-161.
00E-31F8WSCA0.
00E+000.
00E+000.
00E+000.
00E+00ASCA5.
31E+012.
69E+003.
02E+011.
56E+01CSCA0.
00E+000.
00E+000.
00E+000.
00E+00MISCA0.
00E+000.
00E+000.
00E+000.
00E+00首先,对于表3中的最小值和平均值,可以反映出算法的寻优能力和收敛精度.
八个测试函数,除了F5和F7,WSCA和CSCA均达到理论值0,证明了这两种改进策略的有效性,但从图3可直观看出,虽然两种改进策略均能寻到理论值,但WSCA具有更高的收敛速度和精度,如图3(d),WSCA收敛于77代,CSCA收敛于499代,是WSCA的70倍,与WSCA相比,收敛速度较慢,证明权重系数对个体移动方向和大小的影响力度与算法的收敛速度具有较强的相关性.
其次,从表3的标准差可以看出不同改进策略算法的稳定性.
WSCA和CSCA的标准差基本都为0,对于标准差不为0的两个函数F5和F7,WSCA和CSCA的标准差与SCA的标准差相比分别都是相差1E-01和1E-29,说明了WSCA和CSCA两种改进策略的有效性;ASCA尽管没有函数寻到最优,但由于加入了调节因子,改变了参数R1的收敛方式,增加算法在前期全局探索的时间,并让算法在后期快速收敛,所以ASCA的寻优精度和速度相较于SCA均有所提升,例如在多维高峰函数F7中,ASCA与SCA相差7个数量级.
最后,结合表3和图3可看出对于三个改进策略,在位置更新处引入权重系数的WSCA的寻优效果最为明显,改进效果次之的是CSCA,ASCA改进的效果相对于其他两个不是很明显,但是也比SCA的收敛效果好,所以仍具一定竞争性.
·5163·第12期林杰,等:混合策略改进正弦余弦算法综上所述,ASCA用非线性调节因子取代原始SCA中线性递减函数,调节因子在算法迭代前期下降缓慢,给全局探索足够时间,在迭代后期迅速下降收敛,加快算法开发和收敛速度,通过迭代次数的增加使全局搜索的局部开发得到了更好的平衡;WSCA引入权重系数,寻优效果相对其他两个改进策略最有优势,因为在权重系数随迭代系数改变时,位置更新处上一代个体的权重也随迭代次数的变化而变化,即改变位置更新步长,增加算法种群多样性的同时增强了算法全局探索能力;CSCA,通过引入逐维交叉学习策略,强调最优个体的引导作用,使算法能够摆脱局部最优的约束,提高算法收敛精度;将三种改进策略混合在一起,充分发挥算法中和策略的优势,使得MISCA的整体寻优能力和算法收敛精度均优于SCA.
34与其他改进SCA性能对比为进一步验证MISCA的性能,将引用文献[9,12]的改进算法进行比较.
为方便进行比较,三者设置相同的参数,其中种群规模为30,最大迭代次数为1000次,对表1中的八个测试函数独立运行30次,引用SCAPSO[9]和ISCA[12]算法中的数据,比较最大值、中值、平均值和标准差,数据对比结果如表4所示.
从表4中的实验数据可以看出,四个指标中,当SCAPSO和ISCA对测试函数寻优寻到最优值是理论值时,MISCA同样能够对相应的测试函数寻到理论值;另外,MISCA与SCAPSO基本上都找到理论值,没有找到理论最优值的,如F5,MISCA的寻优精度均高于其他两种对比算法;MISCA对函数F1~F4、F6和F8的四个评估性能均找到理论值,而ISCA找到理论值的测试函数个数相对MISCA较少,仅函数F6和F8找到最优,其余函数虽然寻优精度有所提升,但最优结果与理论值仍有一定差距,如函数F1,MISCA的标准差为0,而ISCA的标准差为9.
62E-58.
通过八个测试函数的寻优结果证明MISCA相对于SCAPSO和ISCA具有更佳的寻优能力.
综上所述,本文MISCA相对于目前较新的改进SCA,仍然具有一定的竞争力,在求解优化函数时能够表现出良好的搜索性能.
算法的平均值和标准差在30次独立运行的算法中没有独立比较每次的运行结果.
文献[14]提出,对于算法性能的评估,应进行统计检验.
也就是说,仅基于平均值和标准差来评价算法的优劣是不充分的.
需要进行统计检验来验证所提算法与其他算法相比具有竞争性.
为了判断MISCA每次结果是否在统计上显著地优于其他算法结果,采用Wilcoxon统计检验在5%的显著性水平下进行.
表4与改进SCA对比结果Tab.
4ComparisonresultswithimprovedSCA函数算法最大值中值平均值标准差F1SCAPSO0.
00E+000.
00E+000.
00E+000.
00E+00ISCA5.
10E-571.
37E-592.
01E-589.
62E-58MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F2SCAPSO0.
00E+000.
00E+000.
00E+000.
00E+00ISCA1.
22E-357.
21E-371.
87E-362.
52E-36MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F3SCAPSO0.
00E+000.
00E+000.
00E+000.
00E+00ISCA6.
09E-032.
75E-062.
52E-041.
11E-03MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F4SCAPSO0.
00E+000.
00E+000.
00E+000.
00E+00ISCA9.
93E-158.
80E-162.
07E-152.
64E-15MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F5SCAPSO6.
36E+006.
30E+006.
22E+002.
04E-01ISCA2.
71E+012.
61E+012.
61E+014.
10E-01MISCA1.
10E-041.
57E-052.
46E-052.
89E-05F6SCAPSO0.
00E+000.
00E+000.
00E+000.
00E+00ISCA0.
00E+000.
00E+000.
00E+000.
00E+00MISCA0.
00E+000.
00E+000.
00E+000.
00E+00F7SCAPSO8.
88E-168.
88E-168.
88E-160.
00E+00ISCA8.
88E-168.
88E-168.
88E-164.
01E-31MISCA8.
88E-168.
88E-168.
88E-160.
00E+00F8SCAPSO0.
00E+000.
00E+000.
00E+000.
00E+00ISCA0.
00E+000.
00E+000.
00E+000.
00E+00MISCA0.
00E+000.
00E+000.
00E+000.
00E+00表5中给出了八个测试函数的MISCA和其他算法的Wilcoxon秩及检验中计算的p值.
比如最佳算法是MISCA,则在MISCA/ALO、MISCA/SSA、MISCA/SCA、MISCA/WSCA、MISCA/ASCA、MISCA/CSCA之间进行成对比较.
因为最佳算法无法与自身进行比较,所以对于每个函数中的最佳算法标记为N/A,表示不适用,这意味着对应的算法在秩和检验中没有统计数据与自身比较.
根据文献[14]可知,秩和检验的p值小于0.
05的可以被认为是拒绝零假设的有力验证.
表5测试函数Wilcoxon秩和检验的p值Tab.
5pvalueoftestfunctionWilcoxonranksumtest函数ALOSSASCAWSCAASCACSCAF11.
21E-121.
21E-121.
21E-12N/A1.
21E-12N/AF21.
21E-121.
21E-121.
21E-12N/A1.
21E-12N/AF31.
21E-121.
21E-121.
21E-12N/A1.
21E-12N/AF41.
21E-121.
21E-121.
21E-12N/A1.
21E-12N/AF53.
02E-113.
02E-113.
02E-114.
42E-069.
92E-119.
76E-10F61.
21E-121.
21E-121.
21E-12N/A1.
21E-12N/AF71.
21E-121.
21E-121.
21E-12N/A1.
21E-12N/AF81.
21E-121.
21E-121.
21E-12N/A1.
21E-12N/A根据表5中的结果,WSCA和CSCA中,除函数F5外,其余测试函数的p值均值N/A,这说明除F5外,其余函数在MISCA、WSCA和CSCA中都找到了理论值.
MISCA的p值全部·6163·计算机应用研究第37卷小于0.
05,说明了本文MISCA的优越性在统计上是显著的,即认为MISCA相对于其他对比算法具有更好的寻优能力.
4结束语本文针对SCA易陷入局部最优、易早熟收敛、收敛精度较差等问题进行三点改进.
首先,对SCA中的参数R1的线性递减方式改为非线性递减的调节因子,平衡算法的全局探索和局部开发能力;其次,引入权重系数,有效提高算法开发能力和寻优速度;最后引入逐维交叉学习策略对全局最优位置进行扰动更新,增加种群多样性,摆脱局部最优.
本文算法与两种群智能优化算法、不同改进策略的算法以及两种最新的改进SCA进行了实验仿真,结果表明本文MISCA寻优精度和寻优速度均有大幅度提升,并且相对于其他改进算法仍具有明显竞争力,证明了MISCA在求解优化函数时具有更好的优化性能.
参考文献:[1]王劲孚,张华,谭鑫,等.
基于遗传算法的不规则场地总平面布置研究[J].
工程建设与设计,2019(15):35.
(WangJinfu,ZhangHua,TanXin,etal.
Researchongeneralayoutplanningofirregularspacebasedongeneticalgorithm[J].
Construction&DesignforEngineering,2019(15):35.
)[2]熊沂铖,王栋.
基于蚁群算法的车辆路径问题研究[J].
信息技术,2019,43(7):1517.
(XiongYicheng,WangDong.
Vehicleroutingproblembasedonantcolonyalgorithm[J].
InformationTechnology,2019,43(7):1517.
)[3]王丽,王威,陈博.
改进的粒子群优化正交匹配追踪重构算法[J].
小型微型计算机系统,2019,40(8):17551759.
(WangLi,WangWei,ChenBo.
Improvedparticleswarmoptimizationorthogonalmatchingpursuitreconstructionalgorithm[J].
JournalofChineseComputerSystems,2019,40(8):17551759.
)[4]张立毅,高杨,费腾.
求解旅行商问题的萤火虫遗传算法[J].
计算机工程与设计,2019,40(7):19391944.
(ZhangLiyi,GaoYang,FeiTeng.
Fireflygeneticalgorithmfortravelingsalesmanproblem[J].
ComputerEngineeringandDesign,2019,40(7):19391944.
)[5]尹洪红,杨晓文,刘佳鸣,等.
一种基于蚁狮优化的极限学习机[J].
计算机应用与软件,2019,36(8):230234.
(YinHonghong,YangXiaowen,LiuJiaming,etal.
Anextremelearningmachinebasedonantlionoptimization[J].
ComputerApplicationsandSoftware,2019,36(8):230234.
)[6]马劲松.
基于改进人工蜂群算法的认知无线电频谱分配[J].
电信工程技术与标准化,2019,32(8):8287.
(MaJinsong.
Spectrumallocationbasedonanimprovedartificialbeecolonyalgorithmincognitiveradiosystem[J].
TelecomEngineeringTechnicsandStandardization,2019,32(8):8287.
)[7]张达敏,陈忠云,辛梓芸,等.
基于疯狂自适应的樽海鞘群算法[J].
控制与决策,2020,35(9):21122120.
(ZhangDamin,ChenZhongyun,XinZhiyun,etal.
Basedoncrazyadaptiveslapswarmalgorithm[J].
ControlandDecision,2020,35(9):21122120.
)[8]MirjaliliS.
SCA:asinecosinealgorithmforsolvingoptimizationproblems[J].
KnowledgeBasedSystems,2016,96:120133.
[9]NenavathH,JatothDRK,DasDS.
Asynergyofthesinecosinealgorithmandparticleswarmoptimizerforimprovedglobaloptimizationandobjecttracking[J].
SwarmandEvolutionaryComputation,2018,43:130.
[10]GuptaS,DeepK.
Ahybridselfadaptivesinecosinealgorithmwithoppositionbasedlearning[J].
ExpertSystemswithApplications,2019,119:210230.
[11]NenavathH,JatothRK.
Hybridizingsinecosinealgorithmwithdifferentialevolutionforglobaloptimizationandobjecttracking[J].
AppliedSoftComputing,2018,62:10191043.
[12]GuptaS,DeepK.
Improvedsinecosinealgorithmwithcrossoverschemeforglobaloptimization[J].
KnowledgeBasedSystems,2019,165:374406.
[13]刘生建,杨艳,周永权.
一种群体智能算法———狮群算法[J].
模式识别与人工智能,2018,31(5):431441.
(LiuShengjian,YangYan,ZhouYongquan.
Aswarmintelligencealgorithmlionswarmoptimization[J].
PatternRecognitionandArtificialIntelligence,2018,31(5):431441.
)[14]DerracJ,GarcíaS,MolinaD,etal.
Apracticaltutorialontheuseofnonparametricstatisticaltestsasamethodologyforcomparingevolutionaryandswarmintelligencealgorithms[J].
SwarmandEvolutionaryComputation,2011,1(1):318.
(上接第3602页)[4]TantipathananandhC,BergerWolfT,KempeD.
Aframeworkforcommunityidentificationindynamicsocialnetworks[C]//Procofthe13thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.
NewYork:ACMPress,2007:717726.
[5]HuangS,LeeD.
Exploringstructuralfeaturesinpredictingsocialnetworkevolution[C]//Procofthe10thInternationalConferenceonMachineLearningandApplications.
Piscataway,NJ:IEEEPress,2011:269274.
[6]TakaffoliM,FagnanJ,SangiF,etal.
Trackingchangesindynamicinformationnetworks[C]//ProcofInternationalConferenceonComputationalAspectsofSocialNetworks.
Piscataway,NJ:IEEEPress,2011:94101.
[7]IlhanN,güdücüIG.
Communityeventpredictionindynamicsocialnetworks[C]//Procofthe12thInternationalConferenceonMachineLearningandApplications.
Piscataway,NJ:IEEEPress,2013:191196.
[8]I·lhanN,gˇüdücü爦G.
Predictingcommunityevolutionbasedontimeseriesmodeling[C]//ProcofIEEE/ACMInternationalConferenceonAdvancesinSocialNetworksAnalysisandMining.
NewYork:ACMPress,2015:15091516.
[9]GliwaB,ZygmuntA,ByrskiA.
Graphicalanalysisofsocialgroupdynamics[C]//Procofthe4thInternationalConferenceonComputationalAspectsofSocialNetworks.
Piscataway,NJ:IEEEPress,2012:4146.
[10]GliwaB,BródkaP,ZygmuntA,etal.
Differentapproachestocommunityevolutionpredictioninblogosphere[C]//ProcofACMASONAM.
NewYork:ACMPress,2013:12911298.
[11]SaganowskiS,GliwaB,BródkaP,etal.
Predictingcommunityevolutioninsocialnetworks[J].
Entropy,2015,17(5):30533096.
[12]BródkaP,SaganowskiS,KazienkoP.
GED:themethodforgroupevolutiondiscoveryinsocialnetworks[J].
SocialNetworkAnalysisandMining,2013,3(1):114.
[13]PavlopoulouMEG,TzortzisG,VogiatzisD,etal.
Predictingtheevolutionofcommunitiesinsocialnetworksusingstructuralandtemporalfeatures[C]//Procofthe12thInternationalWorkshoponSematicandSocialMediaAdaptationandPersonalization.
Piscataway,NJ:IEEEPress,2017:4045.
[14]何伟,胡学钢,李磊,等.
社团演化特征构造及预测[J].
小型微型计算机系统,2018,39(5):10161020.
(HeWei,HuXuegang,LiLei,etal.
Featureconstructionandpredictionofcommunityevolution[J].
JournalofChineseComputerSystems,2018,39(5):10161020.
)[15]BlondelVD,GuillaumeJ,LambiotteR,etal.
Fastunfoldingofcommunitiesinlargenetworks[EB/OL].
(20080725).
http://doi.
org/10.
1088/17425468/2008/10/p10008.
[16]BródkaP,KazienkoP,KooszczykB.
Predictinggroupevolutioninthesocialnetwork[C]//Procofthe4thInternationalConferenceonSocialInformatics.
Berlin:SpringerVerlag,2012:5467.
·7163·第12期林杰,等:混合策略改进正弦余弦算法