论文部分内容阅读
分布式约束优化问题(DCOP)和非对称分布式约束优化问题(ADCOP)是解决分布式人工智能领域中多智能体系统(MAS)协同优化问题的重要方法,具有研究意义和实用价值。目前,DCOP求解算法大多是基于集中式单点寻优算法而提出的。而对于ADCOP求解算法的研究尚处于起步阶段,研究成果十分有限。蚁群优化思想(ACO)算法是一种基于种群的集中式优化算法,可以有效地解决集中式中组合优化问题,却很少应用于分布式约束推理问题中。DCOP和ADCOP可以看作是分布式的组合优化问题。因此,本文致力于提出一种基于蚁群优化思想的DCOP和ADCOP求解算法。主要工作如下:①提出了基于蚁群优化思想的DCOP求解算法(ACO_DCOP)。结合DCOP模型特点,本文主要研究了 ACO中构造图结构、转移概率、信息素更新等问题,将ACO应用于求解分布式约束优化问题。因此,本文提出了基于广度优先树结构的构造图。并且转移概率信息素部分考虑了当前上文取值状态,减少了无关信息素对决策的干扰;引入了局部代价预估机制,根据已构造的解来推测Agent赋值可能造成的局部代价预估值,使得启发式信息更加合理的反映Agent局部利益。对于信息素更新部分,本文将解的均值作为评价解的质量的标准,对信息素更新引入奖励惩罚机制,并提出加权信息素增量,来缓解过度惩罚的情况。此外,为了提高算法的并发性,本文引入了流水线技术。在理论分析中,我们证明了ACO_DCOP是一个anytime算法。最后,实验验证了ACO_DCOP算法的性能优于现有的DCOP非完备算法。②提出基于蚁群优化思想的ADCOP求解算法(ACO_ADCOP)。针对ADCOP的不对称性和ACO模型特点,本文主要研究了ADCOP中双向求解问题、隐私性、以及构造图和转移概率等问题。ACO_ADCOP采用深度优先伪树作为构造图结构。针对ADCOP中双向约束求解的问题,本文引入了基于树的反向检测机制,并且消息传递时仅与累加代价相关,保证了 Agent的隐私性。此外,在转移概率中启发式部分引入了局部代价预估机制,即启发式信息不仅考虑当前解与高优先级邻居造成的真实代价,还考虑了其与邻居的代价预估值,可以更好的评估局部利益。最后,本文实验验证了 ACO_ADCOP算法性能优于现有的ADCOP非完备算法。