基于空间学习和情感追踪的多模多目标群搜索算法

丁亚丹; 冯翔; 虞慧群

doi:10.14135/j.cnki.1006-3080.20201022003

基于空间学习和情感追踪的多模多目标群搜索算法

doi: 10.14135/j.cnki.1006-3080.20201022003

丁亚丹^1,,
冯翔^{1, 2, ,},
虞慧群^{1, 2}

1.
华东理工大学信息科学与工程学院，上海 200237
2.
上海智慧能源工程技术研究中心，上海 200237

基金项目: 国家自然科学基金（61772200；61772201，61602175）；上海市浦江人才计划（17PJ1401900）；上海市经信委“信息化发展专项资金”（201602008）

详细信息

作者简介:
丁亚丹（1997-），硕士生，主要研究方向为演化计算、人工智能。E-mail：dorisdingyd@126.com

通讯作者:
冯　翔，E-mail：xfeng@ecust.edu.cn

中图分类号: TP18
计量
- 文章访问数: 616
- HTML全文浏览量: 453
- PDF下载量: 14
- 被引次数: 0
出版历程
- 收稿日期: 2020-10-22
- 网络出版日期: 2021-01-07

A Spatial Learning Based SGSO with Emotional Tracking for Multimodal Multi-objective Optimization

DING Yadan^1
,,
FENG Xiang^{1, 2
, ,},
YU Huiqun^{1, 2}

1.
School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China
2.
Shanghai Engineering Research Center of Smart Energy, Shanghai 200237, China

摘要

摘要: 为了解决多模态多目标优化问题，寻找与帕累托最优解等效的所有解，通过在基本的群搜索算法中引入社会行为，提出了一种新颖的基于空间学习机制和情感追踪行为的社会群搜索优化算法（MMO_LTSGSO）。首先，建立空间学习机制，根据学习到的个体自身位置与最佳个体位置的实时信息，对种群分布状态（离散态、聚合态）进行决策。当种群处于离散态时，采用追随和游走的方式增强算法空间探索能力；随着优化过程的进行，个体彼此影响交互，空间距离逐渐减小，此时种群逐渐聚合，采用动态步长的搜索策略更新个体位置，能实时勘探最优解周围的解，加快算法的收敛速度。其次，引入了情感因子，使一定的个体沿其偏好方向进行情感追踪移动行为，防止算法陷入停滞状态，提高算法求解精度；采用特殊的拥挤距离计算方式和引导进化策略保证算法在决策空间和目标空间的双重多样性。最后，从理论上证明了该算法的收敛性。使用15个多模态多目标优化测试基准函数验证算法的性能，并将其与现有的几个多模多目标优化算法进行性能对比，实验结果验证了本文算法能够有效求解多模多目标优化问题。
- 空间学习 /
- 情感追踪 /
- 群搜索算法 /
- 情感因子 /
- 多模多目标优化
Abstract: In order to solve the multimodal multi-objective optimization problem and find all solutions equivalent to the Pareto optimal solution, this paper proposes a novel group search optimization algorithm (MMO_LTSGSO) based on spatial learning mechanism and emotion tracking behavior by introducing social behavior into the basic group search algorithm. Firstly, a spatial learning mechanism is established and the decision of the population distribution state (discrete state and concentrated state) is made according to the real-time information of the learned individual's own position and the best individual position. When the population is in a discrete state, the following and wandering way is adopted to enhance the space exploration ability of the algorithm. With the optimization process, individuals interact with each other, and the spatial distance gradually decreases. At this time, the population gradually aggregates, the dynamic step search strategy is used to update the individual position, which can explore the solution around the optimal solution in real time and accelerate the convergence speed of the algorithm. Secondly, in order to prevent the algorithm from falling into stagnation and improve the accuracy of the algorithm, the emotion factor is introduced to make certain individuals track their moving behavior along their preferred direction. Then, special congestion distance calculation and guided evolution strategy are used to ensure the diversity of the algorithm in decision space and target space. Finally, the convergence of the algorithm is proved theoretically, and its performance is verified via 15 multimodal multi-objective optimization test benchmark functions, and is also compared with several existing multimodal multi-objective optimization algorithms. It is shown via the experiments results that the proposed algorithm can effectively solve multimodal multi-objective optimization problems.
- spatial learning /
- emotion tracking /
- group search algorithm /
- emotion factor /
- multimodal multi-objective optimization

HTML全文

图 1 解在决策空间和目标空间的分布

Figure 1. Distribution of solutions in decision space and target space

下载: 全尺寸图片幻灯片

图 2 3种搜索偏好行为

Figure 2. Three search preference behaviors

下载: 全尺寸图片幻灯片

图 3 情感因子追踪行为机制

Figure 3. Affective factor tracking behavior mechanism

下载: 全尺寸图片幻灯片

图 4 特殊的排序方式

Figure 4. Special sorting method

下载: 全尺寸图片幻灯片

图 5 MMO_LTSGSO在15个测试函数上的求得的PS与真实PS

Figure 5. The obtained PS by MMO_LTSGSO and the true PS on 15 test functions

下载: 全尺寸图片幻灯片

图 6 5个算法在15个测试函数上的Friedman排名

Figure 6. Friedman ranks of the optimization comprehensive performance for the five algorithms

下载: 全尺寸图片幻灯片

表 1 测试函数的多模性质

Table 1. Multimodal features of the test functions

Function	Number of PS	Overlap in every dimension
MMF1	2	No
MMF2	2	No
MMF3	2	Yes
MMF4	4	No
MMF5	4	No
MMF6	4	Yes
MMF7	2	No
MMF8	4	No
MMF9	2	No
MMF10	2(1 Global+1 Local)	No
MMF11	2(1 Global+1 Local)	No
MMF12	8(4 Global+4 Local)	Yes
SYM-PART simple	9	Yes
SYM-PART rotate	9	Yes
Omni-test(n=3)	27	Yes

下载: 导出CSV

表 2 5个算法在15个多模多目标测试函数上的1/PSP值

Table 2. 1/PSP value of five algorithms on 15 multimodal multi-objective test functions

Test functions	1/PSP（mean±std）
Test functions	MMO_LTSGSO	MO_Ring_PSO_SCD	DN_NSGAII	MMOEA_GD	MMOPIO
MMF1	0.0411±0.0013	0.0455±0.0019	0.0741±0.0200	0.0436±0.0028	0.0361±0.0018
MMF2	0.0177±0.0059	0.0283±0.0120	0.0577±0.1301	0.011±0.0044	0.0267±0.0065
MMF3	0.0148±0.0020	0.0223±0.0087	0.0477±0.0302	0.022±0.0048	0.0175±0.0054
MMF4	0.0222±0.0022	0.0251±0.0020	0.0554±0.0181	0.0217±0.0011	0.0195±0.0027
MMF5	0.0743±0.0051	0.0810±0.0041	0.1517±0.0198	0.0747±0.0032	0.0745±0.0048
MMF6	0.0658±0.0038	0.0679±0.0043	0.1143±0.0170	0.0660±0.0023	0.0658±0.0060
MMF7	0.0204±0.0008	0.0232±0.0017	0.0366±0.0095	0.0205±0.0021	0.0158±0.0017
MMF8	0.0621±0.0125	0.0598±0.0047	0.1236±0.1415	0.0590±0.0061	0.0743±0.0112
MMF9	0.0054±0.0003	0.0070±0.0004	0.0135±0.0081	0.0056±0.0002	0.0025±0.0001
MMF10	0.1599±1.5610	0.1029±0.0207	0.1030±3.1331	0.1118±0.1020	1.8053±2.2440
MMF11	0.1880±0.5616	0.1884±0.3425	1.4972±0.1490	0.1889±0.4118	1.6055±0.3832
MMF12	0.1428±0.5234	0.1433±0.5050	0.1954±0.6892	0.1731±0.5497	1.6757±0.4923
SYM_PART_simple	0.0777±0.0140	0.1443±0.0371	1.1423±1.3414	0.1248±0.0148	0.0778±0.0073
SYM_PART_rotated	0.0947±0.0190	0.1560±0.0459	2.2009±11.424	0.1351±0.0195	0.2210±0.3609
Omni_test	0.0870±0.0258	0.3086±0.0798	1.2623±0.3609	0.9491±0.0123	0.3950±0.0598

下载: 导出CSV

表 3 5个算法在15个多模多目标测试函数上的1/Hv值

Table 3. 1/Hv value of five algorithms on 15 multimodal multi-objective test functions

Test functions	1/Hv（mean±std）
Test functions	MMO_LTSGSO	MO_Ring_PSO_SCD	DN_NSGAII	MMOEA_GD	MMOPIO
MMF1	1.1462±0.0002	1.1480±0.0003	1.1481±0.0015	1.1488±0.0035	1.1459±0.0004
MMF2	1.1629±0.0036	1.1707±0.0097	1.1590±0.0273	1.1967±0.0190	1.1686±0.0030
MMF3	1.1630±0.0032	1.1647±0.0060	1.1633±0.0177	1.1678±0.0131	1.1657±0.0044
MMF4	1.8552±0.0012	1.8585±0.0019	1.8567±0.0007	1.8594±0.0081	1.8556±0.0012
MMF5	1.1459±0.0003	1.1476±0.0006	1.1470±0.0013	1.1471±0.0041	1.1455±0.0003
MMF6	1.1461±0.0004	1.1476±0.0012	1.1475±0.0008	1.1462±0.0219	1.1463±0.0005
MMF7	1.1462±0.0004	1.1475±0.0004	1.1480±0.0012	1.1463±0.0011	1.1430±0.0001
MMF8	2.3752±0.0113	2.3889±0.0361	2.3762±0.0032	2.3834±0.0061	2.3756±0.0019
MMF9	0.1032±0.0003	0.1033±0.0003	0.1033±0.0003	0.1035±0.0002	0.1033±0.0009
MMF10	0.0777±0.0007	0.0791±0.0006	0.0778±0.0030	0.0820±0.0034	0.0779±0.0009
MMF11	0.0689±0.0001	0.0690±0.0003	0.0689±0.0014	0.0690±0.0001	0.0671±0.0001
MMF12	0.6360±0.0002	0.6373±0.0011	0.6357±0.0562	0.6596±0.0665	0.6368±0.0003
SYM_PART_simple	0.0601±0.0007	0.0604±0.0006	0.0601±0.0001	0.0591±0.0094	0.0601±0.0001
SYM_PART_rotated	0.0601±0.0001	0.0605±0.0007	0.0601±0.0002	0.0699±0.0091	0.0602±0.0002
Omni_test	0.0189±0.0002	0.0190±0.0001	0.0189±0.0008	0.0288±0.0008	0.0190±0.0004

下载: 导出CSV

表 4 5个优化算法在决策空间和目标空间的平均排名

Table 4. Average ranking of five optimization algorithms on decision space and objective space

Algorithim	1/PSP	1/Hv	Comprehensive
MMO_LTSGSO	1.87	1.53	1.7
MO_Ring_PSO_SCD	3.47	3.93	3.7
DN_NSGAII	4.47	2.73	3.6
MMOEA_GD	2.73	4.13	3.43
MMOPIO	2.47	2.67	2.57

下载: 导出CSV

参考文献(25)

[1]	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017
[2]	ZITZLER E, LAUMANNS M, THIELE L. SPEA2: Improving the strength Pareto evolutionary algorithm[C]//Fifth Conference on Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Greece: IEEE, 2001: 95-100.
[3]	ZHANG Q, LI H. 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
[4]	COELLO COELLO C A, LECHUGA M S. MOPSO: A proposal for multiple objective particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computation. USA: IEEE, 2002: 1051-1056.
[5]	YUE C T, QU B Y, LIANG J. A multi-objective particle swarm optimizer using ring topology for solving multimodal multi-objective problems[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(5): 805-817. doi: 10.1109/TEVC.2017.2754271
[6]	LIANG J, YUE C T, QU B Y. Multimodal multi-objective optimization: A preliminary study[C]//2016 IEEE Congress on Evolutionary Computation (CEC). Canada: IEEE, 2016: 2454-2461.
[7]	KERSCHKE P, GRIMME C. An expedition to multimodal multi-objective optimization landscapes[C]//International Conference on Evolutionary Multi-Criterion Optimization. Germany: Springer, 2017: 329-343.
[8]	LIU Y, YEN G G, GONG D. A multi-modal multi-objective evolutionary algorithm using two-archive and recombination strategies[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(4): 660-674. doi: 10.1109/TEVC.2018.2879406
[9]	LIANG J, XU W W, YUE C T. Multimodal multiobjective optimization with differential evolution[J]. Swarm and Evolutionary Computation, 2019, 44: 1028-1059. doi: 10.1016/j.swevo.2018.10.016
[10]	HU Y, WANG J, LIANG J. A self-organizing multimodal multi-objective pigeon-inspired optimization algorithm[J]. Information Sciences, 2019, 62: 1-17.
[11]	YU K J, LIANG J J, QU B Y. Multiple learning backtracking search algorithm for estimating parameters of photovoltaic models[J]. Applied Energy, 2018, 226: 408-422. doi: 10.1016/j.apenergy.2018.06.010
[12]	LIANG J, GUO Q Q, YUE C T. et al. A Self-organizing multi-objective particle swarm optimization algorithm for multimodal multi-objective problems[C]//International Conference on Swarm Intelligence. UK: Springer, 2018: 550-560.
[13]	LYNN N, SUGANTHAN P N. Heterogeneous comprehensive learning particles warm optimization with enhanced exploration and exploitation[J]. Swarm and Evolutionary Computation, 2015, 24: 11-24. doi: 10.1016/j.swevo.2015.05.002
[14]	LYNN N, SUGANTHAN P N. Ensemble particle swarm optimizer[J]. Applied Soft Computing, 2017, 55: 533-548. doi: 10.1016/j.asoc.2017.02.007
[15]	QU B Y, SUGANTHAN P N, DAS S. A Distance-based locally informed particle swarm model for multimodal optimization[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(3): 387-402. doi: 10.1109/TEVC.2012.2203138
[16]	YAN L, LI G S, JIAO Y C. A performance enhanced niching multi-objective bat algorithm for multimodal multi-objective problems[C]// 2019 IEEE Congress on Evolutionary Computation (CEC). New Zealand: IEEE, 2019: 1275-1282.
[17]	FAN Q Q, YAN X F. Solving multimodal multiobjective problems through zoning search[C]// IEEE Transactions on Systems, Man, and Cybernetics: Systems. USA: IEEE, 2019: 1-12.
[18]	SHI R Z, LIN W, LIN Q Z. Multimodal multi-objective optimization using a density-based one-by-one update strategy[C]// 2019 IEEE Congress on Evolutionary Computation (CEC). New Zealand: IEEE, 2019: 295-301.
[19]	MAITY K, SENGUPTA R, SHA S. MM-NAEMO: Multimodal neighborhood-sensitive archived evolutionary many-objective optimization algorithm[C]//IEEE Congress on Evolutionary Computation. USA: IEEE, 2019: 286-294.
[20]	JI J Y, YU W J, CHEN W N. Solving multimodal optimization problems through a multiobjective optimization approach[C]//2017 Seventh International Conference on Information Science and Technology (ICIST). Vietnam: IEEE, 2017: 458-463.
[21]	CHENG R, JIN Y C, 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
[22]	FAN Q, LI N, ZHANG Y, et al. Zoning search using a hyper-heuristic algorithm[J]. Science China Information Sciences, 2019, 62(9): 1869-1919.
[23]	LIU X F, ZHAN Z H, GAO Y, et al. Coevolutionary particle swarm optimization with bottleneck objective learning strategy for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(4): 587-602. doi: 10.1109/TEVC.2018.2875430
[24]	FENG X, XU H Y, WANG Y B, et al. The social team building optimization algorithm[J]. Soft Computer, 2019, 23(15): 6533-6554. doi: 10.1007/s00500-018-3303-x
[25]	MODLMEIER A P, LASKOWSKI K L, Brittingham H A, et al. Adult presence augments juvenile collective foraging in social spiders[J]. Animal Behavior, 2015, 109: 9-14. doi: 10.1016/j.anbehav.2015.07.033