遗传算法介绍及应用

1、 遗传算法的介绍及应用目录1遗传算法介绍11.1遗传算法的产生和发展21.2 遗传算法的基本求解步骤2编码2初始化：2估计适应度：3再生(选择):3交叉:3变异：3重复：32 遗传算法的应用例子42.1 编码42.2 初始化42.3 计算适应度52.4 再生（选择）52.5 交叉52.6 变异63 遗传算法解决TSP的例子73.1 TSP 问题描述73.2 遗传算法用于TSP 问题8编码表示8初始化群体和适应度函数及其终止条件的设定8选择算子9交叉算子9变异算子10问题的总结101遗传算法介绍遗传算法（genetic algorithms，GA）是一种模拟自然选择和遗传机制的寻优方法， 它是建

2、立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。1.1遗传算法的产生和发展50 年代末60 年代初， 生物学家Fraser 试图通过计算的方法来模拟生物界"遗传与选择"的进化过程，这便是GA 的雏形。受此启发，Holland 教授认识到自然遗传可以转化为人工遗传算法。1967 年Bagley 在其博士论文中首次提出了"遗传算法"这一术语。1975 年，Holland 出版了自然与

3、人工系统中的适应性行为。该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理-模式定理， 从而奠定了遗传算法的理论基础。20 世纪80 年代初，Holland 教授实现了第一个基于遗传算法的机器学习系统-分类器系统(Classifier System 简称CS)，开创了基于遗传算法的机器学习的新概念。l992 年，John RKoza 出版了专著遗传编程，提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。随着遗传算法的不断发展， 关于遗传算法的国际学术活动越来越多， 遗传算法已成为一个多学科、多领域的重要研究方向。1.2 遗传算法的基本求解步

4、骤 编码：确定用何种码制, 然后将问题参数编码形成基因码链，每一个码链代表一个个体, 表示优化问题的一个解。随机产生一个规模为P的初始种群, 其中每个个体为一定长度的码链, 该群体代表优化问题的一些可能解的集合。1.2.3估计适应度：计算种群中每个个体的适应度, 适应度为群体进化时的选择提供了依据。一般来说适应度越高, 解的素质越好。适应度函数可以根据目标函数而定。(选择):根据每个个体的相对适应度, 计算每个个体的再生次数, 并进行再生操作, 产生新的个体加人下一代群体中, 一般再生的概率与其适应度成正比。从种群中随机选择两个染色体, 按一定的概率进行基因交换，交换位置的选取是随机的。 变异

5、：从种群中随机地选择一个染色体, 按一定的变异概率P进行基因变异,GA的搜索能力主要是由选择与交叉赋于的, 变异算子则保证了算法能搜索到问题空间的每一点, 从而使算法具有全局最优性, 它进一步增强了GA的能力. 重复：若发现最优解, 则算法停止, 否则转3 ,对产生的新一代群体进行重新评价、选择、交叉、变异操作, 如此循环往复, 使群体中最优个体的适应度和平均适应度不断提高。其流程图如下：2 遗传算法的应用例子用遗传算法求解f(x)= （0=<x<=31），x为整数时f(x)的最大值2.1 编码在区间0,31上的整数可以用一个5位的二进制位串进行编码，x的值直接对应二进制位串的数值

6、，如：9对应01001，31对应11111。2.2 初始化在0,31范围内按某种分布，随机产生一个规模为P的初始种群，本例中假定初始种群取为4个二进制串，x1=01100,x2=11001,x3=01000,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)=f

7、itness(xi)/ifitness(xi). 利用上述概率, 对这四个整数进行四次有放回的随机抽取, 产生四个新的整数, 显然概率大的有更多的机会被抽中，四个新的整数=01100，=11001，=11001，=10010.经前四步后，具体情况如表下所示：序号初始种群X值适应度人选种群概率期望复制数实际复制数1011001214412%0.4812110012562551%2.0423010008645%0.204100102040032%1.281合计1233100%44平均308.325%112.5 交叉将（i=1，2，3，4）随机结合成两组，每组两个数；对每组再进行一次随机抽样，以等概

8、率从1，2，3，4中选取一个数n.假设在上述例子中恰=01100，=11001分为一组，随机抽取n=3,那么将由二进制表示的，从后三位开始互换，得到两个新的二进制整数，记为，。同样对另外一组数作类似处理，假设另一组抽得n=2,这样得到四个新的整数，结果为=01001，=11100，=11010，=10001.具体情况如表所示：序号复制后种群复制对象交叉点n交叉后种群X值适应度1011002301001981211001131110028784311001422110102248441001031000117289合计1638平均409.52.6 变异将交叉得到的四个二进制数, 每个数每个二进位

9、进行一次随机抽样，以一个小概率P,例如1、1000将该位取反，即由1变为1，由1变为0，以概率1-P保持该位数字不变。这样得到四个新的数记为（I=1，2，3，4），计算其函数值f(),回到步骤（4）。对产生的新一代群体进行重新计算适应度、选择、交叉、变异操作，如此循环往复，使群体中最优个体的适应度和平均适应度不断提高。变异可保持群体的多样性，可使遗传算法跳出局部极值点。 以上的简单例子, 从开始随机产生的种群到经过一次再生、交叉、变异操作后的新种群中, 我们不难看出初始种群的平均适应度为303.8, 新种群的平均适应度为409.5, 最大值从初始种群的625增加到新种群的784。可见经过一次遗

10、传算法的操作后, 问题的解向最优解的方向前进了一大步。因此经过以上多次类似计算,问题的解最终会接近最优解。当然在应用遗传算法时, 可以事先规定一个最大允许循环次数, 以使计算得到终结, 而以计算过程达到的最大函数值的作为所要的解, 遗传算法实际上是一种搜索方式, 对那些标准数学方法难以奏效的问题给出了一种处理办法。3 遗传算法解决TSP的例子旅行商问题(TSP)，也称为货郎担问题，是一个较古老的问题。最早可以追溯到1759 年Euler 提出的骑士旅行问题。1948 年，由美国兰德公司推动，TSP 成为近代组合优化领域的一个典型难题。应该说，TSP 是一个具有广泛应用背景和重要理论价值的组合优

11、化难题，它已经被证明属于NP 难题。对TSP 问题的大量研究使得TSP 问题成为了一个著名的组合优化问题目前，求解TSP 问题的较为常用的方法有二叉树描述法、启发式搜索法、最近邻法、神经网络法、模拟退火法和遗传算法等。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局概率搜索算法，具有良好的全局寻优能力，成为解决问题的有效方法之一。3.1 TSP 问题描述TSP（旅行商问题）的简单描述是：一名商人欲到n 个城市推销商品，每两个城市i 和j 之间的距离为d，存在i，j 如何使商人每个城市走一遍后回到起点，且所走的路径最短。用数学符号表示为：设n 维向量表示一条路径X=(C1,

12、C2, ,Cn)，目标函数为minF(x)= 用图语言来描述TSP，给出一个图G=(V, E)，每边eE 上有非负权值w(e)，寻找G 的Hamilon 圈C，使得C 的总权W(C)= 最小。TSP 搜索空间随着城市数n 的增加而增大，所有的旅程路线组合数为(n-1)! /2。5 个城市的情形对应120/10=12 条路线，10个城市的情形3628800/20=181440 条路线，100 个城市的情形则对应有4.6663×条路线。在次庞大的搜索空间中寻求最优解，对于常规方法和现有的搜索而言，存在诸多的计算困难。借助遗传算法的搜索能力解决TSP 问题是很自然的想法。3.2 遗传算法用

13、于TSP 问题 编码表示用遗传算法求解TSP 时，算法的编码表示是算法设计的重点，它对遗传基因的操作有一定的限制。TSP 的编码策略主要包括二进制表示、顺序表示、路径表示、矩阵表示和边表示等。由于二进制编码具有如下的特点数据冗长，并且表达能力有限，计算机无法承受如此巨大的计算量甚至根据调整不同的参数时，所运行的时间，有时会达到近几个小时，从时间效率来说，工作效率实在是低下，并达到无法忍受的程度，所以实际中很少使用。顺序表示是指将所有城市依次排列构成一个顺序表，对于一条旅程，可以依次旅行经过顺序处理每个城市，每个城市在顺序表中的顺序就是一个遗传因子的表示。每次处理完一个城市，从顺序表中去掉该城市

14、。处理完所有城市后，将每个城市的遗传因子连接起来，即成为一条旅程的基因表示（染色体编码）。路径表示是表示旅程岁应的基因编码的最自然，最简洁的表示方法。 初始化群体和适应度函数及其终止条件的设定根据编码方法，随机产生初始群体，直到达到所需规模为止。适应度函数，由于是求最短路径，适应度函数一般采用求函数最大值，例如取路径总长度T 的倒数，即fitness=l/T。其中， T=适应度越小的个体，该个体的路径越短，该个体则越好。也有采用fitness=l/T2 计算适应度的算法。也有的算法采用fitness=1/(T+aN)，其中N 为未遍历的城市的个数，a 为惩罚函数系数，常取城市间最长距离的两倍多

15、，路径T 越大，适应度函数越小。迭代停止条件一般是：若某代群体中的最差个体与最好的个体适应度的差不大于某个数（根据问题规模变化），则终止算法。若最佳个体连续保持一定代数，则终止算法。若算法迭代次数达到一定代数，则终止算法。 选择算子选择是从一个旧种群(old population)中选择生命力强的个体位串产生新种群的过程。或者说，选择是个体根据其适值函数f 拷贝自己的过程。直观地讲，可以把适值（或目标）函数f 看作是我们期望的最大效益或好处的某种量度。根据个体的适值拷贝位串意味着：具有高的适值的个体更大可能在下一代中产生一个或多个子孙。显然这个操作是模仿自然选择现象，将达尔文的适者生存理论运用

16、于个体的选择。对于求解TSP 问题， 常用的选择机制有轮盘赌选择机制、随机遍历抽样法、局部选择法、截断选择法、锦标赛选择法等。遗传算法中一个较难解决的问题是如何较快地找到最优解并防止“早熟”收敛问题。为了保证遗传算法的全局收敛性，就要维持解群体的个体多样性。这种做法会明显改善遗传算法的行为，因为其增加了体在种群中的分布区域，但增加了计算时间。 交叉算子Goldberg 提出基于路径表示的部分映射交叉(partiallymapped, PMX)，首先随机地在父个体中选取两杂交点，并交换相应的段再根据该段内的城市确定部分映射。在每代父个体上先填入无冲突的城市。而对有冲突的城市分别执行这些部分映射直

17、到填人无冲突，刚可获得交叉后的两后代。由Davis 提出顺序交叉(order, OX)，它与PMX 操作非常类似。也是首先随机地在父个体中选择两杂交点，再交换杂交段，其它位置根据保持父代个体中城市的相对次序来确定。由Oliver 等提出的循环交叉(CX)，将另一个父个体作为参照以对当前父个体中的城市进行重组。先与另一父个体实现一个循环链并将对应的城市填入相应的位置，循环组成后再将另一父体的城市填入相同的位置。上述几种TSP 操作基本上考虑的是城市的位置和顺序，未考虑城市间的连Grefenstette 认为遗传算法应用与TSP，其遗传操作不仅要考虑城市间的位置，而且有必要考虑城市间的关系，城市间

18、的关系定义为边，让子个体继承父个体中边的信息设计边的遗传操作很有意义。1989 年，Whitle 等提出了一种边重组(Edge RecombinationER)交叉操作，使个体能够从父个体继承9599的边信息。ER 操作是根据继承两个父个体定义的旅程中城市间的相邻关系生成子个体。1991 年，Stark weather 等提出了一种改进的方法，在ER 操作中不再保留父个体中共同部分的序列。实验结果表明这种处理方法比随机选择的处理的性能有相当的改善。 变异算子尽管复制和交叉操作很重要,在遗传算法中是第一位的,但不能保证不会遗漏一些重要的遗传信息。在人工遗传系统中,变异是用来防止这种不可弥补的遗漏，在简单遗传算法中，变异就是某个字符串某一位的值偶然的（概率很小的）随机的改变,即在某些特定位置上简单地把1 变成0，或反之。变异是沿着个体字符空间的随机移动，当它有节制地和交叉一起使用时，它就是一种防止过度成熟而丢失重要概念的