（应用数学专业论文）求解jobshop调度问题的混合遗传算法.pdf

中文摘要 作业车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，j s s p ) 是一类满足任务配 置和顺序约束要求的资源分配问题，是最困难的组合优化问题之一。有效的生 产调度方法和优化技术的研究和应用是实现先进制造和提高生产效益的基础和 关键。j o b s h o p 调度问题的研究早在1 9 5 0 年就展开了，求解的方法以启发式算 法为主，基于优先权规则，即从未排序的工序特定子集中选用工序的规则。 鉴于精确方法仅适合予小规模问题，构造性方法优化质量较差且缺少柔性， 本文以混合遗传算法( g e n e t i c a l g o r i t h m ，g a ) 来求解j o b s b o p 调度问题。主要 工作如下：首先，通过对国内外作业车间调度问题的研究，介绍了已有的求解 j o b s h o p 调度问题的各种算法，确定以遗传算法为主要的研究手段。其次，在阐 述遗传算法基本概念、原理、方法的基础上。针对普通遗传算法在求解j o b s h o p 调度问题时，存在着收敛速度慢或易出现“早熟”现象的缺点，本文提出了一 种将禁忌搜索思想与遗传算法相结合的混合遗传算法。在新算法中，一方面， 在选择操作中利用禁忌表的变化来选择产生新种群中的个体：将候选种群中的 个体逐个与禁忌表中记录的个体进行比较，如果其不在禁忌表中记录的个体的 邻域内，则该个体被选择进入新种群，并按照先进先出的原则存入禁忌表中。 如果其已在禁忌表中记录的个体的邻域内，则该个体被禁忌掉，并在新种群中 加入一个随机产生的新个体。通过该选择操作，可以避免超级个体的出现，并 使适应度低的个体也有机会被选中，同时保持了种群的多样性，有效防止了“早 熟”现象的出现；另一方面，对经过遗传算法的交叉和变异操作产生的后代种 群中的个体进行禁忌搜索操作，从而，加快了新算法的收敛速度。最后通过对 标准作业车间调度问题( f t 类、l a 类) 的测试，找到了己公布的最优解，证 明了新算法在求解j o b s b o p 调度问题方面有较好的效果。 关键词：作业车间调度：优化；遗传算法：禁忌搜索 a b s t r a c t j o bs h o ps c h e d u l i n gp r o b l e m ( j s s p ) i so n eo ft h em o s td i f f i c u l tc o m b i n a t o r i a i o p t i m i z a t i o np r o b l e m s ，w h i c ha l l o c a t e sr e s o u r c e si no r d e rt op e r f o r man u m b e ro f t a s k s ，s u c ha st a s k sc o l l o c a t i n ga n do r d i n a lr e s t r i c t i o n t or e a l i z em o d e mm a n u f a c t u r e a n dp r o m o t ep r o d u c t i o ne f f i c i e n c y , r e s e a r c ho ne f f e c t i v ep r o d u c t i o n s c h e d u l i n g m e t h o d sa n do p t i m i z a t i o nt e c h n i q u e sa n di t sa p p l i c a t i o na r et h ef u n d a m e n t a la n d e s s e n t i a lp r o b l e m s a se a r l ya si nt h e1 9 5 0 sm u c hr e s e a r c hh a v eb e e nd o n ea n dt h e m a i ns o l v i n gm e t h o d sa r eh e u r i s t i ca l g o r i t h m s ，w h i c hb a s e do np r i o r i t y , t h a t s a r r a n g i n go p e r a t i o n sf r o mt h es p e c i a ls u b s e t so fu n o r d e r e do p e r a t i o n s a st h ee x a c tm e t h o d sa r e o n l ys u i t a b l ef o rs m a l ls c a l ep r o b l e m sa n dt h e c o n s t r u c t i v em e t h o d sp e r f o r mp o o r l ya n dl a c kf l e x i b i l i t i e sa sw e l l t h i sd i s s e r t a t i o n p r o p o s e sah y b r i dg e n e t i ca l g o r i t h m ( o 吣t os o l v ej s s p t h em a i nr e s e a r c hw o r ki s l i s t e da sf o l l o w s ：f i r s t l y , t h ed i s s e r t a t i o nr e v i e w sh i s t o r i c a ld e v e l o p m e n t so nj s s p d o m e s t i c a l l ya n di n t e r n a t i o n a l l y , i n t r o d u c e se x i s t i n gm e t h o d ss o l v i n gj s s pa n dt h u s c o n f i r m su s i n gg aa st h ep r i m a r ym e t h o d s e c o n d l y , b a s e do nt h ed e s c r i p t i o no f b a s i cc o n c e p m ，t h e o r ya n df u n d a m e n t a lp r o c e d u r e ，t h ed i s s e r t a t i o np u t sf o r w a r dt h ea h y b r i dg aw h i c hc o m b i n e st a b us e a r c h ( t s ) a n dg aw h e nc o n s i d e r i n gt h e d i s a d v a n t a g e so ft h es t a n d a r dg ao nj s s p ( e g p r e - m a t u r ea n dl o wc o n v e r g e n c e s p e e d ) i nt h en e wa l g o r i t h m ，o no n eh a n d ，w eg e n e r a t ei n d i v i d u a l so fn e wp o p u l a t i o n i ns e l e c to p e r a t i o na c c o r d i n gt ot h ec h a n g e so ft a b ul i s t ：c o m p a r i n ge a c hi n d i v i d u a li n p o p u l a t i o nw i t hi n d i v i d u a l sr e c o r d e di nt a b ul i s t 。i fa ni n d i v i d u a li sn o tw i t h i nt h e a r e ao fa l li n d i v i d u a l sn e i g h b o r h o o di nt a b ul i s t t h ei n d i v i d u a lc a nb es e l e c tt ot h e n e wp o p u l a t i o n ，a n db es a v e di nt a b ul i s ta c c o r d i n gt of i r s ti nf w s to u tr e g u l a t i o n ( f i f o ) i fa ni n d i v i d u a li nt h ea r e ao fa ni n d i v i d u a l sn e i g h b o r h o o di nt a b ul i s t w e f o r b i dt h ei n d i v i d u a la n d a d dan e wr a n d o mg e n e r a t e di n d i v i d u a lt ot h en e w p o p u l a t i o n a f t e rs e l e c t i n go p e r a t i o n ，t h es u p e ri n d i v i d u a l 啪b ea v o i d e da p p e a r i n g a n dm a k el o wf i t n e s si n d i v i d u a lh a v et h ec h a n c et ob es e l e c t e di nn e x tp o p u l a t i o n w h i c hm e a n w h i l ec a nk e e pt h ed i v e r s i t yo ft h ep o p u l a t i o na n dp r e v e n tt h ee m e r g e n c e o fp r e - m a t u r e ；o nt h eo t h e rh a n d ，b e c a u s eo fs e a r c h i n ge v e r yi n d i v i d u a lb yt sw h i c h l l a r eg a i n e db yc r o s s o v e ra n dm u t a t i o no p e r a t i o na c c o r d i n gt og a ，t h en e wm e t h o d t h u sa c c e l e r a t e st h ec o n v e r g e n c er a t i o f i n a l l y , b yt e s t i n gt h es t a n d a r de x a m p l e sl i k e 丌 l 气t h ea n n o u n c e dm a k e s p a n sa r eo b t a i n e d ，w h i c hc a np r o v et h en e wa l g o r i t h m s b e t t e rp e r f o r m a n c eo nj s s e k e y w o r d s ：j o bs h o ps c h e d u l i n gp r o b l e m ；o p t i m i z a t i o n ；g e n e t i ca l g o r i t h m ；t a b u s e a r c h i l l 武汉理一 大学硕十学位论文 第一章引言 1 1 研究的背景与意义 生产调度1 1 j ，即对生产过程进行作业计划，作为一个关键模块，是整个先进 生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展 的核心。有效的生产调度方法和优化技术的研究和应用，是实现先进制造和提 高生产效益的基础和关键。从上个世纪5 0 年代起，调度问题的研究就受到应用 数学、运筹学、工程技术等领域科学家的重视，科学家们利用运筹学中的线性 规划、整数规划、目标规划、动态规划及决策分析方法，研究并解决了一系列 有代表意义的调度和优化问题。但是，人们普遍把c o n w a y , m a x w e l l 和m i l l e r l 2 三人有关调度的研究工作作为调度理论研究的正式开始，他们3 人也被人们称 为调度理论的奠基人。此后3 0 多年的调度理论和应用研究都受到他们的影响。 调度问题涉及面非常广泛，所以有很多种调度问题。根据加工系统的复杂度， 生产调度可以分为单机调度、j o bs h o p 调度、f i o w s h o p 调度、o p e ns h o p 调度、 多机器并行加工( 1 【m a c h i n ei np a r a l l e l ) 调度等几个基本类型。单机调度是指所有 的操作任务都在一台机器上完成，需要对任务进行优化排队；j o bs h o p 调度是最 一般的调度类型，它是指由m 台不同的机器加工n 个有特定加工路线f 顺序) 的工 件，不同工件的工序间没有顺序约束，工序加工不能中断：f l o ws h o p 调度假设 所有工件都在同样的设备上加工，并有一致的加工操作和加工顺序；多机器并 行加工调度是指多台机器并行加工工件，而且并行加工的机器和工件都是类似 的。实际的调度问题通常是上述几种调度类型的组合。 本文主要研究求解j o b s h o p 调度问题( j s s p ) 。j s s p 主要对工场内的作业进 行组织、调度和管理。而工场以完成大量的作业为其基本特征，以组织生产过 程，合理利用设备、生产出产品或配件为其主要目的。这些产品通常有一种或 多种不同的处理方式或过程。每种过程又是由一系列工序所组成。这些工序将 占用定的资源并需要在机器上持续一定的时间。对每一种产品的生产，其相 关的工序又要按照一定的次序迸行。求解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 调度问题，既有重要的 理论意义，又能带来巨大的经济效益。 1 2 j o b s h o p 调度问题 1 2 1j s s p 模型 j o b s h o p 调度问题是许多实际生产调度问题的简化模型。j s s p 研究n 个工件 在川台机器上的加工。已知每个工件在各个机器上的加工次序和每个工件的各 个工序的加工时间。要求确定与工艺约束条件相容的各机器上所有工件的加工 开始时刻、完成时刻、加工次序，使加工性能指标达到最优。各个工件和机器 应满足以下约束： ( 1 ) 在整个加工过程中，每个工件只能被所有的机器都加工并且只加工一次： f 2 1 各个工件必须按工艺路线以指定的次序在机器上加工； ( 3 ) 加工过程不能间断； ( 4 ) 每一时刻每台机器只能加工一个工件。 j o b - s h o p 调度问题的求解就是要找到一个合理的安排使每个工件都能在满足 工艺约束的条件下在各台机器上加工，使得总的加工时间最短。对于工件f ，c ，。 为第f 工件在机器k 上的完成时刻，t 为第i 工件在机器k 上的加工时间，如果 机器h 先于机器k 加工工件f ，则应满足如下约束： c * 一t a 之c a 如果机器k 先于机器h 加工工件f ，则应满足如下约束： 定义变量z 。，则： c 曲一f “芑c * 。m 。1 0 ，否则 仉机器 先于机器i 加工工件f 则上述约束可表示为： c 址一t 持+ l ( 1 一工m t ) 芑c m ， i11 , 2 ，- 一，n ，h ，k 一1 , 2 ，- ，t i t 其中l 为一足够大的正数。对于在机器k 上加工的工件i 和j ，如果工件i 先于 2 武汉理工大学硕士学位论文 工件，在机器七上加工，则应满足如下约束 如集工件，先于工件i 在机器上加工，则应满足如下约束 定义变量y 。，则 则上述约束可表示为 阻工件i 先于工衔在机器t 上加工 # 。 o ，否则 c p c 砖+ l ( 1 一y 耻) 之t 业， i ，。1 , 2 ，一，k 。1 , 2 ， 因此一个n m g c ( n 表示工件数，m 表示机器数，g 表示是j o b s h o p 调度问 题，c 去u 表示性能指标为最大完成时间) 的j o b - s h o p 调度问题的数学模型可描 述如下： f - m i n 也一a x m a 。x 1 ( 1 ) s t 一+ 三( 1 一x i l * ) c i h ， i - 1 2 ，f ，h , k - 1 ，2 ，- ，r n c 业一c k + l o y 牡) 辟， i ，j - 1 , 2 ，l ，k 一1 , 2 ，加 气o ，l 2 0 i 一1 , 2 ，n ，七i l 2 ，m - o o r l i 一1 2 ，l ，h ，k - l 2 ，m y m - 0 0 r 1 f ，j 一1 ，2 ，n ，k 一1 2 ，l 1 2 2j s s p 的表示 3 武汉理工大学硕士学位论文 i 2 2 1 甘特图表示 对于，l 台机器( m a c h i n e ) ( m i , m z , m 0 ，n 个工件a o b ) p ，如j 的加工过程， 所谓调度就是分配各工件在各机器上的加工时间，调度通常用甘特图表示。甘 特图( g a n t tc h a n ) 是在2 0 世纪初由亨利甘特开发的。它基本上是一种线条图， 横轴表示时间，纵轴表示机器。甘特图直观地表明任务计划在什么时候进行， 以及实际进展与计划要求的对比。图2 1 为3 个工件3 个机器面向机器的甘特图。 图2 13 工件3 机器甘特图 1 2 2 2 析取图表示 析取图是描述j s s p 的常用工具，对于拄个工件、1 t i 台机器( 共个工序) 的 j s s p ，所对应的析取图为g = 蚴，剧。其中，y 为所有工序构成的顶点集，包括 马和弓两个虚拟工序( 分别表示加工开始和结束) ；一为n 条子边构成的边集，子 边( 实线) 表示某工件按约束条件在所有机器上从开始到结束的加工路径；e 为 ? i 条子边构成的弧集，子弧( 虚线) 表示同一机器上加工各工序的连接。图2 2 为3 个工件3 个机器的一种可能的j s s p 析取图表示。 武汉理工大学项士学位论文 图2 23 工件3 机器析取图 若以最大完成时间为指标，则对j s s p 的求解就归结为到各弧( 即机器) 上 作为优先决策的各工序的一组顺序( 即走向) ，当同一机器上有多个工序出现冲 突时，上述顺序用于决定各工序的先后，最终得到各工序间没有冲突的一个有 向非循环图，其关键路径长度郎为最大完成时问。 1 2 3j s s p 的复杂- 洼 算法的时间和空间复杂性对计算机的求解能力有重大影响。算法对时间和空 间的需要量称为算法的时间复杂性和空间复杂性。j s s p 是经典的n p - h a r d 问题， n 工件研机器的j o b - s h o p 调度问题共有伽秒”个可能解，即6 工件6 机器的j o b s h o p 调度问题共有俐6 = j 4 1 0 1 7 个可能解。 1 3 求解j o b s h o p 调度问题的算法研究现状 自从j o h n s o n 3 首次解决j o b _ s h o p 调度问题以来，经过众多学者的努力，提 出了多种求解j o b s h o p 调度问题的算法，主要可以分为三类：枚举方法，构造 性方法和邻域搜索算法。 ( 1 ) 枚举方法 数学方法： 数学方法通常采用整数规划、动态规划以及决策分析等方法来解决 武汉理一l ：大学硕十学位论文 调度最优化或近似优化问题。生产调度中广泛使用的是混合整数线性规 划( m i x e di n t e g e rl i n e a rp r o g r a m m i n g ，m i l e ) 和混合整数非线性规划 ( m i x e di n t e g e rn o n l i n e a rp r o g r a m m i n g ，m i n l p ) 方法。 分支定界： 分支定界方法通常是把全部可行解空间反复地分割为越来越小的子 集( 称为分支) ，并且为每个子集的解值计算一个下界( 称为定界) 。在 每次分支后，凡是界限超出已知可行解的那些子集不再作进一步分支， 这样，解的许多子集就可以不考虑了。进行这种分支直到找出最优解为 止。 f l o f i a n 等【4 】于1 9 7 1 年最早成功的运用分支定界方法求解j o b s h o p 调 度闯题。c a r l i e r 和p i n s o n “3 于1 9 8 9 年用分支定界方法第一次成功地得到 了f t1 0 ( 由f i s h 和t h o m p s o n 提出的著名的1 0 个工件、1 0 台机器的j s s p ) 的最优解，并在1 9 9 0 嘲、1 9 9 4 年m 对算法进行了改进，改进的算法有更 高的运算效率。 ( 2 ) 构造性方法 优先分配规则： 经过多年的研究，学者们提出了多种分配规则。p a n w a l k a r 和 l s k a n d e r 8 于1 9 7 7 年总结了1 1 3 个分配规则，包括简单分配规则和组合 分配规则，其中常用的列举如下： a ) 简单分配规则： i s p t ( s h o r t e s tp r o c e s s i n gt i m e ) ：即选择加工时间最短的工序。 i i u 叩( 1 0 n g e s tp r o c e s s i n gt i m e ) ：即选择加工时间最长的工序。 i i i f c f s ( f i r s t c o m e f i r s ts e r v e ) ：即选择同台机器上工件队列中 最先的工序。 i v e f t ( e a r l yf i n i s ht i m e ) ：郎选择完成时间最短的工序。 v 叮( 1 a t ef m i s ht i m e ) ：即选择完成时间最长的工序。 v i m w r ( m o s tw o r kr e m a i n i n g ) ：即选择总剩余加工时间最长 的工件。 v i i m n o r ( m o s tn u m b e ro fo p e r a t i o n sr e m a i n i n g ) ：即选择总剩 余工序数最多的工件。 v i i i f n o r ( f e w e s tn u m b e r so fo p e r a t i o n sr e m a i n i n g ) ：即选择总 6 武汉理t 人学硕士学位论文 剩余工序数最少的工件。 i x e d d ( e a r l yd u ed a t e ) ：即选择交货期最早的工件。 x r a n d o m ( r a n d o m ) ：即随机选择。 b 1 组合分配规则 i f c f s s p t ：即对等待时间超过约定时长的工件使用f c f s 规则，如果所有等待调度的工件等待时间小于约定时长则使 用s p t 规则。 i i l p t s p t ：即等待的工件数少于一定的数量就使用l p t 规 则，否则，使用s p t 规则。 c h a n g 等【9 1 于1 9 9 6 年使用线性规划模型对4 2 条规则进行了评估，结 果显示s p t 规则性能最好，而l p t 性能最差。 移动瓶颈方法： 在所有求解j o b s h o p 调度问题的启发式方法中，由a d a m s 、b a l a s 和 z a w a “”于1 9 8 8 年提出的移动瓶颈方法是目前最好的方法之一，它将各个 机器逐一排列，每一时刻在未排列的机器中定义台机器为瓶颈，当一 台新机器被排列时，所有先前已经建立的排列将被再次优化。其中，瓶 颈的确定和局部再优化过程基于重复解决某一个单机调度问题( 即原问 题的一个松弛) 而进行。显然，该方法的性能依赖于瓶颈的定义和各瓶 颈机器的排列顺序。 ( 3 ) 邻域搜索算法 模拟退火算法( s a ) ： s a 最早由磁f k p a t f i c k f l l j 等在1 9 8 3 用来求解组合优化问题，它是首先 引进跳出局部极小值陷阱机制的算法。算法的基本步骤是首先建立一个 初始解( 随机或者是启发式构造) 并且设置一个初始温度死然后在当 前解s 的邻域0 ) 中产生一个候选撬，如果雕) e 友黟，那么s 替代s ，否 则构造一个关于哪) w 函数，用它们作为接受的概率，这个函数一 般选用b o l t s m 锄分布函数e x p ( 一上型安上屿。 【基本模拟退火算法】： 步骤1 ：在解空间s 中随机产生一个解s ，并令i = o ，最优解s = s ，最优 武汉理1 一大学硕士学位论文 值为胎0 ，确定初始温度g 步骤2 ：若算法终止条件满足则结束搜索并输出最优解5 + ，否则继续以 下步骤； 步骤3 ：在当前解s 的邻域例中产生邻域解s 。； 步骤4 ：若，f s ) ，f s 0 ，则令s + = s ，m ) 娟0 ； 步骤5 ：若e 【o 1 】 禁忌搜索算法( t a b us e a r c h ， i s ) ： g l o v e 一1 3 1 1 1 4 】首先提出了禁忌搜索算法的基本思想：禁忌搜索算法一 方面通过领域搜索从先前的局部最优点出发继续搜索，另方面通过设 置禁忌袁( t a b ul i s t ) 来阻止搜索过程回到已经搜索过的解；另外， 通过设置藐视准则来奖励和赦免一些优良状态( 例如判断状态是否优于 “b e s ts o f a r 状态) 。 【基本禁忌搜索算法】： 步骤1 ：给定算法参数，随机产生初始解善，置禁忌表为空； 步骤2 ：判断算法终止条件是否满足? 若是，则结束算法并输出优化结 果；否则。继续以下步骤： 步骤3 ：利用当前解x 的邻域函数产生其所有( 或若干) 领域解，并从 中确定若干侯选解 步骤4 ：对侯选解判断藐视准则是否满足? 若成立，则用满足藐视准则 的最佳状态y 替代x 成为新的当前解，即x = y ，并用与y 对应的禁忌对 象替换最早进入禁忌表的禁忌对象，同时用y 替换“b e s ts of a r ”状态，然 后转步骤6 ：否则，继续以下步骤； 步骤5 ：判断侯选解对应的各对象的蔡忌属性，选择侯选解集中非禁忌 武汉理_ 【：大学硕士学位论文 对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最 早进入禁忌表的禁忌对象元素； 步骤6 ：转步骤2 。 禁忌搜索过程中产生的新解不是在当前解的邻域中随机产生的，而 或是优于“b e s ts of a r ”的解，或是非禁忌的最佳解，因此选取优良解的概 率远远大于其他解。d e l l a r n i c o 等。”于1 9 9 3 年提出了一种有效禁忌搜 索算法来求解j o b s h o p 调度问题，得到了f t i o 的最优解。 遗传算法( g a ) ： 遗传算法【1 6 】最早由美国密执安大学的h o l l a n d 教授提出，是模拟生 物在自然环境中的遗传和进化过程而形成的一种自适应全局随机优化 搜索算法。 【基本遗传算法】： 步骤1 ：确定算法参数，随机产生个个体作为初始种群x ( o ) ，置进化 代数t 0 ； 步骤2 ：计算或估价石( f ) 中各个个体的适应度。 步骤3 ：种群进化 3 1 选择从x ( f ) 中运用选择操作选择出2 对母体。 3 2 交叉对所选择的2 对母体，依某一确定的概率执行交叉， 形成个中间个体。 3 3 变异对n 个中间个体分别依某一确定的概率执行变异，形成 n 个个体组成新一代种群茗( f + 1 ) 。 步骤4 ：如以满足终止条件，则输出工( f + 1 ) 中具有最大适应度的个体作 为最优解，终止计算，否则置t 一t + 1 并转步3 。 j o b s h o p 调度问题是最有名的复杂组合优化难题之一，而遗传算法 有很强的并行性和很高的计算效率，因此利用遗传算法进行j o b s h o p 调 度问题的求解是很自然的想法，并成为j o b s h o p 调度问题的研究热点。 在过去的2 0 年里，国内外的学者们对这个问题进行了广泛而深入的研 究，提出了多种求解j o b s h o p 调度问题的遗传算法”“”1 ，同时，这也 是本文的研究的重点。 1 4 本文的主要内容和结构 9 武汉理l ：人学硕：b 学位论文 本文的主要研究内容涉及：j o b 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 调度问题的混合遗传算法，并通过仿真实 验证明了新算法的有效性。 本文共分五章，具体章节安排如下： 第一章介绍选题的意义、j o b 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 调度问题的混合遗传算法，基于已有的数学模 型对调度模型进行仿真研究( 这也是本文的核心工作) 。 第五章对本文进行了总结和展望。 1 0 武汉理工大学硕士学位论文 2 1 遗传算法概述 第二章遗传算法 生命科学与工程科学的相互交叉、相互渗透以及相互促进是近代科学技术 发展的一个显著特点，而遗传算法的蓬勃发展正体现了科学发展的这特征和 趋势。 遗传算法( g e n e t i c a l g o r i t h m s ) 是模拟达尔文( d a r w i n ) 的遗传选择和自然 淘汰( n a t u r a ls e l e c t i o n ) 的生物进化过程的计算模型，由美国m i c h i g a n 大学的 j o h nh h o l l a n d 教授于1 9 7 5 年首先提出的。jh o l l a n d 教授和他的研究小组围绕 遗传算法进行研究的宗旨有两个：一是抽取和解释自然系统的自适应过程，二 是设计具有自然系统机理的人工系统。毫无疑问，h o l l a n d 教授的研究无论对自 然系统还是对人工系统都是十分有意义的。 相比于传统优化算法，遗传算法有以下几个特点例： ( 1 ) 遗传算法以决策变量的编码作为算法对象，而传统优化算法直接利用决策 变量的实际值本身来进行优化计算。 ( 2 ) 遗传算法直接以目标函数值作为搜索信息，而传统优化算法还需要其它的 一些辅助信息。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息，而传统优化算法仅仅从解空间 的一个初始点开始搜索。 ( 4 ) 遗传算法使用概率搜索技术，而传统优化算法采用的是确定性的搜索技 术。 2 2 遗传算法的基本定理【1 6 】 2 2 1 模式定理 定义2 1 设z - ，。) 为基本遗传算法( 简称s g a ) 群体状态的空间， h e v 。慨y 是任一模式，p ( f ) 一k ( f l z ：o l ，h o b 工表示s g a 在r 代时 的群体，：，一r 1 为适应函数，则称 武汉理1 i 人学硕士学位论文 ，。而雨磊舻) 为模式h 的平均适应值，这里旧n e ( t 】表示集合日n e ( t ) 中元素的个数，即p ( r ) 中含有h 中元素的个数。称 7 0 ) = 罗，0 ) z 艮1 为p ( f ) 的平均适应值。 定理2 1 ( 模式定理，s c h e m at h e o r e m ) 设s g a 的交叉概率和变异概率分别 为p , t u p ，模式h 的定义长度为6 ) 、阶为口) ，第f + 1 代群体p o + 1 ) 含有 h 中元素个数的期望值记为e 0 日n p 0 + 1 】，则 f 陋n p 。+ ，柏p n 砖+ z 帮 i 一置掣一。国k 推论2 1 在s g a 中，定义长度较短、低阶且适虚值超过平均值的模式在群 体中数目的期望值按指数级递增。 2 2 2 内含并行性定理 在s g a 中，算法一次处理的模式数在2 7 到2 。之间，但由模式定理知，并 不是所有的模式都能以较大的概率被保存下来迸行处理。j h o l l a n d 在分析了有 效模式( 即那些按指数级递增的模式) 的数目后，得到了定理2 2 。 定理2 2 ( 内含并行性定理) 设e 是一个小正数，f ，t ( f l + l ，群体规模 一2 l ，2 ，则s g a 一次处理的那些存活概率乏1 一s 且定义长度sz 的模式数为 d 3 ) 。 定理2 2 只在群体规模n 为一定值时，对所处理的有效模式数进行了估计， b e r t o n i 和d o r i g o 在文献1 2 1 1 中对n 取一般值时证明了定理2 3 。 定理2 3 设f 为串长， 0 ，令，。一言f ，若群体规模一) 一2 廖，这里 上 声，0 是一个参数，则有 ( 1 ) s g a 一次处理的那些存活概率，1 - 且定义长度s2 ，的模式数目的期望 值至少与n l f 4 ；毛孺飘除，其中 武汉理工大学硕士学位论文 1 + 2 鼠 帅c 卢c j ，+ z 日( ；芦) 声，矿，s 芦s ； 扣：s ，i f p ，； 这里日皓) - 一l o g ：亭一( 1 一宇i ( 0 c 宇t 1 ) 称为熵函数； ( 2 ) n p 1 i t , j ，n 咖) 0 石云万大于某一常数； ( 3 ) 当卢苫1 时，存活概率z 1 一扫4 的模式数至少与三“川i 鬲歹同阶。 2 3 遗传算法的基本流程 图2 1 遗传算法的基本流程 武汉理i ：大学硕七学位论文 2 4 遗传算法的基本实现技术 2 4 1 编码方法 在遗传算法中把一个问题的可行解从其解空间转换到遗传算法所能处理的 搜索空间的转换方法称为编码。编码是遗传算法解决问题的先决条件，也是遗 传算法设计的关键步骤。编码方法除了决定了个体的排列形式之外，它还决定 了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，编码方法也 影响到交叉操作、变异操作等遗传操作的运算方法。不合适的编码会极大地影 响遗传算法的性能。为此，g o l d b c r g 提出了三条编码评估规范【2 0 】： 1 ) 完备性( c o m p l e t e n e s s ) ：问题空间中的所有点( 候选解) 都能作为g a 空间 中的点( 个体) 表现； 2 1 健全性( s o u n d n e s s ) ：g a 空间中的个体能对应问题空间中的所有候选解； 3 1 非冗余性( n o n - r e d u n d a n c y ) ：个体和候选解一一对应。 上述的3 个编码评估规范虽然带有普遍的意义，但是缺乏具体的指导思想， 特别是满足这些规范的编码设计不一定能有效地提高遗传算法的搜索效率。 d cj o n g 提出了较为客观明确的编码评估准则，他称之为编码原理。由于其可操 作性较强，常常又称之为编码规则1 2 2 】。 编码规则一( 有意义积木块编码规则) ：应使用能易于产生与所求问题 相关的且具有低阶、短定义长度模式的编码方案。 编码规则二( 最小字符集编码规则) ：应使用能使问题得到自然表示或 描述的具有最小编码字符集的编码方案。 由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方 法。总的来说，这些编码方法可以分为三类： 二进制编码方法 浮点数编码方法 符号编码方法 2 4 1 1 二进制编码方法 二进制编码方法是遗传算法中最常用的一种编码方法，它将原问题的解空间 映射到位串空间b l = o ，1 1 上，然后在位串空间上进行遗传操作。结果再通过解 码过程还原成其表现型以进行适应度的评估。二进制编码方法有下述一些优点： 1 4 武汉理工大学硕士学位论文 f 1 ) 简单易行 ( 2 ) 能表达的模式数最多 f 3 1 符合最小字符集编码原则 f 4 1 便于利用模式定理对算法进行理论分析 尽管二进制编码有如上优点，但它在求解连续数值优化问题时也存在以下一 些缺点： ( 1 ) 相邻整数的二进制编码可能具有较大的h a m m i n g 距离，这种缺陷将降低 遗传算子的搜索效率，二进制编码的这一缺点被称为h a m m i n g 悬崖； ( 2 ) - 进制编码时，所需解的精度确定后，串长也就确定了，当需要改变精度 时，很难在算法执行过程中进行调整，从而使算法缺乏微调的功能； ( 3 ) 当应用于高维、高精度数值问题时，产生的二进制位串很长，搜索空间非 常大，从而使算法的搜索效率很低。 2 4 1 2 浮点数编码方法 为了克服二进制编码的缺点，人们常常使用浮点数编码方法。这样，便可直 接对解进行遗传操作，从而便于引入与闯题领域相关的启发式信息以增加遗传 算法的搜索能力。浮点数编码方法最大的优点是适合于高精度计算，且便于推 广或融合经典连续优化算法，缺点是只能对连续变量问题使用。 2 4 1 3 符号编码方法 符号编码方法是指个体编码串中的基因值取自一个无数值含义、而只有代码 含义的符号集。这个符号集可以是一个字母表，如 凡b ，c ，d ，) ；也可以是一个 数字序号表，如 1 ，2 ，3 ，4 ，5 ，) ；还可以是一个代码表，如 a 1 ，a 2 , a 3 , a 4 ，4 5 ，) 等等。符号编码方法主要用来处理组合优化问题，其优点是便于在遗传算法中 利用所求解问题的专门知识，但缺点是设计遗传操作相对困难( 需要保证遗传 操作使得结果具有合法性，或者说，需要满足问题的各种约束要求) 。 2 4 2 适应度函数 适应度是生物学家在研究自然界中生物的遗传和进化现象时用以度量某个 物种对于其生存环境的适应程度的术语。对生存环境的适应程度较高的物种将 有更大的可能繁殖更多的后代。与此类似，遗传算法中也使用适应度这个术语 来度量群体中的个体作为全局最优解的可接受程度，它是遗传算法评价和选择 武汉理工人学硕士学位论文 个体的度量依据。适应度较高的个体遗传到下一代的概率就较大；面适应度较 低的个体遗传到下一代的概率就相对小一些。下面介绍在设计遗传算法时经常 用到的适应度函数及其调节方法。 2 4 2 1 适应度函数 一般情况下，可以采用问题的目标函数值作为个体的适应性度量。如在求解 极值问题婴8 吾，0 ) 时，s ( x ) 日1 9 9x 的适应函数。但是在遗传优化中，会出现两 种情况，一是求最小值的情况即适应度越小个体性能越好；另一种是求最大值 的情况即适应度越大个体性能越好。这时常常需要将适应函数做一个适当的变 换，即皆转化为求最大值的情况，并且由于要根据各个体的适应度计算各个体 的选择概率，所以应该使适应度非负。 对于最小值问题，其适应度按下式变换 k - 舻。瓣娩 式中，o 为一个适当地相对较大的数。 还有一种较常用的方法是将适应度函数取为目标函数的倒数。即 ，、1 ，忙j 。而五 对于最大值问题，为了保证适应度不出现负值，可采用下式变换 k 阱饥缆溉冀 式中，允。为一个适当地相对较小的数。 2 4 2 2 适应值的调节 在设计遗传算法时，群体的规模一般在几十至几百，与实际物种的规模相差 很远。因此，个体繁殖数量的调节在遗传操作中就显得比较重要。如果群体中 出现了超级个体，即该个体的适应度大大超过群体的平均适应值，则按照适应 值比例选择时，该个体很快就会在后代群体中占有愈来愈多的份额，此时群体 趋于同化，交叉算子无法产生新的后代，变异算子也几乎不起作用，迸化几乎 停止，从而导致算法收敛到某点，而该点可能不是全局最优点，只是一个局 部晟优点，这种现象称为遗传算法的“早熟”现象。在这种情况下，应该降低 武汉理j ：入学硕十学位论文 这个个体的适应度，以降低这些超级个体的竞争力，防止“早熟”现象的出现。 另一方而，在搜索过程的后期，虽然群体中存在足够的多样性，但群体中个体 的差异缩小，缺乏足够的区别性。在这种情况下，群体中实际上己不存在竞争， 从而搜索目标也难以得到改善，出现了停止现象。此时就应该选择对群体中的 个体做“扩大差异”的适应度变换。 目前常用的个体适应度尺度调节方法主要有四种：模拟退火变换、线性尺度 变换、乘幂尺度变换和盯截断变换。 ( 1 ) 模拟退火变换 模拟退火变换的公式为： 。 ，l 一南，丁- 0 9 9 t - ! 毛 矽 j l 式中，l 为第i 个个体的适应度，n 为种群规模，g 为遗传迭代次数( g = 1 ，2 ，) ， t 为温度，t 0 为初始温度。 ( 2 ) 线性尺度变换 线性尺度变换的公式为： j 一砖礼 式中，原适应度 ，尺度变换后的薪适应度 口和占系数 系数口和6 直接影响到这个尺度变换的大小，所以对其选取有一定