遗传算法补充.pptx

《遗传算法补充.pptx》由会员分享，可在线阅读，更多相关《遗传算法补充.pptx（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1遗传算法补充遗传算法补充 1 基本概念 1.1.个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。种群(population)就是模拟生物种群而由若 干个体组成的群体,它一般是整个搜索空间 的一个很小的子集。第1页/共60页 2.2.适应度与适应度函数适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是

2、遗传算 法中指导搜索的评价函数。第2页/共60页3.3.染色体与基因染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体 染色体 9 -1001 （2，5，6）-010 101 110第3页/共60页4.4.遗传操作遗传操作亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作:选择-复制(selection-reproduction)交叉(crossover，亦称交换、交配或杂交)变异(mutation，亦称突变)第4页/共60页选择-复制通常做法是：对于一个规模为N的

3、种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。这里的选择概率P(xi)的计算公式为第5页/共60页交叉 就是互换两个染色体某些位上的基因。s1=01000101,s2=10011011可以看做是原染色体s1和s2的子代染色体。例如,设染色体 s1=01001011,s2=10010101,交换其后4位基因,即第6页/共60页常用的交叉算子常用的交叉算子常用的交叉算子常用的交叉算子n n单点交叉单点交叉 n n双点交叉或多点交叉双点交叉或多点交叉 n n均匀交叉均匀交叉 n n算术交叉算术交叉 A:1011 0111 00B:0001

4、 1100 11双点交叉A:1011 1100 00B:0001 0111 11A:10110111 00B:00011100 11单点交叉A:10110111 11B:00011100 00第7页/共60页 变异变异变异变异 就是改变染色体某个就是改变染色体某个(些些)位上的基因。位上的基因。例如例如,设染色体设染色体 s s=11001101=11001101将其第三位上的将其第三位上的0 0变为变为1,1,即即 s s=11=110 001101 01101 11111 101101=01101=s s。s s也可以看做是原染色体也可以看做是原染色体s s的子代染色体。的子代染色体。第8

5、页/共60页常用的变异算子常用的变异算子常用的变异算子常用的变异算子n n基本位变异基本位变异 n n均匀变异均匀变异 n n非均匀变异非均匀变异 n n高斯变异高斯变异 A:1010 01010 1基本位变异A:1010 01010 0第9页/共60页2 基本遗传算法 遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束第10页/共60页 算法中的一些控制参数：算法中的一些控制参数：群体规模群体规模popSizepopSize，终止进化代数，终止进化代数maxGenmaxGen，交叉概率，交叉概率p pc c和变异概率和变异概率p pm m。群体规模群体规模p

6、opSizepopSize：一般建议为：一般建议为2020100100。终止进化代数终止进化代数maxGenmaxGen：10010010001000交叉概率交叉概率p pc c：0.40.990.40.99变异概率变异概率p pm m：0.0010.0010.10.1第11页/共60页 基本遗传算法步1 在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；步2 随机产生U中的N个个体s1,s2,sN，组成初始种群S=s1,s2,sN，置代数计数器t=1；步3 计算S中每个个体的适应度f()；步4 若终止条件满足，则取S中适应度最大的个体作为所求结果，算法

7、结束。第12页/共60页 步步5 5 按选择概率按选择概率P P(x xi i)所决定的选中机会，所决定的选中机会，每次从每次从S S中随机选定中随机选定1 1个个体并将其染色体复个个体并将其染色体复制，共做制，共做N N次，然后将复制所得的次，然后将复制所得的N N个染色体个染色体组成群体组成群体S S1 1；步步6 6 按交叉率按交叉率P Pc c所决定的参加交叉的染色所决定的参加交叉的染色体数体数c c，从，从S S1 1中随机确定中随机确定c c个染色体，配对进个染色体，配对进行交叉操作，并用产生的新染色体代替原染行交叉操作，并用产生的新染色体代替原染色体，得群体色体，得群体S S2

8、2；第13页/共60页 步7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8 将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；第14页/共60页3 遗传算法举例 例例4.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。y=x2 31 XY第15页/共60页 分析分析 原问题可转化为在区间原问题可转化为在区间0,310,31中搜索能中搜索能使使y y取最大值的点取最大值的点a a的问题。那么，的问题。那么，0,310,31 中的点中的点x x就是个体就是个体,函数值函数值f f(x x)恰

9、好就可以作为恰好就可以作为x x的适应度，区间的适应度，区间0,310,31就是一个就是一个(解解)空间空间 。这样这样,只要能给出个体只要能给出个体x x的适当染色体编码的适当染色体编码,该该问题就可以用遗传算法来解决。问题就可以用遗传算法来解决。第16页/共60页解：(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数,取适应度函数：f(x)=x2 第17页/共60页(3)计算各代种群中的各个体的适应度,并

10、对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。第18页/共60页 首先计算种群首先计算种群S S1 1中各个体中各个体 s s1 1=13(01101),=13(01101),s s2 2=24(11000)=24(11000)s s3 3=8(01000),=8(01000),s s4 4=19(10011)=19(10011)的适应度的适应度f f(s si i)。容易求得容易求得 f f(s s1 1)=)=f f(13)=13(13)=132 2=169=169 f f(s s2 2)=)=f f(24)=24(24)=242 2=576=576 f f

11、(s s3 3)=)=f f(8)=8(8)=82 2=64=64 f f(s s4 4)=)=f f(19)=19(19)=192 2=361=361第19页/共60页再计算种群再计算种群S S1 1中各个体的选择概率。中各个体的选择概率。选择概率的计算公式为 由此可求得 P(s1)=P(13)=0.14 P(s2)=P(24)=0.49 P(s3)=P(8)=0.06 P(s4)=P(19)=0.31第20页/共60页 赌轮选择示意s40.31s20.49s10.14s30.06 赌轮选择法第21页/共60页在算法中赌轮选择法可用下面的子过程来模拟:在0,1区间内产生一个均匀分布的随机数r

12、。若rq1,则染色体x1被选中。若qk-1rqk(2kN),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,n)的积积累累概概率率,其计算公式为 第22页/共60页选择-复制 设从区间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 1第23页/共60页于是，经复制得群体：s1=11000（

13、24）,s2=01101（13）s3=11000（24）,s4=10011（19）第24页/共60页交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）第25页/共60页变异 设变异率pm=0.001。这样，群体S1中共有 540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。第26页/共60页 于是，得到第二代种群于是，得到第二代种群S S2 2：s s1 1=11001=110

14、01（2525）,s s2 2=01100=01100（1212）s s3 3=11011=11011（2727）,s s4 4=10000=10000（1616）第27页/共60页 第二代种群第二代种群S2中各染色体的情况中各染色体的情况 染色体 适应度选择概率积累概率 估计的选中次数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 1第28页/共60页 假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中个染色体都被选中，则得到群体：s1=110

15、01（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）这一轮仍然不会发生变异。第29页/共60页于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）第30页/共60页 第三代种群第三代种群S3中各染色体的情况中各染色体的情况 染色体 适应度选择概率积累概率 估计的选中次数s1=11100 784 0.44 0.44 2s2=01001

16、 81 0.04 0.48 0s3=11000 576 0.32 0.80 1s4=10011 361 0.20 1.00 1第31页/共60页 设这一轮的选择-复制结果为：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）这一轮仍然不会发生变异。第32页/共60页 于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（1

17、6）第33页/共60页 显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。第34页/共60页YYy=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第四代种群及其适应度第35页/共60页例 4.2 用遗传算法求解TSP。分析 由于其

18、任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。第36页/共60页（1）定义适应度函数 我们将一个合法的城市序列s=（c1,c2,cn,cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是 第37页/共60页（2）对个体s=（c1,c2,cn,cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。例如，对于5个城市的TSP

19、，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。第38页/共60页然后进行遗传操作。设 s1=（A,C,B,E,D,A），s2=（A,E,D,C,B,A）实施常规的交叉或变异操作，如交换后三位，得 s1=（A,C,B,C,B,A），s2=（A,E,D,E,D,A）或者将染色体s1第二位的C变为E，得 s1=（A,E,B,E,D,A）可以看出，上面得到的s1，s2和s1都是非法的城市序列。第39页/共60页 为此，对TSP必须设计合适的染色体和相应的遗传运算。事实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键

20、编码、顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位部分映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异置交叉、反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。第40页/共60页 p1=（1 2 3|4 5 6 7|8 9）p2=（4 5 2|1 8 7 6|9 3）将按照下面的方式产生后代。首先，切割点之间的片段被拷贝到后代里：o1=（x x x|4 5 6 7|x x）o2=（x x x|1 8 7 6|x x）为了得到o1，我们只需要移走p2中已在o1中的城市4、5、6和7后，得到 21893 该序列顺次放在o1中：o1=（2

21、 1 8|4 5 6 7|9 3）相似地，我们可以得到另一个后代：o2=（2 3 4|1 8 7 6|5 9）第41页/共60页4 遗传算法的特点与优势 遗传算法的主要特点 遗传算法一般是直接在解空间搜索,而不像图搜索那样一般是在问题空间搜索,最后才找到解。遗传算法的搜索随机地始于搜索空间的一个点集,而不像图搜索那样固定地始于搜索空间的初始节点或终止节点,所以遗传算法是一种随机搜索算法。第42页/共60页 遗传算法总是在寻找优解遗传算法总是在寻找优解,而不像图搜而不像图搜索那样并非总是要求优解索那样并非总是要求优解,而一般是设法尽快而一般是设法尽快找到解找到解,所以遗传算法又是一种优化搜索算法

22、。所以遗传算法又是一种优化搜索算法。遗传算法的搜索过程是从空间的一个遗传算法的搜索过程是从空间的一个点集点集(种群种群)到另一个点集到另一个点集(种群种群)的搜索的搜索,而不而不像图搜索那样一般是从空间的一个点到另一个像图搜索那样一般是从空间的一个点到另一个点地搜索。点地搜索。因而它实际是一种并行搜索因而它实际是一种并行搜索,适适合大规模并行计算合大规模并行计算,而且这种种群到种群的搜而且这种种群到种群的搜索有能力跳出局部最优解。索有能力跳出局部最优解。第43页/共60页遗传算法的适应性强,除需知适应度函数外,几乎不需要其他的先验知识。遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束,不

23、要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。第44页/共60页遗传算法的应用遗传算法的应用n n遗传算法在人工智能的众多领域便得到了广遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化配置（机器配置、分配问题）、组合优化（如（

24、如TSPTSP、背包问题）、函数的最大值以及图、背包问题）、函数的最大值以及图像处理和信号处理等等。像处理和信号处理等等。第45页/共60页n n另一方面，人们又将遗传算法与其他智能另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了与模糊技术、神经网络相结合，已取得了不少成果。不少成果。第46页/共60页5 遗传算法中的编码方式讨论 v遗传算法的编码方法有二进制编码、浮点数编码方法、格雷码、符号编码方法、多参数编码方法等。第47页

25、/共60页(1)二进制编码二进制编码n n是最常用的编码方法n n假设某一参数的取值范围是 AA，B B，AA B B。用长度为l l的二进制编码串来表示该参数，将 AA，B B 等分成2 2l l-1-1个子部分，记每一个等分的长度为。n n参数编码的对应关系:00000000 00000000=0 A 00000000 00000001=1 A+11111111 11111111=-1 B第48页/共60页n n解码解码 假设某一个体的编码是：假设某一个体的编码是：X X：x xl lx xl-1l-1x xl-2l-2x x2 2x x1 1，则上述二进制编码所对应的解码公式为则上述二进

26、制编码所对应的解码公式为：二进制编码的最大缺点之一是长度较大,对很多问题用其他编码方法可能更有利。第49页/共60页函数优化示例函数优化示例 n n求下列一元函数的最大值：n n x-1,2 x-1,2 x-1,2 x-1,2 ，求解结果精确到，求解结果精确到，求解结果精确到，求解结果精确到6 6 6 6位小数。位小数。位小数。位小数。第50页/共60页n n 由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。又因为221 3106 222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b2

27、0b0）。第51页/共60页1.二进制编码方法：二进制编码方法：它由二进制符号0和1所组成的二值符号集。它有以下一些优点：编码、解码操作简单易行交叉、变异等遗传操作便于实现符合最小字符集编码原则利用模式定理对算法进行理论分析。二进制编码的缺点是：对于一些连续函数的优化问题，由于其随机性使得其局部搜索能力较差，如对于一些高精度的问题（如上例），当解迫近于最优解后，由于其变异后表现型变化很大，不连续，所以会远离最优解，达不到稳定。而格雷码能有效地防止这类现象第52页/共60页2.格雷码方法：格雷码方法：格雷码方法是这样的一种编码方法，其连续两个整数所对应的编码值之间仅仅只有一个码位是不同的。第53

28、页/共60页n n假设有一个二进制编码假设有一个二进制编码B=bmbm-1b2b1B=bmbm-1b2b1，其对应的格雷码为，其对应的格雷码为G=gmgm-1g2g1G=gmgm-1g2g1n n由二进制编码转格雷码的转换公式为：由二进制编码转格雷码的转换公式为：n n gm=bmgm=bmn n gi=bi+1 gi=bi+1 bi bi，i=m-1,m-2,2,1i=m-1,m-2,2,1n n由格雷码转二进制的转换公式为：由格雷码转二进制的转换公式为：n n bm=gmbm=gmn n bi=bi+1 bi=bi+1 gi,i=m-1,m-2,2,1gi,i=m-1,m-2,2,1第54

29、页/共60页n n若使用格雷码来对个体进行编码，则编码串之间的若使用格雷码来对个体进行编码，则编码串之间的一位差异，对应的参数值也只是微小的差别。这样一位差异，对应的参数值也只是微小的差别。这样就相当于增前了遗传算法的局部搜索能力，便于对就相当于增前了遗传算法的局部搜索能力，便于对连续函数进行局部空间搜索。连续函数进行局部空间搜索。n n显然，对于相邻的十进制整数，使用格雷码时，两显然，对于相邻的十进制整数，使用格雷码时，两个编码串之间只有一位编码值不同；而使用二进制个编码串之间只有一位编码值不同；而使用二进制编码时，两个编码串之间却相差较大。编码时，两个编码串之间却相差较大。n n格雷码编码

30、方法是二进制编码方法的一种变形，其格雷码编码方法是二进制编码方法的一种变形，其编码精度与相同长度的二进制编码的精度相同。编码精度与相同长度的二进制编码的精度相同。第55页/共60页(3)浮点数编码方法浮点数编码方法n n所谓浮点数编码方法，是指个体的每个基因值用某一范围内的浮点数表示，个体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫真值编码方法。第56页/共60页n n港口年吞吐量振荡规律的描述第57页/共60页n n采用遗传算法求解模型的待定参数n n 上式中含有8个待定参数b,c,d,m,p,g,h,u。采用遗传算法求解这8个参数，从而得出港口年吞吐量的预测模型y(t)。n n1)编码n n 把待定的8个参数表示成一维数组x=(b,c,d,m,p,g,h,u)，数组各元为带符号的十进制数。第58页/共60页(4)符号编码法符号编码法n n符号编码法是指个体染色体编码串中的基符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含因值取自一个无数值含义、而只有代码含义的符号集如义的符号集如A,B,C。n nN个城市的旅行商问题(TSP)，假如用1,2,.N表示这N个城市，那对于任意这样的一个排列1p2p3.pN就表示了一个解，这个串就可以认为是一个染色体，它表示一个个体的基因。第59页/共60页