《GA遗传算法高级教育》由会员分享，可在线阅读，更多相关《GA遗传算法高级教育（50页珍藏版）》请在金锄头文库上搜索。
1、遗传算法(Genetic Algorithm)Keynote ：尤志强1优质课件遗传算法与模拟退火算法一样是为解决组合优化问题而提出！ 人工智能在信息处理和解决组合爆炸方面遇到的困难越来越明显迫使寻求一种适合于大规模问题并具有自组织、自适应、自学习能力的算法，基于生活进化论的遗传算法被提出！2优质课件遗传算法遗传算法简称GA（Genetic Algorithms）是1962年由美国Michigan大学的Holland教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。 遗传算法是以达尔文的自然选择学说（适者生存）以及Mendel遗传学说（基因遗传原理）为基础发展起来的。算
2、法思路： GA将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉、变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。特点：隐含并行性和全局解空间搜索GA的应用领域：机器学习、模式识别、图像处理、神经网络、优化控制、组合优化等3优质课件遗传算法中的自然法则自然选择学说包括以下三个方面：（1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。（2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。（
3、3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。Mendel遗传学说遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对环境具有某种适应性。4优质课件遗传算法中的自然法则遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群
4、体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能得到全局最优解。5优质课件遗传算法中的相关概念遗传算法用到各种进化和遗传学得概念。以下是一些主要的概念：(1)串(String)：它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome).(2)群体(Population):个体的集合称为群体，串是群体的元素。(3)群体规模(Population Size)：在群体中个体的数量称为群体规模，又称群体的大小。(4)基因(Gene):基因是串中的元素，基因用于表示个体的特征。例如有一个串S=1011，则其中1,0,1
5、,1这四个元素分别称为基因，它们的值称为等位基因。(5)基因位置(Gene Position):一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左边向右计算，例如在串S=1011中,0的基因位是3.基因位置对应于遗传学中的地点(Locus).(6)适应度(Fitness)：表示某一个体对于环境的适应程度。 图1 解空间与生物空间的对应6优质课件遗传算法的基本流程遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有的信息来指导搜索有希望改善优化质量的状态。该算法包括5个基本要素：变量编码、初始群体的设定、适应度函数
6、的设计、遗传操作设计和参数设定。（1）编码通过编码将解空间的数据表示成遗传空间的基因型串结构数据。编码一般有二进制编码和实数编码。对于问题解X，X=（x1，x2，xn），二进制编码是把X用0,1串表示，而实数编码是把X用一向量表示，即X=（x1，x2，xn），xi是实数。编码设计应适合要解决的问题，应考虑完全性、封闭性、可扩展性和复杂性等。完全性是指分布在所有问题域的解都可能被构造出来；封闭性是指每个基因编码对应一个可接受的个体，不产生无效的个体；可扩展性是指对于具体问题，要考虑编码形式与大小影响下的解码时间；复杂性是指整体考虑基因型的结构复杂性、解码复杂性、计算复杂性等。 (2)初始群体的生
7、成在遗传算法处理流程中，继编码设计后的任务是初始群体的生成，并以此为起点一代代进化直到满足某种进化停止准则终止进化过程，初始群体也称为进化的初始代，即第一代。初始群体的个体一般可采用随机产生，一般群体可表示为Z=Xi|Xi=（xi1,xi2,.xin），i=1,2,N，即Xi是染色体或个体，xi是基因或位。若是实数编码，则xi7优质课件遗传算法的基本流程（3）适应度函数适应度函数设计是模拟自然选择，进行遗传进化操作的基础，它的评估是遗传操作的依据。适应度函数值即适应度。由于下面定义的选择概率以适应度为基础，因此适应度是非负的。方法一方法一：对于求目标函数最大值的优化问题，变换方法为：对于求目标
8、函数最大值的优化问题，变换方法为： 其中，其中，Cmin为一个适当地相对比较小的数，它可用下面方法之一来选取：为一个适当地相对比较小的数，它可用下面方法之一来选取： 预先指定的一个较小的数。预先指定的一个较小的数。 进化到当前代为止的最小目标函数值。进化到当前代为止的最小目标函数值。 当前代或最近几代群体中的最小目标函数值。当前代或最近几代群体中的最小目标函数值。 方法二方法二：对于求目标函数最小值的优化问题，变换方法为：对于求目标函数最小值的优化问题，变换方法为： 其中，其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得：是一个适当地相对比较大的数，它可用下面几种方法求得： 预
9、先指定的一个较大的数。预先指定的一个较大的数。 进化到当前代为止的最大目标函数值。进化到当前代为止的最大目标函数值。 当前代或最近几代群体中的最大目标函数值。当前代或最近几代群体中的最大目标函数值。F(X) =f(X)+Cmin if f(X)+Cmin 00 if f(X)+Cmin 0F(X) =Cmax - f(X) if f(X) Cmax0 if f(X) Cmax 8优质课件遗传算法的基本流程从群体中选择优胜的个体，淘汰劣质的个体的操作称为选择。它是建立在群体中个体适应值的基础上的，其目的是把优胜的个体遗传到下一代，选择操作的实现是根据适应度大小按照某种策略从父代中挑选个体进入中间
10、群体。选择算子设计依赖选择概率，个体Xi选择概率定义为其中fi是群体中第i个个体的适应值，N是群体的规模。当reli越大时，个体Xi被选择遗传（复制）到下一代的可能性越大。目前常用的遗传选择算子主要有以下几种：（1）基于赌轮法的选择算子(2)期望值方法9优质课件遗传算法的基本流程A、基于赌轮法的选择算子赌轮法是指根据个体被选择概率大小确定相应个体是否被遗传（复制）到下一代，其比较判别过程采用了轮盘赌的思想。设种群有n个个体X1，X2，Xn，Xi的选择概率P（Xi），每个个体对应P（Xi）表示为赌轮上的某个区域，按个体数n转动赌轮n次，根据赌轮停止点区域对应的个体进行选择，个体对应赌轮区域越大被
11、选择的机会越大，计算个体被选择的数量，这些个体将按选择的数量被复制。在计算机辅助实现过程中，模拟赌轮一般采用以下方法：根据个体的排序，按选择概率P（Xi）计算累积概率 ，则Pi（Xi）=qi-qi-1，产生n个随机数rk，对每一个随机数，判断其落在那个概率区间内，则复制相应的Xi，可以得到选择复制后的n个新一代个体。可以看到适应值越大的染色体被选中（复制）的概率也越大。B、期望值方法把每一个体的适应度与平均适应度进行比较，以确定该个体在下一代的复制数，即每个个体在下一代生存的期望数目为Ni=round(p(xi)*N)可以看到适应值越大的染色体被选中（复制）的数目也越多。，其中round(x)
12、 表示与x距离最小的整数。10优质课件遗传算法的基本流程（4）遗传操作设计交叉算子变异算子A、交叉算子交叉是把两个父代个体的部分结构加以重组而生成新个体的操作。交叉的作用，是使新的群体中的个体具有多样性，扩大解的搜索空间，使个体对应的解逐步逼近局部最优解。交叉算子设计一般要考虑三个问题：（1）交叉概率Pc的确定（2）在Pc1的情况下，判别两个个体是否要交叉。（3）对交叉的个体采用何种形式交叉。在n个个体组成的种群和给定交叉概率Pc的条件下，需要交叉的个体数为m=nXPc，每代交叉时，随机抽取个体Xi和Xj，产生（0,1）区间的随机数r，如果rPc,则表示Xi和Xj要交叉，否则不交叉，这样判别直
13、至需要交叉个体数为m时停止。11优质课件遗传算法的基本流程常见的交叉形式有以下几种：（1）单点交叉单点交叉右脚简单交叉，具体操作是：在个体基因串中随机设定一个交叉点。实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。当基因链码的长度为n时，可能有n-1个交叉点位置。单点交叉算子的具体计算过程如下：单点交叉算子的具体计算过程如下： . 对群体中的个体进行两两随机配对。 若群体大小为M，则共有 M/2 对相互 配对的个体组。 . 每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。 若染色体的长度为l ，则共有(l-1)个可能的交叉点位置。 . 对每一对相互配对的个体，
14、依设定的交叉概率pc在其交叉点处相互交换两个个 体的部分染色体，从而产生出两个新的个体。 单点交叉运算的示单点交叉运算的示例例如下所示如下所示:A；10110111 00 A：10110111 11B：00011100 11 B：00011100 0012优质课件遗传算法的基本流程常见的交叉形式：（2）两点交叉 与单点交叉相似，只是需要设置两个交叉点，然后两个染色体相互交换两点之间的部分，从而生成两 个新染色体。一个两点交叉的说明如下：父辈个体：aaa |aaaa| aaaaaa|bbbb|aaa父辈个体：bbb|bbbb|bbbbbb|aaaa|bbb（3）均匀交叉均匀交叉则是依概率交换两个
15、父辈个体基因串的每一位。其过程是：先随机的产生一个与父辈个体基因串具有同样长度的二进制串，其中0表示不交换，1表示交换。这个二进制串称为交叉模板；然后根据该模板对两个父辈基因串进行交叉，得到的两个新基因串即为后代新个体。例如：父辈个体1 ：110010111000父辈个体2 ：101011101011模板 ： 001101011100后代个体1 ：111011101000后代个体2 ：100010111011均匀交叉在交换位时不考虑其所在位置，破坏模式的概率较大。但另一方面它能搜索到一些前面基于点的交叉方法无法搜索到的模式。13优质课件遗传算法的基本流程B、变异算子变异是对群体中的个体的某些基
16、因值得变动。变异的作用是使种群中的某些个体的基因（位）产生突变引入原种群不含有的基因，形成的新个体与其他的个体有所不同。与交叉算子的作用是使对应解逐步逼近局部最优解相比，变异算子的作用是使个体对应的解逐步逼近全局最优解。变异算子设计也要考虑三个问题：（1）变异概率Pm的确定。（2）在Pm1的情况下，判别个体的某基因是否要变异。（3）对需变异的基因采用何种形式变异。若种群有n个个体，且每一个个体都有N个基因，给定的变异概率为Pm，则需要变异的基因数为M=nXNXPm，每代变异时，随机抽取个体Xi及某一基因，产生（0,1）区间的随机数r，如果r0,使得可以记为当综上所述，得到结论：在选择、交叉和变
17、异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模在后代中将以指数级增长。24优质课件标准遗传算法的理论基础积木块假设定义：具有低阶，短的定义长度以及高适应值的模式称为积木块。积木块假设：低阶、短的定义长度以及高适应值的模式（积木块）在遗传算子作用下，相互结合，能够生成高阶、长定义长度、高平均适应值得模式，可最终生成全局最优解。模式定理保证了较优的模式样本数按指数增长，从而满足了寻找最优解的必要条件，而积木块假设，则指出了遗传算法具备寻找全局最优解的能力。不过，上述结论并没有得到理论证明，所以仍然被遗憾地称为假设而不是定理，尽管有大量的实践证据支持这一假设。（只是定性认为，但很
18、可能遗传算法并不是全局收敛的，稍微改进后的遗传算法才是收敛的）隐含并行性模式定理认为遗传算法实质上是模式的运算，编码的字母表越短，算法处理一代种群时隐含处理的模式就越多。当算法采用二进制编码时，效率最高，处理规模为N的一代种群时，可同时处理o(N3)个模式。遗传算法这种以计算少量编码适应度而处理大量模式的性质称为隐并行性。25优质课件接下来我们用定理来证明遗传算法的收敛性！26优质课件遗传算法收敛性27优质课件遗传算法收敛性28优质课件遗传算法收敛性29优质课件遗传算法收敛性30优质课件遗传算法收敛性31优质课件(1)GA对问题参数编码成“染色体”后进行进化操作，而不是针对参数本身，这使得GA
19、不受函数约束条件的限制，如连续性、可导性个体。(2)GA的搜索过程是从问题解的一个集合开始，而不是从单个开始，具有隐含并行搜索特性，从而大大减小了陷入局部极小的可能。(3)GA使用的遗传操作均是随机操作，同时GA根据个体的适配值信息进行搜索，无需其他信息，如导数信息等(4)GA具有全局搜索能力，最善于搜索复杂问题和非线性问题。GA相比于传统优化算法，具有以下的特点GA算法的优越性(1)算法进行全空间并行搜索，并将搜索重点集中于性能高的部分，从而能够提高效率且不易陷入局部极小。(2)算法具有固有的并行性，通过对种群的遗传处理可处理大量的模式，并且容易并行实现。遗传算法的特点与优点32优质课件遗传
20、算法求解问题举例33优质课件例子1利用遗传算法求解区间0,31上的二次函数y=x2的最大值。y=x2 31 XY34优质课件 分析 原问题可转化为在区间0, 31中搜索能使y取最大值的点a的问题。那么，0, 31 中的点x就是个体, 函数值f(x)恰好就可以作为x的适应度，区间0, 31就是一个(解)空间 。这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。35优质课件解(1) 设定种群规模,编码染色体，产生初始种群。 将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (
21、01000), s4= 19 (10011) (2) 定义适应度函数, 取适应度函数：f (x)=x2 (3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,直到适应度最高的个体出现为止。 36优质课件 首先计算种群S1中各个体 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011) 的适应度f (si) 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 3613
22、7优质课件再计算种群S1中各个体的选择概率。选择概率的计算公式为 由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.3138优质课件 赌轮选择法s40.31s20.49s10.14s30.06 赌轮选择示意39优质课件在算法中赌轮选择法可用下面的子过程来模拟: 在0, 1区间内产生一个均匀分布的随机数r。 若rq1,则染色体x1被选中。 若qk-1rqk(2kN), 则染色体xk被选中。 其中的qi称为染色体xi (i=1, 2, , n)的积积累累概概率率, 其计算公式为
23、 40优质课件选择-复制 设从区间0, 1中产生4个随机数如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503 染色体染色体 适应度适应度选择概率选择概率积累概率积累概率选中次数选中次数s1=01101 169 0.14 0.14 1s2=11000 576 0.49 0.63 2s3=01000 64 0.06 0.69 0s4=10011 361 0.31 1.00 141优质课件于是，经复制得群体：s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19） 交叉 设
24、交叉率pc=100%，即S1中的全体染色体都参加交叉运算。 设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）42优质课件变异 设变异率pm=0.001。 这样，群体S1中共有 540.001=0.02位基因可以变异。 0.02位显然不足1位，所以本轮遗传操作不做变异。 于是，得到第二代种群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）43优质课件 第二代种群第二代种群S2中各染色体的情况中各染色体的情况
25、 染色体染色体 适应度适应度选择概率选择概率积累概率积累概率 估计的估计的选中次数选中次数s1=11001 625 0.36 0.36 1s2=01100 144 0.08 0.44 0s3=11011 729 0.41 0.85 2s4=10000 256 0.15 1.00 144优质课件 假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中个染色体都被选中，则得到群体： s1=11001（25）, s2= 01100（12） s3=11011（27）, s4= 10000（16） 做交叉运算，让s1与s2，s3与s4 分别交换后三位基因，得 s1 =11100（28）, s2 =
26、01001（9） s3 =11000（24）, s4 = 10011（19） 这一轮仍然不会发生变异。 45优质课件于是，得第三代种群S3： s1=11100（28）, s2=01001（9） s3=11000（24）, s4=10011（19） 第三代种群第三代种群S3中各染色体的情况中各染色体的情况 染色体染色体 适应度适应度选择概率选择概率积累概率积累概率 估计的估计的选中次数选中次数s1=11100 784 0.44 0.44 2s2=01001 81 0.04 0.48 0s3=11000 576 0.32 0.80 1s4=10011 361 0.20 1.00 146优质课件 设
27、这一轮的选择-复制结果为： s1=11100（28）, s2=11100（28） s3=11000（24）, s4=10011（19） 做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得 s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16） 这一轮仍然不会发生变异。47优质课件 显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。 将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。 Yy=x2 8 13 19 24 X第一代种群及其适应度y=x2 12 16 25 27 XY第二代种群及其适应度y=x2 9 19 24 28 XY第三代种群及其适应度y=x2 16 24 28 31 X第四代种群及其适应度48优质课件例子2运用遗传算法求解TSP问题49优质课件谢 谢！50优质课件
