遗传算法小生境技术简介

《遗传算法小生境技术简介》由会员分享，可在线阅读，更多相关《遗传算法小生境技术简介（8页珍藏版）》请在金锄头文库上搜索。

1、遗传算法小生境技术简介 生物学上，小生境是指特定环境下的一种组织结构。在自然界中，往往特征，形 状相似的物种相聚在一起，并在同类中交配繁衍后代。在 SGA 中，交配完全是 随机的，在进化的后期，大量的个体集中于某一极值点上，在用遗传算法求解多 峰值问题时，经常只能找到个别的几个最优值，甚至往往得到是局部最优解。利 用小生境我们可以找到全部最优解。小生境技术就是将每一代个体划分为若干类，每个类中选出若干适应度较大的个 体作为一个类的优秀代表组成一个群，再在种群中，以及不同种群中之间，杂交， 变异产生新一代个体群。同时采用预选择机制和排挤机制或分享机制完成任务。 基于这种小生境的遗传算法（Nich

2、ed Gene tic Algori thms, NGA），可以更好的 保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多 峰函数的优化问题。模拟小生境技术主要建立在常规选择操作的改进之上。Cavichio在1970年提出 了基于预选择机制的选择策略，其基本做法是：当新产生的子代个体的适应度超 过其父代个体的适应度时，所产生的子代才能代替其父代而遗传到下一代群体中 去，否则父代个体仍保留在下一代群体中。由于子代个体和父代个体之间编码结 构的相似性，所以替换掉的只是一些编码结构相似的个体，故它能够有效的维持 群体的多样性，并造就小生境的进化环境。De Jong在1975年提出

3、基于排挤机 制的选择策略，其基本思想源于在一个有限的生存环境中，各种不同的生物为了 能够延续生存，他们之间必须相互竞争各种有限的生存资源。因此，在算法中设 置一个排挤因子CF （一般取CF=2或3），由群体中随机选取的1/CF个个体组 成排挤成员，然后依据新产生的的个体与排挤成员的相似性来排挤一些与预排挤 成员相类似的个体，个体之间的相似性可用个体编码之间的海明距离来度量。随 着排挤过程的进行，群体中的个体逐渐被分类，从而形成一个个小的生成环境， 并维持群体的多样性。Goldberg等在1987年提出了基于共享机制（Sharing）的小生境实现方法。 这种实现方法的基本思想是：通过反映个体之间

4、的相似程度的共享函数来调节群 体中各个个体的适应度，从而在这以后的群体进化过程中，算法能够依据这个调 整后的新适应度来进行选择运算，以维持群体的多样性，创造出小生境的进化环 境。共享函数（Sharing Function）是表示群体中两个个体之间密切关系程度的一个 函数，可记为S（d ）其中表示个体i和j之间的关系。例如，个体基因型之间 的海明距离就可以为一种共享函数。这里，个体之间的密切程度主要体现为个体 基因型的相似性或个体表现型的相似性上。当个体之间比较相似时，其共享函数 值就比较大；反之，当个体之间不太相似时，其共享函数值比较小。 共享度是某个个体在群体中共享程度的一中度量，它定义为该

5、个体与群体内其它 各个个体之间的共享函数值之和，用 S 表示：S = （ i=1 ， M）在计算出了群体中各个个体的共享度之后，依据下式来调整各个个体的适应度： F （X） =F （X） /S （i=1， M）由于每个个体的遗传概率是由其适应度大小来控制的，所以这种调整适应度的方 法就能够限制群体中个别个体的大量增加，从而维护了群体的多样性，并造就了 一种小生境的进化环境。下面介绍一个基于小生境概念的遗传算法。这个算法的基本思想是：首先两两比 较群体中各个个体之间的距离，若这个距离在预先的距离 L 之内的话，在比较 两者之间的适应度大小，并对其中适应值较低的个体施加一个较强的罚函数，极 大地降

6、低其适应度，这样，对于在预先指定的某一距离 L 之内的两个个体，其中 较差的个体经处理后其适应度变得更差，他在后面的进化过程被淘汰的概率就极 大。也就是说，在距离 L 内将只存在一个优良个体，从而既维护了群体的多样 性，又使得各个个体之间保持一定的距离，并使得个体能够在整个约束的空间中 分散开来，这样就实现了一种小生境遗传算法。 这个小生境算法的描述如下：算法NicheGA （1）设置进化代数计数器；随机生成M个初始群体P （t）,并 求出各个个体的适应度F （i=l, 2, M）o（2）依据各个个体的适应度对其进 行降序排列，记忆前N个个体（NM） .（3）选择算法。对群体P （t）进行比例

7、 选择运算，得到P （t）。（4）交叉选择。对选择的个体集合P （t）作单点 交叉运算，得到P （t）。（5）变异运算。对P （t）作均匀变异运算，得到P（t）。（6）小生境淘汰运算。将第（5）步得到的M个个体和第（2）步所记忆 的N个个体合并在一起，得到一个含有M+N个个体的新群体；对着M+N个个体, 按照下式得到两个个体x和x之间的海明距离：| x-x |=（）当| x-x |L 时，比较个体 x 和个体 x 的适应度大小，并对其中适应度较低的个体处以罚函 数：Fmin（x ，x）二Penalty （7）依据这M+N个个体的新适应度对各个个体进行 降序排列，记忆前N个个体。（8）终止条件判

8、断。若不满足终止条件，贝U：更 新进化代数记忆器t t+1，并将第（7）步排列中的前M个个体作为新的下一代 群体P（t）,然后转到第（3）步：若满足终止条件，贝U：输出计算结果，算法结 束。例 Shubert 函数的全局最优化计算。min f（x , x ）= s.t. -10 x 10（i=1， 2） 上述函数共有760个局部最优点，其中有18个是全局最优点，全局最优点处的 目标函数值是f （x， x ） =-186.731。用上述小生境遗传算法求解该例题时，可用下式进行目标函数值到个体适应度的 变换处理：F（ x ， x ）=L=202 （二进制编码串长度，其中每个变量用10位二进制编码来

9、表示）M=50T=500p =0.1p =0.1L=0.5（小生境之间的距离参数）Penlty=10 （罚函数） 使用上述参数进行了50次，试算，每次都可得到许多全局最优解下表为其中一 次运算所得到的最好的18个个体。从该表可以看出，从小生境的角度来数，该 算法得到了一个较好的结果。上述算法的特点保证了在一个函数峰内只存在一个 较优的个体，这样每一个函数峰就是一个小生境。基于小生境遗传算法的 Shubert 函数优化算法计算结果个体标号 xxf(x ， x )15.48284.8581-186.73125.4830-7.7083-186.73134.85815.4831-186.73144.8

10、581-7.0838-186.7315-4.4252-7.4983-186.7316-7.0832-7.0838-186.73175.4827-1.4249-186.73180.85805.4831-186.73194.8580-0.8009-186.73010-0.8009-7.7084-186.73011-0.80094.8581-186.73012-7.7088-0.7999-186.73013-7.7088-7.0831-186.73014-1.4256-0.8009-186.73015-0.8011-1.4252-186.73016-7.70755.4834-186.73017-7.

11、70884.8579-186.73018-7.0825-1.4249-186.730下面再介绍一种隔离小生境技术的遗传算法隔离小生境技术的基本概念及进化策略依照自然界的地理隔离技术,将遗传 算法的初始群体分为几个子群体,子群体之间独立进化,各个子群体的进化快慢 及规模取决于各个子群体的平均适应水平.由于隔离后的子群体彼此独立,界限 分明,可以对各个子群体的进化过程灵活控制。生物界中,竞争不仅存在于个体之 间,种群作为整体同样存在着竞争,适者生存的法则在种群这一层次上同样适用. 在基于隔离的小生境技术中,是通过将种群的规模同种群个体平均适应值相联系 来实现优胜劣汰、适者生存这一机制的.子群体平均

12、适应值高,则其群体规模就大, 反之,群体规模就小.生物界在进化过程中,适应环境的物种能得到更多的繁殖机 会,其后代不断地增多,但这种增加不是无限制的,否则就会引起生态环境的失衡. 在遗传算法中,群体的总体规模是一定的,为了保证群体中物种的多样性,就必须 限制某些子群体的规模,称子群体中所允许的最大规模为子群体最大允许规模 (maximum allowed scale),记为S .生物界中同样会出现某些物种因不适应环境 数量逐渐减少, 直至灭绝的现象.在隔离小生境机制中, 为了保持群体的多样性, 有时需要有意识地保护某些子群体, 使之不会过早地被淘汰, 并保持一定的进化 能力. 子群体的进化能力

13、是和子群体的规模相联系的, 要保证子群体的进化能力, 必须规定每一子群体生存的最小规模，称为子群体最小生存规模(minimum live scale)，记为S .在群体进化过程中，如果某一子群体在规定的代数内，持续表现 最差,应该使这个子群体灭绝,代之以搜索空间的新解,这一最劣子群体灭绝的机 制，定义为劣种不活(the worst die).子群体在进化过程中，如果出现两个子群体 相似或相同的现象，则去掉其中的一个，代之以搜索空间的新解，这种策略称为同 种互斥或种内竞争(intraspecific competition).解群中出现的新的子群体，在 进化的初期往往无法同已经得到进化的其它子群

14、体相竞争，如果不对此施加保护， 这些新解往往在进化的初期就被淘汰掉，这显然是我们所不希望的.为了解决这 个问题，必须对新产生的解加以保护，这种保护新解的策略叫幼弱保护(immature protection).子群体在进化过程中，如果收敛到或接近局部最优解，会出现进化 停滞的现象，此时应当以某种概率将该子群体去掉，代之以搜索空间的新解，此种 策略称为新老更替(the new superseding the old).在进化过程中，表现最优的 个体进化为最优解的概率最大，应当使它充分进化，故新老更替策略不能用于最 优子群体，这种做法称为优种保留(the best live).优种保留可以作用于最

15、好的 一个子群体，也可以作用于最好的几个子群体.基于隔离小生境技术的遗传算法步骤1) 编码:针对具体问题，选择合适的编码方案，完成问题解空间向遗传算法解空间 的转化.2) 产生初始群体:随机产生N个初始个体.3) 初始群体隔离:将N个初始个体均分给K个子群体,每个子群体含有的个体数均 为 N/K.4) 计算适应值:计算群体中所有个体的适应值.并保存适应值最高的个体.5) 确定子群体规模:子群体的规模同子群体的平均适应值相关，子群体的平均适 应值越大，其在下一代中拥有的个体就越多;反之，在下一代中拥有的个体就少.但数目必须满足最大允许规模和最小保护规模的限制，即第t+1代第k个子群体 的规模 n (t+1)满足 S Wn (t+1) WS .确定子群体规模的具体方法如下,首先给每个子群体都预分配S个个体，剩下的 个体根据子群体的平均适应值利用赌轮法选择，直到总的群体数量达到N为止. 子群体的平均适应值一般可简单取为f (t)= (1)式中f (t)为t代第k个子群体的平均适应值;f (t)为t代第k个子群体中第i 个个体的适应值；n (t+1)为t代第k个子群体的规模.子群体k第t+1代的规模 n (t+1)为：n (t+1)=N . f (t)/ (2) 子群体规模的确定也可以根据其平均适应水平用赌轮法确