遗传算法⼩⽣境技术简介
⽣物学上，⼩⽣境是指特定环境下的⼀种组织结构。在⾃然界中，往往特征，形状相似的物种相聚在⼀起，并在同类中交配繁衍后代。在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个个体（N<M）.(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 ||<L时，⽐较个体x 和个体x 的适应度⼤⼩，并对其中适应度较低的个体处以罚函数： Fmin(x ，x )=Penalty（7）依据这M+N个个体的新适应度对各个个体进⾏降序排列，记忆前N 个个体。（8）终⽌条件判断。若不满⾜终⽌条件，则：更新进化代数记忆器t t+1，并将第（7）步排列中的前M个个体作为新的下⼀代群体P(t)，然后转到第（3）步：若满⾜终⽌条件，则：输出计算结果，算法结束。
[例] Shubert 函数的全局最优化计算。
min f(x , x )={ } { }
< -10 x 10（i=1，2）
上述函数共有760个局部最优点，其中有18个是全局最优点，全局最优点处的⽬标函数值是f （x ， x ）=-186.731。
⽤上述⼩⽣境遗传算法求解该例题时，可⽤下式进⾏⽬标函数值到个体适应度的变换处理：
F（x ， x ）=
L=202（⼆进制编码串长度，其中每个变量⽤10位⼆进制编码来表⽰）
M=50
T=500
p =0.1
p =0.1
L=0.5(⼩⽣境之间的距离参数)黑头面膜
Penlty=10 （罚函数）
使⽤上述参数进⾏了50次，试算，每次都可得到许多全局最优解下表为其中⼀次运算所得到的最好的18个个体。从该表可以看出，从⼩⽣境的⾓度来数，该算法得到了⼀个较好的结果。上述算法的特点保证了在⼀个函数峰内只存在⼀个较优的个体，这样每⼀个函数峰就是⼀个⼩⽣境。
基于⼩⽣境遗传算法的Shubert函数优化算法计算结果
个体标号 x x f（x ， x ）
1 5.4828 4.8581 -186.731
2 5.4830 -7.708
3 -186.731
3 4.8581 5.4831 -186.731
曜的读音
4 4.8581 -7.0838 -186.731
5 -4.4252 -7.4983 -186.731
6 -7.0832 -7.0838 -186.731
7 5.4827 -1.4249 -186.731
8 0.8580 5.4831 -186.731
9 4.8580 -0.8009 -186.730
10 -0.8009 -7.7084 -186.730
11 -0.8009 4.8581 -186.730
12 -7.7088 -0.7999 -186.730
13 -7.7088 -7.0831 -186.730
14 -1.4256 -0.8009 -186.730
15 -0.8011 -1.4252 -186.730
16 -7.7075 5.4834 -186.730
17 -7.7088 4.8579 -186.730
18 -7.0825 -1.4249 -186.730
下⾯再介绍⼀种隔离⼩⽣境技术的遗传算法
隔离⼩⽣境技术的基本概念及进化策略依照⾃然界的地理隔离技术，将遗传算法的初始群体分为⼏个⼦群体,⼦群体之间独⽴进化，各个⼦群体的进化快慢及规模取决于各个⼦群体的平均适应⽔平.由于隔离后的⼦群体彼此独⽴，界限分明，可以对各个⼦群体的进化过程灵活控制。⽣物界中，竞争不仅存在于个体之间，种群作为整体同样存在着竞争，适者⽣存的法则在种群这⼀层次上同样适⽤.在基于隔离的⼩⽣境技术中，是通过将种群的规模同种群个体平均适应值相联系来实现优胜劣汰、适者⽣存这⼀机制的.⼦群体平均适应值⾼，则其群体规模就⼤，反之，群体规模就⼩.⽣物界在进化过程中，适应环境的物种能得到更多的繁殖机会，其后代不断地增多，但这种增加不是⽆限制的，否则就会引起⽣态环境的失衡.在遗传算法中，群体的总体规模是⼀定的，为了保证群体中物种的多样性，就必须限制某些⼦群体的规模，称⼦群体中所允许的最⼤规模为⼦群体最⼤允许规模(maximum allowed scale)，记为S .⽣物界中同样会出现某些物种因不适应环境数量逐渐减少，直⾄灭绝的现象.在隔离⼩⽣境机制中，为了保持群体的多样性，有时需要有意识地保护某些⼦群体，使之不会过早地被淘汰，
并保持⼀定的进化能⼒.⼦群体的进化能⼒是和⼦群体的规模相联系的，要保证⼦群体的进化能⼒，必须规定每⼀⼦群体⽣存的最⼩规模，称为⼦群体最⼩⽣存规模(minimum live scale)，记为S .在群体进化过程中，如果某⼀⼦群体在规定的代数内，持续表现最差，应该使这个⼦群体灭绝，代之以搜索空间的新解，这⼀最劣⼦群体灭绝的机制，定义为劣种不活(the worst die).⼦群体在进化过程中，如果出现两个⼦群体相似或相同的现象，则去掉其中的⼀个，代之以搜索空间的新解，这种策略称为同种互斥或种内竞争(intraspecific competition).解群中出现的新的⼦群体，在进化的初期往往⽆法同已经得到进化的其它⼦群体相竞争，如果不对此施加保护，这些新解往往在进化的初期就被淘汰掉，这显然是我们所不希望的.为了解决这个问题，必须对新产⽣的解加以保护，这种保护新解的策略叫幼弱保护(immature protection).⼦群体在进化过程中，如果收敛到或接近局部最优解，会出现进化停滞的现象，此时应当以某种概率将该⼦群体去掉，代之以搜索空间的新解，此种策略称为新⽼更替(the new superding the old).在进化过程中，表现最优的个体进化为最优解的概率最⼤，应当使它充分进化，故新⽼更替策略不能⽤于最优⼦群体，这种做法称为优种保留(the best live).优种保留可以作⽤于最好的⼀个⼦群体，也可以作⽤于最好的⼏个⼦群体.
基于隔离⼩⽣境技术的遗传算法步骤
1)编码：针对具体问题，选择合适的编码⽅案，完成问题解空间向遗传算法解空间的转化.
2)产⽣初始群体：随机产⽣N个初始个体.
3)初始群体隔离：将N个初始个体均分给K个⼦群体，每个⼦群体含有的个体数均为N/K.
4)计算适应值：计算群体中所有个体的适应值.并保存适应值最⾼的个体.
5)确定⼦群体规模:⼦群体的规模同⼦群体的平均适应值相关,⼦群体的平均适应值越⼤，其在下⼀代中拥有的个体就越多；反之，在下⼀代中拥有的个体就少.但数⽬必须满⾜最⼤允许规模和最⼩保护规模的限制，即第t+1代第k个⼦群体的规模n (t+1)满⾜S ≤n (t+1) ≤S .
确定⼦群体规模的具体⽅法如下,⾸先给每个⼦群体都预分配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）
⼦群体规模的确定也可以根据其平均适应⽔平⽤赌轮法确定.梦里依稀慈母泪
6)保护解除判定：对群体中施加保护的群体，进⾏保护解除判定，对满⾜保护解除条件的，撤除保护.
7)劣种不活判定：对解群中没有保护⽽连续⼏代表现⼜最差的群体，予以剔除并产⽣等规模的新⼦群体.
8)同种互斥判定：随机挑选出两个⼦群体，依据某种原则判定其相似程度，对满⾜相似条件的两个⼦群体，去掉其中的⼀个，产⽣同等规模的新解.
9)新⽼更替判定：判定解群中是否存在已经进化停滞的⼦群体，如果有，进⾏新⽼更替，产⽣同等规模的新解，但对包含最优个体的⼦群体要保留(最优保留机制).
10)重新计算适应值：对新产⽣的⼦群体计算适应性值，并施加幼弱保护措施.
11)⼦群体进化：由于⼦群体的规模同其在群体中的平均表现⽔平相联系，故⼦群体的规模是不断变化的.
根据公式(2)确定的规模，选择出⼦群体的繁殖个体，利⽤交叉和变异算⼦产⽣下⼀代解群.
12)收敛性判定，如果满⾜收敛性条件，或已经进化了规定的代数，则结束进化过程；否则返回第4步。
除了上⾯的还有下⾯⼏种常⽤的的⼩⽣境算法：
1 确定性拥挤算法
确定性拥挤（Deterministic crowding, DC）算法由Mahfoud 提出。该算法属于拥挤算法范畴，采⽤⼦个体与⽗个体直接进⾏竞争的模式，竞争的内容包括适应值和个体之间的距离。算法的过程如下：
确定性拥挤算法（重复G 代）
重复下列步骤N/2次：
（1）⽤放回的⽅式随机选择两个⽗个体p 和p 。
（2）对其进⾏杂交和变异，产⽣两个个体c 和c 。
（3）如果[d(p ，c )+d(p ，c )] [d(p ，c )+d(p ，c )]，则
如果f（c ）>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 lection 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略⼤于其它适应值共享算法中的⼩⽣境树⽴功能。顾客群中的个体的适应值与其它适应值共享算法中个体的适应值相同，⽽商家群中的个体的适应值是属于该商家所有顾客的适应值之和。
算法需要⾸先在搜索空间中随机放置商家群的个体，其余的过程如下；
⾃适应⼩⽣境算法（重复G 代）
幼儿珠心算入门教程（1）将每⼀个顾客群中的个体都安排到最近的商家中去。讨论的英语
（2）计算所有顾客的⼩⽣境数（其归属的商家所拥有的顾客数量）。
（3）⽤公式计算顾客群的个体共享后的适应值。
（4）⽤顾客群中个体共享后的适应值尽⼼选择，杂交和变异出新的个体，⽣成新⼀代顾客群。
（5）顺序选择每⼀个商家群中的个体并对其进⾏变异操作以产⽣新的商家。如果新商家的适应值⽐⽼商家的适应⾼，⽽且与其它商家之间的距离均⼩于，则新商家代替⽼商家。否则进⾏另外⼀次变异操作，直到产⽣可以替换的新商家或变异操作的次数超过指定的最⼤变异为⽌。
⾃适应⼩⽣境算法计算距离的时间的复杂度为O(Kn).
