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

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

Abstract

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

CLC Number:

TP301

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.

Figures/Tables 8

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 23

Related Articles 15

Metrics

Recommended 0

[1]	Zhen ZHENG, Yingjian YAN, Juesong CAI, Yanjiang LIU. Non-specific TVLA method based on two-sample KS test [J]. Journal on Communications, 2023, 44(5): 137-147.
[2]	Jiale ZHANG, Chengcheng ZHU, Xiaobing SUN, Bing CHEN. Membership inference attack and defense method in federated learning based on GAN [J]. Journal on Communications, 2023, 44(5): 193-205.
[3]	Peixin ZHANG, Nan ZHANG, Daqing WANG, Tong WU, Zhe LI, Fengkui GONG. Joint resampling algorithm for parallel dual feedback time-frequency domain symbol timing recovery [J]. Journal on Communications, 2023, 44(4): 15-26.
[4]	Guoliang XU, Feng TAN, Yongyi RAN, Feng CHEN. Joint beam hopping and coverage control optimization algorithm for multibeam satellite system [J]. Journal on Communications, 2023, 44(4): 78-86.
[5]	Guang YANG, Zhaoyang WU, Min NIE, Xiaohong YAN, Fan JIANG. Research on PAPR reduction algorithm based on CWGAN-SLM for multi-wavelet OFDM system [J]. Journal on Communications, 2023, 44(4): 99-110.
[6]	Xin SUN, Guifu ZHANG, Hongyan XING, Wang Zenghui. Research on intrusion detection for maritime meteorological sensor network based on balancing generative adversarial network [J]. Journal on Communications, 2023, 44(4): 124-136.
[7]	Wei LI, Chun LIU, Dawu GU, Wenqian SUN, Jianning GAO, Mengyang QIN. Statistical ineffective fault analysis of the lightweight authenticated cipher algorithm Saturnin-Short [J]. Journal on Communications, 2023, 44(4): 167-175.
[8]	Mu ZHOU, Jing ZHANG, Yong WANG, Xiaolong YANG, Lingxia LI. Optical quantum positioning method based on random resampling of scattering free path [J]. Journal on Communications, 2023, 44(3): 55-65.
[9]	Junfeng TIAN, Qianyu YANG, Xiao Jitian. Distributed audit causal consistency model based on biased stability [J]. Journal on Communications, 2023, 44(3): 164-177.
[10]	Yanshuo ZHANG, Ning LIU, Yuqi YUAN, Yatao YANG. Adaptor signature scheme based on ISRSAC digital signature algorithm [J]. Journal on Communications, 2023, 44(3): 178-185.
[11]	Wei CUI, Ying YU, Haixia YU, Chao CHEN, Yunpeng LI. Sparse channel fast reconstruction algorithm for OFDM system based on IOC-CSMP [J]. Journal on Communications, 2023, 44(2): 52-58.
[12]	Lingtao TANG, Di WANG, Shengyun LIU. Data augmentation scheme for federated learning with non-IID data [J]. Journal on Communications, 2023, 44(1): 164-176.
[13]	Yanhua LIU, Jiaqi LI, Zhengui OU, Xiaoling GAO, Ximeng LIU, Weizhi MENG, Baoxu LIU. Adversarial training driven malicious code detection enhancement method [J]. Journal on Communications, 2022, 43(9): 169-180.
[14]	Chengsheng YUAN, Qiang GUO, Zhangjie FU. Copyright protection algorithm based on differential privacy deep fake fingerprint detection model [J]. Journal on Communications, 2022, 43(9): 181-193.
[15]	Yanwen WANG, Weimin LEI, Wei ZHANG, Huan MENG, Xinyi CHEN, Wenhui YE, Qingyang JING. Survey on video image reconstruction method based on generative model [J]. Journal on Communications, 2022, 43(9): 194-208.