（模式识别与智能系统专业论文）基于改进遗传算法的调度问题研究.pdf

摘要 遗传算法作为一种新型优化算法 由于具有简单 易操作 并行信息处理等 特点 已经在许多领域的优化问题求解方面取得了成功的应用 但是遗传算法在 理论上还不够完善 例如存在容易产生早熟现象以及局部寻优能力较差等问题 影响了其进一步的应用 本文针对常规遗传算法的不足 提出利用分布种群遗传 算法求解j o b s h o p 和f l o w s h o p 问题 提出了一种基于启发式的遗传算法来求解 单机加工时间可控问题 并进行数字计算研究 本文主要内容包括以下几个方面 1 针对常规遗传算法的不足 给出了分布种群遗传算法的抽象形式 并分析 了其收敛性 将该算法运用子f l o w s h o p 和j o b s h o p 问题计算 结果表明 了该算法的有效性 2 针对单机加工时间可控调度问题 使用基于启发式遗传算法求解单机加工 时间可控问题和单机加工时间离散问题 对具有多变量 非线性和不确定 的此类问题的计算结果表明优化整定后的算法在性能上有了明显的提高 3 使用基于分布种群的遗传算法对j o b s h o p 问题的加工时间可控问题进行了 研究 完成了对加工可控j o b s h o p 问题的智能算法求解研究 计算结果表 明了所设计的算法具有优良的品质 关键词 遗传算法 分布种群 n p h a r d 单机加工时间可控 j o b s h o p f l o w s h o p a b s t r a c t a san e wo p t i m i z a t i o nm e t h o d g aw a sw i d e l yu s e di nt h eo p f m a i z a t i o n so f m a n y f i e l d s o w i n g t o t h e f e a t t t r e s o f s i m p f i c 毋 e a s i l y h a n d i n g a n d p a r a l l e l p r o c e s s i n g h o w e v e rg a t h e o r yi sn o tp e r f e c t s u c ha st h e r ee x i s tt h ep r o b l e m so fe a s i l yc r e a t i n g e a r l i n e s sa n db a da b i l i t yi nl o c a lo p t i m a l e t c e n l i g h t e n e db yd i s m b u t i e no fc r e a t u r e l i v i n g 缸n a t u r e t h em a t h e m a t i cm o d e lo f t h ed i s t r b u f i o np o p u a t o nb a s e dg e t i c a l g o r i t h m d p g a i sp r o p o s e di nt h i sp a p e r a n di t sc o n v e r g e n c ea n a l y s i sa a l s o g i v e n d p g ai sa p p l i e dt oo p t i m i z et h ej o b s h o pp r o b l e m j s p a n dh o w s h o p p r o b l e m s f s p a n dt h em o d i f i e dg a b a s e do l lh e m i s t i cm l e si sp r e s e n t e df o rt h e s i n g l em a c h i n es c h e d u l i n gp r o b l e m sw i t hc o n t r o l l a b l ep r o c e s s i n gt i m e s t h et h r e e p r o b l e m sa r et y p i c a l l yn l h a r d w h i c hl n e a l l st h a ti ti si m p o s s i b l et of i n dt h eg l o b a l o p t i m u mi np o l y n o m i a lc o m p l e x i t y g o o da l g o r i t h m sf o rt h i sp r o b l e mc a np r o m o t e p r o d u c t i v i t yo fe n t e r p r i s e s t h es i m u l a t i o nt e s t s 搬m a d ea n dt h er e s u l t sd e m o n s t r a t e t h ee f f i c i e n c yo ft h ea b o v em e t h e d r 1 n b em a i nc o n t e n to ft h i st h e s i si n c l u d e st h e f o l l o w i n g 1 e n l i g h t e n e db yd i s u i b u t i o no fc r e a t u r el i v i n gi nn a t u r a le c o l o g ye n v i r o n m e n t t h em a t h e m a t i cm o d e lo ft h ed i s t r i b u t i o np o p u l a t i o nb a s e dg e n e t i ca l g o r i t h m a n dt h ec o n v e r g e n c ea n a l y s i so f d p g aa r eg i v e n 2 t h ea l g o r i t h m sb a s e do nd p g ai sd e s i g n e df o rt h ej s pa n df s p t h es i m u l a t i o n t e s t sf o rs o m eb e n c h m a r k ss h o wt h ee f f i c i e n c yo f t h ed p g a 3 t h em o d i f i e dg ai sp r e s e n t e dt og e tt h eo p t i m a lr e s u l t so ft h en p h a r ds i n g l e m a c h i n ep r o b l e mw i t hc o n t r o l h b l ep r o c e s s i n gt i m e sa n dt h en p h a r ds i n g l e m a c h i n ep r o b l e mw i l hd i s e r 础c o n t r o l l a b l ep r o c e s s i n gt i m e s t h eg o o d p e r f o r m a n c eo f t h em o d i f i e dg a i sr e a c h e d k e y w o r d g e n e t i ca l g o r i t h m d i s t r i b u t i o np o p u h t i o n n p h a r d s i n g l em a c h i n e s c h e d u l i n gw i t hc o n t r o l l a b l et i m e s j o b s h o p f l o w s h o p m 致谢 遗传算法是一种新发展起来的优化算法 具有对求解问题的要求不严格 使 用方便等特点 已经成为人们解决复杂问题的新方法和新思路 广泛应用于许多 领域 但其在理论和应用方法上仍存在许多不足和缺陷 主要是如何编码解码 如何改进交叉变异操作使之更有效 由于大多数调度问题是n p h a r d 的 搜索算 法的设计对调度结果的好坏有着极大的影响 因此如何寻找一种有效优的搜索方 法求解调度问题就具有重要的研究和应用意义 本文是本人在浙大求学期间对遗 传算法进行研究的总结 并在此基础上对调度问题应用进行讨论 本文是在王宁教授的指导下完成的 另外王骥程先生 王树青教授 张建明 副研究员等老师都给过我许多指导和帮助 在此表示真诚的谢意 对本文以及对我提供了帮助的人还有许多一起求学的师兄妹们 陈庆更 徐 丰 董胜利 阐晓旭 李奇安 蒋丽英 周韶园 陈铭 杨顶方 张日东 苏成 利 陶吉利 黄亮 潘彩霞 谢懿 陈良 杜鹃 潘文斌等同学 在此一并向他 们表示由衷的感谢 特别感谢陈庆更 陈铭 宣琦 李晓波 童长飞 陈露 唐 亮 张浩 他们在学习和生活上给予我无私的帮助 最后更是从心里感激父母家人在我成长的一路上始终对我倾注着无限的爱 没有你们有力的支持和无私的爱我不会走的那么远 祝你们健康幸福 谨以此文献给所有关心和支持我的人们 2 0 0 6 年5 月于浙大玉泉 浙江大学硕士学位论文 第一章绪论 提要 本章阐述了调度问题的背景和课题意义 简要介绍了调度问题和遗传算法的 产生 发展以及研究现状 概迷了求解复杂调度问题的各种优化方法 并介绍了 本文的主要工作和成果 关键词 调度 f l o w s h o p j o b s h o p 优化算法 1 1 引言 自动化技术的应用使人类从繁琐劳累的体力劳动中解放出来 极大提高了工 农业的生产效率 产品质量 因而创造了巨大的财富 生产管理中的调度问题作 为其中关键的环节 在过去的数十年里 随着工业生产规模的日益扩大和生产操 作方式的改变 其理论和技术得到了迅速的发展 调度问题有着深刻的实际背景 是工农业生产 国防 科研 交通运输以及各种服务行业中普遍遇到的问题 一 般地说 凡是有多个不同任务要完成 就有排序问题的存在 这些问题的共同特 征就是要将不同的工作任务安排一个执行的顺序和时间 使预定的目标最优化 所以 排序实质上是要解决如何按时问的先后 将有限的入力物力资源分配 给不同的工作任务 使预定的目标达到最优 随着市场竞争的加剧 企业的生产 正朝着多品种 小批量方向发展 在多品种 小批量制造企业里 由于生产的产 品品种多 批量小 生产组织工作复杂 企业的生产作业计划安排工作难度很大 计划的编制往往凭主观经验 计划的及时性 应变性差 导致产品生产周期长 机床利用效率低等 从而影响了多品种 小批量生产的经济效益 企业的目的是 要以最低成本制造出顾客满意的产品 因此如何进行生产的组织管理 安排生产 计划 进行排序都是我们面临的问题 其中车间作业排序是实现生产高效率 高 柔性和高可靠性的关键 对有效实用的排序方法和优化技术的研究与应用已成为 先进制造技术实践的基础 车间作业调度 j o bs h o pp r o b l e m 简称j s p 是c i m s 领域中研究的 个重 要课题 同时也是在实际中应用最广的运筹学分支之一 这一问题的研究对于在 现有资源条件下提高工作效率和经济效益有重要作用 理论上已经证明车间调度 浙江大学硕士学位论文 问题是一个n p h a r d 口j 要想用多项式复杂度的时间算法找到最优解是不可能的 目前通过数学方法可以得到很多启发式的结果 并且有些可以确定问题解的界 即最劣解与最优解相差得比例 如对2 台机器的f l o w s h o p 问题有j o h n s o n 规则 k u s i a k 规则1 2 3 对m 台机器h o w s h o p 问题有p a l m e r 启发式算法和g u p t a 启发 式算法 一般而言 在实际生产中即便一个次优解也能带来很大的经济效益 所以人 们探索了许多途径以寻求最佳近似解 但是结果却不令人满意 目前大部分研究 工作集中在车间作业调度上 没有考虑资源分配 一般都直接将资源作为约束处 理 从很多研究结果和应用可以看到j s p 的研究有其实际工程意义而且也有深远 的理论意义 这是由于 一方面 车间作业调度问题的研究不仅可以推动相关算 法的发展 如 模拟退火算法 遗传算法 神经网络 免役算法f 6 等 而且还能 在此基础上提出新的算法 这为其它领域类似问题的解决提供了条件和手段 另 一方面 车间作业调度阃题的解决本身具有实际意义 一个好的车间作业调度方 案不仅可以降低生产成本 而且可以提高企业产品的准时交货能力 从而增强企 业的竞争力 1 2 车间调度问题现状及发展 调度问题是一个典型的n p h a r d 问题 理论上已经证明在多项式时间复杂度 内使这一类问题找到全局最优解是不可能的 由于调度问题的复杂性州 导致不 同的研究者从不同的角度研究某一方面的问题 并随着对各类调度问题研究的深 入及交叉学科的发展 涌现出了许多新的车间调度理论与方法 主要分为两类 一类是近似方法 一类是最优化方法 用近似方法求解作业调度问题时 可以很 快得到问题的解 但不能保证得到的解是最优的 用最优化方法求解这一问题时 可以得到全局最优解 但只能解决小规模的作业调度问题 而且求解速度相当慢 对于作业调度问题的研究 已有数十年的历史 观 早在1 9 5 4 年 自从 s j o l m s o n 对两台机床的h o w s h o p 型调度问题进行了研究后田 人们便开始了对 调度问题的广泛研究 1 9 6 0 年 r g i f f l e r 和g l t h o m p s o n 提出了用于生产调度 的优先分派规则方法 1 9 6 6 年 l g e r e 提出了用于j o b s h o p 调度问题一组基于 优先分派规则的启发式算法 1 9 6 9 年 e b a l a s 使用基于析取图 d i s j u n c t i v e g r a p h 的列举方法来处理机器的调度问题 以上是一些较早的关于j o b s h o p 问题研究 浙江大学硕士学位论文 的早期文献报道 2 0 世纪6 0 年代以来越来越多的工作集中在车间调度领域 在求解j o b s h o p 调度问题时 强调使用列举方芜 e d 岫觚出v em e t h o d 求解这一问题 然而 用 列举算法求解j o b s h o p 调度问题时 需要对求解过程进行细致完备的数学表达 虽然列举算法的策略对这一问题有着重要的理论价值 但从很多的研究工作可以 看出 应用列举法来求解这一问题的结果是令人失望的 这是因为使用列举方法 对很多调度问题得不到可行解 因此 它们在实际使用中受到了限制 分枝定界方法 b r a n c h b o u n d 简称b b 是一个主要的列举策略方法之 一 它用动态结构分枝来描述所有的可行解排序的解空间 这些分枝隐含有要 被搜索的可行解 这个方法可以用数学式和规则来描述 在对最优解搜索过程中 它允许把大部分的分枝从搜索过程中去掉 这种方法从它诞生之日起 流行了很 多年 它对解决总工序数n 2 5 0 的问题非常适合 而当要处理大规模问题时 由于这种算法需要较多的计算时间 因此限制了它的使用 此外 b b 方法对初 始上界值相当敏感 如果初始上界值设置不当 则不能得到最优的可行解 目前 对这种方法研究的重心是如何改进分枝定界的策略 从而产生一个更有效的排除 规则 以便在最初的搜索阶段从被考虑的问题中去掉大量的节点 2 0 世纪7 0 年代到8 0 年代中 人们研究的重点转移到了证明j o b s h o p 调度 问题的复杂性 1 2 1 从对j o b s h o p 调度问题复杂性的大量研究工作中 人们发现 仅有极少数特殊实例可以在多项式时间内解决 由于j o b s h o p 调度问题的复杂 性及精确列举方法所存在的上述问题 近似方法变成了一种可行的选择 近似方 法的不足是不能保证得到最优解 由于它求解速度快 因而可用于解决较大规模 的j o b s h o p 调度问题 2 0 世纪8 0 年代末 对j o b s h o p 调度问题的研究工作的重点从对其复杂性的 分析转到最优化方法的探索上来 由于优先分派规则的缺陷 人们有着对更加适 合的最优化技术的追求 8 0 年代束和9 0 年代初是最优化技术最繁荣的时期 在 这个时期涌现出大量的求解j o b s h o p 调度问题新方法 如r n o w i c k 用约束满足 技术和w f 0 0 1 1 1 用神经网络技术求解这一问题 还有e t o t e r 的多起点局部搜索 m ia a r h m 吼和t p e t e r 的模拟退火 s a c g l o v e r 和i c t a i l l a r d 的禁忌搜索口s d n a k a n o 和r d e l l a r 的遗传算法 g a s 等 以下作简要说明 1 遗传算法 遗传算法 g e n e t i ca l g o r i t h m 简称g a 是由j h o l l a n d 于1 9 7 5 j 浙江大学硕士学位论文 年受生物进化论的启发而提出的嘲 g a 是基于 适者生存 的一种高度并行 随机和自适应的优化算法 它将问题的求解表示成 染色体 的适者生存过程 通过 染色体 群的一代代不断进化 包括复制 交叉 和变异等操作 最终收 敛到 最适应环境 的个体 从而求得问题的最优解或满意解 g a 是一种通用 的优化算法 其编码技术和遗传操作比较简单 优化不受限制条件的约束 而其 两个最显著的特点则是隐含并行性和全局解空间搜索 已经应用于求解组合优化 问题中 如k n a p s a c kp r o b l e m t m i n i m u ms p a n n i n gt r e ep r o b l e m l 硼和车间调度 问题 2 l 但g a 在解决f m s 调度问题时也出现了计算速度较慢和过早收敛的问 题 为了克服g a 的不足 人们对g a 进行了大量的改进t 2 z 2 模拟退火法 模拟退火算法 s i m u l a t e da n n e a l i n g 简称s a 的思想最早由 c m e t t o p o l i s 等 1 9 5 3 提出的渊 1 9 8 3 年e x i r k p a 廿i c k 等将其用于组合优化 s a 算法是基于m e n t ec a d 0 迭代求解策略的一种随机寻优算法 其出发点是基于 物理中固体物质的退火过程与一般组合优化问题之间的相似性 模拟退火算法在 某一初温下 伴随温度参数的不断下降 结合概率突跳特性在解空间中随机寻找 目标函数的全局最优解 由于模拟退火法能以一定的概率接受差的能量值 可以 在局部优化时能概率性地跳出并最终趋于全局最优 但它的收敛速度较慢 很难 用于实时动态调度环境 王凌等将模拟退火的概率突跳性和遗传算法的并行搜索 结构有机结合唧 用于求解流水线调度问题 并提出了处理一类含同工件流水线 调度问题的混合优化策略 该算法不仅能够动态缩小搜索空间以提高搜索效率 而且在保优策略的基础上利用重升温技术来增强克服陷入局部极小的能力 其有 效性和快速性得到了改善 3 禁忌搜索法 禁忌搜索 i s t a b us c 缸c h 的思想最早由f g l o v e 目r 1 9 8 6 提出 2 4 1 z 日 它是对局部邻域搜索的一种扩展 是一种全局逐步寻优算法 是对人类智 力过程的一种模拟 t s 算法通过引入一个灵活的存储结构和相应的禁忌准则来 避免迂回搜索 并通过藐视准则来赦免一些被禁忌的优良状态 进而保证多样化 的有效探索以最终实现全局优化 相对于模拟退火和遗传算法 t s 是又一种搜 索特点不同的m e t a h e u r i s t i c 算法 迄今为止 t s 算法在组合优化 生产调度 机器学习 电路设计和神经网络等领域取得了很大的成功 对于复杂的组合优化 问题 禁忌搜索也是一种通过邻域搜索以获取最优解的方法 e g l o v e r 叙述了它 的基本原理并给出了解决f l o ws h o p 调度问题的禁忌搜索算法 为了更有效地 4 浙江大学硕士学位论文 搜索解空间 引入了插入移动和移动相结合的机制以提高了搜索效率 韩丽敏等 用大量实例验证了禁忌搜索法在求解f l o ws h o p 问题有高效性1 2 4 神经网络优化 神经网络优化算法瑚1 就是利用神经网络中神经元的协同 并行计算能力来构造的优化算法 它将实际问题的优化解与神经网络的稳定状态 相对应 把对实际问题的优化过程映射为神经网络系统的演化过程 1 9 8 2 年 j j h o p f i e l d 通过引入能量函数的概念 研究网络的动力学性质 并用电子线路设 计出相应的网络 从而 开拓了神经网络用于联想记忆和优化计算的新途径 进 而掀起了神经网络新的研究热潮 用h o p f i c l d 网络解决t s p 问题就是其在组合 优化问题中的最成功的应用之一 王万良等基于h o p f i e l d 神经网络求解车间调度 问题 其对车间调度问题的换位矩阵表示方法进行了改进 给出新的车间调度问 题的h o p f i e l d 神经网络计算能量函数表达式 然后提出改进的h o p f i e l d 神经网络 车间调度方法嗍 这个时期研究工作主要集中于对近似算法的研究 如g c a r l i e r 和免l p i 砌 在1 9 8 9 年提出了一种b b 方法 l q 用这种方法a d m a s 在1 9 8 8 年提出了s h i f t i n g b o t t l m e c kp r o c c d u r e s b p s b p 是第一个解决f t l 0 标准问题的启发式算法 s b p 算法的主要贡献是提供了用单机调度去决定将被排序的机器中一个合理工件加 工顺序 随着科技的发展和工程应用范围的拓宽 调度问题的规模越来越大 复 杂度越来越高 传统算法的优化结果往往不够理想 尽管启发式算法对问题的依 赖性较强 但对特殊问题却能利用问题信息较快地构造解 其时间性能较为理想 柳 所以 如何合理结合启发式和进化算法的优点来构造新算法 对于实时性和 优化性同样重要的工程领域具有很强的吸引力 基于这种观点 混合算法的思想 已成为提高优化问题求解的一个有效途径 也就是使一些单一算法相互结合取长 补短 产生更好的优化效率 例如 王凌采用n e h 算法初始化遗传算法的主群 体 来求解f l o ws h o p 问题并获得了较好的效果d 近年来 基于混合算法在工 程中已有较多应用 有机地将一些算法的优点相结合 提出更有效的算法 拓宽 优化算法在工程实际中的应用 浙江大学硕士学位论文 1 3 车间调度研究存在的问题 对车间调度问题的研究已有几十年的历史并取得了丰富的成果 但也提出了 许多尚待解决的问题 例如 1 采用遗传算法求解车间调度时 存在早熟和收敛速度侵等问题 此外 g a 的解空间和染色体空间转换时很难相互对应 并且有出现死锁的可能 2 每种算法都有其缺点 取长补短能更好解决问题 3 还有动态规划算法与分析定界算法等 这些方法是建立在对可能调度的 部分枚举上 寻找具有多项式复杂性的最优算法几乎是不可能的 因此它们只能 解决小规模的车间调度问题 距离实际应用还有较大距离 1 4 排序问题的描述及分类 1 4 1 排序问题的描述 由于j o b s h o p 问题是排序闯题的一种 为便于理解 我们先说明排序阀题 排序问题的名词术语来自加工制造行业 这里所说的 机器 代表服务者 工 件 代表服务对象 对于一般的排序问题 机器 和 工件 都有多个 要解 决的闯题是服务者对服务对象的服务顺序和时间安排问题 从一般的意义上讲 调度问题可以表述为 一个或多个服务者为两个或两个以上服务对象服务时 如 何确定服务顺序 使预定目标 调度成本的指标 如 加工费用 库存费用等 调度性能的指标等 如 生产周期 平均流动时闻 用户要求的指标 最大拖延 时间 平均拖延时间 拖延零件的数量等 达到最优 假定有n 个工件 j 1 要经过m 台机器n m 2 m 1 加工 一个工件在一台机器上的加工称为一道 工 序 加工顺序要求表示工件加工在技术上的约束 即工件的加工工艺过程 这 是事先给定的 用 加工顺序 表示各台机器上工件加工的先后顺序 加工顺序 是排序要解决的问题 工件的工序对于不允许中断加工的情况来讲 一个工件在 m 台串联机上加工是需要在这m 台机器上的每一台机器上都加工一次 我们把 工件西在一台串联机上的加工称为工序 o p e r a t i o n 并记为d 扣如果所有工件的工 序约束相同 即所有工件在机器上的加工次序相同 这种调度称为f l o w s h o p 或者称为流水调度作业 如果每个工件在机器上的加工次序都不同 这种调度称 浙江大学硕士学位论文 为j o b s h o p 或者称为顺序调度 以下是这类问题常用的参数 1 输入参数 a 加工时间0 拍c e s s 吨t i m e 指工件巧在机器够上加工所需的时间 用耶 表示 b 就绪时阃 到达时i 间 a r r i v a lt i m e 准备时间 r e a d yl i m e 都是指工件五 可以开始加工的时间 可以用竹表示 c 交货期 d u et i m e 4 表示工件巧的所有工序的加工应该结束的时间 权 w e i g h t j 示工件乃的重要性 2 输出参数 在机器和工件的一种安排下 对于一个排序或者一张时间表的输出数据有 a 完工时间 c o m p l e t i 劬e q 是工件每的最后一道工序的加工时间实际结 束时刻 b 运行时f 司 f l o wt i m e 乃 q 0 c 延迟 1 a t e n e s s 与 o 苏 d 龌前 e a r l i n e s s 冯 懈 一与 o j e 误工计数 衄i t p e n a l 伽岫 如果0 巧 那么u f o 如果q 弓那么 广j d 最大完工时问g m m 嚣 o i j 每 n 最大完工时间又称为加工时间全长 m a k 唧a n g 最大延迟l m 砌嚣 与i j 呵翻 1 4 2 排序问题的分类 排序问题有不同的分类方法 常用的分类方法是按机器 工件和目标函数的 特征分类 按机器的种类和数量不同 可以分成单台机器的排序问题和多台机器 的排序问题 对于多台机器的排序问题 按工件加工路线的特征不同 可以分成 单件车间 j o b s h 叩 的排序问题和流水车间 f l o w s h o p 的排序问题 每个工件的 加工路线各不相同 是单件车间排序问题的基本特征 而所有工件的加工路线完 全相同 则是流水车问排序问题的基本特征 按工件到达车间的情况不同 可以 分成静态的排序问题和动态的排序问题 当进行排序时 所有的工件都己到达车 间 可以一次对它们进行排序 这是静态的排序问题 当工件陆续到达车阃 要 随时安排它们的加工顺序 这是动态的排序问题 按目标函数的不同 也可以得 浙江大学硕士学位论文 到性质不同的排序问题 例如 同样是单台机器的排序问题 使平均流程时间最 短和使误期完工的工件数最少 实质是两种不同的排序问题 由机器 工件和目 标函数的不同性质以及一些其他因素的差别 构成了多种多样的排序问题 此外 按参数性质的不同 可以划分为确定型排序问题与随机型排序问题 所谓确定型排序问题 指加工时间和其他有关参数是己知的确定的量 而随机型 排序问题的加工时间和其他有关参数是随机变量 确定型排序问题与随机型排序 问题的解决方法有实质的差别 在实际的排序问题中 动态的 随机型的调度问 题占的比重较大 其求解难度很大 但是 也确有很多排序问题是确定型的 而 且 有很多问题 其中随机因素所占的比重很小 用确定型的模型来处理不仅方 便 而且有足够精确满足要求 1 5 遗传算法的产生 发展和现状 1 5 1 遗传算法的来源 地球上的生物从其亲代继承特征或性状 这种生命现象称之为遗传 h e r e d i t y 研究这种生命现象与机理的科学即为遗传学 g 疵s 众所周知 构成生物的基本结构与功能单位是细胞 c e l l 细胞中含有一种微小的丝状化合 物称为染色体 c h r o m o s o m e 生物的所有遗传信息都包含在这个复杂而又微小的 染色体中 经过生物学家的研究 现在人们已经明白了控制并决定生物遗传性状 的染色体主要是由一种叫做脱氧核糖核酸 d e o x y r i b o n u c l e i ca c i d 简称d n a 的 物质所构成 除此之外 染色体还含有大量的蛋白质 d n a 在染色体中有规律 的以双螺旋结构排列着 它是个大分子的有机聚合物 其基本结构单位是核苷酸 每个核苷酸由四种称为碱基的环状有机物中的一种 一分子戊糖核磷酸分子所组 成 遗传信息是由基因 g e 组成的 而基因就是d n a 中占有一定位置的基本 遗传单位 细胞在分裂时 遗传物质d n a 通过复制 r e p r o d u c t i o n 而转移到新产生的细 胞中 新细胞就继承了旧细胞的基因 有性生殖生物在繁殖下一代时 两个同源 染色体之间通过交叉 c r o s s o v 哪组合 也就是说在两个染色体的某一相同位置处 d n a 被切断 其前后两串分别交叉组合而形成两个新的染色体 另外 在进行 细胞复制时 有可能发生概率很小的某些复制差错 从而使d n a 中的基因发生 浙扛大学硕士学位论文 变异 m u t a t i o n 产生新的基因 这种新的染色体表现出新的性状 如此这般 遗传基因或染色体在遗传的过程中由于各种各样的原因而发生了变化 生物在其延续生存的过程中 逐步适应于其生存环境 使得其品质不断得到 改良 这种生命现象称为进化 e v o l u t i o n 生物的进化是以集团的形式共同进行 的 这样的集团称为群体 p o v u i a t i o n 组成群体的单个生物称为个体 i n d i v i d u a l 每一个生物个体对其生存环境都有其不同的适应能力 这种能力称为个体的适应 度 f i t n e s s 达尔文的自然选择学说删a r l l a ls e l e m i o n 构成了现代进化论的主体 自然选择学说认为 通过不同生物间的交配以及其他一些原因 生物的基因有可 能发生变异面生成新的生物基因 这部分变异了的基因也将遗传到下一代 虽然 这种变化的概率是可以预测的 但具体到哪一个个体发生变化却是偶然的 这种 新的基因依据其与环境的适应程度决定其增殖能力 有利于适应生存环境的基因 逐步增多 而不利于适应于生存环境的基因逐渐减少 通过这种自然选择机制 物种将逐步地向适应于生存环境方向进化 即进化趋势向上 从而产生出愈来愈 适应环境的物种 所以 遗传和变异是决定生物进化的内在因素 自然界中的多 种生物之所以能适应环境而得以生存进化 是与遗传和变异现象分不开的 正是 生物的这种遗传特性 使生物界的物种能保持相对的稳定 而生物的变异特性 使生物个体产生新的性状 甚至形成新的物种 推动了生物的进化和发展 遗传 算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型 遗传算法 的核心思想同生物进化相似 1 5 2 遗传算法的发展历程 科学技术发展的显著特点之一是生命科学与工程科学的相互交叉 相互渗透 和相互促进 遗传算法的蓬勃发展正体现了学科发展的这一规律 自然界的生物进化是一个不断循环的过程 在这一过程中 生物群体不断的 完善和发展 可见 生物进化过程的本质是一种优化过程 在计算科学上具有直 接的借鉴意义 在计算机技术迅速发展的今天 不仅可以在计算机上模拟实现生 物进化过程 而且还可以实现进化过程 创立新的优化计算方法 并应用到复杂 工程领域之中 遗传算法 g 饥c t i ca l g o r i t h m 简称g a 是由美国m i c h i g a n 大学的j h o l l a n d 9 浙江大学硕士学位论文 教授于1 9 7 5 年首先提出的 1 研 其基本思想是模拟上述的自然界遗传机制和生物 进化论而形成的一种过程搜索最优解的算法 遗传算法在形式上与基于导数的解 析方法和其他启发式方法一样也是一种迭代方法 它从选定的初始解出发 通过 不断迭代逐步改进当前解 直到最后搜索到最优解或满意解 在遗传算法中 迭 代计算过程采用了模拟生物体的进化机制 从一组解 群体 出发 采用类似于自 然选择和有性繁殖的方式 在继承原有基因的基础上 生成具有更好性能指标的 下一代解的群体 采用遗传算法求解优化问题的步骤如下 1 随机给定一组初始解 2 评价当前这组解的性能 3 根据 2 的评价结果 从当前解中选择一定数量的解作为基因操作对象 4 对所选择的解进行基因操作 杂交或称为交叉 突变或称为变异 得到 一组新的解 5 返回到 2 对该组新的解进行评价 6 若当前解满足要求或进化过程达到一定的代数 则计算结束 否则转向 3 继续进行 同其它搜索方法相比 遗传算法的特点是几乎不需要所求问题的任何信息而 只需要目标函数的信息 不受搜索空间是否连续或可微的限制就可找到最优解 因此 遗传算法广泛地应用于自动控制 计算科学 模式识别 工程设计 故障 诊断和社会科学等领域 适用于解决复杂的非线性和多维空间寻优问题 是2 l 世纪智能计算的关键技术之一 需要指出的是遗传算法的思想虽然来源于自然进化 但是它和自然进化的特 性存在不少相异之处 例如 自然进化是在一个动态改变的环境下进行的 没有 静态的最优解 甚至连最优化的标准也是变化的 通过变异及保持种群的多样性 来长期保持种群的可进化性 而在遗传算法中 环境 最优解 优化的标准一般 是静止不变的 遗传算法的目标是收敛于某一最优解 自然进化中的个体的寿命 一般是不同的 而在遗传算法中同一个种群中的个体的寿命一般是相同的 并且 在遗传算法中的个体没有年龄的大小以及性别之分 自然进化中的个体间存在多 种关系 而遗传算法中一般只考虑竞争关系 遗传算法通过交叉和变异模拟了生 1 0 浙江大学硕士学位论文 物进化中的遗传现象和变异现象 但是却没有模拟自然进化中个体的后天学习情 况 比如人类的后天学习对于其生存能力是有很大影响的 所以 我们现在所指 的遗传算法不是自然遗传算法 而是人工遗传算法 遗传算法研究的历史起源可追述到2 0 世纪6 0 年代初期 当时工作是以对自 然遗传系统的计算机模拟为主f 3 习 不久j h o l a n d 教授及其学生认识到自然遗传 算法可以转化为人工遗传算法 提出了利用群体的进化模拟适应性系统的思想 尽管当时没有给出实现这些思想的具体办法 但却给出了群体 适应值 选择 变异 交叉等基本概念 1 9 6 7 年 j h o a n d 的学生l d b a g e y 通过对跳棋游戏 参数的研究 在其博士论文中首次提出了遗传算法这一术语p 叫 1 9 7 1 年 i l b h o l l s t i e n 第一次把遗传算法应用于求解函数优化问题 并阐述了遗传算法用 于数字反馈控制的方法刚 极大地促进了遗传算法的应用 所以 遗传算法既是 一种自然进化系统的计算模型 也是一种通用的求解优化问题的适应性搜索方 法 1 9 7 5 年 j h o l l a n d 出版了著名的专著 自然系统和人工系统的适配 f j 日 该书系统地阐述了遗传算法的基本理论和方法 并提出了对遗传算法的理论研究 和发展极为重要的模式理论 s c h e m a t at h e o r y 首次确认了选择 交叉和变异等 遗传算子 以及遗传算法的隐并行性 从而奠定了遗传算法的理论基础 同年 d j o n g 把自己的计算试验和j h o l l a n d 的理论结合起来 对遗传算法的机理与参 数设计问题进行了较为系统地研究 建立了著名的五函数测试平台 为遗传算法 及其应用打下了坚实的基础册 此后 遗传算法作为函数优化器 f u n c t i o n o p f m 妇t s 不但在各个领域内得到了广泛应用 而且还丰富和发展了遗传算法的 基本理论 1 9 8 0 年 a d b c t h k e 对函数优化g a 进行了研究1 3 日 包括应用研究 和数学分析 s e s m i t h 在1 9 8 0 年首次提出使用变长为串的概念1 3 7 这在某种程 度上为以后的遗传规划奠定了基础 此外 许多研究人员对遗传算法理论的框架 和遗传算子进行了构建和改进 并将遗传算法分别应用于工程设计 自动控制 经济金融 博弈问题 机器学习 人工神经网络 优化调度等诸多领域之中 1 9 8 9 年 d 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 na n d m a c h i n el e a r n i n g 一书嗍 这是第一本遗传算法教科书 它是当时关于遗传算 法领域研究工作的全面而系统的总结 与j h o l l a n d 的著作侧重于适应性系统的 浙江大学硕士学位论文 进化数学分析不同 该书将遗传算法的基本原理与范围广泛的应用实例相结合 并给出了大量可以使用的应用程序 1 9 9 1 年 l d a v s 编辑出版了 遗传算法手 册 h a n d b o o ko f g e n e t i ca l g o r i t h m 一书 3 9 其中包括了遗传算法在工程技术 和社会生活中的大量应用实例 为推广和普及遗传算法的应用起到了重要的指导 作用 随着遗传算法研究和应用的不断深入与扩展 有关遗传算法的国际学术会议 和活动也逐步活跃起来 自1 9 8 5 开始以来 国际遗传会议 即i c g a i n t e r n a t i o n a l c o n f e r e n c eo ng e n e t i ca l g o r i t h m 每两年就举行一次 此外 以遗传算法的理论基 础为中心的学术会议f o g a f o u n d a t i o no f g e n e t i ca l g o r i t h m 也从1 9 9 0 年开始每 两年举行一次 现在每年发表的与遗传算法相关的论文更是数量庞大 这些众多 的论文和频繁的国际会议活动集中反应了遗传算法的学术意义和应用价值 1 5 3 遗传算法的研究现状 遗传算法作为一种搜索算法其基本框架已经形成 在应用中也展现了它的特 点和魅力 但同时也暴露了它在理论和应用技术上的不足和缺陷 所以对遗传算 法的研究仍是方兴未艾 遗传算法的理论和方法研究的主要方向有 1 使遗传算法更好地模拟复杂系统的适应性过程和进化行为 这方面研究 主要是j h o l l a n d 的团队和s a n t af ei n s t i t u t e 的e v c a 研究组 e v o l v i n gc e l l u l a r a u t o m a t a h t t p w w w s a n t a f e e d u p r o j e e t s e v e a 0 等少数单位 大部分研究机构的 研究主要集中于遗传算法作为求解优化问题算法的一系列问题 2 遗传算法的理论研究 这方面的工作主要以收敛性分析为主 即研究群 体收敛到优化问题的全局最优解的概率 遗传算法的理论分析有两类 一类是遗 传算法的马氏链模型 另一类是v o s e l i e p i n s 模型 马氏链模型采用转移概率与 极限理论 v o s e l i e p i l 坞模型采用不动点理论 具有浓厚的几何色彩旧 尽管遗 传算法已经有了不少的理论研究结果 但仍然不能说已经相当完善 遗传算法的 理论研究与实际应用之间还有不小的距离 遗传算法对生物演化的模拟基本上还 是形式的 还未深入到生物演化内部规律的模拟 这使得遗传算法的作用受到限 制 但是我们相信随着生命科学的发展和科学研究者的努力 遗传算法的理论将 会越来越完善 并与其应用相互推动 使遗传算法发挥出巨大的潜力 浙江大学硕士学位论文 3 遗传策略研究和设计 为了维持群体可进化性并最终搜索到问题的全局 最优解 遗传算法必须采用合适的运算形式 将遗传算法应用于优化问题的求解 可以视为一种随机化搜索过程 在该过程中 不仅需要探索解空间上的全局最优 解 而且应当充分利用已获得的解空间信息逼近当前局部最优解 这两者我们分 剐称之为求泛和求精的能力 但是这两种能力并非可以同时获得 对于任何一种 算法来说它们构成了一对矛盾 求精能力好的算法往往不具备良好的解空间上的 搜索能力 反之亦然 对于复杂的应用问题 我们往往需要遗传算法兼备这两种 能力 因此 遗传策略的研究与设计是一个重要的研究方向 具体又可以将之分 成微观遗传策略 m i c r og e n e t i cs t r a t e g y 和宏观遗传策略 m a c r og e n e t i cs t r a t e g y 其中微观策略主要讨论群体规模 遗传算予的形式和参数设计 及其对g a 求解 能力的影响 这方面研究一直集中在对遗传算子适应性的控制上 即进化过程中 遗传算子参数的适应性调整 进而达到预期的搜索目标 遗传算法的宏观策略主 要讨论关于通过对g a 流程的再设计来改变g a 的宏观特征 或者以g a 流程为 基础 引入其它算法构成混合g a h y b f i dg e n e t i ca l g o r i t h m s h g a 啡明 以期 提高g a 求解问题全局最优解的能力 4 遗传算法编码方式 目前遗传算法的编码方式有很多嗍 大致可以分为 二进制编码和非二进制编码 j h o l a n d 建议采用二进制编码 并得到了许多学者 的支持 但非二进制编码中的浮点数编码具有精度高 便于大空间搜索的优点 越来越受到重视 从整体上来讲 二进制编码的进化层次是基因 而浮点数编码 的进化层次是个体 同时 对于非二进制编码 一般结合具体闻题领域的知识 设计合适的遗传操作 或者采用不同的计算模型1 4 1 1 6 本文的研究方法和主要工作内容 求解n p h a r d 问题算法的衡量标准有三种 数值算例 最坏情况分析 和概 率分析 本文将采用理论研究与数字计算相结合 对比验证 并辅以如下三种手 段分析典型实例所得解 来验证不周算法的性能 1 最好解 2 最好解与最优解的偏差 3 达到最好解的频率 解的分布与统计分析 浙江大学硕士学位论文 本文主要研究内容如下 1 针对常规遗传算