第五章遗传算法

第5章遗传算法计算智能与人工智能（Bezdek，1992）

——计算智能取决于制造者提供的数据，而不依赖于知识；人工智能则应用知识精品。计算智能是一种智力方式的低层认知，含有知识的智能是一种中层或高层认知系统。人工智能系统：计算智能系统+知识（精品）5.1进化计算进化计算的研究起源于20世纪50年代。（如何模仿生物，进而将他们运用于复杂的优化问题，成为一个研究热点）1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。大约在同一时期：

Rechenberg和Schwefel提出了进化策略。

Fogel提出了进化规划。1967年，Bagley在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的应用。1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。

1975年是遗传算法研究的历史上十分重要的一年。Holland出版了他的著名专著《自然系统和人工系统的适应性》该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（schematatheory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把Holland的模式理论与他的计算使用结合起来。

1989Goldberg对遗传算法从理论上，方法上和应用上作了系统的总结。1990年，Koza提出了遗传程序设计（GeneticProgramming）的概念。（用于搜索解决特定问题的最适计算机程序）进化计算的三大主流板块Holland提出的遗传算法(GeneticAlgorithm)。Rechenberg和Schwefel提出的进化策略(EvolutionaryStrategies)。Fogel提出的进化规划(Evolutionaryprogramming)，又称为进化程序设计。遗传算法思想来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法(以字符串表示状态空间)。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。5.2遗传算法遗传算法的特点特点：通用鲁棒次优解、满意解遗传算法能解决的问题：优化NP完全NP难高度复杂的非线性问题遗传算法基本机理遗传算法先将搜索结构编码为字符串形式,每个字符串结构被称为个体。然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。常用的遗传算子有复制、杂交、变异和反转。遗传算法与传统优化算法的主要不同遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;遗传算法不是从单个点,而是在群体中从一个点开始搜索;遗传算法利用适应值信息,无需导数或其它辅助信息;遗传算法利用概率转移规则,而非确定性规则。遗传算法的准备工作确定表示方案;确定适应值的度量;确定控制该算法的参数和变量;确定怎样指定结果及程序运行结束的标准。基本遗传算法基本遗传算法(SimpleGeneticAlgorithm:SGA)又称为简单遗传算法，只使用选择算子、交叉算子和变异算子这三种基本的遗传算子。其遗传操作简单、容易理解，是其它遗传算法的雏形和基础。基本遗传算法的构成要素（四）1、染色体编码方法：首先必须对问题的解空间进行编码，使之能用遗传算法进行操作。较常用的是二进制编码方法，现在使用非二进制编码的也逐渐增多。

编码：将问题结构变换为位串形式编码表示的过程

解码：将位串形式编码表示变换为原问题结构的过程2、适应度函数（fitnessfunction，又称为适应值／适值函数）用来评价一个染色体的好坏。3、遗传算子选择算子(selection)：又称为复制算子。按照某种策略从父代中挑选个体进入下一代，如使用比例选择、轮盘式选择。交叉算子(crossover)：又称为杂交算子。将从群体中选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体。如使用单点一致交叉。变异算子(mutation)：按照一定的概率（一般较小），改变染色体中某些基因的值。4、运行参数N：群体大小，即群体中包含的个体的数量T：遗传算法终止的进化代数。Pc：交叉概率，一般取为0.4～0.99。Pm：变异概率，一般取为0.0001～0.1。轮盘式选择首先计算每个个体i被选中的概率然后根据概率的大小将将圆盘分为n个扇形，每个扇形的大小为2πpi。选择时转动轮盘，参考点r落到扇形i则选择个体i。......p1p2pir单点一致交叉首先以概率pc从种群中随机地选择两个个体p1、p2。在{1,2,...,l}内随机选择一个数i,作为交叉的位置，称为交叉点。然后将两个个体交叉点后面的部分交换。例如：

0110101100011001100111000110011100101100杂交操作举例[Crossover][Parents][Offspring]111001000000101111000101011010110101100110111324111001111000101000000101001010110111010110111100110101变异操作简单的变异操作过程如下:每个位置的字符变量都有一个变异概率,各位置互相独立。通过随机过程选择发生变异的位置：产生一个新结构,其中是从对应位置的字符变量的值域中随机选择的一个取值。可以同样得到。一致变异以概率pm对种群中所有个体的每一位进行变异。对于个体pi的第j位，在[0,1]的范围内随机地生成一个数r,如果r<pm,则对第j位取反，否则保持第j位不变。反转操作简单反转操作的步骤如下:从当前群体中随机选择一个结构a=s1s2…sl从中随机选择两个数i和j,并定义

i=min{i',j'},j=max{i',j'};颠倒a中位置i、j之间的部分,产生新结构基本遗传算法随机产生一个由固定长度字符串组成的初始群体;对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：计算群体中的每个个体字符串的适应值;应用下述三种操作(至少前两种)来产生新的群体:复制:把现有的个体字符串复制到新的群体中。杂交:通过遗传重组随机选择两个现有的子字符串,产生新的字符串。变异:将现有字符串中某一位的字符随机变异。把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解(或近似解)。基本遗传算法流程图GEN=0概率地选择遗传操作随机创建初始群体计算群体中每个个体的适应值i:=0显示结果结束GEN:=GEN+1是是否（转下页）i=N?GEN=T？1否概率地选择遗传操作根据适应值选择一个个体完成交叉i:=i+1i:=i+1复制个体p(r)选择（接上页）基于适应值选择两个个体把新的两个孩子加到群体中p(c)交叉变异p(m)把新的孩子加入到群体中完成变异根据适应值选择一个个体把变异后个体加入到群体中1遗传算法举例问题：求Maxf(x)=x2,x[0,31]（1）编码：x00000--11111

此时取均长为5，每个染色体{0,1}5（2）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体：编码：01101，11000，01000，10011

解码：1324819

适应度：16957664361（3）适应度评价：fitness(x)=x2（4）选择：选择概率Pi=fi/ff=1170

个体：01101110000100010011

适应度：16957664361选择概率：0.140.490.060.31选择结果：01101110001100010011（5）交叉操作：发生交叉的概率较大哪两个个体配对交叉是随机的交叉点位置的选取是随机的(单点交叉)0110101100110001101111000110011001110000(6)变异：发生变异的概率很小

(7)新群体的产生:保留上一代最优个体，一般为10%左右，至少1个用新个体取代旧个体，随机取代或择优取代。

11000，11011，11001，10011

01101，11000，01000，10011(初始种群)（8）重复上述操作：说明：GA的终止条件一般人为设置；

GA只能求次优解或满意解。分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解——择优取代有问题。遗传算法的工作步骤：（1）编码：将待解空间的解数据表示成基因型串结构数据（2）初始群体的生成：按照设定的编码方案，随机产生N个初始串结构数据，构成一个种群作为初始点开始迭代。（3）适应性评估检测：适应度函数对每个种子进行分值评定，表明种子的优劣性。（4）选择：从当前群体中选出优良的种子作为父代繁殖下一代。常用轮盘赌实现。（5）杂交：按照设定的杂交率可以得到新一代个体，新个体组合了其父辈个体的特性。（6）变异：对于选中的个体按照变异率改变串结构数据中某个串的值。利用遗传算法求解迷宫

编码采用一系列的二进制位代表可行解的染色体。每个染色体都是一组随机的二进制位。二进制位的长度在整个群体中都是一样的。以下为一个长为20的染色体的编码：

01010010100101001111

这可能是一个很差的解，也可能是一个十分完美的解，重要的是每一个单个的染色体都代表了一个可行解。

赌轮选择法：从种子群体中选择一些成员的方法，种子被选中的概率和它们的适应性分值(适应度)成正比，适应性分值越高，种子被选中的概率越大。这表明适应性强的个体被选中的概率大，同时实现了“适者生存”原则。对n个个体进行编号计算从1开始到n结束的累计概率产生0-1之间的随机数，判断在累计概率中的位置确定被随机选中的个体

杂交率：用来确定两个种子进行局部的互换以产生两个新的子代的概率。经验表明这一数值通常取为0.6–1之间是理想的。每一次从群体中选择两个种子，再随机产生一个0—1之间的数值，该数值与杂交率比较来确定是否杂交，如果数值低于杂交率，就进行杂交，然后在种子的长度上随机地选择一个位置，并把在此位置之后的所有位进行互换。例如，设给定的两个种子串码为：

10001001110010010 01010001001000011随机选择第10位，互换第10位之后的所有位，两个种子变为：

10001001101000011 01010001010010010

变异率：就是在一个种子中将位实行翻转的几率。同生物界一样，GA中变异发生的概率很低，通常取值在0.001~0.01之间。变异为新个体的产生提供了机会。按照设定的变异率在一个种子中将位实行翻转，即0变1，1变0。

问题描述：创建一个迷宫，它的右边有一入口，左边有一出口，并有一些障碍物散布在其中。在出发点放置一个虚拟的人Bob，然后要为他解决如何寻找路径的问题，使他能够找到出口，并避免与所有障碍物相碰撞。

迷宫的表示：通过一个二维整数数组，用0来表示开放的空间，1代表墙壁或障碍物。{1，1，1，1，1，1，1，1，1，1，1，1，1，1，11，0，1，0，0，0，0，0，1，1，1，0，0，0，15，0，0，0，0，0，0，0，1，1，1，0，0，0，11，0，0，0，1，1，1，0，0，0，0，0，1，0，11，1，0，0，1，1，1，0，0，0，0，0，1，0，11，0，0，0，0，1，0，0，0，0，1，1，1，0，11，0，1，1，0，0，1，0，0，0，0，0，0，0，81，0，1，1，0，0，0，1，0，0，0，0，0，0，11，1，1，1，1，1，1，1，1，1，1，1，1，1，1}

为染色体编码：每个染色体必须把Bob的每一个行动编入代码中。Bob的行动仅限为4个方向，向东，向南，向西，向北，故编码后的染色体应该就是代表这4个方向信息的一个字符串。具体如下：二进制代码十进制译码代表的方向000向北011向南102向东113向西

对于一个随机的二进制字符串，就能根据上表译出John行动时所遵循的一系列方向。如：

111110011011101110010101

它代表的基因就是：

11，11，10，01，10，11，10，11，10，01，01，01

转为十进制就是：

3，3，2，1，2，3，2，3，2，1，1，1

即John将要行走的方向是： 西，西，东，南，东，西，东，西，东，南，南，南#defineCROSSOVER_RATE0.7

杂交率#defineMUTATION_RATE

0.001

变异率#defineCHROMO_LENGTH

70

每个染色体的长度#definePOP_SIZE

140

种群里的种子数

确定群体大小的一条有用规则是将基因组的数目取为染色体长度的２倍1.UpdateFitnessScores（）;

intDiffX=abs(posX-m_iEndX);

intDiffY=abs(posY-m_iEndY);

Score=1/(1+DiffX+DiffY)Epoch（）方法2.创建一个新的群体3.用轮盘赌法选择2个父辈（parents）4.杂交操作

5.变异操作

Epoch函数将无止境地重复，直到一个染色体可以作为解，或到用户要求停止时为止Bob有时会被粘住在一个局部地区不确定地逗来逗去，如同一个喝醉了酒的人在试着寻找他的回家的路。这主要由于群体太快地收敛到一个特殊类型的染色体。这样，由于群体中的成员变得如此相似，c