十进制整数编码的DE算法模式集定理研究

王凯光,高岳林

(北方民族大学数学与信息科学学院,宁夏 银川750021)

1.引言和预备知识

差分进化算法(Differential Eveolution,简称DE[1−3])是由Storn和Price于1995年提出的为解决切比雪夫不等式(Chebyshev Inequality)的一种采用浮点矢量编码的在连续空间进行搜索的全局优化算法[4−6],是通过差分方式进行迭代搜索的全局性进化算法,具有简单、易实现、收敛性好、鲁棒性强等优点[7−13],但就算法寻优的本质上说,其大小如何影响种群多样性的分布,进而影响算法的收敛性质[11,13],在理论机制上面尚未得到说明.鉴于此,本文将在二进制模式定理[14−15]研究基础上,应用十进制编码对DE算法的动力学机制进行初步研究,探索种群规模(NP)、收缩因子(F)、交叉概率(CR) 等控制参数对种群寻优的动力学机制,并提出相应的编码规则以及基本概念,给出能够很好解释DE算法各类参数对种群寻优能力影响的十进制模式集定理.

ⅠDE算法原理

一般地,极小化优化问题如下表示:

其中,D为决策变量的维数,NP为种群规模,f(Xi)为适应度函数,Xi(i=1,2,··· ,NP) 为D维参量矢量,xij(i= 1,2,··· ,NP;j= 1,2,··· ,D)为第i个个体的第j个分量,aij,bij分别为寻优范围的下界和上界,差分进化算法(Differential Eveolution,DE)基本操作原理如下描述[1,4,7].

(i)初始化种群

设置DE算法的种群为X(t),则个体可表示为:

其中t为进化代数,NP为种群规模.

初始化种群:确定所求优化问题的维数D,最大进化代数T,种群规模NP,设置生成初值寻优向量如下所示:

(ii)变异操作

DE算法的个体变异成分是父代个体的差分矢量,每次差分变异个体均来源于第t代父代个体种群中的两个个体(Xti1,Xti2),其中i1,i2∈NP,则差分矢量定义为:Di1,2=Xti1−Xti2,那么对任意矢量个体Xti,定义变异操作为:

其中,i1,i2,i3∈{1,2,··· ,NP}且i1,i2,i3互不相同,种群规模NP≥4,F为收缩因子.在种群中随机选取不为零的相异矢量,通过差分操作得到变异个体,变异个体将实现调整种群多样性的可能.

(iii)交叉操作

对于种群目标矢量个体(xti),与变异个体进行交叉操作,产生试验个体Uit+1,为保持种群多样性,引入交叉概率CR和随机函数rand(0,1)对变异个体和目标矢量个体(xti)进行交叉选择,保证试验个体至少有一位由变异个体贡献,对于其他位点,通过交叉概率CR决定变异个体和目标矢量个体(xti)对试验个体中某些位点的贡献,交叉操作的试验方程如下:

式(1.7)中randj[0,1],CR∈(0,1)为交叉概率,CR取值越大,表明矢量个体在不同位点发生交叉而产生新矢量个体的概率就越大;CR = 0时,表明没有发生任何交叉操作,有利于保持种群的多样性和全局群搜索能力;CR=1时,表明一定在某些位点发生交叉操作,有利于保持全局搜索和加快收敛速度.CR=0或1是发生交叉操作的两种极端情况,j=jrand为随机选择的位点,这是为了试验个体Uti要从变异个体V ti至少获得一个发生基因变异的位点,确保变异个体目标矢量个体(xti)、试验个体三者矢量个体之间互不相同,表明交叉操作引起种群间的交叉是有效交叉.

(iv)选择操作

DE算法的选择操作是一种基于贪婪算法的选择机制,经过变异和选择操作之后生成的试验个体与目标矢量个体(xti)进行竞争和选择,若当Uit+1的适应度值好于Xit的适应度值,那么作为最优个体会被种群继承到下一代,否则保留到下一代的个体将是(xti),选择算子在种群中的选择作用由下述方程进行描述:

Ⅱ二进制编码模式定理

引理1.1[14−15](模式定理,Schema Theorem) 在遗传算子选择、交叉、变异作用下,那些低阶、短定义距、高适应度的模式的生存数量,将随着迭代次数的增加而以指数级增长.

2.十进制编码DE算法的模式集定理

对于十进制整数编码的DE算法,采用V={0,1,2,3,4,5,6,7,8,9}10个基本字符作为基本字符串(Essential Character String),字符串中不确定位点(也称为分配符)∗均在10个基本字符中取值,基本字符串中若含有不确定位点∗,则称为普通字符串(Ordinary Character String),显然基本字符串也属于普通字符串(简称字符串(Character String)),字符串中任意字符的位点用{di|i ∈Z+,di ∈V}来表示.

Ⅰ基本概念及定义

定义2.1(模式,Schema)H称之为一个模式,若存在形式={∗,0,1,2,3,4,5,6,7,8,9},其中∗的位点是任意的,并记作H=V,其中分配符∗∈{0,1,2,3,4,5,6,7,8,9}.例如,H=∗5∗7∗∗9就是一个模式,而H=0517119就是一个确定的模式表示形式.

定义2.2(模式集,Schema Sets)ℵ称之为一个模式集,若存在形式ℵ={Hi|i ∈Z+}.

定义2.3(模式集阶,Schema Sets Order) 包含在模式集ℵ中所有模式{Hi|i ∈Z+}的阶的总和,称为模式集ℵ的模式集阶,记作Θ(ℵ).若∀Hi ∈ℵ,O(Hi) =ki,则

例1现有一个模式集ℵ={Hi|i ∈{1,2,3}},其中,O(Hi) =ki,i ∈{1,2,3},那么,也即这个模式集ℵ的阶为说明此时该模式集ℵ中3个相异个体分别包含各自模式{Hi|i= 1,2,3}的阶ki,那么这三个模式{Hi|i= 1,2,3}的阶的总和为

注 由于一个种群规模为NP的种群,假设其中存在有限个模式的个体,相异模式个体所携带的表示其特征量的模式是相异的,采用{Hi|i ∈Z+}作为模式集阶的基本量是基于以下考虑:假设这里有两个相异模式的个体(此时模式和个体是相当的)H1、H2,O(H1)=k1,O(H2)=k2,即这两个模式个体所携带的染色体(确定字符串)上的不同位点上基因(确定字符)的个数分别为k1,k2,经过选择、交叉、变异后所得新个体中染色体(新确定字符)上的位点会增加或者说新的确定子字符个数会增加,按照遗传算法模式定理,新增加的确定字符个数将介于min{k1,k2}和ki之间,或者说新个体的多样性特征会增加与两父代个体不同的某些特征,鉴于种群进化的不确定性,采用{Hi|i ∈Z+}作为模式集阶的基本量,具有概率上的广义特征.

定义2.4(模式集串长,String Length of Schema Sets Order) 模式集ℵ中所有模式{Hi|i ∈Z+}包含的所有字符的数量为l,则称该模式集ℵ的串长为l,并记作L(ℵ)=l.

例2若ℵ={Hi|i= 1,2},L(H1) =l1,L(H2) =l2,则L(ℵ) =L(H1)+L(H2) =l1+l2,也即这个模式集ℵ的串长为L(ℵ) =L(H1)+L(H2) =l1+l2,说明此时该模式集ℵ中2个相异个体分别包含各自模式{Hi|i= 1,2,3}的串长li,那么两个模式{Hi|i= 1,2,3}的串长总和为L(ℵ)=l1+l2,模式集ℵ的串长对相异模式个体的变异强度有概率上被分割或替换的可能性,串长越长,这样的可能性就越大,反之越小.

定义2.5(模式集距,Schema Sets Order Range) 模式集ℵ中所有模式{Hi|i ∈Z+}进行降序或升序排列,模式{Hi|i ∈Z+}按次序排列的第一个模式的第一个位点上的确定字符(按次序方向)与按次序排列的最后一个模式的最后一个位点上的确定字符(按次序方向)的距离,称为模式集距,记作δ(ℵ).

例3现有模式集ℵ={Hi|i= 1,2},其中H1=∗2∗∗4,H2=∗2∗5∗,将该模式集的基本量按顺序排列,对于模式集的第一个基本量H1,按顺次序排列的第一个确定字符为2,其确定为点为第2位点,同样模式集的第二个基本量H2,按顺次序排列的最后一个确定字符为5,其确定位点为第9位点,那么该模式集ℵ距为δ(ℵ)=9−2=7,同模式集串长的概率意义类似,不同的是模式集距中若有位点被分割或替换,发生变异的可能性强于模式集串长.

定义2.6(平均适应度函数,Function of Average Fitness) 设X(t)={Xt1,Xt2··· ,XtNP}为第t代种群,Ev(Xti)为Xti的适应度,则称

为模式集ℵ的平均适应度函数.

其中,Ev(Xti)是种群规模为NP的种群中,任意个体(既包含同一模式的个体,也包含相异模式的个体,总之是所有种群个体)的平均适应度,f(ℵ,t) 是种群规模为NP的种群所包含的相异模式个体的平均适应度,二者具有检索个体数量上的不同,但其数学性质完全类似.

ⅡDE算法的模式集定理

文[16-18]介绍了标准的遗传算法的基本模式定理,Whitley教授[19−20]将二进制编码的字符串推广到任意进制字符串编码上,我们将在前人已有的研究基础上对DE算法的模式集定理进行探讨.我们知道,控制DE算法的各类参数主要有种群规模NP、收缩因子F、交叉概率CR.下面介绍十进制整数编码DE算法的模式集定理,它将从动力学角度较为详细地阐述DE算法的进化机理.

定理2.1设DE算法的交叉概率和收缩因子分别为CR和F,模式集ℵ的距为δ(ℵ),模式集ℵ的阶为Θ(ℵ),第t+1代种群X(t+1)中含有ℵ中元素个数的期望值记为E(ℵ∩X(t+1)),则有

其中,l为X(t)所包含模式集ℵ的串长.(t)=∑x∈ℵ∩X(t)Ev(Xti)/|X(t)|,|ℵ∩X(t)|为X(t)中含于模式集ℵ的元素个数.

证 (i) 选择操作对模式集ℵ的生存数量的影响

假设种群规模为X={X1,X2,··· ,XNP},给定相应进化代数t,模式集ℵ包含个数不大于种群规模为NP个相异的模式{Hi|i ∈NP},其适应度函数(或称之为种群演化初始时模式集的平均适应度函数)记为f(ℵ,t).按照进化算法演化次序,一个确定种群规模NP的种群,模式集ℵ中任一个体按照选择操作被选择的次数与其适应度函数成正比例关系,种群每演化一次,|ℵ∩X(t)|中相异模式的每一个体被选择的平均次数占种群规模中所有个体被选择的平均比例数量为:

其中,

为证明方便,假设种群规模为NP的种群X={X1,X2,··· ,XNP},NP个数量的个体所携带的模式{Hi|i ∈NP}两两相异,ℵ∩X(t) 中的个体数目|ℵ∩X(t)|经过N次选择,T为最大迭代次数,理论上期望在经过{t,t ≤T}次迭代后,模式集ℵ在这样的种群规模ℵ∩X(t)内元素被选择的次数的期望为:

上式(2.5)说明下一代种群中模式集ℵ的生存数量与模式集ℵ的适应度函数值成正比,与群体X(t)平均适应度函数值成反比.可以分为两种情况,一种是:当f(ℵ,t)>¯F(t)时,模式集ℵ的生存数量增加.另一种是:当f(ℵ,t)<¯F(t)时,模式集ℵ的生存数量衰减.由此可见,群体中任意模式集的生存数量都会在选择操作中呈现如此变化规律.

那么当群体从初始迭代值t= 0开始进行DE算法演化操作,假设λ这一常数不变,则上式(2.6)可改写为:

这表明,在选择操作作用下,模式集ℵ的生存数量是以指数形式进行演化的.分为两种情况,一种情况是:当λ >0时,模式集ℵ的生存数量以指数形式增加.另一种情况是:当λ <0时,模式集ℵ的生存数量以指数形式衰减.但这样的变化仅是描述了已有模式集ℵ的生存数量的变化,并未在原有基础上产生新的模式.

(ii) 交叉操作对模式集ℵ的生存数量的影响

由于选择操作不能检索新的种群区域,为此增加交叉操作.这里采用单点交叉(这并不影响定理的证明).由于单点交叉时随机选择1到l −1位点中某一位点作为交叉点,交换交叉位点之后的所有对应字符子串,当交叉操作作用在模式集ℵ所包含所有模式{Hi|i ∈NP}的定义距{li|i ∈NP}之内,模式集ℵ有被破坏的可能,应该明确注意到,即使交叉操作作用在模式的定义距内部,模式集同样存在不被破坏的可能.

由上式(2.8)可以看出,定义距δ(Hi)越大,模式被破坏的概率越大.一般地,对任意模式{Hi|i ∈NP}可以计算出经交叉操作后生存概率的下界为Psurvival,在单点操作作用下,任一长度为{li|i ∈NP}的模式的生存概率为那么,在交叉作用下模式集ℵ存活概率(ℵ存活估计值)为:

现考虑模式集ℵ在选择和交叉两种操作用下的生存数量有如下估计式:

这表明,模式集ℵ增加或衰减依赖于平均适应度函数值以及定义距δ(Hi).当f(ℵ,t)>(t)且δ(Hi)较小时,模式集ℵ的生存数量呈现指数级增长.反之,呈现指数级衰减.

(iii) 收缩因子F对模式集ℵ的生存数量的影响

DE算法是以差分形式V t+1i=Xti3+F ·(Xti1−Xti2)进行变异的,其中F类似于进化算法中的变异概率,则对任一模式{Hi|i ∈NP}的每一位点发生变异的概率为F,那么该位点不发生变异的概率为1−F,若每一模式Hi在变异操作作用下能够生存下来(即Hi不受破坏),也就意味着该模式Hi确定位点上的字符在变异时不能发生任何变化,又因为模式Hi的阶为O(Hi),则在变异操作作用下模式Hi不被破坏的概率为(1−F)O(Hi),从而模式集ℵ在变异操作作用下不被破坏的概率为或者写成(1−F)Θ(ℵ),它们之间是等价的关系.

综上所述,经过选择,交叉,变异操作后,X(t+1)含有模式集ℵ中元素的个数期望值如下式所示:

同时,由于收缩因子与变异概率在种群中个体的作用上是相当的,假设种群规模为NP的种群X(t) ={Xi(t)|i ∈{1,2,··· ,NP}}中每一个体的变异概率为{Pi|i ∈{1,2,··· ,NP};Pi ∈(0,1)},在种群规模为NP的种群X(t)中,任取三个相异个体{Xij|j=1,2,3},于是将(1.6) 式可改写为如下式子:

由于相异个体{Xij|j= 1,2,3}所属模式{Hij|j= 1,2,3}也是相异的,同样地,三个相异个体的变异概率{Pi|i ∈{1,2,3};Pi ∈(0,1)}是随机相异的,因而模式{Hij|j= 1,2,3}关于下一代模式和变异概率分别满足下式:

同样地,

其中,这里的P是一个理论上的具有概率特征的数学量,在算子操作作用下起到改变个体编码数值的作用,但仅仅是一种改变具体数值编码的可能性,在寻优过程中,由于自然环境或是其它影响因素,这种概率上的改变会更加明显,最终使得个体的数值编码发生改变,从而产生个体变异,实现进一步交叉和选择的可能,为产生新的寻优个体提供客观条件.在实际操作中应该对于不同模式{Hij|j=1,2,3}的变异概率,也即如下式子:

其中上面两式在理论说明上是等价的,由此可得,

当F <1,CR<1时,(1−F)Θ(ℵ)≈1−F ·Θ(ℵ),且

注意到(2.17)式以及选择、变异、交叉三种算子对模式集ℵ中所有模式{Hi(t)|i ∈{1,2,··· ,NP}}的生存数量的分析,可以得出以下结论:

结论成立.

定理2.2(模式集定理) 对DE算法进行十进制整数编码,在DE选择、交叉、变异操作作用下,具有较低模式集阶、较短模式集距、较高适应度函数值的模式集的生存数量,随种群迭代次数的增加呈现指数级增长.

推论2.1在DE算法中,低阶、短距且适应度函数值高于平均适应度函数值的模式集ℵ,在子代种群中的数量期望值以指数形式增加.

推论2.2在定理2.1证明过程中,有效地缩减了收缩因子的变化范围,将F的变化范围在理论上缩小到(0,1)区间,同时也体现了收缩因子与变异概率在种群演化过程中具有概率上的相当性特征,和Storn教授与Price教授在文[1]中对F的取值为0.5左右吻合,与文[21-26]将F均取值为(0,1)区间高度吻合.

推论2.3在种群规模为NP的种群中,适应度函数值高于平均适应度函数值的模式集ℵ中任意模式{Hi|i ∈{1,2,··· ,NP}}将会按照指数级增长方式被选择.

3.结语

本文基于十进制整数编码基础上尝试在理论层面推导出选择、交叉、变异等操作算子在推动种群演化、种群寻优的模式集定理(即DE算法推动种群演化的动力学机制),研究结论表明,在DE选择、交叉、变异等操作算子作用下,具有较低模式集阶、较短模式集距、较高适应度函数值的模式集的生存数量,将随种群迭代次数的增加呈现指数级增长.该定理从根本上说明了差分进化算法(Differential Eveolution,简称DE)在推动种群寻优的动力学机制,有效解决了离散种群个体在全局寻优方面的动力学演化机制,为后续研究连续型种群个体的动力学演化机制提供了研究基础.在研究之余,我们隐约感觉到在生物学意义上的闭生态种群中的个体具有量子特征,至于这样的量子特征在寻优过程是如何体现的,以及体现出来的是何种量子特征,还有待于进一步研究和讨论.同时还研究了收缩因子F与变异概率的相当性特征,将收缩因子F的范围缩小至(0,1)区间.本文提出的十进制整数编码DE算法的模式定理在理论层面较好解释了种群演化的内部动力学机制.