小生境遗传算法综述

反映个体之间相似程度的共享函数来调整群体中各个个体的适应度，以维护群体的多样性，
从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算。其
中：个体i、j的相似程度可以是基因型的海明距离或表现型的欧氏距离，以dij表示；经调整 后个体的适应度为其原适应度值除以小生境数mi，mi为个体i与群体内其他个体之间的共享 函数
nbWinners = 1; for (j = i+1 ; j< n-1 ; j++) { if (Fitness(P[j])>0 && Distance (P[I], P[j])<Sigma){ if (nbWinners < Kappa) { nbWinners++; }
内最佳个体数。据说该方法适用于求解具有非常复 杂搜索空间的优化问题。
数随着群体的进化而变化。每个小生境i有两个参数：midi和σshi；分别代表小生境的中心点 位置和小生境的半径。当群体中的个体与midi的距离小于σshi时，则该个体为小生境i的成员。
1、计算群体的初始适应度； 2、运行 FSGA 或其他算法，记录最佳个体 S； 3、以 G(S)修正群体的适应度，目的是抑制 S 所在 区域的个体参与下一次进化； 4、如果最佳个体超出某一设定的临界值，则该个 体作为问题的一个峰值输出； 5、如果所有的峰值都输出，则停止；否则，转步 2；
图 2 Sequential Niching 的实现步骤 Fig 2 The pseudocode of Sequential Niching
Fi+1(x) = Fi (x)G(x, ) Si−1
（6）
同年Yin & Germay[17]将MacQueen’s KMEAN聚类算法引入FSGA。该方法的基本思想是： 先将群体分成k组，对应于k个小生境；个体的共享适应度由其原适应度除以小生境数mi，mi 由下式给出：
mi
=
nc
−
nc
⎜⎜⎝⎛
d ic 2d max
削平山峰的方法是以上一次 FSGA 所得的最佳个体的函数修改下一次运行 FSGA 时的 个体适应度。该函数为一单调递减函数，Beasley 测试了以下两种函数形式：
G(x, S ) = ⎪⎨⎧⎜⎝⎛ d xS r ⎟⎠⎞α d xS < r
⎪⎩ 1
其他
（4）
G(x,S) = ⎪⎨⎧exp⎜⎝⎛logm(r −dxS)r ⎟⎠⎞ dxS < r
1. 物种形成与小生境技术
自然界中，“物以类聚，人以群分”是一种司空见惯的现象。生物总是倾向于与自己特 性、形状相类似的生物生活在一起，一般总是与同类交配繁殖后代，这种交配方式在生物进 化过程中具有积极作用。生物学上，有共同特性的组织被称为物种（species）。而物种赖以 生存的资源环境，我们称之为小生境（niches）[4]。在自然界，小生境技术（niching）表现 为：生态环境中分享不同资源的物种的形成。对应于象GA这样的人工系统，小生境技术表 现为：在一个固定规模的群体中子群体的形成，每个子群体对应问题的一个子任务（在多峰 值优化问题中，每个子任务对应于找出一个山峰）。
上述几种小生境实现方法都需要计算群体中个体间的距离dij，也就是说群体内所有个体 平均分享境内有限的资源，这在群体规模比较大时将影响算法的效率。由此， Pétrowski[13]
于 1996 年提出将群体内有限资源只提供给境内最优个体的基于Clearing机制的小生境实现
方法。该方法算法如图 3 所示。
叉（forking）技术以细分搜索空间。一种方法是用 salient schema 细分基因型空间，而另一种方法则 以 当 前 最 佳 个 体 为 中 心 利 用 neighborhood hypercubes 细分表现型空间。两种方法中搜索空间 的细分都取决于当前群体和解的收敛情况（详细情
况请参考文献[18]）。之后 1998 年 Jelasity 明确提出了一种可变半径的小生境实现方法—— GAS。该方法中，物种由表现型搜索空间的点为中心，以 radius function 为半径确定一个物 种。每个物种表述搜索空间中互不相交的区域。该方法使用一种类似于模拟退火的 cooling
小生境技术具有相对简单、有效和通用的特性，因此，它可作为 SGA 强有力的组成部 分。它可促使群体内个体间协同合作，使算法易于找出优化问题的所有局部最优解和全局最
1 本课题得到福建省教育厅（JB04025）资助 -1-

优解。而 SGA 中，个体间仅仅存在竞争，最好的个体在进化中迅速占据整个群体，即一个 物种占据环境的全部资源，或者说算法仅能找出其中的一个最优解（全局最优解或局部最优 解）。
void Clearing(double Sigma, int Kappa) { int i , j , nbWinners; SortFitness (P); for (i=0 ; i<n ; i++) { if ( Fitness (P[i]) > 0) {
该算法包括 3 个函数：降序排序函数 void SortFitness(P)、适应度函数 double Fitness(P[i])和距 离函数 double Distance(P[i],P[j])。P 为群体，内有 n 个个体；Sigma 为小生境半径；Kappa 为小生境
-4-

技术，使得搜索朝着最优解所在的区域逐步收敛（详细情况请参考文献[19]）。 1999 年Gan和Warwick提出一种类似于GAS的小生境动态聚集方法（Dynamic Niche
Clustering，简称DNC）[15、20]。该方法定义一个小生境序列向量Nichset，代表群体中小生境
1997 年 Tsutsui 等介绍了稳态进化方法的两种 改进方法，称为 forking GA。这两种方法都利用分
else { Fitness (P[j]) = 0.0;} }}}} }
图 3 Clearing 方法的源程序 Fig 3 the algorithm of Clearing Niching
（3）
式中：n为群体规模；α为共享程度；бsh为小生境半径，其表达式由Deb和Goldberg[11、12]于 1989 年给出；k为优化问题的维度；m为优化问题最优解的个数。
但该方法需要事先知道多峰值函数最优解的个数，并且其复杂度达到O(n2)——n为群体 规模。1991 年Oei介绍了几种降低算法复杂度的方法，主要是以在群体中选取几个个体作为 样本代替计算所有个体间的相似度，但每个小生境都要限定个体的最大数量[15]。
图 1 DC 的实现步骤 Fig 1 the pseudocode of deterministic crowding
代循环。DC的伪代码如图 1 所示。
DC具有算法简单、收敛速度快和隐含并行性等优点，被用于解决列车轨道混凝土的生
产工艺问题，取得了较好的结果[14]。
小生境技术中最著名及用得最多的可能是 1987 年Goldberg & Richardson提出的基于共 享机制（Fitness Sharing）的小生境实现方法（简称FSGA）[10]。该方法的基本思想是：通过
1、随机选择两个父代个体P1、P2 ； 2、对P1、P2进行交叉、变异生成子代个体C1、C２ ； 3、计算P1与C1、P2与C2、P1与C2、P2与C1的距离d1、d2、 d3、d4 ； 4、如果 d1+d2 不大于 d3+d4 ，那么：
如果C1的适应度大于P1的适应度，用C1代替P1； 如果C2的适应度大于P2的适应度，用C2代替P2； 否则： 如果C2的适应度大于P1的适应度，用C2代替P1； 如果C1的适应度大于P2的适应度，用C1代替P2；
另一个值得关注的小生境实现方法是 1993 年Beasley等提出的Sequential Niching[16]。该方法 认为FSGA在求解多峰值函数时，父代群体与子 代群体中适应度分布曲线变化不大，只能求得其 中最大的一个峰值。因此Beasley提出反复运行 FSGA来搜索所有峰值。其基本思想是：运行 FSGA，找出一个峰值，后将该山峰削平，使得 再次运行FSGA时得以搜索其他峰值，如此反 复，直到找到所有的峰值。其实现步骤如图 2 所示。
小生境遗传算法综述1

李明林
(福州大学机械工程学院 福建 福州, 350002)
（Email：lml_007@）
摘 要：本文在阅读大量遗传算法小生境技术资料基础上，介绍了遗传算法的特点、物种形 成和小生境技术，详细陈述上世纪 80 年代以来的各种小生境实现方法，包括共享函数法、 确定性排挤法、可变半径的聚类算法和隔离小生境方法等；最后对小生境遗传算法的工程应 用提出了展望。 关键词: 小生境，遗传算法，聚类算法，隔离
2. 小生境技术的研究进展
小生境技术最早是由Cavicchio[5]在 1970 年提出的基于预选择机制（Preselection）的小 生境实现方法。1975 年DeJong一般化了Cavicchio的预选择机制[6]，在其博士论文提出了基
于排挤机制（Crowding）的小生境实现方法[7]。他们声称这两种方法都可在群体中形成小生
法收敛于局部最优解。通过对Crowding方法的 修改，Mahfoud提出了一种基于所谓确定性排 挤机制（deterministic crowding，简称DC）的 小生境实现方法。该方法据说可从根本上消除 基因漂移[8，9]。DC的基本思想是：将父代群体 随机两两配对，若N为群体规模，则配对后将 生成N/2 对父代个体。每对父代个体进行交叉、 变异或其他遗传操作，生成两个子代个体。两 子代个体分别与其中一个相似的父代个体进 行竞争，适应度高的代替适应度低的进入下一
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概 率搜索算法。