遗传算法及其育种

遗传算法及其育种1 前言遗传算法(GA, Gene tic Algori thm)是一种逐次迭代方法，但是，遗传算法是模拟 生物的遗传和进化过程而发展起来的一种搜索和优化方法，其搜索过程始终是在群体中进 行的，所以，遗传算法具有全局性、并行性、快速性和自适应性，是求解复杂问题最优解 的有效方法。GA于20世纪60年代由美国Michigan大学J.H.Holland教授首先提出。它可广泛 应用于人工智能、机器学习、函数的优化、自动控制等领域。GA的突出特点是将问题的解 空间通过编码转换为GA的搜索空间，把问题的解转换为生物的个体，并借助生物的遗传和 进化理论，对多个个体同时进行选择、交叉和变异操作。这样，可以较快地搜索到最优解。 但是，遗传算法易陷入局部最优。搜索效率还不是很高。因此，为了克服这些缺点缺点， 本文提出了育种算法，可以较好地解决遗传算法的问题。2 基础遗传算法及局限2.1 基础遗传算法的主要步骤准备工作使用遗传算法首先将搜索、优化问题转换成求适应度函数最大值的问题，建立适应度 函数。目标函数的优化方向应对应于适应度增大的方向。对于最小值优化(min F(x)问 题可以令适应度函数2为f (x) = C - F (x)(1)x= x x兀1 2 na xb (i=1,2,.n)iii其中，C为大于F(x)的最大值的一个常数，这样求F(x)的最小值，就变成了求适应度函 数f (x)最大值的问题。根据自变量的可能取值范围和自变量的精度5 ,确定编码的长度L。若编码为二进制 码，则编码长度为L = ln(bmax-a+1) / In 252)式中，b 为所有自变量上限的最大值，a 为所有自变量下限的最小值。编码后，二进 m axmin制串与自变量的十进制数值的映射关系3为M(b - a )3x = a +maxmin(3)i min2 L - 1式中，M为二进制串对应的十进制数值。最后，随机产生N组初始个体(长度为L的二进制字符串)，即随机生成N组初始解，为使初始解尽可能分布在解空间的各个角落，N必须足够大，一般N=20150。用(3)式算出各个初始解的十进制值，代入适应度函数(1)计算出个体的适应度。就可开始遗传操作，遗传操作分：选择复制、交叉、变异三个步骤。选择复制 选择复制的目的是选择适应度大的优秀个体，淘汰部分个体，实现“优胜劣汰”。选择 的方法常用轮盘赌法，即按个体适应度占总适应度的比例把整个轮盘划分给各个个体，然 后再随机地转动轮盘，随机地选取个体。如图1 所示，由于适应度大的个体在轮盘中所占 的区域大，故被选中的概率也大，保护了优秀个体。由于优秀个体被大量复制，搜索可以 较快地收敛到稳定状态。同时，选择是随机进行的，因此适应度小的个体也有可能被选中， 部分地保持了个体的多样性。图 1 轮盘赌法选择交叉 交叉是将选择出来的群体按一定的交叉概率随机地选择出一部分个体，随机地两两配 对，并按选定的交叉方式，把成对的个体的基因部分地进行交换，形成新的个体。如图 2 所示，交叉点也是随机选取的。交叉操作使群体在继承父代的基因的同时又不完全等同于 父代，有可能产生更优秀的个体，使搜索向最优解靠近。1 0 1 :0 10 1 0 :1 1图 2 交叉操作示例变异 交叉操作是父代基因的重组，基因全部来源于父代，经过多次交叉后，就很难产生新 的个体了。变异是以较小的概率随机地改变一个串位的值。如对于二进制串，就是将随机 选取的串位的值由 1 变成 0 或者由 0 变成 1。变异操作不依赖于父代的基因，更容易产生 新的个体，保持群体的多样性。为了使搜索能够收敛，搜索初期变异率不能太高。通过不断重复以上的遗传操作，优秀个体的适应度越来越高，直到一个或者多个个体 达到最优解。若相同的个体越来越多，直到所有个体均相同，即使这时没有达到全局最优， 搜索也很难进行下去，搜索到的就是局部最优。2.2 基础遗传算法的局限容易陷入局部最优 遗传算法的选择复制操作会使优秀个体大量复制，这样种群中会出现许多相同的个体， 而相同个体之间即使进行交叉操作也不会产生新的个体。另外，变异出来的更优秀个体由 于数量少，很容易在选择复制操作中被淘汰，因此，搜索容易陷入局部最优搜索效率低 对于基础遗传算法，优秀个体的存活和发展要靠相同个体的规模来保证，而这种规模 反过来又成了新的优秀个体发展起来的障碍，由于轮盘的大部分区域已被旧的优秀个体占 据，因此新的优秀个体存活并发展起来的概率很小，过程也较漫长。这种由机制的缺陷所 产生的竞争及内耗是不可避免的。这和生物界自然进化过程缓慢的道理是一样的。所以遗 传算法的搜索效率不是最高的。具有三种操作，运算量大 遗传算法具有选择、交叉、变异三种操作，特别是选择和交叉操作，需要多个操作步骤，实现程序较长，运行时间也较长，因此不便于复杂问题的求解。7 育种算法的应用实例 育种算法不是针对某一特定函数提出的，因此算法具有普遍意义，适用于各种优化问 题。用育种算法进行了许多函数的优化计算，效果均非常良好，下面是其中两例。例 1 具有针状全局最优的函数如下F (r) = S +1rr =、:( x - 50)2 + (y 一 50)2 + e0 x, y 100图2 例1 的函数图该函数的函数图形如图2 所示，在(50,50)处取得全局最大值1.1512，其第二极大值为 1.12837，它是一个多峰值函数，采用传统优化方法几乎不能找到全局最优点，一些改进3 遗传算法同样也找不到全局最优。微粒群算法限定繁殖1500代，实验100次，有10次可 以找到全局最优，平均最优值达到1.12903，至 1.145 平均需要 40949.3 代3。采用单种 子育种算法，取L=14, N=100，限定繁殖100代，实验100次有29次找到全局最优，平均 最优值达到1.133,最大值1.1494。采用三种子育种算法取C= 99, L=15, N=99,不保留 热点，限定繁殖800代，实验100次有80次找到全局最优，平均最优值达到1.144，最大 值1.1503。性能得到了大幅提高。例 2 优化问题如下：min.F =艺 sin(x sin(ix ) -H cos(x cos(ix )i11-ii11- ii =1i =10 x 10i 该例的极值如麦田的麦芒一样不计其数，要找出其中最矮的一株其难度是可想而知的 取调用函数次数= 140000次，连续十次实验的结果如下：差分进化算法搜索到的最小值为 -10.78783，平均值为-10.51465。微粒群算法搜索到的最小值为-10.76252，平均值为 -10.39754。三种子育种算法(N=199, L=16, C=-99，调用函数次数=50000次)搜索到的 最小值为10.7977，平均值为10.2557。若调用函数次数增大到140000次，育种算法搜 索到的最小值为10.86433，平均值为10.537。例 3 测试函数如下：/ (x) = (一1) i+i sin(x ) + (一1) i sin()13 _i3 x 13i用育种算法搜索在D=4,无约束和约束条件为x + x + x + x 20时，函数的全局最优。 1234取自变量的分辩率为0.01，算出二进制串长度为10，群体规模为100。共实验100次， 搜索到的极值点为X =X =7.609, X =X =11.222，最大值为7.62，平均迭代次数20,平1324均用时 1 秒。对于有约束的搜索，可以把约束条件作为一个判断条件，插入程序中，当约 束条件不满足时，令对应个体的适应度为一个很小的值，这样就把不满足约束条件的解排 除了。该例有约束条件时搜索到的极值点为：X =X =7, X =X =3，最大值为：4.84,平1324均迭代次数： 77，平均用时： 4秒。例4用De Jong测试平台中的一个典型函数3max /(x, y) = 100(x2 - y)2 + (1 一 x)2x,y一 2.048 x, y 2.048进行遗传算法和育种算法优化实验，共实验100次。 遗传算法采用轮盘赌法保留优秀个 体法选择，变异率可变。实验结果如表 1 所示，育种算法搜索到的全部为全局最优 (3905.926)，且平均代数远低于遗传算法的平均代数,平均用时0.5秒。例 5 分别用基础遗传算法、自适应遗传算法和育种算法对标准测试函数2min / (x, y) = 4 + 4.5x 一 4y + x2x,y+ 2 y 2 一 2 xy + x 4 一 2 x 2 y8 x, y 8进行优化实验，共实验100组。实验结果如表2所示，基础遗传算法无一次搜索到全局最 优，自适应遗传算法和育种算法全部搜索到全局最优，但是自适应遗传算法代数较多，平 均为453代，育种算法平均只有29代，平均用时0.2秒。例 6 分别用微粒群6算法和育种算法对测试函数/ (x) = e-(X1 + x2 b/50 cos(|X I + |x |)一 50 x , x 5012 进行优化实验，共实验100次。取搜索终止条件为函数值大于等于0.99。实验结果表明， 微粒群算法平均代数为1589代。育种算法取个体长度L=12,群体规模N=100。则搜索到的 函数值平均为0.993，平均代数仅74代，平均用时2秒。另外，分别取控制参数C=-10和C=0,搜索到的最小值为一0.93928。方程/(x) = 0的根有多组，其中一组为X1=17.993, X=49.511。2例7求: Min f(x)二 + x x 2 + x12 34约束： x x + x x 2 = 1123 40x +x x 1012 40 x x + x 101 3 4-10 x x 0，所以x单独计算：11For k = 1 To 12M = M + ZQ(1, j, k) * 2人(12 - k) 二进制转换成十进制Next kX(1) = 0.0001 + M * 10 / (2 人 12 - 1)将 x 放开， x 只受等式约束，不受区间约束。即令22x 二(1 - x x2)/x 效果好一些2 3 4 1X(2) = (1 - X(3) * X(4) * X(4) / X(1)在程序中加入约束条件和函数,X(0)存放函数值X(0) = X(1)人 0.5 + X(2) * X(3)人 2 + X(4)If X(1) + X(2) * X(4) 10 Then Goto LIIf X(4) + X(1) * X(3) 10 Then Goto LI不满足约束条件时跳出程序，则该组变量取值被排除。设种群规模N=99,个体长度L=12，调用函数次数= 2 0 0 0 0的搜索结果:例8：min f=(L-L2)/2)人2+22)人0.5*Al+0.5*L2*A2;两个等式约束：1. (L-L2)/2)/(24*E*I)*(3*LA2-4*(L-L2)/2)A2)*(L-L2)/2)A2+hA2)A(-0.5)-(xA2+yA2)A(-0.5)*y*E*Al=k2 . (L-L2)/2)A2+hA2)A(-0.5)-(xA2+yA2)A(-0.5)*x*E*A1-2*(L-L2)/2)-x)/L2*E*A2)*(y+( (L-L2)/2)+L2)A2*(L-L2)/2)A2/(3*L)+(L-L2)/2)A2*(4*(L-L2)/2)A3+l0*(L-L2)/2)A2*L2+6*( (L-L2)/2)*L2A2+L2A3)/(6*LA2)/(E*I)*(L-L2)/2)A2+hA2)A(-0.5)-(xA2+yA2)A(-0.5)*y*E*A1) =(x-(L-L2)/2)*(L-L2)/2)A2+hA2)A(-0.5)-(xA2+yA2)A(-0.5)*y*E*A1四个不等式约束：1(L-L2)/2)A2+hA2)A(0.5)-(xA2+yA2)A(0.5)02(xA2+yA2)A(0.5)-(L-L2)/2)A2+hA2)A(0.5)-(L-L2)/2)A2+hA2)A(0.5)*q/E03. x-(L-L2)/2)04. (L-L2)/2)-x-L2*q/(2*E)1000 Then GoTo 11 限定-1000vAlvl000C = (P + (L - L2) / 2) + L2)人 2 * (L - L2) / 2)人 2 / (3 * L) + (L - L2) / 2)人 2 * (4 * (L - L2) / 2)人 3 + 10 * (L- L2) / 2)人 2 * L2 + 6 * (L - L2) / 2) * L2 人 2 + L2 人 3) / (6 * L 人 2) / (E* I) * (L - L2) / 2)人 2 + h 人 2)人(-0.5)- (z 人 2 + P 人 2)人(-0.5) * P * E * A1)If C = 0 Then GoTo 11D = (z - (L - L2) / 2) * (L - L2) / 2)人 2 + h 人 2)人(-0.5) - (z 人 2 + P 人 2)人(-0.5) * P * E * A1F = 2 * (L - L2) / 2) - z) / L2 * EG = (L - L2) / 2)人 2 + h 人 2)人(-0.5) - (z 人 2 + P 人 2)人(-0.5) * z * E * A1 - D / CIf F = 0 Then GoTo 11A2 = G / FIf abs(A2)1000 Then GoTo 11 限定-1000vA2v1000请在下面输入约束条件和函数,X(0)存放函数值If (L - L2) / 2)人 2 + h 人 2)人(0.5) - (z 人 2 + P 人 2)人(0.5) 0 Then GoTo 11If (z 人 2 + P 人 2)人(0.5) - (L - L2) / 2)人 2 + h 人 2)人(0.5) - (L - L2) / 2)人 2 + h 人 2)人(0.5)* q / E 0 Then GoTo 11If z - (L - L2) / 2) 0 Then GoTo 11If (L - L2) / 2) - z - L2 * q / (2 * E) 0 Then GoTo 11X(0) = (L - L2) / 2)人 2 + h 人 2)人 0.5 * A1 + 0.5 * L2 * A2结果：L2、h、x、y限定在10； A1、A2限定在10000。个体长度L=12；种群规模N=99, 调用函数次数200000次 min=4533.337 |口| X中前子 Media Player军棋MicrosoftOutlook4356217644 .03660678255 .0864331147 .52077563929620466472tS网上邻居维普浏览器 byjzarix_E.-. POPO2IJLI4我的电脑V3.2 5TEP7MicroWIN金山词霸例9：-42T 1.064164895 摄左值二 10388. 9620357809 -4301.20885984153 -4235.40066439347-4281.3477084027 :-4223.75939239805-4236.719T3T42881-4285.6552072954 :-4274.70407718459-4240.38998577211-4330.76183643978-4318.12371604201-4188.62015872385-4533.33792212133摄小值杲小值杲小值摄小值杲小值杲小值摄小值摄小值摄小值摄小值摄小值摄小值：多次搜索的最小值=-4533. 337922121339.99023199023199.62759462T59462T95.9T81675824563-992.860229799973-4.622710622T1062-T.0451T704517T05(:(L-L2)/2：T2+h2) (0. 5)-O2+y2) (0. 5)=-3. 98668738399642仗2+“(0. 5)-(L-L2)/2)2+h2) (0. 5)-(L-L2)/2) 2+V2) (0. 5)*q/E=-51.5095394403198 k-(L-L2)/2)=-. 22T59462T594627(L-L2)/2)-x-L2*q/ C2*E)=-62. 2113553113553爹汝搜索的杲大值=1Q144. 42445S7694)=9.72161172161172)=-9.995115995116)=-4.6S62026S620269)=-9.995115995116；摄丈值二10451.摄丈值二9511 盘丈值二102TT；呈犬值二10010 摄大值二10165.摄大值二|摄丈值杲大值i杲丈佰摄丈值；摄丈值i摄丈值10009.8857603566 10210.2280981889 10402.5587329067 10070.0962832999 9973.20751192971 9885.47975745723 10144.4244587694sin3-0JP+0.001(xa+/)l1max F=l,次大 0.9 9 0 5a = Abs(X(1): b = Abs(X(2): r = Sqr(a * a + b * b)max X(0) = 0.5 (Sin(r) 2) 0.5) / (1 + 0.001 * r) 2N = 120L= 14Xmin = -100Xmax = 100ccc = 0种群大小（个体组数,一组 2 个个体） 每一个体的长度,二进制串的位数 自变量的最小值 自变量的最大值 指定值（函数中间值或无穷大）min y=2.8*(2*k(1)+4*k(2)+8*k(3)+3.5*(2*k(4)+4*k(5)+8*k(6)+4.6*(2*k(7)+4*k(8)+8*k(9)约束条件是：2*k(1)+4*k(2)+8*k(3)=0 2*k(4)+4*k(5)+8*k(6)=02*k(7)+4*k(8)+8*k(9)=02*k(1)+4*k(2)+8*k(3)+2*k(4)+4*k(5)+8*k(6)+2*k(7)+4*k(8)+8*k(9)=1 从以上两个例可以看出，与遗传算法及其改进算法相比，单种子育种算法其优化性能已经 得到了很大提高，而多种子育种算法在处理复杂的多峰值函数上表现出比单种子育种算法 更大的优越性。另外，只要繁殖代数足够，育种算法最后总能找到全局最优，这与遗传算 法落入局部最优不易摆脱相比具有很大的优越性。例 10 用育种算法求解售货商问题。设有 9 个城市，售货商从 0 号城市出发要把货 物送到其他8 个城市，且每个城市只能达到一次，最后回到0 号城市，各城市之间的距离 矩阵L如下。求售货商的送货次序，使总的路程最短。0 2 5 9 3 2 8 512 0 913 5 4 3 9 590546676 915 0 21 6 8 2 3342077592 5 6 17 0 9 8 6 846679081 53785880219 6 2 9 612 0该例售货商有数万种送货方案可共选择，若采用单纯的随机搜索，十次均搜索到最优 路径，平均需要计算总距离16812次。用育种算法以8 个城市为候选库，随机抽取送货城市，可得到送货次序行向量，把行向量看做生物个体，用育种算法的方法，就可找到最短 的路径。以路径最短为选种条件，取种群规模N =20,搜索到的全局最优如图5所示。优化 十次共用时2秒钟，十次全部搜索到最优排列，总路程23，有四条最短路径，其中的一种 为：0-5-3-1-7-8-6-2-4-0。十次优化中，计算总距离次数最少的仅280次，最 多的也不过4280次，平均1232次。因此育种算法使搜索效率提高了13倍多。目录文件算法操作虽优序列:53178624摄小值二23決数=280摄忧序列:534268T1垠小值二23次数=400垠忧序列:53178624垠小值二23次数=760垠忧序列:53118624提小值二23决数=980摄忧序列:1T862435提小值二23决数=14LILI摄忧序列:53426871摄小值二23决数=4280虽忧序列:42681135摄小值二23决数=2000虽忧序列:53118624摄小值二23次数=960摄忧序列:1T862435摄小值二23次数=520摄忧序列:42687135杲小值二23次数=740图 5 TSP 问题的求解结果