[1]LIAO Xin,SHI Meifeng,CHEN Yuan.Adaptive multi-point crossover genetic algorithm for solving continuous distributed constraint optimization problems[J].CAAI Transactions on Intelligent Systems,2023,18(4):793-802.[doi:10.11992/tis.202202017]
Copy

Adaptive multi-point crossover genetic algorithm for solving continuous distributed constraint optimization problems

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 18 Number of periods: 2023 4 Page number: 793-802 Column: 学术论文—智能系统 Public date: 2023-07-15
Title:
Adaptive multi-point crossover genetic algorithm for solving continuous distributed constraint optimization problems
Author(s):
LIAO Xin;  SHI Meifeng;  CHEN Yuan
College of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400000, China
Keywords:
continuous distributed constraint optimization problems; anytime property; adaptive multi-point crossover; genetic algorithm; distributed population; breadth first search pseudo-tree; agent; solution quality
CLC:
TP183
DOI:
10.11992/tis.202202017
Abstract:
Aiming at the limitations of the solving algorithm for continuous distributed constraint optimization problems (DCOPs), such as the lack of anytime property, the limitation of constraints function form and the inability to guarantee convergence, an adaptive multi-point crossover genetic algorithm for solving C-DCOP (AMCGA) is proposed. In AMCGA, the agent firstly builds distributed population and breadth first search (BFS) pseudo-tree to calculate the individual fitness in a distributed way. Secondly, the agent selects elite individuals through greedy strategy for adaptive multi-point crossover, achieving global search; cooperative communication between agents ensures the consistency of solutions in the distributed population. Finally, the agent uses mutation operator to complete local search. AMCGA is suitable for any form of constraint function and is proved to have anytime property and global convergence. Extensive experimental results on four types of benchmark problems demonstrate that the solution quality of AMCGA is superior to the state-of-the-art C-DCOP solving algorithms, it can effectively break through the limitations of current C-DCOP solving algorithms, and improve the solution quality by 20% to 30%.
References:
[1] 段沛博, 张长胜, 张斌. 分布式约束优化方法研究进展[J]. 软件学报, 2016, 27(2): 264–279
ALLAN R L, FABRICIO E, JEAN P A. Distributed constraint optimization problems: review and perspectives[J]. Expert systems with applications, 2016, 27(2): 264–279
[2] 邓衍晨. 求解分布式约束优化问题的推理算法研究[D]. 重庆: 重庆大学, 2018.
DENG Yanchen. The study on inference-based algorithms for distributed constraint optimization problems[D]. Chongqing: Chongqing University, 2018.
[3] SULTANIK E A, MODI P J, REGLI W C. On modeling multiagent task scheduling as a distributed constraint optimization problem[C]//Proceedings of the 20th International Joint Conference on Artifical Intelligence. New York: ACM, 2007: 1531?1536.
[4] 马瑞, 金艳, 刘鸣春. 基于机会约束规划的主动配电网分布式风光双层优化配置[J]. 电工技术学报, 2016, 31(3): 145–154
MA Rui, JIN Yan, LIU Mingchun. Bi-level optimal configuration of distributed wind and photovoltaic generations in active distribution network based on chance constrained programming[J]. Transactions of China electrotechnical society, 2016, 31(3): 145–154
[5] 吴玲, 张朱峰, 吴威. 基于分布式约束优化的多UCAV协同任务分配[J]. 海军工程大学学报, 2018, 30(6): 64–68
BARTHS A, ENEMBRECK F. Distributed constraint optimization with MULBS: a case study on collaborative meeting scheduling[J]. Journal of network and computer applications, 2018, 30(6): 64–68
[6] FERDINANDO F, ENRICO P, WILLIAM Y. A multiagent system approach to scheduling devices in smart homes[C]// Proceedings of the 16th Conference on Autonomous Agents and Multi-Agent Systems. Paulo: AAMAS Press, 2017: 981–989.
[7] MULDOON C, O’HARE G M P, O’GRADY M J, et al. Distributed constraint optimization for resource limited sensor networks[J]. Science of computer programming, 2013, 78(5): 583–593.
[8] 雷兴明, 邢昌风, 吴玲. 基于分布式约束优化的武器目标分配问题研究[J]. 计算机工程, 2012, 38(7): 128–130
CHENG Shanjun, RAJA A, XIE Jiang. Dynamic multiagent load balancing using distributed constraint optimization techniques[J]. Web intelligence and agent systems, 2012, 38(7): 128–130
[9] JMODI P J, SHEN W M, TAMBE M. Adopt: asynchronous distributed constraint optimization with quality guarantees[J]. Artificial intelligence, 2005, 161(1/2): 149–180.
[10] PETCU A, FALTINGS B. A scalable method for multiagent constraint optimization[C]//Proceedings of the 19th International Joint Conference on Artificial Intelligence. New York: ACM, 2005: 266?271.
[11] LITOV O, MEISELS A. Forward bounding on pseudo-trees for DCOPs and ADCOPs[J]. Artificial intelligence, 2017, 252: 83–99.
[12] ZHANG Weixiong, WANG Guandong, ZHAO Xing, 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.
[13] FARINELLI A, ROGERS A, PETCU A, et al. Decentralised coordination of low-power embedded devices using the max-sum algorithm[C]// Proceedings of the 7th International Joint Conference on Autonomous Agents and Multi-Agent Systems. Estoril: AAMAS Press, 2008: 639–646.
[14] MAHESWARAN R T, PEARCE J P, TAMBE M. A family of graphical-game-based algorithms for distributed constraint optimization problems[J]. Coordination of large-scale multiagent systems, 2006: 127–146.
[15] CHEN Ziyu, WU Tengfei, DENG Yanchen, et al. An ant-based algorithm to solve distributed constraint optimization problems[C]//Proceedings of the 32th AAAI Conference on Artificial Intelligence. New Orleans: AAAI Press, 2018:4653–4661.
[16] STRANDERS R, FARINELLI A, ROGERS A, et al. Decentralised coordination of continuously valued control parameters using the max-sum algorithm[C]// Proceedings of the 8th International Conference on Autonomous Agents and Multi-Agent Systems. Budapest: Springer Press, 2009: 601?608.
[17] 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. Lison: IOS Press, 2010: 61?66.
[18] KHOI D H, WILLIAM Y, MAKOTO Y, et al. New algorithms for continuous distributed constraint optimization problems[C]// Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems. Auckland: Springer Press, 2020: 502?510.
[19] 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.
[20] AMIT S, MOUMITA C, MD M K. A local search based approach to solve continuous DCOPs[C]// Proceedings of the 20th International Conference on Autonomous Agents and Multi-Agent Systems. Richland: Springer Press, 2021: 1127?1135.
[21] EIBEN A E, RAUE P E, RUTTKAY Z. Solving constraint satisfaction problems using genetic algorit-hms[C]//Proceedings of the First IEEE Conference on Evolutionary Computation. Orlando: IEEE Press, 1994:542?547.
[22] CHEN Ziyu, LIU Lizhen, HE Jingyuan, et al. A genetic algorithm based framework for local search algorithms for distributed constraint optimization problems[J]. Autonomous agents and multi-agent systems, 2020, 34(2): 41.
[23] CHEN Ziyu, HE Zhen, HE Chen. An improved DPOP algorithm based on breadth first search pseudo-tree for distributed constraint optimization[J]. Applied intelligence, 2017, 47(3): 607–623.
[24] ALBERT R, BARABASI A L. Statistical mechanics of complex networks[EB/OL]. (2001-06-09)[2022-02-22]. https://arxiv.org/abs/cond-mat/0106096.
[25] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440–442.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems