第３１卷第９期 湖ｊ匕广播电视大学学报 Ｖｏ１．３１，Ｎｏ．９ ２０１１年９月 ＪｏｕｒｎａｌｏｆＨｕＢｃｉＴＶＵｎｉｖｅｒｓｉｔｙ Ｓｅｐｔｅｍｂｅｒ．２０１１，１５７￣１５８ 遗传算法及其改进研究 吴 曼，陈长明，史 哲，杜 鹏 （西北大学图书馆，陕西西安７１００６９） ［内容提要】 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索 算法。本文讲述了遗传算法的相关知识要点，通过对遗传算法特点的分析，提出遗传算法的缺点，然后针对遗传 算法的缺点提出相应的一些改进方法。 ［关键词］遗传算法；研究 ［中图分类号］ＴＰ３ ［文献标识码］Ａ ［文章编号］ １００８—７４２７（２０１１）０９．０１５７—０２ １．引言 境中由于某种偶然因素引起的基因模式突变的个体繁殖方 “物竞天择，适者生存”是达尔文生物进化论的基本原 式。在变异算子中，常以一定的变异概率（Ｐｍ）在群体中选 理，揭示了物种总是向着更适应自然界的方向进化的规律。 取个体，随机选择个体的二进制串中的某些位进行由概率控 可见，生物进化过程本质上是一种优化过程，在计算科学上 制的变换（Ｏ与１互换）从而产生新的个体【２】。如果变异概 具有直接的借鉴意义。在计算机技术迅猛发展的时代，生物 率太小，就难以产生新的基因结构，太大又会使遗传算法成 进化过程不仅可以在计算机上模拟实现，而且还可以模拟进 了单纯的随机搜索，一般取Ｐ￣－－０．１￣０．２。在遗传算法中，变 化过程，创立新的优化计算方法，并应用到复杂工程领域之 异算子增加了群体中基因模式的多样性，从而增加了群体进 中，这就是遗传算法等一类进化计算方法的思想源泉。 化过程中自然选择的作用，避免早熟现象的出现。 ２．遗传算法概述 ２．２基本遗传算法的算法描述 遗传算法是将生物学中的遗传进化原理和随优化理论 用Ｐ（ｔ）代表第ｔ代种群，下面给出基本遗传算法的程 相结合的产物，是一种随机性的全局优算法。遗传算法不但 序伪代码描述： 具有较强的全局搜索功能和求解问题的能力，还具有简单通 Ｐｒｏｃｅｄｕｒｅ ＳＧＡ 用、鲁棒性强、适于并行处理等特点，是一种较好的全局优 化搜索算法。在遗传算法的应用中，由于编码方式和遗传算 Ｂｅｇｉｎ： 子的不同，构成了各种不同的遗传算法。但这些遗传算法都 ＩｎｉｔＰｏｐ０； 有共同的特点，即通过对生物遗传和进化过程中选择、交叉、 ｔ＝０：，，计数变量 变异机理的模仿，来完成对问题最优解的自适应搜索过程。 基于这个共同点，Ｈｏｌｌａｎｄ的遗传算法常被称为简单遗传算 ｄｏ｛ 法（简记ＳＧＡ），简单遗传算法只使用选择算子、交叉算子 Ｓｅｌｅｃｔｉｏｎ０； 和变异算子这三种基本遗传算子，其遗传进化操作过程简 Ｃｒｏｓｓｏｖｅｒ（）； 单，容易理解，是其他一些遗传算法的雏形和基础，这种改 进的或变形的遗传算法，都是以其为基础【１】。 Ｍｕｔａｔｉｏｎ（）； ２．１遗传算法几个基本概念 ＰｅｒｆｏｒｍＥｖｏｌｕｔｉｏｎ０； 个体（ＩｎｄｉｖｉｄｕａｌＳｌｒｉｎｇ）：个体是遗传算法中用来模拟生 ｔ－－ｔ＋ｌ；－ 物染色体的一定数目的二进制串，该二进制串用来表示优化 问题的满意解。 ｝ｕｎｔｉｌ（ｔ＝Ｔ）ｆｉｒ是事先指定的最大迭代次数 种群（ｐｏｐｕｌａｔｉｏｎ）．包含一组个体的群体，是问题解的 Ｏｕｔｐｕｔ（）； 集合。 Ｅｎｄ； 基因模式（Ｓｃｈｅｍａｔａ）：基因模式是指二进制位串表示 的个体中，某一个或某些位置上具有相似性的个体组成的集 基本操作： ＩｎｉｔＰｏｐ（） 合，也称模式。 操作结果：产生初始种群，初始化种群中的个体，包括 适应度（Ｆｉｔｎｅｓｓ）：适应度是以数值方式来描述个体优 生成个体的染色体值、计算适应度、计算对象值。 劣程度的指标，由评价函数Ｆ计算得到。Ｆ作为求解问题的 Ｓｅｌｅｃｔｉｏｎ（） 目标函数，求解的目标就是该函数的最大值或最小值。 初始条件：种群已存在 遗传算子（ｇｅｎｅｔｉｃ ｏｐｅｒａｔｏｒ）：产生新个体的操作，常用 的遗传算子有选择、交叉和变异。 操作结果：对当前种群进行交叉操作。 ． Ｃｒｏｓｓｏｖｅｒ（） 选择（Ｒｅｐｒｏｄｕｃｔｉｏｎ）：选择算子是指在上一代群体中按 照某些指标挑选出的，参与繁殖下一代群体的一定数量的个 初始条件：种群已存在。 操作结果：对当前种群进行交叉操作。 体的一种机制。个体在下一代种群中出现的可能性由个体的 Ｍｕｔａｔｉｏｎ（） 适应度决定，适应度越高的个体，产生后代的概率就越高。 初始条件：种群已存在。 交叉（ｃｒｏｓｓｏｖｅｒ）：交叉是指对选择后的父代个体进行 对当前种群进行变异操作。 基因模式的重组而产生后代个体的繁殖机制。在个体繁殖过 程中，交叉能引起基因模式的重组，从而有可能产生含优良 ＰｃｒｆｏｒｍＥｖｏｌｕｔｉｏｎ（） 初始条件：种群已存在且当前种群不是第一代种群。 性能的基因模式的个体。交叉可以发生在染色体的一段基因 串或者多段基因串。交叉概率（Ｐｃ）决定两个个体进行交叉 操作结果：如果当前种群的最优个体优于上一代的最优 操作的可能性，交叉概率太小时难以向前搜索，太大则容易 本，则将其赋值给ｂｅｓｔｉｎｄｉ，否则不进行任何操作。 Ｏｕｔｐｕｔ（） 破坏高适应度的个体结构，一般 取０．２５ ０．７５ 变异（Ｍｕｔａｔｉｏｎ）：变异是指模拟生物在自然的遗传环 初始条件：当前种群是最后一代种群。 操作结果：输出ｂｅｓｔｉｎｄｉ的表现型以及对象值。 ［收稿日期】２０ｌ１．ｏ７．１０ 【基金项目］西北大学科学研究基金，项目编号；０９ＮＷ２６。 作者吴曼系西北大学图书馆馆员。 １５８ 湖北广播电视大学学报 第９期 ３．遗传算法的缺点及改进 遗传算法有两个明显的缺点：一个原因是出现早熟往往 是由于种群中出现了某些超级个体，随着模拟生物演化过程 的进行，这些个体的基因物质很快占据种群的统治地位，导 致种群中由于缺乏新鲜的基因物质而不能找到全局最优值； 另一个主要原因是由于遗传算法中选择及杂交变异等算子 的作用，使得一些优秀的基因片段过早丢失，从而了搜 索范围，使得搜索只能在局部范围内找到最优值，而不能得 到满意的全局最优值【３】。为提高遗传算法的搜索效率并保证 得到问题的最优解，从以下几个方面对简单遗传算法进行改 进。 ３．１编码方案 因实数编码方案比二进制编码策略具有精度高、搜索范 围大、表达自然直观等优点，并能够克服二进制编码自身特 点所带来的不易求解高精度问题、不便于反应所求问题的特 定知识等缺陷，所以确定实数编码方案替代ＳＧＡ中采用二 进制编码方案［４１。 ３．２适应度函数 采用基于顺序的适应度函数，基于顺序的适应度函数最 大的优点是个体被选择的概率与目标函数的具体值无关，仅 与顺序有关【 。构造方法是先将种群中所有个体按目标函数 值的好坏进行排序，设参数 ∈（Ｏ。１），基于顺序的适应度 函数为： 优的个体几乎是处于一种不发生变化的状态，而此时的优良 个体却不一定是全局最优的，这很容易导致演化趋向局部最 优解。这容易使进化走向局部最优解的可能性增加。同时， 由于对每个个体都要分别计算Ｐｃ和Ｐｍ，会影响程序的执行 效率，不利于实现。 对自适应遗传算法进行改进，使群体中具有最大适应度 值的个体的交叉概率和变异概率不为零，改进后的交叉概率 和变异概率的计算公式如式（４）和（５）所示。这样，经过 改进后就相应地提高了群体中性能优良个体的交叉概率和 变异概率，使它们不会处于一种停滞不前的状态，从而使得 算法能够从局部最优解中跳出来获得全局最优解【＿”。 ＝｛ ： ＿‘，－ 一 卜 ： ｌ ｛ ｅ ．（４） ｛ ＜｛ ｆ ｆ＜ｆａ （５） 【ｐ ｌ ｅｖａｌ（Ｘ；）： ．（１一 ）Ｈｉ＝１，２，…，ｍ （１） 其中：ｆｍａｘ为群体中最大的适应度值；ｆａｖｅ为每代群 体的平均适应度值；ｆ 为待交叉的两个个体中较大的适应 度值；ｆ为待变异个体的适应度值：ｐｃｌ为最大交叉概率； ｐｍｌ为最大变异概率。 ３．４种群的进化与进化终止条件 将初始种群和产生的子代种群放在一起，形成新的种 群，然后计算新的种群各个体的适应度，将适应度排在前面 的ｍ个个体保留，将适应度排在后面ｍ个个体淘汰，这样 种群便得到了进化【８１。每进化一次计算一下各个个体的目标 函数值，当相邻两次进化平均目标函数之差小于等于某一给 定精度ｅ时，即满足如下条件： Ｆ（Ｘ‘Ⅲ 、一Ｆ（Ｘ ）Ｉ－＜Ｅ ｋｌ ｆｍ￣ｘ－－ｆ＂ ｐ ：（６） ， ≥ （２） ｛ｋ２ ｋ３ ｆ￣－ｆ：＝Ｐ 州 ， ＜ ， 。口Ｖｅ （３） Ｊ／ Ｉ ４ ，＜ 式中，ＦｒＹ ｃｍ’、为第ｔ＋１次进化后种群的平均目标函数 值，ＦｆＸ＇）为第ｔ次进化后种群的平均目标函数值，此时， 可终止进化。 ３．５重要参数的选择 ＧＡ的参数主要有群里规模ｎ，交叉、变异概率等。由 于这些参数对ＧＡ性能影响很大，因此参数设置的研究受到 重视。对于交叉、变异概率的选择，传统选择方法是静态人 工设置。现在有人提出动态参数设置方法，以减少人工选择 参数的困难和盲目性。 ４．结束语 遗传算法作为当前研究的热点，已经取得了很大的进 展。由于遗传算法的并行性和全局搜索等特点，已在实际中 广泛应用。本文针对传统遗传算法的早熟收敛、得到的结果 可能为非全局最优收敛解以及在进化后期搜索效率较低等 缺点进行了改进，改进后的遗传算法在全局收敛性和收敛速 度方面都有了很大的改善，得到了较好的优化结果。 ［参考文献］ 【１】邢文训，谢金星．现代优化计算方法［Ｍ】．清华大学出版社， １９９９． ［２】王小平，曹立明．遗传算法理论【Ｍ】．西安交通大学出版社， ２００２． ［３】李敏强，寇纪淞，林丹，李书全．遗传算法的基本理论与应用 【Ｍ】．科学出版社，２００２． 【４】涂承嫒，涂承宇．一种新的收敛于全局最优解的遗传算法Ⅲ， 信息与控制，２００１，２． 【５】陈玮，周激，流程进，陈莉．～种改进的两代竞争遗传算法叫． 四川大学学报：自然科学版，２００３，２． ［６王慧妮，彭其渊，张晓梅．基于种群相异度的改进遗传算法及 ６】应用［Ｊ】．计算机应用，２００６，３． 【７】金晶，苏勇．一种改进的自适应遗传算法 ．计算机工程与应 用，２００５，１８． 【８１陆涛，王翰虎，张志明．遗传算法及改进【Ｊ］．计算机科学，２００７， ８． Ｒｅｓｅａｒｃｈ ｏｎ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｔｓ Ｉｍｐｒｏｖｅｍｅｎｔ ＷＵⅥ ，ＣＨＥＮ Ｃｈａｎｇ—ｍｉｎｇ，ＳＨＩ Ｚｈｅ，ＤＵ Ｐｅｎｇ ［Ａｂｓｔｒａｃｔ】Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｓｏｒｔ ｏｆ ｓｅｌｆ－ａｄａｐｔｉｎｇ，ｏｖｅｒａｌｌ—ｏｐｔｉｍｉｚｅｄ，ｐｒｏｂａｂｉ￣ｔｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈ ｓｉｍｕｌａｔｅｓ ｏｒｇａｎｉｓｍ’Ｓ ｈｅｒｅｄｉｔｙ ａｎｄ ｅｖｏｌｕｔｉｏｎ ｐｒｏｃｅｓｓ．Ｔｈｊｓ ｐａｐｅｒ ｉｌｌｕｓｔｒａｔｅｓ ｔｈｅ ｋｅｙ ｐｏｉｎｔｓ ｉｎ Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ．ａｎｄ ｂｙ ａｎａｌｙｚｉｎｇ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ｆｉｓｔｓ ｉｔｓ ｗｅａｋ ｐｏｉｎｔｓ，ａｎｄ ｐｏｓｅｓ ｓｏｍｅ ｃｏｕｎｔｅｒｍｅａｓｕｒｅｓ． ［Ｋｅｙ ｗｏｒｄｓ】ｇｅｎｅｔｉｃ ｌａｇｏｒｉｔｈｍ；ｒｅｓｅａｒｃｈ
