小生境遗传算法选编课件讲课稿.ppt

《小生境遗传算法选编课件讲课稿.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、小生境遗传算法选编课件自然界中，“物以类聚，人以群分”是一种司空见惯的现象。生物总是倾向于与自己特性、形状相类似的生物生活在一起，一般总是与同类交配繁殖后代，这种交配方式在生物进化过程中具有积极作用。生物学上，有共同特性的组织被称为物种（species）。而物种赖以生存的资源环境，我们称之为小生境（niches）。什么是小生境？在SGA（标准遗传算法）中，交配完全是随机的，在进化的后期，大量的个体集中于某一极值点上，在用遗传算法求解多峰值问题时，经常只能找到个别的几个最优值，甚至往往得到是局部最优解。利用小生境我们可以找到全部最优解。小生境技术就是讲每一代个体划分为若干类，

2、每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间通过杂交，变异产生新一代个体群，同时采用预选择（Preselection）机制或排挤（crowding）机制或分享（sharing）机制完成选择操作。·Cavichio在1970年提出了基于预选择机制的选择策略：其基本思想是当新产生的子代个体的适应度超过其父代个体的适应度时，所产生的子代才能代替其父代而遗传到下一代群体中去，否则父代个体仍保留在下一代群体中。由于子代个体和父代个体之间编码结构的相似性，所以替换掉的只是一些编码结构相似的个体，故它能够有效的维持群体的多样性，并造就小生境

3、的进化环境。其预选择机制算法步骤如下：step1算法初始化，主要完成初四种群的建立，遗传参数的设定等；step2完成种群中所有个体适应度的计算；step3执行遗传操作，即选择，交叉，变异；step4针对新生成子串和父串的适应度大小进行比较，若子串的适应度比父串的适应度高，则子串替换父串；否则保持父串不变；step5若满足算法终止条件，则算法停止，否则返回step2.DeJong在1975年提出基于排挤机制的选择策略：其基本思想源于在一个有限的生存环境中，各种不同的生物为了能够延续生存，他们之间必须相互竞争各种有限的生存资源。因此，在算法中设置一个排挤因子CF（一般取CF=2

4、或3），由群体中随机选取的1/CF个个体组成排挤成员，然后依据新产生的的个体与排挤成员的相似性来排挤一些与预排挤成员相类似的个体，个体之间的相似性可用个体编码之间的海明距离来度量。随着排挤过程的进行，群体中的个体逐渐被分类，从而形成一个个小的生成环境，并维持群体的多样性。基于排挤机制算法的具体实施步骤如下：step1算法初始化，主要完成初四种群的建立，遗传参数的设定，排挤因子CF的确定等；step2完成种群中所有个体适应度的计算；step3执行遗传操作，即选择，交叉，变异；step4随机确定当前群体中1/CF个个体作为排挤因子成员；step5完成新生个体与排挤因子成员相似性

5、的比较；step6新群体的生成，即使用新生成的个体选择排挤因子成员中最相似的个体完成替换；step7若满足算法终止条件，则算法停止，否则返回step2。Goldberg等在1987年提出了基于共享机制（Sharing）的小生境实现方法。这种实现方法的基本思想是：通过反映个体之间的相似程度的共享函数来调节群体中各个个体的适应度，从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算，以维持群体的多样性，创造出小生境的进化环境。共享函数（SharingFunction）是表示群体中两个个体之间密切关系程度的一个函数，基于共享机制算法步骤如下：step1算法

6、初始化，主要完成初四种群的建立，遗传参数的设定等；step2完成种群中所有个体适应度的计算；step3执行遗传操作，即选择，交叉，变异；step4完成个体共享度的计算step5根据个体共享度重新计算每个个体的适应度step6对子代和父代个体的适应度大小进行比较step7用子代个体替换父代个体，形成新一代群体。step8若满足算法终止条件，则算法停止，否则返回step3.算法类型时间节点标准遗传算法（SGA）1960，开始进行遗传算法的相关研究；1962，提出遗传算法；60年代末期，行程呢过数学框架，实现简单形式的计算；1975，Hollod教授的专著《自然和人工系统的适配》

7、出版,标志着遗传算法的创立。小生境遗传算法（NGA）1970，Cavichio提出了基于预选择机制的选择策略1975，DeJong提出基于排挤机制的选择策略1987，Goldberg等提出了基于共享机制（Sharing）的小生境实现方法遗传算法与小生境遗传时间节点对比：例：Shubert函数（多元多峰）#minf(x,y)=(sum(i*cos((i+1)*x)+i))*(sum(i*cos((i+1)*y)+i)),#i=1:5,-10<=x,y<=10#该函数是一个多模态函数,在其定义域内共有760个局部最优点