适应度二次选择的QPSO和SA协同搜索大规模离散优化算法

doi:10.11959/j.issn.1000-436x.2020173

通信学报 ›› 2020, Vol. 41 ›› Issue (8): 22-31.doi: 10.11959/j.issn.1000-436x.2020173

适应度二次选择的QPSO和SA协同搜索大规模离散优化算法

张兆娟¹,王万良¹,唐继军²

¹ 浙江工业大学计算机科学与技术学院，浙江杭州 310023
² 天津大学智能与计算学部，天津 300050

修回日期:2020-06-10 出版日期:2020-08-25 发布日期:2020-09-05
作者简介:张兆娟（1990- ），女，江西九江人，浙江工业大学博士生，主要研究方向为大数据、分布式优化、深度学习等|王万良（1957- ），男，江苏高邮人，博士，浙江工业大学教授、博士生导师，主要研究方向为人工智能、大数据分析、优化调度、计算机智能自动化等|唐继军（1971- ），男，湖南常德人，博士，天津大学特聘教授、博士生导师，主要研究方向为深度学习、生物信息、高性能计算等
基金资助:
国家自然科学基金资助项目(61873240)

Second fitness selection QPSO and SA cooperative search for large-scale discrete optimization algorithm

Zhaojuan ZHANG¹,Wanliang WANG¹,Jijun TANG²

¹ College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China
² College of Intelligence and Computing,Tianjin University,Tianjin 300050,China

Revised:2020-06-10 Online:2020-08-25 Published:2020-09-05
Supported by:
The National Natural Science Foundation of China(61873240)

摘要/Abstract

摘要：

针对大规模离散工程优化问题，提出一种改进的离散量子粒子群优化算法（IDQPSO-SA）。首先，提出一种适应度的二次选择更新平均最优位置策略，使QPSO能够适用离散空间的优化问题。其次，引入二次切割与连接（DCJ）排序策略加速搜索进程。最后，在QPSO并行搜索基础上，引进模拟退火（SA）的概率突跳性，协同进行全局搜索。在大规模、高维离散工程优化问题上进行了测试，并同已有算法进行比较，结果表明，IDQPSO-SA进一步提高了面向大规模离散优化问题时的搜索效率，并有效提升了算法的性能。

关键词: 协同搜索, 量子粒子群, 模拟退火, 二次切割与连接排序, 离散优化

Abstract:

To address the large-scale discrete optimization problem,a cooperative optimization algorithm called IDQPSO-SA was proposed.First,a strategy by applying two selections on the averaging fitness values to update the mean best position was presented,which could overcome the deficiency that QPSO was not applicable for discrete problems.Second,the double cut joining (DCJ) sorting strategy was incorporated into IDQPSO-SA,since the DCJ sorting strategy could considerably reduce the search space.Finally,the probability jumping ability of simulated annealing (SA) was combined with the parallel search of QPSO,and the global search was carried out collaboratively.By comparing with existing algorithms,the experimental results show that IDQPSO-SA further improves the search efficiency and has a comparable performance when faced with large-scale discrete optimization problems.

Key words: cooperative search, QPSO, SA, DCJ sorting, discrete optimization

中图分类号:

TP301

张兆娟,王万良,唐继军. 适应度二次选择的QPSO和SA协同搜索大规模离散优化算法[J]. 通信学报, 2020, 41(8): 22-31.

Zhaojuan ZHANG,Wanliang WANG,Jijun TANG. Second fitness selection QPSO and SA cooperative search for large-scale discrete optimization algorithm[J]. Journal on Communications, 2020, 41(8): 22-31.

图/表 8

图1

图2

图3

表1

表2

表3

表4

表5

参考文献 23

[1]	王凌, 沈婧楠, 王圣尧 ,等. 协同进化算法研究进展[J]. 控制与决策, 2015,30(2): 193-202.
	WANG L , SHEN J N , WANG S Y ,et al. Advances in co-evolutionary algorithms[J]. Control and Decision, 2015,30(2): 193-202.
[2]	王万良, 张兆娟, 高楠 ,等. 基于人工智能技术的大数据分析方法研究进展[J]. 计算机集成制造系统, 2019,25(3): 529-547.
	WANG W L , ZHANG Z J , GAO N ,et al. Research progress of big data analytics methods based on artificial intelligence technology[J]. Computer Integrated Manufacturing Systems, 2019,25(3): 529-547.
[3]	GHEYAS I A , SMITH L S . Feature subset selection in large dimensionality domains[J]. Pattern Recognition, 2010,43(1): 5-13.
[4]	张震, 魏鹏, 李玉峰 ,等. 改进粒子群联合禁忌搜索的特征选择算法[J]. 通信学报, 2018,39(12): 60-68.
	ZHANG Z , WEI P , LI Y F ,et al. Feature selection algorithm based on improved particle swarm joint taboo search[J]. Journal on Communi-cations, 2018,39(12): 60-68.
[5]	王晟, 王雪, 毕道伟 . 无线传感器网络遗传—禁忌搜索移动代理测量调度方法[J]. 通信学报, 2008,29(11): 194-199.
	WANG S , WANG X , BI D W . Genetic algorithm-tabu search for mo-bile agents measurement scheduling in wireless sensor networks[J]. Journal on Communications, 2008,29(11): 194-199.
[6]	叶苗, 王宇平, 代才 ,等. 无线传感器网络中新的最小暴露路径问题及其求解算法[J]. 通信学报, 2016,37(1): 49-60.
	YE M , WANG Y P , DAI C ,et al. New minimum exposure path prob-lem and its solving algorithm in wireless sensor networks[J]. Journal on Communications, 2016,37(1): 49-60.
[7]	GHEYAS I A , SMITH L S . Feature subset selection in large dimensionality domains[J]. Pattern Recognition, 2010,43(1): 5-13.
[8]	SUN J , FENG B , XU W . Particle swarm optimization with particles having quantum behavior[C]// Proceedings of the 2004 Congress on Evolutionary Computation. Piscataway:IEEE Press, 2004: 325-331.
[9]	LI L , JIAO L , ZHAO J ,et al. Quantum-behaved discrete multi-objective particle swarm optimization for complex network clustering[J]. Pattern Recognition, 2017,63: 1-14.
[10]	LUKEMIRE J , MANDAL A , WONG W K . d-QPSO:a quantum-behaved particle swarm technique for finding d-optimal designs with discrete and continuous factors and a binary response[J]. Technometrics, 2019,61(1): 77-87.
[11]	KIRKPATRICK S . Optimization by simulated annealing:quantitative studies[J]. Journal of Statistical Physics, 1984,34(5-6): 975-986.
[12]	LU R , ZHAO X , LI J ,et al. Genomic characterisation and epidemiology of 2019 novel coronavirus:implications for virus origins and receptor binding[J]. The Lancet, 2020,395(10224): 565-574.
[13]	WU A , PENG Y , HUANG B ,et al. Genome composition and divergence of the novel coronavirus(2019-nCoV) originating in China[J]. Cell Host ＆ Microbe, 2020,27(3): 325-328.
[14]	WANG S W , BITBOL A F , WINGREEN N S . Revealing evolutionary constraints on proteins through sequence analysis[J]. PLoS Computational Biology, 2019,15(4):e1007010.
[15]	WANG Y K , BASHASHATI A , ANGLESIO M S ,et al. Genomic consequences of aberrant DNA repair mechanisms stratify ovarian cancer histotypes[J]. Nature Genetics, 2017,49(6):856.
[16]	TOOSI H , MOEINI A , HAJIRASOULIHA I . BAMSE:Bayesian model selection for tumor phylogeny inference among multiple samples[J]. BMC bioinformatics, 2019,20(11):282.
[17]	XU A W . A fast and exact algorithm for the median of three problem:a graph decomposition approach[J]. Journal of Computational Biology, 2009,16(10): 1369-1381.
[18]	FEIJ?O P . Reconstruction of ancestral gene orders using intermediate genomes[J]. BMC bioinformatics, 2015,16(14):S3.
[19]	王万良 . 人工智能及其应用(第 4 版)[M]. 北京: 高等教育出版社, 2020.
	WANG W L . Artificial intelligence:principles and applications[M]. 4rd Ed,Beijing: Higher Education Press, 2020.
[20]	GAO N , YANG N , TANG J . Ancestral genome inference using a genetic algorithm approach[J]. PLoS One, 2013,8(5):e62156.
[21]	GAO N , ZHANG Y , FENG B ,et al. A cooperative co-evolutionary genetic algorithm for tree scoring and ancestral genome inference[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2015,12(6): 1248-1254.
[22]	XIA R , LIN Y , ZHOU J ,et al. A median solver and phylogenetic inference based on double-cut-and-join sorting[J]. Journal of Computational Biology, 2018,25(3): 302-312.
[23]	YANCOPOULOS S , ATTIE O , FRIEDBERG R . Efficient sorting of genomic permutations by translocation,inversion and block interchange[J]. Bioinformatics, 2005,21(16): 3340-3346.

r/个	进化成本		与真实祖先的进化距离		邻接准确率		运行时间/s
r/个	QPSOSA-Median	SA-Median	QPSOSA-Median	SA-Median	QPSOSA-Median	SA-Median	QPSOSA-Median	SA-Median
550	1 545.1	1 600.4	510.1	544.0	2.74×10^-1	2.46×10^-1	8 014	456
600	1 609.2	1 664.0	573.8	602.7	2.26×10^-1	2.08×10^-1	4 867	454
650	1 662.3	1 718.4	623.0	653.6	1.95×10^-1	1.75×10^-1	5 744	445
700	1 696.1	1 750.3	670.8	699.4	1.67×10^-1	1.49×10^-1	5 471	440
750	1 730.5	1 786.3	711.1	730.2	1.43×10^-1	1.33×10^-1	4 516	435
800	1 759.5	1 811.4	749.5	767.0	1.20×10^-1	1.12×10^-1	4 390	427
850	1 783.5	1 832.4	782.3	793.9	1.04×10^-1	9.76×10^-2	4 424	425
900	1 799.3	1 850.0	801.6	817.6	9.34×10^-2	8.64×10^-2	4 710	422
950	1 813.8	1 866.2	826.0	839.6	8.18×10^-2	7.54×10^-2	4 689	419
1 000	1 821.9	1 876.2	846.9	857.9	7.24×10^-2	6.60×10^-2	4 985	417

r/个	QPSOSA-Median	GA-Median	AS-Median
550	1 545.1	1 714.8	1 551.9
600	1 609.2	1 764.8	1 621.8
650	1 662.3	1 810.0	1 680.0
700	1 696.1	1 835.3	1 719.3
750	1 730.5	1 865.8	1 757.6
800	1 759.5	1 890.4	1 790.9
850	1 783.5	1 908.0	1 814.2
900	1 799.3	1 918.3	1 830.2
950	1 813.8	1 929.9	1 848.0
1 000	1 821.9	1 940.0	1 856.2

r/个	QPSOSA-Median	GA-Median	AS-Median
550	510.1	545.4	541
600	573.8	595.5	615.9
650	623	639.7	678.9
700	670.8	677.5	726.4
750	711.1	720.1	765.4
800	749.5	754.2	802.6
850	782.3	780.1	831.4
900	801.6	803.6	854.4
950	826	825.3	872.7
1 000	846.9	848.4	888

r/个	QPSOSA-Median	GA-Median	AS-Median
550	2.74×10^-1	2.09×10^-1	2.72×10^-1
600	2.26×10^-1	1.84×10^-1	2.19×10^-1
650	1.95×10^-1	1.63×10^-1	1.74×10^-1
700	1.67×10^-1	1.47×10^-1	1.46×10^-1
750	1.43×10^-1	1.29×10^-1	1.23×10^-1
800	1.20×10^-1	1.12×10^-1	1.01×10^-1
850	1.04×10^-1	9.92×10^-2	8.51×10^-2
900	9.34×10^-2	8.89×10^-2	7.25×10^-2
950	8.18×10^-2	8.04×10^-2	6.37×10^-2
1 000	7.24×10^-2	7.06×10^-2	5.46×10^-2

r/个	QPSOSA-Median/s	GA-Median/s	AS-Median/s
550	8 014	33 032	33 496
600	4 867	32 908	48 625
650	5744	32818	67 486
700	5 471	32 735	96 020
750	4 516	32 676	107 456
800	4 390	32 528	123 077
850	4 424	32 478	131 336
900	4 710	32 445	131 510
950	4 689	32 451	137 438
1 000	4 985	32 420	142 356

适应度二次选择的QPSO和SA协同搜索大规模离散优化算法

Second fitness selection QPSO and SA cooperative search for large-scale discrete optimization algorithm

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 23

相关文章 14

Metrics

推荐阅读 0

[1]	吴家皋, 郭亚航, 蔡沈磊, 刘林峰. 基于多时间段优化贝叶斯网络的车载容迟网络路由算法[J]. 通信学报, 2021, 42(12): 109-120.
[2]	陈卓,冯钢,刘怡静,周杨. MEC中基于改进遗传模拟退火算法的虚拟网络功能部署策略[J]. 通信学报, 2020, 41(4): 70-80.
[3]	赵春晖,李雪源,崔颖. 混合编码方式的图像聚类算法[J]. 通信学报, 2017, 38(2): 1-9.
[4]	孙康宁,马林华,茹乐,范文同,胡星,黄绍城. 混合信道下LDPC码稳定条件分析及度序列优化[J]. 通信学报, 2016, 37(9): 168-174.
[5]	吴涛,陈曦,严余松. 三元相关性量子行为粒子群优化算法研究[J]. 通信学报, 2015, 36(3): 208-215.
[6]	孙知信,陈亚当,任志广. 基于P2P流媒体直播系统的数据传输策略[J]. 通信学报, 2011, 32(6): 1-9.
[7]	何欣,桂小林. 基于概率感知覆盖的无线传感器网络节点优化部署方案[J]. 通信学报, 2010, 31(9A): 1-8.
[8]	李靖,孙力娟,王汝传,黄海平,凡高娟. 基于混合智能算法的有向传感器网络覆盖优化方法[J]. 通信学报, 2010, 31(9A): 30-36.
[9]	刘琳,于海斌. 异构无线传感器网络中簇首的优化部署策略[J]. 通信学报, 2010, 31(10): 229-237.
[10]	范一鸣,余建军,方智敏. 融合小生境机制的QoS多播路由遗传模拟退火算法[J]. 通信学报, 2008, 29(5): 65-71.
[11]	朱晓锦,陈艳春,邵勇,王健. 面向信道分配的分段退火混沌神经网络模型[J]. 通信学报, 2008, 29(5): 122-127.
[12]	舒万能. 网格计算中资源负载均衡问题的优化调度模型及其算法[J]. 通信学报, 2008, 29(3A): 50-55.
[13]	刘林峰,刘业. 传感器网络中基于模拟退火算法的拓扑控制方案[J]. 通信学报, 2006, 27(9): 71-77.
[14]	高火涛,李咏絮,郑霞. 天线阵互耦系数的估计[J]. 通信学报, 2005, 26(4): 19-23.