A Spatial Learning Based SGSO with Emotional Tracking for Multimodal Multi-Objective Optimization
-
摘要: 为了解决多模态多目标优化问题,寻找与帕累托最优解等效的所有解,通过在基本的群搜索算法中引入社会行为,提出了一种新颖的基于空间学习机制和情感追踪行为的社会群搜索优化算法(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, and 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.
-
表 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 表 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) 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 表 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) 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 表 4 5个优化算法在决策空间和目标空间的平均排名
Table 4. Average ranking of five optimization algorithms on decision space and objective space
Algorithms 1/PSP 1/Hv Comprehensive MMO_LTSGSO 1.87 1.53 1.70 MO_Ring_PSO_SCD 3.47 3.93 3.70 DN_NSGAII 4.47 2.73 3.60 MMOEA_GD 2.73 4.13 3.43 MMOPIO 2.47 2.67 2.57 -
[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 com-prehensive 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 -