Large-scale Multi-objective Natural Computation Based on Dimensionality Reduction and Clustering

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 12

Fig. 1

Fig. 2

Table 1

Standard test function description

函数名称	目标函数描述	维数	说明
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	不连续，多模态

Table 1

Fig. 3

Fig. 4

Fig. 5

Table 2

Table 3

Fig. 6

Table 4

Fig. 7

Table 5

References 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]	Yan Xiuying, Dang Miaomiao. Optimization of Household Electricity Consumption Period Based on Improved Multi-objective Particle Swarm Optimization [J]. Journal of System Simulation, 2022, 34(1): 70-78.
[2]	Hongliang Zhang, Renman Ding, Gongjie Xu. Energy-Efficient Scheduling of Multi-objective Flexible Job Shop Considering Interval Processing Time [J]. Journal of System Simulation, 2022, 34(09): 1976-1987.
[3]	Li Yuan, Geng Zewei. Fault Diagnosis of Industrial Process Based on LLE and K-means Clustering Algorithm [J]. Journal of System Simulation, 2021, 33(9): 2066-2073.
[4]	Tian Dong, Shan Guihua, Chi Xuebin, Zhang Yanling, Feng Weihua, Wang Jianwei, Wang Aiguo, Wang Rui. Visual Analysis Method of Tobacco Quality Data Based on Dimension Reduction [J]. Journal of System Simulation, 2021, 33(9): 2279-2288.
[5]	Ran Xiansheng, Yang Jing, Luo Ling, Chen Kai. Multi-objective Optimization of Multi-task Parallel Motorcycle Suspension System Parameters [J]. Journal of System Simulation, 2021, 33(5): 1216-1223.
[6]	Wang Runhong, Wang Hongjun, Zou Xiangjun, Zeng Zeqin, Li Hui, Huang Zhaofeng, Liu WeiLiang. Combined Gearbox Transmission Ratio Optimization Research Based on Hybrid Particle Swarm [J]. Journal of System Simulation, 2021, 33(4): 825-836.
[7]	Wang Hongfeng, Zhang Yitian, Chen Jingze. An Evolutionary Multi-Objective Simulation Optimization Algorithm for Supply Chain with Uncertain Demands [J]. Journal of System Simulation, 2021, 33(12): 2761-2770.
[8]	Li Fei, Su Zhong. Intelligent Control of Wastewater Treatment Processes Based on Adaptive Immune Optimization [J]. Journal of System Simulation, 2021, 33(12): 3012-3020.
[9]	Wei Le, Li Xijin. Dynamic Environmental and Economic Dispatching of Wind Farm Based on Multi-objective [J]. Journal of System Simulation, 2020, 32(9): 1825-1830.
[10]	Wang Xiaofeng, Chen Yang, Zhang Guangjie, Chen Jianyu. Multi-objective Topology Mapping Method for Network Emulation [J]. Journal of System Simulation, 2020, 32(8): 1436-1445.
[11]	Wang Chuang, Zhang Yong, Li Xuegui, Dong Hongli. An Improved Particle Swarm Optimization Algorithm and Its Application in Clustering analysis [J]. Journal of System Simulation, 2020, 32(8): 1577-1587.
[12]	Zhang Xiaoyu, Shao Chunfu. Multi-objective Signal Timing Optimal Model for Rural-urban Fringe Area Intersection [J]. Journal of System Simulation, 2020, 32(4): 709-717.
[13]	Tian Hongjun, Wang Lei, Wu Qidi. MOEA/D Algorithm Based on the Hybrid Framework for Multi-objective Evolutionary Algorithm [J]. Journal of System Simulation, 2020, 32(2): 201-216.
[14]	Ding Yu, Wang Yan, Ji Zhicheng. Collaborative Optimization of Production and Energy Consumption in Flexible Workshop [J]. Journal of System Simulation, 2020, 32(12): 2426-2437.
[15]	Liu Jianjun, Si Guangya, Wang Yanzheng, He Dachuan. Research on Multi-objective Optimization Method Based on Model [J]. Journal of System Simulation, 2020, 32(11): 2138-2145.