资源描述
一种新的改进遗传算法及其性能分析 摘要： 虽然遗传算法以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称，但是它仍然有一定的缺陷，比如收敛速度慢。本文根据几个基本定理，提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法，它的主要思想是：在进化的开始阶段，我们使用短一些的变异染色体长度和高一些的交叉变异概率来解决，在全局最优解附近，使用长一些的变异染色体长度和低一些的交叉变异概率。最后，一些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保留最佳个 体的遗传算法。 关键字： 编译染色体长度；变异概率；遗传算法；在线离线性能 遗传算法是一种以自然界进化中的选择和繁殖机制为基础的自适应的搜索技术，它是由975 年首先提出的。它以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称。然而它也有一些缺点，如本地搜索不佳，过早收敛，以及收敛速度慢。近些年，这个问题被广泛地进行了研究。 本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。一些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优 于只保留最佳个体的遗传算法。 在第一部分，提出了我们的新算法。第二部分，通过几个优化例子，将该算法和只保留最佳个体的遗传算法进行了效率的比较。第三部分，就是所得出的结论。最后，相关定理的证明过程可见附录。 1. 算法的描述 些定理 在提出我们的算法之前，先给出一个一般性的定理（见附件），如下：我们假设有一个变量（多变量可以拆分成多个部分，每一部分是一个变量） x a, b , x R，二进制的染色体编码是 1. 定理 1 染色体的最小分辨率是 s = 定理 2 染色体的第 ( i = 1,2, l ) 定理 3 单点交叉的染色体搜索步骤的数学期望 Ec(x)是 x) = 中 定理 4 位变异的染色体搜索步骤的数学期望 Em(x)是 x ) = ( b- a) 中 法机制 在进化过程中，我们假设变量的值域是固定的，交叉的概率是一个常数，所以从定理 1 和定理 3我们知道，较长的染色体长度有着较少的染色体搜索步骤和较高的分辨率；反之亦然。同时，交叉概率与搜索步骤成正比。由定理 4，改变染色体的长度不影响变异的搜索步骤，而变异概率与搜索步骤也是成正比的。 进化的开始阶段，较短染色体（可以是过短，否则它不利于种群多样性）和较高的交叉和变异概率会增加搜索步骤，这样可进行更大的域名搜索，避免陷入局部最优。而全局最优的附近，较长染色体和较低的 交叉和变异概率会减少搜索的步骤，较长的染色体也提高了变异分辨率，避免在全局最优解附近徘徊，提高了算法收敛速度。 最后，应当指出，染色体长度的改变不会使个体适应性改变，因此它不影响选择（轮盘赌选择）。 法描述 由于基本遗传算法没有在全局优化时收敛，而遗传算法保留了当前一代的最佳个体，我 们的方法采用这项策略。在进化过程中，我们跟踪到当代个体平均适应度的累计值。它被写成： X(t) = (t) 其中 当累计平均适用性增加到最初个体平均适应度的 k ( k 1, k R) 倍，我们将染色体长度变为其自身的 m (m 是一个正整数 ) 倍，然后减小交叉和变异的概率，可以提高个体分辨率、减少搜索步骤 以及提高算法收敛速度。算法的执行步骤如下： 第一步：初始化群体，并计算个体平均适应度 后设置改变参数的标志 . 第二步：在所保留的当代的最佳个体，进行选择、再生、交叉和变异，并计算当代个体的累积平均适应度 三步：如果 且 1，把染色体的长度增加至自身的 m 倍，减少交叉和变 异概率，并设置 于 0;否则继续进化。 第四步：如果满足结束条件，停止；否则转自第二步。 2. 测试和分析 我们采用以下两种方法来测试我们的方法，和只保留最佳个体的遗传算法进行比较： 敛的分析 在功能测试中，我们进 行了以下政策：轮盘赌选择，单点交叉，位变异。种群的规 模是 60。 L 是染色体长度， 们随机选择 4 个遗传算法所保留的最佳个体来与我们的方法进行比较，它们具有不同的固定染色体长度和交叉和变异的概率。表 1 给出了在 100 次测试的平均收敛代。 在我们的方法中，我们采取的初始参数是 10， k = 满足改变参数的条件时，我们调整参数 l = 30， 从表 1 中得知，我们的方法显著提高了遗传 算法的收敛速度，正符合上述分析。 表 1 功能测试结果 方法 我们的算法 l=10 m=0.1 l=10 m=0.1 l=30 m=0.1 l=30 m=0.1 57 15236 35791 1626 4363 98 26973 42374 450 5433 线和离线性能的分析 出了遗传算法的定量评价方法，包括在线和离线性能评价。前者测试动态性能，而后者评估收敛性能。为了更好地分析测试 功能的在线和离线性能，我们把个体的适应性乘以 10，并 别给出了 4 000 和 1 000 代的曲线： (a) 在线 (b) 离线 图 1 (a) 在线 (b) 离线 图 2 从图 1和图 2可以看出，我们方法的在线性能只比第四种情况差一点点，但比第二种、第三种、第五种好很多，这几种情况下的在线性能几乎完全相同。同时，我们方法的离线性能也比其他四种好很多。 3. 结论 本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。一些关键功能的测试表 明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保留最佳个体的遗传算法。 附件 有了第一部分中假定的条件，定理 1 和定理 2 的验证是显而易见的。下面给出定理 3和定理 4的证明过程： 定理 3 单点交叉的染色体搜索步骤的数学期望 Ec(x)是 x) = 中 证明： 如图 示，我们假设交叉发生在第 k 个基因位点，从 k到 l 的父基因位点没有变化，基因位点 1 到 k 上的基因改变了。 在交叉过程中， 1 到 k 基因位点上的基因改变的概率为 1”变化 ”0”或者 ”0”变为 ”1”)，因此，交叉之后，基因位点上的染色体搜索步骤从 1到 k 的数学期望是 此外，每个位点的染色体发生交叉的概率是相等的，即 叉后，染色体搜索步骤的数学期望是 把 ( 换为 ( 我们得到 其中 l 是非常大的， ， 所以 图 1 单点交叉 定理 4 位变异的染色体搜索步骤的数学期望是 其中 证明： 每个基因位点上的基因的变异概率是相等的，比如 此变异搜索步骤的数学期望是： 参考 1 自适应变异概率的遗传算法以及其性能分 析 . J. 1999, 27( 5) : 89 2. 2 基于大规模的分布式系统损失最小化的改进遗传算法 . A. 进化计算议 C . 1995: 120 25. 3 一种改进的遗传算法以及它在 E 计划波导过滤器设计重点额应用 J . 2000, 28( 6) : 12124. 4 T J . 应用智能 , 2000, 12: 163 81. 5 . 经典遗传算法的收敛分析 . J . 基于神经网络的 1994, 5( 1) : 96 01. it as In on an of is is as at of of at of of of is of is an on a in it in 970s. It it as as as In In an is it is of In , is in , of is of in 1 of we as us is be x a, b , x R, . of is s = of of ( i = 1,2, l ) c(x) of c (x) = Pc c is of x ) of m ( x ) = ( b- a) Pm m is of 1. 2 of we of of is a so , we of is in to , of of is in to At of be it is to of at of of of up it be it . 1. 3 of to on at we of up to It is (t) = (t) is is to k k 1, k R) of we to m m is a of of up is as . on of of up to ; k , to m of of ; If is go . 2 e to it 2. 1 of we of 0, l is m of we of to 1 00 In we 10, 0.1 k= is we to l= 30, 1, we of it of ur l=10 m=0.1 l=10 m=0.1 l=30 m=0.1 l=30 m=0.1 57 15236 35791 1626 4363 98 26973 42374 450 5433 2. 2 of of To of w e of 0, we a 000 000 f1 (a) (b) 1 of a) (b) 2 of 1 2, we of is of it is of At of is of 3 n on an of is it of is of of , we c(x) of c(x) = c is of As we on i. e. s k to l do on to k of on to k (“1” 0” 0” 1”). of on to k of on of is of q. ( q. ( , we l is , ne of m is of of on of is m, of 1 of J . 1999, 27( 5) : 89 2. 2 A . of C . 1995: 120 25. 3 An it s J . 2000, 28( 6) : 121 24. 4 T of in As J . 2000, 12: 163 5 . of J . 1994, 5( 1) : 96 01.
展开阅读全文