论文部分内容阅读
分布式约束优化问题(DCOP)是多智能体系统(MAS)领域中的一个基本框架,可对多智能体协作优化问题进行建模,已成功应用于任务调度、资源分配等问题中。目前,求解DCOP的非完备算法大都采用单解优化思想,并且普遍存在过早收敛、解的质量差等问题。针对上述问题,本文致力于研究利用基于种群进化的遗传算法来提高DCOP的求解质量。具体研究内容如下:
①针对现有基于局部搜索的DCOP求解算法易陷入局部最优,提出一个基于遗传算法的局部搜索算法框架(LSGA)。通过分析遗传算法和基于局部搜索的DCOP求解算法的特性,提出了基于种群的并行局部搜索框架和一系列适用于分布式环境下的全新遗传算子以提升局部搜索算法的寻优能力。具体地,该框架以局部利益与取值出现频次相结合构建适应度函数,以实现无全局信息的分布式环境下局部利益和全局利益的平衡;利用Agent之间的通信结构设计出一种适用于DCOP的交叉方法,以实现无全局控制的分布式环境下的交叉操作;提出自适应的交叉概率和变异概率来控制交叉算子和变异算子对局部搜索算法的影响。本文理论分析了基于LSGA的局部搜索算法的收敛性和复杂度,实验结果表明LSGA不仅有效地提高了局部搜索算法的性能并优于现有的局部搜索DCOP改进求解算法。
②针对基于LSGA的局部搜索算法由于搜索策略单一而导致种群多样性受限的问题,提出基于遗传算法的多局部搜索策略融合DCOP求解算法(Multi-Subswarm_DCOP)。通过分析不同局部搜索策略的特性,结合遗传算法的个体信息交互模式,构建出基于多子群的多局部搜索策略融合的遗传算法框架,借此设计出Multi-Subswarm_DCOP算法。具体地,该算法构建了包含不同个体的3个子群并让分属不同子群的个体交替排列;然后,3个子群分别采用爬山法、模拟退火和变邻域搜索策略进行并行局部寻优以保持种群多样性;借于不同子群个体的交替排列,利用类似轮转的方式执行交叉操作,以实现不同局部搜索策略下寻优信息的融合;此外,提供了一个基于自适应变异概率的变异算子实现搜索过程中的局部扰动。本文理论分析了Multi-Subswarm_DCOP算法的复杂度,实验结果表明Multi-Subswarm_DCOP算法在多种测试问题的求解上均优于基于LSGA的局部搜索算法以及其它类型的DCOP非完备求解算法。
①针对现有基于局部搜索的DCOP求解算法易陷入局部最优,提出一个基于遗传算法的局部搜索算法框架(LSGA)。通过分析遗传算法和基于局部搜索的DCOP求解算法的特性,提出了基于种群的并行局部搜索框架和一系列适用于分布式环境下的全新遗传算子以提升局部搜索算法的寻优能力。具体地,该框架以局部利益与取值出现频次相结合构建适应度函数,以实现无全局信息的分布式环境下局部利益和全局利益的平衡;利用Agent之间的通信结构设计出一种适用于DCOP的交叉方法,以实现无全局控制的分布式环境下的交叉操作;提出自适应的交叉概率和变异概率来控制交叉算子和变异算子对局部搜索算法的影响。本文理论分析了基于LSGA的局部搜索算法的收敛性和复杂度,实验结果表明LSGA不仅有效地提高了局部搜索算法的性能并优于现有的局部搜索DCOP改进求解算法。
②针对基于LSGA的局部搜索算法由于搜索策略单一而导致种群多样性受限的问题,提出基于遗传算法的多局部搜索策略融合DCOP求解算法(Multi-Subswarm_DCOP)。通过分析不同局部搜索策略的特性,结合遗传算法的个体信息交互模式,构建出基于多子群的多局部搜索策略融合的遗传算法框架,借此设计出Multi-Subswarm_DCOP算法。具体地,该算法构建了包含不同个体的3个子群并让分属不同子群的个体交替排列;然后,3个子群分别采用爬山法、模拟退火和变邻域搜索策略进行并行局部寻优以保持种群多样性;借于不同子群个体的交替排列,利用类似轮转的方式执行交叉操作,以实现不同局部搜索策略下寻优信息的融合;此外,提供了一个基于自适应变异概率的变异算子实现搜索过程中的局部扰动。本文理论分析了Multi-Subswarm_DCOP算法的复杂度,实验结果表明Multi-Subswarm_DCOP算法在多种测试问题的求解上均优于基于LSGA的局部搜索算法以及其它类型的DCOP非完备求解算法。