典型小生境遗传算法原理与性能比较分析*

赵 越，茹婷婷

(1.吉林建筑大学计算机科学与工程学院，吉林长春130118；2.吉林建筑大学基础科学部，吉林长春130118)

近年来，随着智能计算领域各项研究的不断深入，人们对于遗传算法的认识也在不断丰富和提升.与传统意义上的优化算法相比，遗传算法的通用性和鲁棒性更强，故其在各个领域的应用很广［1-2］.尽管如此，基本遗传算法本身也存在不尽如人意的地方，主要表现在两个方面：一是问题的求解过程中可能会出现早熟或随机漫游现象；二是遗传算法不具备全局收敛性［3-4］.对于这些不足，究其根本原因在于缺乏对种群多样性的保护机制.针对各种优化问题而言，求解的目标往往更加全面，即需要全局最优解和局部最优解.在遗传算法中引入小生境技术能够很好地解决这个问题.

1 小生境技术与物种形成过程

在自然环境当中，“物以类聚，人以群分”是一种普遍的现象.这说明生物往往倾向于和其本身在性状和特征等方面相似的同类在一起生活，并与其同类交配完成后代的增殖.生物的这种生存特点和增殖方式是有其积极意义的.在生物学上，小生境(niche)是指特定环境下一种组织的功能，我们也常常把具有共同特性的组织称为物种(species).

为了说明小生境技术相对于基本遗传算法的优势所在，我们考察基本遗传算法应用于多峰函数最大值点的求解与搜索过程.对于如(1)所示多峰函数，欲求其最大值点.

若选用基本遗传算法，初始群体的产生常常是以均匀分布的方式随机产生.在算法的初始阶段，个体在函数的定义域内分布范围相对较宽.伴随着整个优化过程的不断推进，群体将逐渐聚集到一个山峰上，我们得到的并非是全部的解.产生这种现象的根本原因是由于单一群体的规模有限，无法完成对于定义域内所有点的探测.而在实际应用中，常常也需要得到其他山峰的情况.于是我们考虑生物界中的真实情况，也就是说交叉操作并非完全随机，它受物种类别、所在区域、性别等条件的限制.尽管加入某些限制会对算法的性能造成一定影响，但从另一个角度讲它能够以一定区域为限制保持种群的多样性，这是有现实意义并被实验研究证明为有效的方法.因而我们需要对现有具有代表性的小生境技术进行研究.

2 典型小生境技术研究

对于小生境机制的模拟方法，近年来已经出现多种.归纳起来主要有三类，具体如下.

2.1 基于预选择机制的小生境技术

基于预选择机制的小生境技术是由Cavicchio于1970年在已有遗传算法理论基础上首先提出的.该预选择机制规定，只有新生成子串的适应度超过其父串的时候，子串才能完成对父串的替换.也就是说，这种机制仅允许子代替换与其本身性状相似的个体(即父代个体)，因而该方法能够有效保持群体的多样性.更进一步讲，Cavicchio认为该方法可以在群体规模较小的条件下仍能保持群体的多样性.基于预选择机制算法的实现步骤如下.

step1 算法初始化.主要完成初始种群的建立，遗传参数的设定等.

step2 完成种群中所有个体适应度的计算.

step3 执行遗传操作，即选择、交叉、变异.

step4 针对新生成子串和父串的适应度大小进行比较.若子串的适应度比父串的适应度高，则子串替换父串；否则保持父串不变.

step5 若满足算法终止条件，则算法停止；否则返回step2.

2.2 基于拥挤机制的小生境技术

1975年，De Jong对Cavicchi的预选择机制进行了改进，提出基于拥挤机制的小生境技术.在该排挤机制中，De Jong针对每代群体选择代间覆盖的机制，根据相似度来完成群体中一部分个体的替换.算法的具体实现步骤如下.

step1 算法初始化.主要完成初始种群的建立，遗传参数的设定，排挤因子CF的确定等.

step2 完成种群中所有个体适应度的计算.

step3 执行遗传操作，即选择、交叉、变异.

step4 随机确定当前群体中1/CF个个体作为排挤因子成员.

step5 完成新生成个体与排挤因子成员相似性的比较.

step6 新群体的生成.即使用新生成的个体选择排挤因子成员中最相似的个体完成替换.

step7 若满足算法终止条件，则算法停止；否则返回step2.

对于以上算法，执行的起始过程由于群体中个体的差别不大，故替换操作多数情况下为随机选择；随着算法不断执行，群体中个体将形成多个小生境并逐渐被分类.在这种情况下，该算法选择与其自身性状最相似的排挤因子进行替换，故能够保持群体的多样性.据De Jong称，基于拥挤机制的小生境遗传算法针对某些优化问题能够获得比较满意的结果，如多峰函数求极值等.

2.3 基于共享机制的小生境技术

基于共享机制的小生境技术是Goldberg和Richardson于1987年提出的.在该机制中，使用共享函数来确定每个个体在整个群体中的共享度.一个个体共享度的计算方法为该个体与整个群体中所有其他个体之间共享函数值之和.共享函数能够提供群体中两个个体之间关系密切程度(根据基因或表现型的相似性确定)的度量.若共享函数值较大则表明两个个体间的关系较密切；反之则表明两个个体间关系的密切程度不大.

也可以用形式化的方式来表达这个问题.设dij表示两个个体之间关系的密切程度(度量方式有多种，如海明距离等).若以S表示共享函数，Si表示个体i在群体中的共享度，则(其中m为群体中个体的数量减1).

在完成群体中所有个体共享度计算的基础上，个体i的适应度f(i)调整为fs(i)，其中fs(i) =f(i)/Si.据此可知，基于共享机制的小生境技术能够限制种群中的某一个或特殊个体无限制的增殖.目标已有的测试数据表明，较基本遗传算法而言，基于共享机制的小生境技术在解决多峰函数的优化问题时能够体现出更好的搜索性能.基于共享机制的小生境遗传算法的基本实现步骤如下.

step1 算法初始化.主要完成初始种群的建立，遗传参数的设定等.

step2 完成种群中所有个体适应度的计算.

step3 执行遗传操作，即选择、交叉、变异.

step4 完成种群中所有个体共享度的计算.

step5 根据个体的共享度重新计算每个个体的适应度.

step6 对子代和父代个体的适应度大小进行比较.

step7 用子代个体替换父代个体，形成新一代群体.

step8 若满足算法终止条件，则算法终止；否则返回step3.

2.4 隔离小生境技术

通过考察自然界中存在地理隔离方式，我们将遗传算法中的初始群体以某种方式进行划分，得到若干个子群体.子群体间的进化是彼此独立的.而各个子群体由于其平均适应度不同，故子群体间的进化速度和群体自身规模通常是有差异的.由于隔离后的子群体的进化过程彼此独立，故可以针对各子群体进行更为灵活的控制.据此，我国学者提出隔离小生境技术的概念.另外，自然界中的竞争不仅存在于种群中个体之间，种群与种群之间也存在相互竞争.也就是说，适者生存的机制不仅存在于个体之间，对于种群也同样适用.在隔离小生境技术中，我们通过引入两级竞争机制来实现竞争机制，以保证得到更优秀的个体.

3 几种小生境技术性能比较分析

适应值共享算法的执行起始为选择阶段，该方法通过调整个体适应值的手段达到维持种群多样性的目的.拥挤算法的执行起始为替换阶段，新个体以某种方式与老个体竞争完成替换，目的同样是维持种群多样性.而遗传算法的竞争机制为优胜劣汰，由于适应值共享算法能够通过调整个体适应值完成搜索过程，故其对于解的搜索能力优于拥挤算法.

预选择机制通过限定只有子串才能完成对父串的替换，故该方法能够在一定程度上维持种群多样性.但由于该方法较拥挤机制的灵活度差，故其收敛和搜索性能不及拥挤算法.

隔离小生境遗传算法为两级竞争机制，即子群体中个体之间的竞争和子群体之间的竞争.子群体个体间的竞争侧重于局部搜索性能，而子群体间的竞争侧重于全局搜索性能.故该算法能够较好的平衡遗传算法局部搜索与全局搜索间的矛盾.

［1］华洁，崔杜武.基于个体优化的自适应小生境遗传算法［J］.计算机工程，2010(1)：200-202.

［2］陆青，梁昌勇，杨善林，张俊岭.面向多模态函数优化的自适应小生境遗传算法［J］.模式识别与人工智能，2009(1)：93-99.

［3］谭艳艳，许峰.自适应模糊聚类小生境遗传算法［J］.计算机工程与应用，2009(4)：56-59.

［4］黄鵾，陈森发，孙燕，郜振华.一种小生境正交遗传算法研究［J］.东南大学学报(自然科学版)，2004(1)：135-137.