改进的遗传算法

企 业 技 术 开 发 2011年 6月 摘 要：文章给出了遗传算法的改进方法，利用改进的遗传算法对测试函数进行计算，结果表明该方法的有效性。 关键词：遗传算法；测试函数；改进 中图分类号：O242.23 文献标识码：A 文章编号：1006-8937（2011）11-0182-02 Improved genetic algorithm ZHOU Rui- fen （School of Mechanical Science and Engineering，Northeast Petroleum University，Daqing，Heilongjiang 163318，China） Abstract:This paper gives the improved genetic algorithm，the test functions are calculated by the improved method，the results show that the method is effective. Keywords：genetic algorithm；test function；improvement 改进的遗传算法 周瑞芬 （东北石油大学 机械科学与工程学院，黑龙江 大庆 163318） 企 业 技 术 开 发 TECHNOLOGICAL DEVELOPMENT OF ENTERPRISE 2011年 6月 Jun.2011 第 30卷第 11期 Vol.30 No.11 大自然生物进化过程的规律是“物竞天择，适者生 存”。经过竞争后群体中的一部分个体将被淘汰，另一部 分则成为种群，种群通过婚配的作用产生子代群体（简 称子群）。进化过程中，可能会因为变异而产生新的个 体。综合变异的作用，子群成长为新的群体而取代旧群 体。在新的一个循环过程中，新的群体将替代旧的群体 而成为循环的开始。 遗传算法就是模仿了生物的遗传、进化原理。在求 解过程中，遗传算法从一个初始变量种群开始，根据“生 存竞争”和“优胜劣汰”的原则，借助选择、交叉、变异等 操作，一代一代地寻找问题的最优解，直至满足收敛判 据或预先设定的迭代次数为止。 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的遗传算法存在局 部寻优能力不足、进化过程中不能保留最优个体等缺 点，本文对遗传算法进行改进，增强了局部寻优能力，并 能保留下寻优过程中的最优个体。 1 标准遗传算法 遗传算法包括诸多要素，主要有种群规模、编码方 法、适应函数的确定以及遗传算子等。 种群是由染色体构成的。每个个体就是一个染色 体，每个染色体对应着问题的一个解。种群中个体的数 量称为种群大小或者种群规模。种群大小通常采用一个 不变的常数。一般来说，遗传算法中种群规模越大越好， 但种群规模的增大将导致运算时间的增加，种群大小的 设定和所求问题变量的维数有很大的关系，也和变量的 变化范围有很大的关系。 在遗传算法中，要对染色体进行合适的编码来表示 问题的解，这是遗传算法的基础工作也是最重要的工 作。编码方法主要有二进制编码、实数编码、顺序编码和 整数编码等，具体选择编码方法时可根据所研究问题的 特点而定。 遗传操作在进化搜索中以适应函数为依据，利用种 群中每个个体的适应值来进行搜索。因此适应函数的选 取直接影响到遗传算法的收敛速度以及能否找到最优 解。适应函数是由目标函数变换而成的，但要求适应函 数满足对每个个体对应的适应值均大于零，否则就无法 应用轮盘赌方法进行选择操作。 遗传算法包括选择、交叉和变异 3种基本形式，是模 拟自然选择以及遗传过程中发生的繁殖、杂交和突变现 象的主要载体。选择即从当前群体中选择适应值高的个 体以生成交配池的过程，常用的是轮盘赌选择法。交叉 操作是模仿自然界有性繁殖的基因重组过程，其作用 在于将原有的优良基因遗传给下一代个体，并生成包 含更复杂基因结构的新个体。遗传算法中，在交叉运算 之前还必须先对群体中的个体进行配对（一般是随机配 对），然后在这些配对组中两个个体之间进行交叉操作。 变异操作模拟自然界生物体进化中染色体上某位基因 发生的突变现象，从而改变染色体的结构和物理性状。 对于实数型编码最常用的变异有位值变异和向梯度方 向变异。 遗传算法是一种反复迭代的方法，最常用的终止条 件是规定一个最大的迭代次数，算法迭代次数达到最大 迭代次数时计算停止。终止条件也可通过检查适应函数 值的变化来实现，如果群体平均适应函数值变化率和最 优个体适应函数值变化率满足精度，则可以认为群体处 于稳定状态，群体进化基本收敛，可结束群体进化过程。 当然，终止条件还可通过检查各个个体的变化状况来实 现，如果群体中每个个体与最优个体都很接近时，可结 束群体进化过程。 收稿日期：2011－03－15 作者简介：周瑞芬（1972—），女，河北唐山人，博士研究生，副教授，主 要从事油田节能问题的研究。 第 30卷第 11期 表 1 改进后遗传算法结果对比 种群 规模 20 50 60 20 50 60 N=50 1.5E- 02 2.6E- 02 5.4E- 02 0.315 0.923 2.135 N=100 1.2E- 04 1.3E- 02 1.5E- 03 0.021 8.3E- 02 9.1E- 02 N=400 6.2E- 06 2.3E- 02 2.1E- 04 5.4E- 02 2.1E- 02 4.5E- 02 改进前（N表示迭代次数） 改进后（N表示迭代次数） N=50 3.7E- 03 1.5E- 02 2.3E- 02 1.1E- 01 5..1E- 02 0.313 N=100 2.1E- 05 5.10E- 04 3.9E- 04 1.0E- 02 2.1E- 03 5.2E- 02 N=400 1.3E- 08 2.1E- 04 1.2E- 07 1.4E- 02 3.1E- 04 1.3E- 02 测试函 数名称 Sphere Griewank 变量 个数 7 20 30 7 20 30 2 遗传算法的改进 遗传算法的改进策略有很多，主要有适应函数的设 置改进、选择算子的改进、交叉算子的改进、变异算子的 改进。本文从保留历史最优个体、定期替换当前最优个 体、定期进行轴向搜索局部求精等 3个方面对算法进行 了改进。 2.1 保留历史最优个体 在基本遗传算法中，由于遗传算子的作用，可能会 出现新产生的种群中的最优个体适应值不如上一代种 群中最优个体适应值，这样就把搜索过程中出现的最好 个体信息丢失掉。因此，应当保存历史搜索过程中得到 的最优个体，但该个体不参与每一次的遗传运算。 2.2 定期替换当前最优个体 由于保留了搜索过程中的历史最优个体，为了充分 利用保留的这个历史最优个体的信息，加快搜索进程，应 当在迭代到一定次数后，判断当前最优个体适应值是否 优于历史最优个体适应值，若是则继续更新历史最优个 体信息，若不是则用历史最优个体替换当前最优个体。 2.3 定期进行轴向搜索 遗传算法的局部搜索能力较差，因此需定期轴向搜 索局部求精，也就是每迭代一定次数后对当前最优个体 进行一次轴向搜索，这样可以加快收敛速度，更易得到 全局最优解，另外轴向搜索也起到了一定的变异 作用，增强了种群的多样性。由于一次轴向搜索 的计算量比较大，因此采用了定期轴向搜索。 所谓轴向搜索是指得到当前最优个体后，以 当前最优个体为中心，进行轴向搜索，即：x（1）从出 发以 α 为步长进行搜索，对 i=1，2，…，n 依次实 行下列步骤： 从 x（i）出发沿坐标轴 ei的正方向探测，即令： x=x（i）+αei （1） 比较目标函数 f（x）与 f（x（i）），若 f（x）