资源描述：
《遗传算法时间复杂性的研究_戴晓晖》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第14卷第1期系统工程学报Vol.14No.11999年3月JOURNALOFSYSTEMSENGINEERINGMar.1999①遗传算法时间复杂性的研究②戴晓晖李敏强寇纪淞(天津大学系统工程研究所,天津300072)摘要遗传算法的时间复杂性是目前研究的焦点之一.本文以模式生存的概念为基础,将模式风险函数引入遗传算法的分析中,建立了一种随机可靠性模型,分析了遗传算法的时间复杂性.关键词:遗传算法,模式,可靠性,时间复杂性分类号:N94THESTUDYONTHETIMECOMPLEXITYOFGENETICALGORITHMSDaiXi
2、aohuiLiMinqiangKouJisong(InstitueofSystemsEngineering,TianjinUniversity,Tianjin300072)AbstractInpresent,theoneoftheresearchfocusesongeneticalgorithmisthetimecomplexityofgeneticalgorithm.Webaseonthenotionofschemasurvival,drawthenotionofschemahazardfunctionintotheanalysiso
3、fgeneticalgorithm,setupastochasticreliabilitymodel,andanalyzethetimecomplexityofgeneticalgorithm.Keywords:geneticalgorithms,schema,reliability,timecomplexity0引言遗传算法(geneticalgorithm,GA)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模[1]型,它是由美国Michigan大学的Holland教授于1975年首次提出的,这是一种新的全局优化搜索算法,其简
4、单通用,鲁棒性强,适于并行处理,已经广泛地应用在计算机科学、优化调度、运输问题及组合优化等领域.尽管遗传算法在实际应用中取得了巨大的成功,但相对其鲜明的生物基础,其数学基础是相对不完[2,3]善的,主要表现为:(1)缺乏广泛而完整的遗传算法收敛性理论;(2)Holland的模式定理尚不能清楚[4,5,6]地解释遗传算法的早熟现象和欺骗问题;(3)遗传算法的搜索效率及其时间复杂性.这些不足严重阻碍了遗传算法的应用与推广.本文以模式生存的概念为基础,将模式风险函数引入到遗传算法的分析中,建立了一种随机可靠性模型,分析了遗传算法的时间复杂性.
5、①国家自然科学基金资助项目(79400013,69574022).②男,博士生.male,doctoralstudent.本文1998年5月5日收到.—74—系统工程学报第14卷第1期1风险函数首先,对“模式生存”概念进行重新定义,即模式H生存到下一代,被理解为至少有r个模式H的个体生存下来,这里r是一个预先给定的小的正整数.显然,r的大小极为重要.考虑到遗传算法的随机误差,r的值应大于1,即r=2,3,4….假设在t代群体中含有模式H的mH(t)个个体,这mH(t)个个体的平均适应度为fH.根据赌轮选择N策略,在一次选择中,个体i被选
6、中的概率为fi/∑fj,其中N为群体大小.j=1令ps为模式H的个体在一次实验中被选中的概率,那么m(t)Hfi)fHps=∑(N=mH(t)N(1)i=1∑fj∑fjj=1j=1将群体N划分为两个不相交的集合,即模式H的mH(t)个个体组成的集合RH和非模式H的N-mH(t)个个体组成的集合RH.整个群体的选择可以认为是N次相互独立的贝努利实验的结果.在每次实验中,任一模式H的个体被选中的概率为ps,而非H模式的个体被选中的概率为1-ps,那么模式H的个体在N次实验中被选中的概率为NxN-xps(1-ps)x其中x为从集合RH中被选出
7、的个体数.在遗传算法的运行过程中,它们中的一些遭到交叉算子或变异算子作用的破坏,另一些继续生存下去.每个个体生存的概率为W(H)psurv=1-pc-o(H)pm(2)L-1其中pc为交叉概率、pm为变异概率、L为染色体长度、W(H)为模式H的定义距、o(H)为模式H的阶.假定生存个体的个数服从二项式分布,个体j(属于x个被中的个体集合)在交叉、变异算子作用下生存的概率为xjx-jpsurv(1-psurv)j因此,至少有r个模式H的个体生存的概率为NNNxxN-xjx-j∑∑ps(1-ps)psurv(1-psurv)j=rx=jxj
8、因此,最多有r-1个个体不能生存的概率为NNNxN-xxjx-j1-∑∑ps(1-ps)psurv(1-psurv)j=rx=jxj上式实际上是一个条件概率,即模式H在t代中生存,而在t+1代灭亡的概率.令
