遗传算法理论及用于求解实际问题.pptx

《遗传算法理论及用于求解实际问题.pptx》由会员分享，可在线阅读，更多相关《遗传算法理论及用于求解实际问题.pptx（41页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、3.1 遗传算法的基本概念基本思想使用模拟生物和人类进化的方法求解复杂的优化问题，因而也称为模拟进化优化算法。遗传算法将择优与随机信息交换结合在一起，在每一代中，使用上代中最好的，即最适应环境的位或片段，形成新的人工生物集。遗传算法是一个迭代过程，在每次迭代中都保留一组候选解，并按某种优劣指标进行排序，然后按某种指标从中选出一些解，利用遗传算子，即下面要讲到的遗传操作，对其进行运算以产生新一代的一组解。重复上述过程，直到满足指定的收敛要求为止。第1页/共41页3.1.1 遗传算法的基本概念定义3.1 个体:个体是一个数据结构，用来描述基本的遗传结构。定义3.2 适应性：每个个体有一对应的适应值

2、。在优化问题中，适应值来自于一个估计函数。定义3.3 群体:由个体组成的集合。定义3.4 遗传操作：遗传操作作用于群体而产生新的群体。标准的代遗传操作一般包括选择(或复制)，交叉(或重组)和变异三种基本形式。例子第2页/共41页 一个简单的遗传操作实例 第3页/共41页3.1.2 遗传算法的基本流程遗传算法涉及五大要素：1.参数编码2.初始群体设定3.适应度函数设计4.遗传操作设计5.控制参数设定 第4页/共41页确定实际问题参数集对参数进行编码初始化群体(t)评价群体满足停止准则?遗传操作结束群体(t)群体(t)三个基本操作：1.选择2.交叉3.变异其它高级操作标准遗传算法基本流程框图第5页

3、/共41页选择种群新后代变异交叉1234110001110001110101010111010001101101101154.538.343.734.61324#位串适应值排序110001110001110100011100010001011101110011000101010110011100交叉点变异位标准遗传算法基本流程框图实例交配池第6页/共41页遗传算法的执行过程1.选择编码策略，把参数集合和域转换为相应编码空间；2.定义适应值函数f(X);3.定义遗传策略，包括选择群体大小、选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；4.随机初始化生成群体(t);5.计算群体中个体的

4、适应值f(X);6.按照遗传策略，运用选择、交叉和变异操作作用于群体，形成下一代群体；7.判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则返回步骤6），或者修改遗传策略再返回步骤6）。第7页/共41页3.2 遗传编码3.2.1 二进制编码3.2.2 Gray编码3.2.3 实数编码3.2.4 有序编码3.2.5 结构式编码第8页/共41页3.2.1 二进制编码在二进制编码过程中，首先要确定二进制串的长度l，串长l取决于变量的定义域及计算所需的精度。例例3.23.2 变量x的定义域为2，5，要求其精度为10-6，则我们需将2，5分成至少7 000 000个等长小区域，而每个小区域用

5、一个二进制串表示。于是串长至少等于23，这是因为：4194304=2227000000223=8388608这样，计算中的任何一个二进制串（b22b21b0）都对应-2，5中的一个点。第9页/共41页3.2.2 Gray编码Gray编码即是将二进制码通过如下变换进行转换得到的码。设有二进制串（12n），对应的Gray串为（12n），则从二进制码到Gray码的变换为其中表示模2加法。从一个Gray码到二进制串的变换为例3.3 二进制串1101011对应的Gray串为101110。第10页/共41页3.2.3 实数编码为了克服二进制编码的缺点，对于问题的变量是实向量的情形，直接可以采用十进制进行编

6、码，这样可以直接在解的表现形式上进行遗传操作，从而便于引入与问题领域相关的启发式信息以增加系统的搜索能力 第11页/共41页例3 作业调度问题（JSP）的种群个体编码常用mn的矩阵Y=yij，i=1，2，m，j=1，2，n（n为从加工开始的天数，m为工件的优先顺序）。表示工件i在第j日的加工时间。下表是一个随机生成的个体所示。010102020303040405050606070708080909工件工件工件工件1 10 02 21 12 22 21 12 2工件工件工件工件2 20 01 12 20 00 04 4工件工件工件工件3 31 10 00 01 13 31 1工件工件工件工件4

7、40 02 23 30 00 01 1工件工件工件工件5 50 02 20 03 30 00 00 01 11 1第12页/共41页3.2.4 有序编码对很多组合优化问题，目标函数的值不仅与表示解的字符串中各字符的值有关，而且与其所在字符串中的位置有关。这样的问题称为有序问题。若目标函数的值只与表示解的字符串中各字符的位置有关而与其具体的字符值无关，则称为纯有序问题，如采用顶点排列的旅行商问题。例3.4 有10个城市的TSP问题，城市序号为1，2，10，则编码位串表示对城市采用按序号升序方法访问行走路线。1 3 5 7 9 2 4 6 8 10表示按特定“1 3 5 7 9 2 4 6 8 1

8、0 1”依次访问各个城市。第13页/共41页3.2.5 结构式编码对很多问题其更自然的表示是树或图的形式，这时采用其它形式的变可能很困难。这种将问题的解表达成树或图的形式的编码称为结构式编码。第14页/共41页3.3 适应值函数适应值函数构成了个体的生成环境。根据个体的适应值可以决定它在此环境下的生存能力。若SL表示位串空间，SL上的适应值函数可表示为f:SLR+，f为实值函数，R+表示非负实数集合。针对进化过程中关于遗传操作的控制的需要，选择函数变换T：gf，使得对于最优解x*，max f(x*)=opt g(x*)(x*u，v)。第15页/共41页3.4 遗传操作3.4.1 选择(sele

9、ction)3.4.2 交叉操作(crossover)3.4.3 变异操作(mutation)第16页/共41页3.4.1 选择(selection)选择即从当前群体中选出个体以生成交配池（mating pool）的过程。所选出的这些个体具有良好的特征，以便产生优良的后代。1.基于适应值比例的选择2.基于排名的选择3.基于局部竞争机制的选择第17页/共41页1.基于适应值比例的选择（1）繁殖池选择 相对适应值：每个个体的繁殖量：Ni=round(reliN)（2）转盘赌选择 2pi现生成一个0，1内的随机数r，若p1+p2+pi-10，且p1p2pN，故限定1a2。通常使用的值为a=1.1。第

10、19页/共41页2.基于排名的选择（2）非线性排名选择 将群体成员按适应值从好到坏依次排列，并按下式进行分配选择概率：其中q是常数，表示最好的个体的选择概率。第20页/共41页3.基于局部竞争机制的选择（1）锦标赛选择(tournament selection)选择时，先随机地选择在群体中选择k个个体（放回或不放回）进行比较，适应值最好的个体将被选择作为生成下一代的父体。反复执行该过程，直到下一代个体数量达到预定的群体规模。参数k称为竞赛规模，一般取k=2。（2）(，)和+选择 (，)选择是先从规模为种群中随机选取个体通过交叉和变异生成（）个后代，然后再从这些后代中选取个最优的后代作为新的一代

11、种群。+选择则是从这些后代与其父体共+个后代中选取个最优的后代。第21页/共41页3.4.2 交叉操作(crossover)交叉的具体步骤为：1.从交配池中随机取出要交配的一对个体；2.根据位串长度L，对要交配的一对个体，随机选取1，L-1中一个或多个的整数k作为交叉点；3.根据交叉概率pc(0pc1)实施交叉操作，配对个体在交叉点处，相互交换各自的部分内容，从而形成新的一对个体。对二进制编码常用的交叉算子有单点交叉单点交叉、多点多点交叉交叉和均匀交叉均匀交叉。第22页/共41页1.1.单点交叉单点交叉 对于从交配池中随机选择的两个串s1=a11a12a1l1a1l2a1L，s2=a21a22

12、a2l1a2l2a2L，随机选择一个交叉位x 1，2，L1，不妨设 l1 xl2，对两个位串中该位置右侧部分的染色体位串进行交换，产生两个子位串个体为：s1=a11a12a1l1 a2l2a2L，s2=a21a22a2l1 a1l2a1L例3.5 考虑如下两个11位变量的父个体：父个体1：0 1 1 1 0 0 1 1 0 1 0父个体2：1 0 1 0 1 1 0 0 1 0 11 0 1 0 1 1 0 0 1 0 1交叉点在位置5，交叉后生成两个子个体：子个体1：0 1 1 1 0 1 0 0 1 0 11 0 0 1 0 1子个体2：1 0 1 0 11 0 1 0 1 0 1 1 0

13、 1 0第23页/共41页2.多点交叉 对于选定的两个个体位串，随机选择多个交叉点，构成交叉点集合：x 1，x 2，x K1，2，L1，x kx k1，k=1，2，K1将L个基因为划分为K1个基因位集合：Qk=lk，lk+1，lk+11，k=1，2，K1，l1=1，lK+2=L+1算子形式为生成的新个体为s1=a11a12a1L，s2=a21a22a2L 第24页/共41页例3.6 考虑如下两个11位变量的父个体：父个体1：0 1 1 1 0 0 1 1 0 1 0父个体2：1 0 1 0 1 1 0 0 1 0 11 0 1 0 1 1 0 0 1 0 1交叉点在位置2，6，10，交叉后生成

14、两个子个体：子个体1：0 1 1 0 1 11 0 1 1 1 1 0 1 1 1子个体2：1 0 1 1 0 0 0 0 1 00 0 1 0 0第25页/共41页3.均匀交叉 将位串上的每一位按相同概率随机进行均匀交叉。均匀交叉算子生成的新个体为：s1=a11a12a1L，s2=a21a22a2L，其操作描述如下：第26页/共41页例3.8 设城市数的旅行商问题，对如下的两个个体进行交叉，中间得竖线表示交叉点。得到下一代的个体为：它们都不是合法的个体。怎样保证所产生的个体仍然合法?一种方法是为参与交换的数增加一个映射如下:将此映射应用于未交换的等位基因得到:则为合法的。第27页/共41页3

15、.4.3 变异操作 变异的具体操作为:对中任一个体，随机产生一实数，如果大于事先定义的变异概率的阈值，就对该个体进行变异。1.实值变异2.二进制变异第28页/共41页3.5 初始化群体初始群体中的个体一般是随机产生的。我们往往希望在问题解空间均匀采样，随机生成一定数目的个体（为群体规模的2倍，即2n），然后从中挑出较好的个体构成初始群体。对于二进制编码，染色体位串上的每一位基因在0，1上随机均匀选择，所以群体初始化至少需要Ln次随机取值。可以证明初始群体的位串译码到问题实空间中也是均匀分布的。第29页/共41页3.6 控制参数的选取 主要的参数包括：位串长度L，群体规模n，交叉概率pc，变异概

16、率pm。参数的最佳建议：n=20200 pc=0.61.0 pm=0.0050.01 第30页/共41页3.7 算法的终止准则(1)预先规定最大演化代数;(2)连续多代后解的适应值没有明显改进，则终止;(3)达到明确的解目标，则终止。第31页/共41页3.9 遗传算法简例例3.9 用GA求解一元函数最大值的优化问题：f(x)=xsin(10 x)+2.0 x-1，2（1）编码 变量x作为实数，可以视为遗传算法的表现型形式。现采用二进制编码形式。如果设定求解精度精确到6位小数，由于区间长度为2（1）=3，因此将闭区间1，2分为3106等份。因为2 097 152=2213106222=4 194

17、 304所以编码的二进制串长至少需要22位。第32页/共41页现在采用22位二进制编码，将一个二进制串（b21b20b0）与区间1，2内对应的实数值的建立对应：例如:一个二进制串s1=1000101110110101000111表示实数0.637 197x=（1000101110110101000111）2=2 288 967第33页/共41页（2）产生初始种群 一个个体由串长为22的随机产生的二进制串组成染色体的基因码，我们可以产生一定数目的个体组成的种群。设产生的4个初始个体如下：s1=s2=s3=s4=第34页/共41页（3）计算适应度 对于个体的适应度的计算，考虑到本例目标函数在定义域

18、内均大于0，而且是求函数的最大值，所以直接引用目标函数作为适应值函数：f(s)=f(x)这里二进制串s对应变量x的值。编编号号个体串个体串x x适应值适应值百分百分比比%累计百累计百分比分比%s s1 110001011101101010001111000101110110101000111 0.637 1970.637 197 2.586 3452.586 34529.129.129.129.1s s2 2000000111000000010000000000111000000010000-0.958 973-0.958 973 1.078 8781.078 87812.112.141.24

19、1.2s s3 311100000001111110001011110000000111111000101 1.627 8881.627 888 3.250 6503.250 65036.536.577.777.7s s4 400100010001101110100100010001000110111010010-0.599 032-0.599 032 1.981 7851.981 78522.322.3100100第35页/共41页（4）遗传操作 设按转盘赌方式选择子个体，生成的随机数为0.35，0.72。则选中的个体为s2和s3。对s2和s3进行交叉操作，随机选择一个交叉点，例如第5位与第

20、6位之间的位置，交叉后产生新的子个体：s2=s3=这两个子个体的适应值分别为：f(s2)=f(0.998 113)=1.940 865f(s3)=f(1.666 028)=3.459245交叉后个体s3的适应值比其父个体的适应值高。第36页/共41页下面考察变异操作。假设已经以一小概率选择了s3的第5个遗传因子（即第5位）变异，遗传因子由原来的0变成1，产生新的个体为s3=计算该个体的适应值：f(s3)=f(1.721 638)=0.917 743，发现个体的适应值比其父个体的适应值减少了，但是如果选择第10个遗传因子变异，产生的新个体为s3=f(s3)=f(1.630 818)=3.3435

21、55显然，这个个体的适应值比其父个体的适应值提高了。这说明变异操作有“扰动”作用。第37页/共41页（5）模拟结果 设定种群大小为50，交叉概率pc=0.25，变异概率pm=0.01，按照标准的遗传算法SGA，在运行到第89代时获得最佳个体：smax=xmax=1.850 549，f(xmax)=3.850 274这个个体对应的解与微分方程预计的最优解得情况吻合。表3.3列出了模拟一部分代的种群中最佳个体的演变情况（150代终止）。第38页/共41页代数代数个体的二进制串个体的二进制串x x适应值适应值1 11111000110100001110000111100011010000111000

22、01.831 6241.831 6243.534 8063.534 8064 4111100101000110110000011110010100011011000001.842 4161.842 4163.790 3623.790 3627 7111100111001110101011011110011100111010101101.854 8601.854 8603.833 2803.833 2801111111100111001110101011011110011100111010101101.854 8601.854 8603.833 2863.833 2861717111100101

23、111110101011011110010111111010101101.847 5361.847 5363.842 0043.842 0041818111100101111110111000011110010111111011100001.847 5541.847 5543.842 1023.842 1023434111100110111101100001111110011011110110000111.853 2901.853 2903.843 4023.843 4024040111100110001000100101111110011000100010010111.848 4431.84

24、8 4433.846 2323.846 2325454111100110001011011000011110011000101101100001.848 6991.848 6993.847 1553.847 1557171111100110100011011000111110011010001101100011.850 8971.850 8973.850 1623.850 1628989111100110011111100101111110011001111110010111.850 5491.850 5493.850 2743.850 274150150111100110011111100101111110011001111110010111.850 5491.850 5493.850 2743.850 274模拟世代的种群中最佳个体的演变情况 第39页/共41页3.10遗传算法的应用领域1.天然气管道的最优控制2.喷气式飞机涡轮机的设计3.旅行商问题4.作业调度问题5.遗传学习6.自动控制领域7.人工智能与计算机科学8.社会和经济领域第40页/共41页感谢您的观看！第41页/共41页