λ）选择允许μ个父代个体及其产生的λ个子代个体共同竞争，选择μ个高适应值个体进入下一代，仿真结果表明，当在整个种群中进行随机交叉操作时，用（μ+λ）选择能产生最快的局部收敛速度，局部收敛时，种群的平均适应值等于最优个体的适应值，这表明，整个种群中的个体适应值全部一样，种群多样性损失殆尽。
为此，受生物学小生境现象的启发，为了改善GAs全局搜索性能，我们把整个种群分解成m个小生境（小种群），每个小种群由一组具有相似适应值的个体组成，父代个体的交叉仅限于小生境内部，在每个小生境的交叉操作之后即应用（μ+λ）选择机制，即小生境中的全体父代个体和由他们繁殖的全体子代共同竞争，确定性的选择与小生境个数相同数量的优良个体进入下一代，变异操作在各个小生境中按概率进行，对小生境中的最佳个体变异时应用（1+1）选择，以保证全局收敛性,对其他个体仅做随机变异,不做选择.全体小生境在其内部完成一代进化操作后在整个种群范围内进行重构.
将种群中m×n个个体按适应值大小排序后,自然的形成m个由n个相似个体构成的小生境,小生境中的交叉操作降低了子代个体的不确定性,(n+n)选择提供了最强的选择压,两种机制的共同作用可获得最快的局部收敛速度,m个小生境并行的进化,在获得最快的局部收敛速度的前提下增加了互不相交的子空间中独立的进行搜索的概率,减少了整个种群局部收敛的可能性,随机变异和重构操作使IGAs在整个搜索空间中动态的构造小生境,为全局收敛提供了可靠的保证。交叉操作后的(n+n)选择和最佳个体变异后的（1+1）选择隐含了最佳个体保留机制，因此，能使IGAs收敛到全局最优解。
以下从理论对其进行证明：
L
设种群规模为m×n，个体的二进制编码长度为L位。个体a∈{0,1},其适应度函数为f(a)， 按适应度值降序排序后的种群为P={ai|i=1,?, m×n}并且满足当1≤i≤m×n-1,i
L-O（H）
L
|H|=2
≤2。设H模式中最佳个体为局部最优解xH∈H，变异概率为0，当交叉算子在H空间中
全体状态可达，并在整个种群中随机配对和应用（m×n+m×n）选择时，可以证明：当进化过程趋于无穷时，对全体i∈{1,?, m×n}，ai趋于xH，即进化过程收敛于局部最优解。
采用相似个体交叉和(n+n)选择时，规模为m×n的种群被划分为m个规模为n的子种群 P(i)| i∈{1,?,m},其中的个体分别属于相应的最大阶模式 H(i)| i∈{1,?,m},设H(i)中最佳个体为局部最优解xH(i)，并设
假设1
H（i）∩H（j）≠Φ，
?i，j∈{1,?,m}, i≠j
f(a(∈H(i))≠f(a∈H(j)),
?i，j∈{1,?,m}, i≠j
成立,则必有xH(i)≠xH(j)|i≠j.仍设变异操作等于0,用相同的方法不难证明,当进化过程趋于无穷时,各个子种群将依概率1收敛于相应的局部最优解xH(i),从而维持了整个种群的个体多样性.对于实际问题,假设1不会完全成立,因此,个体多样性会有所损失,但是,因假设1 不成立的概率小于1,故各子种群收敛到同一局部最优解的概率也必小于1.从以上理论分析表明，即使不考虑变异的效果，IGAs也能以大于0的概率维持整个种群中个体的多样性，个体多样度的大小取决于小生境的数量，小生境数量越多，多样度越大。 3.3.4 变异算子的改进
定义1. 对优化问题的最优解而言，其对应染色体上每个基因称为该基因位上的有效基因。 定义 2. 同一基因位上等位基因的多样性是指在种群中，染色体相同基因位的基因既有“0”又有“1”，即在该基因位上基因全为“0”（或“1”）的概率P(“0”)(或P(“1”))为：
P(“0”)=0或P(“1”)=0 （3-1）
J. Crain Potts等人认为, 产生早熟收敛的主要原因是由于有效基因的缺失造成的。由于交叉算子不会产生新的基因，而选择操作的目的在于加快基因的收敛过程，这不可避免的会造成某一类基因在特定基因位上的比例下降，导致该基因位上的基因缺损，因此，为了预防早熟收敛，在有效基因未知的情况下，变异算子必须有能力保持同一基因位上等位基因的多样性，这才有助于防止等效基因的缺失，从而能够最大程度的避免早熟收敛。
而对于传统的变异算子无法有效的保持同一基因位上等位基因的多样性。因为在一个规模为N的种群中，假设在染色体第j个基因位上有n1个“1”和n2 （n2=N-n1）个“0”，则该基因位上的所有基因经取反后变为同一基因的概率为
n1n2??P(\0\)?(1?Pm)Pm?0?????? n2n1??P(\1\)?(1?Pm)Pm?0与式子（3-1）矛盾。
在这里，我们引用双亲变异算子：同或/异或，该算子与传统的变异算子不同，双亲变异算子要有两个染色体参与，例如：
由“同或/异或”的逻辑运算规律可知，运算后的两种逻辑状态互补，即一个为“1”，另一个为“0”。即同一基因位上的基因经过变异之后，该基因位上至少有一个“0”和“1”同时存在，不会出现全“0”或全“1”的情况，这与式（3-1）的要求相吻合。
最后，本文提出的改进的GAs如下所示：
选择二进制编码策略，若变量 xi∈[u,v]，则，
xi?ai?(bi?ai)??(gij?2i)/(2L?1?1)
j?1L
i
其中，L是变量xi对应串的长度，gj为第i个变量xi的第j个基因，将与n个变量x1~xn相对应的基因
i
i
n
n
n-1
n-1
1
1
串gL, ? , g1构成一个长串 gL? g1gL? g1? gL? g1，其染色体的长度为n?L;
定义串的适应度函数F=C―f(x)，C为保证F恒为正的一给定常数； 选择种群大小np等遗传参数，随机产生np个长串构成群体； 计算群体中串的适应度，由串解码的解越好，则适应度越高； 按照个体适应度值构造m个小生境； while(种群不满足停止规则时)
for (m个小生境)
交叉与(n+n)选择
双亲变异与最佳个体的（1+1）选择 endfor 重构小生境 endwhile
3.3.5 试验结果及分析 算例1 我们所用的函数为:
F1?0.002??j?1251j??(xi?aij)6i?12
我们将改进型遗传算法（IGAs）与标准遗传算法(SGA)进行实验比较，改进型遗传算法取
（pc, pm）=(0.9, .017)。交叉为一点交叉方式，如果算法在100代之内不能优化到阈值1.0，则认为搜索失败。实验结果如表3.1所示：
表3.1：仿真实验结果
收敛代数 自变量编码长度 (SGA/IGAs） 种群大小
20 50 80 100
12 F/76 F/84 30/16 18/22
14 F/95 33/9 29/14 20/22
16 F/F 31/42 76/35 28/30
20 F/72 F/26 29/39 37/14
其中，F表示在100代内算法未能找到函数的最大值。 上表表明IGAs只有一次未能在100代内找到阈值，而SGA则有6次。SGA对种群规模比较敏感，种群越小，算法的成功率越低，而IGAs 可以较好的维持算法在小种群时的收敛性，此外，编码长度对算法的影响也不大。
算例2 测试函数为：
F2= e?0.01xcosx20.8x（X?0）
此函数的理论最大值显然是：
FM=f(xM)=max{f(x)}=1.0000000000 XM=0.0000000000 此外，该函数第一峰为：
y1=f(x1)=0.9960810988 当 x1=3.9262095676 第二峰为：
y2=f(x2)=0.9921771679 当 x2=7.8532003851
其中群体规模取pop_size=18，染色体长度取L=40，(pc, pm)=(0.9, 0.1)。迭代次数上限为T=80，适应度函数取为F(x)=f(x)，这里，我们把SGA、IGAs、保留杰出个体GA(elitist GA, EGA)进行比较。其中EGA见参考文献[2]。结果如表3.2：
SGA EGA IGAs
代
数 序号
xm
15.7150955200 11.6227931976 18.9991989136 19.6880568695 4.1989650726
Fm
xm
Fm
xm
Fm
1 15 35 45 55 0.9843755153 0.9727005959 0.7485142350 0.9486948723 0.9494066238 8.0390424728 3.9201649287 3.9583498251 3.9294452090 3.9295440272 0.9704386650 0.9960578056 0.9960181063 0.9906810572 0.9960810572 4.1028136456 0.0469582658 0.0000000058 0.0000000006 0.0000000000 0.9756682346 0.9981565387 1.0000000000 1.0000000000 1.0000000000
表 3.2：仿真实验结果
可以看出，SGA的效果最差，数据波动剧烈，多数偏离最优解，甚至次最优解。EGA在15代之后虽然接近最优解，但这之后一直没有大的改进，表示其陷入了局部最优解。而IGAs 在35代时已非常接近理论值，这之后，xm 和 Fm也一直保持在理论值附近，即全局最优解附近。
x42算例3 测试函数为Camel函数 F3(x,y)?(4?2.1x?)x?xy?(?4?4y2)y2,此函
32数有6个局部极小点，其中有两个（-0.0898，0.07126）和(0.0898,-0.7126)为全局极小,最小值为-1.031628。x，y∈[-100，100]。进化代数为1000，(Pc,Pm)=(0.9, 0.1)，适应度函数取为F(x)=f(x)。我们把本文算法和基于适应度共享机制的小生境技术遗传算法相比较，
结果如表3.3所示：
表3.3：仿真实验结果
运行时间(秒) (适应度共享/IGAs) 种群大小 20 50 80 100
实验结果表明，在相同的实验条件下，改进的遗传算法运行时间缩短了5~20倍，并且这种优势随着种群规模和编码长度的增大更加明显。
自变量编码长度 12 7.78/3.56 55.56/11.16 203.65/26.34 344.23/33.52 14 23.60/5.65 85.36/15.66 16 29.28/7.12 98.64/16.02 20 35.64/8.96 101.23/16.89 332.12/39.44 421.67/68.45 259.87/29.78 298.86/35.48 356.27/43.49 389.67/59.68
3.3.6 结论
本文针对遗传算法中的早熟收敛现象，将基于局部竞争机制的小生境技术和双亲变异相结合，能在经历不多的代数即收敛于全局最优解，而且有较高的收敛精度，大大的改善了遗传算法的全局收敛性能。
相关推荐：
loading