Distributed data-driven evolutionary computation for multi-constrained optimization

doi:10.11772/j.issn.1001-9081.2023121814

Abstract

Abstract:

Distributed data acquisition and processing in ubiquitous computing mode have brought the demand for distributed data-driven optimization. To address the challenges such as distributed data acquisition， asynchronous constraints evaluation and incomplete information， a Distributed Data-Driven Evolutionary Algorithm （DDDEA） framework for multi-constrained optimization was constructed. A series of terminal nodes were responsible for data provision and distributed evaluation， while the server nodes were responsible for global evolutionary optimization. Based on this framework， a specific algorithm instance was implemented， the terminal nodes utilized their local data to construct a Radial Basis Function （RBF） model to assist the differential evolution of the server node. Experimental comparison with three centralized data-driven evolutionary algorithms for multi-constrained optimization on two standard test suites show that， the DDDEA achieves significant optimal results in 68.4% of test cases and has a success rate of 1.00 in finding feasible solutions in 84.2% of test cases. Therefore， the DDDEA has satisfactory global search and convergence abilities.

Key words: distributed optimization, data-driven optimization, constrained optimization, evolutionary computation, Differential Evolution (DE) algorithm

摘要：

泛在计算模式下，数据分布式获取和处理带来了分布式数据驱动优化的需求。针对数据分布获取、约束异步评估且信息缺失的挑战，构建分布式数据驱动的多约束进化优化算法（DDDEA）框架，由一系列终端节点负责数据提供和分布式评估，服务器节点负责全局进化优化。基于该框架具体实现了一个算法实例，终端节点利用局部数据构建径向基函数（RBF）模型，辅助驱动服务器节点差分进化（DE）算法对问题进行寻优。通过与3个集中式数据驱动的多约束进化优化算法在两个标准测试集的实验对比，DDDEA在68.4%的测试用例中取得显著最优结果，在84.2%的测试用例中找到可行解的成功率为1.00，表明该算法具有良好的全局搜索能力和收敛能力。

关键词: 分布式优化, 数据驱动优化, 约束优化, 进化计算, 差分进化算法

CLC Number:

TP301.6

Fengfeng WEI, Weineng CHEN. Distributed data-driven evolutionary computation for multi-constrained optimization[J]. Journal of Computer Applications, 2024, 44(5): 1393-1400.

魏凤凤, 陈伟能. 分布式数据驱动的多约束进化优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1393-1400.

Figures/Tables 5

References 47

1	马华东，赵东，王新兵，等.一种新型群智感知系统架构模型和实现方法［J］.中国科学：信息科学，2023，53（7）：1262-1280. 10.1360/ssi-2022-0157
	MA H D， ZHAO D， WANG X B， et al. A novel crowdsensing system architecture model and its implementation methods［J］. SCIENTIA SINICA Informationis， 2023， 53（7）： 1262-1280. 10.1360/ssi-2022-0157
2	门瑞，樊书嘉，阿喜达，等.物联网中结合计算卸载和区块链的综述［J］.计算机应用，2023，43（10）：3008-3016. 10.11772/j.issn.1001-9081.2022091466
	MEN R， FAN S J， SHAN Axida， et al. Survey on combination of computation offloading and blockchain in internet of things［J］. Journal of Computer Applications， 2023， 43（10）： 3008-3016. 10.11772/j.issn.1001-9081.2022091466
3	吴磊，郭斌，徐若楠，等.泛在计算视角下的群智模块化机器人［J］. 中国科学：信息科学，2023，53（11）：2107-2151. 10.1360/ssi-2022-0385
	WU L， GUO B， XU R N， et al. Emergence of crowd modular robotics： a ubiquitous computing perspective［J］. SCIENTIA SINICA Informationis， 2023， 53（11）： 2107-2151. 10.1360/ssi-2022-0385
4	ZHANG Z， LIN S， DEDEOGLU M， et al. Data-driven distributionally robust optimization for edge intelligence［C］// Proceedings of the 2020 IEEE Conference on Computer Communications. Piscataway： IEEE， 2020： 2619-2628. 10.1109/infocom41043.2020.9155440
5	YANG Q， LIU Y， CHEN T， et al. Federated machine learning： concept and applications［J］. ACM Transactions on Intelligent Systems and Technology， 2019， 10（2）： 1-19. 10.1145/3298981
6	公茂果，高原，王炯乾，等.基于进化策略的自适应联邦学习算法［J］.中国科学：信息科学，2023，53（3）：437-453. 10.1360/ssi-2021-0190
	GONG M G， GAO Y， WANG J Q， et al. Adaptive federated learning algorithm based on evolution strategies［J］. SCIENTIA SINICA Informationis， 2023， 53（3）： 437-453. 10.1360/ssi-2021-0190
7	HONG T， ZHANG Y， LIU J， et al. Distributed data-driven optimization for voltage regulation in distribution systems［J］. IEEE Transactions on Power Systems， 2023， 39（1）： 1263-1273. 10.1109/tpwrs.2023.3242868
8	QIN J， ZHU Y， FU W. Distributed clustering algorithm in sensor networks via normalized information measures［J］. IEEE Transactions on Signal Processing， 2020， 68： 3266-3279. 10.1109/tsp.2020.2995506
9	WHITLEY L D. An overview of evolutionary algorithms： practical issues and common pitfalls［J］. Information and Software Technology， 2001， 43（14）： 817-831. 10.1016/s0950-5849(01)00188-4
10	TANG J， LIU G， PAN Q. A review on representative swarm intelligence algorithms for solving optimization problems： applications and trends［J］. IEEE/CAA Journal of Automatica Sinica， 2021， 8（10）： 1627-1643. 10.1109/jas.2021.1004129
11	刘若辰，李建霞，刘静，等.动态多目标优化研究综述［J］.计算机学报，2020，43（7）：1246-1278. 10.11897/SP.J.1016.2020.01246
	LIU R C， LI J X， LIU J， et al. A survey on dynamic multi-objective optimization［J］. Chinese Journal of Computers， 2020， 43（7）： 1246-1278. 10.11897/SP.J.1016.2020.01246
12	柴天佑，丁进良，王宏，等.复杂工业过程运行的混合智能优化控制方法［J］.自动化学报，2008，34（5）：505-515. 10.3724/sp.j.1004.2008.00505
	CHAI T Y， DING J L， WANG H， et al. Hybrid intelligent optimal control method for operation of complex industrial processes［J］. Acta Automatica Sinica， 2008， 34（5）： 505-515. 10.3724/sp.j.1004.2008.00505
13	王凌，王晶晶.考虑运输时间的分布式绿色柔性作业车间调度协同群智能优化［J］.中国科学：技术科学，2023，53（2）：243-257. 10.1360/sst-2021-0355
	WANG L， WANG J J. A cooperative memetic algorithm for the distributed green flexible job shop with transportation time［J］. SCIENTIA SINICA Technologica， 2023， 53（2）： 243-257. 10.1360/sst-2021-0355
14	GONG Y-J， CHEN W-N， ZHAN Z-H， et al. Distributed evolutionary algorithms and their models： a survey of the state-of-the-art［J］. Applied Soft Computing， 2015， 34： 286-300. 10.1016/j.asoc.2015.04.061
15	XU J， JIN Y， DU W， et al. A federated data-driven evolutionary algorithm［J］. Knowledge-Based Systems， 2021， 233： 107532. 10.1016/j.knosys.2021.107532
16	ZHU H， JIN Y. Real-time federated evolutionary neural architecture search［J］. IEEE Transactions on Evolutionary Computation， 2022， 26（2）： 364-378. 10.1109/tevc.2021.3099448
17	LIU Q， YAN Y， LIGETI P， et al. A secure federated data-driven evolutionary multi-objective optimization algorithm［J］. IEEE Transactions on Emerging Topics in Computational Intelligence， 2024， 8（1）： 191-205. 10.1109/tetci.2023.3313555
18	GUO X-Q， CHEN W-N， WEI F-F， et al. Edge-cloud co‑evolutionary algorithms for distributed data-driven optimization problems［J］. IEEE Transactions on Cybernetics， 2023， 53（10）： 6598-6611. 10.1109/tcyb.2022.3219452
19	MORÁN-FERNÁNDEZ L， BOLÓN-CANEDO V， ALONSO-BETANZOS A. Centralized vs. distributed feature selection methods based on data complexity measures［J］. Knowledge-Based Systems， 2017， 117： 27-45. 10.1016/j.knosys.2016.09.022
20	RAHI K H， SINGH H K， RAY T. Partial evaluation strategies for expensive evolutionary constrained optimization［J］. IEEE Transactions on Evolutionary Computation， 2021， 25（6）： 1103-1117. 10.1109/tevc.2021.3078486
21	GIOVANNI DE G， MUNDO D， MALETTA C， et al. Multi-objective optimization of a vehicle body by combining gradient-based methods and vehicle concept modelling［J］. Case Studies in Mechanical Systems and Signal Processing， 2015， 1： 1-7. 10.1016/j.csmssp.2015.06.002
22	WEI F-F， CHEN W-N， ZHANG J. A hybrid regressor and classifier-assisted evolutionary algorithm for expensive optimization with incomplete constraint information［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2023， 53（2）： 5071-5083. 10.1109/tsmc.2023.3259947
23	LIU B， ZHANG Q， GIELEN G G E. A Gaussian process surrogate model assisted evolutionary algorithm for medium scale expensive optimization problems［J］. IEEE Transactions on Evolutionary Computation， 2014， 18（2）： 180-192. 10.1109/tevc.2013.2248012
24	POWELL M J D. The uniform convergence of thin plate spline interpolation in two dimensions［J］. Numerische Mathematik， 1994， 128： 107-128. 10.1007/s002110050051
25	REGIS R G， SHOEMAKER C A. A stochastic radial basis function method for the global optimization of expensive functions［J］. INFORMS Journal on Computing， 2007， 19（4）： 497-509. 10.1287/ijoc.1060.0182
26	REGIS R G. Particle swarm with radial basis function surrogates for expensive black-box optimization［J］. Journal of Computational Science， 2014， 5（1）： 12-23. 10.1016/j.jocs.2013.07.004
27	STORN R， KENNETH P. Differential evolution： a simple and efficient heuristic for global optimization over continuous spaces［J］. Journal of Global Optimization， 1997， 11（4）： 341-359.
28	WANG W， LIU H-L， CHEN TAN KAY， et al. A surrogate-assisted differential evolution algorithm for high-dimensional expensive optimization problems［J］. IEEE Transactions on Cybernetics， 2023， 53（4）： 2685-2697. 10.1109/tcyb.2022.3175533
29	WANG Y， YIN D-Q， YANG S， et al. Global and local surrogate-assisted differential evolution for expensive constrained optimization problems with inequality constraints［J］. IEEE Transactions on Cybernetics， 2019， 49（5）： 1642-1656. 10.1109/tcyb.2018.2809430
30	WANG B-C， LI H-X， LI J-P， et al. Composite differential evolution for constrained evolutionary optimization［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2019， 49（7）： 1482-1495. 10.1109/tsmc.2018.2807785
31	STEIN M. Large sample properties of simulations using Latin hypercube sampling［J］. Technometrics， 1987， 29（2）： 143-151. 10.1080/00401706.1987.10488205
32	LI J-Y， ZHAN Z-H， WANG H， et al. Data-driven evolutionary algorithm with perturbation-based ensemble surrogates［J］. IEEE Transactions on Cybernetics， 2021， 51（8）： 3925-3937. 10.1109/tcyb.2020.3008280
33	季新芳，张勇，巩敦卫，等.异构集成代理辅助的区间多模态粒子群优化算法［J/OL］.自动化学报，2021，45（x）：1-23 ［2023-12-05］. . 10.16383/j.aas.c210223
	JI X F， ZAHNG Y， GONG D W， et al. Interval multimodal particle swarm optimization algorithm assisted by heterogeneous ensemble surrogate［J/OL］. Acta Automatica Sinica， 2021， 45（x）： 1-23 ［2023-12-05］. . 10.16383/j.aas.c210223
34	DORIGO M， GAMBARDELLA L M. Ant colony system： a cooperative learning approach to the traveling salesman problem［J］. IEEE Transactions on Evolutionary Computation， 1997， 1（1）： 53-66. 10.1109/4235.585892
35	CHEN W-N， ZHANG J， CHUNG H S H， et al. A novel set-based particle swarm optimization method for discrete optimization problems［J］. IEEE Transactions on Evolutionary Computation， 2010， 14（2）： 278-300. 10.1109/tevc.2009.2030331
36	KENNEDY J， EBERHART R. Particle swarm optimization［C］// Proceedings of the 1995 International Conference on Neural Networks. Piscataway： IEEE， 1995： 1942-1948. 10.1109/ICNN.1995.488968
37	VANNESCHI L， CASTELLI M， SILVA S. A survey of semantic methods in genetic programming［J］. Genetic Programming and Evolvable Machines， 2014， 15（2）： 195-214. 10.1007/s10710-013-9210-0
38	WEI F-F， CHEN W-N， YANG Q， et al. A classifier-assisted level-based learning swarm optimizer for expensive optimization［J］. IEEE Transactions on Evolutionary Computation， 2021， 25（2）： 219-233. 10.1109/tevc.2020.3017865
39	PILLAI A S， SINGH K， SARAVANAN V， et al. A genetic algorithm-based method for optimizing the energy consumption and performance of multiprocessor systems［J］. Soft Computing， 2018， 22（10）： 3271-3285. 10.1007/s00500-017-2789-y
40	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. 10.1109/4235.996017
41	REGIS R G. Evolutionary programming for high-dimensional constrained expensive black-box optimization using radial basis functions［J］. IEEE Transactions on Evolutionary Computation， 2014， 18（3）： 326-347. 10.1109/tevc.2013.2262111
42	HANDOKO S D， KWOH C K， ONG Y S. Feasibility structure modeling： an effective chaperone for constrained memetic algorithms［J］. IEEE Transactions on Evolutionary Computation， 2010， 14（5）： 740-758. 10.1109/tevc.2009.2039141
43	LIANG J J， RUNARSSON T P， MEZURA-MONTES E， et al. Problem definitions and evaluation criteria for the CEC 2006 special session on real-parameter optimization［J］. Journal of Applied Mechanics， 2006， 41（8）： 1-24.
44	MALLIPEDDI R， SUGANTHAN P N. Problem definitions and evaluation criteria for the CEC 2010 competition on constrained real-parameter optimization［R/OL］. ［2023-11-10］. .
45	LIU B， ZHANG Q， GIELEN G. A surrogate-model-assisted evolutionary algorithm for computationally expensive design optimization problems with inequality constraints［J］. Simulation-Driven Modeling and Optimization， 2016， 153： 347-370. 10.1007/978-3-319-27517-8_14
46	LI G， ZHANG Q. Multiple penalties and multiple local surrogates for expensive constrained optimization［J］. IEEE Transactions on Evolutionary Computation， 2021， 25（4）： 769-778. 10.1109/tevc.2021.3066606
47	DONG H， WANG P， FU C， et al. Kriging-assisted Teaching-Learning-Based Optimization （KTLBO） to solve computationally expensive constrained problems［J］. Information Sciences， 2021， 556： 404-435. 10.1016/j.ins.2020.09.073

测试用例	不等约束数	维数	可行域比例/%
g01	9	13	0.011 1
g02	2	20	99.997 1
g04	6	5	52.123 0
g06	2	2	0.006 6
g07	8	10	0.000 3
g08	2	2	0.856 0
g09	4	7	0.512 1
g10	6	8	0.001 0
g12	1	3	4.771 3
g16	38	5	0.020 4
g18	13	9	0.000 0
g19	5	15	33.476 1
g24	2	2	79.655 6
c01	2	30	100.000 0
c07	1	30	50.372 5
c08	1	30	37.527 8
c13	3	30	0.000 0
c14	3	30	0.612 3
c15	3	30	0.602 3

测试用例	不等约束数	维数	可行域比例/%
g01	9	13	0.011 1
g02	2	20	99.997 1
g04	6	5	52.123 0
g06	2	2	0.006 6
g07	8	10	0.000 3
g08	2	2	0.856 0
g09	4	7	0.512 1
g10	6	8	0.001 0
g12	1	3	4.771 3
g16	38	5	0.020 4
g18	13	9	0.000 0
g19	5	15	33.476 1
g24	2	2	79.655 6
c01	2	30	100.000 0
c07	1	30	50.372 5
c08	1	30	37.527 8
c13	3	30	0.000 0
c14	3	30	0.612 3
c15	3	30	0.602 3

测试用例	DDDEA	GPEEC	MPMLS	KTLBO
g01	-14.793 1	-9.611 3^-	-5.214 2^-	-0.751 4^-
g02	-0.413 8	-0.338 08^-	-0.318 1^-	-0.340 3^-
g04	-3.044 3E+04	-3.043 0E+04^-	-3.060 0E+04⁺	-2.981 8E+04^-
g06	-6.961 8E+03	-6.110 0E+03^-	-6.954 4E+03^-	-3.646 9E+03^-
g07	27.936 3	28.904 3^-	997.986 2^-	216.913 0^≈
g08	-0.095 8	-0.094 7^-	-0.095 8^-	-0.072 6^-
g09	963.162 9	2.392 7E+06^-	823.029 2⁺	934.816 4^≈
g10	7.423 0E+03	NaN^/	1.288 1E+04^-	1.150 2E+04^-
g12	-1.000 0	-1.000 0^≈	-1.000 0^≈	-1.000 0^≈
g16	-1.577 6	-1.402 2^-	-1.537 9^≈	-1.246 6^≈
g18	NaN	-0.402 6^/	NaN^/	-0.083 9^/
g19	165.747 1	1.739 5E+03^-	578.727 0^-	810.270 7^-
g24	-5.508 0	-5.471 9^≈	-5.505 0^-	-5.168 1^-
c01	-0.292 5	-0.189 0^-	-0.222 7^-	-0.285 5^-
c07	9.113 3E+07	9.623 8E+10^-	4.309 9E+08^-	4.971 5E+09^-
c08	4.009 7E+08	8.795 3E+10^-	1.292 5E+09^-	1.831 8E+09^-
c13	-11.295 9	-7.545 5^-	-14.820 0⁺	-6.780 3^-
c14	6.057 2E+12	3.964 8E+13^-	6.978 9E+13^-	3.103 0E+14^-
c15	NaN	5.115 9E+14^/	3.269 7E+14^/	6.293 1E+14^/
#（+，-，≈，/）		（0，14，2，3）	（3，12，2，2）	（0，13，4，2）

测试用例	DDDEA	GPEEC	MPMLS	KTLBO
g01	-14.793 1	-9.611 3^-	-5.214 2^-	-0.751 4^-
g02	-0.413 8	-0.338 08^-	-0.318 1^-	-0.340 3^-
g04	-3.044 3E+04	-3.043 0E+04^-	-3.060 0E+04⁺	-2.981 8E+04^-
g06	-6.961 8E+03	-6.110 0E+03^-	-6.954 4E+03^-	-3.646 9E+03^-
g07	27.936 3	28.904 3^-	997.986 2^-	216.913 0^≈
g08	-0.095 8	-0.094 7^-	-0.095 8^-	-0.072 6^-
g09	963.162 9	2.392 7E+06^-	823.029 2⁺	934.816 4^≈
g10	7.423 0E+03	NaN^/	1.288 1E+04^-	1.150 2E+04^-
g12	-1.000 0	-1.000 0^≈	-1.000 0^≈	-1.000 0^≈
g16	-1.577 6	-1.402 2^-	-1.537 9^≈	-1.246 6^≈
g18	NaN	-0.402 6^/	NaN^/	-0.083 9^/
g19	165.747 1	1.739 5E+03^-	578.727 0^-	810.270 7^-
g24	-5.508 0	-5.471 9^≈	-5.505 0^-	-5.168 1^-
c01	-0.292 5	-0.189 0^-	-0.222 7^-	-0.285 5^-
c07	9.113 3E+07	9.623 8E+10^-	4.309 9E+08^-	4.971 5E+09^-
c08	4.009 7E+08	8.795 3E+10^-	1.292 5E+09^-	1.831 8E+09^-
c13	-11.295 9	-7.545 5^-	-14.820 0⁺	-6.780 3^-
c14	6.057 2E+12	3.964 8E+13^-	6.978 9E+13^-	3.103 0E+14^-
c15	NaN	5.115 9E+14^/	3.269 7E+14^/	6.293 1E+14^/
#（+，-，≈，/）		（0，14，2，3）	（3，12，2，2）	（0，13，4，2）

[1]	Xiaofang LIU, Jun ZHANG. Probability-driven dynamic multiobjective evolutionary optimization for multi-agent cooperative scheduling [J]. Journal of Computer Applications, 2024, 44(5): 1372-1377.
[2]	Yuntao ZHAO, Wanqi XIE, Weigang LI, Jiaming HU. Robot hand-eye calibration algorithm based on covariance matrix adaptation evolutionary strategy [J]. Journal of Computer Applications, 2023, 43(10): 3225-3229.
[3]	Qingqing NIE, Dingsheng WAN, Yuelong ZHU, Zhijia LI, Cheng YAO. Hydrological model based on temporal convolutional network [J]. Journal of Computer Applications, 2022, 42(6): 1756-1761.
[4]	Feifan SHI, Xuhua SHI. Adaptive reference vector based constrained multi-objective evolutionary algorithm [J]. Journal of Computer Applications, 2022, 42(2): 542-549.
[5]	Rongrong DAI, Honghui LI, Xueliang FU. Data center flow scheduling mechanism based on differential evolution and ant colony optimization algorithm [J]. Journal of Computer Applications, 2022, 42(12): 3863-3869.
[6]	XI Yarui, QIAO Zhiwei, WEN Jing, ZHANG Yanjiao, YANG Wenjing, YAN Huiwen. High order TV image reconstruction algorithm based on Chambolle-Pock algorithm framework [J]. Journal of Computer Applications, 2020, 40(6): 1793-1798.
[7]	SHI Xiaoqian, CHEN Qidong, SUN Jun, MAO Zhongjie. Adaptive distribution based quantum-behaved particle swarm optimization algorithm for engineering constrained optimization problem [J]. Journal of Computer Applications, 2020, 40(5): 1382-1388.
[8]	ZHANG Xin, ZOU Dexuan, SHEN Xin. Hybrid two-norm particle swarm optimization algorithm with crossover term [J]. Journal of Computer Applications, 2018, 38(8): 2148-2156.
[9]	LIU Bao, DONG Minggang, JING Chao. Multi-objective differential evolution algorithm with improved ranking-based mutation [J]. Journal of Computer Applications, 2018, 38(8): 2157-2163.
[10]	YUAN Yichuan, YANG Zhou, LUO Tingxing, QIN Jin. Multi-population-based competitive differential evolution algorithm for dynamic optimization problem [J]. Journal of Computer Applications, 2018, 38(5): 1254-1260.
[11]	LI Jiadi, MA Chi, LI Dequan, WANG Junya. Distributed quantized subgradient optimization algorithm for multi-agent switched networks [J]. Journal of Computer Applications, 2018, 38(2): 509-515.
[12]	LI Xiaowen, YUAN Xianghui, ZHOU Chunxiang. Optimal line-shape parameter estimation algorithm of orbit plane based on inertial angle measurement [J]. Journal of Computer Applications, 2016, 36(12): 3499-3504.
[13]	LI Kangshun, ZUO Lei, LI Wei. Novel differential evolution algorithm based on simplex-orthogonal experimental design [J]. Journal of Computer Applications, 2016, 36(1): 143-149.
[14]	LONG Wen, ZHAO Dongquan, XU Songjin. Improved grey wolf optimization algorithm for constrained optimization problem [J]. Journal of Computer Applications, 2015, 35(9): 2590-2595.
[15]	XU Jun, LU Haiyan, SHI Guijuan. Application of restricted velocity particle swarm optimization and self-adaptive velocity particle swarm optimization to unconstrained optimization problem [J]. Journal of Computer Applications, 2015, 35(3): 668-674.