基于分解和支配關(guān)系的超多目標(biāo)進(jìn)化算法

趙輝; 王天龍; 劉衍舟; 黃橙; 張?zhí)祢U

doi:10.11999/JEIT190589

基于分解和支配關(guān)系的超多目標(biāo)進(jìn)化算法

doi: 10.11999/JEIT190589 cstr: 32379.14.JEIT190589

1.
重慶郵電大學(xué)通信與信息工程學(xué)院重慶 400065
2.
信號(hào)與信息處理重慶市重點(diǎn)實(shí)驗(yàn)室重慶 400065

基金項(xiàng)目: 國家自然科學(xué)基金(61671095)

詳細(xì)信息

作者簡(jiǎn)介:
趙輝：女，1980年生，教授，博士生導(dǎo)師，研究方向?yàn)樯羁展馔ㄐ?、信?hào)理論與信息處理、信號(hào)與圖像處理

王天龍：男，1994年生，碩士，研究方向?yàn)樾盘?hào)與圖像處理、進(jìn)化計(jì)算、多目標(biāo)優(yōu)化

劉衍舟：男，1994年生，碩士，研究方向?yàn)樾盘?hào)與圖像處理

黃橙：男，1993年生，碩士，研究方向?yàn)樾盘?hào)與圖像處理

張?zhí)祢U：男，1971年生，教授，博士生導(dǎo)師，研究方向?yàn)闊o線通信的智能信號(hào)處理、通信抗干擾和信息對(duì)抗

通訊作者:
趙輝　zhaohui@cqupt.edu.cn

中圖分類號(hào): TP391.4
計(jì)量
- 文章訪問數(shù): 3373
- HTML全文瀏覽量: 1206
- PDF下載量: 95
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-08-05
- 修回日期: 2020-02-13
- 網(wǎng)絡(luò)出版日期: 2020-03-25
- 刊出日期: 2020-08-18

Decomposition and Dominance Relation Based Many-objective Evolutionary Algorithm

1.
School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
2.
Chongqing Key Laboratory of Signal and Information Processing, Chongqing 400065, China

Funds: The National Natural Science Foundation of China (61671095)

摘要

摘要:
近年來，超多目標(biāo)優(yōu)化問題(MaOPs)成為了進(jìn)化計(jì)算領(lǐng)域的研究熱點(diǎn)。然而，在處理各種優(yōu)化問題中，如何有效地平衡收斂性和多樣性仍是一個(gè)難題。為了解決上述的問題，該文提出了一種基于分解和支配關(guān)系的超多目標(biāo)進(jìn)化算法(DdrEA)。首先利用權(quán)重向量把整個(gè)種群分解為一組子種群，這些子種群將進(jìn)行協(xié)同優(yōu)化；然后利用角度和角度支配關(guān)系計(jì)算子種群內(nèi)每個(gè)解的值；最后根據(jù)適應(yīng)度值進(jìn)行精英選擇，即在每個(gè)子空間內(nèi)選取適應(yīng)度值最小的解作為精英解進(jìn)入下一代。DdrEA通過與當(dāng)前較優(yōu)的NSGA-II/AD, RVEA, MOMBI-II等多個(gè)超多目標(biāo)進(jìn)化算法進(jìn)行實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)結(jié)果表明該文算法性能明顯優(yōu)于對(duì)比算法，能夠有效平衡種群的收斂性和多樣性。
- 超多目標(biāo)優(yōu)化 /
- 分解 /
- 支配關(guān)系 /
- 進(jìn)化算法
Abstract:
In recent year, the Many-objective Optimization Problems (MaOPs) have become an increasingly hot research area in evolutionary computation. However, it is still a difficult problem to achieve a good balance between convergence and diversity on solving various kinds of MaOPs. To alleviate this issue mentioned above, a Decomposition and dominance relation based many-objective Evolutionary Algorithm(DdrEA) is proposed in this paper. Firstly, the population is decomposed into numbers of sub-populations by using a set of uniform weight vectors, in which they are optimized in a cooperative manner. Then, the fitness value of solution in each sub-population is calculated by angle dominance relation and angle. Finally, elite selection strategy is performed according to its corresponding fitness value. That is, in each subspace, the solution with the smallest fitness value is selected as the elite solution to enter the next generation. Comparing with several high-dimensional and multi-objective evolutionary algorithms (NSGA-II/AD, RVEA, MOMBI-II), the experimental results show that the performance of the proposed algorithm DdrEA is better than that of the comparison algorithm, and the convergence and diversity of the population can be effectively balanced.
- Many-objective optimization /
- Decomposition /
- Dominance relation /
- Evolutionary algorithm

HTML全文

圖 1 兩個(gè)目標(biāo)下的角度支配準(zhǔn)則

下載: 全尺寸圖片幻燈片

圖 2 各算法在15目標(biāo)WFG1問題上獲得的結(jié)果

下載: 全尺寸圖片幻燈片

圖 3 各算法在10目標(biāo)WFG9問題上獲得的結(jié)果

下載: 全尺寸圖片幻燈片

表 1 DdrEA算法框架

輸入: N (種群規(guī)模)
輸出: P (最終種群)
(1) ${ V} = \operatorname{Uniform\;Reference\;Vector} (N)$;
(2) $P = \operatorname{RandomInitialize} (N)$;
(3) 　while 終止條件未滿足 do
(4) 　　${\rm{Pool} } = \operatorname{Bianry\;Tournament} (P)$;
(5) 　　$O = \operatorname{Variation} ({\rm{Pool}})$;
(6) 　　$P = \operatorname{Environmental\;Selection} (P \cup O,V,N)$;
(7) 　end while

下載: 導(dǎo)出CSV

表 2 環(huán)境選擇算法框架

輸入: P (合并后的種群), V (參考向量);
輸出: Q (下一代種群);
(1) /目標(biāo)值標(biāo)準(zhǔn)化/ 　(2) ${f_i}\;(p) = \dfrac{{{f_i}(p) - z_i^{{\rm{id}}}}}{{z_i^{{\rm{na}}} - z_i^{{\rm{id}}}}},\forall p \in P$;
(3) /種群分解/
(4) for $i = 1\;{\rm{to }}\left\| P \right\|$ do
(5) 　for $j = 1\;{\rm{to }}N$ do 　(6) 　　${\theta _{i,j} } = \arccos \dfrac{ { {f_i}\;(p) \cdot {v_j} } }{ {\left\\| { {f_i}\;(p)} \right\\|} }$;
(7) 　end for
(8) end for
(9) for $i = 1\;{\rm{to }}\left\| P \right\|$ do
(10) 　　$r = \arg \min {\theta _{i,j}},j \in \{ 1,2, ··· ,N\} $;
(11) 　　${\overline P _k} = {\overline P _k} \cup \{ {I_r}\} $;
(12) end for
(13) /精英選擇/
(14) 非支配排序獲得每個(gè)解的AD等級(jí);
(15) for $i = 1\;{\rm{to }}N$ do
(16) 　for $j = 1\;{\rm{to } }\left\| { { { {\overline P}_k} } } \right\|$ do
(17) 　　${\rm{fi}}{{\rm{t}}_{i,j}} = F_i^p + {\theta _{i,j}}$;
(18) 　end for
(19) end for
(20) for $i = 1\;{\rm{to }}N$ do
(21) 　$r = \arg \min {\rm{fi}}{{\rm{t}}_{i,j}}$
(22) 　$Q = Q \cup \{ {I_r}\} $
(23) end for

下載: 導(dǎo)出CSV

表 3 各算法在WFG測(cè)試集上獨(dú)立運(yùn)行30次的HV均值和標(biāo)準(zhǔn)差

測(cè)試問題	M	DdrEA	NSGA-II/AD	RVEA	MOMBI-II
WFG1	5	9.7500e-1 (3.88e-3)	9.7759e-1 (1.72e-3) +	9.9722e-1 (5.54e-4) +	9.4668e-1 (5.46e-2) =
	10	9.9821e-1 (4.94e-4)	9.9849e-1 (1.57e-4) +	9.9768e-1 (5.30e-4) –	9.9990e-1 (6.65e-5) +
	15	9.9960e-1 (2.23e-4)	9.9977e-1 (5.94e-5) +	9.9546e-1 (1.65e-2) –	9.9900e-1 (9.15e-4) –
WFG2	5	9.5980e-1 (4.39e-3)	9.8390e-1 (6.84e-4) +	9.9385e-1 (1.19e-3) +	9.9432e-1 (2.64e-3) +
	10	9.9548e-1 (1.94e-3)	9.9819e-1 (3.42e-4) +	9.8944e-1 (2.64e-3) –	9.9459e-1 (4.80e-3) =
	15	9.9516e-1 (3.28e-3)	9.9854e-1 (4.21e-4) +	9.7143e-1 (6.37e-3) –	9.4784e-1 (4.42e-2) –
WFG3	5	2.1343e-1 (1.95e-2)	2.4953e-1 (4.42e-3) +	1.5392e-1 (2.34e-2) –	9.1612e-2 (1.14e-3) –
	10	9.2805e-2 (1.72e-2)	7.7407e-2 (1.47e-2) –	0.0000e+0 (0.00e+0) –	8.8033e-2 (1.38e-2) =
	15	8.3502e-4 (3.18e-3)	5.6841e-4 (2.97e-3) =	0.0000e+0 (0.00e+0) =	0.0000e+0 (0.00e+0) =
WFG4	5	7.9321e-1 (6.31e-4)	6.4860e-1 (1.20e-3) –	7.9120e-1 (6.98e-4) –	7.9039e-1 (7.50e-3) =
	10	9.6871e-1 (4.54e-4)	8.3306e-1 (1.02e-3) –	9.5997e-1 (2.21e-3) –	9.2583e-1 (5.33e-2) –
	15	9.8842e-1 (4.27e-3)	9.0197e-1 (2.24e-3) –	9.7572e-1 (3.32e-3) –	6.5742e-1 (6.09e-2) –
WFG5	5	7.4375e-1 (4.53e-4)	5.9898e-1 (9.69e-4) –	7.4385e-1 (3.78e-4) =	7.1661e-1 (1.18e-2) –
	10	9.0472e-1 (2.50e-4)	7.6876e-1 (7.00e-4) –	9.0333e-1 (3.03e-4) –	8.2511e-1 (1.49e-2) –
	15	9.1756e-1 (2.50e-4)	8.2982e-1 (1.15e-3) –	9.1591e-1 (2.52e-4) –	3.0980e-1 (1.03e-1) –
WFG6	5	7.2159e-1 (1.32e-2)	5.8627e-1 (1.86e-2) –	7.2535e-1 (1.44e-2) =	7.2502e-1 (2.91e-2) =
	10	8.8790e-1 (1.79e-2)	7.4225e-1 (2.01e-2) –	8.7718e-1 (1.67e-2) –	8.6054e-1 (5.34e-2) –
	15	8.9955e-1 (2.46e-2)	7.9363e-1 (2.38e-2) –	7.2363e-1 (8.04e-2) –	6.2650e-1 (5.72e-2) –
WFG7	5	7.9404e-1 (5.38e-4)	6.4353e-1 (1.20e-3) –	7.8991e-1 (5.70e-4) –	7.8952e-1 (8.36e-3) –
	10	9.6965e-1 (2.60e-4)	8.2831e-1 (4.30e-3) –	9.5835e-1 (1.80e-3) –	9.6818e-1 (3.92e-3) =
	15	9.9072e-1 (9.04e-4)	8.9903e-1 (1.10e-3) –	9.8234e-1 (5.24e-3) –	7.5033e-1 (8.01e-2) –
WFG8	5	6.8107e-1 (1.14e-3)	4.6230e-1 (5.93e-3) –	6.7438e-1 (2.36e-3) –	3.1772e-1 (6.41e-3) –
	10	8.7577e-1 (6.90e-3)	6.0416e-1 (6.06e-2) –	8.3098e-1 (8.86e-2) =	6.4422e-1 (1.85e-2) –
	15	8.9925e-1 (1.56e-3)	7.6855e-1 (6.04e-2) –	7.7368e-1 (1.23e-1) –	5.1932e-1 (7.33e-2) –
WFG9	5	7.4084e-1 (4.55e-2)	6.3546e-1 (3.05e-3) –	7.5200e-1 (5.64e-3) =	5.5025e-1 (5.88e-2) –
	10	9.0376e-1 (4.59e-2)	8.1230e-1 (7.64e-3) –	8.8746e-1 (3.28e-2) –	8.0514e-1 (1.40e-2) –
	15	9.1408e-1 (3.94e-2)	8.4483e-1 (3.67e-2) –	8.3486e-1 (5.14e-2) –	2.6009e-1 (3.09e-2) –
	$ + \;/\; - \;/\; = $		7/19/1	2/20/5	2/18/7

下載: 導(dǎo)出CSV

表 4 各算法在DTLZ測(cè)試集上獨(dú)立運(yùn)行30次的HV均值和標(biāo)準(zhǔn)差

測(cè)試問題	M	DdrEA	NSGA-II/AD	RVEA	MOMBI-II
DTLZ1	5	8.4928e-1 (4.56e-2)	9.0703e-1 (4.42e-3) +	9.7490e-1 (1.72e-4) +	9.7461e-1 (2.59e-4) +
	10	9.8958e-1 (5.26e-3)	9.8084e-1 (1.48e-3) –	9.9968e-1 (1.73e-5) +	9.6198e-1 (3.15e-2) –
	15	9.1625e-1 (6.21e-2)	9.9583e-1 (3.87e-4) +	9.9990e-1 (4.62e-5) +	9.0337e-1 (3.90e-2) –
DTLZ2	5	7.9489e-1 (2.85e-4)	7.1691e-1 (5.66e-3) –	7.9479e-1 (3.56e-4) =	7.9449e-1 (5.39e-4) –
	10	9.7092e-1 (2.45e-4)	9.0347e-1 (4.42e-3) –	9.6974e-1 (1.49e-4) –	9.7085e-1 (2.13e-4) =
	15	9.9160e-1 (1.05e-4)	9.5411e-1 (3.00e-3) –	9.9109e-1 (2.99e-4) –	8.8008e-1 (6.31e-2) –
DTLZ3	5	6.2295e-1 (4.78e-2)	7.1455e-1 (7.51e-3) =	7.9246e-1 (2.06e-3) +	7.9042e-1 (2.58e-3) +
	10	8.8458e-1 (2.77e-2)	8.9986e-1 (5.59e-3) =	9.6952e-1 (3.56e-4) +	8.2910e-1 (9.36e-2) –
	15	7.0985e-1 (5.92e-2)	9.4928e-1 (5.01e-3) +	9.9072e-1 (2.96e-4) +	5.5538e-1 (5.08e-2) –
DTLZ4	5	7.9479e-1 (4.40e-4)	7.2830e-1 (5.61e-3) –	7.8505e-1 (2.91e-2) =	7.8426e-1 (2.85e-2) –
	10	9.7157e-1 (2.23e-4)	9.1475e-1 (4.07e-3) –	9.6980e-1 (1.53e-4) –	9.7226e-1 (2.24e-3) +
	15	9.9206e-1 (1.14e-4)	9.6070e-1 (2.35e-3) –	9.9076e-1 (1.18e-3) –	9.9044e-1 (1.51e-3) –
DTLZ5	5	1.0799e-1 (3.39e-3)	1.2935e-1 (3.74e-4) +	1.0483e-1 (2.04e-3) –	9.0959e-2 (2.73e-4) –
	10	9.1644e-2 (1.16e-3)	1.0062e-1 (2.77e-4) +	9.0893e-2 (1.10e-4) –	9.1359e-2 (7.19e-4) =
	15	9.1168e-2 (3.89e-4)	9.4858e-2 (3.18e-4) +	9.0648e-2 (3.24e-3) =	9.1206e-2 (3.78e-4) =
DTLZ6	5	1.0371e-1 (5.39e-3)	1.2924e-1 (2.68e-4) +	1.0340e-1 (1.29e-2) =	9.0959e-2 (2.53e-4) –
	10	9.1619e-2 (8.82e-4)	1.0053e-1 (2.70e-4) +	9.1873e-2 (8.07e-4) =	9.2808e-2 (1.11e-3) +
	15	9.1147e-2 (5.02e-4)	9.4877e-2 (2.90e-4) +	8.7721e-2 (1.72e-2) =	9.1664e-2 (5.93e-4) +
DTLZ7	5	2.4710e-1 (5.77e-3)	2.3300e-1 (4.51e-3) –	2.0265e-1 (3.05e-3) –	2.4292e-1 (5.42e-3) –
	10	1.9578e-1 (2.23e-3)	1.9180e-1 (3.40e-3) –	1.4878e-1 (2.05e-2) –	1.5877e-1 (1.00e-2) –
	15	1.6487e-1 (4.21e-3)	1.5882e-1 (5.21e-3) –	5.8918e-2 (5.77e-2) –	1.2108e-1 (1.74e-3) –
	$ + \;/\; - \;/\; = $		9/10/2	6/9/6	5/13/3

下載: 導(dǎo)出CSV

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

ZHOU Aimin, QU Boyang, LI Hui, et al. Multiobjective evolutionary algorithms: A survey of the state of the art[J]. Swarm and Evolutionary Computation, 2011, 1(1): 32–49. doi: 10.1016/j.swevo.2011.03.001

賴文星, 鄧忠民, 張?chǎng)谓? 基于多目標(biāo)優(yōu)化NSGA2改進(jìn)算法的結(jié)構(gòu)動(dòng)力學(xué)模型確認(rèn)[J]. 計(jì)算力學(xué)學(xué)報(bào), 2018, 35(6): 669–674. doi: 10.7511/jslx20170828004

LAI Wenxing, DENG Zhongmin, and ZHANG Xinjie. Structural dynamics model validation based on NSGA2 improved algorithm[J]. Chinese Journal of Computational Mechanics, 2018, 35(6): 669–674. doi: 10.7511/jslx20170828004

LI Bingdong, LI Jinlong, TANG Ke, et al. Many-objective evolutionary algorithms: A survey[J]. ACM Computing Surveys, 2015, 48(1): 1–35. doi: 10.1145/2792984

HE Zhenan, YEN G G, and ZHANG Jun. Fuzzy-based Pareto optimality for many-objective evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(2): 269–285. doi: 10.1109/TEVC.2013.2258025

YANG Shengxiang, LI Miqing, LIU Xiaohui, et al. A grid-based evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(5): 721–736. doi: 10.1109/TEVC.2012.2227145

ZHANG Qingfu and LI Hui. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712–731. doi: 10.1109/TEVC.2007.892759

鄭金華, 喻果, 賈月. 基于權(quán)重迭代的偏好多目標(biāo)分解算法解決參考點(diǎn)對(duì)算法影響的研究[J]. 電子學(xué)報(bào), 2016, 44(1): 67–76. doi: 10.3969/j.issn.0372-2112.2016.01.011

ZHENG Jinhua, YU Guo, and JIA Yue. Research on MOEA/D based on user-preference and alternate weight to solve the effect of reference point on multi-objective algorithms[J]. Acta Electronica Sinica, 2016, 44(1): 67–76. doi: 10.3969/j.issn.0372-2112.2016.01.011

BADER J and ZITZLER E. HypE: An algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary Computation, 2011, 19(1): 45–76. doi: 10.1162/EVCO_a_00009

CHENG Ran, JIN Yaochu, OLHOFER M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 773–791. doi: 10.1109/TEVC.2016.2519378

LIU Yuan, ZHU Ningbo, LI Kenli, et al. An angle dominance criterion for evolutionary many-objective optimization[J]. Information Sciences, 2020, 509: 376–399. doi: 10.1016/J.INS.2018.12.078

HUBAND S, HINGSTON P, BARONE L, et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(5): 477–506. doi: 10.1109/TEVC.2005.861417

DEB K, THIELE L, LAUMANNS M, et al. Scalable Test Problems for Evolutionary Multiobjective Optimization[M]. ABRAHAM A, JAIN L, and GOLDBERG R. Evolutionary Multiobjective Optimization. London: Springer, 2005: 105–145. doi: 10.1007/1-84628-137-7_6.

HERNáNDEZ GóMEZ R and COELLO COELLO C A. Improved metaheuristic based on the r2 indicator for many-objective optimization[C]. 2015 Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM, 2015: 679–686. doi: 10.1145/2739480.2754776.

DEB K. Multi-objective Optimisation Using Evolutionary Algorithms: An Introduction[M]. WANG L H, NG A H C, and DEB K. Multi-Objective Evolutionary Optimisation for Product Design and Manufacturing. London: Springer, 2011: 3–34. doi: 10.1007/978-0-85729-652-8_1.

DEB K and GOYAL M. A combined genetic adaptive search (GeneAS) for engineering design[J]. Journal of Computer Science and Informatics, 1996, 26: 30–45.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

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