一种基于遗传算法的连续型分布式约束优化问题求解方法

摘要

本发明公开了一种基于遗传算法的连续型分布式约束优化问题求解方法(AMCGA)，在AMCGA中，智能体(Agent)首先构建分布式种群和广度优先搜索(BreadthFirstSearch,BFS)伪树以分布式地计算个体适应度；然后通过贪婪策略选择精英个体进行自适应多点交叉实现全局搜索，智能体之间协同通信保证分布式种群中解的一致性；最后利用变异算子完成局部搜索。AMCGA适用于任意形式的约束函数，并被证明是具有anytime属性和全局收敛性。在四类基准问题上的广泛实验结果表明，AMCGA的求解质量优于最先进的C‑DCOP求解算法。AMCGA能有效地打破目前C‑DCOP求解算法的局限，并在求解质量方面存在20％至30％的提升。

说明书

技术领域

本发明涉及约束优化方法，特别涉及一种基于遗传算法的连续型分布式约束优化问题求解方法。

背景技术

分布式约束优化问题(Distributed Constraint Optimization Problems,DCOPs)是解决分布式多智能体系统建模的有效框架。DCOP由一组智能体构成，每个智能体控制一组离散变量，通过与局部的智能体协同通信优化全局目标函数。全局目标函数被定义为约束代价的集合，其中约束代价由变量所定义。相比于传统的集中式优化，DCOP强调通过局部交互使得全局最优，因此DCOP具有更强的容错性和更高的并行度。目前DCOP已经广泛应用于实际生活，如会议调度，微网控制，任务调度，智能家居，传感器网络和资源分配等。DCOP求解算法主要分为完备算法和非完备算法，完备算法如ADOPT，DPOP和PT-FB等提供一个全局最优解，但计算开销和内存需求随着问题规模增加而呈现指数级增长；非完备算法如DSA，Max-sum，MGM和ACO-DCOP等在较低的计算开销和内存需求下提供一个近似解。然而在一些实际应用中，智能体必须取得一个或者多个连续值参数，比如方向，速度或者传感器激活时间等。DCOP建模连续型变量问题的效果并不理想，因此Stranders等人提出了连续型DCOP(Continuous DCOP,C-DCOP)来更有效地建模连续型变量应用。与DCOP相比，C-DCOP的变量和值域是连续的，并且约束代价由一组函数所定义。

近年来，为了应对C-DOCP中变量，值域和约束代价的变化，研究人员提出了连续最大和算法(Continuous Max-Sum,CMS)。在CMS中，约束代价函数被近似为分段线性函数，通过对比离散最大和和连续最大和算法，由CMS能够得到更高质量的解证明了C-DCOP的必要性。然而只有极少数实际应用可以适用于分段线性函数。混合连续最大和(HybridContinuous Max-Sum,HCMS)首先通过离散最大和获得一组近似解，通过非线性优化方法提高近似解的精度。虽然HCMS解决了分段线性函数的局限，但由于存在导数计算，使得HCMS不适用于不可微的问题，并且不能保证收敛。精确连续DPOP(Exact Continuous DPOP,EC-DPOP)，近似连续DPOP(Approximate Continuous DPOP,AC-DPOP)，聚类近似连续DPOP(Clustered AC-DPOP)和连续DSA(Continuous DSA)被同时提出解决函数形式的限制。EC-DPOP，AC-DPOP和CAC-DPOP能够获得高质量的解，但计算开销和内存需求巨大；C-DSA逻辑简单，计算开销小，但解的质量不佳。基于C-DCOP的粒子群优化算法(Particle SwarmOptimization based C-DCOP,PFD)被提出以减少计算开销和内存需求。PFD引入种群思想，通过种群寻优的方式找到近似解，然而搜索能力差和容易陷入局部最优的问题限制了解质量的提升。连续协同约束近似(Continuous Cooperative Constraint Approximation,C-CoCoA)是一种非迭代算法，不具备anytime属性，虽然能够以极快的计算速度和极小的计算开销求解C-DCOP，但由于C-CoCoA中的半贪婪的局部搜索策略，使得其在复杂的大规模问题上的求解质量不佳。

发明内容

针对以上存在的问题，本发明提供如下技术方案：一种基于遗传算法的自适应多点交叉遗传算法(Adaptive Multi-point Crossover Genetic Algorithm based C-DCOP,AMCGA)用于解决目前C-DCOP求解算法的缺点与局限，包括如下步骤：

一个C-DCOP可以由一个五元组定义，其中:

A＝{a

X＝{x

D＝{D

F＝{f

α:X→A是一个映射函数，表示将每个变量x

一个C-DCOP的解为一个赋值集合X

图1表示一个C-DCOP的例子，图1(a)表示4个变量的约束图，每个变量由相应的一个智能体控制，每条边代表一个图1(b)中所定义的约束代价函数。变量X

分布式种群是基于种群的C-DCOP求解算法中常用的一种方法，每个智能体持有所有个体一个维度的变量，所有智能体协同持有一个分布式种群，一个个体代表一个解。图2表示一个K个染色体，n个智能体的分布式种群，使用C

BFS伪树是DCOP和C-DCOP中常用的一种通信结构，其特点为多个分支并行计算，通信路径和通信时间短。

图3(a)表示以图1为例的一个BFS伪树，图3(b)表示BFS伪树的有序排列。BFS伪树用于智能体之间的通信，有序排列代表消息传递的顺序，深度较小的智能体相比于深度较大的智能体有着更高的优先级，使用H

AMCGA是一种基于种群的C-DCOP求解算法，种群中的个体被称为染色体，染色体的一个维度称为一个基因。AMCGA包括五个阶段：初始化、评估、选择、交叉和变异阶段。在初始化阶段，AMCGA初始化种群和参数；智能体在评估阶段协同计算染色体的适应度；选择阶段通过贪婪策略选择精英染色体；在交叉阶段，智能体执行多点交叉算子；在变异阶段，智能体执行变异算子并保留精英染色体。

初始化阶段：AMCGA首先构造有序的BFS伪树。

评估阶段：当接收到高优先级邻居的赋值后，智能体依次计算与每个高优先级邻居的每条染色体的部分适应度并发送给相应的高优先级邻居。除了叶智能体，每个智能体将从低优先级邻居接收的部分适应度求和，若该智能体不为根智能体，则将求和之后的部分适应度沿着BFS伪树发送给一个高优先级邻居。

选择阶段：由于每个智能体都会将部分适应度发送给高优先级邻居，因此染色体的所有部分适应度都将传递到根智能体。根智能体首先对染色体的适应度排序并选择适应度靠前的G条染色体；然后对每一条染色体进行判断，若[0,1]之间的随机数r

交叉阶段：当收到高优先级邻居传递的information后，智能体首先复制交叉染色体和非交叉染色体作为父代；若智能体被标记为交叉点，则使用交叉染色体执行交叉算子。

变异阶段：在交叉完成之后，子代染色体与非交叉染色体合并，通过公式(4)计算变异概率并对每一条染色体执行变异算子。

附图说明

图1表示一个C-DCOP的例子，图1(a)表示4个变量的约束图，每个变量由相应的一个智能体控制，每条边代表一个图1(b)中所定义的约束代价函数。

分布式种群是基于种群的C-DCOP求解算法中常用的一种方法，每个智能体持有所有个体一个维度的变量，所有智能体协同持有一个分布式种群，一个个体代表一个解。图2表示一个K个染色体，n个智能体的分布式种群，使用C

BFS伪树是DCOP和C-DCOP中常用的一种通信结构，其特点为多个分支并行计算，通信路径和通信时间短。图3(a)表示以图1为例的一个BFS伪树，图3(b)表示BFS伪树的有序排列。BFS伪树用于智能体之间的通信，有序排列代表消息传递的顺序，深度较小的智能体相比于深度较大的智能体有着更高的优先级，使用H

图4为智能体a

图5为AMCGA在不同交叉点数量下的收敛曲线。

图6为AMCGA在不同交叉概率下的收敛曲线。

图7为AMCGA在不同变异概率下的收敛曲线。

图8为AMCGA与竞争算法在稀疏随机图上的求解质量。

图9为AMCGA与竞争算法在稠密随机图上的求解质量。

图10为AMCGA与竞争算法在无尺度网络上的求解质量。

图11为AMCGA与竞争算法在随机树上的求解质量。

图12为AMCGA与竞争算法在小世界网络上的求解质量。

图13为AMCGA与竞争算法在稠密随机图上的收敛曲线。

具体实施方式

下面通过具体实施方式对本发明作进一步详细说明。在以下的实施方式中，很多细节描述是为了使得本申请能被更好的理解。然而，本领域研究人员可以毫不费力的认识到，其中部分特征是可以省略的，本申请相关的一些操作并没有在说明书中显示或者描述，这是为了避免本申请的核心部分被过多的描述所淹没，而对于本领域研究人员而言，详细描述这些相关操作并不是必要的，他们根据说明书中的描述以及本领域的一般知识即可完整了解相关流程。

发明主要包括三方面的内容：1.提出一种基于遗传算法的连续型分布式约束优化问题求解方法；2.设计自适应多点交叉遗传算法；3.引入交叉算子。

初始化阶段：AMCGA首先构造有序的BFS伪树；然后初始化参数：K：染色体的数量，G：精英个体的数量，P

以图1和图3为例，假设染色体的数量为4，分布式种群可表示为C＝{C

C

C

C

C

智能体a

评估阶段：每条染色体的适应度通过公式(2)计算，其中C

C.fitness(x

C.fitness(x

C.fitness(x

C.fitness(x

选择阶段：Iter

交叉阶段：执行交叉算子具体来说，智能体将自身持有染色体一个维度的基因前后互换位置在之前的例子中，C

C

C

变异阶段：变异算子具体来说，在[0,1]之间的随机数r

C

C

因此，新种群的完整赋值为：

C

C

C

C

以上应用了具体个例对本发明进行阐述，只是用于帮助理解本发明，并不用以限制本发明。对于本发明所属领域的研究人员，依据本发明的思想还可以做出若干简单推演、变形或替换。