A High-precision Decomposition Strategy for Large-scale Constrained Problems

Fabiola Paz; Guillermo Leguizamon; Efren Mezura-Montes

Autores/as

Fabiola Paz Universidad Nacional de Jujuy, Argentina https://orcid.org/0000-0003-2671-9526
Guillermo Leguizamon Universidad Nacional de San Luis, Argentina https://orcid.org/0000-0003-3784-1754
Efren Mezura-Montes Universidad de Veracruz, México https://orcid.org/0000-0002-1565-5267

Palabras clave:

algoritmo coevolutivo cooperativo, problemas con restricciones a gran escala, agrupación diferencial, separabilidad aditiva y multiplicativa

Resumen

Las estrategias de descomposición aplicadas a problemas de optimización, como los algoritmos Coevolutivos Cooperativos (CC), han demostrado ser eficaces para abordar diversos problemas de optimización con restricciones a gran escala. Este enfoque descompone un problema con restricciones de gran escala en subproblemas más simples y de menor escala, sin afectar negativamente el rendimiento del algoritmo de optimización. La eficacia del enfoque CC depende en gran medida de la calidad de dicha descomposición. Una buena descomposición tiene en cuenta la interacción entre las variables. Sin embargo, estrategias recientes como RDG y ERDG sólo identifican interacciones aditivas en la descomposición del problema. En consecuencia, estos métodos suelen ser eficaces únicamente para problemas que presentan esta propiedad. No obstante, en problemas reales pueden surgir otros tipos de separabilidad además de la aditiva. Este artículo propone una nueva estrategia de descomposición denominada Agrupación Diferencial Dual para problemas con restricciones (CDDG, por sus siglas en inglés). La novedad de CDDG radica en mejorar la descomposición en funciones separables, tanto aditivas como multiplicativas, lo que aumenta considerablemente el alcance de CC. Para validar la efectividad del CDDG, se llevan a cabo experimentos y comparaciones con métodos de vanguardia. Los resultados demuestran que CDDG puede adaptarse mejor a las características específicas de cada problema de prueba.

Descargas

Los datos de descarga aún no están disponibles.

Referencias

P. Xu, W. Luo, X. Lin, J. Zhang, Y. Qiao, and X. Wang, “Constraintobjective cooperative coevolution for large-scale constrained optimization,” ACM Transactions on Evolutionary Learning and Optimization, vol. 1, no. 3, pp. 1–26, 2021.

M. Omidvar, X. Li, and X. Yao, “A review of population-based metaheuristics for large-scale black-box global optimization: Part b,” IEEE Transactions on Evolutionary Computation, 2021.

D. Liu, Z. Hu, Q. Su, and M. Liu, “A niching differential evolution algorithm for the large-scale combined heat and power economic dispatch problem,” Applied Soft Computing, vol. 113, p. 108 017, 2021.

Y.-H. Jia, Y. Mei, and M. Zhang, “A two-stage swarm optimizer with local search for water distribution network optimization,” IEEE Transactions on Cybernetics, vol. 53, no. 3, pp. 1667–1681, 2021.

A. Ghosh, K. Deb, E. Goodman, and R. Averill, “An interactive knowledgebased multiobjective evolutionary algorithm framework for practical optimization problems,” IEEE Transactions on Evolutionary Computation, vol. 28, no. 1, pp. 223–237, 2023.

J. Zhang, L. Xing, G. Peng, F. Yao, and C. Chen, “A large-scale multiobjective satellite data transmission scheduling algorithm based on svm y nsga-ii,” Swarm and Evolutionary Computation, vol. 50, p. 100 560, 2019.

J. Xiao, T. Zhang, J. Du, and X. Zhang, “An evolutionary multiobjective route grouping-based heuristic algorithm for large-scale capacitated vehicle routing problems,” IEEE transactions on cybernetics, vol. 51, no. 8, pp. 4173–4186, 2019.

M. A. Potter and K. A. De Jong, “A cooperative coevolutionary approach to function optimization,” in International Conference on Parallel Problem Solving from Nature, Springer, 1994, pp. 249–257.

R. Zhong, E. Zhang, and M. Munetomo, “Cooperative coevolutionary surrogate ensemble-assisted differential evolution with efficient dual differential grouping for large-scale expensive optimization problems,” Complex and Intelligent Systems, vol. 10, no. 2, pp. 2129–2149, 2024.

A. Vakhnin and E. Sopov, “Improving de-based cooperative coevolution for constrained large-scale global optimization problems using an increasing grouping strategy,” in IOP Conference Series: Materials Science and Engineering, IOP Publishing, vol. 734, 2020, p. 012 099.

C. Peng and Q. Hui, “Epsilon-constrained ccpso with different improvement detection techniques for large-scale constrained optimization,” in 2016 49th Hawaii International Conference on System Sciences (HICSS), IEEE, 2016, pp. 1711–1718.

E. Sayed, D. Essam, R. Sarker, and S. Elsayed, “Decomposition-based evolutionary algorithm for large scale constrained problems,” Information Sciences, vol. 316, pp. 457–486, 2015.

A. E. Aguilar-Justo, E. Mezura-Montes, S. M. Elsayed, and R. A. Sarker, “Decomposition of large-scale constrained problems using a genetic-based search,” in 2016 IEEE International Autumn Meeting on Power, Electronics and Computing (ROPEC), IEEE, 2016, pp. 1–6.

C. Peng and Q. Hui, “Comparison of differential grouping and random grouping methods on sccpso for large-scale constrained optimization,” in 2016 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2016, pp. 2057–2063.

A. E. Aguilar-Justo and E. Mezura-Montes, “A local cooperative approach to solve large-scale constrained optimization problems,” Swarm and Evolutionary Computation, vol. 51, p. 100 577, 2019.

M. Yang, A. Zhou, C. Li, and X. Yao, “An efficient recursive differential grouping for large-scale continuous problems,” IEEE Transactions on Evolutionary Computation, 2020.

F. Paz, G. Leguizamon, and E. Mezura-Montes, “Efficient differential grouping method for large-scale constrained optimization,” in 30 Congreso Argentino de Ciencias de la Computacion (CACIC). Del 7 al 10 de octubre, 2024), 2024.

J. Liu, R. Sarker, S. Elsayed, D. Essam, and N. Siswanto, “Large-scale evolutionary optimization: A review and comparative study,” Swarm and Evolutionary Computation, p. 101 466, 2024.

I. Rahimi, A. H. Gandomi, F. Chen, and E. Mezura-Montes, “A review on constraint handling techniques for population-based algorithms: From single-objective to multi-objective optimization,” Archives of Computational Methods in Engineering, vol. 30, no. 3, pp. 2181–2209, 2023.

T. Takahama and S. Sakai, “Efficient constrained optimization by the econstrained adaptive differential evolution,” in IEEE congress on evolutionary computation, IEEE, 2010, pp. 1–8.

K. Deb, “An efficient constraint handling method for genetic algorithms,” Computer methods in applied mechanics and engineering, vol. 186, no. 2-4, pp. 311–338, 2000.

J.-Y. Li, Z.-H. Zhan, K. C. Tan, and J. Zhang, “Dual differential grouping: A more general decomposition method for large-scale optimization,” IEEE Transactions on Cybernetics, 2022.

IEEE, “Ieee standard for floating-point arithmetic,” IEEE Std 754-2019, 2019.

Y. Sun, M. N. Omidvar, M. Kirley, and X. Li, “Adaptive threshold parameter estimation with recursive differential grouping for problem decomposition,” in Proceedings of the genetic and evolutionary computation conference, 2018, pp. 889–896.

F. Paz, G. Leguizamon, and E. Mezura-Montes, “A novel cooperative coevolutionary algorithm for large-scale constrained optimization,” in Argentine Congress of Computer Science, Springer, 2024, pp. 19–33.

Y. Sun, P. Xu, Z. Zhang, T. Zhu, and W. Luo, “Brain storm optimization integrated with cooperative coevolution for large-scale constrained optimization,” in International Conference on Swarm Intelligence, Springer, 2023, pp. 356–368.

M. Chen, W. Du, Y. Tang, Y. Jin, and G. G. Yen, “A decomposition method for both additively and nonadditively separable problems,” IEEE Transactions on Evolutionary Computation, vol. 27, no. 6, pp. 1720–1734, 2022.

Y. Sun, X. Li, A. Ernst, and M. N. Omidvar, “Decomposition for largescale optimization problems with overlapping components,” in 2019 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2019, pp. 326–333.