种群动力学优化算法

第40卷第11期计算机科学Vol. 40 No. 112013年11月Computer ScienceNov 2013种群动力学优化算法黄光球李涛陆秋琴(西安建筑科技大学管理学院西安710055)摘要为了快速求解大规模复杂优化问题基于种群动力学理论构造出了可全局收敛的种群动力学优化算法。在该算法中,每个种群对应着优化问题的一个试探解,种群的一个特征对应于试探解的一个变量;采用正交拉丁方原理构造出了种群初始值确定方法,以达到对搜索空间的均衡分散性和整齐可比性覆盖;将任意两种群间的竞争、互利、捕食被食、融合、突变和选择等行为用于构造种群的进化策略,以使种群的适应度指教要么保持原状不变,要么向好的方向转移,从而确保整个算法的全局收敛性;在种群演变过程中,种群从一种状态转移到另一种状态,实现了种群对优化问题全局最优解的搜索。应用可归约随机矩阵的稳定性条件证明了本算法具有全局收敛性。测试结果表明本算法是高效的关键词进化计算,函数优化,生物地理学优化算法,种群动力学中图法分类号TP18文献标识码APopulation Dynamics-based OptimizationHUANG Guang-qiu LI Tao LU Qiurqin(School of Management, Xi'an University of Architecture& Technology, Xi'an 710055, China)Abstract To solve large-scale optimization problems(OP), a population dynamics-based optimization algorithm withglobal convergence was constructed based on the population dynamics theory. In the algorithm, each population is justan alternative solution of OP, and a feature attribute of a population corresponds to a variable of an altermative solution.The principle of orthogonal Latin squares is used to produce initial values of populations so as to cover search spacewith balance dispersion and neat comparability. The competition, mutual-benefit, predator-prey, mergence, mutation andselection behavior between any two populations are used to construct evolution policies of populations so as to ensurepopulation suitability index(PSDof each population to keep either to stay unchanged or to transfer toward better statestherefore the global convergence is ensured. During evolution process of populations, each population's transferringfrom one state to another realizes the search for the global optimum solution. The stability condition of a reducible sto-hastie matrix was applied to prove the global convergence of the algorithm. The case study shows that the algorithm isKeywords Evolutionary computation, Function optimization, Biogeography-based optimization, Population dynamics2008年, Dan Simon用生物地理学的方法提出了生物地1引言理学优化算法( Biogeography-Based Optimization,BBO)1)。种群动力学模型是描述种群与环境、种群与种群之间相该算法通过种群在栖息地间的迁移实现了对优化问题最优解互作用的动力学关系的数学模型口,可用于描述预测以至调的搜索。BBO算法解决优化问题主要依赖以下2方面2:节和控制物种的发展过程与发展趋势。常用的种群动力学模(1)栖息地的特征向量SV对应优化问题的试探解;栖息地型包括 Malthus人口模型、 Logistic模型·和 Lotka-Vol-的适宜度指数(HS)对应于优化问题的目标函数值,好的试terra模型3。近年来种群动力学模型得到广泛的研究和应探解具有较高HSI值;(2)栖息地的迁入和迁出机制对应优用先后得到了 Logistic模型和 Lotka-Volterra模型的滞后效化算法中的信息交互机制,高HSI的试探解以一定的迁出率应模型、功能性反应作用模型、反应扩散模型及年龄进行相应操作,将信息共享给低HSI试探解;低HSI试探解结构种群模型等,这些修正模型考虑到了种群的增长率和通过高HSI的试探解接受许多新的特征,这些额外的新特征环境容纳量的时间效应、非线性繁殖特性进化过程的时可以提高低HSI试探解的质量。若栖息地的较高HSI使得滞效应和随机干扰等因素2。该栖息地种群数量增多,则调低迁入率、调高迁出率。到稿日期:201301-27返修日期:20130405本文受陕西省科学技术研究发展计划中国煤化工科技计划项目(12JK0789,陕西重点学科建设专项资金资助项目(E8),陕西房地产技术经济及管理研究CNMHG黄光球(1964-),男博士,教授,主要研究方向为智能计算、计算机模拟Emil: huangnan93@so涛(1988-),男,硕土生,主要研究方向为智能计算;陆秋琴(196-),女博土,教授,主要研究方向为先进计算、计算机模拟280本文提出的种群动力学优化算法( Population dynamics-based Optimization,简称PDO算法)采用与BBO算法完全不dt =x(ntanztaiI2(4)同的设计思路,即:BBO算法采用的是生物地理学理论,而dt=x2(n2+ax1+a22x2)PD算法采用的是种群动力学理论这两种理论存在很大差式中各符号及其含义说明如下:别。PDO算法假定一生态系统中存在多种不同种类的生物(1)n<0且n2<0,表示互利共生两个种群如果分离则种群种群间进行自由竞争、互利、捕食被食以及融合等活不能单独存活的死亡率动,通过优胜劣汰强壮者获得进化,虚弱者被淘汰。而BBO(2)n>0且n>0,表示种群1和2的自然增长率,种群算法是通过种群的迁人和迁出实现进化1和种群2可以单独存活测试结果表明,PDO算法具有很强的搜索能力,且具有(3)n>0且n2<0,表示种群1可以离开种群2而单独存全局收敛性,可以用于求解大规模优化问题。活但种群2不能离开种群1而单独存活,这是一种捕食被2种群动力学优化算法构造方法食关系。(4)当a12<0且a2>0时,表示式(4)是捕食被食关系2.1一般优化问题定义系统。考虑一般优化问题(5)当a1<0且a2<0时,表示式(4)是竞争关系系统min f(X)(6)当a12>0且a2>0时,表示式(4)是互利关系系统。g;(X)≥0,i=1,2,…,I(1)(7)当a12=0且ax>0或a12>0且a2=0时,表示式st了h(X=0,i=1,2,…,E(4)是偏利关系系统x∈ScR,X0(8)当a12=0且a<0或a1<0且a2=0时,表示式式中,R是n维欧氏空间;X=(x,x…,x)是一个η维非(4)是偏害关系系统负实数决策向量;S为搜索空间,又称解空间;f(X为目标函(9)当a12=0且an=0时,表示式(4)是中性关系系统数g;(X)≥0为第i个约束条件,=1,2,…,1I为不等式约(10)当a1<0且a2<0时,表示式(4)是种内密度制约束条件个数;(X)=0为第i个等式约束条件,i=1,2,…,E,的。E为等式约束条件个数。目标函数f(X和约束条件g;(X、2.3优化问题试探解与种群动力学参数的关系h(X)不需要特殊的限制条件,传统的基于函数连续性和可导生态系统中一个种群由n个特征来表示,一个种群对应性的数学优化方法无法解决该问题于一个优化问题的试探解,N个种群所对应的优化问题的试为了使本文提出的算法适用于各种优化问题,将优化问探解解集为S={X1,x2,…,XN},X1=(x,x,…,x),i题(1)的目标函数改写成式(2):1,2,…,N;种群i中的一个特征j对应于优化问题试探解Xi∈(1,2,…,1,gA=0(2)解对应具有较高F指数的种群,差的试探解对应具有较低(X≥0;中的一个变量x6;种群的适应度指数PSI( Population Suita-f(X,Vj{1,2,…,E}h(bility Index,PSD对应于优化问题的目标函数值。好的试探FOXX∈ScR,X≥0其它PSI指数的种群即对于优化问题(1),种群i中的适应度指数式中Fa为非常大的实数用于对不满足约束条件的试探解即PS指数为进行惩罚。PSI(i)=Fm-F(X)(5)2.2 LotkaVolterra种群动力学模型24种群动力学进化算子生物群落是在特定时间聚集在一定地域或生境中所有生PDO算法利用种群动力学模型来构造进化算子实现种物种群的集合。设群落由N个种群组成,N≥2。种群间相群间信息交换,进而实现对优化问题解空间的搜索。PDO算互作用关系可分为两大类:a)无相互作用关系:包括互不影响法的进化算法如下所述。的中性作用,一方受害另一方不受影响的偏害作用以及一方(1)竟争算子。种群动力学竞争算子描述的是任意2个受益另一方不受影响的偏利作用;b)相互作用关系:包括竞种群间的竞争行为。依据式(4),可以构造出种群i与种群j争(资源利用性竞争和相互干扰性竞争)互利(专性互利共生间的竞争算子即对于i,j∈{1,2,…,N},i≠j,s∈{1,2,…,和兼性互利共生)和捕食作用(捕食被食)。PDO算法中的n},有算子可利用上述各类相互作用关系进行构建。可描述各种群t=x(1+n-auxfl-anx: 1)(6)间相互作用的种群动力学模型为 Lotka-volterra模型,N个v=z1(1-n-a211-am1)种群的 Lotka-Volterra模型如下式中,和v为种群i与种群j的特征s在时期t时的状态d=x(r;-∑ayx;),i=1,2,…,N(3)值,Ⅵ=(v,h…,)=(功,咖…,项)右和¤为种群i与种群j的特征s在时的期t-1时状态值,X式中,x是种群讠的大小,x≥0;n>0称为种群i的内禀增(x1,d1(2,1,…功1);参与竞争长率;a(i≠j的正负符号和绝对值表示种群j对种群i的影的种群=Ran中国煤化工;Rand(a,b)表响性质和强度a表示种群i的种内调节参数,a<0表示种示在[ab区间产CNMHG正负号直接放内竞争或种内密度制约。下面我们重点研究2个种群间的入到表达式中,所以有n>0,a1>0,a12>0,n>0,a2>0,Lotka-volterra模型,由式(3)可得:a2>0,下同281(2)互利算子。种群动力学互利算子描述的是任意2个的求解性能。但对于高维优化问题,进化算法的求解性能则种群间的互利行为,依据式(4),可以构造出种群i与种群j急剧下降。一个很重要的原因是在高维空间,单位体积内初间的互利算子,即对于i,j∈{1,2,…,N},i≠j,s∈{1,2,始解的含量极低,当然极难做到均匀分布。例如,在边长为0的n维空间立方体中(即0≤x≤10,i=1,2,…,n),若100v=右1(1+n-a1x1+a121)个初始解分布于其中,则单位体积内的初始解的个数为v=功1(1-n2+an1x1-a21)10-(m-2)。在2维空间内,单位体积内的初始解的个数为1式中,参与互利的种群i=Rand(1,N),=Rand(1,N),ij。个,而在1000维空间内,单位体积内的初始解的个数为3)捕食被食算子。种群动力学捕食被食算子描述的1098个,两者相差10倍。若在100维空间要做到单位体是任意2个种群间的捕食被食行为依据式(4),可以构造出积内含1个初始解(即保持与2维空间具有相同的搜索效种群i与种群j间的捕食被食算子,即对于i,∈{1,2,…,力),则需要10∞0个初始解。显然,这在工程应用中是不可能N},i≠j,s∈{1,2,…,n},有实现的。如何让很少的初始解尽可能地代表高维空间的分布v=右1(1+n-a1x-a12x1)(8)特性呢?正交表就是一个很好的解决方案v=d1(1-n2+a1G1-a21)正交表是遵循概率统计规律,依照一定原则(如正交拉丁式中,参与捕食被食的种群i=Rand(1,N),j=Rnd(1,N),方)生成的。通常等水平正交表写成L(r),其中a表示正交表的行数或初始解的个数;t表示正交表同一列中出现的因(4)融合算子。融合算子描述的是当前种群i的某些特素的水平数(位级数);m表示正交表的列数(即优化问题解空性与其它若干个种群的某些特性融合在一起(而余下的特性却保留下来),产生新一代种群,即对于∈1,2,…,N,∈优的覆盖度,关键在于它的均衡分散性和整齐可比性。正是{1,2,…,n},有这种均衡性带来“冒尖”(即优良的组合明显化),这一点在非参数统计中有以下定理1保证。tax2+2Ax,若Ran(0,1)≤(9)定理113设随机变量X遵守连续概率分布P(X),否则X1,X2,…,XN为总体X的一个容量为N的简单样本。把N式中,=Rand(1,N);Vk,v∈{1,2,…,B},≠L≠i;B次随机变数X1,X2,…,XN按照观测值从小到大排列起来,为与种群i发生融合的其它种群数,称为融合种群数,B≥1,a,A,g称为融合选择率且0PS(x-2)i=1,2,…,N式中,k=(+j-1mdN;若k=0,则k=N其它算法1所确定的N个初始解X=(x1,x(11)1,2,…,N具有很好的均衡分散性和整齐可比性旦新的种群形成之后,PDO算法继续通过竞争、互利、2.6PDO算法设捕食-被食融合突变和选择等算子对群落不断进行演化,直算法2PI中国煤化工到找到最优解。(1)初始化:a)令CNMHG到的所有参数;2.5高维空间初始点的选择方法c)按算法1确定N个初始解;d)对N个初始解的从优到劣进行排众所周知,对于低维优化问题进化算法一般都具有很好序,使PSI值较高的初始解排在前面。282(2)执行下列操作表1PDO算法时间复杂度计算表FORt=1TOG//G为演化最大代数时间复杂度最多循环次数EH-X-1,i=1,2,…,KP//将前KP个最佳试探解作为精英保存始化On+4nN+N(N+1)选代准备OnKP)下来;竟争算子O(2n)FOR i=l TON互利算子o(2n)随机选择种群 i=Rand(1,N),确保ij捕食被食算子O(2n)融合算子FOR s=l TO目标函数计算Ip≤ PA THEN/A为当前种群i与种群j发生竞争行为的概结果排序O4n+(N+1))率上限B1为该竞争行为出现的实际概率p1=Ran(0,1)突变算子O3mr-+4nme选择算子O(3n)GN按式(6)执行竞争算子,得到v和v结果排序O(n+(N+1))计算v=2(v+v)情英替换OnKP)结果输出ELSEIF Pi,p=0的误差满足最低要求 E THEN转(3)将倒数KP个最差的解用保存下来的精英进行替换,即X-k1=E1,k=1,2,…,KP(1)式(12)的证明。设X’为第t次演化后的种群的状END FOR态,记为Y,设Y中状态最好的种群为 g Best2=X,即有F(3)结束。( g Best)=F。通过PD算法存每次演化过程中对当前种2.7算法的时间复杂度群最好状态的更中国煤化工PDO算法(算法2)的时间复杂度计算过程如表1所列,CNMHG其时间复杂度与演化次数G种群规模N变量个数n搜索F(X+1)≤F(X)→Vk>i,内,k=0→Vk>i,p,算子的时间复杂度以及其他辅助操作相关力,,=0→Vk>i,户,A=0·283·(2)式(13)的证明。在PDO化算法中设gesr+为Y+ Markov链上的一个状态,根据引理1中式(12)的结论可得,中最优种群的状态,此时种群随机选择活动行为,有竞争行该 Markov链的转移矩阵为:为、互利行为捕食被食行为融合行为和静止行为5种情况。p2,1p2,20情形1当前种群i选择竞争行为。若种群i的状态可以转移到更优的状态上,则其将以概率P1= pI pMps+p(1PN. 1 PN.p)抄=力内更新到新状态,显然P1>0,命题得证。其根据引理1中式(13)的结论得中,pM为突变算子执行成功的概率(即被突变了);ps为选择p1>0,R=(p2,1,p31,pu…,px:)T算子执行成功的概率(即被选中了)情形2当前种群i选择互利行为。若种群i的状态可∵.:|≠0,C=(p)=(1)≠0以转移到更优的状态上,则其将以概率P2=P2Mps+p(1AM)内s=pps更新到新状态,显然P2>0,命题得证。由以上可知转移矩阵P是N阶可归约随机矩阵满足情形3当前种群i选择捕食被食行为。若种群i的状定理2的条件,所以下式成立态可以转移到更优的状态上,则其将以概率P3=力3Mps+0(1-pM)s=内加s更新到新状态,显然P3>0,命题得证情形4当前种群i选择融合行为。若种群i的状态可以转移到更优的状态上,则其将以概率P4= P4 PMPs+p4(1因C=C=(1),T=0,故必有R=(1,1,…,1),这是p)ps=p4p更新到新状态,显然P4>0,命题得证因为Mkov转移矩阵P中每行的概率之和为1。因此有P情形5当前种群i选择静止行为。若种群i的状态可以转移到更优的状态上,则其将以概率P5=pMs+(110且为稳定的随机矩阵AM)内=内内更新到新状态显然P3>0,命题得证。在任意一个时间段内,任一种群i必选上述5种行为之,即p+p2++p+p=1。综合上述各种情况,可得总上式表明,当k→∞时,概率A1=1,i=1,2,…,N,也即概率为:无论初始状态如何,最后都能以概率1收敛到全局最优状态Pa=P+P2+P,+P=(p+P2+P3+p4)Ps=ps1上。于是得因0≤内≤1,易知P4≥0;如果P>0,命题得证;如果limp{F(Ⅺ)→F(X)}=1,=1,2,…,NP=0,说明p=0,即F(V)>F(X1)出现的概率永为0表因此,PDO化算法具有全局收敛性,证毕。明种群演化已经到达全局最优解状态 g Best+=x',而不是定理3表明:局部最优解。(1)若随机搜索的每个状态都能以概率p>0转移到综合上述情况可得彐k0,证毕。个比当前状态更优的状态上,则该随机搜索收敛,即搜索几乎定理21设P是一n阶可归约随机矩阵,也就是通过以概率1找到全局或局部最优解。概率p越大,收敛越快(2)随机搜索的某个状态若无法以概率p>0转移到一个相同的行变换和列变换后可以得到P其中C比当前状态更优的状态上,则宁愿保持当前状态不变也不要是m阶本原随机矩阵并且R≠0,T≠0,则有:转移到比当前状态更差的状态上。若该情况经常出现,则收敛过程很慢。(3)若随机搜索的状态以同样的概率转移到一个比当前00状态更好、保持不变或更差的状态上(即下一个状态是好是坏或保持不变随机出现)则该随机搜索发散,即该随机搜索找到全局或局部最优解的概率几乎为0。文献[1]用很复杂的上述的矩阵是一个稳定的随机矩阵且P=1P理论证明了粒子群算法不收做,就是这个原因。P=PP唯一确定并且与初始分布无关。P∞满足如下条顺便指出,当随机搜索陷入局部最优解状态时,很多随机件搜索算法采用所谓的逃逸方法试图跳出局部最优解状态。然P=[Ax,01n,1j≤m而,若跳出后的状态比局部最优解状态差,这种情况几乎以很内=0,1≤i≤n,m