《遗传算法小生境技术简介》由会员分享，可在线阅读，更多相关《遗传算法小生境技术简介（8页珍藏版）》请在金锄头文库上搜索。
1、遗传算法小生境技术简介生物学上，小生境是指特定环境下的一种组织结构。在自然界中，往往特征，形状相似的物种相聚在一起，并在同类中交配繁衍后代。在 SGA 中，交配完全是随机的，在进化的后期，大量的个体集中于某一极值点上，在用遗传算法求解多峰值问题时，经常只能找到个别的几个最优值，甚至往往得到是局部最优解。利用小生境我们可以找到全部最优解。小生境技术就是将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群，再在种群中，以及不同种群中之间，杂交，变异产生新一代个体群。同时采用预选择机制和排挤机制或分享机制完成任务。基于这种小生境的遗传算法（Niched Genet
2、ic Algorithms，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 之内的话，在比较两者之间的适应度大小，并对其中适应值较低的个体施加一个较强的罚函数，极大地降低其适应度，这样，对于在预先指定的某一距离 L 之
6、内的两个个体，其中较差的个体经处理后其适应度变得更差，他在后面的进化过程被淘汰的概率就极大。也就是说，在距离 L 内将只存在一个优良个体，从而既维护了群体的多样性，又使得各个个体之间保持一定的距离，并使得个体能够在整个约束的空间中分散开来，这样就实现了一种小生境遗传算法。这个小生境算法的描述如下：算法 NicheGA （1）设置进化代数计数器；随机生成 M 个初始群体 P（t），并求出各个个体的适应度 F （i=1，2，M）。（2） 依据各个个体的适应度对其进行降序排列，记忆前 N 个个体（Nf（p ）,则用 c 代替 p ，否则保留 p 。如果 f（c ）f（p ），则用 c 替换 p ，否
7、则保留 p 。如果 f（c ）f（p ），则用 c 替换 p ，否则保留 p 。如果 f（c ）f（p ），则用 c 替换 p ，否则保留 p 。其中，N 是种群规模，的 d（i，j）是个体 i 和个体 j 之间的距离。2 限制锦标赛算法限制锦标赛选择（Restricted tournament selection RTS）算法由 Harik 提出。该算法属于拥挤算法范畴，采用了个体与种群中其它个体进行竞争的模式，竞争的内容包括适应值和个体之间的距离。该算法的过程如下：限制锦标赛算法（重复 G 代）重复下列步骤 N/2 次：（1） 用有放回的方式随机选择两个父个体 p 和 p 。（2） 对其进
8、行杂夹和变异，产生两个子个体 c 和才 c 。（3） 分别为 c 和 c 从当前的种群中随机的选择出 w 个个体。（4） 不失一般性，设 d 和 d 分别是 w 个个体的中与 c 和 c 距离最近的两个个体。（5） 如果 f（c ）f（d ），则用 c 替 d 换，否则保留 d 。如果 f（c ）f（d ），则用 c 替换 d ，否则保留 d 。3 多小生境拥挤算法多小生境拥挤算法（Multi-niche crowding，MNC）由 Cedeno 提出。该算法属拥挤算法的范畴，采用种群中的若干个体相互竞争的模式，竞争的内容包括适应值和个体之间的距离。竞争选择出的老个体被新个体产生的子个体替换
9、。算法的过程如下：多小生境拥挤算法（重复 G 代）重复下列步骤 N/2 次：（1） 用有放回的方式随机选父个体 p 。（2） 从种群中随机选择 C 个体作为 p 的交配候选集，从中选出与 p 最接近的个体 p 。（3） 对 p 和 p 进行杂交和变异，产生两个个体 c 和 c 。（4） 分别为 c 和 c 从中当前种群中各随机选择出 C 群个体，每群个体包含 w 个个体。（5） 每一群个体都选出一个与对应字个体距离最近的个体。这样就为每个个体产生了 C 个替换候选个体。（6） 不失一般性，设 d 和 d 是两个替换候选集中适应值最低的个体。（7） 用 c 替换 d ，用 c 替换 d 。Ced
10、eno 还给出了 C ，w 和 C 的最优参数值。C 应该在区间2，4内，C 和 w至少应该两倍于用户希望找到的全局峰个数。该算法的步骤 2 提出了一中基于试探性的方法的限制交配策略。4 标准适应值共享算法标准适应值共享算法（Standard fitness sharing SH）由 Goldberg 和Richardson 提出。该算法属于适应值共享算法范畴，事先需要给出解空间中小生境的半径，并假设解空间中峰半径均相同。算法的过程如下：标准的适应值共享算法（重复 G 代）（1） 计算种群中个体之间的共享函数值 sh（d ）sh（d ）= 其中， 是事先给出的峰半径，d 是个体 i 和个体 j
11、 之间的距离， 是控制共享函数形状的参数，一般取 =1（线形共享函数）。两个个体之间共享函数值越大，则两个个体越接近。（2） 计算种群中个体的小生境数 m m = 其中，N 是种群规模。个体的小生境数越大，则该个体周围绕着越多其它个体。（3） 计算种群中个体共享后的适应值 f f =f / m （4） 用个体共享后的适应值进行选择，杂交和变异出新的个体，生成新一代种群。Deb 和 Goldberg 在假设解空间中峰均匀分布并且峰半径相同的前提下，提出计算峰半径的计算公式。此外它们还提供了一种基于峰半径的限制交配策略，从而保证所有的杂交均在同一物种进行，确保了后代和父母的均属于同一小生境。标准适
12、应值共享算法计算距离的时间复杂度为 O（N ）。5 清除算法清除（Clearing）算法由 Petrowski 提出。该算法属于适应值共性算法范畴，事先需要给出解空间的小生境半径 （重要参数）和小生境的容量 （次要参数），并假设解空间中峰值半径均相同。算法的过程如下：清除算法（G）（1） 按照适应值对个体进行降序排列。（2） 将第一个体指定为第一个小生境中心。（3） 从第二个个体开始顺序执行下列步骤到最后一个个体：（3.1）如果当前个体到所有已指定小生境中心的距离均大于，则该个体被指定为一个新的小生境中心。该个成为优胜者。（3.2）如果当前个体到某个已指定的小生境中心的距离小于，并且该小生境个
13、数小于，则该个体加入到该小生境中去，该小生境的个体总数增加 1。该个体成为优胜者。（3.3）其它个体均为失败者。（3.4）维持所有优胜者的适应度不变，将所有失败者的适应值置为 0。（4）用个体修改后的适应值进行选择，杂交和变异出新个体，生成新一代种群。清除算法计算距离的时间复杂度为 O（kN），其中 k 是该算法维持的小生境数量。如果将优胜者的小生境数看为一，而将失败者的小生境看作无穷大，则清除算法也可看作标准适应值共享算法的改进。6 结合适应值共享的自适应 k 均值聚类算法结合适应值共享的自适应算法 k 均值聚类算法（Adaptive k-mean clustering with fitne
14、ss sharing）算法由 Yin 和 German 提出。该算法属于适应值共性算法范畴，事先需要给出解空间中小生境中新建的最小距离 和小生境中的个体到该小生境中心之间的最大距离 。解空间中峰半径可能不相同。算法的过程如下：结合适应值共享的自适应 k 均值均类算法（重复 G 代）（1） 按照适应值对个体进行降序排列。（2） 产生在1，N之间的随机整数 k（初始小生境个数）。（3） 将前 k 个个体分别放入不同的小生境中并成为小生境中心。确保所有 小生境中心间距离大于 ，如果不能满足这一条件，则合并小生境，新的小生境中心就是该小生境中所有个体的中心。（4） 对于其它 N-k 个个体中的每一个，
15、计算其与当前所有想生境中心之间 的距离。如果距离大于 ，则生成新的小生境，该个体成为新小生境的中心。否则将该个体安排到距离最近的小生境中去。据需要确保所有小生境中心间的距离均大于 ，如果不能满足这一条件，则需要合并小生境。（5） 所有个体均被安置完毕后，固定小生境的中心，将所有个体按照最小 距离原则安排到最近的小生境中去。（6） 计算计算种群个体的小生境数 m m =n - n （d /2 ） 若 x C 其中，n 是第 c 个小生境中包含个个体总数，d 是个体 i 与它归属的小生境中心之间的距离，x 是第 i 个个体，C 第 c 个小生境的个体基， 是控制函数形状的参数，通常 =1。（7）
16、用公式计算个体共享后的适应值。（8） 用个体共享后的适应值进行选择，杂交和变异出新的个体，生成新一 代个体种群。结合适应值共享的自适应性 k 均值聚类算法计算距离的时间复杂度为 O（Kn）。7 动态小生境共享算法动态小生境共享算方法（Dynamic niche sharing）是由 Miller 和 Shaw 提出。该算法属于适应值共享算法范畴，事先需要给出解空间中小生境的半径 和小生境的数量 k。算法的过程如下；动态小生境共享算法（重复 G 代）（1） 按照适应值对个体进行降序排列。（2） 将第一个个体指定为第一个小生境中心。（3） 从第二个个体开始顺序执行下列步骤到最后一个个体：（3.1）如果当前个体与所有已指定的小生境中心之间的距离大于 ，而且已指定的小生境数量小于 k，则形成一个新的小生境，该个体成为新小生境的中心。（3.2）如果当前个体与所有小生境中心之间的距离均大于 ，而且已指定的小生境数量不小于 k，则该个体成为
