Local Elite-Guided Collaborative Optimization Algorithm for Continuous Distributed Constraint Optimization Problems

Meifeng Shi; Yanmei Yu; Yuan Chen

doi:10.54097/92sp0c97

Authors

Meifeng Shi
Yanmei Yu
Yuan Chen

DOI:

https://doi.org/10.54097/92sp0c97

Keywords:

Continuous Distributed Constraint Optimization Problems, Local Elite-Guided Collaboration, Differentiated Strategy, Cross-population Elite Recombination

Abstract

To address the issues of premature convergence to local optima and slow convergence speed in Continuous Distributed Constraint Optimization Problems (C-DCOPs), this paper proposes a Local Elite-Guided Collaborative Optimization (EGA-LC) algorithm. Utilizing a Breadth-First Search (BFS) pseudo-tree, the algorithm constructs a distributed population structure partitioned into ten sub-populations for parallel search, each further classified into dominant, non-dominant, and local dominant sub-populations based on fitness. Subsequently, a differential evolution strategy is designed to guide individual updates through the synergistic influence of global elites and local dominant solutions, enabling deep mining of high-quality local constraint information. Furthermore, a periodic cross-population recombination and reassignment mechanism is introduced, which leverages historical global optimal solutions to accelerate convergence and prevents evolution stagnation by reallocating sub-populations. Experimental results on four benchmark problem sets demonstrate that EGA-LC significantly outperforms five state-of-the-art algorithms in terms of both solution quality and convergence speed.

Downloads

Download data is not yet available.

References

[1] Pujol-onzalez M. Multi-agent coordination: DCOP and beyond[C]//IJCAI Proceedings Internation-al Joint Conference on Artificial Intelligence.2011,22(3):2838.

[2] Leite A, Enembreck F, Barthes J P A. Distributed constraint optimization problems: Review and perspectives[J]. Expert Systems with Applications,2014, 41(11):5139-5157.

[3] Kumar A, Faltings B, Petcu A. Distributed constraint optimization with structured resource constraints[C]//Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS).2009:923-930.

[4] Muldoon C, O'Hare G M P, O'Grady M J, et al. Distributed constraint optimisation for resource limited sensor networks[J]. Science of Computer Programming, 2013,78(5):583-593.

[5] Fioretto F, Yeoh W, Pontelli E. A multiagent system approach to scheduling devices in smart homes[C]//Proceedings of the 16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).2017:981-989.

[6] Wang Jie. Research on Complete Synchronous Search Algorithms for Distributed Constraint Optimization Problems Based on Pseudotrees [D]. Chongqing University, 2023.

[7] Modi P J, Shen W M, Tambe M, et al. ADOPT: Asynchronous distributed constraint optimization with quality guarantees[J]. Artificial Intelligence, 2005, 161(1-2): 149-180.

[8] Rashik M, Rahman M M, han M M, et al. Speeding up distributed pseudo-tree optimization procedures with cross edge consistency to solve DCOP[J]. Applied Intelligence, 2021, 51: 1733- 1746.

[9] Zhang W, Wang G, Xing Z, et al. Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks[J]. Artificial Intelligence,2005,161(1-2):55-87.

[10] Okamoto S, Zivan R, Nahon A. Distributed Breakout: Beyond Satisfaction[C]// Proc. of the 25th International Joint Conference on Artifical Intelligence,2016,447-453.

[11] Leite A R, Enembreck F, Barthes J P A. Distributed constraint optimization problems: Review and perspectives[J].Expert Systems with Applications, 2014, 41 (11): 5139-5157.

[12] Hsin C, Liu M. Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms[C]//Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN).2004:433-442.

[13] Stranders R, Farinelli A, Rogers A, et al. Decentralised control of continuously valued control parameters using the max-sum algorithm[J].2009.

[14] Voice T, Stranders R, Rogers A, et al. A hybrid continuous max-sum algorithm for decentralised coordination[C]//Proceedings of the 19th European Conference on Artificial Intelligence. 2010:61-66.

[15] Hoang K D, Yeoh W, Yokoo M, et al. New algorithms for continuous distributed constraint optimization problems[C]//Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems. 2020:502-510.

[16] Choudhury M, Mahmud S, Khan M M. A particle swarm based algorithm for functional distributed constraint optimization problems[C]// Proceedings of the 34th AAAI Conference on Artificial Intelligence. New York: AAAI Press, 2020:7111-7118.

[17] Shi M, Liao X, Chen Y. A particle swarm with local decision algorithm for functional distributed constraint optimization problems[J].International Journal of Pattern Recognition and Artificial Intelligence, 2022,36(12):2259025.

[18] Sarker A, Choudhury M, Khan M M. A local search based approach to solve continuous DCOPs[C] //Proc of the 20th International Conference on Autonomous Agents and Multiagent Systems,2021:1127-1135.

[19] Liao Xin, Shi Meifeng, Chen Yuan. An adaptive multi-point crossover genetic algorithm for solving continuous distributed constraint optimization problems [J]. CAAI Transactions on Intelligent Systems, 2023, 18(04): 793-802.

[20] Shi M, Zhang P, Liao X, et al. An estimation of distribution based algorithm for continuous distributed constraint optimization problems[J]. Information Technology and Control, 2024,53(1):80-97

[21] Voice T, Stranders R, Rogers A, et al. A hybrid continuous max-sum algorithm for decentralised coordination[M]//ECAI 2010. IOS Press, 2010: 61-66.

[22] Sarker, A., Choudhury, M., Khan, M. M. A local search based approach to solve continuous DCOPs[C]//Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems,2021:1127-1135.