小生境遗传算法.docx

生物学上，小生境是指特定环境下的一种组织结构。在自然界中，往往特征，形状相似的物种相聚在一起，并在同类中交配繁衍后代。在SGA 中，交配完全是随机的，在进化的后期，大量的个体集中于某一极值点上，在用遗传算法求解多峰值问题时，经常只能找到个别的几个最优值，甚至往往得到是局部最优解。利用小生境我们可以找到全部最优解。小生境技术就是将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群，再在种群中，以及不同种群中之间，杂交，变异产生新一代个体群。同时采用预选择机制和排挤机制或分享机制完成任务。基于这种小生境的遗传算法（Niched Genetic Algorithms，NGA），可以更好的保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多峰函数的优化问题。模拟小生境技术主要建立在常规选择操作的改进之上。Cavichio 在1970年提出了基于预选择机制的选择策略，其基本做法是：当新产生的子代个体的适应度超过其父代个体的适应度时，所产生的子代才能代替其父代而遗传到下一代群体中去，否则父代个体仍保留在下一代群体中。由于子代个体和父代个体之间编码结构的相似性，所以替换掉的只是一些编码结构相似的个体，故它能够有效的维持群体的多样性，并造就小生境的进化环境。De Jong在1975年提出基于排挤机制的选择策略，其基本思想源于在一个有限的生存环境中，各种不同的生物为了能够延续生存，他们之间必须相互竞争各种有限的生存资源。因此，在算法中设置一个排挤因子CF（一般取CF=2或3），由群体中随机选取的1/CF 个个体组成排挤成员，然后依据新产生的的个体与排挤成员的相似性来排挤一些与预排挤成员相类似的个体，个体之间的相似性可用个体编码之间的海明距离来度量。随着排挤过程的进行，群体中的个体逐渐被分类，从而形成一个个小的生成环境，并维持群体的多样性。Goldberg等在1987年提出了基于共享机制（Sharing）的小生境实现方法。这种实现方法的基本思想是：通过反映个体之间的相似程度的共享函数来调节群体中各个个体的适应度，从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算，以维持群体的多样性，创造出小生境的进化环境。共享函数（Sharing Function）是表示群体中两个个体之间密切关系程度的一个函数，可记为S（d ）其中表示个体i和j之间的关系。例如，个体基因型之间的海明距离就可以为一种共享函数。这里，个体之间的密切程度主要体现为个体基因型的相似性或个体表现型的相似性上。当个体之间比较相似时，其共享函数值就比较大；反之，当个体之间不太相似时，其共享函数值比较小。共享度是某个个体在群体中共享程度的一中度量，它定义为该个体与群体内其它各个个体之间的共享函数值之和，用S 表示：S = （i=1， ，M）在计算出了群体中各个个体的共享度之后，依据下式来调整各个个体的适应度：F （X）=F （X）/S （i=1， ，M）由于每个个体的遗传概率是由其适应度大小来控制的，所以这种调整适应度的方法就能够限制群体中个别个体的大量增加，从而维护了群体的多样性，并造就了一种小生境的进化环境。下面介绍一个基于小生境概念的遗传算法。这个算法的基本思想是：首先两两比较群体中各个个体之间的距离，若这个距离在预先的距离L 之内的话，在比较两者之间的适应度大小，并对其中适应值较低的个体施加一个较强的罚函数，极大地降低其适应度，这样，对于在预先指定的某一距离L之内的两个个体，其中较差的个体经处理后其适应度变得更差，他在后面的进化过程被淘汰的概率就极大。也就是说，在距离L 内将只存在一个优良个体，从而既维护了群体的多样性，又使得各个个体之间保持一定的距离，并使得个体能够在整个约束的空间中分散开来，这样就实现了一种小生境遗传算法。这个小生境算法的描述如下：算法 NicheGA （1）设置进化代数计数器；随机生成M个初始群体P（t），并求出各个个体的适应度F （i=1，2，M）。（2） 依据各个个体的适应度对其进行降序排列，记忆前N个个体（NM）.(3) 选择算法。对群体P（t）进行比例选择运算，得到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 |f（p ）,则用c 代替p ，否则保留p 。如果f（c ）f（p ），则用c 替换p ，否则保留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） 对其进行杂夹和变异，产生两个子个体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提出。该算法属拥挤算法的范畴，采用种群中的若干个体相互竞争的模式，竞争的内容包括适应值和个体之间的距离。竞争选择出的老个体被新个体产生的子个体替换。算法的过程如下：多小生境拥挤算法（重复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 。Cedeno 还给出了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之间的距离， 是控制共享函数形状的参数，一般取 =1（线形共享函数）。两个个体之间共享函数值越大，则两个个体越接近。（2） 计算种群中个体的小生境数m m = 其中，N 是种群规模。个体的小生境数越大，则该个体周围绕着越多其它个体。（3） 计算种群中个体共享后的适应值f f =f / m （4） 用个体共享后的适应值进行选择，杂交和变异出新的个体，生成新一代种群。Deb和Goldberg 在假设解空间中峰均匀分布并且峰半径相同的前提下，提出计算峰半径的计算公式。此外它们还提供了一种基于峰半径的限制交配策略，从而保证所有的杂交均在同一物种进行，确保了后代和父母的均属于同一小生境。标准适应值共享算法计算距离的时间复杂度为O（N ）。5 清除算法清除（Clearing）算法由Petrowski 提出。该算法属于适应值共性算法范畴，事先需要给出解空间的小生境半径 （重要参数）和小生境的容量 （次要参数），并假设解空间中峰值半径均相同。算法的过程如下：清除算法（G）（1） 按照适应值对个体进行降序排列。（2） 将第一个体指定为第一个小生境中心。（3） 从第二个个体开始顺序执行下列步骤到最后一个个体：（3.1）如果当前个体到所有已指定小生境中心的距离均大于，则该个体被指定为一个新的小生境中心。该个成为优胜者。（3.2）如果当前个体到某个已指定的小生境中心的距离小于，并且该小生境个数小于，则该个体加入到该小生境中去，该小生境的个体总数增加1。该个体成为优胜者。（3.3）其它个体均为失败者。（3.4）维持所有优胜者的适应度不变，将所有失败者的适应值置为0。（4）用个体修改后的适应值进行选择，杂交和变异出新个体，生成新一代种群。清除算法计算距离的时间复杂度为O（kN），其中k是该算法维持的小生境数量。如果将优胜者的小生境数看为一，而将失败者的小生境看作无穷大，则清除算法也可看作标准适应值共享算法的改进。6 结合适应值共享的自适应k均值聚类算法结合适应值共享的自适应算法k均值聚类算法（Adaptive k-mean clustering with fitness sharing）算法由Yin 和German提出。该算法属于适应值共性算法范畴，事先需要给出解空间中小生境中新建的最小距离 和小生境中的个体到该小生境中心之间的最大距离 。解空间中峰半径可能不相同。算法的过程如下：结合适应值共享的自适应k均值均类算法（重复G代）（1） 按照适应值对个体进行降序排列。（2） 产生在1，N之间的随机整数k（初始小生境个数）。（3） 将前k个个体分别放入不同的小生境中并成为小生境中心。确保所有 小生境中心间距离大于 ，如果不能满足这一条件，则合并小生境，新的小生境中心就是该小生境中所有个体的中心。（4） 对于其它N-k个个体中的每一个，计算其与当前所有想生境中心之间 的距离。如果距离大于 ，则生成新的小生境，该个体成为新小生境的中心。否则将该个体安排到距离最近的小生境中去。据需要确保所有小生境中心间的距离均大于 ，如果不能满足这一条件，则需要合并小生境。（5） 所有个体均被安置完毕后，固定小生境的中心，将所有个体按照最小 距离原则安排到最近的小生境中去。（6） 计算计算种群个体的小生境数m m =n - n （d /2 ） 若x C 其中，n 是第c个小生境中包含个个体总数，d 是个体i与它归属的小生境中心之间的距离，x 是第i个个体，C 第c 个小生境的个体基， 是控制函数形状的参数，通常 =1。（7） 用公式计算个体共享后的适应值。（8） 用个体共享后的适应值进行选择，杂交和变异出新的个体，生成新一 代个体种群。结合适应值共享的自适应性k均值聚类算法计算距离的时间复杂度为O（Kn）。7 动态小生境共享算法动态小生境共享算方法（Dynamic niche sharing）是由Miller和Shaw 提出。该算法属于适应值共享算法范畴，事先需要给出解空间中小生境的半径 和小生境的数量k。算法的过程如下；动态小生境共享算法（重复G代）（1） 按照适应值对个体进行降序排列。（2） 将第一个个体指定为第一个小生境中心。（3） 从第二个个体开始顺序执行下列步骤到最后一个个体：（3.1）如果当前个体与所有已指定的小生境中心之间的距离大于 ，而且已指定的小生境数量小于k，则形成一个新的小生境，该个体成为新小生境的中心。（3.2）如果当前个体与所有小生境中心之间的距离均大于 ，而且已指定的小生境数量不小于k，则该个体成为独立个体。（4） 对于那些属于某个小生境的个体，其小生境数就是它所属的小生境中个体的数量。对于那些独立个体，采用公式计算小生境数。（5） 用公式计算个体共享后的适应值。（6） 用共享后的适应值进行选择，杂交和变异出新的个体，生成新一代种群。动态小生境共享算法计算距离的时间复杂度为O（Kn）。8 自适应小生境算法自适应小生境算法（Adaptive nicking）由Goldberg 和 Wang 提出。该算法属于适应值共享算法范畴，事先需要给出解空间中小生境的半径 和小生境的数量k。算法包含两个分别被称为顾客和商家的个体群，利用这两个个体群的共同演化实现多峰优化的目的。顾客群类似于其它适应值共享算法中的种群，而商家群则代表搜索空间中峰的集合。商家群的个体数量k略大于其它适应值共享算法中的小生境树立功能。顾客群中的个体的适应值与其它适应值共享算法中个体的适应值相同，而商家群中的个体的适应值是属于该商家所有顾客的适应值之和。算法需要首先在搜索空间中随机放置商家群的个体，其余的过程如下；自适应小生