遗传算法课堂PPT

《遗传算法课堂PPT》由会员分享，可在线阅读，更多相关《遗传算法课堂PPT（71页珍藏版）》请在装配图网上搜索。

1、1遗传算法原理与应用遗传算法原理与应用赵 鹏21.1.遗传算法起源遗传算法起源 遗传算法是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。一、基本原理一、基本原理 3生物进化循环图生物进化循环图4生物遗传概念在遗传算法中的对应关系生物遗传概念在遗传算法中的对应关系生物遗传概念遗传算法中的作用适者生存在算法停止时，最优目标值的解有最大的可能被保留个体(individual)解染色体(chromosome)解的编码（字符串，向量等）基因(gene)解中每一分量的特征（如各分量的值）适应性(fitne

2、ss)适应函数值群体(population)选定的一组解（其中解的个数为群体的规模）种群(reproduction)根据适应函数值选取的一组解交配(crossover)通过交配原则产生一组新解的过程变异(mutation)编码的某一个分量发生变化的过程5遗传算法的主要特征：遗传算法的主要特征：进化发生在解的编码上，这些编码按生物学的术语称为染色体。由于对解进行了编码，优化问题的一切性质都通过编码来研究。编码和解码是遗传算法的一个主题。自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法中，通过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平均数的后代。当染色体结合时，双亲的遗传

3、基因的结合使得子女保持父母的特征。当染色体结合后，随机的变异会造成子代同父代的不同。6遗传算法主要处理步骤遗传算法主要处理步骤 首先是对优化问题的解进行编码，称一个解的编码为一个染色体，组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和利于之后遗传算法中的计算。第二是适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。当适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体组成种群，形成一个可以繁衍下一代的群体。第三是染色体的结合。双亲的遗传基因结合是通过编码之间的交配达到下一代的产生。新一代的产生是一

4、个生殖过程，它产生了一个新解。最后是变异。新解产生过程中可能发生基因变异，变异使某些解的编码发生变化，使解有更大的遍历性。72、基本遗传算法 基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数8函数优化示例 求下列一元函数的最大值：0.2)10sin()(xxxf GA是通过某种编码机制把对象抽象为由特定符号按一

5、定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。编码 9SGA对于本例的编码 由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。又因为221 3106 222，所以本例的二进制编码长度至少需要需要2222位位，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b0）。10几个术语 基因型：1000101110110101000111 表现型：0.637197 编码解码个体（染色体）基因11初始种群 SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的

6、数量称为种群规模。适应度函数 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。12选择算子选择算子 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。13轮盘赌选择示意s40.31s20.49s10.14s30.06轮盘赌选择法14轮盘赌选择方法 轮盘赌

7、选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：niiiiFFP1/15轮盘赌选择方法的实现步骤（1）计算群体中所有个体的适应度函数值（需要解码）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。16交叉算子 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉

8、运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。17单点交叉运算 交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉点交叉点18变异算子 所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互

9、配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。19基本位变异算子 基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。20基本位变异算子的执行过程 变异前：000001110000000010000变异后：000001110001000010000变异点变异点21运行参数（1）M ：种群规模（2）T ：遗传运算的终止进化代数（3）Pc ：交叉概率（4）Pm：变异概率 初始种群

10、初始种群23遗传算法应用举例 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。y=x2 31 XY24 分析 原问题可转化为在区间0,31中搜索能使y取最大值的点a的问题。那么，0,31 中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间0,31就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。25解(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函

11、数,取适应度函数：f(x)=x2 26(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。27 首先计算种群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=36128再计算种群S1中各个体的选择概率。NjjiixfxfxP1)()()(选择概率的计算公式为 由此可求得 P(s1)=P(13)=

12、0.14 P(s2)=P(24)=0.49 P(s3)=P(8)=0.06 P(s4)=P(19)=0.3129 赌轮选择示意s40.31s20.49s10.14s30.06 赌轮选择法30在算法中赌轮选择法可用下面的子过程来模拟:在0,1区间内产生一个均匀分布的随机数r。若rq1,则染色体x1被选中。若qk-1rqk(2kN),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,n)的积累概率积累概率,其计算公式为 ijjixPq1)(31选择-复制 设从区间0,1中产生4个随机数如下:r1=0.450126,r2=0.110347 r3=0.572496,r4=0.98503 染色体

13、 适应度选择概率积累概率选中次数选中次数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 132于是，经复制得群体：s1=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）33交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）34变异

14、设变异率pm=0.001。这样，群体S1中共有 540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。35 于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）36 第二代种群第二代种群S2中各染色体的情况中各染色体的情况 染色体 适应度选择概率积累概率 估计的估计的选中次数选中次数s1=11001 625 0.36 0.36 1s2=01100 144 0.08 0.44 1s3=11011 729 0.41 0.85 1s4=10000 256 0.15 1.00 137 假设这一

15、轮选择-复制操作中，种群S2中的4个染色体都被选中个染色体都被选中，则得到群体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）做交叉运算，让s1与s2，s3与s4 分别交换后三位基因，得 s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）这一轮仍然不会发生变异。38于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）39 第三代种群第三代种群S3中各染色体的情况中各染色体的情况 染色体 适应度选择概率积累概率 估计的估计的选

16、中次数选中次数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 140 设这一轮的选择-复制结果为：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）这一轮仍然不会发生变异。41 于是，得第四代种群S4：s1=11111（31）,s2=11100（2

17、8）s3=11000（24）,s4=10000（16）42 显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。43YYy=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第四代种群及其适应度44遗传算法的描述Step1 选择问题的一

18、个编码；给出一个有N个染色体的初始群体pop(1),t:=1;Step2 对群体pop(t)中的每一个染色体popi(t)计算它的适应函数 fi=fitness(popi(t);Step3 若停止规则满足，则算法停止；否则，计算概率 Pi=fi/fi,i=1,2,N并以概率从pop(t)中随机选一些染色体构成一个新的种群Newpop(t+1)=pop(t)|j=1,2,N;Step4 通过交配，交配概率为pc，得到一个有N个染色体的crosspop(t+1);Step5 以较小概率pm，使得一个染色体的基因发生变异，形成mutpop(t+1);t:=t+1,一个新的体群pop(t)=mutpo

19、p(t);返回step2.453、遗传算法的特点（1）群体搜索，易于并行化处理；（2）不是盲目穷举，而是启发式搜索；（3）适应度函数不受连续、可微等条件的约束，适用范围很广。46二、理论基础二、理论基础1、遗传算法的数学基础 2、遗传算法的收敛性分析 3、遗传算法的改进 471、遗传算法的数学基础（1）模式定理（2）积木块假设 模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即 0 或者 1。模式示例：10*1模式模式48两个定义定义1：模式 H 中确定位置的个数称为模式 H 的阶，记作

20、O(H)。例如O(10*1)=3。定义2：模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式 H 的定义距，记作(H)。例如(10*1)=4。模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。模式的阶和定义距的含义49模式定理 模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。从模式定理可看出，有高平均适应度、短定义距、

21、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义距的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。50积木块假设 积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。定理 若参数满足：变异概率0pm1,交配概率0pc 1,则简单遗传算法不收敛于全局最优解。512、遗传算法的收敛性分析 遗传

22、算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。定理 如果改进简单遗传算法按交配、变异、种群选取之后更新当前最优染色体的进化循环过程，则收敛于全局最优解。改进遗传算法：进化的每一代中，记录前面各代最优解并存放在群体的第一位，这个染色体不参与遗传运算。52种群规模对收敛性的影响 通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。选择操作使高适应度个体能

23、够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。选择操作对收敛性的影响53交叉概率对收敛性的影响 交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。变异概率对收敛性的影响 变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随

24、机搜索算法。54遗传算法的本质 遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。55GAGA的局限性的局限性 在于 GA在进化搜索过程中，每代总要维持一定规模的群体，若群体规模太小，含有的信息量也少，不能使算法得到充分发挥，若群体规模大，包含的信息量也大，但计算次数会激剧增加，因而限制了算法的使用。GA的另一个不足之处是“早熟”。造成这种成熟前收敛的原因，一方面是 GA中最重要的遗传算子交叉算子使群体中的染色体具有局部相似

25、性，父代染色体的信息交换量小，从而使搜索停滞不前；另一方面是变异概率又太小，以至于不能使搜索转向其它的解空间进行搜索。GA的爬山能力差，也是由于变异概率低造成的。563、遗传算法的改进 遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。57遗传算法的改进途径（1）对编码方式的改进（2）对遗传算子的改进（3）对控制参数的改进（4）对执行策略的改进 58对编码方式的改进 二进制编码优点在于编码、解码操作简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空

26、间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题，浮点数编码改善了遗传算法的计算复杂性。59TSP问题的基本遗传算法(1)编码 自然数编码，i1i2i3in(2)适应度函数 fi：巡回路长度的倒数(3)选择操作 繁殖池；赌轮选择(4)杂交算子 例，基于位置的杂交 父代1：1 2 3 4 5 6 7 8 9 10 父代2：5 9 2 4 6 1 10 7 3 8 所选位置 *子代1：1 9 2 3 6 4 5 7 8 10 子代2：9 2 3 4 5 6 1 8 10 7(5)变异算子 例，基于位置的变异、基于次序的变异、打乱变异60对遗传算子的改进排序选择 均匀交叉 逆序变

27、异（1 1）对群体中的所有个体按其对群体中的所有个体按其适应度大小进行降序排序；适应度大小进行降序排序；（2 2）根据具体求解问题，设计根据具体求解问题，设计一个概率分配表，将各个概率值一个概率分配表，将各个概率值按上述排列次序分配给各个个体；按上述排列次序分配给各个个体；（3 3）以各个个体所分配到的概以各个个体所分配到的概率值作为其遗传到下一代的概率，率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产基于这些概率用赌盘选择法来产生下一代群体。生下一代群体。61对遗传算子 的改进排序选择 均匀交叉 逆序变异（1 1）随机产生一个与个体随机产生一个与个体编码长度相同的二进制屏蔽编码长度

28、相同的二进制屏蔽字字P=WP=W1 1W W2 2W Wn n ；（2 2）按下列规则从按下列规则从A A、B B两两个父代个体中产生两个新个个父代个体中产生两个新个体体X X、Y Y：若：若W Wi i=0=0，则，则X X的第的第i i个基因继承个基因继承A A的对应基因，的对应基因，Y Y的第的第i i个基因继承个基因继承B B的对应基的对应基因；若因；若W Wi i=1=1，则，则A A、B B的第的第i i个基因相互交换，从而生成个基因相互交换，从而生成X X、Y Y的第的第i i个基因。个基因。62对遗传算子的改进排序选择 均匀交叉 逆序变异变异前：变异前：3 4 8|7 9 6

29、5|2 13 4 8|7 9 6 5|2 1变异后：变异后：3 4 8|5 6 9 7|2 13 4 8|5 6 9 7|2 163对控制参数的改进 Schaffer建议的最优参数范围是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。64对控制参数的改进 Srinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和Pm，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和

30、Pm，使性能较差的个体被淘汰。651、遗传算法的应用领域（1）组合优化 （2）函数优化（3）自动控制 （4）生产调度（5）图像处理 （6）机器学习（7）人工生命 （8）数据挖掘 66遗传算法应用于组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能求出其最优解。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有NP难度的组合优化问题上取得了成功的应用。67三、实现技术三、实现技术1.群体的规模群体的规模 群体规模取个体编码长度的线性倍数是实际应用经常采用的方法；当多个进化代没有改变解的性能可以扩大群体的数量；反之

31、，可以减少群体的数量。2.初始群体的选取初始群体的选取 随机选取 采用启发式算法或经验选择一些优良的种子 “没有免费的午餐”68三、实现技术三、实现技术3.终止规则终止规则 1)给定最大的遗传代数；2)与目标值的差距 3)自适应：当若干代无法改变解的性能时。4.适应度函数适应度函数 1)简单适应度函数，fitness(x)=f(x)2)非线性加速适应函数，如,fitness(x)=1/(fmax-f(x),f(x)fmax M ,f(x)=fmax 3)线性加速适应度函数，fitness(x)=af(x)+b69三、实现技术三、实现技术5.交配规则交配规则 1)常用方法双亲双子法 2)变化交配法 父代A 1|1|0|1001 子代A 1|1|0|1001 父代B 1|1|0|0010 子代B 1|1|0|0010 避开相同的基因 3)其他6.约束条件的处理约束条件的处理 1)构造可行解 2)用罚函数的方式纳入到适应度中70问题背包问题的GA算法？个人观点供参考，欢迎讨论