基于动态分组的多策略引力搜索算法

张强; 王梅

doi:10.3969/j.issn.1000-5641.2019.01.08

基于动态分组的多策略引力搜索算法

doi: 10.3969/j.issn.1000-5641.2019.01.08

张强,
王梅

东北石油大学计算机与信息技术学院, 黑龙江大庆 163318

基金项目:

国家自然科学基金 61702093

黑龙江省自然科学基金 F2015020

详细信息

作者简介:
张强, 男, 博士, 研究方向为进化算法、神经网络和智能优化.E-mail:zhangqiang@nepu.edu.cn

中图分类号: TP301.6
计量
- 文章访问数: 125
- HTML全文浏览量: 88
- PDF下载量: 192
- 被引次数: 0
出版历程
- 收稿日期: 2018-01-12
- 刊出日期: 2019-01-25

Multi-strategy gravitational search algorithm based on dynamic grouping

School of Computer and Information Technology, Northeast Petroleum University, Daqing Heilongjiang 163318, China

摘要

摘要: 给出了一种基于动态分组的多策略引力搜索算法.算法迭代初期利用自适应分组策略对种群进行分组寻优，每个分组内只更新最差个体，采用云模型理论来改进最优个体的进化行为；迭代后期将种群分为优势子群和拓展子群，采用差分变异算子更新优势子群提高寻优精度和速度，利用Tent混沌理论进化拓展子群完成个体变异.典型复杂函数测试表明，该算法具有很好的收敛精度和计算速度.
- 引力搜索算法 /
- 云模型 /
- 佳点集 /
- 混沌 /
- 连续空间优化
Abstract: A multi-strategy gravitational search algorithm based on dynamic grouping is proposed in this paper. At the initial stage of the algorithm iteration, adaptive grouping strategies are used to optimize populations. Only the least-optimal individuals are updated in each group. The cloud model theory is used to improve the evolutionary behavior of the optimal individuals. In the later part of the algorithm iteration, the populations are divided into dominant and extension subgroups. The differential mutation operator is subsequently used to update the dominant subgroups to improve the precision and speed of the optimization. Tent chaos theory is used to update the extension subgroups to complete the individual variation. Typical complex function tests show that the algorithm has good convergence accuracy and computational speed.
- gravitational search algorithm /
- cloud model /
- good point set /
- chaos /
- continuous space optimization

HTML全文

步骤1:算法初始化, 设置迭代次数、结束条件和算法运行参数.
步骤2:计算每个个体的适应值, 利用公式(2)计算重力常数.
步骤3:根据个体的适应值利用公式(1)计算每个个体的质量, 再利用公式(3)、公式(4)、公式(5)计算每个个体的加速度.
步骤4:根据公式(6)计算每个个体的速度, 并更新个体的位置.
步骤5:重复步骤2到步骤4, 直到满足结束条件或迭代次数.

下载: 导出CSV

步骤1:设定种群规模、分组个数$m$、最大迭代数$T$、分组内迭代数和最小收敛精度, 采用第2.1节的方法初始寻优个体.
步骤2:根据第2.2节对种群里的个体进行分组, 根据第2.3节对个体进行更新.
步骤3:如果未满足结束条件, 且分组内的迭代次数达到指定次数和分组个数$m$不为2, 则执行步骤2.
步骤4:若$m$等于2, 采用第2.4节的方法进化后期的双子群个体寻优行为.
步骤5:若满足收敛精度或达到最大迭代数则退出, 否则执行步骤4.

下载: 导出CSV

表 1 实验测试函数

Tab. 1 Experimental test function

序号	函数	最优解	最小值
1	$f_1 =\sum\limits_{i=1}^n {X_i^2 }, -5.12\le x_i \le 5.12$	(0, $\cdots$, 0)	0
2	$f_2 =\sum\limits_{i=1}^n {[x_i^2 }-10\cos (2\pi x_i )]+10n, \; \left\| {x_i } \right\|\le 5.12$	(0, $\cdots$, 0)	0
3	$f_3 =\sum\limits_{i=1}^n {\left\| {x_i } \right\|} +\prod\limits_{i=1}^n {\left\| {x_i } \right\|}, \;\left\| {x_i } \right\|\le 10$	(0, $\cdots$, 0)	0
4	$f_4 =20+\exp (1)-20\exp \left[{-\frac{1}{5}\sqrt {\frac{1}{n}\sum\limits_{i=1}^n {x_i ^2} } } \right]$	(0, $\cdots$, 0)	0
	$-\exp \left[{\frac{1}{n}\sum\limits_{i=1}^n {\cos (2\pi x_i )} } \right], \; \vert x_i \vert \le 32.768$
5	$f_5 =\sum\limits_{i=1}^{11} {\left[a_i-\frac{x_1 (b_i^2 +b_i x^2)}{b_i^2 +b_i x_3 +x_4 }\right]^2}, \vert x_i \vert \le 5, $	(0.1928, 0.1908,	0.000 307 5
		0.123 1, 0.135 8)
	$b_i^{-1}=[{0.25, 0.5, 1, 2, 4, 6, 8, 10, 12, 14, 16}]$
	$a_i =[0.1957, 0.1947, 0.1735, 0.16, 0.0844, 0.0627, $
	0.0456, 0.0342, 0.0323, 0.0235, 0.0246]
6	$f_6\! =\!\!\sum\limits_{i=1}^{n-1} {[100\times (x_{i+1}-x_i^2 )+(x_i-1)^2]}, \;-5\le x_i \le 10$	(1, $\cdots$, 1)	0
7	$f_7 =0.5\times \sum\limits_{i=1}^n {(x_i^4 -16\times x_i^2 +5\times x_i )}, \;\vert x\vert _i \le 5$	(-2.903 534, $\cdots$, -2.903 534)	-39.165 99$\times n$
8	$f_8 =\sum\limits_{i=1}^n {ix_i^4 } +{\rm {rand()}}[0, 1], \;\vert x_i \vert \le 1.28$	(0, $\cdots$, 0)	0

下载: 导出CSV

表 2 $f_{1}$计算结果对比

Tab. 2 Comparison of calculation results for $ f_{1}$

算法	函数$f_1 $
算法	最优结果	最差结果	平均结果	方差	时间/s
DE	3.134E-15	5.690E-14	2.535E-14	2.103E-14	5.126
GSA	7.228E-18	2.475E-17	1.537E-17	2.062E-35	9.236
DE-GSA	1.125E-18	1.106E-17	1.078E-17	5.173E-28	6.572
QGSA	1.307E-18	2.135E-17	1.197E-17	1.156E-28	6.323
MS-GSA	0	6.529E-20	2.613E-22	2.426E-38	3.751

下载: 导出CSV

表 3 $f_{2}$计算结果对比

Tab. 3 Comparison of calculation results for $ f_{2}$

算法	函数$f_2 $
算法	最优结果	最差结果	平均结果	方差	时间/s
DE	1.440E+02	1.870E+02	1.706E+02	1.654E+01	5.619
GSA	7.960E+00	2.288E+01	1.398E+01	1.529E+01	9.264
DE-GSA	2.236E-14	6.124E-13	1.614E-13	2.972E-28	7.991
QGSA	3.398E-15	9.995E-15	5.107E-15	6.437E-28	8.064
MS-GSA	0	7.288E-15	5.691E-17	4.126E-30	3.563

下载: 导出CSV

表 4 $f_{3}$计算结果对比

Tab. 4 Comparison of calculation results for $ f_{3}$

算法	函数$f_3 $
算法	最优结果	最差结果	平均结果	方差	时间/s
DE	7.727E-07	1.988E-06	1.397E-06	4.501E-07	4.263
GSA	1.378E-08	2.489E-08	1.859E-08	1.039E-17	9.015
DE-GSA	5.528E-13	2.162E-09	6.241E-12	3.837E-17	8.903
QGSA	5.019E-10	3.831E-08	7.018E-08	8.967E-17	8.416
MS-GSA	1.118E-14	6.707E-12	6.905E-13	3.215E-24	3.785

下载: 导出CSV

表 5 $f_{4}$计算结果对比

Tab. 5 Comparison of calculation results for $ f_{4}$

算法	函数$f_4 $
算法	最优结果	最差结果	平均结果	方差	时间/s
DE	2.594E-07	1.089E-06	6.326E-07	3.070E-07	5.253
GSA	2.631E-09	3.806E-09	3.115E-09	1.245E-19	9.288
DE-GSA	2.821E-10	1.016E-10	2.062E-10	1.327E-21	7.987
QGSA	1.659E-11	1.840E-09	3.236E-10	1.307E-19	8.395
MS-GSA	9.864E-16	3.189E-15	4.291E-15	2.219E-30	3.905

下载: 导出CSV

表 6 $f_{5}$计算结果对比

Tab. 6 Comparison of calculation results for $ f_{5}$

算法	函数$f_5 $
算法	最优结果	最差结果	平均结果	方差	时间/s
DE	8.224E-04	1.011E-03	9.705E-03	8.260E-04	5.329
GSA	1.728E-03	5.713E-03	3.126E-03	6.945E-04	6.693
DE-GSA	5.515E-04	1.037E-03	8.521E-04	3.068E-04	6.205
QGSA	1.488E-03	2.624E-03	2.049E-03	4.360E-04	5.792
MS-GSA	3.075E-04	9.028E-04	6.323E-04	2.281E-04	5.251

下载: 导出CSV

表 7 $f_{6}$计算结果对比

Tab. 7 Comparison of calculation results for $ f_{6}$

算法	函数$f_6 $
算法	最优结果	最差结果	平均结果	方差	时间/s
DE	1.629E+01	2.671E+01	2.354E+01	4.471E+00	5.147
GSA	2.401E+01	2.475E+01	2.440E+01	3.424E-02	9.226
DE-GSA	2.335E+01	2.472E+01	2.364E+01	4.618E-01	6.362
QGSA	2.231E+01	2.448E+01	2.326E+01	7.111E-01	6.792
MS-GSA	8.486E-03	1.095E+00	4.494E-01	1.517E-01	4.639

下载: 导出CSV

表 8 $f_{7}$计算结果对比

Tab. 8 Comparison of calculation results for $ f_{7}$

算法	函数$f_7 $
算法	最优结果	最差结果	平均结果	方差	时间/s
DE	-1.066E+03	-7.456E+02	-8.186E+02	4.532E+03	6.239
GSA	-1.118E+03	-9.629E+02	-1.044E+03	1.401E+03	9.693
DE-GSA	-1.128E+03	-1.020E+03	-1.062E+03	6.191E+02	7.382
QGSA	-1.131E+03	-1.031E+03	-1.053E+03	1.525E+03	7.065
MS-GSA	-1.138E+03	-1.063E+03	-1.083E+03	1.436E+02	4.258

下载: 导出CSV

表 9 $f_{8}$计算结果对比

Tab. 9 Comparison of calculation results for $ f_{8}$

算法	函数$f_8 $
算法	最优结果	最差结果	平均结果	方差	时间/s
DE	3.943E-02	5.421E-02	4.587E-02	5.559E-03	7.127
GSA	8.900E-03	2.497E-02	1.384E-02	1.648E-05	9.683
DE-GSA	1.114E-03	6.512E-02	2.272E-02	2.853E-04	9.362
QGSA	1.105E-05	8.551E-04	2.248E-04	5.553E-08	9.895
MS-GSA	3.373E-06	2.923E-04	6.653E-05	4.577E-09	7.092

下载: 导出CSV

表 10 高维函数计算结果对比

Tab. 10 Comparison of calculation results for a high-dimensional function

函数	算法	$N=100$			$N=200$
函数	算法	平均结果	方差	时间/s	平均结果	方差	时间/s
	DE	3.91E-02	2.21E-02	6.29	1.38E+02	2.51E+02	10.43
$f_1 $	GSA	2.08E-03	2.51E-05	10.85	3.09E+00	7.07E-01	20.50
	MS-GSA	8.42E-06	2.61E-16	4.61	9.44E-06	7.49E-16	9.25
	DE	7.27E+02	5.97E+01	7.67	1.27E+03	2.26E+02	11.56
$f_2 $	GSA	7.42E+01	1.69E+02	11.23	2.62E+02	1.04E+03	20.84
	MS-GSA	5.15E-05	3.84E-11	8.62	4.74E-05	9.13E-11	16.07
	DE	1.64E+00	3.52E-01	6.59	4.73E+01	1.12E+01	10.45
$f_3 $	GSA	9.95E-01	2.27E-01	10.92	2.04E+01	1.04E+01	20.79
	MS-GSA	9.23E-06	6.07E-12	5.37	9.69E-06	5.69E-12	10.95
	DE	2.38E+00	3.77E-01	7.34	9.63E+00	1.85E-01	11.12
$f_4 $	GSA	1.19E+00	2.45E-01	11.11	3.99E+00	1.80E-01	20.94
	MS-GSA	9.32E-06	3.15E-12	5.13	9.27E-06	8.21E-12	11.08

下载: 导出CSV

参考文献(23)

[1]	RASHEDI E, NEZAMABADI-POUr H, SARYAZDI S. GSA:A gravitational search algorithm[J]. Information Sciences, 2009, 179(13):2232-2248. doi: 10.1016/j.ins.2009.03.004
[2]	卫晓娟, 丁旺才, 李宁洲.基于自适应混合引力搜索算法的混沌系统参数辨识[J].兰州大学学报(自然科学版), 2016, 52(3):410-416. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QKC20162016080300063348
[3]	LI P, DUAN H B. Path planning of unmanned aerial vehicle based on improved gravitational search algorithm[J]. Science China Technological Sciences, 2012, 55:2712-2719, doi: 10.1007/s11431-012-4890-x
[4]	BAHROLOLOUM A, NEZAMABADI-POUR H, BAHROLOLOUM H, et al. A prototype classifier based on gravitational search algorithm[J]. Applied Soft Computing, 2012, 12(2):819-825. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=89ad19c532681ba0926898a285c64fed
[5]	毕晓君, 刁鹏飞, 王艳娇.求解动态优化问题的改进多种群引力搜索算法[J].中南大学学报(自然科学版), 2015, 46(9):3325-3331. http://cdmd.cnki.com.cn/Article/CDMD-10217-1018083023.htm
[6]	王宇, 黄胜, 廖全蜜.基于引力搜索算法的船舶舱室布置方法[J].上海交通大学学报, 2016, 50(1):131-139. http://d.old.wanfangdata.com.cn/Periodical/shjtdxxb201601021
[7]	KAZAK N, DUYSAK A. Modified gravitational search algorithm[C]//International Symposium on Innovations in Intelligent Systems and Applications. IEEE, 2012: 1-4.
[8]	YAZDANI S, NEZAMABADI-POUR H, KAMYAB S. A gravitational search algorithm for multimodal optimization[J] Swarm and Evolutionary Computation, 2014, 14(2):1-14. http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0231970977/
[9]	GU B J, PAN F. Modified gravitational search algorithm with particle memory ability and its application[J] International Journal of Innovative Computing, Information and Control, 2013, 9:4531-4544. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=5bca18da48712ea87d14ecb55d1b89e1
[10]	张英杰, 龚中汉.基于阈值统计学习的差分进化引力搜索算法[J].计算机研究与发展, 2014, 51(10):2187-2194. doi: 10.7544/issn1000-1239.2014.20130395
[11]	LI X T, YIN M H, MA Z Q. Hybrid differential evolution and gravitation search algorithm for unconstrained optimization[J]. International Journal of Physical Sciences, 2011, 6(25):5961-5981.
[12]	隋永霞, 孙合明.基于高斯变异的引力搜索算法[J].江南大学学报(自然科学版), 2015, 14(5):596-600. doi: 10.3969/j.issn.1671-7147.2015.05.017
[13]	张维平, 任雪飞, 李国强, 等.改进的万有引力搜索算法在函数优化中的应用[J].计算机应用, 2013, 33(5):1317-1320. http://d.old.wanfangdata.com.cn/Periodical/jsjyy201305031
[14]	华罗庚, 王元.数论在近代分析中的应用[M].北京:科学出版社, 1978:1-99.
[15]	刘香品, 宣士斌, 刘峰.引入佳点集和猴群翻过程的人工蜂群算法[J].模式识别与人工智能, 2015, 28(1):80-89. http://d.old.wanfangdata.com.cn/Periodical/mssbyrgzn201501011
[16]	毕晓君, 张磊.基于混合策略的双种群约束优化算法[J].控制与决策, 30(4): 715-720.
[17]	俞志富, 李俊武, 王利华.一种基于云模型和证据理论的融合识别方法[J].信息与控制, 2014, 43(1):30-36. http://d.old.wanfangdata.com.cn/Periodical/xxykz201401006
[18]	王庆龙, 王智学, 何红悦.基于模糊-云模型的C~4ISR系统效能需求建模与分析方法[J].系统工程与电子技术, 2016, 38(9):2065-2071. http://www.cnki.com.cn/Article/CJFDTotal-XTYD201609014.htm
[19]	SARKER R A, ELSAYED S M, RAY T. Differential evolution with dynamic parameters selection for optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(5):689-707. http://ieeexplore.ieee.org/document/6600821/
[20]	李章维, 周晓根, 张贵军.一种动态自适应差分进化算法[J].计算机科学, 2015, 42(6):52-56. http://d.old.wanfangdata.com.cn/Periodical/jsjkx2015z1013
[21]	孔祥勇, 高立群, 欧阳海滨, 等.求解大规模可靠性问题的改进差分进化算法[J].东北大学学报(自然科学版), 2014, 35(3):328-332. doi: 10.3969/j.issn.1005-3026.2014.03.006
[22]	刘振军.结构全局优化设计的漏淹优化算法研究[D].辽宁大连: 大连理工大学, 2016.
[23]	柏静.基于多种混合策略的人工蜂群算法改进研究[D].济南: 山东师范大学, 2016.