随着硬件和网络技术的发展,以及分布式计算环境的广泛应用,分布式约束优化问题(Distributed Constraint Optimization Problem,DCOP)作为建模多 agent系统的一个重要框架,逐渐成为研究热点。目前,DCOP的研究主要分为三个层面,包括模型层,算法层以及应用层。在模型层中,传统DCOP框架过分依赖agent之间的对称约束设置,并且难以适用于动态环境的变化。在算法层面,DCOP算法主要分为完备算法以及非完备算法。完备算法能够找到问题的最优解,但需要消耗过多的计算与通信资源。非完备算法虽然能够有效的减缓资源消耗带来的压力,但求得的解一般为次优解,因此常用于求解规模较大的DCOP。在应用层方面,实际问题首先被构建成为多agent系统,再利用DCOP建模,最后选取合适的DCOP算法进行求解。基于以上三个研究层面,本文从模型适用性、算法求解效率提升以及DCOP应用拓展三个角度开展DCOP相关研究,并且通过实验和仿真对所提出的相关算法和应用进行了验证,具体包括:(1)针对目前已有的DCOP算法研究,本文进行了综述。具体地,我们首先介绍了 DCOP模型,对DCOP的适用性进行了分析,而后,基于已有的DCOP算法研究,我们总结出DCOP算法求解的基本流程。在此流程基础上,从解的质量保证、求解策略等角度深入地对算法进行了较为完整的分类。最后,通过对部分经典DCOP算法的对比,总结了当前DCOP研究中尚且存在的问题,并以此开展研究。(2)针对非对称DCOP(Asymmetric DCOP,ADCOP)模型,结合隐私保护策略,改进原有的DCOP算法,使其适用于求解ADCOP。具体地,本文首先提出了多重混淆机制,通过该机制,可以有效的防止一个agent的约束值信息被相邻agent获知或推理间接得知。而后,基于该机制,本文提出了两种求解ADCOP的算法,分别为基于PEAV(Private Event As Variable)表达方式的非完备算法AsyDALO(Asymmetric Distributed Asynchronous Local Optimization)以及基于类AsyDPOP(Asymmetric Distributed Pseudo-tree Optimization Procedure)的 AsyDALO算法。其中,两种算法均可以对所求的解提供一个理论保证。实验表明,相对于没有多重混淆机制的ADCOP算法,本文提出的基于两种机制的算法不仅可以提供可靠的解,并且在隐私保护方面有很大的提升。(3)通过分析MULBS(Multiple Local Bound Search)算法的性能瓶颈,本文提出其改进算法,MULBS+。两者的差异体现在两个方面,首先,不同于MULBS中的搜索策略,我们提出了最小冲突机制搜索方案,并将其应用在MULBS+算法中。另一方面MULBS+根据约束图的密度,通过子图的动态划分,进行子图内的局部并行搜索和子图间的全局并行搜索,进而提高算法的并行性。实验结果表明,该算法对于求解约束图密度较大的DCOP,除个别情况由于并行搜索的消息传递而造成执行时间增加外,其求解的准确度和求解速度方面都优于原有算法。(4)针对非完备算法的研究,本文提出了局部稳定支持并行(Local Stability Supported Parallel,LSPA)搜索算法。首先,文中提出了局部稳定支持的概念,用于评估agent是否需要更改当前赋值。其次,通过构建一个更值得信任的初始解,使LSPA能够更快地收敛到稳定解。为了实现算法的并行搜索,LSPA以agent为单位,根据局部稳定支持的定义,计算agent个体局部稳定支持特性。实验表明,LSPA能在理想的时间内获得更好的解决方案。(5)针对异构网络中的用户关联问题,本文利用DCOP,从多agent系统的角度对该类问题进行建模。为了提高DCOP算法求解的效率,在模型的建立中,我们通过引入参数η,使模型中的agent和约束数量可以得到有效的控制。除此之外,文章对所求得的解的质量进行了理论分析,分析表明该解与η的选取有关。与其他已有的该类问题解决方案相比,该方法在整体网络吞吐量方面,有较高的性能提升。