分布式约束优化算法若干问题研究

作     者：段沛博 

作者单位：东北大学 

学位级别：硕士

导师姓名：张斌

授予年度：2013年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：DCOP 算法分析 MULBS+ 策略自适应性 APLODO 

摘      要：在实际生活中,许多问题都可以抽象成为多agent模型进行解决,而分布式约束优化(DCOP)算法是近年解决多agent问题的主要算法。多agent问题的求解具有NP难度,如何能够快速的获得最优、完备的解决方案,对提高生产率,促进社会的发展具有重要意义。虽然目前有很多DCOP算法,但由于大部分算法是针对问题的特殊求解目标提出的,而且算法的执行策略各异,求解质量也不尽相同,因此当有新的实际问题抽象成为多agent模型时,算法在选择上就出现了制约。其次,虽然当前有相关研究,将主要DCOP算法进行整合,建立了分布式约束优化问题解决框架(FRODO),但该框架主要用于算法性能分析,在实际问题应用中的算法选择方面存在不足,同时,由于该框架的提出时间较早,因此算法的时效性和性能两个方面也亟待提高。 针对这些问题,本文分析了FRODO框架在解决实际问题时存在的不足。并根据分析结果,从算法的扩展性、策略自适应性两方面完善了算法框架。在此基础上,本文根据约束图特征对典型算法进行分类并给出了策略自适应匹配算法,最后,本文设计并实现了支持策略自适应的DCOP算法平台APLODO,针对平台测试过程中发现的MULBS算法的不足,对其进行了改进。 在具体实现中,本文首先对实际问题在FRODO框架中的解决过程进行了分析,分析表明,一个支持策略自适应的DCOP算法框架,应具备良好的算法可扩展性以及策略自适应性,针对这两个特性,一方面,本文对DCOP算法的执行过程进行模块划分,并以MULBS算法为例阐述了该模式下的算法实现方式。另一方面,本文根据算法搜索策略、解的完整度、异步性、时效性选取了5种典型算法,在完善的评价指标体系下,从约束图密度、节点数量和取值空间大小三个特征入手,对算法进行性能的分析、分类。然后,本文结合实际问题求解目标以及算法分类结果,提出策略自适应匹配算法,该算法的核心是算法的打分机制,其次,本文在FRODO框架基础上设计并实现了APLODO平台,最后通过对平台的算法测试,发现MULBS算法在冲突解决机制和算法并行性方面存在缺陷,因此本文给出了MULBS的改进算法MULBS+,实验表明,该算法除增加一定的通信信息外,在测试指标的其他方面都优于原算法。