CN106056208A - 面向生物地理学优化算法的约束处理方法和装置 - Google Patents

Abstract

本发明提供了一种面向生物地理学优化算法的约束处理方法和装置，其中方法包括：改进迁徙步骤：捕获从目标种群选取的个体；提取所述选取个体的目标维度元素；基于个体迁出率，依据模拟二进制交叉算子对选取个体的目标维度元素进行加权融合，产生新的待迁入元素；改进变异步骤：根据该新的待迁入元素更新目标的子种群并利用高斯分布进行扰动，以获得目标种群中的优秀者；可行性约束处理步骤：确定所述目标种群中的优秀者及确定最优个体，以微分进化算法更新变异参数。通过结合微分进化算法的信息搜索能力和生物地理学算法的信息利用能力，提升并平衡了该处理方案的全局优化能力。

Description

面向生物地理学优化算法的约束处理方法和装置

技术领域

本发明涉及生物地理学优化算法领域，更具体的说，涉及一种面向生物地理学优化算法的约束处理方法和装置。

背景技术

生物地理学优化算法是由Simon于2008年基于生物地理学数学模型提出的一种新型群体智能算法，该算法模拟生物种群在不同栖息地间的迁徙机制，来实现种群信息的共享，并模拟栖息地的突发现象来探索新的区域，从而达到寻优的目的。生物地理学算法结构简单，控制参数少，收敛速度快，具有出色的信息利用能力，已经在工程的不同领域获得应用。

然而，生物地理学优化算法通过迁徙操作最大程度地利用种群中已有信息，牺牲了对新区域的探索；其采用随机变异操作虽然能获得新的元素，探索未知空间，增加种群多样性，但探索力度不够强。

从而，生物地理学优化算法的信息探索能力和信息利用能力不平衡。因此生物地理学算法容易陷入局部最优解，发生早熟。

发明内容

本发明公开了一种面向生物地理学优化算法的约束处理方法和系统，通过结合微分进化算法的信息搜索能力和生物地理学算法的信息利用能力，提升并平衡了该处理方案的全局优化能力。，并将生物地理学算法引入约束优化领域。

为达到上述目的，本发明披露了：

一种面向生物地理学优化算法的约束处理方法，

改进迁徙步骤：

捕获从目标种群选取的个体；

提取所述选取个体的目标维度元素；

基于个体迁出率，依据模拟二进制交叉算子对选取个体的目标维度元素进行加权融合，产生新的待迁入元素；

改进变异步骤：根据该新的待迁入元素更新目标的子种群并利用高斯分布进行扰动，以获得目标种群中的优秀者；

可行性约束处理步骤：确定所述目标种群中的优秀者及确定最优个体，以微分进化算法更新变异参数。

优选地，所述捕获从目标种群选取的个体包括：

依据轮盘赌机制从种群X中随机选择两个互不相同的个体。

优选地，在所述改进迁徙步骤前还包括：

对当前迭代次数判断，当确定小于设定值，则执行可行性约束处理，其包括：

对目标种群按照优秀者在前地依据个体序号排序，并完成个体适应度值到物种数量的映射；

计算目标种群中各个个体的迁入率及迁出率以更新存在概率，并计算所述变异参数。

优选地，对当前迭代次数判断，当确定大于所述设定值时，输出种群X中最优个体及相应适应度值和约束违反度值。

优选地，改进变异步骤包括：

对目标种群中符合第一变异条件的个体进行修正，计算新个体的适应度值和总约束违反度值，优秀者存入第一种群；对目标种群中符合第二变异条件的个体，进行基于目标种群、子种群、第一种群的个体比较，优秀者存入目标种群。。

本发明还对应披露了：

一种面向生物地理学优化算法的约束处理装置，

改进迁徙模块，其配置为：

捕获从目标种群选取的个体；

提取所述选取个体的目标维度元素；

基于个体迁出率，依据模拟二进制交叉算子对选取个体的目标维度元素进行加权融合，产生新的待迁入元素；

改进变异模块，其配置为根据该新的待迁入元素更新目标的子种群并利用高斯分布进行扰动，以获得目标种群中的优秀者；

可行性约束处理模块，其配置为确定所述目标种群中的优秀者及确定最优个体，以微分进化算法更新变异参数。

优选地，该装置还包括判断模块，其配置为：

对当前迭代次数判断，当确定小于设定值，则执行可行性约束处理，其包括：

对目标种群按照优秀者在前地依据个体序号排序，并完成个体适应度值到物种数量的映射；

计算目标种群中各个个体的迁入率及迁出率以更新存在概率，并计算所述变异参数。

优选地，该判断模块还实现：

对当前迭代次数判断，当确定大于所述设定值时，输出种群X中最优个体及相应适应度值和约束违反度值。

优选地，所述改进变异模块配置为：

对目标种群中符合第一变异条件的个体进行修正，计算新个体的适应度值和总约束违反度值，优秀者存入第一种群；对目标种群中符合第二变异条件的个体，进行基于目标种群、子种群、第一种群的个体比较，优秀者存入目标种群。

通过本发明的面向生物地理学优化算法的约束处理方法和装置，引入模拟二进制交叉算子、高斯分布、自适应微分进化算法和基于可行性的约束处理机制，提升并且平衡生物地理学算法的信息搜索能力和信息利用能力，从而实现约束优化问题的求解。改进算法的迁徙算子依据模拟二进制交叉算子，从种群中随机选取两个个体，并按照预设加权系数对两个体进行结合，从而获得新的特征元素；改进变异元素基于高斯分布对变异个体进行扰动来产生新的个体。另外，在改进算法中，部分较差个体除按照生物地理学算法进化外，也依据两种微分进化的变异元素进行更新，以提升算法的全局优化能力和加快收敛速度。面向生物地理学优化算法的约束处理方法的不同个体相互比较时遵循可行性约束处理机制，通过结合微分进化算法的信息搜索能力和生物地理学算法的信息利用能力，提升并平衡了该处理方案的全局优化能力。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍。

图1为本发明实施例的面向生物地理学优化算法的约束处理方法流程图图。

图2为本发明另一实施例的面向生物地理学优化算法的约束处理方法流程图图。

图3为本发明另一实施例的面向生物地理学优化算法的约束处理方法流程图图。

图4为本发明实施例的面向生物地理学优化算法的约束处理装置结构示意图。

图5为本发明另一实施例的面向生物地理学优化算法的约束处理装置结构示意图。

具体实施方法

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。

本发明公开了一种面向生物地理学优化算法的约束处理方法和系统，通过结合微分进化算法的信息搜索能力和生物地理学算法的信息利用能力，提升并平衡了该处理方案的全局优化能力。

为了能够实现实施例中的方案，需要实行如下的构建和初始化处理：

步骤1：设定参数：迁入率最大值I＝1，迁出率最大值E＝1，变异率最大值mmax＝1，分布参数η＝10，微分进化算法变异参数变动范围的上边界FL＝0.7和下边界FU＝0.9，种群规模NP，优化变量的上边界Ubound，优化变量的下边界Lbound，预设最大迭代次数Gmax，不等式约束的违反容忍度δ；定义优化问题的适应度值Fitness和总约束违反度函数Constraint。

步骤2：初始化迭代次数G＝1，目标种群X、栖息地存在概率P和变异参数向量F，矩阵X的每一行表示一个个体，向量P的每一维元素都代表相应维度个体的存在概率，F的每一维元素对应种群X中相应个体的微分进化变异参数，用以计算种群X中每一个栖息地的适应度值和总约束违反度值，基于可行性约束处理机制，可确定种群中的最优个体。

图1为本发明实施例的面向生物地理学优化算法的约束处理方法，包括：

S101：改进迁徙步骤：

参见图2，该步骤具体实现为：

S201：捕获从目标种群选取的个体；

作为优选，所述捕获从目标种群选取的个体包括：

依据轮盘赌机制从种群X中随机选择两个互不相同的个体。

S202：提取所述选取个体的目标维度元素；

S203：基于个体迁出率，依据模拟二进制交叉算子对选取个体的目标维度元素进行加权融合，产生新的待迁入元素；

将遗传算法的模拟二进制交叉算子引入，改进基本迁徙操作，模拟二进制交叉算子的更新机制如下：

$C_{2j}=\frac{1}{2}\[(1+{\mathrm{\β}}_j){\mathrm{Parent}}_{1j}+(1-{\mathrm{\β}}_j){\mathrm{Parent}}_{2j}\]$

其中Parent1j和Parent2j表示从种群X中随机选出的两个个体的第j维元素，C1j和C2j表示交叉后所得的新元素，β按如下公式计算：

$\mathrm{\β}\left(u\right)=\left\{\begin{array}{cc}{\left(2u\right)}^{\frac{1}{\mathrm{\η}+1}}& \begin{array}{cc}if& u\≤0.5\end{array}\\ \frac{1}{{\[2(1-u)\]}^{\frac{1}{\mathrm{\η}+1}}}& \begin{array}{cc}if& u>0.5\end{array}\end{array}\right.$

在改进迁徙操作中，对每一维需要执行迁徙操作的元素，基于个体迁出率，依据轮盘赌机制从种群X中随机选择两个互不相同的个体，依据模拟二进制交叉算子对不同优秀个体的元素进行加权融合，产生两个新的待迁入元素。新元素继承优秀个体，同时也对优化空间的新区域进行了探索，从而提升了算法的信息探索能力。

其中η表示模拟二进制交叉算子的分布参数，u表示0和1之间的随机数。

S102：改进变异步骤：根据该新的待迁入元素更新目标的子种群并利用高斯分布进行扰动，以获得目标种群中的优秀者；

对种群中越出优化范围的个体进行修正，计算种群所有个体的适应度值和总约束违反度值。

引入高斯分布对变异元素进行了改进，高斯分布的概率密度函数如下： $f_{\mathrm{\μ},{\mathrm{\σ}}^2}\left(x\right)=\frac{1}{\mathrm{\σ}\sqrt{2\mathrm{\π}}}{e}^{\frac{(x-\mathrm{\μ})}{2{\mathrm{\σ}}^2}}$

其中μ表示概率分布的平均值，σ表示表示概率分布的方差。若元素Xij需执行变异操作，则改进变异操作如下：

X′_ij＝X_ij+N(0，1)

其中N(0，1)表示均值为1，方差为0的高斯分布，X′_ij表示X_ij执行改进变异操作后所获得的新元素。改进变异的元素抛弃了盲目随机的变异方式，对于需执行变异操作的元素，基于高斯分布对其进行扰动，实现对原有个体周边区域的探索，有较大的可能性获得优秀解，从而使算法能够以更大的可能性快速脱离局部最优解，进一步提升并平衡了该处理方案的全局优化能力。

S103：可行性约束处理步骤：确定所述目标种群中的优秀者及确定最优个体，以微分进化算法更新变异参数。

引入可行性约束处理机制，使得算法能够处理优化问题中约束条件，以最小值优化为例，机制的具体原理如下：可行个体优于不可行个体；当两个不可行个体相互比较时，总约束违反度小的个体优秀；当两个可行个体相互比较时，适应度值小的个体优秀。

作为优选，该改进变异步骤包括：

对目标种群中符合第一变异条件的个体进行修正，计算新个体的适应度值和总约束违反度值，优秀者存入第一种群；

作为优选，可实施如下技术方案以完成上述步骤，但并不局限于此。

种群X中序号在区间[0.7*NP+1，NP]内的每一个个体均按照微分进化的rand/1和rand to best/1两种变异方式进化，获得两个新个体，对超出优化范围的个体进行修正后，计算新个体的适应度值和总约束违反度值，优秀者存入种群DEX。

对目标种群中符合第二变异条件的个体，进行基于目标种群、子种群、第一种群的个体比较，优秀者存入目标种群：

对于种群X中序号在区间[1，0.7*NP]内的个体，将X中的个体与NewX1和NewX2中的对应个体进行比较，优秀者存入种群X；对于种群X中序号在区间[0.7*NP+1，NP]内的个体，将种群X、NewX1、NewX2、DEX中的个体相互比较，优秀者存入种群X。

更新微分进化变异参数F，更新机制如下：

$F_i^{G+1}=\left\{\begin{array}{cc}{\mathrm{FL}}_i+{\mathrm{rand}}_1\&CenterDot;({\mathrm{FU}}_i-{\mathrm{FL}}_i)& \begin{array}{cc}if& rand<0.3\end{array}\\ F_i^G& otherwise\end{array}\right.$

其中和分别表示第G次迭代和第G+1次迭代中种群X中第i个体的微分进化变异参数，FUi和FLi表示变异参数Fi变化范围的上边界和下边界，rand和rand1表示0和1之间的随机数；G＝G+1。

微分进化算法是一种经典的群体智能优化算法，通过不同个体之间的加权差值对其他个体进行扰动来搜索优化空间，具有出色的信息搜索能力，为将微分进化算法的信息搜索能力引入生物地理学算法，新型混合生物地理学算法采用如下混合机制：种群中较差30％个体除按照改进迁徙操作和变异操作进化外，还依据微分进化算法的rand/1和randto best/1两种变异方式进行更新。基于这种方式，种群中较差个体能够快速向优秀个体进化，对优化空间进行更为有效地探索，从而将微分进化算法的信息搜索能力与生物地理学算法的信息利用能力合理结合，提升并平衡了该处理方案的全局优化能力。

参见图3，在实施例一基础上，

在所述改进迁徙步骤S101前还包括：

S301：对当前迭代次数判断，当确定小于设定值，则执行可行性约束处理，其包括：

S302：对目标种群按照优秀者在前地依据个体序号排序，并完成个体适应度值到物种数量的映射；

303：计算目标种群中各个个体的迁入率及迁出率以更新存在概率，并计算所述变异参数。

而：

当确定大于所述设定值时，S304：

输出种群X中最优个体及相应适应度值和约束违反度值。

判断当前迭代次数G大于Gmax时，输出种群X中最优个体及相应适应度值和约束违反度值，不再执行其他步骤。

基于可行性约束处理机制，对种群X中的个体进行排序，优秀者在前，并依据种群个体序号，完成个体适应度值到物种数量的映射，映射方式如下：Xi表示按照可行性约束处理机制排序后种群X中第i个个体，其对应的物种数量Si＝NP-i+1。

计算目标种群中各个个体的迁入率λi，迁出率μi，更新存在概率P，计算变异率mi：

${\mathrm{\&lambda;}}_i=I(1-\frac{S_i}{NP})$

${\mathrm{\&mu;}}_i=E{\left(\frac{S_i}{NP}\right)}^2$

${\stackrel{\&CenterDot;}{P}}_i=\left\{\begin{array}{cc}-({\mathrm{\&lambda;}}_i+{\mathrm{\&mu;}}_i)P_i+{\mathrm{\&mu;}}_{i-1}{P}_{i-1}& S_i=0\\ -({\mathrm{\&lambda;}}_i+{\mathrm{\&mu;}}_i)P_i+{\mathrm{\&lambda;}}_{i+1}{P}_{i+1}+{\mathrm{\&mu;}}_{i-1}{P}_{i-1}& 0<S_i<NP\\ -({\mathrm{\&lambda;}}_i+{\mathrm{\&mu;}}_i)P_i+{\mathrm{\&lambda;}}_{i+1}{P}_{i+1}& S_i=NP\end{array}\right.$

$m_i=m_{max}(1-\frac{P_i}{P_{\max }})$

其中Pi表示个体Xi的存在概率，Pmax＝max(Pi)。

以上实施例中的面向生物地理学优化算法的约束处理算法，基于模拟二进制交叉算子对迁徙算子改进，将高斯分布引入变异操作，种群中较差个体依据微分进化变异算子进化，以上改进方案平衡了生物地理学算法的信息探索能力和信息利用能力。

引入可行约束处理机制，使该算法能够处理约束优化，为将生物地理学算法向约束优化领域推广提供了一种途径，从而能够以更大的可能性和更快的速度收敛至全局最优解。

本发明的实施例还公开了：一种面向生物地理学优化算法的约束处理装置，包括：

改进迁徙模块401，其配置为：

捕获从目标种群选取的个体；

提取所述选取个体的目标维度元素；

基于个体迁出率，依据模拟二进制交叉算子对选取个体的目标维度元素进行加权融合，产生新的待迁入元素；

改进变异模块402，其配置为根据该新的待迁入元素更新目标的子种群并利用高斯分布进行扰动，以获得目标种群中的优秀者；

可行性约束处理模块403，其配置为确定所述目标种群中的优秀者及确定最优个体，以微分进化算法更新变异参数。

优选地，所述改进变异模块配置为：

对目标种群中符合第一变异条件的个体进行修正，计算新个体的适应度值和总约束违反度值，优秀者存入第一种群；

对目标种群中符合第二变异条件的个体，进行基于目标种群、子种群、第一种群的个体比较，优秀者存入目标种群。。

参见图5，其还包括判断模块501，其配置为：

对当前迭代次数判断，当确定小于设定值，则执行可行性约束处理，其包括：

对目标种群按照优秀者在前地依据个体序号排序，并完成个体适应度值到物种数量的映射；

计算目标种群中各个个体的迁入率及迁出率以更新存在概率，并计算所述变异参数。

该判断模块还实现：

对当前迭代次数判断，当确定大于所述设定值时，输出种群X中最优个体及相应适应度值和约束违反度值。

改进变异模块配置为

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

综上所述：

通过本发明的面向生物地理学优化算法的约束处理方法和装置，引入模拟二进制交叉算子、高斯分布、自适应微分进化算法和基于可行性的约束处理机制，提升并且平衡生物地理学算法的信息搜索能力和信息利用能力，从而实现约束优化问题的求解。改进算法的迁徙算子依据模拟二进制交叉算子，从种群中随机选取两个个体，并按照预设加权系数对两个体进行结合，从而获得新的特征元素；改进变异元素基于高斯分布对变异个体进行扰动来产生新的个体。另外，在改进算法中，部分较差个体除按照生物地理学算法进化外，也依据两种微分进化的变异元素进行更新，以提升算法的全局优化能力和加快收敛速度。面向生物地理学优化算法的约束处理方法的不同个体相互比较时遵循可行性约束处理机制，通过结合微分进化算法的信息搜索能力和生物地理学算法的信息利用能力，提升并平衡了该处理方案的全局优化能力。

对于系统实施例而言，由于其基本相应于方法实施例，所以描述得比较简单，相关之处参见方法实施例的部分说明即可。以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(Read-OnlyMemory，ROM)或随机存储记忆体(Random AccessMemory，RAM)等。

对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明实施例的精神或范围的情况下，在其它实施例中实现。因此，本发明实施例将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。

Claims (9)

1.一种面向生物地理学优化算法的约束处理方法，其特征在于：

改进迁徙步骤：

捕获从目标种群选取的个体；

提取所述选取个体的目标维度元素；

基于个体迁出率，依据模拟二进制交叉算子对选取个体的目标维度元素进行加权融合，产生新的待迁入元素；

改进变异步骤：根据该新的待迁入元素更新目标的子种群并利用高斯分布进行扰动，以获得目标种群中的优秀者；

可行性约束处理步骤：确定所述目标种群中的优秀者及确定最优个体，以微分进化算法更新变异参数。

2.根据权利要求1所述的面向生物地理学优化算法的约束处理方法，其特征在于，所述捕获从目标种群选取的个体包括：

依据轮盘赌机制从种群X中随机选择两个互不相同的个体。

3.根据权利要求1所述的面向生物地理学优化算法的约束处理方法，其特征在于，在所述改进迁徙步骤前还包括：

对当前迭代次数判断，当确定小于设定值，则执行可行性约束处理，其包括：

对目标种群按照优秀者在前地依据个体序号排序，并完成个体适应度值到物种数量的映射；

计算目标种群中各个个体的迁入率及迁出率以更新存在概率，并计算所述变异参数。

4.根据权利要求3所述的面向生物地理学优化算法的约束处理方法，其特征在于，对当前迭代次数判断，当确定大于所述设定值时，输出种群X中最优个体及相应适应度值和约束违反度值。

5.根据权利要求3所述的面向生物地理学优化算法的约束处理方法，其特征在于，改进变异步骤包括：

对目标种群中符合第一变异条件的个体进行修正，计算新个体的适应度值和总约束违反度值，优秀者存入第一种群；

对目标种群中符合第二变异条件的个体，进行基于目标种群、子种群、第一种群的个体比较，优秀者存入目标种群。

6.一种面向生物地理学优化算法的约束处理装置，其特征在于，

改进迁徙模块，其配置为：

捕获从目标种群选取的个体；

提取所述选取个体的目标维度元素；

基于个体迁出率，依据模拟二进制交叉算子对选取个体的目标维度元素进行加权融合，产生新的待迁入元素；

改进变异模块，其配置为根据该新的待迁入元素更新目标的子种群并利用高斯分布进行扰动，以获得目标种群中的优秀者；

可行性约束处理模块，其配置为确定所述目标种群中的优秀者及确定最优个体，以微分进化算法更新变异参数。

7.根据权利要求6所述的面向生物地理学优化算法的约束处理系统，其特征在于，还包括判断模块，其配置为：

对当前迭代次数判断，当确定小于设定值，则执行可行性约束处理，其包括：

对目标种群按照优秀者在前地依据个体序号排序，并完成个体适应度值到物种数量的映射；

计算目标种群中各个个体的迁入率及迁出率以更新存在概率，并计算所述变异参数。

8.根据权利要求7所述的面向生物地理学优化算法的约束处理系统，其特征在于，该判断模块还实现：

对当前迭代次数判断，当确定大于所述设定值时，输出种群X中最优个体及相应适应度值和约束违反度值。

9.根据权利要求7所述的面向生物地理学优化算法的约束处理系统，所述改进变异模块配置为：

对目标种群中符合第一变异条件的个体进行修正，计算新个体的适应度值和总约束违反度值，优秀者存入第一种群；

对目标种群中符合第二变异条件的个体，进行基于目标种群、子种群、第一种群的个体比较，优秀者存入目标种群。