基于生态种群竞争模型的协同进化

1000-9825/2001/12(04)0556-07○c2001JournalofSoftware　软件学报Vol.12,No.4基于生态种群竞争模型的协同进化

曹先彬,　罗文坚,　王煦法

(中国科学技术大学计算机科学与技术系,安徽合肥　230026)

E-mail:xbcao@http://www.77cn.com.cn

http://www.77cn.com.cn

摘要:遗传算法基于适应度的进化模式没有考虑进化的外部环境和进化成分之间的关系,这是协同进化研究的内容.借鉴生态学对个体生存环境和种群竞争的认识,构造了一种基于生态种群竞争模型的新的协同进化模式.模拟实验表明,采用该模式的改进遗传算法在改善未成熟收敛和收敛速度两方面具有良好的性能.

关键词:遗传算法;生态环境;种群密度;生态种群竞争;未成熟收敛

中图法分类号:TP18　　　文献标识码:A

协同进化(co-evolution)是近年来针对遗传算法(geneticalgorithms,简称GA)的不足而兴起的一个研究热点,意指多个种群通过适应度的关联同时进化,最早由Ehrlich和Raven提出[1].这一概念在理论进化中非常重要,它被广泛定义为一种适应度基于种群密度、种群自身及相作用种群的遗传成分的进化,特别适合于复杂进化系统的动态描述.与协同进化相比,遗传算法作为目前常用的一种优化技术,只是采用基于个体自身适应度的进化模式,而没有考虑其进化的环境和个体之间的复杂联系对个体进化的影响.正因如此,它在应用中表现出了易出现未成熟收敛,并且收敛的速度较慢等缺陷.现有的改进方法虽然很多[2～4],但如果仍然只是通过个体适应度来控制个体的进化,则难以获得满意效果.

另一方面,对协同进化的研究刚刚开始,其研究领域也不全面.目前主要是在人工智能游戏背景下讨论进化计算中的竞争性协同,即一个种群中任意一个体基于适应度的进化都相关于另一种群中部分个体的直接竞争,这需要为游戏的每一步(Host种群)构造相应的对手集(parasite)和测试集,以保证在对手集进化的同时,Host能随之克服对手的挑战,最终达到最优状态.如文献[1,5,6]等中的工作.但这种方法的实现非常困难,很难构造一个通用的模型;另外,也没有直接考虑个体或种群与环境之间的相互作用.因此,我们认为在研究进化时,有必要先从协同进化的3个方面对其建模,再用来指导个体的进化.

生态学[7]目前对个体所处的环境和相互间的竞争协同认识得较为深入,它认为,生存在一定自然环境资源制约中的种群,通过相互之间的竞争协同,互相驱使双方提高性能和复杂性,从而实现种群之间的协同进化.衡量种群竞争协同的一个主要因素是种群密度,如果种群密度大,则该种群的竞争能力就强,反过来又增强了种群密度.本文借鉴种群密度的概念,提出一种协同进化模型,该模型的动力学特征可以比较全面地描述个体与环境及相互之间的协同行为.基于该模型的改进进 收稿日期:1999-10-20;修改日期:2000-01-21

基金项目:国家自然科学基金资助项目(69971022);中国科学技术大学青年基金资助项目

作者简介:曹先彬(1969-),男,安徽巢湖人,博士,副教授,主要研究领域为计算智能,网络安全;罗文坚(1974-),男,广东梅州人,博士生,主要研究领域为人工免疫,网络安全;王煦法(1948-),男,江苏丹阳人,教授,博士生导师,主要研究领域为计算

曹先彬等:基于生态种群竞争模型的协同进化557化算法在一定程度上脱离了只采用个体适应度控制进化的生物进化框架.实验结果显示了该模型在改善未成熟收敛和提高收敛速度两方面的有效性.

1　基于种群密度的协同进化模型

协同进化的个体在自身进化过程中受3个主要因素的影响:个体适应度、所处生存环境以及与其他个体之间的相互竞争.这一观点与生态学对生物进化的认识非常类似.理论生态学在这些方面的研究也比较深入.从种群的角度来考虑,它认为,在一定生态环境中的种群,其种群进化不仅受到自身适应度的影响,同时还受到环境和与其他种群相互之间的竞争协同的影响,其中后两种因素在种群层次上可以通过种群密度来体现.

首先,如果不考虑种群之间的相互竞争,我们引入生态学中的逻辑斯谛(logistic)方程来描述种群增长与环境间的动力学特征,它是生态学中预测种群密度的一个有效工具.

=rN,dtK

其中K表示环境负荷量,r表示种群个体增长率,N是种群大小,(1)称为Logistic系数.从式K

(1)可以看出,Logistic系数对种群密度变化起着一种制动作用,使种群密度总是趋向于环境负荷量.当N>K时,Logistic系数是负值,种群密度下降;当N<K时,Logistic系数是正值,种群密度上升;当N

=K时,Logistic系数为0,此时种群密度不变(如图1所示).

Fig.1　Therelationshipofpopulationincrementandenvironment

图1　种群增长与环境之间的关系

以Logistic方程为基础,我们进一步考虑种群之间的协同.这时,种群增长符合一定的竞争方程(Lotka-Volterra竞争方程),这个竞争方程是在Logistic方程的基础上建立起来的,构成了种群竞争的理论模型.我们以此为基础来构造基于种群密度的协同进化模型.先考虑两个种群N1和N2之间的协同.:

111122=r1N1,dtK1

222211=r2N2,dtK2(2)(3)

其中K1和K2分别表示在不发生竞争的情况下,种群N1和N2的环境负荷量;r1和r2表示每个种群、每个个体的最大瞬时增长率;a12和a21是竞争系数,aij表示种群Nj的每个个体对种群Ni的竞争抑制作用.:

558JournalofSoftware　软件学报　2001,12(4)

(1)若不存在种间协同,即方程中a12或N2等于0和a21或N1等于0时,两个种群各自遵循

形增长,直到种群密度达到各自的环境负荷量为止,此时两种群密度达到Logistic方程,都能呈“S”

平衡.

(2)若存在种群协同,N1种群中每个个体对自身种群增长的抑制作用等于1/K1.同样,N2种群中每个个体对N2种群增长的抑制作用等于1/K2;N2种群中每个个体对N1种群增长的抑制作用等于a12/K1,N1种群中每个个体对N2种群增长的抑制作用等于a21/K2.一般来讲,竞争系数是大于0而小于1的数值.协同的结果将取决于K1,K2,a12和a21这4个值的相互关系.

令式(2)和式(3)中的dN1/dt=0,dN2/dt=0,即可作出每个种群的dN/dt等值线,如图2所示.从中可以看出:

(1)当K2/a21<K1,K1/a12>K2时,N1等值线位于N2等值线上方,种群1总是得胜,只有在N1=K1和N2=0时才能达到稳定平衡(如图2(a)所示);

(2)当K2/a21>K1,K1/a12<K2时,N2等值线位于N1等值线上方,种群2总是得胜,只有在N2=K2和N1=0时才能达到稳定平衡(如图2(b)所示);

(3)当K2/a21<K1,K1/a12<K2时,两个种群都可能得胜,都能抑制对手,存在3种平衡,但交叉点平衡是不稳定的.稳定平衡的条件是N2=K2,N1=0或N1=K1,N2=0,谁能得胜将取决于两个种群的最初数量比(如图2(c)所示);

(4)当K2/a21>K1,K1/a12>K2时,两个种群都不能抑制对方,只存在一个平衡点(交叉点),两个种群可以在各自的环境负荷量下以特定种群密度共存(如图2(d)所示).

K1/a12

K2N2dN10dK2N2K1/a12dN2N1

K2/a21K2N2K1/a12dN20K1/a12K2N2dt=0dN0N10K2/a211

(a)0dN0K1(b)dN10K2/a211(c)dN10K1K2a21(d)

Fig.2Theiso-linesoftwocollaborativepopulations图2两种群协同等值线

对于一个由n个不同种群组成的群落,上述竞争方程可以改写成以下形式:

n

Ki-Ni-dNiiidt=rN∑aj=1ijNj

K.(4)

i

这就是基于生态种群密度的协同模型.引入此模型到进化算法中可以得到相应的协同进化模式.它充分考虑了群体间的各种关系,我们相信它能大大提高染色体的多样性,同时也有利于提高全 …… 此处隐藏：8725字，全部文档内容请下载后查看。喜欢就下载吧 ……