《遗传算法介绍及应用》由会员分享，可在线阅读，更多相关《遗传算法介绍及应用（11页珍藏版）》请在金锄头文库上搜索。
1、 遗传算法的介绍及应用目录1 遗传算法介绍.1 1.1 遗传算法的产生和发展.2 1.2 遗传算法的基本求解步骤.2 1.2.1 编码.2 1.2.2 初始化：.2 1.2.3 估计适应度：.3 1.2.4 再生(选择):.3 1.2.5 交叉:.3 1.2.6 变异：.3 1.2.7 重复：.3 2 遗传算法的应用例子.4 2.1 编码.4 2.2 初始化.4 2.3 计算适应度.5 2.4 再生（选择）.5 2.5 交叉.5 2.6 变异.6 3 遗传算法解决 TSP 的例子.7 3.1 TSP 问题描述.7 3.2 遗传算法用于 TSP 问题.8 3.2.1 编码表示.8 3.2.2 初
2、始化群体和适应度函数及其终止条件的设定.8 3.2.3 选择算子.9 3.2.4 交叉算子.9 3.2.5 变异算子.10 3.2.6 TSP 问题的总结.101 1 遗传算法介绍遗传算法介绍遗传算法（genetic algorithms，GA）是一种模拟自然选择和遗传机制的寻优方法， 它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。1.11.1 遗传算法的产生和发展遗传算法的产生和发展50 年代末 60 年代初
3、， 生物学家 Fraser 试图通过计算的方法来模拟生物界“遗传与选择“的进化过程，这便是 GA 的雏形。受此启发，Holland 教授认识到自然遗传可以转化为人工遗传算法。1967 年 Bagley 在其博士论文中首次提出了“遗传算法“这一术语。1975 年，Holland 出版了自然与人工系统中的适应性行为 。该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理-模式定理， 从而奠定了遗传算法的理论基础。20 世纪 80 年代初，Holland 教授实现了第一个基于遗传算法的机器学习系统-分类器系统(Classifier System 简称 CS)，开创了基于遗传算法的机器学
4、习的新概念。l992 年，John RKoza 出版了专著遗传编程 ，提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。随着遗传算法的不断发展， 关于遗传算法的国际学术活动越来越多， 遗传算法已成为一个多学科、多领域的重要研究方向。1.21.2 遗传算法的基本求解步骤遗传算法的基本求解步骤1.2.11.2.1 编码编码：确定用何种码制, 然后将问题参数编码形成基因码链，每一个码链代表一个个体, 表示优化问题的一个解。1.2.21.2.2 初始化：初始化：随机产生一个规模为 P 的初始种群, 其中每个个体为一定长度的码链, 该群体代表优化问题的一些可能解的集
5、合。1.2.31.2.3 估计适应度：估计适应度：计算种群中每个个体的适应度, 适应度为群体进化时的选择提供了依据。一般来说适应度越高, 解的素质越好。适应度函数可以根据目标函数而定。1.2.41.2.4 再生再生( (选择选择):):根据每个个体的相对适应度, 计算每个个体的再生次数, 并进行再生操作, 产生新的个体加人下一代群体中, 一般再生的概率与其适应度成正比。1.2.51.2.5 交叉交叉: :从种群中随机选择两个染色体, 按一定的概率进行基因交换，交换位置的选取是随机的。1.2.61.2.6 变异：变异：从种群中随机地选择一个染色体, 按一定的变异概率P进行基因变异,GA的搜索能力
6、主要是由选择与交叉赋于的, 变异算子则保证了算法能搜索到问题空间的每一点, 从而使算法具有全局最优性, 它进一步增强了GA的能力.1.2.71.2.7 重复：重复：若发现最优解, 则算法停止, 否则转3 ,对产生的新一代群体进行重新评价、选择、交叉、变异操作, 如此循环往复, 使群体中最优个体的适应度和平均适应度不断提高。其流程图如下：2 2 遗传算法的应用例子遗传算法的应用例子用遗传算法求解f(x)= （0=x=31） ，x为整数时f(x)的最大值2x2.12.1 编码编码在区间0,31上的整数可以用一个5位的二进制位串进行编码，x的值直接对应二进制位串的数值，如：9对应01001，31对应11111。2.22.2 初始化初始化在0,31范围内按某种分布，随机产生一个规模为P的初始种群，本例中假定初始种群取为4个二进制串，x1=01100,x2=11001,x3=01000,x4=10010。以上5位字串称为染色体，每个分量称为基因，每个基因有两种状态0或者1。2.32.3 计算适应度计算适应度计算种群中每个个体的适应度，本题中，适应度函数可定为：fitnes(x)=f(x)= ,于是Fitness（x1）=144，Fitness（x2）=625,Fitness(x3)2x=64,Fitness(x4)=4002.42.4 再
