《遗传算法理论及用于求解实际问题.ppt》由会员分享，可在线阅读，更多相关《遗传算法理论及用于求解实际问题.ppt（42页珍藏版）》请在三一办公上搜索。
1、,3.1 遗传算法的基本概念3.2 遗传编码3.3 适应值函数3.4 遗传操作3.5 初始化群体3.6 控制参数的选取3.7 算法的终止准则3.8 遗传算法的基本理论3.9 遗传算法简例3.10遗传算法的应用领域,3.1 遗传算法的基本概念,基本思想使用模拟生物和人类进化的方法求解复杂的优化问题，因而也称为模拟进化优化算法。遗传算法将择优与随机信息交换结合在一起，在每一代中，使用上代中最好的，即最适应环境的位或片段，形成新的人工生物集。遗传算法是一个迭代过程，在每次迭代中都保留一组候选解，并按某种优劣指标进行排序，然后按某种指标从中选出一些解，利用遗传算子，即下面要讲到的遗传操作，对其进行运算
2、以产生新一代的一组解。重复上述过程，直到满足指定的收敛要求为止。,3.1.1 遗传算法的基本概念,定义3.1 个体:个体是一个数据结构，用来描述基本的遗传结构。定义3.2 适应性：每个个体有一对应的适应值。在优化问题中，适应值来自于一个估计函数。定义3.3 群体:由个体组成的集合。定义3.4 遗传操作：遗传操作作用于群体而产生新的群体。标准的代遗传操作一般包括选择(或复制)，交叉(或重组)和变异三种基本形式。,例子,一个简单的遗传操作实例,3.1.2 遗传算法的基本流程,遗传算法涉及五大要素：参数编码初始群体设定适应度函数设计遗传操作设计控制参数设定,遗传算法的执行过程,选择编码策略，把参数集
3、合和域转换为相应编码空间；定义适应值函数f(X);定义遗传策略，包括选择群体大小、选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；随机初始化生成群体(t);计算群体中个体的适应值f(X);按照遗传策略，运用选择、交叉和变异操作作用于群体，形成下一代群体；判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则返回步骤6），或者修改遗传策略再返回步骤6）。,3.2 遗传编码,3.2.1 二进制编码3.2.2 Gray编码3.2.3 实数编码3.2.4 有序编码3.2.5 结构式编码,3.2.1 二进制编码,在二进制编码过程中，首先要确定二进制串的长度l，串长l取决于变量的定义域及
4、计算所需的精度。例3.2 变量x的定义域为2，5，要求其精度为10-6，则我们需将2，5分成至少7 000 000个等长小区域，而每个小区域用一个二进制串表示。于是串长至少等于23，这是因为：4194304=2227000000223=8388608这样，计算中的任何一个二进制串（b22b21b0）都对应-2，5中的一个点。,3.2.2 Gray编码,Gray编码即是将二进制码通过如下变换进行转换得到的码。设有二进制串（12n），对应的Gray串为（12n），则从二进制码到Gray码的变换为其中表示模2加法。从一个Gray码到二进制串的变换为例3.3 二进制串1101011对应的Gray串为1
5、01110。,3.2.3 实数编码,为了克服二进制编码的缺点，对于问题的变量是实向量的情形，直接可以采用十进制进行编码，这样可以直接在解的表现形式上进行遗传操作，从而便于引入与问题领域相关的启发式信息以增加系统的搜索能力,例3 作业调度问题（JSP）的种群个体编码常用mn的矩阵Y=yij，i=1，2，m，j=1，2，n（n为从加工开始的天数，m为工件的优先顺序）。表示工件i在第j日的加工时间。下表是一个随机生成的个体所示。,3.2.4 有序编码,对很多组合优化问题，目标函数的值不仅与表示解的字符串中各字符的值有关，而且与其所在字符串中的位置有关。这样的问题称为有序问题。若目标函数的值只与表示解
6、的字符串中各字符的位置有关而与其具体的字符值无关，则称为纯有序问题，如采用顶点排列的旅行商问题。例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 10 1”依次访问各个城市。,3.2.5 结构式编码,对很多问题其更自然的表示是树或图的形式，这时采用其它形式的变可能很困难。这种将问题的解表达成树或图的形式的编码称为结构式编码。,3.3 适应值函数,适应值函数构成了个体的生成环境。根据个体的适应值可以决定它在此环境下的生存能力。若SL表示位串空间，S
7、L上的适应值函数可表示为f:SLR+，f为实值函数，R+表示非负实数集合。针对进化过程中关于遗传操作的控制的需要，选择函数变换T：gf，使得对于最优解x*，max f(x*)=opt g(x*)(x*u，v)。,3.4 遗传操作,3.4.1 选择(selection)3.4.2 交叉操作(crossover)3.4.3 变异操作(mutation),3.4.1 选择(selection),选择即从当前群体中选出个体以生成交配池（mating pool）的过程。所选出的这些个体具有良好的特征，以便产生优良的后代。1.基于适应值比例的选择2.基于排名的选择3.基于局部竞争机制的选择,1.基于适应值
8、比例的选择,（1）繁殖池选择 相对适应值：每个个体的繁殖量：Ni=round(reliN)（2）转盘赌选择,现生成一个0，1内的随机数r，若p1+p2+pi-1rp1+p2+pi，则选择个体i。,2.基于排名的选择,（1）线性排名选择 首先假设群体成员按适应值大小从好到坏依次排列为x1，x2，xN，然后根据一个线性函数分配选择概率pi。设线性函数pi（abi/（N+1）/N，i=1，2，N，其中a，b为常数。由于，易得，b=2(a1)。又要求对任意i=1，2，N，有pi0，且p1p2pN，故限定1a2。通常使用的值为a=1.1。,2.基于排名的选择,（2）非线性排名选择 将群体成员按适应值从好
9、到坏依次排列，并按下式进行分配选择概率：其中q是常数，表示最好的个体的选择概率。,3.基于局部竞争机制的选择,（1）锦标赛选择(tournament selection)选择时，先随机地选择在群体中选择k个个体（放回或不放回）进行比较，适应值最好的个体将被选择作为生成下一代的父体。反复执行该过程，直到下一代个体数量达到预定的群体规模。参数k称为竞赛规模，一般取k=2。（2）(，)和+选择(，)选择是先从规模为种群中随机选取个体通过交叉和变异生成（）个后代，然后再从这些后代中选取个最优的后代作为新的一代种群。+选择则是从这些后代与其父体共+个后代中选取个最优的后代。,3.4.2 交叉操作(cro
10、ssover),交叉的具体步骤为：从交配池中随机取出要交配的一对个体；根据位串长度L，对要交配的一对个体，随机选取1，L-1中一个或多个的整数k作为交叉点；根据交叉概率pc(0pc1)实施交叉操作，配对个体在交叉点处，相互交换各自的部分内容，从而形成新的一对个体。对二进制编码常用的交叉算子有单点交叉、多点交叉和均匀交叉。,1.单点交叉 对于从交配池中随机选择的两个串s1=a11a12a1l1a1l2a1L，s2=a21a22a2l1a2l2a2L，随机选择一个交叉位x 1，2，L1，不妨设 l1 xl2，对两个位串中该位置右侧部分的染色体位串进行交换，产生两个子位串个体为：s1=a11a12a
11、1l1 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 1交叉点在位置5，交叉后生成两个子个体：子个体1：0 1 1 1 0 1 0 0 1 0 1子个体2：1 0 1 0 1 0 1 1 0 1 0,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
12、+2=L+1算子形式为,生成的新个体为s1=a11a12a1L，s2=a21a22a2L,例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 1交叉点在位置2，6，10，交叉后生成两个子个体：子个体1：0 1 1 0 1 1 1 1 0 1 1子个体2：1 0 1 1 0 0 0 0 1 0 0,3.均匀交叉,将位串上的每一位按相同概率随机进行均匀交叉。均匀交叉算子生成的新个体为：s1=a11a12a1L，s2=a21a22a2L，其操作描述如下：,例3.8 设城市数的旅行商问题，对如下的两个个体进行交
13、叉，中间得竖线表示交叉点。得到下一代的个体为：它们都不是合法的个体。怎样保证所产生的个体仍然合法?一种方法是为参与交换的数增加一个映射如下:将此映射应用于未交换的等位基因得到:则为合法的。,3.4.3 变异操作,变异的具体操作为:对中任一个体，随机产生一实数，如果大于事先定义的变异概率的阈值，就对该个体进行变异。1.实值变异2.二进制变异,3.5 初始化群体,初始群体中的个体一般是随机产生的。我们往往希望在问题解空间均匀采样，随机生成一定数目的个体（为群体规模的2倍，即2n），然后从中挑出较好的个体构成初始群体。对于二进制编码，染色体位串上的每一位基因在0，1上随机均匀选择，所以群体初始化至少
14、需要Ln次随机取值。可以证明初始群体的位串译码到问题实空间中也是均匀分布的。,3.6 控制参数的选取,主要的参数包括：位串长度L，群体规模n，交叉概率pc，变异概率pm。参数的最佳建议：n=20200 pc=0.61.0 pm=0.0050.01,3.7 算法的终止准则,(1)预先规定最大演化代数;(2)连续多代后解的适应值没有明显改进，则终止;(3)达到明确的解目标，则终止。,3.9 遗传算法简例,例3.9 用GA求解一元函数最大值的优化问题：f(x)=xsin(10 x)+2.0 x-1，2（1）编码 变量x作为实数，可以视为遗传算法的表现型形式。现采用二进制编码形式。如果设定求解精度精确
15、到6位小数，由于区间长度为2（1）=3，因此将闭区间1，2分为3106等份。因为2 097 152=2213106222=4 194 304所以编码的二进制串长至少需要22位。,现在采用22位二进制编码，将一个二进制串（b21b20b0）与区间1，2内对应的实数值的建立对应：例如:一个二进制串s1=1000101110110101000111表示实数0.637 197x=（1000101110110101000111）2=2 288 967,（2）产生初始种群 一个个体由串长为22的随机产生的二进制串组成染色体的基因码，我们可以产生一定数目的个体组成的种群。设产生的4个初始个体如下：s1=s2
16、=s3=s4=,（3）计算适应度 对于个体的适应度的计算，考虑到本例目标函数在定义域内均大于0，而且是求函数的最大值，所以直接引用目标函数作为适应值函数：f(s)=f(x)这里二进制串s对应变量x的值。,（4）遗传操作 设按转盘赌方式选择子个体，生成的随机数为0.35，0.72。则选中的个体为s2和s3。对s2和s3进行交叉操作，随机选择一个交叉点，例如第5位与第6位之间的位置，交叉后产生新的子个体：s2=s3=这两个子个体的适应值分别为：f(s2)=f(0.998 113)=1.940 865f(s3)=f(1.666 028)=3.459245交叉后个体s3的适应值比其父个体的适应值高。,
17、下面考察变异操作。假设已经以一小概率选择了s3的第5个遗传因子（即第5位）变异，遗传因子由原来的0变成1，产生新的个体为s3=计算该个体的适应值：f(s3)=f(1.721 638)=0.917 743，发现个体的适应值比其父个体的适应值减少了，但是如果选择第10个遗传因子变异，产生的新个体为s3=f(s3)=f(1.630 818)=3.343555显然，这个个体的适应值比其父个体的适应值提高了。这说明变异操作有“扰动”作用。,（5）模拟结果 设定种群大小为50，交叉概率pc=0.25，变异概率pm=0.01，按照标准的遗传算法SGA，在运行到第89代时获得最佳个体：smax=xmax=1.850 549，f(xmax)=3.850 274这个个体对应的解与微分方程预计的最优解得情况吻合。表3.3列出了模拟一部分代的种群中最佳个体的演变情况（150代终止）。,模拟世代的种群中最佳个体的演变情况,3.10遗传算法的应用领域,1.天然气管道的最优控制2.喷气式飞机涡轮机的设计3.旅行商问题4.作业调度问题5.遗传学习6.自动控制领域7.人工智能与计算机科学8.社会和经济领域,
