| 低约束密度分布式约束优化问题的求解算法 |
| |
| 作者姓名： | 丁博 王怀民 史殿习 唐扬斌 |
| |
| 作者单位： | 1. 国防科学技术大学,计算机学院,湖南,长沙,410073
2. 国防科学技术大学,计算机学院,湖南,长沙,410073;国防科学技术大学,计算机学院,并行与分布处理国家重点实验室,湖南,长沙,410073 |
| |
| 基金项目： | 国家自然科学基金(90818028); 国家重点基础研究发展计划(973)(2011CB302600); 国家杰出青年科学基金(60625203) |
| |
| 摘 要： | 多Agent协作过程中的许多挑战都可以建模为分布式约束优化问题.针对低约束密度的分布式约束优化问题,提出了一种基于贪婪和回跳思想的求解算法.在该算法中,各Agent基于贪婪原则进行决策,能够利用低约束密度问题中大量赋值组合代价为0这一特点来加快求解速度.同时,Agent间的回跳机制可以在贪婪原则陷入局部最优时保证算法的完全性.相对于已有主流算法,该算法可以在保持多项式级别的消息长度/空间复杂度的前提下,以较少的消息数目求解低约束密度的分布式约束优化问题.给出了算法关键机制的正确性证明,并通过实验验证了算法的上述性能优势.
|
| 关 键 词： | 分布式约束优化问题 多Agent 算法 |
| 收稿时间： | 2009-06-16 |
| 修稿时间： | 2009-10-10 |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载免费的PDF全文 |
|
