《遗传算法的改进》ppt课件

1、遗传算法的改良遗传算法的改良n 自从1975年Holland系统地提出遗传算法的完好构造和实际以来，众多学者不断努力于推进遗传算法的开展，对编码方式、控制参数确实定、选择方式和交叉机理等进展了深化的探求，引入了动态战略和自顺应战略以改善遗传算法的性能，提出了各种改良的遗传算法。n下面引见几种改良的遗传算法。分层遗传算法n (1,2,)iNnNnGA iNN对于一个问题，首先随机地生成个样本，然后将它们分成 个子种群，每个子种群包含个样本，对每个子种群独立地运行各自的遗传算法，即它们为。这 个遗传算法最好在设置特性上有较大的差异，这样就可以为将来的高层遗传算法产生更多种类的优良模式。11, ,

2、(1,1)1 iiNRnR i j iN jnGAjNANA iGA 在每个子种群的遗传算法运行到一定代数后，将个遗传算法的结果记录到二维数组，则表示的结果种群的第 个个体。同时，将 各结果种群的平均适应度值纪录到数组中，表示的结果种群平均适应度值。1.1,2. ,1 ,11,;11 , ,1 ,1ANNRR inR jnxi jNxnR i xnR j xn选择基于数组即 个遗传算法的平均适应度值，对数组 代表的结果种群进行选择操作，一些结果种群由于它们的平均适应度高而被复制，甚至复制多次；另一些结果种群由于它们的种群平均适应度值低而被淘汰。交叉如果和被随机匹配到一起，而且从位置 进行交叉（

3、） 则和相互交换相应的部分。这一步相当ijGAGAnx于交换和中结果种群的个个体。3.1,1RNnN变异以很小的概率将少量的随机生成的新个体替换中随机抽取的个体。产生 个新的种群，重新开始在新的种群中继续各自的操作。继续循环操作，直至得到满意的结果。CHC算法n CHC算法是Eshelman于1991年提出的一种改良遗传算法，第一个C代表跨世代精英选择(Cross generational elitist selection)战略，H代表异物种重组，第二个C代表大变异。CHC算法与根本遗传算法不同点在于：n1、选择n通常，遗传算法是根据个体的顺应度复制个体完成选择操作的，而在CHC算法中，上世

4、代种群与经过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体。这一战略称为跨世代精英选择。n2、交叉n CHC算法运用的重组操作是对均匀交叉的一种改良。n当两个父个体位置相异的位数为m时，从中n随机选取m/2个位置，实行父个体位置的互换。显然，这样的操作对方式具有很强的破坏性。因此，确定一阀值，当个体间的海明间隔低于该阀值，不进展交叉操作。并且，随着种群的进化，逐渐减小该阀值。n3、变异nCHC算法在进化前期不采取变异操作，当种群进化到一定的收敛时期，从优秀个体中选择一部分个体进展初始化。初始化的方法是选择一定比例的位置，随机决议他们的值。这个比例值称为分散率，普通取0.35。自

5、顺应遗传算法n 遗传算法的参数中交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性, Pc 越大，新个体产生的速度就越快，然而 Pc过大时遗传方式被破坏的能够性也越大，使得具有高顺应度的个体结果很快就被破坏；但是假设Pc过小，会使搜索过程缓慢，不断停滞不前。对于变异概率Pm，假设Pm过小，就不易产生新的个体构造，假设Pm取值过大，那么遗传算法就变成了随机搜索算法。Srinvivas等提出了一种自顺应遗传算法， Pc和 Pm可以随顺应度自动改动。n算法思想: 对于顺应度高与群体平均顺应值的个体，相对应于较低的Pc和 Pm，使该解得以维护进入下一代；而低于平均

6、顺应值的个体，相对应于较高的Pc和 Pm，使该解被淘汰。1maxmax23maxmax4maxmax(),(),cmavgavgcavgavgavgmavgPPkffffffPkffkffffffPkffffff在自适应遗传算法中， 和按如下公式进行自适应调整：其中，群体中最大的适应度值每代群体的平均适应度值要交叉的两个个体重较大的适应度值要变异个体的适应度值n从上式可以看出，当顺应度度值越接近最大顺应度值时，交叉率和变异率就越小，当等于最大顺应度值时，交叉率和变异率为零，这种调整方法对于群体处于进化后期比较适宜，但对于进化初期不利，由于进化初期群体中的较优个体几乎不发生变化，容易使进化走向部

7、分最优解的能够性增大。为此，可以作进一步的改良，使群体中最大顺应度值的个体的交叉率和变异率分别为 和 。为了保证每一代的最优个体不被破坏，采用精英选择战略，使他们直接复制到下一代中。2cP2mP12max1max112max1max11212()(),()(),0.9,0.6,0.1,0.001cmcccavgavgccavgmmmavgavgmmavgccmmPPPPffPffffPPffPPffPffffPPffPPPP改进后， 和按如下公式进行自适应调整：取基于小生境技术的遗传算法n 根本遗传算法在求解多峰值函数的优化计算问题时, 往往只能找到几个部分最优解, 而无法收敛到全局最优解。这

8、是由于在规范的遗传算法的初期, 群体坚持了多样性, 但是到了算法后期, 群体的多样性遭到了破坏, 大量个体集中于某一个极值点附近, 它们的后代呵斥了近亲繁衍, 这样就易呵斥收敛于一个部分最优解, 而无法跳出该部分搜索 。n 在生物学中, 小生境是指特定环境下的一种生存环境, 一样的生物生活在同一个小生境中。自创此概念, 遗传算法将每一代个体划分为假设干类, 每个类中选出假设干顺应度较大的个体作为一个类的优秀代表组成一个种群, 再在种群中以及不同种群之间经过杂交、变异产生新一代个体群, 同时采用预选择机制或者排斥机制或共享机制完成选择操作。这样可以更好的坚持群体的多样性, 使其具有很高的全局寻优

9、才干和收敛速度。n 基于预选择机制的选择战略：当新产生的子代个体的顺应度超越其父代个体的顺应度时，所产生的子代个体才干替代其父代个体而遗传到下一代群体中，否那么父代个体仍保管在下一代群体中。由于子代个体和父代个体之间编码构造的类似性，所以交换掉的只是一些编码构造类似的个体，可以有效地维持群体的多样性，并培育小生境的进化环境。n 基于排斥机制的选择战略：思想来源于在一个有限的生存空间中，各种不同的生物为了可以延续生存，必需相互竞争各种有限资源。因此，在算法中设置一个排斥因子CFCF=2或3，由群体中随机地选取N/CF个个体组成排斥成员，然后根据新产生的个体与排斥成员之间的类似性来排斥一些类似个体

10、，随着排斥过程的进展，群体中的个体逐渐被分类，从而构成一个个小的生成环境，并维持了群体的多样性。n 共享法的选择战略：经过个体之间的类似程度的共享函数来调整群体中各个个体的顺应度，顺应度共享函数的直接目的是将搜索空间的多个不同峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体。混合遗传算法n 梯度法、爬山法、模拟退火等一些优化算法具有很强的部分搜索才干，假设交融这些优化方法的思想，构成一种混合遗传算法，是提高遗传算法运转效率和求解质量一个有效手段。n1、遗传算法与最速下降法相结合n主要改良是：在每次繁衍中产生的新的子代，都要以概率Ps判别能否需求进展线性搜索运算，经最速下降算子的线性搜索

11、运算产生的新的个体承继了其父代的优良质量。2:1( )( )()( )( )exp()( )( )kkMetrolpisijPf if jP ijf if jf if jt、遗传算法与模拟退火法相结合的混合遗传算法改进为：将接受准则应用于确定从当前解到新解 转移的概率背包问题背包问题 (knapsack problem)11,10-11,20nniinssppcixxin这是一个典型的最优化问题。基本背包问题：设 件物体的重量分别为使用价值分别为，一个背包能承受的总重量为 如何装包使总价值最大。第 件物体装包设 为变量，否则111212max.0,1,1,21,10iiniiiiiiinnpxscxstinxniiisppppsss这一问题的数学模型为现在用遗传算法求解这一问题、遗传编码。每个个体串的长度为实行二进制编码