[计算机软件及应用]遗传算法应用实例.doc

遗传算法及其应用实例 遗传算法（Genetic Algorithm）是由美国Michigan大学的Holland教授（1969）提出，后经由De Jong（1975），Goldberg（1989）等归纳总结所形成的一类模拟进化算法。 遗传算法搜索最优解的方法是模仿生物的进化过程，即通过选择与染色体之间的交叉和变异来完成的。遗传算法主要使用选择算子、交叉算子与变异算子来模拟生物进化，从而产生一代又一代的种群。 ()Xt（1）选择算子：是模拟自然选择的操作，反映“优胜劣汰”原理。它根据每一个个体的适应度，按照一定规则或方法，从代种群中选择出一些优良的个体（或作为母体，或让其遗传到下一代种群）。 t(1)Xt.（2）交叉算子：是模拟有性繁殖的基因重组操作，它将从种群所选择的每一对母体，以一定的交叉概率交换它们之间的部分基因。 （3）变异算子：是模拟基因突变的遗传操作，它对种群中的每一个个体，以一定的变异概率改变某一个或某一些基因座上的基因值为其他的等位基因。 交叉算子与变异算子的作用都在于重组染色体基因，以生成新的个体。 遗传算法的运算过程如下： 步1（初始化） 确定种群规模，交叉概率，变异概率和终止进化准则；随机生成个个体作为初始种群；置。 NcPmP(0)X0t.步2（个体评价） 计算评估中各个体的适应度。 步3（种群进化） 3.1. 选择（母体） 从中运用选择算子选择出对母体（）。 /2MMN.3.2. 交叉 对所选择的对母体，以概率执行交叉，形成个中间个体。 M3.3. 变异 对个中间个体分别独立以概率执行变异，形成个候选个体。 M3.4. 选择（子代） 从上述所形成的个候选个体中依据适应度选择出个个体组成新一代种群。 N步4（终止检验） 如已满足终止准则，则输出中具有最大适应度的个体作为最优解，终止计算，否则置并转步2。 1tt.以上运算过程只是遗传算法的多种实现方式中的一种，根据实际问题的不同，遗传算法的实现也是多种多样的。 遗传算法具有通用、并行、稳健、简单与全局优化能力强等突出优点，适用于解决复杂、困难的全局优化问题。 一个优化问题被称为是复杂的，通常指它具有下述特征之一： （1）目标函数没有明确解析表达（如非数值优化问题）。 （2）目标函数虽有明确表达，但不可能恰好估值（如大部分最优控制问题、金融优化问题）。 （3）目标函数有极多的峰值（如计算、组合优化问题）。 DNA（4）多目标优化，即目标函数是向量值。 一个优化问题被称为是困难的，则通常是指：或者目标函数不连续、不可微、高度非线性，或者优化问题是困难的组合问题。 f对于这些复杂、困难的优化问题，已知的优化方法或者根本不可用，或者可用但不有效。相比之下，遗传算法不但保证可用，而且常常显得更为有效。 但是，我们必须注意到，一个通用而又较少依赖于目标函数值与其他辅助信息的算法不可能比专用且充分利用目标函数值与相关辅助信息的算法更为有效，而当一个问题有某些辅助信息可供使用时，舍弃应用本来可供应用的信息而去应用于这些信息无关的算法也不是一个聪明的选择。所以，遗传算法一般来说并不适宜应用于通常的数值优化问题（例如连续可微的数学规划问题），或者说，当应用于这样的问题时，遗传算法并不总能显示其优越性。 01234567-20-15-10-505101520接下来，我们通过一个求解简单函数的最小值点的问题来初步展示遗传算法的具体实现方法： 问题1： 求函数在区间上的最小值点。 ()11sin(6)7cos(5)fxxx.0,2x. 上图为函数在区间上的曲线图像，可以看出，该函数有多个极值点，如果使用其他的搜寻方法，很容易陷入局部最小点，而不能搜寻到真正的全局最小点，但遗传算法可以较好地弥补这个缺陷。遗传算法的具体实现如下： 1.问题分析。对于本问题，自变量可以抽象为个体的基因组，即用二进制编码表示；函数值可以抽象为个体的适应度，函数值越小，适应度越高。 xx()fx关于二进制编码方式，在精度允许的范围下，可以将区间内的无穷多点用间隔足够小的有限点来代替，以降低计算量同时保证精度损失不大。如用16位二进制数来表示该区间的点，相邻点的间隔仅为，相邻点的函数值的变化幅度已经很小，由此带来的精度损失完全可以接受。 516209.58751021.另一个问题是普通的二进制编码方式可能具有较大的汉明（Hamming）距离，例如15和16的二进制表示为01111和10000，从15到16必须改变所有位，这种缺陷将降低遗传算法的搜索效率。采用格雷编码（Gray Encoding）可以避免这一缺陷。格雷码的特点是任意两个连续的两个整数的编码值之间只有一个位是不同的，其他位都完全相同。格雷编码的原理如下： 设有二进制串，对应的格雷串，则从二进制编码到格雷编码的变换为。 12nbbb12naaa11,1,1iiibiabbi.从格雷编码到二进制编码的变换为。 1()mod2iijjba.例如，0-15的格雷码如下表所示： 0 1 2 3 4 5 6 7 0000 0001 0011 0010 0110 0111 0101 0100 8 9 10 11 12 13 14 15 1100 1101 1111 1110 1010 1011 1001 1000 2.根据遗传算法的运算过程编写程序。 % f(x) = 11sin(6x) + 7cos(5x), 0 = x = 2 * pi L = 16; N = 32; M = 48; T = 100; Pc = 0.8; Pm = 0.03; for i = 1 : 1 : N x1(1, i) = rand() * 2 * pi; x2(1, i) = uint16(x1(1, i) / (2 * pi) * 65535); grayCode(i, :) = num2gray(x2(1, i), L); end for t = 1 : 1 : T y1 = 11 * sin(6 * x1) + 7 * cos(5 * x1); for i = 1 : 1 : M / 2 a, b = min(y1); grayCodeNew(i, :) = grayCode(b, :); grayCodeNew(i + M / 2, :) = grayCode(b, :); y1(1, b) = inf; end for i = 1 : 1 : M / 2 p = unidrnd(L); if rand() Pc for j = p : 1 : L temp = grayCodeNew(i, j); grayCodeNew(i, j) = grayCodeNew(M - i + 1, j); grayCodeNew(M - i + 1, j) = temp; end end end for i = 1 : 1 : M for j = 1 : 1 : L if rand() Pm grayCodeNew(i, j) = 1 - grayCodeNew(i, j); end end end for i = 1 : 1 : M x4(1, i) = gray2num(grayCodeNew(i, :); end x3 = double(x4) * 2 * pi / 65535; y3 = 11 * sin(6 * x3) + 7 * cos(5 * x3); for i = 1 : 1 : N a, b = min(y3); x1(1, i) = x3(1, b); grayCode(i, :) = grayCodeNew(b, :); y3(1, b) = inf; end end x1 y1 = 11 * sin(6 * x1) + 7 * cos(5 * x1) 3.结论分析。程序运行结果为： 最小值点为。 1.8486,()17.8340xfx. 下面针对上面的问题，讨论遗传算法中一些初始化参数的设定方法及其影响。 （1）编码长度。使用二进制编码时，通常由对问题的求解精度决定，编码长度越长，可期望的最优解的精度也就越高，但应注意过大的会增大运算量。 L（2）种群规模。种群规模表示每一代种群中所含个体数目。当取值较小时，可提高遗传算法的运算速度，但却降低种群的多样性，容易引起遗传算法早熟，出现假收敛；而当取值较大时，又会使得遗传算法效率降低。一般建议的取值范围是。 NNNN20100（3）交叉概率。在遗传算法中交叉算子被认为是主要搜索算子，因而一般取较大值。一般说，较大的容易破坏群体中已形成的优良模式，是搜索的随机性太大，而较小的使发现新个体（特别是优良新个体）的速度太慢。一般建议的取值范围是。另外，比较理想的的方式是非一致地使用交叉概率，例如在遗传算法的前期使用较大的，后期降低以保留优良个体。 cPcPcP0.40.99（4）变异概率。较大的变异概率使遗传算法在整个搜索空间中大步跳跃，而小的变异概率使遗传算法聚焦于特别区域作局部搜mPmP索。一般在不使用交叉算子的情形（演化策略（Evolution Strategy）算法，进化程序（Evolution Programming）算法），变异算子作主要搜索算子，取较大值（）； 而在与交叉算子联合使用的情形（遗传算法），通常取较小值（）。 mP0.410.00010.5（5）终止进化代数。遗传算法不同于传统优化算法，它很难有明确的搜索终止准则（特别是对于非数值优化问题），于是通常需指定一个终止进化代数来终止算法，一般设。一般来说，事先指定通常只能找到给定问题的在给定时限内所能寻求的相对满意解，但不一定是问题的最优解或较高精度的近似解。为了获得较高精度解，通常可依据种群适应度的稳定情况来实时调整的设置。 T100,1000T.T总体来说，以上参数的确定并没有明确的准则可依据，需要根据实际问题的特点以及算法的运行情况进行实时的调整，以搜索获得更为满意的最优解。 -505-50500.20.40.60.81接下来，我们用遗传算法来求解一个更为复杂的函数最值问题。 问题2： 求Schaffer函数的最大值点： 222121222212sin0.5(,)0.5,55,1,210.001()ixxfxxxixx. 根据遗传算法的一般运算过程编写MATLAB程序如下： L = 32; N = 60; M = 80; T = 100; Pc = 0.6; Pm = 0.02; for i = 1 : 1 : N x10(1, i) = unidrnd(2 L - 1); x10(2, i) = unidrnd(2 L - 1); x11(1, i) = double(x10(1, i) / (2 L - 1) * 10 - 5; x11(2, i) = double(x10(2, i) / (2 L - 1) * 10 - 5; end for t = 1 : 1 : T for i = 1 : 1 : N temp1(1, i) = x11(1, i) 2 + x11(2, i) 2; y1(1, i) = 0.5 - (sin(sqrt(temp1(1, i) 2 - 0.5) / (1 + 0.001 * temp1(1, i); grayCode1(1, i, :) = num2gray(x10(1, i), L); grayCode1(2, i, :) = num2gray(x10(2, i), L); end for i = 1 : 1 : M a, b = max(y1); grayCode2(1, i, :) = grayCode1(1, b, :); grayCode2(2, i, :) = grayCode1(2, b, :); y1(1, b) = -inf; end for i = 1 : 1 : M / 2 p = unidrnd(L); if rand() Pc for j = p : 1 : L temp = grayCode2(1, i, j); grayCode2(1, i, j) = grayCode2(1, M - i + 1, j); grayCode2(1, M - i + 1, j) = temp; temp = grayCode2(2, i, j); grayCode2(2, i, j) = grayCode2(2, M - i + 1, j); grayCode2(2, M - i + 1, j) = temp; end end end for i = 1 : 1 : M for j = 1 : 1 : L for k = 1 : 1 : 2 if rand() Pm grayCode2(k, i, j) = 1 - grayCode2(k, i, j); end end end end for i = 1 : 1 : M x20(1, i) = gray2num(grayCode2(1, i, :); x20(2, i) = gray2num(grayCode2(2, i, :); x21(1, i) = double(x20(1, i) / (2 L - 1) * 10 - 5; x21(2, i) = double(x20(2, i) / (2 L - 1) * 10 - 5; temp2(1, i) = x21(1, i) 2 + x21(2, i) 2; y2(1, i) = 0.5 - (sin(sqrt(temp2(1, i) 2 - 0.5) / (1 + 0.001 * temp2(1, i); end for i = 1 : 1 : N a, b = max(y2); x10(1, i) = x20(1, b); x10(2, i) = x20(2, b); x11(1, i) = x21(1, b); x11(2, i) = x21(2, b); y2(1, b) = -inf; end end x11 运行结果显示，遗传算法常常在附近陷入局部最大，而难以达到的全局最大点。为此，应对遗传算法加以改进。 22212xx.12(,)(0,0)xx.之前的遗传算法存在的一个缺陷是不能保证搜寻到的最佳个体可以被遗传到下一代，因此可能会错过全局最优点。父子混合选择遗传算法（Father-Offspring Combined Selection Genetic Algorithm）对此加以改进，该算法要求上一代的最佳个体必须被无条件地遗传到下一代，因此记录了到目前为止算法所发现的最佳个体，因而适应度序列必然具有单调性，即关于进化代数是单调不减的。可以证明的是，该算法是遗传算法保证收敛的执行策略。 父子混合选择遗传算法的执行过程如下： 步1（初始化） 随机产生对母体组成初始种群，置。 M(0)X0t.步2（种群进化） 2.1. 独立地对中的对母体执行交叉，生成中间种群（由个中间个体组成）。 ()XtN()Yt2.2. 独立地对中的每一个中间个体执行变异，生成子代种群。 ()Zt2.3. 在父代种群与子代种群的并集中选择对母体作为新一代父代种群。 ()()XtZt.(1)Xt.步3（终止检验） 如果终止准则满足，停机并输出中的最佳个体作为问题的近似解，否则置并转步2。 1tt.根据这一算法重新编写程序。 L = 32; N = 60; T = 100; Pc = 0.6; Pm = 0.02; for i = 1 : 1 : N x0(1, i) = unidrnd(2 L - 1); x0(2, i) = unidrnd(2 L - 1); end for t = 1 : 1 : T for i = 1 : 1 : N grayCode(1, i, :) = num2gray(x0(1, i), L); grayCode(2, i, :) = num2gray(x0(2, i), L); end for i = 1 : 1 : N / 2 if rand() Pc p = unidrnd(L); for j = 1 : 1 : p - 1 grayCode(1, i + N, j) = grayCode(1, i, j); grayCode(2, i + N, j) = grayCode(2, i, j); grayCode(1, N - i + 1 + N, j) = grayCode(1, N - i + 1, j); grayCode(2, N - i + 1 + N, j) = grayCode(2, N - i + 1, j); end for j = p : 1 : L grayCode(1, i + N, j) = grayCode(1, N - i + 1, j); grayCode(2, i + N, j) = grayCode(2, N - i + 1, j); grayCode(1, N - i + 1 + N, j) = grayCode(1, i, j); grayCode(2, N - i + 1 + N, j) = grayCode(2, i, j); end end end for i = N + 1 : 1 : 2 * N for j = 1 : 1 : L for k = 1 : 1 : 2 if rand() Pm grayCode(k, i, j) = 1 - grayCode(k, i, j); end end end end for i = N + 1 : 1 : 2 * N x0(1, i) = gray2num(grayCode(1, i, :); x0(2, i) = gray2num(grayCode(2, i, :); end for i = 1 : 1 : 2 * N x1(1, i) = double(x0(1, i) / (2 L - 1) * 10 - 5; x1(2, i) = double(x0(2, i) / (2 L - 1) * 10 - 5; temp(1, i) = x1(1, i) 2 + x1(2, i) 2; y(1, i) = 0.5 - (sin(sqrt(temp(1, i) 2 - 0.5) / (1 + 0.001 * temp(1, i); end for i = 1 : 1 : N a, b = max(y); x2(:, i) = x0(:, b); y(1, b) = -inf; end for i = 1 : 1 : N x0(:, i) = x2(:, i); end end x1 运行结果显示，该算法已经搜索到了近似最优解。 关于遗传算法的收敛性问题，这里可以给出几个结论供参考。 经典遗传算法并不保证全局最优收敛，而只能在一定的约束条件下，实现全局最优收敛。经典遗传算法可能出现未成熟收敛问题，主要表现在以下两个方面：一是群体中所有的个体都陷于同一适应度而停止进化；二是接近最优解的个体总是被淘汰，进化过程不收敛。抑制未成熟收敛的对策有：提高变异概率；调整选择概率；维持群体中个体的多样性等等。但这些方式都不能确保全局最优收敛。 但是，如果在每次迭代过程中保留最优个体，那么就能够保证其收敛。不过，保留最优个体的遗传算法在概率意义下的收敛，并不表明该方法一定具有很快的收敛速度，也不意味着该方法具有更佳的性能，因为它可能需要更长的时间，其计算代价可能是无法接受的。 在设计遗传算法的编码方式时，应考虑以下问题： （1）对于问题空间的任何一个点有表达空间的一个点与之对应，即问题空间的所有可能解都能表示为所设计得染色体形式。 （2）对于表达空间中的任何一个点都有问题空间中的一个点与之对应，即任何一个染色体都对应于一个可能解。 （3）问题空间和表达空间一一对应。 这三点是编码方式或策略应遵守的普遍准则，但是，在实际应用中，对于很多问题，很难设计出同时满足上述三个性质的编码方案。此时，首先必须满足第一个要求，即在保证所有可能解均可以被表示为染色体形式的前提下，是允许生成无用解的。 最后，我们使用遗传算法来解决一个更为贴近实际的问题旅行商问题（Travelling Salesman Problem）。问题的具体表述如下： 一个旅行商需要访问个城市，在任意路线的两个城市之间有一个关联的费用（例如公里数、航空费用等）。找出一个费用最少的路N径：从一个城市出发，经过所有其他的城市一次且仅一次，然后回到出发点。 这个问题已被证明是难题，当城市数量较大时，使用普通算法将耗费大量的时间，因此我们尝试使用遗传算法来求解。 NP适应度评价函数的很直观：我们要做的是评估路径的长度，然后按照长度对路径进行排序，最短的就是最好的。因此，对于本问题的求解，最重要的部分在于编码方式的确定。 假设我们有个城市要访问，编号为。加入简单的用一个四位二进制数（）来代表每一个城市，二进制串代表按照序号顺序进行访问。但问题在于，交叉算子与变异算子很难应用到这种编码方式上，一般的交叉算子和变异算子会产生大量的不可行解，从而影响搜索速度。 91,2,90001,0010,1001000100100011010001010110011110001001.另一种方式是使用一个数字（例如）代表一个城市，通过对这个数字排序构造路径，选择合适的遗传算子产生路径。Davis（1985）提出了有序交叉（Order Crossover）算子，较好地解决了这个问题，具体方式如下： 9有序交叉通过在一个双亲的路径中选择城市子序列创建子代。首先，选择两个划分点，用标志，划分点任意插入到双亲路径中的相同位置，如： | 1(192|4657|83)2(459|1876|23)pp.两个子代和按下面的方法产生。首先，双亲中划分点中间的部分复制到后代中： 1(|4657|)2(|1876|)cc.然后，从一个双亲路径的第二个划分点开始，从另外一个双亲路径中来的城市按相同的顺序复制。当字符串的结尾到达时，转从字符串的开始处继续，最终得到两个子代： 1(239|4657|18)2(392|1876|45)cc.一般来说，对于TSP问题，城市的顺序在生成最少花费路径时非常重要，于是双亲路径中的顺序信息片段传递到子代路径中去时很关键的。 根据该思路编写程序如下：（测试数据来自TSPLIB95：rd100.tsp） rd100 = importdata(rd100.tsp); cityAmount = 100; for i = 1 : 1 : cityAmount for j = 1 : 1 : cityAmount distance(i, j) = sqrt(rd100(i, 2) - rd100(j, 2) 2 + (rd100(i, 3) - rd100(j, 3) 2); end end L = 100; N = 200; T = 10000; Pc = 0.8; Pm = 0.15; for i = 1 : 1 : N x(i, :) = randperm(L); end for t = 1 : 1 : T for i = 1 : 1 : N / 2 if rand() p2 temp = p1; p1 = p2; p2 = temp; end flag1 = zeros(1, L); flag2 = zeros(1, L); for j = p1 : 1 : p2 x(i + N, j) = x(i, j); flag1(1, x(i, j) = 1; x(N - i + 1 + N, j) = x(N - i + 1, j); flag2(1, x(N - i + 1, j) = 1; end j = p2 + 1; k = 1; while 1 if j L j = 1; end if k = p1 k = p2 + 1; end if k L break; end if flag1(1, x(N - i + 1, j) = 0 x(i + N, k) = x(N - i + 1, j); j = j + 1; k = k + 1; else j = j + 1; end end j = p2 + 1; k = 1; while 1 if j L j = 1; end if k = p1 k = p2 + 1; end if k L break; end if flag2(1, x(i, j) = 0 x(N - i + 1 + N, k) = x(i, j); j = j + 1; k = k + 1; else j = j + 1; end end else x(i + N, :) = x(i, :); x(N - i + 1 + N, :) = x(N - i + 1, :); end end for i = N + 1 : 1 : 2 * N