基于降维和聚类的大规模多目标自然计算方法

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

摘要/Abstract

摘要：

在多目标优化问题中，随着决策变量数目增多，算法的寻优能力会显著下降，针对这种“维数灾难”的问题，提出基于LLE降维思想和K-means聚类策略的大规模多目标自然计算方法。首先通过LLE降维思想对决策变量进行优化，得到高维变量在低维空间中的表示，再通过K-means策略对个体分组，为种群选择合适的引导个体，提高算法的收敛性和多样性。为验证算法有效性，将该方法应用于多目标粒子群优化算法和非支配排序遗传算法中，对收敛性进行了分析，证明该算法以概率1收敛。通过ZDT、DTLZ系列8个测试问题进行仿真试验，与6个代表性算法进行对比，通过PF、IGD指标、HV指标的评价结果验证其综合性能，并将其应用于水泵调度问题中。综合实验结果表明，所提方法具有较好性能。

关键词: 降维, 多目标优化, LLE, 自然计算方法, K-means

Abstract:

In multi-objective optimization problems, as the number of decision variables increases, the optimization ability decreases significantly. To solve "dimension disaster", a large-scale multi-objective natural computation method based on dimensionality reduction and clustering is proposed. The decision variables are optimized by locally linear embedding(LLE) to obtain the representation of high-dimensional variables in the low-dimensional space, then the individuals are grouped through K-means to select the appropriate guide individuals for the population to strengthen the convergence and diversity. To verify the effectiveness, the method is applied to the multi-objective particle swarm optimization algorithm and the non-dominated sorting genetic algorithm. The convergence is analyzed to prove that the algorithm converges with probability 1. Experiments is carried out through 8 functions of ZDT and DTLZ series, compared with 6 representative algorithms, and its comprehensive performance is verified through the evaluation results of PF, IGD and HV, and applied to the water pump scheduling problem. Comprehensive experimental results show that the proposed method has better performance.

Key words: dimension reduction, multi-objective optimization, locally linear embedding(LLE), natural computation, K-means

中图分类号:

TP391.9

季伟东, 岳玉麒, 王旭, 林平. 基于降维和聚类的大规模多目标自然计算方法[J]. 系统仿真学报, 2023, 35(1): 41-56.

Weidong Ji, Yuqi Yue, Xu Wang, Ping Lin. Large-scale Multi-objective Natural Computation Based on Dimensionality Reduction and Clustering[J]. Journal of System Simulation, 2023, 35(1): 41-56.

图/表 12

图1

图2

表1

标准测试函数描述

函数名称	目标函数描述	维数	说明
ZDT1	$Z D T 1 = m i n f 1 (x) = x 1 m i n f 2 (x) = g (1 - f 1 / g) g (x) = 1 + 9 ∑ i = 2 d x i / (d - 1) s . t . 0 ≤ x i ≤ 1, i = 1, 2, ⋯, 30$	$D$ =1 000	凸，连续
ZDT2	$Z D T 2 = m i n f 1 (x) = x 1 m i n f 2 (x) = g (1 - (f 1 / g) 2) g (x) = 1 + 9 ∑ i = 2 d x i / (d - 1) s . t . 0 ≤ x i ≤ 1, i = 1, 2, ⋯, 30$	$D$ =1 000	凹，连续
ZDT3	$Z D T 3 = m i n f 1 (x) = x 1 m i n f 2 (x) = g (1 - f 1 / g - (f 1 / g) s i n (10 π f 1)) g (x) = 1 + 9 ∑ i = 2 d x i / (d - 1) s . t . 0 ≤ x i ≤ 1, i = 1, 2, ⋯, 30$	$D$ =1 000	凹，不连续
ZDT4	$Z D T 4 = m i n f 1 (x) = x 1 m i n f 2 (x) = g (1 - f 1 / g) g (x) = 1 + 10 (d - 1) + ∑ i = 2 d (x i 2 - 10 c o s (4 π x i)) s . t . 0 ≤ x 1 ≤ 1, - 5 ≤ x i ≤ 5, i = 2,3, ⋯, 10$	$D$ =1 000	凸，多模态
ZDT6	$Z D T 6 = m i n f 1 (x) = 1 - e x p (- 4 x i) s i n 6 (6 π x 1) m i n f 2 (x) = g (1 - (f 1 / g) 2) g (x) = 1 + 9 ∑ i = 2 d x i / (d - 1) 0.25 s . t . 0 ≤ x i ≤ 1, i = 1, 2, ⋯, 10$	$D$ =1 000	凹，不连续
DTLZ2	$D T L Z 2 = m i n f 1 (x) = c o s π 2 x 1 c o s π 2 x 2 (1 + g (x)) m i n f 2 (x) = c o s π 2 x 1 s i n π 2 x 2 (1 + g (x)) m i n f 3 (x) = s i n π 2 x 1 (1 + g (x)) g (x) = ∑ i = 3 d (x i - 0.5) 2 s . t . 0 ≤ x i ≤ 1, i = 1, 2, ⋯, d$	$D$ =1 000	凸，连续
DTLZ4	$D T L Z 4 = m i n f 1 (x) = c o s π 2 x 1 α c o s π 2 x 2 α (1 + g (x)) m i n f 2 (x) = c o s π 2 x 1 α s i n π 2 x 2 α (1 + g (x)) m i n f 3 (x) = s i n π 2 x 1 α (1 + g (x)) g (x) = ∑ i = 3 d (x i - 0.5) 2 s . t . 0 ≤ x i ≤ 1, i = 1, 2, ⋯, d$	$D$ =1 000	凹，非均匀
DTLZ7	$D T L Z 7 = m i n f 1 (x) = 1 n / 3 ∑ i = (j - 1) n / 3 j n / 3 x i, j = 1, 2, 3 s . t . g j (x) = f 3 (x) + 4 f j (x) - 1 ≥ 0, j = 1, 2 g 3 = 2 f 3 (x) (x) + m i n i, j ≠ 1, i ≠ j [f j (x) + f j (x)] - 1 ≥ 0 s . t . 0 ≤ x i ≤ 1, i = 1, 2, ⋯, n, n > 3$	$D$ =1 000	不连续，多模态

表1

图3

图4

图5

表2

表3

图6

表4

图7

表5

参考文献 34

1	乔俊飞, 李霏, 杨翠丽. 一种基于均匀分布策略的NSGAⅡ算法[J]. 自动化学报, 2019, 45(7): 1325-1334.
	Qiao Junfei, Li Fei, Yang Cuili. An NSGAⅡ Algorithm Based on Uniform Distribution Strategy [J]. Acta Automatica Sinica, 2019, 45(7): 1325-1334.
2	邱飞岳, 莫雷平, 江波, 等. 基于大规模变量分解的多目标粒子群优化算法研究[J]. 计算机学报, 2016, 39(12): 2598-2613.
	Qiu Feiyue, Mo Leiping, Jiang Bo, et al. Research on Multi-objective Particle Swarm Optimization Algorithm Based on Large-Scale Variable Decomposition[J]. Chinese Journal of Computers, 2016, 39(12): 2598-2613.
3	Zhang X, Ye T, Ran C, et al. A Decision Variable Clustering-Based Evolutionary Algorithm for Large-Scale Many-objective Optimization[J]. IEEE Transactions on Evolutionary Computation (S1941-0026), 2018, 22(99): 97-112.
4	Potter M A. A Cooperative Co-Evolutionary Approach to Function[J]. Third Parallel Problem Solving Form Nature(S0302-9743), 1994, 866: 249-257.
5	Potter M A, Jong K. Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents[J]. Evolutionary Computation. IEEE (S1530-9304), 2014, 8(1): 1-29.
6	Antonio L M, Coello C. Use of Cooperative Coevolution for Solving Large Scale Multiobjective Optimization Problems[C]// 2013 IEEE Congress on Evolutionary Computation. Cancun, Mexico: IEEE, 2013: 2758-2765.
7	Basu S, Mondal A, Basu A. A Cooperative Coevolutionary Approach for Multi-objective Optimization[M].Recent Trends in Signal and Image Processing. Springer, Singapore, 2019: 57-65.
8	Zhang X, Ye T, Ran C, et al. A Decision Variable Clustering-Based Evolutionary Algorithm for Large-Scale Many-objective Optimization[J]. IEEE Transactions on Evolutionary Computation (S1941-0026), 2018, 22(99): 97-112.
9	Chen H, Zhu X, Pedrycz W, et al. PEA: Parallel Evolutionary Algorithm by Separating Convergence and Diversity for Large-Scale Multi-objective Optimization[C]// 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS). IEEE, 2018: 223-232.
10	Zille H, Ishibuchi H, Mostaghim S, et al. A Framework for Large-Scale Multiobjective Optimization Based on Problem Transformation[J]. IEEE Transactions on Evolutionary Computation (S1941-0026), 2018, 22(2):260-275.
11	He C, Li L, Tian Y, et al. Accelerating Large-Scale Multi-objective Optimization via Problem Reformulation[J]. IEEE Transactions on Evolutionary Computation(S1941-0026), 2019, 23(6): 949-961.
12	Cheng R, Jin Y. A Competitive Swarm Optimizer for Large Scale Optimization[J]. IEEE Transactions on Cybernetics (S2168-2275), 2015, 45(2): 191-204.
13	Zhang X, Zheng X, Cheng R, et al. A Competitive Mechanism Based Multi-objective Particle Swarm Optimizer with Fast Convergence[J]. Information Sciences (S0020-0255), 2018, 427: 63-76.
14	王蓉芳, 焦李成, 刘芳, 等. 自适应动态控制种群规模的自然计算方法[J]. 软件学报, 2012, 23(7): 1760-1772.
	Wang Rongfang, Jiao Licheng, Liu Fang, et al. Nature Computation with Self-adaptive Dynamic Control Strategy of Population Size[J]. Journal of Software, 2012, 23(7): 1760-1772.
15	Kumar R S, Kondapaneni K, Dixit V, et al. Multi-objective Modeling of Productionand Pollution Routing Problem with Time Window: A Self-learning Particle Swarm Optimization Approach[J]. Computersand Industrial Engineering (S0360-8352), 2016, 99: 29-40.
16	Wang Jing. Real Local-linearity Preserving Embedding[J]. Neurocomputing (S0925-2312), 2014, 136(20): 7-13.
17	张潞瑶, 季伟东, 程昊. 基于LLE降维思想的自然计算方法[J]. 系统仿真学报, 2020, 32(10): 1943-1955.
	Zhang Luyao, Ji Weidong, Cheng Hao. Natural Calculation Method Based on LLE Dimensionality Reduction Idea [J]. Journal of System Simulation, 2020, 32(10): 1943-1955.
18	马瑞, 王家廞, 宋亦旭, 等. 基于局部线性嵌入(LLE)非线性降维的多流形学习[J]. 清华大学学报(自然科学版), 2008, 48(4): 582-585.
	Ma Rui, Wang Jiaxin, Song Yixu, et al. Multi-manifold Learning using Locally Linear Embedding(LLE) Nonlinear Dimensionality Reduction[J]. Journal of Tsinghua University (Science and Technology), 2008, 48(4): 582-585.
19	Ridder D, Kouropteva O, Okun O. Supervised Locally Linear Embedding[C]// Artificial Neural Networks and Neural Information Processing. Istanbul, Turkey: Springer, 2003: 333-341.
20	Roweis S T, Saul L K. Nonlinear Dimensionality Reduction by Locally Linear Embedding[J].Science(S1095-9203), 2000, 290(5500): 2323-2326.
21	Li Yuan, Bai Yansong. Research on KNN fault Detection with Improved Principal Component Analysis [J]. Journal of Shenyang University of Chemical Technology(S2095-5198), 2018, 32(4): 366-371.
22	SOLIS F J, WETS J B. Minimization by Random Search Techniques[J]. Mathematics of Operations Research(S0364-765X), 1981, 6(1): 19-30.
23	张孟健, 龙道银, 王霄, 等. 基于马尔科夫链的灰狼优化算法收敛性研究[J]. 电子学报, 2020, 48(8): 1587-1595.
	Zhang Mengjian, Long Daoyin, Wang Xiao, et al. Research on the Convergence of Grey Wolf Optimization Algorithm Based on Markov Chain[J]. Chinese Journal of Electronics, 2020, 48(8): 1587-1595.
24	潘峰, 周倩, 李位星, 等. 标准粒子群优化算法的马尔科夫链分析[J]. 自动化学报, 2013, 39(4): 381-389.
	Pan Feng, Zhou Qian, Li Weixing, et al. Markov Chain Analysis of Standard Particle Swarm Optimization Algorithm[J]. Acta Automatica Sinica, 2013, 39(4): 381-389.
25	Zitzler E, Deb K, Thiele L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results[J]. Evolutionary Computation (S1530-9304), 2000, 8(2): 173-195.
26	Deb K, Thiele L, Laumanns M, et al. Scalable Test Problemsfor Evolutionary Multiobjective Optimization[C]// IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2002: 26-33.
27	Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation (S1941-0026), 2002, 6(2): 182-197.
28	Coello C A C, Pulido G T, Lechuga M S. Handling Multiple Objectives with Particle Swarm Optimization[J]. IEEE Transon Evolutionary Computation (S1941-0026), 2004, 8(3): 256-279.
29	Zhang Q, Hui L. MOEA/D: A Multio-bjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation (S1941-0026), 2008, 11(6):712-731.
30	Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm[C]// Athens. Greece, Technical Report Gloriastrasse, 2001: 103.
31	Kukkonen S, Lampinen J. GDE3: The Third Evolution Step of generalized Differential Evolution[C]// 2005 IEEE Congress on Evolutionary Computation. IEEE, 2005: 443-450.
32	Hu W, Yen G G. Adaptive Multiobjective Particle Swarmoptimization Based on Parallel Cell Coordinate System[J]. IEEETransactions on Evolutionary Computation (S1941-0026), 2015, 19(1): 1-18.
33	Czyzak P, Jaszkiewicz A. Pareto Simulated Annealing—A Metaheuristic Technique for Multiple-objective Combinatorial Optimization[J]. Journal of Multi-criteria Decision Analysis (S1099-1360), 1998, 7(1): 34-47.
34	公茂果, 焦李成, 杨咚咚, 等. 进化多目标优化算法研究[J]. 软件学报, 2009, 20(2): 271-289 .
	Gong Maoguo, Jiao Licheng, Yang Dongdong, et al. Research on Evolutionary Multi-objective Optimization Algorithm[J]. Journal of Software, 2009, 20(2): 271-289.

测试函数	IGD指标	DRC-NSGA	NSGA-II	DRC-MOPSO	MOPSO	MOEA/D	SPEA2
	Best	4.20×10^-3	1.53×10³	7.55×10^-2	2.67×10²	2.02×10³	2.21×10³
ZDT1	Mean	5.33×10^-3	1.70×10³	9.74×10^-2	2.97×10²	2.43×10³	2.70×10³
	std	2.78×10^-3	1.13×10²	1.77×10^-2	1.43×10	9.98×10	1.18×10²
	Best	1.41×10^-2	1.57×10³	7.80×10^-2	1.66×10²	1.30×10³	1.75×10³
ZDT2	Mean	2.73×10^-2	1.76×10³	1.12×10^-1	1.95×10²	2.38×10³	2.67×10³
	std	2.39×10^-2	1.12×10²	2.46×10^-2	4.55×10	9.68×10	1.21×10²
	Best	2.78×10^-2	1.53×10³	7.93×10^-2	1.67×10²	2.14×10³	1.14×10³
ZDT3	Mean	3.79×10^-2	1.71×10³	8.91×10^-2	2.96×10²	2.45×10³	1.98×10³
	std	3.16×10^-3	9.14×10¹	9.84×10^-3	2.95×10	8.40×10	8.65×10
	Best	3.90×10^-1	5.05×10³	4.12×10^-1	3.80×10³	5.41×10³	4.05×10³
ZDT4	Mean	6.03	5.53×10³	6.57×10^-1	4.91×10³	6.49×10³	4.93×10³
	std	1.34	1.95×10²	1.17	2.79×10²	1.99×10²	1.75×10²
	Best	1.09×10^-2	3.03×10	3.70×10^-2	2.19×10	3.09×10	3.89×10
ZDT6	Mean	2.32×10^-2	3.49×10	5.87×10^-2	2.40×10	3.68×10	4.29×10
	std	1.83×10^-3	5.13×10^-1	1.68×10^-2	1.09	6.10×10^-1	4.13×10^-1
DTLZ2	Best	4.91×10^-2	3.45×10³	4.85×10^-2	2.93×10²	2.85×10³	4.21×10³
	Mean	5.83×10^-2	4.76×10³	5.27×10^-2	3.46×10²	3.96×10³	5.02×10³
	std	1.88×10^-3	2.49×10²	2.03×10^-3	2.03×10	8.74×10	9.83×10²
DTLZ4	Best	3.97×10^-2	2.67×10³	3.75×10^-2	1.93×10²	4.86×10³	3.74×10³
	Mean	4.70×10^-2	3.01×10³	4.68×10^-2	2.94×10²	6.83×10³	4.19×10³
	std	2.89×10^-3	2.07×10²	3.93×10^-3	4.53×10	9.93×10	2.98×10²
DTLZ7	Best	4.67×10^-2	2.45×10³	4.78×10^-2	1.96×10²	3.85×10³	2.47×10³
	Mean	5.86×10^-2	4.18×10³	5.98×10^-2	2.27×10²	4.73×10³	4.03×10³
	std	7.98×10^-3	8.02×10	7.53×10^-2	2.86×10	8.37×10	8.92×10

测试函数	HV指标	DRC-NSGA	NSGA-II	DRC-MOPSO	MOPSO	CCMOPSO	GDE3
ZDT1	Mean	0.858	0.309	0.762	0.407	0.850	0.407
ZDT2	Mean	0.780	0.310	0.650	0.603	0.850	0.603
ZDT3	Mean	0.957	0.305	0.925	0.437	0.864	0.437
DTLZ2	Mean	0.991	0.567	0.974	0.853	0.587	0.759

时间间隔(5 min)	1			…	288
水泵号	1	2	3	…	1	2	3
位串	0	1	0	…	1	0	1
状态	关闭	开启	关闭	…	开启	关闭	开启

DRC-MOPSO		DRC-NSGA		MOPSO		NSGA-II		SPEA2
电力成本	维护成本	电力成本	维护成本	电力成本	维护成本	电力成本	维护成本	电力成本	维护成本
131	110	110	95	131	150	168	170	192	163
132	106	111	94	169	132	174	167	193	161
133	95	112	90	170	131	175	162	198	159
146	89	113	89	173	126	176	161	199	158
162	88	115	87			193	151
163	87	117	85			196	150
175	83	122	84			210	146
		140	82

[1]	胡剑鹏, 罗霞. 城市轨道交通动态客流分配仿真方法研究[J]. 系统仿真学报, 2022, 34(3): 512-526.
[2]	闫秀英, 党苗苗. 基于改进多目标粒子群算法的家庭用电时段优化[J]. 系统仿真学报, 2022, 34(1): 70-78.
[3]	张洪亮, 丁仁曼, 徐公杰. 考虑区间工时的多目标柔性作业车间节能调度[J]. 系统仿真学报, 2022, 34(09): 1976-1987.
[4]	田东, 单桂华, 迟学斌, 张艳玲, 冯伟华, 王建伟, 王爱国, 王锐. 基于降维技术的烟叶质量可视分析方法[J]. 系统仿真学报, 2021, 33(9): 2279-2288.
[5]	冉险生, 杨静, 罗领, 陈凯. 多任务并行的摩托车悬架系统参数多目标优化[J]. 系统仿真学报, 2021, 33(5): 1216-1223.
[6]	汪润鸿, 王红军, 邹湘军, 曾泽钦, 李慧, 黄钊丰, 刘伟良. 基于混合粒子群算法的组合式变速箱传动比优化研究[J]. 系统仿真学报, 2021, 33(4): 825-836.
[7]	王洪峰, 张翼天, 陈景泽. 一种面向需求不确定性供应链的进化多目标仿真优化方法[J]. 系统仿真学报, 2021, 33(12): 2761-2770.
[8]	李霏, 苏中. 基于自适应免疫优化的污水处理过程控制[J]. 系统仿真学报, 2021, 33(12): 3012-3020.
[9]	魏乐, 李希金. 基于多目标的含风电场动态环境经济调度[J]. 系统仿真学报, 2020, 32(9): 1825-1830.
[10]	王晓锋, 陈阳, 张光杰, 陈建宇. 面向网络仿真拓扑的多目标优化映射方法[J]. 系统仿真学报, 2020, 32(8): 1436-1445.
[11]	王闯, 张勇, 李学贵, 董宏丽. 改进粒子群优化算法及其在聚类分析中应用[J]. 系统仿真学报, 2020, 32(8): 1577-1587.
[12]	张小雨, 邵春福. 城乡结合部道路交叉口多目标信号配时优化模型[J]. 系统仿真学报, 2020, 32(4): 709-717.
[13]	卿东升, 张晓芳, 李建军, 郭瑞, 邓巧玲. 基于蜂群-粒子群算法的天然林空间结构优化[J]. 系统仿真学报, 2020, 32(3): 371-381.
[14]	田红军, 汪镭, 吴启迪. 基于多目标进化算法混合框架的MOEA/D算法[J]. 系统仿真学报, 2020, 32(2): 201-216.
[15]	丁宇, 王艳, 纪志成. 柔性作业车间生产与能耗协同优化决策方法[J]. 系统仿真学报, 2020, 32(12): 2426-2437.