[1]廖鑫,石美凤,陈媛.求解连续型分布式约束优化问题的自适应多点交叉遗传算法[J].智能系统学报,2023,18(4):793-802.[doi:10.11992/tis.202202017]
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]
点击复制
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]
求解连续型分布式约束优化问题的自适应多点交叉遗传算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
18
期数:
2023年第4期
页码:
793-802
栏目:
学术论文—智能系统
出版日期:
2023-07-15
- Title:
- Adaptive multi-point crossover genetic algorithm for solving continuous distributed constraint optimization problems
- Keywords:
- continuous distributed constraint optimization problems; anytime property; adaptive multi-point crossover; genetic algorithm; distributed population; breadth first search pseudo-tree; agent; solution quality
- 分类号:
- TP183
- 摘要:
- 针对连续型分布式约束优化问题(continuous distributed constraint optimization problems, C-DCOPs)求解算法的anytime属性的缺失、约束函数形式的限制和无法保证收敛等局限，本文提出一种求解C-DCOP的自适应多点交叉遗传算法(adaptive multi-point crossover genetic algorithm based C-DCOP, AMCGA)。在AMCGA中，智能体(agent)构建分布式种群和广度优先搜索(breadth first search, BFS)伪树以分布式地计算个体适应度；通过贪婪策略选择精英个体进行自适应多点交叉实现全局搜索，智能体之间协同通信保证分布式种群中解的一致性；利用变异算子完成局部搜索。AMCGA适用于任意形式的约束函数，并被证明具有任意时间属性和全局收敛性。在4类基准问题上的广泛实验结果表明，AMCGA的求解质量优于最先进的C-DCOP求解算法，能有效地打破目前C-DCOP求解算法的局限，并在求解质量方面存在20%~30%的提升。
- 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.
备注/Memo
收稿日期:2022-02-22。
基金项目:重庆市教育委员会科学技术研究计划青年项目（KJQN202001139）；重庆市基础研究与前沿探索项目（cstc2018jcyjAX0287）；重庆理工大学研究生创新项目（clgycx20203110）；重庆理工大学科研启动基金项目（2019ZD03）.
作者简介:廖鑫，硕士研究生，主要研究方向为计算智能与分布式约束优化;石美凤，讲师，主要研究方向为计算智能、多智能体系统、分布式约束优化、多目标优化和图像处理。主持重庆市科委基础研究与前沿探索项目、重庆市教委科学技术研究计划青年项目、教育部产学合作协同育人项目等项目3项，授权发明专利2项。发表 学术论文10余篇。;陈媛，教授，主要研究方向为智能信息处理、数据挖掘 。主持和参与重庆市科委攻关项目、重庆市科委自然科学基金一般项目等4项。发表学术论文20余篇，出版著作5部。
通讯作者:石美凤.E-mail:shimf@cqut.edu.cn
更新日期/Last Update:
1900-01-01