改進(jìn)多元宇宙算法求解大規(guī)模實(shí)值優(yōu)化問題

劉小龍

doi:10.11999/JEIT180751

改進(jìn)多元宇宙算法求解大規(guī)模實(shí)值優(yōu)化問題

doi: 10.11999/JEIT180751

劉小龍^,

華南理工大學(xué)工商管理學(xué)院廣州 510641

基金項(xiàng)目: 國家自然科學(xué)基金(71471065, 71571072, 71771091)，廣州社科聯(lián)基金(2018GZGJ02)

詳細(xì)信息

作者簡介:
劉小龍：男，1977年生，講師，研究方向?yàn)榉律鷥?yōu)化與計(jì)算智能

通訊作者:
劉小龍　xlliu@scut.edu.cn

中圖分類號(hào): TP301.6
計(jì)量
- 文章訪問數(shù): 3201
- HTML全文瀏覽量: 1296
- PDF下載量: 118
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-07-22
- 修回日期: 2019-01-17
- 網(wǎng)絡(luò)出版日期: 2019-02-14
- 刊出日期: 2019-07-01

Application of Improved Multiverse Algorithm to Large Scale Optimization Problems

Xiaolong LIU^,

School of Business Administration, South China University of Technology, Guangzhou 510641, China

Funds: The National Natural Science Foundation of China (71471065, 71571072, 71771091), Guangzhou Social Science Federation Fund (2018GZGJ02)

摘要

摘要: 針對(duì)多元宇宙優(yōu)化(MVO)算法中蟲洞存在機(jī)制、白洞選擇機(jī)制等不足，該文提出一種改進(jìn)多元宇宙優(yōu)化算法(IMVO)。設(shè)計(jì)固定概率的蟲洞存在機(jī)制和前期快速收斂后期平緩收斂的蟲洞旅行距離率，加快算法全局探索能力和快速迭代能力；提出黑洞的隨機(jī)白洞選擇機(jī)制，設(shè)計(jì)黑洞圍繞白洞恒星進(jìn)行公轉(zhuǎn)并模型化，解決代間宇宙信息溝通的問題，中低維度數(shù)值比較實(shí)驗(yàn)驗(yàn)證了改進(jìn)算法的優(yōu)良性能。選取大規(guī)模實(shí)值問題較難優(yōu)化的3個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行對(duì)比實(shí)驗(yàn)，改進(jìn)算法在大規(guī)模優(yōu)化問題上的求解精度和成功率方面具有較好的適用性和魯棒性。
- 大規(guī)模優(yōu)化問題 /
- 多元宇宙優(yōu)化 /
- 元啟發(fā)式優(yōu)化 /
- 非線性收斂因子
Abstract: To overcome the mechanism shortcomings of wormhole and white hole selection in the Multi-Verse Optimizer (MVO), an Improved Multi-Universes Optimization (IMVO) algorithm is proposed. To speed up global exploration ability and quick iteration ability, this thesis designs the existence mechanism of wormhole with fixed probability and the Travel Distance Rate (TDR) that its convergence from early stage's smoothly to later stage's fast. The random white hole selection mechanism is proposed; Black holes can revolve around selected white hole stars and is modelled to solve the problem of information communication of the Inter-generational Universes. The performance of IMVO is verified by comparison experiments in low-middle dimensions. Three benchmarks test functions are selected for comparison in large scale which are difficult to be optimized, the experimental results show that IMVO has good applicability and robustness with higher solving accuracy and success rate in large scale optimization problem.
- Large scale optimization problem /
- Multi-Verses Optimization (MVO) /
- Meta heuristic optimization /
- Non-linear convergence factor

HTML全文

圖 1 多元宇宙算法內(nèi)部主循環(huán)結(jié)構(gòu)

下載: 全尺寸圖片幻燈片

圖 2 黑洞圍繞白洞螺旋式公轉(zhuǎn)

下載: 全尺寸圖片幻燈片

表 1 文獻(xiàn)[10]的時(shí)間復(fù)雜度

操作	計(jì)算復(fù)雜度	循環(huán)次數(shù)
初始化	O(N)	1×D
計(jì)算宇宙膨脹率	O(N)	L×D
排序/標(biāo)準(zhǔn)化宇宙	O(N)	L×D
黑白洞換維度	O(K)	L×D
穿越選擇	O((1–K)WEP)	L×D
參數(shù)更新	O(1)	L

下載: 導(dǎo)出CSV

表 2 本文的時(shí)間復(fù)雜度

操作	計(jì)算復(fù)雜度	循環(huán)次數(shù)
初始化	O(N)	1×D
計(jì)算宇宙膨脹率	O(N)	L×D
黑白洞選擇	O(N)	L×D
策略1：穿越	O(N/2)	L×D
策略2：公轉(zhuǎn)	O(N/2)	L×D
參數(shù)更新	O(1)	L

下載: 導(dǎo)出CSV

表 3 單峰基準(zhǔn)測(cè)試函數(shù)的50維對(duì)比實(shí)驗(yàn)

	算法	均值	標(biāo)準(zhǔn)差	成功率(%)
f₁	文獻(xiàn)[10]	2.08583	0.648651	0
f₁	本文	4.64e-21	9.90e-21	100
f₂	文獻(xiàn)[10]	15.92479	44.7459	0
f₂	本文	4.04e-11	3.86e-11	100
f₅	文獻(xiàn)[10]	1272.13	1479.477	0
f₅	本文	6.70e-20	1.77e-19	100
f₇	文獻(xiàn)[10]	0.051991	0.029606	100
f₇	本文	3.08e-04	3.91e-04	100

下載: 導(dǎo)出CSV

表 4 多峰基準(zhǔn)測(cè)試函數(shù)的50維對(duì)比實(shí)驗(yàn)

	算法	均值	標(biāo)準(zhǔn)差	成功率(%)
f₉	文獻(xiàn)[10]	118.046	39.34364	0
f₉	本文	0	0	100
f₁₀	文獻(xiàn)[10]	4.074904	5.501546	0
f₁₀	本文	8.71e-12	5.66e-12	100
f₁₁	文獻(xiàn)[10]	0.938733	0.059535	100
f₁₁	本文	0	0	100
f₁₂	文獻(xiàn)[10]	2.459953	0.791886	0
f₁₂	本文	1.83e-23	3.51e-23	100

下載: 導(dǎo)出CSV

表 5 基準(zhǔn)測(cè)試函數(shù)30維度的算法對(duì)比實(shí)驗(yàn)

		f₁	f₂	f₅	f₇	f₉	f₁₀	f₁₁	f₁₂
文獻(xiàn)[6]	均值	6.54e-125	2.15e-73	27.27950	2.42e04	0	3.02e-15	0	0.087646
文獻(xiàn)[6]	標(biāo)準(zhǔn)差	6.80e-125	3.64e-73	0.215438	4.41e-04	0	1.95e-15	0	0.011997
本文	均值	5.24e-21	1.86e-11	2.46e-20	3.41e-04	0	5.51e-12	0	1.14e-23
本文	標(biāo)準(zhǔn)差	1.96e-20	1.37e-11	4.03e-20	3.23e-04	0	6.56e-12	0	1.90e-23

下載: 導(dǎo)出CSV

表 6 基準(zhǔn)測(cè)試函數(shù)10維度的算法對(duì)比實(shí)驗(yàn)

函數(shù)	算法	DA^[18]	CSA^[17]	MVO^[10]	IMVO^[11]	本文
f₁₀	均值	2.28	1.07	8.06e-02	4.27e-05	9.66e-12
	標(biāo)準(zhǔn)差	1.13	0.921	2.04e-01	2.22e-05	8.08e-12
	最差值	4.20	3.02	1.16	1.04e-04	7.76e-11
	最好值	4.44e-15	1.75e-03	1.17e-02	7.08e-06	3.67e-13
f₁₂	均值	9.78e-01	3.83e-01	1.07e-02	1.25e-10	4.32e-23
	標(biāo)準(zhǔn)差	8.58e-01	6.07e-01	5.70e-02	1.18e-10	1.06e-22
	最差值	3.49	3.20	3.12e-01	4.45e-10	4.71e-22
	最好值	4.84e-03	5.67e-05	9.21e-05	7.76e-12	9.15e-27

下載: 導(dǎo)出CSV

表 7 本文IMVO算法和文獻(xiàn)[6,10]中WOA, IWOA對(duì)較大規(guī)模單峰和多峰函數(shù)尋優(yōu)對(duì)比

F	對(duì)比算法	D=200			D=500
F	對(duì)比算法	均值	標(biāo)準(zhǔn)差	成功率(%)	均值	標(biāo)準(zhǔn)差	成功率(%)
f₂	文獻(xiàn)[10]	7.50e-51	9.40e-51	100	1.10e-49	2.10e-49	100
	文獻(xiàn)[6]	1.60e-67	1.90e-67	100	5.30e-66	9.60e-66	100
	本文	1.59e-10	1.43e-10	100	2.56e-10	2.41e-10	100
f₅	文獻(xiàn)[10]	1.98e+02	2.22e-01	0	4.96e02	4.66e-01	0
	文獻(xiàn)[6]	1.98e+02	5.43e-02	0	4.96e02	3.78e-01	0
	本文	6.13e-20	1.29e-19	100	3.48e-19	4.15e-19	100
f₁₀	文獻(xiàn)[10]	5.15e-15	1.94e-15	100	5.86e-15	2.97e-15	100
	文獻(xiàn)[6]	8.88e-16	0	100	4.44e-15	0	100
	本文	7.16e-12	6.87e-12	100	6.49e-12	1.13e-11	100
f₁₂	文獻(xiàn)[10]	8.09e-02	4.05e-02	0	9.19e-02	5.92e-02	0
	文獻(xiàn)[6]	2.02e-02	2.75e-02	0	8.30e-02	3.17e-02	0
	本文	5.09e-24	8.06e-24	100	4.25e-24	9.01e-24	100

下載: 導(dǎo)出CSV

表 8 求解不同規(guī)模f₂和f₁₀函數(shù)的優(yōu)化均值對(duì)比

維度D	f₂均值			f₁₀均值
維度D	文獻(xiàn)[10]	文獻(xiàn)[6]	本文	文獻(xiàn)[10]	文獻(xiàn)[6]	本文
30	1.00e-21	2.20e-73	1.86e-11	7.40	3.02e-15	5.51e-12
200	7.50e-51	1.60e-67	1.59e-10	5.15e-15	8.88e-16	7.16e-12
500	1.10e-49	5.30e-66	2.56e-10	5.86e-15	4.44e-15	6.49e-12

下載: 導(dǎo)出CSV

表 9 改進(jìn)算法的大規(guī)模實(shí)值優(yōu)化結(jié)果(閾值為1)

F	對(duì)比算法	D=1000			D=2000
F	對(duì)比算法	均值	標(biāo)準(zhǔn)差	成功率(%)	均值	標(biāo)準(zhǔn)差	成功率(%)
f₅	文獻(xiàn)[10]	8.70e+08	7.81e+07	0	7.11e+09	3.23e+08	0
f₅	本文	2.05e-19	3.42e-19	100	5.62e-19	1.37e-18	100
f₇	文獻(xiàn)[10]	1.08e+04	8.35e+02	0	1.81e+05	9.44e+03	0
f₇	本文	2.52e-04	3.99e-04	100	2.70e-04	3.87e-04	100
f₉	文獻(xiàn)[10]	1.37e+04	3.36e+02	0	3.04e+04	3.28e+02	0
f₉	本文	0	0	100	0	0	100

下載: 導(dǎo)出CSV

參考文獻(xiàn)(18)

MAHDAVI S, RAHNAMAYAN S, and SHIRI M E. Multilevel framework for large-scale global optimization[J]. Soft Computing, 2017, 21(14): 4111–4140. doi: 10.1007/s00500-016-2060-y

BOLUFé-R?HLER A, FIOL-GONZáLEZ S, and CHEN S. A minimum population search hybrid for large scale global optimization[C]. Proceedings of 2015 IEEE Congress on Evolutionary Computation, Sendai, Japan, 2015: 1958–1965. doi: 10.1109/CEC.2015.7257125.

梁靜, 劉睿, 于坤杰, 等. 求解大規(guī)模問題協(xié)同進(jìn)化動(dòng)態(tài)粒子群優(yōu)化算法[J]. 軟件學(xué)報(bào), 2018, 29(9): 2595–2605. doi: 10.13328/j.cnki.jos.005398

LIANG Jing, LIU Rui, YU Kunjie, et al. Dynamic multi-swarm particle swarm optimization with cooperative coevolution for large scale global optimization[J]. Journal of Software, 2018, 29(9): 2595–2605. doi: 10.13328/j.cnki.jos.005398

羅家祥, 倪曉曄, 胡躍明. 融合多種搜索策略的差分進(jìn)化大規(guī)模優(yōu)化算法[J]. 華南理工大學(xué)學(xué)報(bào): 自然科學(xué)版, 2017, 45(3): 97–103. doi: 10.3969/j.issn.1000-565X.2017.03.014

LUO Jiaxiang, NI Xiaoye, and HU Yueming. A hybrid differential evolution algorithm with multiple search strategies for large-scale optimization[J]. Journal of South China University of Technology:Natural Science Edition, 2017, 45(3): 97–103. doi: 10.3969/j.issn.1000-565X.2017.03.014

MIRJALILI S and LEWIS A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95: 51–67. doi: 10.1016/j.advengsoft.2016.01.008

龍文, 蔡紹洪, 焦建軍, 等. 求解大規(guī)模優(yōu)化問題的改進(jìn)鯨魚優(yōu)化算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2017, 37(11): 2983–2994. doi: 10.12011/1000-6788(2017)11-2983-12

LONG Wen, CAI Shaohong, JIAO Jianjun, et al. Improved whale optimization algorithm for large scale optimization problems[J]. Systems Engineering-Theory &Practice, 2017, 37(11): 2983–2994. doi: 10.12011/1000-6788(2017)11-2983-12

MIRJALILI S, MIRJALILI S M, and LEWIS A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46–61. doi: 10.1016/j.advengsoft.2013.12.007

姜天華. 混合灰狼優(yōu)化算法求解柔性作業(yè)車間調(diào)度問題[J]. 控制與決策, 2018, 33(3): 503–508. doi: 10.13195/j.kzyjc.2017.0124

JIANG Tianhua. Flexible job shop scheduling problem with hybrid grey wolf optimization algorithm[J]. Control and Decision, 2018, 33(3): 503–508. doi: 10.13195/j.kzyjc.2017.0124

梁靜, 劉睿, 瞿博陽, 等. 進(jìn)化算法在大規(guī)模優(yōu)化問題中的應(yīng)用綜述[J]. 鄭州大學(xué)學(xué)報(bào): 工學(xué)版, 2018, 39(3): 15–21. doi: 10.13705/j.issn.1671-6833.2017.06.016

LIANG Jing, LIU Rui, QU Boyang, et al. A survey of evolutionary algorithms for large scale optimization problem[J]. Journal of Zhengzhou University:Engineering Science, 2018, 39(3): 15–21. doi: 10.13705/j.issn.1671-6833.2017.06.016

MIRJALILI S, MIRJALILI S M, and HATAMLOU A. Multi-verse optimizer: A nature-inspired algorithm for global optimization[J]. Neural Computing and Applications, 2016, 27(2): 495–513. doi: 10.1007/s00521-015-1870-7

趙世杰, 高雷阜, 徒君, 等. 耦合橫縱向個(gè)體更新策略的改進(jìn)MVO算法[J]. 控制與決策, 2018, 33(8): 1422–1428. doi: 10.13195/j.kzyjc.2017.0441

ZHAO Shijie, GAO Leifu, TU Jun, et al. Improved multi verse optimizer coupling horizontal-and-vertical individual updated strategies[J]. Control and Decision, 2018, 33(8): 1422–1428. doi: 10.13195/j.kzyjc.2017.0441

CHOPRA N and SHARMA J. Multi-objective optimum load dispatch using Multi-verse optimization[C]. Proceedings of the 2016 IEEE 1st International Conference on Power Electronics, Intelligent Control and Energy Systems, Delhi, India, 2016: 1–5.

HU Cong, LI Zhi, ZHOU Tian, et al. A multi-verse optimizer with levy flights for numerical optimization and its application in test scheduling for network-on-chip[J]. PLOS One, 2016, 11(12): e0167341. doi: 10.1371/journal.pone.0167341

FARIS H, ALJARAH I, and MIRJALILI S. Training feedforward neural networks using multi-verse optimizer for binary classification problems[J]. Applied Intelligence, 2016, 45(2): 322–332. doi: 10.1007/s10489-016-0767-1

JANGIR P, PARMAR S A, TRIVEDI I N, et al. A novel hybrid particle swarm optimizer with multi verse optimizer for global numerical optimization and optimal reactive power dispatch problem[J]. Engineering Science and Technology, An International Journal, 2017, 20(2): 570–586. doi: 10.1016/j.jestch.2016.10.007

ALI E E, EL-HAMEED M A, EL-FERGANY A A, et al. Parameter extraction of photovoltaic generating units using multi-verse optimizer[J]. Sustainable Energy Technologies and Assessments, 2016, 17: 68–76. doi: 10.1016/j.seta.2016.08.004

MIRJALILI S. Dragonfly algorithm: A new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems[J]. Neural Computing and Applications, 2016, 27(4): 1053–1073. doi: 10.1007/s00521-015-1920-1

ASKARZADEH A. A novel metaheuristic method for solving constrained engineering optimization problems: Crow search algorithm[J]. Computers & Structures, 2016, 169: 1–12. doi: 10.1016/j.compstruc.2016.03.001

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)