基于多指标精英个体博弈机制的多目标优化算法

doi:10.16182/j.issn1004731x.joss.21-1148

摘要/Abstract

摘要：

为了改善多目标优化算法的收敛性与优化解集的多样性，缓解种群在目标空间中的坍缩，提出一种基于多指标精英个体博弈机制的多目标优化算法。利用Pareto支配关系与多指标综合筛选精英个体。将带有K-means聚类的精英个体博弈机制与交叉变异策略融合，有效提升了算法的收敛性与多样性。对算法进行了详细的收敛性分析，证明了算法的收敛性。将8个代表性的比较算法在标准测试函数上进行解集指标对比并解决实际水泵调度问题，本文算法在收敛性与多样性上优于或持平其他比较算法，验证了本文算法的有效性，在一定程度上减小了种群在目标空间中坍缩的概率。

关键词: 多目标优化, 收敛性分析, 博弈机制, K-means聚类, 精英个体筛选

Abstract:

In order to improve the convergence of multi-objective optimization algorithm and the diversity of optimization solution set, and alleviate the flown down of population in target space, a multi-objective optimization algorithm based on multi-attribute elite individual game mechanism is proposed. This paper uses Pareto dominance relationship and multi-index to comprehensively screen elite individuals. The elite individual game mechanism with K-means clustering is integrated with cross and mutation strategy, which effectively improves the convergence and diversity of the algorithm. A detailed convergence analysis of the algorithm is performed to prove the convergence of the algorithm. Eight representative comparison algorithms are compared on the standard test function to solve the actual pump scheduling problem. The convergence and diversity of the algorithm in this paper are better than or equal to other comparison algorithms, verifying the effectiveness of the algorithm and reducing the probability of population flown down in the target space to a certain extent.

Key words: multi-objective optimization, convergence analysis, game mechanism, K-means clustering, elite individual screening

中图分类号:

TP301.6

王旭, 季伟东, 周国辉, 杨佳慧. 基于多指标精英个体博弈机制的多目标优化算法[J]. 系统仿真学报, 2023, 35(3): 494-514.

Xu Wang, Weidong Ji, Guohui Zhou, Jiahui Yang. Multi-objective Optimization Algorithm Based on Multi-index Elite Individual Game Mechanism[J]. Journal of System Simulation, 2023, 35(3): 494-514.

图/表 22

图1

图2

图3

图4

图5

图6

图7

表1

表2

表3

图8

图9

表4

图10

表5

表6

表7

表8

图11

表9

图12

表10

参考文献 34

1	Zhou A M, Qu B Y, Li H, et al. Multiobjective Evolutionary Algorithms: A Survey of the State of the Art[J]. Swarm and Evolutionary Computation (S2210-6502), 2011, 1(1): 32-49.
2	Zitzler E, Thiele L. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 1999, 3(4): 257-271.
3	Coello C A C, Pulido G T. A Micro-genetic Algorithm for Multi-objective Optimization[C]// EMO 2001. Zurich Switzerland: Springer, 2001: 126-140.
4	Zhang Q, Li H. MOEA/D: A Multi-objective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2007, 11(6): 712-731.
5	耿焕同, 周山胜, 韩伟民, 等. 基于自适应进化策略的MOEA/D算法[J]. 计算机工程与设计, 2019, 40(4): 1106-1113.
	Geng Huantong, Zhou Shansheng, Han Weimin, et al. MOEA/D Algorithm Based on Adaptive Evolutionary Strategy[J]. Computer Engineering and Design, 2019, 40(4): 1106-1113.
6	Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2002, 6(2): 182-197.
7	Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multi-objective Optimization[C]// Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Athens, Greece: EUROGEN, 2001: 95-100.
8	Knowles J D, Corne D W. Approximating the Non-dominated Front Using the Pareto Archive Evolution Strategy[J]. Evolutionary Computation (S1063-6560), 2000, 8(2): 149-172.
9	Bader J, Zitzler E. HypE: An Algorithm for Fast Hypervolume-based Many-objective Optimization[J]. Evolutionary Computation (S1063-6560), 2011, 19(1): 45-76.
10	Zitzler E, Kunzli S. Indicator-based Selection in Multiobjective Search[C]// 8th International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer-Verlag, 2004: 832-842.
11	Coello C A C, Lechuga M S. MOPSO: A Proposal for Multiple Objective Particle Swarm Optimization[C]// CEC'02: 2002 Congress on Evolutionary Computation. Washington, USA: IEEE, 2002: 1051-1056.
12	韩博文, 姚佩阳, 孙昱. 基于多目标MSQPSO算法的UAVS协同任务分配[J]. 电子学报, 2017, 45(8): 1856-1863.
	Han Bowen, Yao Peiyang, Sun Yu. UAVS Cooperative Task Allocation Based on Multi-objective MSQPSO Algorithm[J]. Acta Electronica Sinica, 2017, 45(8): 1856-1863.
13	张屹, 陆逸舟, 王帅, 等. 基于多源交配选择策略的重组算子与多目标优化研究[J]. 电子学报, 2021, 49(9): 1754-1760.
	Zhang Yi, Lu Yizhou, Wang Shuai, et al. Research on Reproduction Operator and Multi-objective Optimization Based on Multi-source Mating Selection Strategy[J]. Acta Electronica Sinica, 2021, 49(9): 1754-1760.
14	鲍毅, 戴波, 汪志华, 等. 基于灰狼算法的多目标智能家居负荷控制算法[J]. 系统仿真学报, 2019, 31(6): 1216-1222.
	Bao Yi, Dai Bo, Wang Zhihua, et al. Multi Objective Flexible Load Scheduling in Smart Home Based on Grey Wolf Algorithm[J]. Journal of System Simulation, 2019, 31(6): 1216-1222.
15	Yue C, Suganthan P N, Liang J, et al. Differential Evolution Using Improved Crowding Distance for Multimodal Multiobjective Optimization[J]. Swarm and Evolutionary Computation (S2210-6502), 2021, 62(9): 100849.
16	季伟东, 岳玉麒, 王旭, 等. 基于降维和聚类的大规模多目标自然计算方法[J]. 系统仿真学报, 2023, 35(1): 41-56.
	Ji Weidong, Yue Yuqi, Wang Xu, et al. Large-Scale Multi-objective Natural Computation Based on Dimensionality Reduction and Clustering[J]. Journal of System Simulation, 2023, 35(1): 41-56.
17	喻金平, 王伟, 巫光福, 等. 基于博弈机制的多目标粒子群优化算法[J].计算机工程与设计, 2020, 41(4): 964-971.
	Yu Jinping, Wang Wei, Wu Guangfu, et al. Game Mechanism Based Multi-objective Particle Swarm Optimization[J]. Computer Engineering and Design, 2020, 41(4): 964-971.
18	罗智勇, 朱梓豪, 谢志强, 等. 面向云计算的花朵差分授粉工作流多目标优化算法研究[J]. 电子学报, 2021, 49(3): 470-476.
	Luo Zhiyong, Zhu Zihao, Xie Zhiqiang, et al. A Multi-objective Workflow Scheduling Algorithm Based on Flower Pollination Cloud Environment[J]. Acta Electronica Sinica, 2021, 49(3): 470-476.
19	陈晓纪, 石川, 周爱民, 等. 混合个体选择机制的多目标进化算法[J]. 软件学报, 2019, 30(12): 3651-3664.
	Chen Xiaoji, Shi Chuan, Zhou Aimin, et al. Multiobjective Evolutionary Algorithm Based on Hybird Individual Selection Mechanism[J]. Journal of Software, 2019, 30(12): 3651-3664.
20	谢承旺, 张飞龙, 陆建波, 等. 一种多策略协同的多目标萤火虫算法[J]. 电子学报, 2019, 47(11): 2359-2367.
	Xie Chengwang, Zhang Feilong, Lu Jianbo, et al. Multi-objective Firefly Algorithm Based on Multiply Cooperative Strategies[J]. Acta Electronica Sinica, 2019, 47(11): 2359-2367.
21	张伟, 黄卫民. 基于种群分区的多策略自适应多目标粒子群算法[J]. 自动化学报, 2022, 48(10): 2585-2599.
	Zhang Wei, Huang Weimin. Multi-strategy Adaptive Multi-objective Particle Swarm Optimization Algorithm Based on Swarm Partition[J]. Acta Automatica Sinica, 2022, 48(10): 2585-2599.
22	张磊, 毕晓君, 王艳娇. 基于重新匹配策略的ε约束的多目标分解优化算法[J]. 电子学报, 2018, 46(5): 1032-1040.
	Zhang Lei, Bi Xiaojun, Wang Yanjiao. The ε Constrained Multi-objective Decomposition Optimization Algorithm Based on Re-matching Strategy[J]. Acta Electronica Sinica, 2018, 46(5): 1032-1040.
23	韩红桂, 阿音嘎, 张璐, 等. 自适应分解式多目标粒子群优化算法[J]. 电子学报, 2020, 48(7): 1245-1254.
	Han Honggui, Yinga A, Zhang Lu, et al. Adaptive Multiobjective Particle Swarm Optimization Based on Decomposition Archive[J]. Acta Electronica Sinica, 2020, 48(7): 1245-1254.
24	Cheng R, Jin Y. A Competitive Swarm Optimizer for Large Scale Optimization[J]. IEEE Transactions on Cybernetics (S2168-2267), 2015, 45(2): 191-205.
25	郑金华, 邹娟. 多目标进化优化[M]. 北京: 科学出版社, 2017: 96-97.
	Zheng Jinhua, Zou Juan. Multi-objective Evolutionary Optimization[M]. Beijing: Science Press, 2017: 96-97.
26	Deb K, Agrawal R. Simulated Binary Crossover for Continuous Search Space[J]. Complex Systems (S0891-2513), 1995, 9(2): 115-148.
27	Veldhuizen D, Lamont G B. Evolutionary Computation and Convergence to a Pareto Front[D]. California, USA: Stanford University, 1998.
28	Veldhuizen D. Multiobjective Evolutionary Algorithms: Classifications, Analyses and New Innovations[J]. Evolutionary Computation (S1063-6560), 1999 8(2): 125-147.
29	郑金华, 邹娟. 多目标进化优化[M]. 北京: 科学出版社, 2017: 86-87.
	Zheng Jinhua, Zou Juan. Multi-objective Evolutionary Optimization[M]. Beijing: Science Press, 2017: 86-87.
30	潘峰, 周倩, 李位星, 等. 标准粒子群优化算法的马尔科夫链分析[J]. 自动化学报, 2013, 39(4): 381-389.
	Pan Feng, Zhou Qian, Li Weixing, et al. Analysis of Standard Particle Swarm Optimization Algorithm Based on Markov Chain[J]. Acta Automatica Sinica, 2013, 39(4): 381-389.
31	Van Zyl J E, Savic D A, Walters G A. Operational Optimization of Water Distribution Systems Using a Hybrid Genetic Algorithm[J]. Journal of Water Resources Planning & Management (S0733-9496), 2004, 130(2): 160-170.
32	Czyzak P, Jaszkiewicz A. Pareto Simulated Annealing-A Metaheuristic Technique for Multiple-objective Combinatorial Optimization[J]. Journal of Multi-criteria Decision Analysis (S1057-9214), 1998, 7(1): 34-47.
33	Deb K. Multi-objective Genetic Algorithms: Problem Difficulties and Construction of Test Problems[J] Evolutionary Computation (S1063-6560), 1999, 7(3): 205-230.
34	Deb K, Thiele L, Laumanns M, et al. Evolutionary Multiobjective Optimization: Theoretical Advances and Applications[M]. Germany: Springer, 2005: 105-145.

测试函数	维度		真实PF样本数
测试函数	向量维度	目标数	真实PF样本数
ZDT1	30	2	1 000
ZDT2	30	2	500
ZDT3	30	2	136
ZDT4	10	2	200
ZDT6	10	2	2 992
DTLZ2	10	3	10 000
DTLZ4	10	3	4 000
DTLZ7	20	3	9 409

算法名称	算法参数
MOMEIG	w=0.5， c₁= c₂=1， P_C=0.7， P_M=1/n， η₁=2， η₂=5， k=7
NSGA-II	P_C=0.7， P_M=1/n， η₁=2， η₂=5
SPEA2	P_C=0.7， P_M=1/n， η₁=2， η₂=5
MOPSO	w =0.5， c₁= c₂=1
GMOPSO	w =0.5， c₁= c₂=1
AMOPSO-DA	w =0.5， c₁= c₂=1， d=100
pccsAMOPSO	p_archive=25， g_archive=100
MOFA-MCS	α=0.25， β₀=1， γ=1

测试函数	MOMEIG	MOMEIG-v1	MOMEIG-v2	MOMEIG-v3
ZDT1	1.322E-03	2.898E-03	4.461E-02	3.610E-03
ZDT2	1.129E-03	2.927E-03	2.580E-02	4.072E-03
ZDT3	4.389E-03	4.576E-03	2.805E-01	9.799E-03
ZDT4	2.072E+00	2.128E+00	2.512E+01	5.708E+00
ZDT6	9.855E-04	9.981E-04	9.427E-01	3.616E-03
DTLZ2	4.179E-02	4.405E-02	1.145E-01	7.244E-02
DTLZ4	4.512E-02	5.052E-02	1.551E-01	1.693E-01
DTLZ7	6.331E-02	7.836E-02	2.683E-01	6.812E-02

测试函数	IGD指标	MOMEIG	NSGA-II	SPEA2	MOEA/D	MOPSO
ZDT1	Best	1.200E-03	1.165E-02	1.348E-02	1.972E-02	5.000E-03
	Mean	1.327E-03	5.037E-02	2.874E-02	2.782E-01	6.823E-03
	std	1.081E-04	5.272E-02	1.455E-02	2.226E-01	6.285E-04
ZDT2	Best	1.045E-03	3.034E-02	7.149E-02	6.740E-01	3.504E-03
	Mean	1.134E-03	5.960E-02	1.241E-01	2.122E+01	8.409E-02
	std	5.351E-05	1.320E-02	2.682E-02	2.019E+01	2.011E-01
ZDT3	Best	3.800E-03	3.973E-02	5.131E-02	1.373E-02	9.617E-02
	Mean	4.407E-03	6.475E-02	9.688E-02	1.995E-01	1.001E-01
	std	3.279E-04	1.093E-02	2.079E-02	1.824E-01	2.015E-03
ZDT4	Best	3.895E-01	6.675E-01	9.119E-03	7.172E-02	2.351E+00
	Mean	2.084E+00	4.009E+00	4.548E-01	4.526E-01	1.201E+01
	std	1.344E+00	2.691E+00	1.380E-01	2.147E-01	6.904E+00
ZDT6	Best	7.000E-04	1.488E-03	4.106E-01	4.655E-02	1.713E-03
	Mean	9.867E-04	2.183E-02	6.743E-01	1.149E-01	5.183E-02
	std	1.592E-04	7.363E-02	1.429E-01	1.057E-01	1.462E-01
DTLZ2	Best	3.850E-02	4.530E-02	1.111E-01	6.795E-02	4.166E-01
	Mean	4.191E-02	4.701E-02	1.490E-01	7.119E-02	5.072E-01
	std	1.928E-03	1.014E-03	2.025E-02	1.565E-03	5.790E-02
DTLZ4	Best	3.450E-02	4.089E-02	9.615E-02	6.927E-02	6.119E-02
	Mean	4.509E-02	5.080E-02	1.474E-01	4.635E-01	8.236E-02
	std	6.302E-03	4.502E-03	3.107E-02	1.713E-01	1.228E-02
DTLZ7	Best	5.150E-02	5.288E-02	4.186E-01	1.006E-01	5.760E-02
	Mean	6.329E-02	6.000E-02	4.932E-01	4.139E-01	1.841E-01
	std	8.014E-03	3.774E-03	3.905E-02	2.804E-01	1.459E-01

算法	ZDT1	ZDT2	ZDT3	ZDT4	DTLZ2	DTLZ7
MOMEIG	3.886E-03	3.989E-03	8.235E-03	1.567E+00	5.798E-02	8.867E-02
GMOPSO	4.393E-03	4.027E-03	1.430E-01	6.663E+00	5.844E-02	1.051E-01