1、 PDF外文：http:/ 外文译文题目（中文） ： 一种新的改进遗传算法及其性能分析 学 院 : 计算机科学与技术 专 业 : 软件工程 学 号 : 200813138032 学生姓名 : 王 月 指导教师 : 张 葵 日 期 : 二 一 二 年 四 月 五 日 天津大学学报
2、;2003 年 9 卷 2 期 一种新的改进遗传算法及其性能分析 罗批，李锵，郭继昌，腾建辅 （ 天津大学电子信息工程系，天津 300072） 摘要： 虽然遗传算法以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称，但是它仍然有一定的缺陷，比如收敛速度慢。本文根据几个基本定理，提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法，它的主要思想是：在进化的开始阶段，我们使用短一些的变异染色体长度和高一些的交叉变异概率来解决，在全局最优解附近，使用长一些的变异染色体长度和低一些的交叉变异概率。 最后
3、，一些关键功能的测试表明，我们的解决方案可以 显著 提高遗传算法的收敛速度 ，其综合性能优于只保留最佳个体的遗传算法。 关键字： 编译染色体长度；变异概率；遗传算法；在线离线性能 文章编号： 1006 4982(2003) 02 0140 04 遗传算法是一种 以自然界进化中的选择和繁殖机制为基础的 自适应的搜索技术 ， 它是由Holland 1975 年首先提出 的。它以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称。然而它也有一些缺点， 如本地搜索不佳，过早收敛，以及收敛速度慢
4、 。近些年，这个问题被广泛地进行了研究。 本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。 一些关键功能的测试表明，我们的解决方案可以 显著 提高遗传算法的收敛速度 ，其综合性能优于只保留最佳个体的遗传算法。 在第一部分，提出了我们的新算法。第二部分，通过几个优化例子，将该算法和只保留最佳个体的遗传算法进行了效率的比较。第三部分，就是所得出的结论。最后，相关定理的证明过程可见附录。 1. 算法的描述 1.1 一些定理 在提出 我们的算法之前，先给出一个一般性的定理（见附件），如下：我们假设有一个变量（多变量可以拆分成
5、多个部分，每一部分是一个变量） x a, b , x R，二进制的染色体编码是 1. 定理 1 染色体的最小 分辨率是 s = 12l ab 定理 2 染色体的第 i 位的 权重 值 是 wi = 12l ab12i ( i = 1,2, l ) 定理 3 单点交叉的染色体搜索 步骤 的数学期望 Ec(x)是 Ec (x) = lab2Pc 其中 Pc是交叉概率 定理 4 位变异的染色体搜索步骤的
6、数学期望 Em(x)是 Em ( x ) = ( b- a) Pm 其中 Pm 是变异概率 1.2 算法机制 在进化过程中，我们假设变量的值域是固定的，交叉的概率是一个常数 ，所以从定理 1 和定理 3 我们知道，较长的染色体长度有着较少的染色体搜索步骤和较高的分辨率；反之亦然。 同时，交叉概率 与 搜索步骤 成正比 。 由定理 4，改变染色体的长度不影响 变异的 搜索步骤 ，而变异 概率 与 搜索步骤 也是成正比的。 进化 的开始阶段 ， 较 短
7、染色体（可以是过短，否则它 不利于 种群多样性）和 较高的 交叉和 变异概率 会增加 搜索步骤 ，这样 可进行更大的域名搜索，避免陷入局部最优。 而全局最优的附近，较长染色体和较低的交叉和变异概率会减少搜索的步骤，较长的染色体也提高了变异分辨率，避免在全局最优解附近徘徊，提高了算法收敛速度。 最后，应当指出， 染色体长度的改变不会使个体适应性改变，因此它不影响选择（轮盘赌选择）。 1.3 算法描述 由于基本遗传算法没有在全局优化时收敛，而遗传算法保留了当前一代的最佳个体，我 们的方法采用这项策略。 在进化过程中，我们跟踪到当代个体平均适应度的累
8、计 值 。它被写成： X(t) = G1 Gt avgf1(t) 其中 G 是当前进化的一代， favg 是个体的平均适应度。 当累计平均适用性增加到最初个体平均适应度的 k ( k> 1, k R) 倍 ， 我们将染色体长度变为其自身的 m (m 是一个正整数 ) 倍，然后减小交叉和变异的概率， 可以提高个体分辨率、减少搜索步骤以及提高算法收敛速度。 算法的执行步骤 如下： 第一步：初始化群体，并计算个体平均适应度 favg0，然后设置改变参数的标志 flag。 flag设为 1. 第二步：在所保留的当代的最佳个体，进行选择、再生、交叉和变异， 并计算当代个体的累积平均适应度 favg 第三步：如果 kffavgavg 0 且 flag = 1， 把染色体的长度增加至自身的 m 倍，减少交叉
