低约束密度分布式约束优化问题的求解算法

• 作者: 丁博 史殿习 唐扬斌 王怀民
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 分布式约束优化问题 多Agent 算法
• 年，卷（期）: 2011,（4）
• 所属期刊栏目: 系统软件与软件工程
• 页码范围: 625-639
• 分类号: TP311
• 字数: 13596字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2011.03765

摘要

多Agent协作过程中的许多挑战都可以建模为分布式约束优化问题.针对低约束密度的分布式约束优化问题,提出了一种基于贪婪和回跳思想的求解算法.在该算法中,各Agent基于贪婪原则进行决策.能够利用低约束密度问题中大量赋值组合代价为0这一特点来加快求解速度.同时,Agent间的回跳机制可以在贪婪原则陷入局部最优时保证算法的完全性.相对于已有主流算法,该算法可以在保持多项式级别的消息长度/空间复杂度的前提下,以较少的消息数目求解低约束密度的分布式约束优化问题.给出了算法关键机制的正确性证明,并通过实验验证了算法的上述性能优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王怀民	国防科学技术大学计算机学院	119	3450	29.0	56.0
3	史殿习	国防科学技术大学计算机学院	50	574	13.0	22.0
4	丁博	国防科学技术大学计算机学院	19	295	8.0	17.0
7	唐扬斌	国防科学技术大学计算机学院	5	179	3.0	5.0