遗传算法的改进ppt课件.ppt
遗传算法的改进,遗传算法的改进,自从1975年Holland系统地提出遗传算法的完整结构和理论以来，众多学者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定、选择方式和交叉机理等进行了深入的探究，引入了动态策略和自适应策略以改善遗传算法的性能，提出了各种改进的遗传算法。下面介绍几种改进的遗传算法。,分层遗传算法,CHC算法,CHC算法是Eshelman于1991年提出的一种改进遗传算法，第一个C代表跨世代精英选择(Cross generational elitist selection)策略，H代表异物种重组，第二个C代表大变异。CHC算法与基本遗传算法不同点在于：1、选择通常，遗传算法是依据个体的适应度复制个体完成选择操作的，而在CHC算法中，上世代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体。这一策略称为跨世代精英选择。,2、交叉 CHC算法使用的重组操作是对均匀交叉的一种改进。当两个父个体位置相异的位数为m时，从中随机选取m/2个位置，实行父个体位置的互换。显然，这样的操作对模式具有很强的破坏性。因此，确定一阀值，当个体间的海明距离低于该阀值，不进行交叉操作。并且，随着种群的进化，逐渐减小该阀值。3、变异CHC算法在进化前期不采取变异操作，当种群进化到一定的收敛时期，从优秀个体中选择一部分个体进行初始化。初始化的方法是选择一定比例的位置，随机决定他们的值。这个比例值称为扩散率，一般取0.35。,自适应遗传算法,遗传算法的参数中交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性, Pc 越大，新个体产生的速度就越快，然而 Pc过大时遗传模式被破坏的可能性也越大，使得具有高适应度的个体结果很快就被破坏；但是如果Pc过小，会使搜索过程缓慢，一直停滞不前。对于变异概率Pm，如果Pm过小，就不易产生新的个体结构，如果Pm取值过大，那么遗传算法就变成了随机搜索算法。Srinvivas等提出了一种自适应遗传算法， Pc和 Pm能够随适应度自动改变。,算法思想: 对于适应度高与群体平均适应值的个体，相对应于较低的Pc和 Pm，使该解得以保护进入下一代；而低于平均适应值的个体，相对应于较高的Pc和 Pm，使该解被淘汰。,从上式可以看出，当适应度度值越接近最大适应度值时，交叉率和变异率就越小，当等于最大适应度值时，交叉率和变异率为零，这种调整方法对于群体处于进化后期比较合适，但对于进化初期不利，因为进化初期群体中的较优个体几乎不发生变化，容易使进化走向局部最优解的可能性增大。为此，可以作进一步的改进，使群体中最大适应度值的个体的交叉率和变异率分别为 和 。为了保证每一代的最优个体不被破坏，采用精英选择策略，使他们直接复制到下一代中。,基于小生境技术的遗传算法,基本遗传算法在求解多峰值函数的优化计算问题时, 往往只能找到几个局部最优解, 而无法收敛到全局最优解。这是因为在标准的遗传算法的初期, 群体保持了多样性, 但是到了算法后期, 群体的多样性遭到了破坏, 大量个体集中于某一个极值点附近, 它们的后代造成了近亲繁殖, 这样就易造成收敛于一个局部最优解, 而无法跳出该局部搜索 。 在生物学中, 小生境是指特定环境下的一种生存环境, 相同的生物生活在同一个小生境中。借鉴此概念, 遗传算法将每一代个体划分为若干类, 每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群, 再在种群中以及不同种群之间通过杂交、变异产生新一代个体群, 同时采用预选择机制或者排挤机制或共享机制完成选择操作。这样可以更好的保持群体的多样性, 使其具有很高的全局寻优能力和收敛速度。,基于预选择机制的选择策略：当新产生的子代个体的适应度超过其父代个体的适应度时，所产生的子代个体才能代替其父代个体而遗传到下一代群体中，否则父代个体仍保留在下一代群体中。由于子代个体和父代个体之间编码结构的相似性，所以替换掉的只是一些编码结构相似的个体，能够有效地维持群体的多样性，并造就小生境的进化环境。 基于排挤机制的选择策略：思想起源于在一个有限的生存空间中，各种不同的生物为了能够延续生存，必须相互竞争各种有限资源。因此，在算法中设置一个排挤因子CF（CF=2或3），由群体中随机地选取N/CF个个体组成排挤成员，然后依据新产生的个体与排挤成员之间的相似性来排挤一些相似个体，随着排挤过程的进行，群体中的个体逐渐被分类，从而形成一个个小的生成环境，并维持了群体的多样性。 共享法的选择策略：通过个体之间的相似程度的共享函数来调整群体中各个个体的适应度，适应度共享函数的直接目的是将搜索空间的多个不同峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体。,混合遗传算法,梯度法、爬山法、模拟退火等一些优化算法具有很强的局部搜索能力，如果融合这些优化方法的思想，构成一种混合遗传算法，是提高遗传算法运行效率和求解质量一个有效手段。1、遗传算法与最速下降法相结合主要改进是：在每次繁殖中产生的新的子代，都要以概率Ps判断是否需要进行线性搜索运算，经最速下降算子的线性搜索运算产生的新的个体继承了其父代的优良品质。,背包问题 (knapsack problem),
