资源描述：
《遗传算法中初始种群与交叉_变异率对解的影响及其解决方案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第17卷第3期科技通报Vol.17No.32001年5月BULLETINOFSCIENCEANDTECHNOLOGYMay2001遗传算法中初始种群与交叉、变异率对解的影响及其解决方案唐世浩,朱启疆(北京师范大学资环系,北京100875)摘要:本文的研究表明,在相同的遗传算子下,初始种群性状和数量以及交叉、变异率的确定对算法收敛速度和结果的影响不能忽略L初始种群或交叉、变异率选择不当,将增加迭代次数,甚至直接导致算法陷入局部最优解L为此,本文提出一种基于空间分割的遗传算法及初始种群产生和种群数量确定方法,并根据有关文献,提出一种自适应交叉、变异率方法L实际计算表明
2、,该算法在很大程度上避免了算法收敛于局部最优点,取得较好的效果L关键词:遗传算法;优化;初始种群中图分类号:TP301.6文献标识码:A文章编号:100127119(2001)03200012070引言[1]1962年Holland教授首次提出了GA算法的思想,从而吸引了大批的研究者,迅速推广到优化、搜索、机器学习等方面,并奠定了坚实的理论基础L遗传算法(GeneticAlgorithm,GA)借用了生物遗传学的观点,通过自然选择、遗传、变异等作用机制,实现各个个体的适应性[2]的提高L与传统优化算法相比,遗传算法具有以下特点:(1)遗传算法采用群体搜索代替传统优
3、化方法中的个体搜索L因此,遗传算法在搜索过程中不容易陷入局部最优L(2)遗传算法利用适应值信息,无需导数或其它辅助信息,即使在所定义的适应函数不连续、多峰或不可微的情况下,也能以很大的概率求得全局最优解L(3)遗传算法利用概率转移规则,而非确定性规则L遗传算法由于不受搜索空间限制性假设的约束,不必要求诸如连续性、导数存在和单峰的假设,并且由于其固有的并行性,在最优化设计、机器学习和并行处理等方面得到广泛应用L1遗传算法的基本原理常用的遗传算法一般包含四个主要操作:编码、选择、交叉和变异L应用遗传算法寻求最优收稿日期:2000211207基金项目:国家自然科学基金资
4、助项目(49871055)作者简介:唐世浩,男,1971年生,辽宁大连人,博士研究生.2科技通报17卷解的基本思想是:首先将问题的候选解进行编码,即一个候选解对应一个编码,经过编码后的候选解称为个体,许多候选解的个体组成了候选解群,称之为群体L对这样的群体像生物进化那样进行选择、交叉和变异的操作,产生新一代群体L选择的基础是适应度值,不同的问题有不同的适应度函数,对于适应度函数值高的个体在下一代有较多的选择机会,而适应度函数值低的个体,则在下一代产生数目较少的后代,最后逐渐被淘汰L通过这样的筛选,使得整个群体一代比一代优良L选择操作提高了群体的平均适应度值,但没有
5、产生新的个体L新个体的产生是通过交叉和变异操作实现的L交叉通过双亲编码的随机交换产生新一代的群体,体现了自然界信息交换的思想L交叉操作产生的新一代个体,既保留了双亲的部分基因,又引入新的基因L变异操作模拟生物进化过程中基因突变现象,虽然发生变异的概率值很小,但这种变异在优化过程中非常有意义,它可以防止求解过程中过早收敛产生局部最优解而非总体最优解L经过上述多代操作,即可最终获得问题的最优解L2初始种群和交叉、变异率对解的影响Holland教授最初提出的简单遗传算法存在着收敛速度慢、易陷入局部极小等缺陷,为提高算法性能,产生了许多改进的遗传算法L一般研究认为遗传算法
6、的搜索和优化能力取决于遗传操作基因(即遗传算子),因此目前大部分改进的遗传算法主要集中在对遗传算子的改进上,对于初始种群性状和数量以及交叉、变异率对算法的影响却鲜有研究L为简单起见,下面以求一维多峰函数F(x)=x+103sin(53x)+73cos(43x)x∈[0,9]最大值为例,说明在相同的控制参数下(解的表示方式、初始种群大小、遗传算子、终止条件相同),随机产生的初始种群和不同交叉、变异率对计算结果的影响L2.1随机产生初始种群的影响图1(a)、(b)分别为采用同一随机初始化遗传算法程序经25次迭代产生的结果L从图1(a)(b)图1随机产生初始种群对同一程
7、序两次运行结果的影响第3期唐世浩等.遗传算法中初始种群与交叉、变异率对解的影响及其解决方案3(b)可以看出,由于随机产生的初始种群略微偏向一侧,导致本次的遗传计算收敛于局部最优解L因此,在算子一定并且世代数一定的情况下随机产生初始种群可以导致计算结果不稳定L2.2交叉、变异率对解的影响许多研究都注意到,交叉、变异率对解的全局收敛性影响很大L在一般遗传算法中,交叉、变异率是个常数L然而实际计算时,交叉、变异率很难确定,小交叉、变异率可能不能保证收敛于全局最优解,大交叉、变异率会增加迭代次数,有时交叉、变异率常常需人为调整,使算法的客观性降低L图2为在其它参数固定的条
8、件下,采用
