A new differential evolution using a bilevel optimization model for solving generalized multi-point dynamic aggregation problems

Yu Shen; Hecheng Li; Yu Shen; Hecheng Li

doi:10.3934/mbe.2023612

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 8: 13754-13776. doi: 10.3934/mbe.2023612

Previous Article Next Article

Research article

A new differential evolution using a bilevel optimization model for solving generalized multi-point dynamic aggregation problems

Yu Shen ¹,
Hecheng Li ^{2
,
,}

1.
School of Computer Science and Technology, Qinghai Normal University, Xining 810008, Qinghai, China
2.
School of Mathematics and Statistics, Qinghai Normal University, Xining 810008, Qinghai, China

Received: 06 April 2023 Revised: 16 May 2023 Accepted: 29 May 2023 Published: 16 June 2023

The multi-point dynamic aggregation problem (MPDAP) comes mainly from real-world applications, which is characterized by dynamic task assignation and routing optimization with limited resources. Due to the dynamic allocation of tasks, more than one optimization objective, limited resources, and other factors involved, the computational complexity of both route programming and resource allocation optimization is a growing problem. In this manuscript, a task scheduling problem of fire-fighting robots is investigated and solved, and serves as a representative multi-point dynamic aggregation problem. First, in terms of two optimized objectives, the cost and completion time, a new bilevel programming model is presented, in which the task cost is taken as the leader's objective. In addition, in order to effectively solve the bilevel model, a differential evolution is developed based on a new matrix coding scheme. Moreover, some percentage of high-quality solutions are applied in mutation and selection operations, which helps to generate potentially better solutions and keep them into the next generation of population. Finally, the experimental results show that the proposed algorithm is feasible and effective in dealing with the multi-point dynamic aggregation problem.
- multi-point dynamic aggregation problem,
- multirobot system,
- task allocation,
- bilevel optimization model,
- differential evolution
Citation: Yu Shen, Hecheng Li. A new differential evolution using a bilevel optimization model for solving generalized multi-point dynamic aggregation problems[J]. Mathematical Biosciences and Engineering, 2023, 20(8): 13754-13776. doi: 10.3934/mbe.2023612

Related Papers:

Abstract

The multi-point dynamic aggregation problem (MPDAP) comes mainly from real-world applications, which is characterized by dynamic task assignation and routing optimization with limited resources. Due to the dynamic allocation of tasks, more than one optimization objective, limited resources, and other factors involved, the computational complexity of both route programming and resource allocation optimization is a growing problem. In this manuscript, a task scheduling problem of fire-fighting robots is investigated and solved, and serves as a representative multi-point dynamic aggregation problem. First, in terms of two optimized objectives, the cost and completion time, a new bilevel programming model is presented, in which the task cost is taken as the leader's objective. In addition, in order to effectively solve the bilevel model, a differential evolution is developed based on a new matrix coding scheme. Moreover, some percentage of high-quality solutions are applied in mutation and selection operations, which helps to generate potentially better solutions and keep them into the next generation of population. Finally, the experimental results show that the proposed algorithm is feasible and effective in dealing with the multi-point dynamic aggregation problem.

References

[1]	B. Xin, Y. G. Zhu, Y. L. Ding, G. Q. Gao, Coordinated motion planning of multiple robots in multi-point dynamic aggregation task, in Proceedings IEEE International Conference on Control and Automation, Kathmandu, Nepal, 2016,933–938. https://doi.org/10.1109/ICCA.2016.7505398
[2]	V. Akbari, F. S. Salman, Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity, European J. Operat. Res., 257 (2017), 625–640. https://doi.org/10.1016/j.ejor.2016.07.043 doi: 10.1016/j.ejor.2016.07.043
[3]	A. Khan, B. Rinner, A. Cavallaro, Cooperative robots to observe moving targets: Review, IEEE Transact. Cybernet., 48 (2018), 187–198. https://doi.org/10.1109/TCYB.2016.2628161 doi: 10.1109/TCYB.2016.2628161
[4]	W. Q. Jin, S. Q. Dong, C. Q. Yu, Q. Q. Luo, A data-driven hybrid ensemble AI model for COVID-19 infection forecast using multiple neural networks and reinforced learning, Comput. Biol. Med., 146 (2022), 105560. https://doi.org/10.1016/j.compbiomed.2022.105560 doi: 10.1016/j.compbiomed.2022.105560
[5]	R. P. Yuan, J. T. Li, X. L. Wang, L. Y. He, Multirobot task allocation in e-commerce robotic mobile fulfillment systems, Math. Problems Eng., (2021), Article ID 6308950. https://doi.org/10.1155/2021/6308950 doi: 10.1155/2021/6308950
[6]	C. Y. Ju, J. Kim, J. Seol, H. I. Son, A review on multirobot systems in agriculture, Comput. Electron. Agriculture, 202 (2022), 107336. https://doi.org/10.1016/j.compag.2022.107336 doi: 10.1016/j.compag.2022.107336
[7]	B. Xin, S. Liu, Z. Peng, G. Gao, An estimation of distribution algorithm for multi-robot multi-point dynamic aggregation problem, in Proceedings IEEE International Conference on Systems, Man, and Cybernetics (SMC), Miyazaki, Japan, 2018,775–780.
[8]	S. Lu, B. Xin, L. Dou, L. Wang, A multi-model estimation of distribution algorithm for agent routing problem in multi-point dynamic task, in Proceedings of the 37th Chinese Control Conference (CCC), Wuhan, China, 2018, 2468–2473.
[9]	G. Gao, Y. Mei, X. Bin, Y. H. Jia, W. N. Browne, A memetic algorithm for the task allocation problem on multi-robot multi-point dynamic aggre- gation missions, inProceedings IEEE Congress on Evolutionary Computation (CEC), Glasgow, U.K., 2020, 1–8.
[10]	R. Hao, J. Zhang, B. Xin, C. Chen, L. Dou, A hybrid differential evolution and estimation of distribution algorithm for the multi-point dynamic aggregation problem, in Proceedings Genetic Evolution Computational Conference Companion, 2018,251–252.
[11]	G. Q. Gao, Y. Mei, Y. H. Jia, W. N. Browne, B. Xin, Adaptive coordination ant colony optimization for multipoint dynamic aggregation, IEEE Transact. Cybernet., 52 (2022), 7362–7376. https://doi.org/10.1109/TCYB.2020.3042511 doi: 10.1109/TCYB.2020.3042511
[12]	A. Sinha, P. Malo, K. Deb, A review on bilevel optimization: From classical to evolutionary approaches and applications, IEEE Transact. Evolut. Comput., 22 (2018). https://doi.org/10.1109/TEVC.2017.2712906 doi: 10.1109/TEVC.2017.2712906
[13]	A. Sinha, T. Soun, K. Deb, Using Karush-Kuhn-Tucker proximity measure for solving bilevel optimization problems, Swarm and Evolutionary Computation, 44 (2019), 496-510. https://doi.org/10.1016/j.swevo.2018.06.004 doi: 10.1016/j.swevo.2018.06.004
[14]	S. N. Liu, M. Z. Wang, N. Kong, An enhanced branch-and-bound algorithm for bilevel integer linear programming, European J. Operat. Res., 291 (2020), 61–67. https://doi.org/10.1016/j.ejor.2020.10.002 doi: 10.1016/j.ejor.2020.10.002
[15]	G. X. Li, X. M. Yang, Convexification method for bilevel programs with a nonconvex follower's problem, J. Optimiz. Theory Appl., 188 (2021), 724–743. https://doi.org/10.1007/s10957-020-01804-9 doi: 10.1007/s10957-020-01804-9
[16]	A. Joseph, O. Y. Ozaltin, Feature selection for classification models via bilevel optimization, Comput. Operat. Res., 5 (2018), 1–32. https://doi.org/10.1016/j.cor.2018.05.005 doi: 10.1016/j.cor.2018.05.005
[17]	H. C. Li, Z. C. Wang, An evolutionary algorithm using parameter space searching for interval linear fractional bilevel programming problems, Int. J. Pattern Recogn. Artif. Intell., 30 (2016), 1–18. https://doi.org/10.1142/S0218001416590114 doi: 10.1142/S0218001416590114
[18]	Y. Aboelnage, S. Nasr, Modified evolutionary algorithm and chaotic search for bilevel programming problems, Symmetry, 12 (2020), 767–796. https://doi.org/10.3390/sym12050767 doi: 10.3390/sym12050767
[19]	N. N. Goshu, S. M. Kassa, A systematic sampling evolutionary (SSE) method for stochastic bilevel programming problems, Comput. Operat. Res., 120 (2020), 1–14. https://doi.org/10.1016/j.cor.2020.104942 doi: 10.1016/j.cor.2020.104942
[20]	M. M. Islam, H. K. Singh, T. Ray, An enhanced memetic algorithm for single-objective bilevel optimization problems, Evolut. Comput., 25 (2017), 607–642. https://doi.org/10.1162/EVCOa00198 doi: 10.1162/EVCOa00198
[21]	A. Yousria, S. Nasr, I. El-Desoky, Enhanced genetic algorithm and chaos search for bilevel programming problems, In Advances in Intelligent Systems and Computing, Hassanien, A.Ed. Springer: Cham, Switzerland, 2019,478–487.
[22]	A. Sinha, Z. Lu, K. Deb, P. Malo, Bilevel optimization based on iterative approximation of multiple mappings. Journal of Heuristics, 26 (2020), 151–185. https://doi.org/10.48550/arXiv.1702.03394 doi: 10.48550/arXiv.1702.03394
[23]	A. Molai, Solving fuzzy multiobjective linear bilevel programming problems based on the extension principle, Iranian J. Numer. Anal. Optimiz., 11 (2021), 1–31. https://doi.org/10.22067/IJNAO.2021.11304.0 doi: 10.22067/IJNAO.2021.11304.0
[24]	R. Storn, K. Price, Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces, J. Global Optimiz., 11 (1997), 341–359. https://doi.org/10.1023/A:1008202821328 doi: 10.1023/A:1008202821328
[25]	S. Chakraborty, A. Kumar, S. Absalom, E. Ezugwu, Differential evolution and its applications in image processing problems: a comprehensive review, Arch. Comput. Methods Eng., 30 (2023), 985-–1040. https://doi.org/10.1007/s11831-022-09825-5 doi: 10.1007/s11831-022-09825-5
[26]	Y. Wang, H. Liu, H. Long, Z. Zhang, S. Yang, Differential evolution with a new encoding mechanism for optimizing wind farm layout, IEEE Transact. Industr. Inform., 14 (2018), 1040–1054. https://doi.org/10.1109/TII.2017.2743761 doi: 10.1109/TII.2017.2743761
[27]	R. Chi, Z. Li, X. Chi, Z. Qu, H. Tu, Reactive power optimization of power system based on improved differential evolution algorithm, Math. Problems Eng., (2021), 1–19. https://doi.org/10.1155/2021/6690924 doi: 10.1155/2021/6690924
[28]	L. Jebaraj, C. Venkatesan, I. Soubache, C. C. A. Rajan, Application of differential evolution algorithm in static and dynamic economic or emission dispatch problem: A review, Renewable Sustain. Energy Rev., 77 (2017), 1206–1220. https://doi.org/10.1016/j.rser.2017.03.097 doi: 10.1016/j.rser.2017.03.097
[29]	X. Sui, S. C. Chu, J. Pan, H. Luo, Parallel compact differential evolution for optimization applied to image segmentation, Appl. Sci., 10 (2020), 2195. https://doi.org/10.3390/app10062195 doi: 10.3390/app10062195
[30]	M. Abdel-Basset, R. Mohamed, W. Elkhalik, M. Sharawi, Task scheduling approach in cloud computing environment using hybrid differential evolution, Mathematics, 10 (2022), 4049. https://doi.org/10.3390/math10214049 doi: 10.3390/math10214049
[31]	S. Tsafarakis, K. Zervoudakis, A. Andronikidis, E. Altsitsiadis, Fuzzy self-tuning differential evolution for optimal product line design, European J. Operat. Res., 287 (2020), 1161–1169. https://doi.org/10.1016/j.ejor.2020.05.018 doi: 10.1016/j.ejor.2020.05.018
[32]	X. Wang, T. M. Choi, Z. Li, S. Shao, An effective local search algorithm for the multidepot cumulative capacitated vehicle routing problem, IEEE Transact. Syst. Man Cybern. Syst., 50 (2020), 4948–4958. https://doi.org/10.1109/TSMC.2019.2938298 doi: 10.1109/TSMC.2019.2938298

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)