基于布朗运动与梯度信息的交替优化算法

doi:10.11772/j.issn.1001-9081.2021050839

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (7): 2139-2145.DOI: 10.11772/j.issn.1001-9081.2021050839

• 先进计算 • 上一篇

基于布朗运动与梯度信息的交替优化算法

沙林秀, 聂凡(), 高倩, 孟号

西安石油大学电子工程学院，西安 710065

收稿日期:2021-05-21 修回日期:2021-09-29 接受日期:2021-09-30 发布日期:2021-09-29 出版日期:2022-07-10
通讯作者: 聂凡
作者简介:沙林秀（1978—），女，陕西安康人，副教授，博士，主要研究方向：智能钻井控制
高倩（1995—），女，陕西渭南人，硕士研究生，主要研究方向：虚拟现实
孟号（1993—），男，安徽淮北人，硕士研究生，主要研究方向：检测系统、图形处理。
基金资助:
陕西省科技攻关重点项目(2020GY?046);西安石油大学研究生创新与实践能力培养计划项目(YCS21212115)

Alternately optimizing algorithm based on Brownian movement and gradient information

Linxiu SHA, Fan NIE(), Qian GAO, Hao MENG

School of Electronic Engineering，Xi’an Shiyou University，Xi’an Shaanxi 710065，China

Received:2021-05-21 Revised:2021-09-29 Accepted:2021-09-30 Online:2021-09-29 Published:2022-07-10
Contact: Fan NIE
About author:SHA Linxiu， born in 1978， Ph. D.， associate professor. Her research interests include intelligent drilling control.
GAO Qian， born in 1995， M. S. candidate. Her research interests include virtual reality.
MENG Hao， born in 1993， M. S. candidate. His research interests include detection system， graphic processing.
Supported by:
Key Science and Technology Project of Shaanxi Province(2020GY-046);Postgraduate Innovation and Practical Ability Training Program of Xi’an Shiyou University(YCS21212115)

摘要/Abstract

摘要：

针对群智能优化算法在优化过程中容易陷入局部最优、种群多样性低以及高维函数优化困难的问题，提出一种基于布朗运动与梯度信息的交替优化算法（AOABG）。首先，采用全局、局部搜索交替的寻优策略，即在有变优趋势的范围内切换为局部搜索，有变劣趋势的范围内切换为全局搜索；然后，局部搜索引入基于梯度信息的均匀分布概率的随机游走，全局搜索引入基于最优解位置的布朗运动的随机游走。将所提出的AOABG与近三年的哈里斯鹰优化算法（HHO）、麻雀搜索算法（SSA）、特种部队算法（SFA）在10个测试函数上对比。当测试函数维数为2、10时，AOABG在10个测试函数上的100次最终优化结果的均值与均方差均优于HHO、SSA与SFA。当测试函数为30维时，除了HHO在Levy函数上的表现优于AOABG（两者优化结果均值处于同一数量级）外，AOABG在其他9个测试函数上表现最好，与上述算法相比，优化结果均值提升了4.64%~94.89%。实验结果表明，AOABG在高维函数优化中收敛速度更快、稳定性更好、精度更高。

关键词: 交替寻优策略, 高维函数优化, 收敛速度, 布朗运动, 梯度信息

Abstract:

Aiming at the problems that swarm intelligence optimization algorithms are easy to fall into local optimum as well as have low population diversity in the optimization process and are difficult to optimize high-dimensional functions， an Alternately Optimizing Algorithm based on Brownian-movement and Gradient-information （AOABG） was proposed. First， a global and local alternately optimizing strategy was used in the proposed algorithm， which means the local search was switched in the range of getting better and the global search was switched in the range of getting worse. Then， the random walk of uniform distribution probability based on gradient information was introduced into local search， and the random walk of Brownian motion based on optimal solution position was introduced into global search. The proposed AOABG algorithm was compared with Harris Hawk Optimization （HHO）， Sparrow Search Algorithm （SSA） and Special Forces Algorithm （SFA） on 10 test functions. When the dimension of test function is 2 and 10， the mean value and standard deviation of AOABG’s 100 final optimization results on 10 test functions are better than those of HHO， SSA and SFA. When the test function is 30-dimensional， except for Levy function where HHO performs better than AOABG but the mean value of the two is in the same order of magnitude， AOABG performs best on the other nine test functions with an increase of 4.64%-94.89% in the average optimization results compared with the above algorithms. Experimental results show that AOABG algorithm has faster convergence speed， better stability and higher accuracy in high-dimensional function optimization.

Key words: alternately optimizing strategy, high-dimensional function optimization, convergence rate, Brownian movement, gradient information

中图分类号:

TP301.6

沙林秀, 聂凡, 高倩, 孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 计算机应用, 2022, 42(7): 2139-2145.

Linxiu SHA, Fan NIE, Qian GAO, Hao MENG. Alternately optimizing algorithm based on Brownian movement and gradient information[J]. Journal of Computer Applications, 2022, 42(7): 2139-2145.

图/表 11

图1 交替寻优策略流程

Fig.1 Flowchart of alternately optimizing strategy

图2 全局搜索策略（二维）

Fig.2 Global search strategy in two dimension

图3 全局搜索策略下二维空间搜索轨迹与点分布

Fig.3 Search paths and points distributions in two-dimensional space under global search strategy

图4 AOABG的流程

Fig.4 Flowchart of AOABG

表1 算法参数设置

Tab.1 Parameter settings of algorithms

算法	参数	值
HHO	无	无
SSA	警惕阈值 $S T$	$0.8$
	生产者数量 $N P$	$0.3 × n$
	预警数量 $S D$	$0.1 × n$
SFA	$t v 1$	$0.5$
	$t v 2$	$0.3$
	$p 0$	$0.25$
	$w 0$	$0.75$
AOABG	局部搜索步长 $α$	$0.01 × r a n g e$
	全局搜索步长 $β$	$0.05 × r a n g e$
	布朗运动方差系数 $k$	$1$

表1 算法参数设置

Tab.1 Parameter settings of algorithms

算法	参数	值
HHO	无	无
SSA	警惕阈值 $S T$	$0.8$
	生产者数量 $N P$	$0.3 × n$
	预警数量 $S D$	$0.1 × n$
SFA	$t v 1$	$0.5$
	$t v 2$	$0.3$
	$p 0$	$0.25$
	$w 0$	$0.75$
AOABG	局部搜索步长 $α$	$0.01 × r a n g e$
	全局搜索步长 $β$	$0.05 × r a n g e$
	布朗运动方差系数 $k$	$1$

表2 测试函数

Tab.2 Test functions

函数	函数名称	原搜索空间	最优值
F₁（X）	Ackley	$[- 32,32] s$	$0$
F₂（X）	Alpine	$[- 10,10] s$	$0$
F₃（X）	Rastrigin	$[- 5.12,5.12] s$	$0$
F₄（X）	Levy	$[- 10,10] s$	$0$
F₅（X）	Girewank	$[- 600,600] s$	$0$
F₆（X）	Salomon	$[- 100,100] s$	$0$
F₇（X）	Sphere	$[- 100,100] s$	$0$
F₈（X）	Rosenbrock	$[- 30,30] s$	$0$
F₉（X）	Schwefel P2.22	$[- 10,10] s$	$0$
F₁₀（X）	Sum of different power	$[- 1,1] s$	$0$

表2 测试函数

Tab.2 Test functions

函数	函数名称	原搜索空间	最优值
F₁（X）	Ackley	$[- 32,32] s$	$0$
F₂（X）	Alpine	$[- 10,10] s$	$0$
F₃（X）	Rastrigin	$[- 5.12,5.12] s$	$0$
F₄（X）	Levy	$[- 10,10] s$	$0$
F₅（X）	Girewank	$[- 600,600] s$	$0$
F₆（X）	Salomon	$[- 100,100] s$	$0$
F₇（X）	Sphere	$[- 100,100] s$	$0$
F₈（X）	Rosenbrock	$[- 30,30] s$	$0$
F₉（X）	Schwefel P2.22	$[- 10,10] s$	$0$
F₁₀（X）	Sum of different power	$[- 1,1] s$	$0$

表3 各算法优化结果（s=2，n=10）

Tab.3 Optimization results of different algorithms （s=2，n=10）

测试函数	HHO		SFA		SSA		AOABG
测试函数	均值	均方差	均值	均方差	均值	均方差	均值	均方差
F₁	1.10E-01	2.08E-02	2.16E+00	2.96E+00	5.46E+00	1.14E+00	1.91E-02	1.26E-04
F₂	1.73E-03	4.56E-05	3.04E-02	5.41E-03	3.38E-01	1.57E-02	2.34E-04	1.27E-08
F₃	5.30E-01	3.20E-01	1.51E+00	3.96E-01	4.29E+00	1.72E+00	1.60E-04	4.31E-08
F₄	2.49E-04	1.13E-07	2.18E-02	1.53E-03	8.93E-01	5.27E-02	3.38E-06	2.02E-11
F₅	7.04E-01	8.43E-02	2.42E-01	3.04E-02	9.25E-01	6.57E-02	1.74E-02	1.72E-04
F₆	1.64E-01	2.24E-02	3.64E-01	5.02E-02	2.43E-01	6.07E-03	1.77E-02	3.04E-04
F₇	7.00E-03	1.40E-04	4.51E+00	1.45E+02	1.72E+02	1.02E+04	2.91E-04	8.14E-08
F₈	5.54E-01	3.31E+00	4.16E+00	4.55E+01	4.08E+00	5.24E+00	6.97E-03	1.08E-04
F₉	2.15E-02	4.64E-04	4.25E-01	1.45E-01	4.16E+00	1.98E-01	2.92E-03	1.81E-06
F₁₀	2.06E-05	2.05E-09	1.19E-04	4.80E-08	5.90E-04	1.04E-07	1.04E-08	1.80E-16

表4 各算法优化结果（s=10，n=20）

Tab.4 Optimization results of different algorithms （s=10，n=20）

测试函数	HHO		SFA		SSA		AOABG
测试函数	均值	均方差	均值	均方差	均值	均方差	均值	均方差
F₁	1.93E+01	2.49E+00	1.94E+01	3.29E-02	2.03E+01	4.91E-02	8.83E+00	2.17E-03
F₂	1.43E+01	1.12E+01	2.85E+01	7.27E+00	3.71E+01	2.20E+01	9.45E-01	2.64E-01
F₃	1.76E+02	2.96E+02	2.39E+02	5.37E+02	2.59E+02	5.64E+02	1.77E+01	1.40E+01
F₄	2.23E+01	8.90E+01	8.59E+01	4.05E+02	1.02E+02	3.94E+02	1.07E+01	7.98E+00
F₅	1.67E+02	8.65E+02	3.55E+02	2.57E+03	3.76E+02	2.62E+03	1.32E+01	3.03E-04
F₆	9.53E+00	1.77E+00	1.81E+01	1.21E+00	2.03E+01	5.04E-01	3.87E+00	3.29E-03
F₇	2.29E+03	2.87E+05	2.50E+04	1.45E+07	3.39E+04	1.50E+07	1.40E+03	3.25E-02
F₈	7.76E+05	1.07E+09	1.14E+08	1.42E+15	9.66E+07	7.98E+14	6.87E+05	1.58E+06
F₉	1.22E+01	2.11E+00	8.68E+01	8.74E+01	8.99E+01	2.98E-01	6.10E+00	3.65E-04
F₁₀	7.43E-02	4.09E-03	3.19E-01	7.60E-03	5.46E-01	3.10E-02	6.18E-07	3.58E-13

表5 各算法优化结果（s=30，n=30）

Tab.5 Optimization results of different algorithms （s=30，n=30）

测试函数	HHO		SFA		SSA		AOABG
测试函数	均值	均方差	均值	均方差	均值	均方差	均值	均方差
F₁	1.93E+01	4.60E-02	1.99E+01	8.96E-02	2.01E+01	2.90E-02	9.72E+00	1.11E+01
F₂	2.51E+01	1.80E+01	5.00E+01	4.11E+01	5.76E+01	3.10E+01	1.29E+00	1.77E-01
F₃	2.44E+02	3.57E+02	3.39E+02	1.41E+03	3.57E+02	9.86E+02	3.09E+01	4.19E+01
F₄	4.73E+01	9.46E+01	1.41E+02	5.97E+02	1.27E+02	4.48E+02	9.65E+01	5.69E+02
F₅	1.10E+02	7.21E+02	4.68E+02	3.86E+03	4.34E+02	4.13E+03	1.80E+01	7.98E-03
F₆	7.22E+00	4.02E-01	2.33E+01	1.12E+00	2.42E+01	2.51E-01	4.54E+00	2.32E-03
F₇	2.12E+03	2.54E+03	4.57E+04	5.55E+07	5.44E+04	1.70E+07	1.90E+03	1.37E-02
F₈	1.14E+06	7.61E+08	1.27E+08	8.33E+14	1.46E+08	4.51E+14	1.09E+06	3.38E+05
F₉	1.94E+01	2.46E+00	1.05E+02	1.04E+02	9.93E+01	3.48E+01	9.11E+00	2.67E-04
F₁₀	6.02E-02	4.03E-04	4.80E-01	4.83E-02	4.75E-01	2.56E-02	4.10E-02	1.14E-21

图5 二维测试函数F1~F8下的优化曲线

Fig.5 Optimization curves under 2-dimensional test functions F1 to F8

图6 30维测试函数F1~F8下的优化曲线

Fig.6 Optimization curves under 30-dimensional test functions F1 to F8

参考文献 15

1	段海滨，叶飞. 鸽群优化算法研究进展［J］. 北京工业大学学报， 2017， 43（1）：1-7. 10.11936/bjutxb2016090003
	DUAN H B， YE F. Progresses in pigeon-inspired optimization algorithms［J］. Journal of Beijing University of Technology， 2017， 43（1）：1-7. 10.11936/bjutxb2016090003
2	ZONG W G， KIM J H， LOGANATHAN G V. A new heuristic optimization algorithm： harmony search［J］. Simulation， 2001， 2（2）：60-68. 10.1177/003754970107600201
3	YANG X S. Firefly algorithms for multimodal optimization［C］// Proceedings of the 5th International Conference on Stochastic Algorithms： Foundations and Applications. Cham： Springer， 2009：169-178. 10.1007/978-3-642-04944-6_14
4	YANG X S， DEB S. Cuckoo search via Lévy flights［C］// Proceedings of the 2009 World Congress on Nature and Biologically Inspired Computing. Piscataway： IEEE， 2009：210-214. 10.1109/nabic.2009.5393690
5	YANG X S. A new metaheuristic bat-inspired algorithm［J］. Computer Knowledge and Technology， 2010， 284：65-74. 10.1007/978-3-642-12538-6_6
6	HEIDARI A A， MIRJALILI S， FARIS H， et al. Harris hawks optimization： algorithm and applications［J］. Future Generation Computer Systems， 2019， 97：849-872. 10.1016/j.future.2019.02.028
7	XUE J K， SHEN B. A novel swarm intelligence optimization approach： sparrow search algorithm［J］. Systems Science and Control Engineering， 2020，8（1）：22-34. 10.1080/21642583.2019.1708830
8	潘科，张伟，王亚刚. 特种部队算法：一种新的元启发式算法［J/OL］. 控制与决策. （2021-08-02）［2021-08-21］. .
	PAN K， ZHANG W， WANG Y G. Special forces algorithm： a new meta-heuristic algorithm［J/OL］. Control and Decision. （2021-08-02）［2021-08-21］..
9	郭雨鑫，刘升，高文欣，等. 多策略改进哈里斯鹰优化算法［J］. 微电子学与计算机， 2021， 38（7）：18-24.
	GUO Y X， LIU S， GAO W X， et al. Improved Harris hawks optimization algorithm with multiple strategies［J］. Microelectronics and Computer， 2021， 38（7）：18-24.
10	毛清华，张强. 融合柯西变异和反向学习的改进麻雀算法［J］. 计算机科学与探索， 2021， 15（6）：1155-1164.
	MAO Q H， ZHANG Q. Improved sparrow algorithm combining Cauchy mutation and opposition-based learning［J］. Journal of Frontiers of Computer Science and Technology， 2021， 15（6）：1155-1164.
11	汤安迪，韩统，徐登武，等. 混沌精英哈里斯鹰优化算法［J］. 计算机应用， 2021， 41（8）：2265-2272. 10.11772/j.issn.1001-9081.2020101610
	TANG A D， HAN T， XU D W， et al. Chaotic elite Harris hawks optimization algorithm［J］. Journal of Computer Applications， 2021， 41（8）：2265-2272. 10.11772/j.issn.1001-9081.2020101610
12	国强，朱国会，李万臣. 基于混沌麻雀搜索算法的TDOA/FDOA定位［J/OL］. 吉林大学学报（工学版）. （2021-09-02）［2021-09-11］..
	GUO Q， ZHU G H， LI W C. TDOA/FDOA localization based on chaotic sparrow search algorithm［J/OL］. Journal of Jilin University （Engineering and Technology Edition）. （2021-09-02）［2021-09-11］..
13	夏学文，刘经南，高柯夫，等. 具备反向学习和局部学习能力的粒子群算法［J］. 计算机学报， 2015， 38（7）：1397-1407. 10.11897/SP.J.1016.2015.01397
	XIA X W， LIU J N， GAO K F， et al. Particle swarm optimization algorithm with reverse-learning and local-learning behavior［J］. Chinese Journal of Computers， 2015， 38（7）：1397-1407. 10.11897/SP.J.1016.2015.01397
14	张永韡，汪镭，吴启迪. 动态适应布谷鸟搜索算法［J］. 控制与决策， 2014， 29（4）：617-622.
	ZHANG Y W， WANG L， WU Q D. Dynamic adaptation cuckoo search algorithm［J］. Control and Decision， 2014， 29（4）：617-622.
15	SHA L X， PAN Z Q. FSQGA based 3D complexity wellbore trajectory optimization［J］. Oil and Gas Science and Technology， 2018， 73： No.79. 10.2516/ogst/2018008

[1]	陆国庆, 孙昊. 基于随机行走的群机器人二维地图构建[J]. 计算机应用, 2021, 41(7): 2121-2127.
[2]	程美英, 钱乾, 倪志伟, 朱旭辉. 信息筛选多任务优化自组织迁移算法[J]. 计算机应用, 2021, 41(6): 1748-1755.
[3]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[4]	陈维兴, 刘清涛, 孙习习, 陈斌. 机坪感知网络的快速收敛平均一致性时间同步算法[J]. 计算机应用, 2020, 40(11): 3407-3412.
[5]	李人敏, 黄劲松, 陈琛, 吴君钦. 基于改进粒子群算法的毫米波大规模MIMO混合预编码方案[J]. 计算机应用, 2018, 38(8): 2365-2369.
[6]	欧阳宁, 曾梦萍, 林乐平. 基于并列卷积神经网络的超分辨率重建[J]. 计算机应用, 2017, 37(4): 1174-1178.
[7]	梁本来, 杨忠明, 秦勇, 蔡昭权. 引入梯度下降的蚁群算法求解多约束服务质量路由[J]. 计算机应用, 2017, 37(3): 722-729.
[8]	尤心心, 葛檬. 基于置信传播的复杂网络社团发现算法[J]. 计算机应用, 2017, 37(11): 3115-3118.
[9]	李萌, 秦品乐, 李传朋. 基于多新息理论的深度信念网络算法[J]. 计算机应用, 2016, 36(9): 2521-2525.
[10]	关志艳, 冯秀芳. 差分进化融合混合虚拟力的有向传感器网络覆盖算法[J]. 计算机应用, 2016, 36(12): 3244-3250.
[11]	张斌, 张达敏, 阿明翰. 基于模拟退火的果蝇优化算法[J]. 计算机应用, 2016, 36(11): 3118-3122.
[12]	王振朝高扬薛文玲杨建坡. 基于并行滤波器的回波抵消技术方案[J]. 计算机应用, 2013, 33(07): 1839-1841.
[13]	张雪媛王永刚张琼. 基于分数布朗运动的自相似流量判别及生成方法[J]. 计算机应用, 2013, 33(04): 947-949.
[14]	欧旭梁京章罗德相张新华. 利用前两代信息的改进粒子群优化算法[J]. 计算机应用, 2010, 30(2): 472-475.
[15]	梁昔明肖伟龙文秦浩宇. 基于梯度信息指导交叉的遗传算法[J]. 计算机应用, 2010, 30(10): 2582-2584.

基于布朗运动与梯度信息的交替优化算法

Alternately optimizing algorithm based on Brownian movement and gradient information

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 15

相关文章 15

编辑推荐

Metrics