《2022年遗传算法研究综述_葛继科 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法研究综述_葛继科 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、收稿日期 :2008-01- 12; 修回日期 :2008-03-26基金项目 :西南大学研究生科技创新基金资助项目( 2006011)作者简介 : 葛继科( 1977- ), 男, 河南濮阳人,博士研究生, 主要研究方向为人工智能 、 语 义网格 ( gjkid s wu. edu . cn); 邱玉辉( 1938- ), 男, 教授, 博导 , 主要研究方向为人工智能、 语义网格 ; 吴春明( 1972-), 男, 博士研究生, 主要研究方向为网络技术; 蒲国林( 1971- ), 男, 博士研究生, 主要研究方向为人工智能.遗传算法研究综述*葛继科1, 邱玉辉1, 吴春明1, 蒲国林2(
2、1 . 西南大学 计算机与信息科学学院, 重庆 400715 ; 2. 四川文理学院 计算机科学系 , 四川 达州 635000)摘要:介绍了遗传算法的基本工作原理和主要特点,讨论了遗传算法的理论、 技术、 存在问题及改进方法, 概述了遗传算法的常见应用领域,分析了近五年国内对遗传算法的研究现状。最后 , 进一步探讨了遗传算法的未来研究方向 。关键词 :遗传算法 ; 算子; 优化 ; 收敛性中图分类号 :TP301 . 6文献标志码 :A文章编号 :1001 - 3695(2008) 10 - 2911 - 06Summ ary of genetic algorithms researchGE
3、 J- i ke1, Q IU Yu-hu i1, W U Chun-m ing1,PU Guo - lin2( 1 . School of Computer&Inform ation Scie n c e , SouthwestUniversity, Chongqing 400715, China; 2. D e pt.of Co m puterScie nce , Sichuan Uni-versit y ofArts&Scienc e ,Dazhou Sichuan 635000, China)Abstract :This paper introduced the h istory ,b
4、asic principle andmain charactersof genetic algorithms ,d iscussedthe theory ,technology ,lm iitation and m i provingm easuresaboutgenetic algorithm. Then s ummarized the mi p le mentation techni ques andapplications of genetic algorithms ,analyzed the researchstate of genetic algorithms in China du
5、ring t he past five years ,andpointed out the genetic algorithms.researchdirections in the futu re .Key words:genetic algorithm( GA);operator ; optm iization ;convergence遗传算 法是由 美国 M ichigan大学 的 H olland教 授于 1969年提出 , 后经 DeJong 、 Goldberg等人 归纳总 结所 形成 的一 类模拟进化算法 1 3。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传 学说
6、。遗传 算法是 模拟自 然界生物进化过程与机制求解极值问题的一类自组织、自适应人工智能技术 4, 其基本思想 是模 拟自 然界 遗传 机制 和生 物进 化论而形成的一种过程 搜索 最优 解的 算法 , 具 有坚 实的 生物 学基础; 它提供从智能生成过程观点对 生物智 能的模拟 , 具 有鲜明的认知学意义 ; 它适合于无 表达或 有表达 的任何类 函数 , 具有可实现的并行计算行为; 它 能解决 任何种 类实际问 题, 具有广泛的应用价值。因此, 遗传 算法广 泛应用 于自动控 制、 计算科学、 模式识别、工程 设计、智能故障诊 断、 管 理科学和 社会科学等领域 , 适用于解决复杂的非线性和
7、多维空间寻优问题。虽然遗传算法在许多领域中都有成功的应用, 但其自身也存在不足 , 如局部搜索能力差、 存 在未成 熟收敛 和随机 游走等现象 , 导致算法的收敛性能差,需 要很长 时间才 能找到 最优解等问题。这些不足阻碍了遗 传算法 的推广应 用。如何 改善遗传算法的搜索能力和提高算法的收敛速度, 使其更好地应用于实际问题的解决中, 是各国研究者一直探索的主要课题。1遗传算法的执行过程及特点111遗传算法的 执行过程遗传算法作为一种自适应全局优化搜索算法, 使用二进制遗传编码 , 即等位基因# = 0 , 1, 个体空间 HL= 0, 1L, 且繁殖分为交叉与变异两个独立 的步骤 进行。其
8、基 本执行 过程如下 5:a)初始化。确定 种群 规模 N、 交 叉概 率 Pc、 变 异概 率 Pm和置终止进化准则; 随机 生成 N 个个 体作为 初始 种群 X ( 0);置进化代数计数器 tz 0 。b)个体评价。计算或估价X ( t)中各个体的适应度。c)种群进化。( a)选择 (母体 )。从 X ( t)中运用选择算子选择出 M /2对母体 (MN )。(b) 交叉。对所选择的M /2对 母体 , 依 概率 Pc执行 交叉形成 M 个中间个体。( c)变异。对 M 个中 间个 体分 别独 立依 概率 Pm执 行变异, 形成 M 个候选 个体。( d)选择 (子代 )。从上述所 形成
9、的 M 个候 选个体 中依适应度选择出 N 个个体组成新一代种群X ( t+ 1)。d)终止检验。如已满足终止准则, 则输出 X ( t+ 1)中具有最大适应度的个体作 为最优 解, 终止 计算 ; 否 则置tzt+ 1并转 c)。112遗传算 法的特点遗传算法利 用了生物进 化和遗传 的思想。 它不同于 枚举法、 启发式算法、搜索算法 等传统的优化方法, 具有如下特点 :a)自组织、自适 应和 智能 性。遗 传算 法削 除了 算法 设计中的一个最大障碍, 即需要 事先描 述问题 的全部特 点, 并说明针对问题的不同特点算法应采取的措施。因此, 它可用来解决复杂的非结构化问题 ,具有很强的鲁棒
10、性。b)直接处理的对象是参数编码集 , 而不是问题参数本身。第 25卷第 10期2008年 10月计 算 机 应 用 研 究Application R esearc h ofCo mputersVo.l 25No . 10Oc. t2008名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - c)搜索过程中 使用 的是 基于 目标 函数 值的 评价 信息 , 搜索过程既不受优化函数连续性的约束, 也没有优化函数必须可导的要求。d)易于
11、并行化 , 可 降低 由于 使用 超强 计算 机硬 件所 带来的昂贵费用。e)基本思想简单 , 运行 方式和 实现步 骤规范 , 便于 具体使用。2遗传算法的理论研究211编码表示在许多问题求解中, 编 码是遗传 算法中 首要解 决的问 题,对算法的性能有很重要的影响。H olland提出的二进 制编码是遗传算法中最常用 的一 种编 码方 法, 它采 用最 小字 符编 码原则, 编 /解码操作简单易行, 利于交叉、变异操作的 实现 , 也可以采用模式定理对算法进行理论分 析 1。但二进 制编码 用于多维、 高精度数值问题优化时, 不能 很好地 克服连 续函数 离散化时的映射误差 ; 不能直接反
12、映问题的固有结构, 精度不高 , 并且个体长度大、 占用内存多。针对二 进制编 码存在的 不足 , 人们提出了多种改进方法, 比较典型的有以下几种:a)格雷码编码。为了克服二进制编 码在连 续函数 离散化时存在的不足 , 人们提出了 用格雷 码进行 编码的方 法, 它是二进制编码的 变形 6。假设 有一 个二进 制编 码为 X = xmxm -1,x2x1, 其对应的格雷码为Y= ymym -1, y2y1,则ym= xmyi= xi + 1? xii= m -1 , m - 2, , 1格雷码不仅具有二进制编码的一些优点, 而且能够提高遗传算法的局部搜索能力。b)实数编码。该方法适合于遗传算
13、 法中表 示范围 较大的数, 使遗 传算 法更 接近问 题空 间, 避免了 编码 和解码 的过 程。它便于较大空间的遗传搜索, 提高了遗 传算法 的精度 要求 6;便于设计专门问题的遗传算子 ; 便于算法与经典优化方法的混合作用 , 改善了遗传算法的计算复杂性, 提高了运算效率。c)十进制编 码。该方 法 利用 十进 制编 码控 制参 数, 缓解了 / 组合爆炸 0和遗传算法的早熟收敛问题 7。d)非数值编码。染色体编码串中的 基因值 取一个 仅有代码含义而无数值含义的符号集 , 这些符号可以是数字也可以是字符 8。非数值编码的优点是在遗传算 法中可 以利用 所求问题的专门知识及相关算法。对
14、于非数值编码 , 问题的解和染色体的编码要注意染色体的可行性、染色体的合法性和映射的惟一性。212适应度函数在遗传算法中 , 适应度 是描述个 体性能 的主要 指标 , 根据适应度的大小对个体进行优 胜劣汰。对 于求解 有约束 的优化问题时 , 一般采用罚函数方法将目标函数和约束条件建立成一个无约束的优化目标函数; 然后再 将目标 函数作适 当处理 , 建立适合遗传算法的适应度函 数。将目标 函数转 换成适 应度函数一般应遵循两个原则: 适 应度必 须非负 ; 优化 过程中 目标函数的变化方 向 应与 群 体进 化 过 程中 适 应度 函 数变 化 方 向一致 9。在使用遗传 算法 求解 具体
15、 问题 时, 适应 度函 数的 选择对算法的收敛性以及收敛速度的影响较大, 针对不同的问题需根据经验或算法来确定相应的参数。何新贵等人 在对遗传算法的研究过程中, 考虑函数在搜索点的函数值及其变化率, 并 将该信 息加入 适应度函 数, 使得按概率选择的染色体不但具有较小的函数值, 而且具有较大的函数变化率值 10。实验结果表 明, 这类 方法的 收敛 速度明 显高于标准的遗传算法。陶 卿等人 提出基于 约束区 域神经 网络的动态遗传算法 11,将遗传 算法的 全局 搜索和 约束 区域神 经网络模型的局部搜索结合起来 ; 利用动态遗传算法确定神经网络模型的初始点 , 同时使用神经网络确定动态遗
16、传算法的适应度函数。213遗传算 子在遗传算法 中通过一系列算子来决定后代, 算子对当前群体中选定的成员进行重组和变异。1)选择算子选择操作通 过适应度 选择优 质个体 而抛弃劣质个体 , 体现了 /适者生存 0的原理。 Potts等人概括 了 23种选择方法 12。常见的选择操作主要有以下几种:a)轮盘赌选择。选择某假设的概率 是通过 这个假 设的适应度与当前群体中其他成员 的适应 度的比 值而得到。 此方法是基于概率选择的, 存在统 计误差 , 因此 可以结 合最优 保存策略以保证当前适应度最优的个 体能够进 化到下 一代而 不被遗传操作的随机性破坏 ,保证算法的收敛性。b)排序选择。对个
17、体适应值取正值 或负值 以及个 体适应度之间的数值差异程度无特殊要求, 对群体中的所有个体按其适应度大小进行排序 ,根据排序来分配各个体被选中的概率。c)最优个体保存。父代群体中的最 优个体 直接进 入子代群体中。该方法可保证在遗传 过程中所 得到的 个体不 会被交叉和变异操作所破坏 ,它是遗传算法收敛性的一个重要保证条件; 它也容易使得局部最优个体不 易被淘 汰, 从 而使算 法的全局搜索能力变强。d)随机联赛选择。每次选取N 个个 体中适应度 最高的个体遗传到下一代群体中。具体操作如下: 从群体中随机 选取 N个个体进行适应度大小比较 , 将其中适应度最高的个体遗传到下一代群体中 ; 将上
18、述过程重复执行 M ( 为群体大 小 )次, 则可得到下一代群体。2)交叉算子交叉是指对 两个相互 交叉的 染色体 按某种方式相互交换其部分基因 , 从而形成两个新的个体。它是产生新个体的主要方法, 决定了 遗传算 法的全 局搜索能 力, 在遗传算法中起关键作用。 Potts等 人概 括了 17种 交叉方 法 12。几种常用的适用于二进制编码或实数编码方式的交叉算子如下:a)单点交叉。在个体编码串中随机 设置一 个交叉 点后在该点相互交换两个配对个体的部分基因。b)两点交叉。在相互配对的两个个 体编码 串中随 机设置两个交叉点 , 并交换两个交叉点之间的部分基因。c)均匀交叉。两个相互配对个体
19、的 每一位 基因都 以相同的概率进行交换,从而形成两个新个体。d)算术交叉。 由两 个 个 体 的线 性 组 合 而产 生 出 新 的个体。3)变异算子变异是指将 个体染色 体编码 串中的 某些基因座上的基因值用该基因座的其他等位基因来替换, 从而形成一个新的个体。它是产生新个体的辅助方法, 决定了遗传算法的局部搜索能力 12。变异算 子与 交叉算 子相 互配 合, 可 以共同完成对搜索空间的全局搜索和局部搜索, 从而使得遗传算法以良好的搜索性能完成最优 化问题 的寻优 过程。在遗 传算法#2912#计 算 机 应 用 研 究第 25卷名师资料总结 - - -精品资料欢迎下载 - - - -
20、- - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 中使用变异算子主要有以下两个目的: 改善遗传算法的局部搜索能力 ; 维持群体的多样性, 防止出 现早熟现 象。下面 是几种常用的变异操作:a)基本位变异。对个体编码串以变异概率 P 随机 指定某一位或某几位基因进行变异操作。b)均匀变异 (一致变异 )。分别用符 合某一范围 内均匀分布的随机数 , 以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。均匀变异操 作特别 适合应 用于遗 传算法的初期运行阶段, 它使得搜索点可以在整个
21、搜索空间内自由地移动 , 从而可以增加群体的多样性 , 使算 法能够 处理更 多的模式。c)二元变异。需要两 条 染色 体参 与, 通过 二元 变异 操作后生成两条新个体中的各个基因 分别取 原染色 体对应 基因值的同或/ 异或。它改变了传统的变异 方式 , 有效地 克服了 早熟收敛 , 提高了遗传算法的优化速度13。d)高斯变异。在进行变 异时 用一 个均 值为 L、 方差 为 R2的正态分布的一个随机数来 替换原 有基因值。 其操作 过程与均匀变异类似。214参数选择遗传算法的参数选择一般 包括群 体规模、收敛 判据、杂交概率和变异概率等。参数选择关系到遗传算法的精度、 可靠性和计算时间等
22、诸多因素, 并 且影响 到结果 的质量 和系统性 能。因此 , 在遗传算法中参数选择的研究非常重要。在标准的遗传算法中经常采用经验对参数进行估计, 这将带来很大的盲目性从而影响算法的全局最优性和收敛性, 人们意识到这些参数应该随着遗 传进化 而自适应 变化。基 于这一观点 , D avis提出了自适 应算 子概率 方法 14, 即用自 适应 机制把算子概率与算子产生的个体表示适应性相结合, 高适应性值被分配高算子概率。W h itley等人提出了 自适应突变 策略与一对父串间的H amming距离成反比 的观点15,结 果显示 能有效地保持基因的多样性。张良 杰等人 通过 引入 i位 改进子
23、空间概念 , 采用模糊推理技术确定选取突变概率的一般性原则 16。文献 17 中用模 糊规则 对选 择概率 和变 异概率 进行 控制 , 在线改变其值。相应的算例表明, 这种方法有较好的性能。215收敛性分析遗传算法的收敛性通常是指 遗传算 法所生 成的迭 代种群(或其分布 )收敛到某 一稳定 状态 (或分布 ), 或其 适应值 函数的最大或平均值随迭代趋于 优化问 题的最优 值。依不 同的研究方法及所应用的数 学工 具, 收敛性 分析 可分为Vose -L iepins模型、M arkov链模型和公理化模型等。1) Vose -L iepins模型该模型是V ose 和 L iepins提
24、出来的 ,它 用两个矩阵 算子分别刻画比 例 选 择 与组 合 算 子 ( 即杂 交 算 子 与 变 异 算子 的 复合 ), 通过这两个算子不动点的存在性与 稳定性 来刻画 遗传算法的渐近行为 18。Vose -L iepins模型只适用于 简单 遗传算 法, 可应 用于 比例选择、单点杂交和单点变异等,没 有推广 到更具 实用性 的其他遗传算 法 执 行 策 略 中, 如 锦 标 赛 选 择、 多 点 杂 交 等。 另 外,Vose -L iepins模型不易处理变异、 杂交概率随 时间变化的 情形 ,其框架亦很难推广到描述一般非 二进制 或连续 变量情 形的遗传算法。Vose -L ie
25、pins模型虽然在种群规模无限的假设下可精确刻画遗传算法 , 但在有限规模情形下却只能描述遗传算法的平均形态。为了克服这个缺陷 , N ix和 Vose 结 合 V ose -L iepins模型与 M arkov链描 述, 发 展了 遗 传算 法的 一 个精 确 Markov链模型 19。2)M arkov链模型遗传算法的 马氏链模型 主要有 三种 : 种 群马氏 模型、V ose模型 19和 C erf扰动马氏链模型20。种群马氏链 模型将遗传算 法的种群 迭代序 列视为 一个有限状态马氏链加以研究 , 主要是运用种群马氏链转移概率矩阵的某些一般性质分析遗传算法的极限行为。在 Vose 模
26、型中 ,种 群的状态由一个概率向量表示, 概率向量的维数为所有可能个体的数目。当种群规模趋于无穷大时,相对频率的极 限就 代表 了每 一个 个体 在种 群中 出现 的概 率。在无限种群规模假设下 , 可以导出表示种群的概率向量的不动点及其稳定性 , 从而导致对遗传算法极限行为的刻画。R. Cerf利用 A zenco tt等人关于模拟退火的一系列工作, 将遗传算法看成一种特殊形式的广义模拟退火模型, 利用动力系统的随机扰动理论对遗传算法 的极限行 为及收 敛速度 进行了研究 20。尽管在Cerf模型中所研究的马氏链序列仍然是种群序列 , 但研究方法与种群马氏链 模型 有差异 , 所 以称 之为
27、 Cerf扰动马氏链模型。用 M arkov链模型描述遗传算法虽然有直接、精确的 优点 ,但由于有限状态M arkov链理论本身的限制, 与 V ose -L iepins模型类似 , 该模型只能用于描述通常的二进制或特殊的非二进制遗传算法。另外 , 这类 方 法所 得收 敛性 一般 是指 相应 的 M ar -kov链趋于某一平稳分 布。这与 优化 中通 常所 指的 收敛 性定义不同 , 它并不保 证遗 传算 法一 定能 收敛 到问 题的 全局 最优解。再者 , 相应 M arkov链的状态 数 ( 转移矩 阵的规 模 ) 通常很大, 这使得具体确定、 分析 转移矩阵的性态十分困难, 因而对
28、于较大规模的遗传算法 , M arkov链 分析 只能 基于 遍历 性考 察而得出相应遗传算法收敛性的某些/粗糙 0结论。3)公理化模型遗传算法的 公理化方法基 于对模拟 进化计 算操作 的公理化描述 , 应用各个相关操作的本质特征数来对算法的收敛性直接进行概率估计 21。这一方 法不 仅适用 于包 括非 齐次、自适应等在内的各种遗传算法分析 , 而且分析方法本身直观、 清晰 ,所导出的结论 也对 遗传 算法 的各 种参 数选 择提 供参 考依 据。这一模型具有重要的理论意义与实用价值。文献 5还 通过详 细估 计常见 选择 算子与 演化 算子 的选择压、 选择强度、保持率、迁入率、迁出率等参
29、 数, 导出了一系列具有重要应用价值的遗传算 法收敛 性结果。公 理化模 型也可用于其他模拟演化算法的收敛性分析。216欺骗问 题欺骗问题是 遗传算法研 究中的一 个热点。 根据模式 定理可知 , 低 阶、 短距 的优模 式在 遗传 子代中 将以 指数级 增长 , 最终, 不同的最优模式相互组合,从而 得到最优解。但是, 对于欺骗问题 , 复制算子受欺骗条件的/ 迷惑 0, 使最 优低阶模 式在组合后形成非最优高阶模式 , 从而使遗传算法偏离最优解。由于欺骗问题的存在,许多问题 被归结 为遗传 算法难题 , 使 遗传算法的应用受到一定的局限。目 前遗传算 法的欺 骗问题 研究主要集中在三个方面
30、: a)设计欺 骗函数 , 如 Goldberg曾设 计一个离散遗传算法的最小欺骗问题。b)修改 遗传算 法以解 决欺骗#2913#第 10期葛继科 , 等: 遗传算法研究综述名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 函数的影响 , 如黄炎等人提出一种基于可调变异算子求解遗传算法中欺骗问题的方法, 即在遗传搜索过程中通过改变变异算子的方向和概率求解遗传算法的欺骗问题 22。该方 法能够在消除遗传算法中欺骗性条件的同时保持群
31、体的多样性, 使遗传算法可以顺利地收敛到全局最优 解。 c)理解欺 骗函数 对遗传算法的影响 , 何军等人讨论了一类遗传算法求解完全欺骗性问题的平均计算时间 23。217并行遗传算 法并行算法的基本思想是将一 个复杂 的任务 分解为 多个较简单的子任务 , 然后将各子任务分别分配给多个处理器并行执行求解。例如 , Zeigler等 人把高性能并行遗传算法应用到大型并行计算机 24,这种分而 治之的 思想 可以由 不同 的方法 和途径实现 , 导致了各种不同类型的并行遗传算法。并行遗传算法可以分为四大类, 即全局并行遗传算法、 粗粒度并行遗传算法、细粒度并行遗传算法和混合并行遗传算法。侯广坤等人
32、讨论了并行遗传 算法的 迁移现 象及群 体规模估算模型 , 分析了迁移的过程, 揭示了迁移的实质, 并提出了在理想条件下的迁移计算模型 25, 基于 迁移计 算模 型导出 了粗粒度并行遗传算法进化质量 估量模 型。王洪燕 等人对 并行遗传算法的研究现状进行了详细的介绍 26。3遗传算法的应用遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题的具体领域 , 广泛应用于多种学科领域。311函数优化函数优化是遗传算法的经典应用领域, 也是对遗传算法进行性能评价的常用算例。不同研 究者构 造出了 各种各 样的复杂形式的测试函数, 有连续 函数也 有离散 函数 , 有凸函 数也有凹函数 ,
33、 有低维函数也有高维函数, 有确定函数也有随机函数,有单峰值函数也有多峰值函 数等。用这 些几何 特性各 具特色的函数来评价遗传算法的性能 , 更能反映算法的本质效果。对于一些非线性、 多模型、 多目标 的函数优化问题, 用其他优化方法较难求解 , 遗传算法却可以方便地得到较好的结果 27。312组合优化随着问题规模的增大 , 组合优化问题的搜索空间也急剧扩大, 有时在目前的计算机上用枚举法很难或甚至不可能求出其精确的最优解。对这类复杂问题, 应把主要精力放在寻求其满意解上 , 而遗传算法是寻求这种满意解的最佳工具之一。实践证明 , 遗传算法已经在求解旅行商问题、背包、 装箱、布局优化、图形
34、划 分 等 各 种 具 有 NP 难 度 的 问 题 上 得 到 成 功 的 应用 6 , 28 30。313生产调度在很多情况下 , 用常规方法建立的数学模型难以精确求解生产调度问题 , 即使经过一 些简化 之后可 以进行求 解, 有时也会因简化太多而使得求解结 果与实 际目标相 差甚远。 一般情况下 , 在现实生产中主要是靠经 验来进 行调度。研 究发现 , 遗传算法已成为解决复杂调度问题的有效工具, 在单件生产车间调度、流水线 生产车间调 度、 生 产规划、任务分 配等方面 , 遗传算法都得到了有效的应用 8 , 31, 32。314自动控制在自动控制领域中有很多与优化相关的问题需要求解
35、, 遗传算法已在其中得到了初步的应用, 并显示出良好的效果。例如用遗传算法进行航空控制 系统 的优 化 33、 使用 遗传算 法设计 空 间 交汇 控 制 器、 基 于 遗 传算 法 的 模 糊控 制 器 的 优化 设计 34、 基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习 , 利用遗传算法进行人工神经网络的结构优化设计和权值学习等 , 都显 示出 了遗 传算 法在 这些 领域 中应 用的 可能性。315机器人 学机器人是一 类复杂的、难以精确建模的人工系统。由于遗传算法的起源来自于人工自适应系统的研究, 机器人学理所当然地成为遗传算法的一个重 要应用 领域。遗传 算法已 经在移动
36、机器人路径规划 35、 关节机器人运动轨迹规划、机 器人逆运动学求解、细胞机器人的结构优化和行为协调等方面进行了研究和应用 36。316图像处 理图像处理是 计算机视觉 中的一个 重要研 究领域。在 图像处理过程中 , 如扫描、 特征 提取、 图像分割等不可避免地会存在一些误差 , 从而影响图像的效果。如何使这些误差最小化是计算机视觉达到实用化的重要 要求。遗传 算法可 用于图 像处理中的优化计算 , 目 前已 在模 式识 别 (包 括汉 字识 别 37)、 图像恢复、 图像边缘特征提取等方面得到了应用 38,39。317人工生 命人工生命是 用计算机、机械等人工媒体模拟或构造出的具有自然生物
37、系统特有行为的 人造系 统。自组织 能力和 自学习能力是人工生命的两大主要 特征。人工 生命与 遗传算 法有着密切的联系 , 基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于初期阶段, 但遗传算法已在其进化模型、 学习模型、行为模型、自组织模型等方面显示出了初步的应用能力 , 并且必将会得到更为深入的应用和发展。人工生命与遗传算法相辅相成 , 遗传算法为人工生命的研究提供一个有效的工具 , 人工生命的研究也必将促进遗传算法的进一步发展 40。318遗传编 程遗传编程 ( genetic progra mming ,GP)采用树型结 构表示计算机程序 , 运用遗传
38、算法的思想 , 通过自 动生成 计算机 程序来解决问题。虽 然遗 传编 程的 理论 尚未 成熟 , 应 用也 有一 些限制, 但它已成功地应用于人工智能、 机 器学习等领 域 41。 K oza等 人描述 了基 本的 遗传编 程方 法并且 给出 了很多 可以 被 GP成功学习的程序 42 44。319机器学 习学习能力是 高级自适应系统所具备的能力之一, 基于遗传算法的机器学习,特别是分 类器系 统,在 很多领 域中都 得到了应用。遗传算法被用于学习模糊控制规则 , 可以更好地改进模糊系统的性能 ; 基于遗传算法的机器学习不但可以用来调整人工神经网络的 连接 权, 也可 用于 人工 神经 网络
39、 结构 的优 化设计 45,46。3110数据挖掘数据挖掘能 够从大规模数 据库中 提取隐 含的、未知的、有潜在应用价值的知识和规则。 许多数据 挖掘问 题可以 看做是搜索问题。其中 , 数据库可 看做是 搜索空 间, 挖 掘算法 可看做#2914#计 算 机 应 用 研 究第 25卷名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 是搜索策略。应用遗传算法在数据库中进行搜索, 对随机产生的一组规则进行进化, 直到 数据库 能被该
40、 组规则覆 盖, 从而挖掘出隐含在 数据库 中的 规则4749。 Sunil已 成功 地开发 了一个基于遗传算法的数据挖掘 工具 50, 利用该 工具 对两个 飞机失事的真实数据库进行了数据挖掘实验, 结果表明遗传算法是进行数据挖掘的有效方法之一。4近五年国内遗传算法研究现状在前人研究的基础上 , 本文以已 发表论 文为依 据, 重 点考查了 2002)2006年国内学者及工程技术人员在遗传算法方面的研究 情 况, 如 表 1所 示。该 表 数 据 的 统 计 源 是 中 国 知 网( CNKI)的 /电子技术 及信息科学类0中收录的中文核心期刊。表 12002) 2006年国内遗传算法研究现
41、状年度综述函数优化组合优化生产调度自动控制机器人学图像处理人工生命遗传编程机器学习数据挖掘2002699104231991833166200391027827882723201020044127933921828101715200531207732258322226212006194572812724211612表 1 分别从综述、函数 优化、组合优化、生产 调度、自动控制、 机器人学、图像处 理、 人 工生命、遗传 编程、机器 学习、数据挖掘 11个方面 对近五年 国内发表在 中文核心 期刊上、与遗传算法有关的论文进行了分 类。图 1是根 据表 1 生成的对 比分析图。通过对表1及图 1的分
42、析可以得出如下结论:a)针对遗传算法函数优化和组合优 化方面 进行研 究的文章每年几乎都是最多的。这说明 对遗传 算法进 行的研 究更多的还是停留在理论层面, 而生产调度及自动控制等实际应用领域的研究成果较少, 有待进一步深入研究。b)总体来看 , 近五年国内对遗传算法 的研究 在逐年增 长,但从 2005年起有所回落 , 到 2006年出现减少的现象。从这一现象来看 , 国内关于遗传算法的研 究兴趣 可能已达 到饱和 , 理论研究已经比较成熟。另外 , 就目 前研究 现状来看 , 很 难在原有的基础上得出更多新的成果。c)遗传算法在数据挖掘和机器学习 领域进 行的研 究在研究成果中所占的比重
43、逐年明 显增长。这 说明遗 传算法 在数据挖掘和机器学习领域的研究 成为新 的热点。虽 然有效 成果占总的研究成果的比例还很少 , 但这是一个可以进行深入研究的方向。5遗传算法的未来研究方向遗传算法在各种问题的求解 与应用 中展现 了其特 点和魅力, 同时也暴露出它在理论和应用上的诸多不足和缺陷。未来几年内遗传算法的研究重点可能集中在以下几方面:a)算法的数 学基 础, 包括 算法 的收 敛性、收 敛速 度估 计、早熟机理的探索与预防、 交 叉算子 的几何 意义与统 计解释、参数设置对算法的影响等方面。 算法的收 敛速度 估计是 当前特别值得研究和探讨的问题 , 它能从理论上对遗传算法的任何修
44、正形式提供评判标准 ,从而指明改进算法性能的正确方向。b)遗传算法与优化技术的融合。对 遗传算 法的大 范围群体搜索性能与快速收敛的局部优化方法进行混合, 从而产生有效的全局优化方法。这 种策略 可从根本 上提高 遗传算 法计算性能 , 对此可以进行大量的理论分析和实验。c)算法的改进与深化。根据具体应 用领域 对遗传 算法进行改进与完善 , 仅泛泛地对 一般问 题进行 研究是 远远不 够的。当前针对具体应用问题深化研 究遗传算 法是特 别值得 提倡的工作。d)算法的选择。基于实验研究的结 论并不 具有普 遍意义上的指导作用 , 因此从数学的角度进行遗传算法的理论研究将对算法的合理选择提供理论
45、指导。e)算法的并 行化 研究。 遗传 算法 的群 体适 应度 评价、随机搜索等特征使其具有明显的并行性。因此, 设计各种并行执行策略、建立相应的并行化遗传算 法的数 学基础 , 是一 项具有重要意义的工作。6结束语遗传算法作 为一种非确定性的拟自然算法, 为复杂系统的优化提供了一种新的方法 , 实践证明其效果显著。尽管遗传算法在很多领域具有广泛的应用 价值, 但它 仍存在一 些问题 , 各国学者一直都在探索对遗传算法的改进及发展, 以使遗传算法有更广泛的应用领域。参考文献 : 1HOLL ANDJ H.Ad aptation in natural and artifici al s yste
46、msM .Ann A r b or : Un ivers ity ofM ichiganPress , 1975. 2DeJONG K A. The analysis of thebehavior of a classof genetic adap -tive syste msD .Ann Arbor:Un iversity ofM ichigan, 1975. 3GOLDBERG D E. Genetic algorithms in search ,optim ization andma -chine learningM .B oston: Add ison- W esley Long ma
47、n Press ,1989 . 4张文修 , 梁怡 . 遗传算法的数学基础M . 西安 : 西安交通大学出版社 , 2000. 5徐宗本 , 张 讲社 ,郑亚 林.计算 智 能中 的仿 生学 : 理论 与 算法M .北京 : 科学出版社, 2003. 6周明 , 孙树栋 . 遗传算法原理及应用 M .北京 : 国防 工业出版社, 1999. 7唐飞 , 滕弘飞 . 一种 改进的 遗传算 法及其 在布局 优化中 的应用 J.软件学报 ,1999, 10 ( 10): 1096-1102. 8玄光男 , 程润传 . 遗传算法与工程设计M . 北京 : 科学出版社,2000 . 9邢文训 , 谢金星
48、 . 现代优化计算方法 M .北京 : 清华 大学出版社, 1999. 10 何新贵 , 梁久祯 . 利用目标函数梯度的遗传算法 J .软件学报 ,2001 , 12 ( 7): 981 -985. 11 陶卿 , 曹进德 , 孙德敏 , 等.基于约 束区域神经网络的 动态遗传算法 J.软件学报 ,2001, 12 ( 3): 462 -467. 12P OTTS C J ,TERR I D.The develop m ent and evaluation of an i m-proved genetic algorithm based on migration and artificials
49、 election J.IEEE T rans on Sys tems,M an,and Cybernetics ,1994 ,24( 1 ): 73 -86. 13 杨启文 , 蒋静坪 , 张国宏 .遗传 算法优化速度的改进 J.软件学报 , 2001, 12 ( 2): 270 -275.#2915#第 10期葛继科 , 等: 遗传算法研究综述名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 14 DAV ISL.Adap t
50、ive operator p robability in genetic algorithms C / /Proc of the 3rd International Conference on Genetic A lgorithms .SanFran cisco :Morgan Kau f mann Pub lishers , 1989: 61 -69. 15 WH ITLEY D,STARKWEATHER D.Gene-ticII:a distributed ge -netic algorithms J.Journalof Expermi ent al& TheoreticalA rtif