GA遗传算法课件

遗传算法(GeneticAlgorithm)Keynote：尤志强1精选课件ppt遗传算法与模拟退火算法一样是为解决组合优化问题而提出！

人工智能在信息处理和解决组合爆炸方面遇到的困难越来越明显迫使寻求一种适合于大规模问题并具有自组织、自适应、自学习能力的算法，基于生活进化论的遗传算法被提出！2精选课件ppt遗传算法遗传算法简称GA（GeneticAlgorithms）是1962年由美国Michigan大学的Holland教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。遗传算法是以达尔文的自然选择学说（适者生存）以及Mendel遗传学说（基因遗传原理）为基础发展起来的。算法思路：GA将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉、变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。特点：隐含并行性和全局解空间搜索GA的应用领域：机器学习、模式识别、图像处理、神经网络、优化控制、组合优化等3精选课件ppt遗传算法中的自然法则自然选择学说包括以下三个方面：（1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。（2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。（3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。Mendel遗传学说遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对环境具有某种适应性。4精选课件ppt遗传算法中的自然法则遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能得到全局最优解。5精选课件ppt遗传算法中的相关概念遗传算法用到各种进化和遗传学得概念。以下是一些主要的概念：(1)串(String)：它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome).(2)群体(Population):个体的集合称为群体，串是群体的元素。(3)群体规模(PopulationSize)：在群体中个体的数量称为群体规模，又称群体的大小。(4)基因(Gene):基因是串中的元素，基因用于表示个体的特征。例如有一个串S=1011，则其中1,0,1,1这四个元素分别称为基因，它们的值称为等位基因。(5)基因位置(GenePosition):一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左边向右计算，例如在串S=1011中,0的基因位是3.基因位置对应于遗传学中的地点(Locus).(6)适应度(Fitness)：表示某一个体对于环境的适应程度。图1解空间与生物空间的对应6精选课件ppt遗传算法的基本流程遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有的信息来指导搜索有希望改善优化质量的状态。该算法包括5个基本要素：变量编码、初始群体的设定、适应度函数的设计、遗传操作设计和参数设定。（1）编码通过编码将解空间的数据表示成遗传空间的基因型串结构数据。编码一般有二进制编码和实数编码。对于问题解X，X=（x1，x2，…，xn），二进制编码是把X用0,1串表示，而实数编码是把X用一向量表示，即X=（x1，x2，…，xn），xi是实数。编码设计应适合要解决的问题，应考虑完全性、封闭性、可扩展性和复杂性等。完全性是指分布在所有问题域的解都可能被构造出来；封闭性是指每个基因编码对应一个可接受的个体，不产生无效的个体；可扩展性是指对于具体问题，要考虑编码形式与大小影响下的解码时间；复杂性是指整体考虑基因型的结构复杂性、解码复杂性、计算复杂性等。

(2)初始群体的生成在遗传算法处理流程中，继编码设计后的任务是初始群体的生成，并以此为起点一代代进化直到满足某种进化停止准则终止进化过程，初始群体也称为进化的初始代，即第一代。初始群体的个体一般可采用随机产生，一般群体可表示为Z={Xi|Xi=（xi1,xi2,…..xin）}，i=1,2,…N}，即Xi是染色体或个体，xi是基因或位。若是实数编码，则xi

7精选课件ppt遗传算法的基本流程（3）适应度函数适应度函数设计是模拟自然选择，进行遗传进化操作的基础，它的评估是遗传操作的依据。适应度函数值即适应度。由于下面定义的选择概率以适应度为基础，因此适应度是非负的。方法一：对于求目标函数最大值的优化问题，变换方法为：

其中，Cmin为一个适当地相对比较小的数，它可用下面方法之一来选取：

•预先指定的一个较小的数。

•进化到当前代为止的最小目标函数值。

•当前代或最近几代群体中的最小目标函数值。

方法二：对于求目标函数最小值的优化问题，变换方法为：其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得：

•预先指定的一个较大的数。

•进化到当前代为止的最大目标函数值。

•当前代或最近几代群体中的最大目标函数值。F(X)=f(X)+Cminiff(X)+Cmin>00

iff(X)+Cmin≤0F(X)=Cmax-f(X)

iff(X)

Cmax0

iff(X)

Cmax8精选课件ppt遗传算法的基本流程从群体中选择优胜的个体，淘汰劣质的个体的操作称为选择。它是建立在群体中个体适应值的基础上的，其目的是把优胜的个体遗传到下一代，选择操作的实现是根据适应度大小按照某种策略从父代中挑选个体进入中间群体。选择算子设计依赖选择概率，个体Xi选择概率定义为其中fi是群体中第i个个体的适应值，N是群体的规模。当reli越大时，个体Xi被选择遗传（复制）到下一代的可能性越大。目前常用的遗传选择算子主要有以下几种：（1）基于赌轮法的选择算子(2)期望值方法9精选课件ppt遗传算法的基本流程A、基于赌轮法的选择算子赌轮法是指根据个体被选择概率大小确定相应个体是否被遗传（复制）到下一代，其比较判别过程采用了轮盘赌的思想。设种群有n个个体X1，X2，…，Xn，Xi的选择概率P（Xi），每个个体对应P（Xi）表示为赌轮上的某个区域，按个体数n转动赌轮n次，根据赌轮停止点区域对应的个体进行选择，个体对应赌轮区域越大被选择的机会越大，计算个体被选择的数量，这些个体将按选择的数量被复制。在计算机辅助实现过程中，模拟赌轮一般采用以下方法：根据个体的排序，按选择概率P（Xi）计算累积概率

，则Pi（Xi）=qi-qi-1，产生n个随机数rk，对每一个随机数，判断其落在那个概率区间内，则复制相应的Xi，可以得到选择复制后的n个新一代个体。可以看到适应值越大的染色体被选中（复制）的概率也越大。B、期望值方法把每一个体的适应度与平均适应度进行比较，以确定该个体在下一代的复制数，即每个个体在下一代生存的期望数目为Ni=round(p(xi)*N)可以看到适应值越大的染色体被选中（复制）的数目也越多。，其中round(x)表示与x距离最小的整数。10精选课件ppt遗传算法的基本流程（4）遗传操作设计交叉算子变异算子A、交叉算子交叉是把两个父代个体的部分结构加以重组而生成新个体的操作。交叉的作用，是使新的群体中的个体具有多样性，扩大解的搜索空间，使个体对应的解逐步逼近局部最优解。交叉算子设计一般要考虑三个问题：（1）交叉概率Pc的确定（2）在Pc<1的情况下，判别两个个体是否要交叉。（3）对交叉的个体采用何种形式交叉。在n个个体组成的种群和给定交叉概率Pc的条件下，需要交叉的个体数为m=nXPc，每代交叉时，随机抽取个体Xi和Xj，产生（0,1）区间的随机数r，如果r<Pc,则表示Xi和Xj要交叉，否则不交叉，这样判别直至需要交叉个体数为m时停止。11精选课件ppt遗传算法的基本流程常见的交叉形式有以下几种：（1）单点交叉单点交叉右脚简单交叉，具体操作是：在个体基因串中随机设定一个交叉点。实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。当基因链码的长度为n时，可能有n-1个交叉点位置。单点交叉算子的具体计算过程如下：

Ⅰ.对群体中的个体进行两两随机配对。若群体大小为M，则共有[M/2]对相互配对的个体组。

Ⅱ.每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为l

，则共有(l-1)个可能的交叉点位置。

Ⅲ.对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。

单点交叉运算的示例如下所示:A；1011011100A’：1011011111B：0001110011B’：000111000012精选课件ppt遗传算法的基本流程常见的交叉形式：（2）两点交叉

与单点交叉相似，只是需要设置两个交叉点，然后两个染色体相互交换两点之间的部分，从而生成两

个新染色体。一个两点交叉的说明如下：父辈个体：aaa|aaaa|aaaaaa|bbbb|aaa父辈个体：bbb|bbbb|bbbbbb|aaaa|bbb（3）均匀交叉均匀交叉则是依概率交换两个父辈个体基因串的每一位。其过程是：先随机的产生一个与父辈个体基因串具有同样长度的二进制串，其中0表示不交换，1表示交换。这个二进制串称为交叉模板；然后根据该模板对两个父辈基因串进行交叉，得到的两个新基因串即为后代新个体。例如：父辈个体1：110010111000父辈个体2：1模板：0后代个体1：111011101000后代个体2：1均匀交叉在交换位时不考虑其所在位置，破坏模式的概率较大。但另一方面它能搜索到一些前面基于点的交叉方法无法搜索到的模式。13精选课件ppt遗传算法的基本流程B、变异算子变异是对群体中的个体的某些基因值得变动。变异的作用是使种群中的某些个体的基因（位）产生突变引入原种群不含有的基因，形成的新个体与其他的个体有所不同。与交叉算子的作用是使对应解逐步逼近局部最优解相比，变异算子的作用是使个体对应的解逐步逼近全局最优解。变异算子设计也要考虑三个问题：（1）变异概率Pm的确定。（2）在Pm<1的情况下，判别个体的某基因是否要变异。（3）对需变异的基因采用何种形式变异。若种群有n个个体，且每一个个体都有N个基因，给定的变异概率为Pm，则需要变异的基因数为M=nXNXPm，每代变异时，随机抽取个体Xi及某一基因，产生（0,1）区间的随机数r，如果r<Pc,则表示要变异，，否则不变异，这样判别直至需要变异的基因数为M时停止，一般地，一个个体变异的基因数控制为最多一个是较合理的。14精选课件ppt遗传算法的基本流程常用的变异形式：（1）基本变异算子基本变异算子是针对二值基因链码而言。其具体操作是：对群体中基因链码随机挑选C个基因位置并对这些基因位置的基因值以变异概率P取反，即0变成1,1变成0。当C=1时，表示一个基因值取反。基本位变异运算的示例如下所示：

A：1010101010A’：1010001010

（2）均匀变异算子该变异方法是针对实数编码方式的。设v=（v1,v2,...,vm）是群体中体，Z=(z1,z2,…,zm)是变异产生的后代。均匀性变异则是先在个体v中随机的选择一个分量vk，然后，在一个定义的区间[ak,bk]中均匀随机取一个数Vk1代替vk以得到Z，即Z=（v1,v2,…,vk1,…,vm）。（3）自适应变异算子该算子与基本变异算子的操作相似，两者之间的区别就是使用自适应变异算子时变异率不是固定不变而是随着群体中个体多样性的程度自适应调整。基本位变异变异点15精选课件ppt基本遗传算法的运行参数M：群体大小，即群体中所含个体的数量，一般取为20~100；G：遗传算法的终止进化代数，一般取为100~500；Pc：交叉概率，一般取为0.4~0.99；也可以采取办法：在指定交叉形式下，若有Pc0，使进化代数最小达到终止条件，则交叉概率Pc0最优。Pm：变异概率，一般取为0.01~0.001。也可以采取办法：在指定变异形式下，若有Pm0，使进化代数最小达到终止条件，则变异概率Pm0最优。遗传算法的基本流程16精选课件ppt1、复制操作通常采用比例复制，即复制概率正比于个体的适配值，如此意味着适配值高的个体在下一代中复制自身的概率大，从而提高了种群的平均适配值。2、交叉操作通过交换两个父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，从而有助于产生优良个体3、变异操作通过随机改变个体中某些基因二产生新个体，有助于增加种群的多样性，避免过早收敛遗传算法的基本流程遗传操作总结17精选课件ppt遗传算法的流程图开始Gen=0编码随机产生M个初始个体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子j=0j=0j=0根据适应度选择复制个体选择两个交叉个体选择个体变异点执行变异执行交叉执行复制将复制的个体添入新群体中将交叉后的两个新个体添入新群体中将变异后的个体添入新群体中j=j+1j=j+2j=j+1

j=M?

j=pc·M?

j=pm·L·M?Gen=Gen+1输出结果终止YNYYYNNNpcpm18精选课件ppt遗传算法伪代码ALOGRITHMGA(i):Begin

t:=0;InitializeP(t);P(t)={X1(t),X2(t),…,Xn(t)}EvaluateP(t);

f(P(t))={f(X1(t)),f(X2(t)),…,f(Xn(t))}while(notterminationcondition)do{Create

BP(t);//繁殖池

PC(t)=crossover{BP(t)};Pm(t)=mutation{BP(t)};Evaluate[PC(t)]

and[Pm(t)]

;P(t+1)=select[PC(t)∪Pm(t)∪Q];

t:=t+1printXbest,f(Xbest);}printXbest,f(Xbest);End19精选课件ppt标准遗传算法的理论基础模式定理和隐含并行性是holland为解释基于二进制编码的标准遗传算法(SGA)的功效而建立的，是最早对遗传算法全局收敛性作定性分析的理论基础，它说明了适配值高、长度短、阶数低的图式在后代中至少以指数增长包含该图式的个体数。（1）模式定义基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。例：以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即{00001,10001}；又如模式*1**0描述了所有在位置2为“1”及位置5为“0”的字符串，即{01000,01010,01100,01110,11000,11010,11100,11110}；而模式01010描述了只有一个串的集合，即{01010}。模式的概念提供了一种简单的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。

引入模式概念，使不同串之间通过模式而相互联系。通过分析模式在遗传操作下的变化，可以了解什么性质被延续，什么性质被丢弃。从而把握遗传算法的实质。（2）模式阶定义模式H中确定位置的个数称作该模式的模式阶（SchemaOrder），记作O(H).例：模式011*1*的阶数为4，而模式0*****的阶数为1当一个模式的阶越高时，其所代表的集合中的个体数就越少，因而确定性越高。但是，模式阶并不能反映模式的所有性质。需要再引入定义距概念20精选课件ppt标准遗传算法的理论基础（3）模式定义距的定义模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作例：模式011*1*的定义距为4，而模式0*****的定义距为0。

模式定理设H是任一个模式，P(g)={x1(g),x2(g),…,xn(g)}是第g代群体，xi(g)(i=1,2,…,n)是该群体中所有个体，S(H，g)表示在群体P(g)中与模式H相匹配的个体的集合，m(H,g)表示集合S(H,g)中的个体的数目，f(H,g)表示S(H,g)中个体的平均适应度。P(g)中个体的平均适应度为21精选课件ppt标准遗传算法的理论基础模式定理：设遗传算法的交叉概率和变异概率分别为Pc和Pm，l为个体基因链码的长度，则有模式定理反映了子代个体模式数目与父代个体适应度以及交叉、变异过程的关系：（1）子代个体模式数目依赖父代个体适应度的关系假设一代中群体大小为n，且群体中的个体两两互不相同，则S(H,g)中所有个体被选择的总概率为因而在第g+1代中模式H的样本数m(H,g+1)为可见模式的增长或减少依赖于模式的平均适应度与群体平均适应度之比，那些平均适应度高于群体平均适应度的模式将在下一代中得以增长；而那些平均适应度低于群体平均适应度的模式将在下一代中减少。22精选课件ppt标准遗传算法的理论基础（2）子代个体模式数目依赖父代个体交叉作用的关系对于模式H来说，只有当交叉点落在定义距之外才能使该模式生存。在简单交叉（单点交叉）下H被破坏的概率。小于等于表示：因为虽然有时交叉点落在定义距之内，但当用于交叉的双亲的基因链码在模式H的确定位置上相同时，所生成的后代个体仍具有模式H。由于交叉概率为Pc，因此，H生存的概率为这样，在考虑了选择和交叉算子之后，有23精选课件ppt标准遗传算法的理论基础（3）子代个体模式数目依赖父代个体变异作用的关系模式在变异操作中的变化：由于个体基因链码在某一位置发生改变的概率为Pm，则该个体该位置不变的概率为1-Pm。而模式H在变异算子作用下若要不受破坏，则其中所有的确定位置必须保持不变，因此模式H保持不变的概率为。当Pm《1时，模式H在变异算子作用下的生存概率为

综上所述，模式H在选择、交叉和变异的共同作用下，其后代个体的数目为忽略可以得到如果存在常数c>0,使得可以记为当

综上所述，得到结论：在选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模在后代中将以指数级增长。24精选课件ppt标准遗传算法的理论基础积木块假设定义：具有低阶，短的定义长度以及高适应值的模式称为积木块。积木块假设：低阶、短的定义长度以及高适应值的模式（积木块）在遗传算子作用下，相互结合，能够生成高阶、长定义长度、高平均适应值得模式，可最终生成全局最优解。模式定理保证了较优的模式样本数按指数增长，从而满足了寻找最优解的必要条件，而积木块假设，则指出了遗传算法具备寻找全局最优解的能力。不过，上述结论并没有得到理论证明，所以仍然被遗憾地称为假设而不是定理，尽管有大量的实践证据支持这一假设。（只是定性认为，但很可能遗传算法并不是全局收敛的，稍微改进后的遗传算法才是收敛的）隐含并行性模式定理认为遗传算法实质上是模式的运算，编码的字母表越短，算法处理一代种群时隐含处理的模式就越多。当算法采用二进制编码时，效率最高，处理规模为N的一代种群时，可同时处理o(N^3)个模式。遗传算法这种以计算少量编码适应度而处理大量模式的性质称为隐并行性。25精选课件ppt接下来我们用定理来证明遗传算法的收敛性！26精选课件ppt遗传算法收敛性27精选课件ppt遗传算法收敛性28精选课件ppt遗传算法收敛性29精选课件ppt遗传算法收敛性30精选课件ppt遗传算法收敛性31精选课件ppt(1)GA对问题参数编码成“染色体”后进行进化操作，而不是针对参数本身，这使得GA不受函数约束条件的限制，如连续性、可导性个体。(2)GA的搜索过程是从问题解的一个集合开始，而不是从单个开始，具有隐含并行搜索特性，从而大大减小了陷入局部极小的可能。(3)GA使用的遗传操作均是随机操作，同时GA根据个体的适配值信息进行搜索，无需其他信息，如导数信息等(4)GA具有全局搜索能力，最善于搜索复杂问题和非线性问题。GA相比于传统优化算法，具有以下的特点GA算法的优越性(1)算法进行全空间并行搜索，并将搜索重点集中于性能高的部分，从而能够提高效率且不易陷入局部极小。(2)算法具有固有的并行性，通过对种群的遗传处理可处理大量的模式，并且容易并行实现。遗传算法的特点与优点32精选课件ppt遗传算法求解问题举例33精选课件ppt例子1利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。

y=x2

31

XY34精选课件ppt

分析

原问题可转化为在区间［0,31］中搜索能使y取最大值的点a的问题。那么，［0,31］中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间［0,31］就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。35精选课件ppt

解

(1)

设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定义适应度函数,

取适应度函数：f(x)=x2

(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体出现为止。

36精选课件ppt

首先计算种群S1中各个体

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)

的适应度f(si)

容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=36137精选课件ppt再计算种群S1中各个体的选择概率。选择概率的计算公式为

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.3138精选课件ppt●赌轮选择法s40.31s20.49s10.14s30.06

赌轮选择示意39精选课件ppt

在算法中赌轮选择法可用下面的子过程来模拟:①在［0,1］区间内产生一个均匀分布的随机数r。②若r≤q1,则染色体x1被选中。③若qk-1<r≤qk(2≤k≤N),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,…,n)的积累概率,其计算公式为40精选课件ppt选择-复制

设从区间［0,1］中产生4个随机数如下:

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

41精选课件ppt于是，经复制得群体：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）交叉设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1’与s2’配对，s3’与s4’配对。分别交换后两位基因，得新染色体：

s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

42精选课件ppt变异设变异率pm=0.001。这样，群体S1中共有

5×4×0.001=0.02位基因可以变异。

0.02位显然不足1位，所以本轮遗传操作不做变异。

于是，得到第二代种群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27