一种基于对偶搜索的双种群协同进化方法及应用

技术领域

本发明涉及多目标演化计算领域，尤其是涉及一种基于对偶搜索的双种群协同进化方法。

背景技术

传统的多目标进化算法，如NSGAII、MOEA/D和IBEA，在求解低维多目标优化问题时通常能够表现出很好的性能，但随着目标变量维数的增加：一方面，决策空间呈指数增长，算法的计算复杂度急剧增加；另一方面，不同目标间优化冲突加剧，收敛性和多样性难以平衡，算法的优化效果显著下降。如何针对高维多目标优化问题(Many-objectiveOptimization Problems,MaOPs)进行快速、高效求解，是当前多目标进化算法领域的研究难点。近年来，学术及工业界先后提出了基于Pareto支配、基于分解和基于指标等多种多目标进化算法框架对MaOPs进行优化研究，但仍存在着许多亟待解决的问题，主要表现在以下几个方面：

(1)搜索能力不足

现有多目标进化算法研究中，新个体的产生一般独立于待优化问题，计算资源被均匀分配到染色体的每个基因上，并试图在每次迭代进化过程中维持种群覆盖整个帕累托前沿(Pareto Front,PF)。但随着目标变量维数的增加，搜索空间呈指数增长，导致具体分配到每个PF子部分的计算资源严重匮乏。

(2)收敛性与多样性冲突难以平衡

为了平衡种群收敛性和多样性冲突，现有研究的普遍做法是在一次种群迭代优化过程中同时保持种群的收敛性和多样性。然而，M维目标空间中非支配空间的比例高达(2M-2)/2M，随着目标空间维数的增加，种群中几乎所有的个体都是互不支配，“一次迭代同时优化”的环境选择机制无法产生足够的选择压力去促进种群多样化。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种基于对偶搜索的双种群协同进化方法及应用。

本发明的目的可以通过以下技术方案来实现：

根据本发明的一个方面，提供了一种基于对偶搜索的双种群协同进化方法，该方法维持了两个对偶互补和协同进化的种群，分别为：分别拥有独立互补的进化范式的面向收敛性优化种群CP和面向多样性优化种群DP；

其中CP采用面向收敛性进化方向的交叉和突变算子进行种群繁殖，并结合收敛性优先环境选择机制来维持种群的收敛性；DP采用面向多样性进化方向的交叉和突变算子进行种群繁殖，并结合多样性优先环境选择机制来维持种群多样性；

所述CP和DP通过限制交配选择、信息共享和信息补偿三种协同交互机制来实现进化信息的互补。

作为优选的技术方案，该方法具体包括以下步骤：

步骤1，随机初始化种群CP和DP；

步骤2，基于控制变量分析技术，将决策变量划分为收敛性变量和多样性变量；

步骤3，基于链接学习技术，将收敛性变量划分为互不依赖的收敛性变量分组；

步骤4，在CP交配选择过程中，限制交配选择策略RMS基于收敛性交配选择策略从CP中选取个体P

步骤5，在DP交配选择过程中，限制交配选择策略RMS基于多样性交配选择策略从DP中选取个体P

步骤6，在CP繁殖过程中，基于收敛性变量分组对个体进行交叉和突变操作；

步骤7，在DP繁殖过程中，基于多样性变量分组对个体进行交叉和突变操作；

步骤8，CP和DP在环境选择过程中执行如下步骤：

S1、对CP和DP后代解进行共享，从而使得新产生的种群能够继承两个父代种群的优势；

S2、CP采用收敛性环境选择机制，引导种群向理想点Z

S3、DP采用多样性环境选择机制，引导种群向最低点Z

步骤9，对CP和DP每次迭代后的新种群采用主从范式或交叉范式进行信息补偿。

作为优选的技术方案，所述限制交配选择策略RMS用于两个种群中父代解的选取。

作为优选的技术方案，所述限制交配选择策略RMS用于两个种群中父代解的选取具体为；在CP进化过程中，RMS基于收敛性交配选择策略从CP中选取个体P

作为优选的技术方案，所述CP和DP在环境选择阶段对各自后代解进行共享，从而使得新产生的种群能够继承两个父代种群的优势。

作为优选的技术方案，所述CP和DP每次迭代后的新种群进行信息补偿，具体包含两种信息补偿范式：一种是主从范式，新产生的两个种群具有主从关系，从种群负责对主种群进行信息补偿，算法的最终输出结果由主种群产生；一种是交叉范式，两个种群基于各自优势进行相互间的信息补偿，算法的最终输出结果由CP和DP共同产生。

作为优选的技术方案，所述将决策变量划分为收敛性变量和多样性变量具体步骤如下：

201)控制变量分析：通过控制变量和随机扰动技术将决策变量划分为收敛性变量和发散性变量；

202)依赖关系分析：基于链接学习技术将收敛性变量划分为互不依赖的独立分组；

203)收敛性交叉算子以互不依赖的收敛性变量分组为单位进行交叉操作；多样性交叉算子以所有发散性变量为单位进行交叉操作；

204)收敛性突变算子在收敛性变量中选择变量进行突变；多样性突变算子在发散性变量中选择变量进行突变。

作为优选的技术方案，分别基于PBI和IPBI中的理想点Z

作为优选的技术方案，所述演化具体过程如下：

801)CP以理想点Z

802)DP以最低点Z

803)若CP和DP之间采用交叉范式进行信息补偿：

S1、将CP和DP的后代解合并；

S2、基于综合性能评价指标(如Hyper-volume，IGD等)对种群进行筛选，将最终保留的个体作为CP和DP下一轮迭代的父代解；

804)若CP和DP之间采用主从范式进行信息补偿：

S1、DP(从种群)将每次搜索到的解合并到CP(主种群)中；

S2、CP基于Pareto支配关系进行解集筛选，算法最终的输出结果由CP产生。

根据本发明的另一个方面，提供了一种采用所述基于对偶搜索的双种群协同进化方法的应用，该方法应用至大规模数据中心的资源调度和整合优化问题，以实现能耗、资源损耗、数据通信流量、任务完成时延的多个冲突目标的优化。

与现有技术相比，本发明具有以下优点：

1)本发明不同于现有多目标进化算法将计算资源均匀分配到染色体的每个基因上，本发明提出的对偶进化机制，通过对收敛性变量或多样性变量执行有目的性的交配、交叉和突变操作，引导种群向对偶方向演化，从而避免将计算资源浪费在不必要的搜索区域；

2)本发明不同于现有多目标进化算法在一次种群迭代优化过程中同时保持种群的收敛性和多样性，本发明提出了一种双种群协同进化范式，通过种群内互补演化和种群间协同交互实现收敛性和多样性的独立并行优化；

3)本发明双种群对偶搜索的演化过程可以利用对偶中心点的互补效应来处理具有凹或凸形状的PF问题；

4)本发明基于对偶搜索的双种群协同进化方法可应用至大规模数据中心的资源调度和整合优化问题，对数据中心能耗、资源损耗、数据通信流量、任务完成时延等多个冲突目标具有显著优化效果。

附图说明

图1为本发明的基于对偶搜索的双种群协同进化框架；

图2为本发明的双种群对偶演化示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明的一部分实施例，而不是全部实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都应属于本发明保护的范围。

本发明基于对偶搜索的双种群协同进化方法，该方法维持了两个协同进化的种群：面向收敛性优化种群(Convergence-oriented Population,CP)和面向多样性优化种群(Diversity-oriented Population,DP)。CP和DP分别拥有独立对偶的进化范式：

(1)CP采用面向收敛性进化方向的交叉和突变算子进行种群繁殖，并结合收敛性优先环境选择机制来维持种群的收敛性；

(2)DP采用面向多样性进化方向的交叉和突变算子进行种群繁殖，并结合多样性优先环境选择机制来维持种群多样性。

作为优选，上述的收敛性及多样性方向的交叉和突变算子可通过决策变量特性分析技术实现，具体步骤如下：

控制变量分析：通过控制变量和随机扰动技术将决策变量划分为收敛性变量和发散性变量；

依赖关系分析：基于链接学习技术将收敛性变量划分为互不依赖的独立分组；

收敛性交叉算子以互不依赖的收敛性变量分组为单位进行交叉操作；多样性交叉算子以所有发散性变量为单位进行交叉操作；

收敛性突变算子在收敛性变量中选择变量进行突变；多样性突变算子在发散性变量中选择变量进行突变。

上述的收敛性及多样性环境选择机制可分别基于PBI和IPBI中的理想点Z

CP和DP在对偶进化过程中采用以下三种协同交互机制来实现进化信息的共享和互补：

限制交配选择策略(RMS)。RMS用于两个种群中父代解的选取。具体地，在CP进化过程中，RMS基于收敛性交配选择策略从CP中选取个体P

信息共享机制。CP和DP在环境选择阶段对各自后代解进行共享，从而使得新产生的种群能够继承两个父代种群的优势；

信息补偿机制。针对决策变量分组造成的进化信息丢失问题，对CP和DP每次迭代后的新种群进行信息补偿。本发明包含两种信息补偿范式：一种是主从范式，新产生的两个种群具有主从关系，从种群负责对主种群进行信息补偿，算法的最终输出结果由主种群产生；一种是交叉范式，两个种群基于各自优势进行相互间的信息补偿，算法的最终输出结果由CP和DP共同产生。

上述收敛性交配选择策略基于轻量级收敛性评价指标(如I

上述多样性交配选择策略基于轻量级多样性评价指标(如SDE,Lp-norm等)作为评价个体优劣标准。

具体实施例

基于对偶搜索的双种群协同进化方法如图1所示，该方法中维持了两个协同进化的种群：面向收敛性优化种群(Convergence-oriented Population,CP)和面向多样性优化种群(Diversity-oriented Population,DP)。CP和DP分别拥有独立互补的进化范式，其中，CP采用面向收敛性进化方向的交叉和突变算子进行种群繁殖，并结合收敛性优先环境选择机制来维持种群的收敛性；DP采用面向多样性进化方向的交叉和突变算子进行种群繁殖，并结合多样性优先环境选择机制来维持种群多样性。CP和DP通过限制交配选择、信息共享和信息补偿三种协同交互机制来实现进化信息的互补。具体方法的演化步骤如下：

步骤1，随机初始化种群CP和DP；

步骤2，基于控制变量分析技术，将决策变量划分为收敛性变量和多样性变量；

步骤3，基于链接学习技术，将收敛性变量划分为互不依赖的收敛性变量分组；

步骤4，在CP交配选择过程中，限制交配选择策略RMS基于收敛性交配选择策略从CP中选取个体P

步骤5，在DP交配选择过程中，限制交配选择策略RMS基于多样性交配选择策略从DP中选取个体P

步骤6，在CP繁殖过程中，基于收敛性变量分组对个体进行交叉和突变操作；

步骤7，在DP繁殖过程中，基于多样性变量分组对个体进行交叉和突变操作；

步骤8，CP和DP在环境选择过程中执行如下步骤：

S1、对CP和DP后代解进行共享，从而使得新产生的种群能够继承两个父代种群的优势；

S2、CP采用收敛性环境选择机制，引导种群向理想点Z

S3、DP采用多样性环境选择机制，引导种群向最低点Z

步骤9，对CP和DP每次迭代后的新种群采用主从范式或交叉范式进行信息补偿。

图2为双种群对偶演化示意图，采用对偶搜索的好处是可以利用对偶中心点的互补效应来处理具有凹或凸形状的PF问题。对偶演化具体过程为：

CP以理想点Z

DP以最低点Z

若CP和DP之间采用交叉范式进行信息补偿：

S1、将CP和DP的后代解合并；

S2、基于综合性能评价指标(如Hyper-volume，IGD等)对种群进行筛选，将最终保留的个体作为CP和DP下一轮迭代的父代解；

若CP和DP之间采用主从范式进行信息补偿：

S1、DP(从种群)将每次搜索到的解合并到CP(主种群)中；

S2、CP基于Pareto支配关系进行解集筛选，算法最终的输出结果由CP产生。

本发明要解决的技术问题是如何缓解高维多目标优化问题所面临的种群收敛性和多样性难以均衡问题。采用的技术方案为：基于协同进化理论提出双种群协同进化计算框架，该框架通过利用决策变量的内在特性帮助和指导不同种群向对偶方向演化，进而结合种群间的限制交配选择、信息共享和信息补偿三种协同交互机制实现种群收敛性和多样性的并行独立优化。此外，该框架适配性强，采用的对偶搜索理念可以利用对偶中心点的互补效应来处理具有凹或凸形状的PF问题。

本发明一种典型的应用场景是大规模数据中心的资源调度和整合优化。具体应用过程为：首先，以能耗、资源损耗、数据通信流量、任务完成时延等指标作为问题优化目标，以服务器剩余可用计算容量为约束条件，建立大规模数据中心资源调度和整合问题的多目标约束优化模型；然后，以待调度的虚拟机数量为染色体长度，虚拟机编号为基因位置，实现种群个体的编码；最后，基于编码方式初始化CP和DP，并按照图1所示双种群协同进化过程进行种群间限制交配选择、信息共享和信息补偿，直到满足算法的终止条件，输出以能耗、资源损耗、数据通信流量、任务完成时延等多个冲突指标为优化目标的Pareto最优解集。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到各种等效的修改或替换，这些修改或替换都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求的保护范围为准。