（机械设计及理论专业论文）遗传算法改进及其在tsp和车间调度问题中的应用研究.pdf

内蒙古科技大学硕士学位论文 摘要 遗传算法是一种以达尔文自然进化论和孟德尔遗传变异理论为基础的基于种群 的智能优化算法 蚁群算法则是对群体性昆虫蚂蚁觅食行为进行模拟而提出的一种 新的基于种群的智能优化算法 它们可广泛应用于自然科学 工程技术和现代管理 等领域中各种复杂问题的优化求解 本文对这两种算法进行了仔细的研究 针对它 们收敛速度慢 容易早熟等不足 通过引入新的思想和方法 设计出一种组合式算 法使得这些问题得到改善或解决 并将其成功地应用到了t s p 问题中 改进遗传算 法并将其应用于流水车间调度问题 主要工作包括以下内容 1 首先论述本文研究内容的目的和意义 对t s p 问题及车间调度问题进行了概 述 介绍了遗传算法及蚁群算法的原理及实现技术 包括算法的基本概念 基本操 作 处理流程和基本步骤等 总结了两种算法的改进及应用情况 2 遗传算法和蚁群算法都各有其优缺点 如何扬长避短 充分发挥它们各自的 优势来解决问题是设计这种算法的目的和初衷 本文在对基本遗传算法和蚁群算法 作相应改进的基础上进行整合 并以m a t l a b 为编程平台实现该组合式算法并以t s p 问题作为测试平台对算法的有效性进行了验证 仿真结果表明该算法能够在加速收 敛的同时 有效地防止算法运行中出现的退化现象和早熟现象 容易求得最优解 3 介绍流水作业车间调度的基本理论 并总结了车间生产调度的优化方法和策 略 对流水车间调度问题进行了描述 本文提出了一种改进遗传算法 通过双交叉 和变异来实现种群的多样性 对c a r 类及r e c 类的多个标准算例进行测试 试验结 果表明 改进遗传算法取得了较好的结果 关键词 遗传算法 混合算法 组合优化 车间调度 内蒙古科技大学硕士学位论文 a b s t r a c t g e n e t i ca l g o r i t h mi sap o p u l a t i o n b a s e di n t e l l i g e n to p t i m i z a t i o na l g o r i t h mb a s e do nt h e n a t u r a le v o l u t i o no fd a r w i na n dm e n d e l st h e o r yo fg e n e t i cv a r i a t i o n a n da n tc o l o n y a l g o r i t h mi san e wp o p u l a t i o n b a s e di n t e l l i g e n to p t i m i z a t i o na l g o r i t h mt h a ti sp u tf o r w a r db y t h es i m u l a t i o no ff o r a g i n gb e h a v i o ro fag r o u po fi n s e c t s t h e yc a l lb ew i d e l yu s e di na v a r i e t yo fa r e a ss u c ha sn a t u r a ls c i e n c e s e n g i n e e r i n ga n dt e c h n o l o g ya n dm o d e m m a n a g e m e n te t c s t u d y i n gt h et w oa l g o r i t h m sc a r e f u l l yi nv i e wo ft h e ks l o wc o n v e r g e n c e l a c ko fe a s ya n ds oe a r l y t h i sp a p e rd e s i g n sam o d u l a ra l g o r i t h mb yi n t r o d u c i n gn e wi d e a s a n dm e t h o d st om a k et h e s ei s s u e si m p r o v e do rr e s o l v e d a n di t ss u c c e s s f u la p p l i c a t i o nt ot h e t s pp r o b l e mh a sb e e nc o m et r u e t h ep a p e ri m p r o v e sg e n e t i ca l g o r i t h ma n da p p l i e si tt ot h e f l o ws h o ps c h e d u l i n gp r o b l e m i t sm a i nt a s l sa r et h ef o l l o w i n g f i r s to fa l l t h i sp a p e rd i s c u s s e st h ep u r p o s ea n ds i g n i f i c a n c eo ft s pa n df l o ws h o p s c h e d u l i n gp r o b l e m sa n do v e r v i e w so ft h ei s s u e s i ti n t r o d u c e st h ep r i n c i p l e sa n d i m p l e m e n t a t i o nt e c h n i q u eo fg e n e t i ca l g o r i t h ma n da n tc o l o n ya l g o r i t h m i n c l u d i n gt h eb a s i c c o n c e p t so fa l g o r i t h m s b a s i co p e r a t i o n s p r o c e s s e sa n db a s i cs t e p st od e a l 晰ma n ds oo n a n ds u m m e su pt h et w oa l g o r i t h m s ss t a t eo fi m p r o v e m e u ta n da p p l i c a t i o n g e n e t i ca l g o r i t h m sa n da n tc o l o n ya l g o r i t h mh a v et h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s s oh o wt o d e v e l o pt h es t r o n gp o i n t sa n da v o i dt h ew e a ko n e st og i v ef u l lp l a yt ot h e i r r e s p e c t i v es t r e n g t h st os o l v et h ep r o b l e mi st h ep u r p o s ea n dm i n dt od e s i g nt h ea l g o r i t h m i n t h i sp a p e r t h eb a s i cg e n e t i ca l g o r i t h ma n da n tc o l o n ya l g o r i t h ma r ei n t e g r a t e da sab a s i so f t h e i rc o r r e s p o n d i n gi m p r o v e s m a t l a bp r o g r a m m i n gp l a t f o r m sf o rt h er e a l i z a t i o no ft h e m o d u l a ra l g o r i t h m a n dt s pi su s e da sat e s tp l a t f o r mt ot e s tt h ev a l i d i t y t h es i m u l a t i o n r e s u l t ss h o wt h a tt h ea l g o r i t h mi sa b l et os p e e du pt h ec o n v e r g e n c e m e a n w h i l ei ti se f f e c t i v e i np r e v e n t i n gt h ee v o l u t i o no fp o p u l a t i o n sa n dp r e m a t u r ed e g r a d a t i o n a n da l s oe a s yt of i n d t h eo p t i m a ls o l u t i o n t h i sp a p e ri n t r o d u c e st h eb a s i cf l o ws h o ps c h e d u l i n gt h e o r ya n ds u m m a r i z e st h e w o r k s h o pp r o d u c t i o ns c h e d u l i n go p t i m i z a t i o nm e t h o d sa n ds t r a t e g i e s a l s of l o ws h o p s c h e d u l i n gp r o b l e mi sd e s c r i b e d i tp r e s e n t sa ni m p r o v e dg e n e t i ca l g o r i t h m a n dt e s t st h ec a r c a t e g o r ya n dt h en u m b e ro fs t a n d a r dc a t e g o r i e sr e ee x a m p l e b yt h ed o u b l ec r o s s o v e ra n d m u t a t i o nt oa c h i e v et h ed i v e r s i t yo ft h ep o p u l a t i o n t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t t h e i m p r o v e da l g o r i t h ma c h i e v e sg o o dr e s u l t s k e yw o r d s g e n e t i ca l g o r i t h m h y b r i da l g o r i t h m c o m b i n a t o r i a lo p t i m i z a t i o n f l o ws h o ps c h e d u l i n g 2 独创性说明 本人郑重声明 所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果 尽我所知 除了文中特别加以标注和致谢的地方 外 论文中不包含其他人已经发表或撰写的研究成果 也不包含为获得 内蒙古科技大学或其他教育机构的学位或证书所使用过的材料 与我一 同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并 表示了谢意 签名 登蔓塑日期 半 兰 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留 使用学位论文的规定 即 学校有权保留送交论文的复印件 允许论文被查阅和借阅 学校可 以公布论文的全部或部分内容 可以采用影印 缩印或其他复制手段保 存论文 签名 保密的论文在解密后应遵循此规定 导师签名 盘日期 二芈f 内蒙古科技大学硕士学位论文 1 绪论 1 1 课题研究的目的及意义 1 1 1t s p 问题概述 旅行商问题 即t s p 问题 t r a v e l l i n gs a l e s m a np r o b l e m 直观地说 旅行商 问题就是商人在经商过程中遇到的问题 商人从自己所在城市出发 希望找到一条 既能经过给定顾客所在城市 又能在回家前遍访每一个城市一次的最短路径 t s p 是最古老的 受到最广泛研究的组合优化问题之一 可从 w w w m a t h p r i n c e t o n e d u t s p 获取更详尽的信息 最早可追溯到17 5 9 年e u l e r 提 出的骑士旅行问题 1 9 4 8 年由美国兰德公司的推动 t s p 问题成为近代组合优化 领域的一个典型的 研究最多的n p 难问题之一 但至今尚未彻底解决 它不但具 有广泛的应用背景 而且具有重要的理论价值 t s p 问题形式简单 易于描述 且属于典型的n p 难问题 因此其作为算法研 究与验证的平台而被广泛研究 在t s p 问题上取得的理论或者实验成果 可以应 用于其他的n p 难解问题 实际上 求解n p 难问题的许多方法都源自于t s p 问题 的研究 例如 目前广泛使用的分支界定法 就是首先使用在t s p 问题上的 蚁 群算法从产生甚至到后来的一些改进大都以t s p 问题作为测试用例 同时值得一 提的是 t s p 问题的研究也是上个世纪7 0 年代以来蓬勃发展的计算复杂性理论的 重要推动力 t s p 问题不但具有很大的理论价值 而且在科学 工程及经济的各个方面具有 广泛的应用 是诸多领域内出现的多种复杂问题的集中概括和简化形式 它们包括 印刷电路板的钻孔路线方案 连锁店货物配送路线 管道铺设 网络通讯 交通调 度 机器人控制 矿物结晶学 超大规模电路板布局 电网规划 组合电路测试 基因组测序等 这些问题中有些是t s p 问题的原型 有些转化为t s p 问题后进行 求解 1 1 2t s p 问题的研究现状 由于t s p 问题有着广泛的应用 国内外学者对其进行了大量的研究 早期的 研究使用精确算法求解该问题 常用的方法包括 分枝定界法 线性规划法 动态 规划法等 但是 随着问题规模的增大 精确算法将变得无能为力 因此 在后来 内蒙古科技大学硕士学位论文 的研究中 国内外学者重点使用近似算法或启发式算法 主要有遗传算法 模拟退 火算法 蚁群算法 禁忌搜索算法 贪婪算法 神经网络方法等 在2 0 世纪8 0 年代早期之前 t s p 的解决方法主要集中于构建启发式方法 c o n s t r u c t i o nh e u r i s t i c s c l o a r k e w r i g h t 1 9 6 4 c h r i s t o f i d e s 19 7 6 g o l d e n s t e w a r t 1 9 8 5 b e n t l e y 1 9 9 2 迭代改进算法 i t e r a t i v ei m p r o v e m e n ta l g o r i t h m s f l o o d 1 9 5 6 c r o e s 1 9 5 8 l i n 1 9 6 5 l i n k e m i g h a n 1 9 7 3 以及一些确定性算法 例如分支定界法 或者分支剪支法 l a w l e r 等人 1 9 8 5 给出了关于早期t s p 求 解方法的一个深入的综述 j o h n s o n 和m c g e o c h 1 9 9 7 的综述文章总结了使用启发式方法求解t s p 的 经典算法 直至1 9 9 7 年 这篇文章讨论了不同元启发式算法解决t s p 问题的相 对性能 并得出了使用l i n k e m i g h a n 启发式方法 l i n k e r n i g h a n 1 9 7 3 进行微 调实现的i l s 算法是解决t s p 问题最成功的算法这一结论 在不关心运算时间的 情况下 a p p l e g a t e 等人 1 9 9 9 提出的路径合并方法 t o u r m e r g i n ga p p m a z h 一种 专门用于t s p 的方法 以及h e l s g a u n 提出的带l i n k e r n i g h a n 方法的迭代算法 h e l s g a u n 2 0 0 2 具有最优的性能 4 l 此外 由于各种算法都有其各自的优点和不足 许多学者利用一种算法的优点 的同时通过结合其它算法避免算法的不足 出现了各种各样的混合优化算法 例 如 把遗传算法和模拟退火算法结合起来的模拟退火遗传混合优化 除此以外还有 人工免疫遗传混合优化 免疫模拟退火算法 还有把蚁群算法和遗传算法相结合的 算法 以及人工神经网络与模拟退火算法相结合的算法等等 这些混合优化算法取 得了很大的成功 我们也注意到 使用精确算法求解t s p 所获取的结果也相当引人注目 在 2 0 0 2 年春季 被证明已经获得最优解的最大规模的t s p 实例共包含1 5 11 2 个城 市 求解这个大规模的实例需要一个连通1 1 0 个处理器的网络 并花费相当于一个 5 0 0 m h z 的e v 6a l p h a 处理器2 2 6 年的c p u 时间 尽管这些实验结果反映了精确 算法取得的巨大进步 然而 这只是转移了人们的视线 这些基于t s p 的计算结 果并不能反映精确算法应用于其他众多优化问题时的性能 事实上 对于大量的优 化问题来说 即使只是一个很小规模的实例 都难以使用精确方法来解决1 4 1 1 1 3 车间调度问题 制造业是国民经济最重要的支柱产业 在工业化国家 约有四分之一的人口从 事制造业 约7 0 8 0 的物质财富来自制造业 制造业是我国国民经济的核心和 工业化的原动力 我国制造业工业总产值约占全国g d p 的4 2 5 制造技术是完 内蒙古科技大学硕士学位论文 成制造活动所需的一切技术手段的总称 是支持制造业的技术后盾 其中 生产车 间调度技术又是最重要的制造技术之一 在制造企业中有着举足轻重的地位 一方 面 随着电子技术 计算机技术的发展 制造设备自动化水平和加工能力得到了极 大的提高 制造过程自动化水平也逐渐提高 使得生产调度问题变得更加复杂 往 往超过人的正常决策能力 另一方面 随着市场竞争的激烈化和国际化 出现了多 种先进管理理念及制造模式 它们核心思想无一不是为了适应市场小批量 多品种 和更具个性化的要求 缩短交货周期 控制生产成本 提高产品质量 提高设备利 用率等幽 所以 传统的依靠人来指挥生产加工过程的模式己经远远不能适应新的 制造环境的需要 迫切需要研究有效的生产调度方法和建立生产调度软件系统 使 得生产过程能更加合理和高效运行 生产调度的理论和方法属于软科学 运用它既 不需要增加投资和设备 又不需要增加人员 就可以提高生产和工作效率 因此 研究生产调度的理论和方法 对于力求建设 节约型 社会的今天 提高工作效率 和经济效益 有着重要的现实意义 总的说来 车间调度问题的实质就是在时间上合理配置系统的有限资源 满足 特定目标的要求 典型的车间调度问题包括一个要完成的作业集 每个作业由一个 操作集组成 各操作的完成需要占用机床或其他资源 并且必须按一些可行的工艺 次序进行加工 每台机床可进行作业的某个操作 在约束条件下 调度的目标是将 作业合理地安排到各机床 并合理安排作业的加工次序和加工开始时间 同时优化 一些性能指标 对于车间调度问题 根据加工系统的复杂性 可分为单机 多台并行机 f l o w s h o p 问题和j o b s h o p 问题 根据性能指标 可分为基于调度费用和调度性能 的指标两大类 根据生产环境的特点 也可以将调度问题分为确定性调度和随机性 调度问题 根据作业的加工特点 也可以将调度问题分为静态调度和动态调度 实 际中 车间调度的类型往往是j o b s h o p 型 且是动态的 目前研究比较多的是作 业车间调度 j o b s h o p 问题和流水车间调度 f l o w s h o p 问题 并随着对各类 调度问题研究的深入及各种交叉学科的发展 出现了许多新的车间调度理论和方 法 从目前来看 还没有一个求解流水车间调度问题最优解的简明算法 整数规划 和分枝定界技术是寻求最优解的常用方法 然而对于一些大规模甚至中规模的问 题 这两种方法仍然不是很有效 以遗传算法 模拟退火 禁忌搜索以及人工神经 网络为代表的智能化优化技术来解决流水车间调度问题 受到人们的普遍关注 其 中 遗传算法以其优良的计算性能和显著的应用效果而特别引人注目 所以很多启 发式混合方法都是在此基础上发展起来的 内蒙古科技大学硕士学位论文 1 1 4 车间调度问题的研究现状 自从车间调度问题在2 0 世纪5 0 年代被开始广泛研究以来 经过几十年发展 产生了许多车间调度问题的类型和求解方法 1 9 5 4 年 j o h n s o n 提出了两台机床上f l o w s h o p 排序问题的最优算法 从此人 们开始对排序理论的研究 s t e v e n sa n dg e m m i l l 1 9 9 7 用启发式方法解决了两机器 f l o w s h o p 的排序问题 这些启发式规则简单易行 但难以得到全局优化结果 且 对问题的性质与应用场合的依赖性较强 仿真方法是在排队论 p e t r i 网 极大代数 等方法的基础之上 通过仿真分析在不同情况下系统的性能来进行计划和调度 其 效果依赖于仿真模型的优劣 蔡自兴 1 9 9 0 另外 对j o b s h o p 问题有较好性 能的方法并不能保证对柔性制造系统调度问题同样有较好的结果 r a h i m i f a r da n d n e w m a n 1 9 9 7 经典运筹学中的分枝定界法 割平面法等被用来解决表达为整 数规则的调度问题 b e r r a d ae t a l 1 9 8 6 这些解析方法可以解决规模较小的一些 问题 但是在解决多重复杂条件约束和含有不确定因素的调度优化问题时结果不理 想 a a n e n e t a l 1 9 9 3 m i t t e n t h a l 用模拟退火算法实现了单台机器n 工件的调度 问题 模拟退火算法还被用于f l o w s h o p 排序 机器分组和有资源约束的调度问题 r a b e l oe t a l 1 9 9 3 模拟退火方法模仿晶体的冷却过程 它渐近收敛于全局最 优解 但收敛速较慢 f o o 等 1 9 9 8 应用随机h o p f i e l d 网络来解决调度问题 构 造网络能量函数 i y a p n o w 函数进行优化 当网络迭代收敛时 能量函数达到最 小 神经网络方法己被成功地应用于解决组合优化问题 但在大规模 复杂调度系 统中 存在计算速度慢与结构参数难以确定的缺点 基于知识的调度方法用专家系 统自动产生调度来辅助人去调度 f a r h o o d if a 1 9 9 0 d o u b l e g e r iz 1 9 9 3 b e n 撕e h 1 9 8 6 它将传统的调度方法与基于知识的调度评价相结合 对设计用于生 产实际的高效益 高柔性的现代集成制造系统具有启发意义 1 9 8 5 年d a v i s 首次将 遗传算法用于解决调度问题 d a v i s 提出了排序中局部交换和环状交换等 遗传算 法是一种兼顾优化效果和计算效率的方法 适合于在复杂而庞大的搜索空间中寻找 优化解 在搜索过程中自动获取和积累有关搜索空间的知识 并自适应地控制搜索 过程 遗传算法比较简单 鲁棒性强 易于并行分布处理 非常适合于解决调度问 题 o r v o s hd a v i d1 9 9 4 c h i ua n df u1 9 9 7 f l e u r ya n dg o u r g a n d1 9 9 8 1 2 课题来源及论文的组织结构 1 2 1 课题来源 内蒙古自治区自然科学基金项目 编号 2 0 0 7 11 0 2 0 7 1 3 内蒙古科技大学硕士学位论文 1 2 2 研究内容 本文主要研究了遗传蚁群混合算法的实现及改进方法 并将其用于t s p 问题的 求解 以及使用改进遗传算法处理车间流水作业调度问题 具体研究内容如下 第1 章主要论述本文研究的目的和意义 对t s p 问题及车间调度问题及其求解 算法进行概述 第2 章和第3 章分别介绍了遗传算法和蚁群算法的基本原理 实现技术 改进 与应用情况等 第4 章主要介绍对遗传蚁群混合算法的实现及进一步的改进 以t s p 问题为测 试算例 对算法进行仿真 第5 章分析了f l o w s h o p 调度问题 运用改进遗传算法进行实验仿真 对结果 进行对比分析 第6 章对全文的工作进行了总结 并对进一步研究方向作了展望 内蒙古科技大学硕士学位论文 2 遗传算法 遗传算法 g e n e t i ca l g o r i t h m 是模拟生物进化过程与机制求解极值问题的一种 白适应人工智能方法 早在2 0 世纪4 0 年代 就有学者开始研究如何利用计算机进行 生物模拟的技术 他们从生物学的角度进行了生物的进化过程模拟 遗传过程模拟 等研究 但由于缺乏一种通用的编码方案 只能依赖变异而非交叉来产生新的基因 结构 因而收效甚微 6 0 年代中期 美国m i c h i g a n 大学的j o l l nh o l l a n d 等人提出了 位串编码技术 创造了一种基于生物遗传和进化机制的适合于复杂系统优化计算的 自适应概率优化技术 这种编码既适于变异操作 又适于交叉操作 并且强调将交 叉作为主要的遗传操作 1 9 7 5 年 h o l l a n d 教授出版了专著 自然与人工系统中的 自适应性行为 l j 该书首次系统地阐述了遗传算法的基本理论和方法 提出了对 遗传算法的理论发展极为重要的模式理论 s c h e m at h e o r y 经过了3 0 多年的发展 遗传算法己成为一个多学科 多领域的重要研究方向 近年来 遗传算法在许多领 域得到了成功的应用 例如 约束优化问题 组合优化问题 可靠性优化问题 流 水车间及作业车间调度问题 机器调度 数据挖掘 图像处理 设备布局 智能控 制等 2 1 1 3 1 2 1 遗传算法发展简史及研究现状 遗传算法被提出之后立即受到了各国学者的广泛关注 有关遗传算法的研究成 果不断涌现 1 9 6 8 年h o l l a n d 提出了著名的模式 s c h e m a 定理 1 9 7 5 年d ej o n g 首 先尝试将遗传算法用于函数优化 提出了5 个测试函数用以测试遗传算法的优化性 能 1 9 8 1 年b e t h k e 应用w a l s h 函数分析模式 1 9 8 3 年w e t z e l 用遗传算法解决了 n p 难问题旅行商问题 t s p 1 9 8 5 年s c h a f f e r 利用多种群遗传算法研究解决了多目 标优化问题 1 9 8 7 年g o l d b e r g 等人提出了借助共享函数的小生境遗传算法 1 9 8 9 年 g o l d b e r g 出版专著 g e n e t i ca l g o r i t h mi ns e a r c h o p t i m i z a t i o n a n dm a c h i n e l e a r n i n g 对遗传算法的研究产生了非常大的影响 5 1 1 9 9 2 年 m i c h a l e w i c z 出版 另一部具有极大影响力的著作 g e n e t i ca l g o r i t h m d a t as t r u c t u r e e v o l u t i o n a r y p r o g r a m m i n g 6 1 从2 0 世纪8 0 年代中期起 遗传算法和进化计算到达一个研究 高潮 以遗传算法和进化计算为主题的国际学术会议在世界各地定期召开 1 9 8 5 年 第一届国际遗传算法会议 i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m s i c g a 在 美国卡耐基 梅隆大学召开 以后每两年召开一届 进入9 0 年代 遗传算法迎来 了兴盛发展时期 无论是理论研究还是应用研究都成了十分热门的课题 尤其是遗 内蒙古科技大学硕士学位论文 传算法的应用研究显得格外活跃 不但它的应用领域扩大 而且利用遗传算法进行 优化和规则学习的能力也显著提高 同时产业应用方面的研究也在摸索之中 此外 一些新的理论和方法在应用研究中亦得到了迅速的发展 这些无疑均给遗传算法增 添了新的活力 遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新 更工程化的应用方面 进化规划年会 a n n u a lc o n f e r e n c eo ne v o l u t i o n a r y p r o g r a m m i n g a c e p 于1 9 9 2 年在美国的加州召开第一届会议 以后每隔两年召开 一届 进化计算会议 i e e ec o n f e r e n c eo ne v o l u t i o n a r yc o m p u t a t i o n 也于19 9 4 年 开始定期召开p 1 1 8 1 1 9 1 此外 相关的国际学术会议还有很多 如 g e c o o g e n e t i c a n de v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e s e a l t h ea s i a p a c i f i cc o n f e r e n c eo n s i m u l a t e de v o l u t i o na n dl e a r n i n g a n n g a i n t e r n a t i o n a lc o n f e r e n c eo n a r t i f i c i a ln e u r a ln e t s g e n e t i ca l g o r i t h m s 等 我国有关遗传算法 进化计算的研究 从上世纪9 0 年代以来一直处于不断上 升的时期 近年来 遗传算法 进化计算的应用在许多领域取得了令人瞩目的成 果 不断地有相关论文及专著发表或出版 目前 关于遗传算法研究的热潮仍在持续 越来越多的从事不同领域的研究人 员已经或正在置身于有关遗传算法的研究或应用之中 研究热点有 收敛性证明 新型高效的遗传算子设计 遗传算法与局部优化算法或智能算法的融合 遗传算法 在各领域的应用研究 软计算与计算智能中的遗传算法等 2 2 遗传算法的特点 遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法 与传统优化算法 如单纯形法 梯度法 动态规划法 分枝定界法等 相比较 遗传算法主要有以 下特点 遗传算法使用概率搜索技术和群体搜索策略 传统优化算法采用点到点的搜 索方式 而遗传算法则采用群体到群体的搜索方式 因而易于达到全局最优 搜索不依赖于目标函数的梯度信息 只需提供能够评价个体相对优劣的数量 指标 适应度 即可 因此 遗传算法的适用面更广 尤其适合于处理复杂的非线性 问题 包括目标函数为高维 不可导 不连续或带有噪声的优化问题 而传统优化 方法对此无法或难以解决 遗传算法以个体的编码作为运算对象 传统的优化算法往往直接利用变量的 实际值本身来进行优化计算 但遗传算法不是直接以变量的值 而是以变量的某种 形式 t 体 的编码为运算对象 这种对变量的编码处理方式 使得我们在优化计 算过程中可以借鉴生物学中染色体和基因等概念 可以模仿自然界中生物的遗传和 内蒙古科技大学硕士学位论文 进化等机理 也使得我们可以方便地应用遗传操作算子 特别是对一些无数值概念 或很难有数值概念 而只有代码概念的优化问题 编码处理方式更显示出了其独特 的优越性 进化过程具有有向随机性 这是遗传算法与穷举法的本质区别 同时 遗传 算法的搜索结果具有非稳定性 与传统优化方法相比 优化效率相对较低 遗传算法本质上是一种无约束优化方法 对于约束优化问题 一般需转化为 无约束优化问题求解 遗传算法具有较强的智能性 可以用来解决复杂的非结构化问题 遗传算法具有可扩展性 易于同别的技术混合使用 遗传算法具有固有的并行性和并行计算的能力 简单通用 鲁棒性强 鉴于遗传算法具有上述特征 一经提出即在理论上引起高度重视 并在实际工 程技术和经济管理领域得到了广泛的应用 其中 对优化问题的求解是遗传算法的 经典应用领域 对于一些非线性 非凸性 非连续性 不可微性的复杂优化问题 当用其他优化方法较难求解时 遗传算法却可以方便地得到较好的结果 2 3 标准遗传算法流程 遗传算法提供了一种求解复杂系统优化问题的通用框架 不依赖于问题的领域 和种类 遗传算法的实现步骤如下 1 编码 由于遗传算法不能直接处理解空间的数据 因此我们必须通过编码 将它们表示成遗传空间的基因型串结构数据 2 种群初始化 随机生成多个个体作为初始群体 由于遗传算法以群体为运 算对象 所以我们必须为遗传操作准备一个由若干初始解组成的初始群体 3 个体评价 适应度评价 计算个体的适应度 遗传算法在搜索进化过程 中一般不需要其他外部信息 仅用评估函数值来评价个体或解的优劣 并作为以后 遗传操作的依据 4 终止条件判断 若满足终止条件 则以进化过程中所得到的具有最大适应 度的个体作为最优解输出 终止计算 否则 转至下一步 5 选择运算 选择个体不断生成下一代在遗传算法中是极其重要的一个环 节 选择和复制的目的是为了从当前群体中选出优良个体 使它们有机会作为父代 为下一代繁殖子孙 判断个体优良与否的标准就是各自的适应度值 6 交叉运算 将交叉算子作用于群体 交叉操作是遗传算法中最重要的遗传 操作 内蒙古科技大学硕士学位论文 7 变异运算 将变异算子作用于群体 变异操作的目的是挖掘群体中个体基 因的多样性 克服局部收敛 群体经过选择 交叉 变异运算之后得到下一代群 体 2 4 遗传算法的实现技术 2 4 1 遗传算法的编码方式 在遗传算法的运行过程中 不是直接对所求问题的实际设计变量进行操作 而 是对可行解的编码表示施加选择 交叉 变异等遗传运算 通过对编码的操作达到 对原问题的优化目的 这是遗传算法不同于传统算法的特点之一 无论用什么方法来编码 在算法执行完选择 交叉和变异等运算后 其出现的 基因型必须是合法的基因表示方式 也就是说 好的基因编码方法不但能够表示所 有合法的基因组合 同时 不会因为执行遗传算法的基本运算 而生成不合法的个 体 编码是应用遗传算法要解决的首要问题 也是实施遗传算法的一个关键步骤 编码方式决定了染色体的表现方式 它还决定了搜索空间到可行域的解码方法 而 且编码方法还直接决定了遗传算子的算法程序设计 因此 编码方法在某种程度上 决定了算法的运行效率 对于具体的应用问题 如何设计一种完美的编码方案一直是遗传算法的应用难 点之一 目前对编码问题还没有形成完善的理论 d ej o n g 曾提出了两条操作性较 强的实用编码原则 8 j 编码原则一 有意义积木块编码原则 应使用能易于产生与所求问题相关的且 具有低阶 短定义长度的编码方案 在此原则中 模式是指具有某些基因相似性的个体集合 而具有低阶 短定义 长度且适应度较高的模式称为构造优良个体的基因块 该编码原则理解为应使用易 于生成适应度较高的个体编码方案 编码原则二 最小字符集编码原则 应使用能使问题得到自然表示或描述的具 有最小字符集的编码方案 在此原则中 说明常常使用二进制编码方法的原因 因为它满足这条编码原则 的要求 根据理论分析表明 与其它编码字符集相比 二进制编码方案能包含最大 的模式数 它可使得遗传算法在确定的规模群体中能够处理最多的模式 上述两个编码原理仅仅为设计编码提供了一定的准则 这些准则在具体应用时 也可能会出现矛盾 因此 要针对具体问题进行有效的编码设计 内蒙古科技大学硕士学位论文 常见的编码方式 二进制编码 格雷编码 浮点数编码 符号编码 多参数级 联编码等 2 4 2 种群设定 遗传操作是对众多个体同时进行的 这众多的个体组成了种群 在遗传算法处 理流程中 继编码设计之后的任务是初始种群的设定 并以此为起点一代代进化直 到按某种进化停止准则终止进化过程 由此得到最后一代种群 关键问题是 种群 规模 种群中的个体数目 如何设定 有两个因素需要考虑 初始种群的设定 进化过程中各代种群的规模如何维持 1 初始种群的设定 遗传算法中初始种群中的个体是随机产生的 一般来讲 初始种群的设定可采 取如下的策略 根据问题的固有知识 设法把握最优解所占空间在整个问题空间中的分布范 围 然后在此分布范围内设定初始种群 先随机生成一定数目的个体 然后从中挑选出最好的个体加到初始种群中 这种过程不断迭代 直到初始种群中的个体数目达到了预先确定的规模目标 种群规模影响遗传优化的最终结果以及遗传算法的执行效率 当种群规模m 太小时遗传算法的优化性能一般不会太好 降低了群体的多样性 有可能会引起遗 传算法的早熟现象 当群体规模m 太大时可以减少遗传算法陷入局部最优解的机 率 同时较大的种群规模意味着计算复杂程度高 一般种群规模m 取为2 0 1 0 0 2 种群多样性 种群规模的确定受遗传操作中的选择操作的影响最大 模式定理告诉我们 若 种群的规模为m 则遗传操作可从这m 个个体中生成和检测m 3 个模式 并在此 基础上不断形成和优化积木块 直到找到最优解 显然m 越大 遗传操作所处理 的模式就越多 生成有意义的积木块并逐渐进化为最优解的机会就越大 换言之 种群规模越大 种群中个体的多样性越高 算法陷入局部解的危险就越小 所以 从考虑种群多样性出发 种群规模应较大 但是种群规模太大会带来若干弊病 一 是从计算效率着眼 种群越大 其适应度评估次数增加 所以计算量也增加 从而 影响算法效能 二是种群中个体生存下来概率 即被选择的概率 大多采用和适应 度成比例的方法 当种群中个体非常多时 少量适应度很高的个体会被选择而生存 下来 但大多数个体却被淘汰 这会影响配对库的形成 从而影响交叉操作 另一 方面 种群规模太小会使遗传算法的搜索空间中分布范围有限 因而搜索有可能停 内蒙古科技大学硕士学位论文 止在未成熟阶段 引起未成熟收敛 p r c m a t u r cc o n v e r g e n c e 现象 显然要避免未 成熟收敛现象 必须保持种群的多样性 即种群规模也不能太小 所以 必须针对 不同的实际问题 确定不同的种群规模 2 4 3 适应度函数 遗传算法在进化搜索中基本上不用外部信息 仅用目标函数即适应度函数为依 据 遗传算法的目标函数不受连续 可微的约束且定义域可以为任意集合 对目标 函数的唯一要求是 针对输入可计算出能加以比较的非负结果 这一特点使得遗传 算法应用范围很广 在具体应用中 适应度函数的设计要结合求解问题本身的要求而定 适应度函 数评估是选择操作的依据 适应度函数的设计直接影响到遗传算法的性能 2 4 4 遗传算法的基本操作 遗传操作是模拟生物基因的操作 以求逐代优化 不断逼近最优解 在遗传算 法中通过编码组成原始种群后 遗传操作的任务就是对种群的个体按照它们对环境 适应的程度 适应度评估 施加一定的操作 从而实现优胜劣汰的进化过程 遗传算法的遗传操作包括三个基本遗传算子 g e n e t i co p e r a t o r 分别是 3 选择 s e l e c t i o n 交叉 c r o s s o v e r 变异 m u t a t i o n 选择算子相当于对 编码空间进行开拓 交叉和变异算子相当于对编码空间进行探索 过多地开拓将导 致遗传算法过早收敛到局部最优解上 称为早熟 过多探索将严重降低遗传算法的 收敛能力和收敛速度 开拓和探索之间的矛盾也就是选择压力 最佳个体选中的概 率与平均选中概率的比值 与种群多样性之间的矛盾 1 选择算子 在遗传算法中 选择就是优胜劣汰 目的是把优胜的个体直接遗传到下一代或 通过配对交叉产生新的个体再遗传到下一代 选择操作是建立在种群中个体的适应度评估基础上 因此选择过程的第一步是 计算适应度 在被选集中的每个个体具有一个选择概率 这个选择概率取决于种群 中个体的适应度及其分布 目前的选择方法主要有 轮盘赌选择法 也叫适应度比 例选择法 排序选择法 精英选择策略 分级选择法 b o l t z m a n n 选择法 锦标赛 选择法 稳态选择方法 随机遍历抽样法 截断选择法和局部选择法等 常用的选择方法有轮盘赌选择法 排序选择法 精英选择策略 锦标赛选择 法 截断选择法等 内蒙古科技大学硕士学位论文 2 交叉算子 交叉操作是遗传算法区别于其它进化算法的独有特征 遗传算法的交叉算子是 模仿自然界有性繁殖的基因重组过程 其作用在于将原有的优良基因遗传到下一代 种群中 生成新个体 在遗传算法中 交叉算子不仅具有优化功能 而且是产生新 个体的主要手段 交叉算子保证了种群的多样性 是遗传算法基本操作的核心 交 叉点位置的确定和部分基因信息的交换是交叉算子设计的主要内容 实现个体结构重组的交叉算子设计一般与所求解的具体问题有关 无论设计如 何 交叉算子都需要考虑以下问题 交叉算子需满足交叉算子的评估准则 即交叉算子需保证前一代中的优秀个 体的性能在后一代中的新个体中尽可能得到遗传和继承 编码设计与交叉设计是相互联系的 要使设计出的交叉算子能满足上一条的 评估准则 交叉算子设计和编码设计需协调操作 这也就是所谓的编码一交叉设 计 对于二进制编码而言 各种交叉算子都应包括 从由选择操作形成的配对库 m a t i n gp 0 0 1 中 对个体随机配对 并按预先设定的交叉概率来决定每对是否需要 进行交叉操作 设定配对个体的交叉点 c r o s ss i t e 并对这些点前后的配对个体的 部分结构 或基因 进行相互交换 目前常用的基本交叉方法有单点交叉 两点交叉 多点交叉 均匀交叉 算术 交叉等 除上述交叉方法外 还有部分匹配交叉 p a r t i a l l ym a t c h e dc r o s s o v e r p m x 顺序交叉 o r d e r e dc r o s s o v e r o x 循环交叉 c y c l ec r o s s o v e r c 洗牌交叉 s h u f f l ec r o s s o v e r 缩小代理交叉 c r o s s o v