小生境遗传算法概要.ppt

Goldberg等在1987年提出了基于共享机制（Sharing）的小生境实现方法。 这种实现方法的基本思想是：通过反映个体之间的相似程度的共享函数来调节群体中各个个体的适应度，从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算，以维持群体的多样性，创造出小生境的进化环境。 共享函数（Sharing Function）是表示群体中两个个体之间密切关系程度的一个函数， 基于共享机制算法步骤如下： step1 算法初始化，主要完成初四种群的建立，遗传参数的设定等； step2 完成种群中所有个体适应度的计算； step3 执行遗传操作，即选择，交叉，变异； step4 完成个体共享度的计算 step5 根据个体共享度重新计算每个个体的适应度 step6 对子代和父代个体的适应度大小进行比较 step7 用子代个体替换父代个体，形成新一代群体。 step8 若满足算法终止条件，则算法停止，否则返回step3. 算法类型 时间节点 标准遗传算法（SGA） 1960，开始进行遗传算法的相关研究； 1962，提出遗传算法； 60年代末期，行程呢过数学框架，实现简单形式的计算； 1975，Hollod 教授的专著《自然和人工系统的适配》出版, 标志着遗传算法的创立。 小生境遗传算法（NGA） 1970，Cavichio 提出了基于预选择机制的选 择策略 1975，De Jong提出基于排挤机制的选择策略 1987，Goldberg等提出了基于共享机制（Sharing）的小生境实现方法 PART COMPANY * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * * 数值分析 * 小生境遗传算法 专业：机械制造及其自动化 学号：2150220022 姓名：赵增伟 基本遗传算法（SGA）的缺憾： 一、求解过程可能会会出现早熟或者随机漫游现象 二、遗传算法不具备全局收敛性 原因：缺乏对种群多样性的保护机制 自然界中，“物以类聚，人以群分”是一种司空见惯的现象。生物总是倾向于与自己特性、形状相类似的生物生活在一起，一般总是与同类交配繁殖后代，这种交配方式在生物进化过程中具有积极作用。生物学上，有共同特性的组织被称为物种（species）。而物种赖以生存的资源环境，我们称之为小生境（niches）。 什么是小生境？ 在SGA（标准遗传算法） 中，交配完全是随机的，在进化的后期，大量的个体集中于某一极值点上，在用遗传算法求解多峰值问题时，经常只能找到个别的几个最优值，甚至往往得到是局部最优解。利用小生境我们可以找到全部最优解。 小生境技术就是讲每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间通过杂交，变异产生新一代个体群，同时采用预选择（Preselection）机制或排挤（crowding）机制或分享（sharing）机制完成选择操作。 · Cavichio 在1970年提出了基于预选择机制的选择策略： 其基本思想是当新产生的子代个体的适应度超过其父代个体的适应度时，所产生的子代才能代替其父代而遗传到下一代群体中去，否则父代个体仍保留在下一代群体中。 由于子代个体和父代个体之间编码结构的相似性，所以替换掉的只是一些编码结构相似的个体，故它能够有效的维持群体的多样性，并造就小生境的进化环境。 其预选择机制算法步骤如下： step1 算法初始化，主要完成初四种群的建立，遗传参数的设定等； step2 完成种群中所有个体适应度的计算； step3 执行遗传操作，即选择，交叉，变异； step4 针对新生成子串和父串的适应度大小进行比较，若子串的适应度比父串的适应度高，则子串替换父串；否则保持父串不变； step5 若满足算法终止条件，则算法停止，否则返回step2. De Jong在1975年提出基于排挤机制的选择策略： 其基本思 想源于在一个有限的生存环境中，各种不同的生物为了能够延续生存，他们之间必须相互竞争各种有限的生存资源。因此，在算法中设置一个排挤因子CF（一般取CF=2或3），由群体中随机选取的1/CF 个个体组成排挤成员，然后依据新产生的的个体与排挤成员的相似性来排挤一些与预排挤成员相类似的个体，个体之间的相似性可用个体编码之间的海明距离来度量。随着排挤过程的进行，群体中的个体逐渐被分类，从而形成一个个小的生成环境