第五章遗传算法

1、l计算智能与人工智能（计算智能与人工智能（Bezdek，1992） 计算智能取决于制造者提供的数据，而不依赖于知识；计算智能取决于制造者提供的数据，而不依赖于知识；人工智能则应用知识精品。人工智能则应用知识精品。l计算智能是一种智力方式的低层认知，含有知识的智计算智能是一种智力方式的低层认知，含有知识的智能是一种中层或高层认知系统。能是一种中层或高层认知系统。l人工智能系统：计算智能系统人工智能系统：计算智能系统+知识（精品）知识（精品）l进化计算的研究起源于进化计算的研究起源于20世纪世纪50年代。（如何模仿生年代。（如何模仿生物，进而将他们运用于复杂的优化问题，成为一个研物，进而将他们运用

2、于复杂的优化问题，成为一个研究热点）究热点）l1965年，年，Holland首次提出了人工遗传操作的重要性，首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。并把这些应用于自然系统和人工系统中。l大约在同一时期：大约在同一时期： Rechenberg和和Schwefel提出了进化策略。提出了进化策略。 Fogel提出了进化规划。提出了进化规划。l 19671967年，年，BagleyBagley在他的论文中首次提出了遗传算在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的法这一术语，并讨论了遗传算法在自动博弈中的应用。应用。l 19701970年，年，Ca

3、vicchioCavicchio把遗传算法应用于模式识别中。把遗传算法应用于模式识别中。l 第一个把遗传算法应用于函数优化的是第一个把遗传算法应用于函数优化的是HollstienHollstien。 l 19751975年是遗传算法研究的历史上十分重要的一年。年是遗传算法研究的历史上十分重要的一年。HollandHolland出出版了他的著名专著版了他的著名专著自然系统和人工系统的适应性自然系统和人工系统的适应性该书系统该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（理论研究和发展极为重要的模

4、式理论（schemata theoryschemata theory），），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。性。l 同年，同年，DeJongDeJong完成了他的重要论文完成了他的重要论文遗传自适应系统的行为分遗传自适应系统的行为分析析。他在该论文中所做的研究工作可看作是遗传算法发展过。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把程中的一个里程碑，这是因为他把HollandHolland的模式理论与他的的模式理论与他的计算使用结合起来。计算使用结合起来。 l 1989 Goldbe

5、rg1989 Goldberg对遗传算法从理论上，方法上和应对遗传算法从理论上，方法上和应用上作了系统的总结用上作了系统的总结。l 19901990年，年，KozaKoza提出了遗传程序设计（提出了遗传程序设计（Genetic Genetic ProgrammingProgramming）的概念。（用于搜索解决特定问题）的概念。（用于搜索解决特定问题的最适计算机程序）的最适计算机程序）lHolland提出的遗传算法提出的遗传算法(Genetic Algorithm)。lRechenberg和和Schwefel提出的进化策略提出的进化策略(Evolutionary Strategies)。lFo

6、gel提出的进化规划提出的进化规划(Evolutionary programming)， 又称为进化程序设计。又称为进化程序设计。l 遗传算法思想来源于生物进化过程遗传算法思想来源于生物进化过程, 它是基它是基于进化过程中的于进化过程中的信息遗传机制信息遗传机制和优胜劣汰和优胜劣汰的的自然选择原则自然选择原则的搜索算法的搜索算法(以字符串表示以字符串表示状态空间状态空间)。遗传算法用概率搜索过程在该。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。状态空间中搜索，产生新的样本。特点：特点：通用通用鲁棒鲁棒次优解、满意解次优解、满意解遗传算法能解决的问题：遗传算法能解决的问题：优化优化N

7、P完全完全NP难难高度复杂的非线性问题高度复杂的非线性问题l 遗传算法先将搜索结构编码为字符串形式遗传算法先将搜索结构编码为字符串形式, 每个字符每个字符串结构被称为串结构被称为个体个体。l 然后对一组字符串结构然后对一组字符串结构(被称为一个群体被称为一个群体)进行循环操进行循环操作。每次循环被称作作。每次循环被称作一代一代,包括一个保存字符串中较优包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息结构的过程和一个有结构的、随机的字符串间的信息交换过程。交换过程。l 类似于自然进化，遗传算法通过作用于染色体上的基类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色

8、体来求解问题。因寻找好的染色体来求解问题。l 在遗传算法中，位字符串扮演染色体的作用，单在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的适应度，取消低适应度的个体，选择高适应度的个体参加操作。个体参加操作。l 常用的遗传算子有复制、杂交、变异和反转。常用的遗传算子有复制、杂交、变异和反转。 遗传算法不是直接作用在参变量集上遗传算法不是直接作用在参变量集上, 而是利用参变而是利用参变量集的某种编

9、码量集的某种编码; 遗传算法不是从单个点遗传算法不是从单个点, 而是在群体中从一个点开始而是在群体中从一个点开始搜索搜索; 遗传算法利用适应值信息遗传算法利用适应值信息, 无需导数或其它辅助信息无需导数或其它辅助信息; 遗传算法利用概率转移规则遗传算法利用概率转移规则, 而非确定性规则。而非确定性规则。 确定表示方案确定表示方案; 确定适应值的度量确定适应值的度量; 确定控制该算法的参数和变量确定控制该算法的参数和变量; 确定怎样指定结果及程序运行结束的标准。确定怎样指定结果及程序运行结束的标准。基本遗传算法基本遗传算法(Simple Genetic Algorithm:SGA)又又称为简单遗

10、传算法，只使用称为简单遗传算法，只使用选择算子、交叉算子选择算子、交叉算子和变异算子和变异算子这三种基本的遗传算子。其遗传操作这三种基本的遗传算子。其遗传操作简单、容易理解，是其它遗传算法的雏形和基础。简单、容易理解，是其它遗传算法的雏形和基础。1、染色体编码方法：首先必须对问题的解空间进行、染色体编码方法：首先必须对问题的解空间进行编码，使之能用遗传算法进行操作。较常用的是二进编码，使之能用遗传算法进行操作。较常用的是二进制编码方法，现在使用非二进制编码的也逐渐增多。制编码方法，现在使用非二进制编码的也逐渐增多。 编码编码：将问题结构变换为位串形式编码表示的过程：将问题结构变换为位串形式编码

11、表示的过程 解码解码：将位串形式编码表示变换为原问题结构的过程：将位串形式编码表示变换为原问题结构的过程2、适应度函数（、适应度函数（fitness function，又称为适应值适，又称为适应值适值函数）用来评价一个染色体的好坏。值函数）用来评价一个染色体的好坏。3、遗传算子、遗传算子选择算子选择算子(selection) ：又称为复制算子。按照某种策：又称为复制算子。按照某种策略从父代中挑选个体进入下一代，如使用比例选择、略从父代中挑选个体进入下一代，如使用比例选择、轮盘式选择。轮盘式选择。交叉算子交叉算子(crossover)：又称为杂交算子。将从群体中：又称为杂交算子。将从群体中选择的

12、两个个体，按照某种策略使两个个体相互交换选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体。如使用单点一部分染色体，从而形成两个新的个体。如使用单点一致交叉。致交叉。变异算子变异算子(mutation)：按照一定的概率（一般较小），：按照一定的概率（一般较小），改变染色体中某些基因的值。改变染色体中某些基因的值。4、运行参数、运行参数N：群体大小，即群体中包含的个体的数量：群体大小，即群体中包含的个体的数量T：遗传算法终止的进化代数。：遗传算法终止的进化代数。Pc：交叉概率，一般取为：交叉概率，一般取为 0.40.99。Pm：变异概率，一般取为：变异概率，一般取为

13、0.00010.1 。l首先计算每个个体首先计算每个个体 i 被选中的概被选中的概率率l然后根据概率的大小将将圆盘分然后根据概率的大小将将圆盘分为为 n个扇形，每个扇形的大小为个扇形，每个扇形的大小为 2pi。选择时转动轮盘，参考点。选择时转动轮盘，参考点r落到扇形落到扇形i则选择个体则选择个体i 。njijfifp1)()(.p1p2pirl首先以概率首先以概率pc从种群中随机地选择两个个体从种群中随机地选择两个个体p1、p2。在在1, 2, . . . ,l内随机选择一个数内随机选择一个数i,作为交叉的位置，作为交叉的位置，称为交叉点。然后将两个个体交叉点后面的部分交称为交叉点。然后将两个

14、个体交叉点后面的部分交换。换。l例如：例如： 0110 101100 0110 011001 1100 011001 1100 101100CrossoverParentsOffspring111001000000101111000101011010110101100110111324111001111000101000000101001010110111010110111100110101简单的变异操作过程如下简单的变异操作过程如下:l 每个位置的字符变量都有一个变异概率每个位置的字符变量都有一个变异概率, 各位置互相各位置互相独立。通过随机过程选择发生变异的位置：独立。通过随机过程选择发生

15、变异的位置：l 产生一个新结构产生一个新结构 , 其中其中 是从对应位置是从对应位置 的字符变量的值域中随机选择的一的字符变量的值域中随机选择的一个取值。个取值。 可以同样得到。可以同样得到。lxxx,.,21txxxxxxssssssssa.111112221111xs1xkxxss,.,2l 以概率以概率pm对种群中所有个体的每一位进行变异。对种群中所有个体的每一位进行变异。l 对于个体对于个体pi的第的第j位，在位，在0,1的范围内随机地生的范围内随机地生成一个数成一个数r, 如果如果 r pm , 则对第则对第j位取反，否则位取反，否则保持第保持第j位不变。位不变。简单反转操作的步骤如

16、下简单反转操作的步骤如下: 从当前群体中随机选择一个结构从当前群体中随机选择一个结构a=s1s2sl 从中随机选择两个数从中随机选择两个数i 和和j , 并定义并定义 i = mini,j, j=maxi,j;1) 颠倒颠倒a中位置中位置i、j之间的部分之间的部分, 产生新结构产生新结构ljijjissssssss.12121 随机产生一个由固定长度字符串组成的初始群体随机产生一个由固定长度字符串组成的初始群体; 对于字符串群体，迭代地执行下述步骤，直到选种标对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：准被满足为止： 计算群体中的每个个体字符串的适应值计算群体中的每个个体字符串

17、的适应值; 应用下述三种操作应用下述三种操作(至少前两种至少前两种)来产生新的群体来产生新的群体:复制复制: 把现有的个体字符串复制到新的群体中。把现有的个体字符串复制到新的群体中。杂交杂交: 通过遗传重组随机选择两个现有的子字符串通过遗传重组随机选择两个现有的子字符串, 产产生新的字符串。生新的字符串。变异变异: 将现有字符串中某一位的字符随机变异将现有字符串中某一位的字符随机变异。 把在后代中出现的最高适应值的个体字符串指定为遗把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解传算法运行的结果。这一结果可以是问题的解(或近或近似解似解)。GEN=0概率地

18、选择遗传操作概率地选择遗传操作随机创建初始群体随机创建初始群体计算群体中每个个体的适应值计算群体中每个个体的适应值i:=0显示结果显示结果结束结束GEN:=GEN+1是是是是否否（转下页）（转下页）i=N?GEN=T？1否否概率地选择遗传操作概率地选择遗传操作根据适应值选根据适应值选择一个个体择一个个体完成交叉完成交叉i:=i+1i:=i+1复制个体复制个体p(r)选择选择（接上页）（接上页）基于适应值选基于适应值选择两个个体择两个个体把新的两个孩把新的两个孩子加到群体中子加到群体中p(c)交叉交叉变异变异p(m)把新的孩子加把新的孩子加入到群体中入到群体中完成变异完成变异根据适应值选根据适应

19、值选择一个个体择一个个体把变异后个体把变异后个体加入到群体中加入到群体中1问题：求问题：求Max f(x)=x2, x 0,31（1）编码：）编码： x 00000-11111 此时取均长为此时取均长为5，每个染色体，每个染色体0,15（2）初始群体生成：群体大小视情况而定，此处设置为）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体：，随机产生四个个体： 编码：编码： 01101，11000，01000，10011 解码：解码： 13 24 8 19 适应度：适应度： 169 576 64 361（3）适应度评价：）适应度评价：fitness(x) =x2（4）选择：选择概率

20、）选择：选择概率Pi=fi/ f f =1170 个体：个体： 01101 11000 01000 10011 适应度：适应度： 169 576 64 361选择概率：选择概率：0.14 0.49 0.06 0.31选择结果：选择结果：01101 11000 11000 10011（5）交叉操作：发生交叉的概率较大）交叉操作：发生交叉的概率较大 哪两个个体配对交叉是随机的哪两个个体配对交叉是随机的 交叉点位置的选取是随机的交叉点位置的选取是随机的(单点交叉单点交叉) 0110 1 0110 0 11 000 11 011 1100 0 1100 1 10 011 10 000 (6) 变异：发

21、生变异的概率很小变异：发生变异的概率很小 (7) 新群体的产生新群体的产生: 保留上一代最优个体，一般为保留上一代最优个体，一般为10%左右，至少左右，至少1个用新个体取代旧个体，随机取代或择个用新个体取代旧个体，随机取代或择优取代。优取代。 11000，11011，11001，10011 01101，11000，01000，10011(初始种群初始种群).9.0,8.0cP0001. 0mP（8）重复上述操作：）重复上述操作：说明：说明：GA的终止条件一般人为设置；的终止条件一般人为设置； GA只能求次优解或满意解。只能求次优解或满意解。分析：按第二代新群体进行遗传操作，若无变异，永分析：按

22、第二代新群体进行遗传操作，若无变异，永远也找不到最优解远也找不到最优解择优取代有问题。择优取代有问题。 利用遗传算法求解迷宫利用遗传算法求解迷宫 1，1，1，1，1，1，1，1，1，1，1，1，1，1，1 1，0，1，0，0，0，0，0，1，1，1，0，0，0，1 5，0，0，0，0，0，0，0，1，1，1，0，0，0，1 1，0，0，0，1，1，1，0，0，0，0，0，1，0，1 1，1，0，0，1，1，1，0，0，0，0，0，1，0，1 1，0，0，0，0，1，0，0，0，0，1，1，1，0，1 1，0，1，1，0，0，1，0，0，0，0，0，0，0，8 1，0，1，1，0，0，0，1，0

23、，0，0，0，0，0，1 1，1，1，1，1，1，1，1，1，1，1，1，1，1，1 二进制代码二进制代码十进制译码十进制译码代表的方向代表的方向00000 0向北向北01011 1向南向南10102 2向东向东11113 3向西向西l 进化策略模仿自然进化原理作为一种求解参数优化问进化策略模仿自然进化原理作为一种求解参数优化问题的方法。最简单的实现方法题的方法。最简单的实现方法: 定义的问题是寻找定义的问题是寻找n维的实数向量维的实数向量x, 它使函数它使函数: F(x):RnR (2) 双亲向量的初始群体从每维可行范围内随机选择。双亲向量的初始群体从每维可行范围内随机选择。(3) 子孙向量的创建是从每个双亲向量加上零均方差高子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量。斯随机变量。(4) 根据最小误差选择向量为下一代新的双亲。根据最小误