资源描述:
《遗传算法介绍及应用》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、遗传算法的介绍及应用目录1遗传算法介绍11.1遗传算法的产生和发展21.2遗传算法的基本求解步骤21.2.1编码21.2.2初始化:21.2.3估计适应度:31.2.4再生(选择):31.2.5交叉:31.2.6变异:31.2.7重复:32遗传算法的应用例子42.1编码42.2初始化42.3计算适应度52.4再生(选择)52.5交叉52.6变异63遗传算法解决TSP的例子73.1TSP问题描述73.2遗传算法用于TSP问题83.2.1编码表示83.2.2初始化群体和适应度函数及其终止条件的设定83.2.3选择算子93.2.4交叉算子93
2、.2.5变异算子103.2.6TSP问题的总结101遗传算法介绍遗传算法(geneticalgorithms,GA)是一种模拟自然选择和遗传机制的寻优方法,它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。基因杂交和基因突变可能产生对环境适应性强的后代,通过优胜劣汰的自然选择,适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理,并引用了随机统计原理而形成的。1.1遗传算法的产生和发展50年代末60年代初,生物学家Fraser试图通过计算的方法来模拟生物界"遗传与选择"的进化过程,这便是GA的雏形。受此启发,H
3、olland教授认识到自然遗传可以转化为人工遗传算法。1967年Bagley在其博士论文中首次提出了"遗传算法"这一术语。1975年,Holland出版了《自然与人工系统中的适应性行为》。该书系统地阐述了遗传算法的基本理论和方法,提出了遗传算法的基本定理-模式定理,从而奠定了遗传算法的理论基础。20世纪80年代初,Holland教授实现了第一个基于遗传算法的机器学习系统--分类器系统(ClassifierSystem简称CS),开创了基于遗传算法的机器学习的新概念。l992年,JohnR.Koza出版了专著《遗传编程》,提出了遗传编程的
4、概念,并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。随着遗传算法的不断发展,关于遗传算法的国际学术活动越来越多,遗传算法已成为一个多学科、多领域的重要研究方向。1.2遗传算法的基本求解步骤1.2.1编码:确定用何种码制,然后将问题参数编码形成基因码链,每一个码链代表一个个体,表示优化问题的一个解。1.2.2初始化:随机产生一个规模为P的初始种群,其中每个个体为一定长度的码链,该群体代表优化问题的一些可能解的集合。1.2.3估计适应度:计算种群中每个个体的适应度,适应度为群体进化时的选择提供了依据。一般来说适应度越高,
5、解的素质越好。适应度函数可以根据目标函数而定。1.2.4再生(选择):根据每个个体的相对适应度,计算每个个体的再生次数,并进行再生操作,产生新的个体加人下一代群体中,一般再生的概率与其适应度成正比。1.2.5交叉:从种群中随机选择两个染色体,按一定的概率进行基因交换,交换位置的选取是随机的。1.2.6变异:从种群中随机地选择一个染色体,按一定的变异概率P进行基因变异,GA的搜索能力主要是由选择与交叉赋于的,变异算子则保证了算法能搜索到问题空间的每一点,从而使算法具有全局最优性,它进一步增强了GA的能力.1.2.7重复:若发现最优解,则算
6、法停止,否则转3,对产生的新一代群体进行重新评价、选择、交叉、变异操作,如此循环往复,使群体中最优个体的适应度和平均适应度不断提高。其流程图如下:2遗传算法的应用例子用遗传算法求解f(x)=(0=7、000,x4=10010。以上5位字串称为染色体,每个分量称为基因,每个基因有两种状态0或者1。2.3计算适应度计算种群中每个个体的适应度,本题中,适应度函数可定为:fitnes(x)=f(x)=,于是Fitness(x1)=144,Fitness(x2)=625,Fitness(x3)=64,Fitness(x4)=4002.4再生(选择)初始种群中每个个体入选种群的概率为:p(xi)=fitness(xi)/∑ifitness(xi).利用上述概率,对这四个整数进行四次有放回的随机抽取,产生四个新的整数,显然概率大的有更多的机会被抽
8、中,四个新的整数=01100,=11001,=11001,=10010.经前四步后,具体情况如表下所示:序号初始种群X值适应度人选种群概率期望复制数实际复制数1011001214412%0.48121100