遗传算法介绍及应用

《遗传算法介绍及应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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