第07章遗传算法

1遗传算法2一、遗传算法概述（1）遗传算法(GeneticAlgorithm,GA)是一类建立在自然选择和群体遗传学机理基础上的通用问题求解算法,具有广泛的适应性。遗传算法是Holland在20世纪60年代末提出的，当时并未受到重视。3基本思想使用模拟生物和人类进化的方法求解复杂的优化问题，因而也称为模拟进化优化算法。将择优与随机信息交换结合在一起。在每一代中，使用上一代中最好的，即最适应环境的位或片段，形成新的人工生物集。一、遗传算法概述（2）4应用领域早期应用研究主要围绕组合优化问题以及复杂的函数优化问题求解，以后它的研究应用迅速扩大，遍及科学、工程、商业等领域：NP完全问题神经网络权值机器学习并行处理知识发现一、遗传算法概述（3）5二、遗传算法中的基本概念（1）•形式化描述GA=(P(0),N,l,s,g,p,f,t)其中：P(0)=(P1(0),P2(0),…,Pn(0)),表示初始种群；N表示种群中含有个体的个数；l表示二进制串的长度；s表示选择策略；g表示遗传算子（选择算子Qr、杂交算子Qc和变异算子Qm)；p表示遗传算子的操作概率（选择概率pr、杂交概率Pc和变异概率Pm)；f是适应度函数；t是终止准则。6二、遗传算法中的基本概念（2）•问题的解空间遗传算法主要用在对所研究问题寻求最优解或次优解的领域中，通常，问题的最优解或次优解是包含在一个庞大的有限可能的解集合中。我们把这个有限可能的解集合称为问题的解空间。种群(popolation)与个体(individual)遗传算法在求解问题时是从初始给定的多个解开始搜索的，这初始给定的多个解的集合称为一个种群，种群是问题的解空间的一个子集，种群中的每个元素叫个体。•个体个体是一个数据结构，用来描述基本的遗传结构。例如：用0,1组成的串可以表示个体，这样的串叫染色体，其中每个0，1叫等位基因。这样的一个串与某个个体相关联，称为该个体的基因型。适应性(Fitness)每个个体有一对应的适应值。在优化问题中，适应值来自一个估计函数。•遗传操作遗传操作作用于群体而产生新的群体。选择(Selection)、交叉(Crossover)、变异(Mutation)适应值1113291101101101001001110110111011100111111001100110111111000110001011适应值1113291101101101001001110110111011100111111001100110111111000110001011n代选择交叉n+1代变异一个简单的遗传算法实例7三、遗传算法的基本流程（1）确定实际问题参数集对参数进行编码初始化群体P(t)评价群体满足停止准则？遗传操作结束群体P(t+1)群体P(t)三个基本操作：1、选择2、交叉3、变异其他高级操作标准遗传算法基本流程框图基本步骤：（1）选择编码策略，把参数集合X和域转换为相应编码空间S。（2）定义适应值函数f(x)。（3）定义遗传策略，包括选择群体大小、交叉、变异方法以及确定交叉概率Pc、变异概率Pm等遗传参数。（4）随机初始化生成群体P(t)。（5）计算群体中个体的适应值f(X)。（6）按照遗传策略，运用选择、交叉和变异操作作用于群体，形成下一代群体。（7）判断群体性能是否满足某一指标，或者已完成预定跌代次数，不满足则返回第6步，或者修改遗传算法再返回第6步。8用遗传算法求解问题时，必须在目标问题实际表示与遗传算法染色体结构之间建立联系，即确定编码和解码运算。霍兰德提出的遗传算法采用二进制编码来表现个体的遗传基因型，它使用的编码符号0和1组成，因此实际的遗传基因型是一个二进制符号串。四、遗传编码（1）优点：在于编码、解码操作简单，交叉、变异等遗传操作便于实现，而且便于用模式定理进行理论分析等。缺点：不便于反映所求问题的特定知识，对于一些连续函数的优化问题等，由于遗传算法的随机特征而使得其局部搜索能力较差；对于一些多维、高精度要求的连续函数的优化，二进制编码存在着连续函数离散化时的映射误差；个体编码串较短时，可能达不到精度要求；个体编码串的长度较长时，虽然能提供精度，会使算法的搜索空间急剧扩大。91、二进制编码在二进制编码中，首先要确定二进制字符串的长度l，串长l取决于变量的定义域及计算所需的精度。例:变量x的定义域[-2,5],要求其精度为10-6,则需要将[-2,5]分成至少7000000个等长小区域,而每个小区域用一个二进制表示。于是串长至少等于23。4194304=2227000000223=8388608这样，计算中的任何一个二进制串(b22b21…b0)都对应[-2，5]中的一个点。四、遗传编码（2）解码过程：将二进制串(b22b21…b0)按下式转换成为1个十进制整数：xl=∑bi*2i按下列计算对应变量x的值：x=-2.0+xi*7/(223-1)i=02210遗传算法将问题空间表示为染色体位串空间，为了执行适者生存的原则，必须对个体位串的适应性进行评价。适应值函数构成了个体的生存环境。根据个体适应值可以决定它在此环境下的生存能力。一般来说，好的染色体位串结构具有比较高的适应值，即可以取得较高的评价，具有较强的生存能力。五、适应值函数（1）11由于适应值是群体中个体生存机会选择的唯一确定性指标，所以适应值函数的形式直接决定着群体的优化。根据实际问题的经济含义，适应值可以是销售收入、利润、生产占有率或机器的可靠性。为了能够直接将适应值函数与群体中个体的优劣度量相联系，在遗传算法中适应值规定为非负，并且在任何情况下总是希望越大越好。五、适应值函数（2）12若SL表示位串空间,SL上的适应值函数可表示为:f:SLR+其中f为实值函数,R+表示非负实数集合。对于给定的优化问题optg(x)(x∈[u,v])目标函数有正有负。甚至可能是复数。所以必须通过建立适应值函数与目标函数的映射关系，保证映射后的适应值是非负的，而且目标函数的优化方向应对应于适应值增大的方向。五、适应值函数（3）13五、适应值函数（4）针对进化过程中关于遗传算法操作控制的需要，选择函数变换T:gf,使得对于最优解x*,maxf(x*)=optg(x*),x*∈[u,v]针对最小化问题，建立适应函数f(x)和目标函数g(x)的映射关系：其中，cmax可以是一个输入值或理论上的最大值，或者是到当前所有代或最近K代中g(x)的最大值，此时cmax随着代数增加会有变化。cmax-g(x)当g(x)cmax0否则f(x)=cmax-g(x)当g(x)cmax0否则f(x)=针对最大化问题，一般采用下述方法：其中，cmax可以是一个输入值或理论上的最小值，或者是到当前所有代或最近K代中g(x)的最小值。g(x)-cmax当g(x)cmax0否则f(x)=14六、遗传操作（1）6.1选择操作选择即从当前群体中选出个体以生成交配池(MatingPool)的过程。所选出的这些个体应该具有良好的特性，以便产生优良的后代。选择压力：不同的选择策略将导致不同的选择压力，即下一代中父代个体复制数目的不同分配关系。较大的选择压力：使最优个体有较高的复制数目，从而使算法收敛速度快，但也较容易出现过早收敛现象。较小的选择压力：一般能使群体保持足够的多样性，从而增大了算法收敛到全局最后的概率，但算法的收敛速度一般较慢。15六、遗传操作（2）1基于适应值比例的选择（1）繁殖池选择繁殖池选择首先根据当前群体中个体的适应值。按照公式：其中：fi是群体中第i个成员的适应值，N是群体规模。则每个个体的繁殖量为：Ni=round(reli*N)reli=fi∑fiNi=1计算出群体中每个个体的繁殖量，即可将它们分别复制Ni个以生成一个临时群体，即繁殖池；再通过在繁殖池中选择个体进行交叉和变异形成下一代群体。显然，个体复制到繁殖池的数目越大，则它被选到进行遗传操作的机会就越大。Ni=0的个体被淘汰出进化过程。16六、遗传操作（3）1基于适应值比例的选择（2）转盘赌选择（RouletteWheelSelection）繁殖池选择首先根据当前群体中个体的适应值。按照公式：记为：pi。reli=fi∑fiNi=1根据选择概率{pi,i=1,2,…N}把圆盘分为N份，其中第i个扇形的中心角为2pi。采取转轮盘的方法进行选择，若某参照点落入第i个扇形内，则选择个体i。生成一个[0,1]之间的随机数r，若p1+p2+…+pi-1r≤p1+p2+…+pi则选择个体i。p1p2p32p1pi……轮盘赌选择策略不同于繁殖池选择策略在于：群体成员在转盘赌选择策略下都有被选择的机会，而在繁殖池选择策略下，具有较小适应值的个体将被剥夺生存的权利，但这些个体适应值的和一般有一定的规模。17六、遗传操作（4）1基于适应值比例的选择（3）波尔兹曼选择在群体的进化过程中,不同阶段需要不同的选择压力。早期阶段选择压力小，是希望较差的个体也有一定的生存机会，使得群体保持较高的多样性；后期阶段选择压力较大，是希望缩小搜索领域，加快最优解改善的速度。18六、遗传操作（5）1基于适应值比例的选择（3）波尔兹曼选择波尔兹曼选择就是利用函数(fi)=exp(fi/T)将适应值进行交换以改变原始的选择压力。其中：T是一个控制参数，T取得较大（小）值时具有较小（大）的选择压力，即适应值的相对比例变小（大），通过这个变换后再按照前面的选择方式进行父体的选择。19六、遗传操作（6）1基于排名的选择使用基于适应值比例的选择策略常常会出现过早收敛和停滞现象。避免这些现象的方法之一是：使用基于排名的选择(RankingSelection)：首先根据个体i的适应值在群体中的排名来分配其选择概率，然后根据这个概率使用转盘赌选择，这个个体的适应值不直接影响后代的数量。优点：无论对极小化问题还是极大化问题，不需要进行适应值的标准化和调节，可以直接使用原始适应值进行排名选择。20六、遗传操作（7）线性排名选择首先假设群体成员按适应值大小从好到坏依次排列为x1,x2,…,xN，然后根据一个线性函数分配选择概率pi。设线性函数pi=(a-b*i/(N+1))/N,i=1,2,…,N，其中a,b为常数。b=2(a-1)。又要求对任意i=1,2,…,N,有pi0，且p1p2…pN,故限定1a2。通常a=1.1。1Nipi线性排名选择21六、遗传操作（8）6.2交叉操作是用两个个体的遗传物交换产生新的个体，它可以把两个个体优良的“格式”传递到下一代的某个个体中，使其具有父辈的性能。如果交叉后得到的个体性能不佳，则可以在后面的复制操作中将被淘汰。交叉操作的具体步骤：(1)从交配池中随机取出要交配的一对个体；(2)根据位串长度L，对要交配的一对个体，随机选取[1,L-1]中的一个或多个整数k作为交叉点；(3)根据交叉概率pc(0pc1)实施交叉操作，配对个体在交叉点处，相互交换各自的部分内容，从而形成一对个体。22六、遗传操作（9）6.2交叉操作1.单点交叉对于从交配池中随机选择的两个串s1=a11a12…a1l1a1l2…a1Ls2=a21a22…a2l1a2l2…a2L随机选择一个交叉位x∈[1,2,…,L-1]，不妨设l1xl2，对两个串该位置右侧部分的染色体位串进行交换，产生两个子位位串个体为：s1’=a11a12…a1l1a122…a1Ls2’=a21a22…a2l1a1l2…a2L例：考虑如下两个11位变量的父个体：父个体1：01110011010父个体2：交叉点在位置5，交叉后生成两个个体：子个体1：01110子个体2：101010110101010110010110101100101单点交叉操作的信息量比较小，交叉点位置的选择可能带来较大的偏差。单点交叉的选择不利于长距模式的保留和重组，而且位串末尾的重要基因总是被交换。23六、遗传操作（10）6.2交叉操作2.多点交叉对于选定的两个个体位串,随机选择多个交叉点,构成交叉点集合:x1,x2,…,xk∈[1,2,…,L-1],xk