（计算机软件与理论专业论文）基于混合蚁群算法jobshop调度问题的研究与实现.pdf

哈尔滨理工大学工学硕士学位论文 基于混合蚁群算法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 调度问题，通常将一些解决某类问题的较好算法 组合起来。本文采用邻域搜索混合蚁群算法和自适应遗传蚁群混合算法来求 解j o b s h o p 调度问题。 针对蚁群算法的早熟收敛及收敛速度慢等问题，设计了一种基于邻域搜 索的混合蚁群算法。运用具有可变邻域搜索的变异算子对搜索结果进行优 化，该算子除了具有通常的变异作用外，还具备步长为2 和3 的局部搜索功 能。最后针对经典j o b s h o p 调度问题中的l a 类部分问题进行了仿真实 验，实验结果对比表明，该算法求解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 1 个经典问题进行 了仿真实验。结果证明了自适应遗传蚁群算法具有更好的全局收敛性能，即 克服了自适应遗传算法搜索到一定阶段时最优解搜索效率降低又避免了蚁群 算法初始信息素匮乏的不足之处。尤其是问题规模越大，算法优势越明显。 关键词j o b s h o p ：蚁群算法；遗传算法；邻域搜索 哈尔滨理工大学工学硕士学位论文 r e s e a r c ha n di m p l e m e n t a t i o nb a s e do nh y b r i da n t c o l o n ya l g o r i t h m sf o rj o b - - s h o ps c h e d u l i n g p r o b l e ms a b s t r a c t j o b s h o pp r o b l e m i st h ec o n c e n t r a t em o d e lo fm a n ya c t u a l j o b s h o p s c h e d u l ep r o b l e m s ，a n di ti sat y p i c a ln o n d e t e r m i n i s t i cp o l y n o m i a l t i m eh a r d p r o b l e m ，s oi ti sr e p o r t e dt h a ti tc a n tg e tt h eb e s to u t c o m et h r o u g hp o l y n o m i a l a n tc o l o n ya l g o r i t h m ( a c a ) ，w h i c hh a sb e e nw i d e l yn o t i c e dd u r i n gr e c e n ty e a r s a n du s e dt os o l o v ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sb ym o r ea n dm o r e p e o p l e ，i sak i n do fo p t i m i z a t i o na l g o r i t h m i no r d e rt os o l v et h ej o b s h o p p r o b l e mb e r e r ，s o m eg o o da l g o r i t h m sa r ec o m b i n e d i nt h i sp a p e r ，ah y b r i da n t c o l o n ya l g o r i t h mb a s e do nn e i g h b o r h o o ds e r a c ha n da na d a p t i v eg e n e t i c a 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 ( a g a a c a ) a r er e s p e c t i v e l yp r o p o s e df o r j s p t oo v e r c o m et h ed i s a d v a n t a g e so fp r e m a t u r i t ya n ds l o wc o n v e r g e n c ei na n t c o l o n ya l g o r i t h m ，ah y b r i da n tc o l o n ya l g o r i t h mb a s e do nn e i g h b o r h o o ds e a r c hi s d e s i g n e d av a r i a b l en e i g h b o r h o o ds e a r c hm u t a t i o no p e r a t o rw h i c hh a sn o to n l y t h eu s u a lv a r i a b i l i t y , b u ta l s ot h el o c a ls e a r c hf u n c t i o nw i t l ls t e p s2a n d3i s a p p l i e dt oo p t i m i z es e a r c hr e s u l t s t h es i m u l a t i o nr e s u l t so fs o m ec l a s s i c a lt y p e l ap r o b l e m si n d i c a t et h a tt h ea l g o r i t h mh a saf a s t e rs p e e df o ro p t i m u mv a l u e s e a r c h i n ga n dab e r e rg l o b a lo p t i m a ls e a r c h i n gc a p a b i l i t y , a n da tt h es a m et i m e ， t h ed i v e r s i f i c a t i o no fs o l u i o n si si n c r e a s e d ，a n dt h ep r o b a b i l i t yf a l l i n gi n t ot h e l o c a le x t r e m ev a l u e sc a l lb er e d u c e d b a s e do na n a l y i s i n ga d a p t i v eg 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 ， j o b - s h o pp r o b l e mi ss o l o v e db yc o m b i n i n gt h et w oo n e s f i r s t l y , u s i n ga d a p t i v e g e n e t i ca l g o r i t h mt og e n e r a t es o m ee x c e l l e n tc h r o m o s o m e ，c o n v e r t i n gt h e mi n t o i n i t i a lp h e r o m o n ed i s t r i b u t i o nf o ra n tc o l o n ya l g o r i t h m ，a n dt h e nu s i n ga n t i i c 0 1 0 n ya l g o r i t h mt os e a r c hf o rt h eb e s ta n s w e ro fj s p t h e nd e t e r m i n i n gt h e b e s t c o n l b i n a t i o nt i m eo fa d a p t i v eg e n e t i ca l g o r i t h ma n da n t c o l o n ya l g o r i t h mt o a v o i de a u r l vo r1 a t et e r m i n a t i o no ft h ea d a p t i v eg e n e t i ca l g o r i t h m f i n a l l y ，t h e r e s u i t si ns o l o v i n ge l e v e nc l a s s i c a ls c h e d u l i n gp r o b l e m si n d i c a t et h a ta g a - a c a h a sb e 讹rw h o l eo n s t r i n g e n c ya n du t i l i z e st h ea d v a n t a g e so f t h et w oa l g o r i t h m s a n do v e r c o m e st h e i rd i s a d v a n t a g e s ，a n di t i sd i s c o v e r e dt h a tt h eb i g g e rt h e p r o b l e mi sc o n c e r n e d ，t h eb e t t e rt h ea l g o r i t h mp e r f o r m s k 叼御o r d sj o b s h o p ，a n tc o l o n ya l g o r i t h m ，g e n e t i ca l g o r i t h m ，n e i g h b o r h 0 0 d s e a r c h i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于混合蚁群算法j o b s h o p 调度问题的研究与实现，是本人在导师指导下，在哈尔滨理工大学攻读硕士学 位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外 不包含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集 体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名： 耍确乡7 日期：办劫年弓月4 - 日 哈尔滨理工大学硕士学位论文使用授权书 基于混合蚁群算法j o b s h o p 调度问题的研究与实现系本人在哈尔滨理 工大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成 果归哈尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本 人完全了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并 向有关部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理 工大学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或 部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密酣。 ( 请在以上相应方框内打) 储虢明务吼僦年弓月仟日 导师签名：号吖胜想日期：2 矽 年多月仟日 哈尔滨理工大学工学硕士学位论文 1 1 课题研究背景 第1 章绪论 本课题来自国家自然科学基金。 车间作业调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ) ，简称j s s p ，是典型的 n p h a r d 问题，是c i m s 领域中研究的重要课题。同时也是在实际中应用最 广的运筹学分支之一，研究它对于在现有资源条件下提高工作效率和经济效益 有重要作用。理论上已经证明车间调度问题是一个n p h a r d 难题，要想在多项 式时间内找到最优解是不可能的。但是，在实际生产中即便一个较优解也能带 来极大的经济效益，所以人们探索了许多途径以寻求最佳近似解。目前大部分 研究集中在车间作业调度问题上，没有考虑资源分配，一般都直接将资源作为 约束处理。因此j s s p 的研究有其实际工程意义而且也有深远的理论意义。这 是由于：一方面，车间作业调度问题的研究不仅可以推动相关算法的研究， 如：模拟退火算法、遗传算法、神经网络、免役算法等，而且还能在此基础上 提出新的算法，这为其他领域类似问题的解决提供了条件和手段；另一方面， 车间作业调度问题的解决本身具有实际意义，一个好的车间作业调度方案不仅 可以降低生产成本，而且可以提高企业产品的准时交货能力，从而增强企业的 竞争力。 1 2 j o b s h o p 调度问题概述 1 2 1 j o b s h o p 调度问题的描述 车间作业( j o b s h o p ) 调度问题是具有特殊工件特性和加工环境的典型和重 要的调度问题，通常是特殊的开环调度问题控1 。它研究n 个工件在m 台机器上 的加工过程，0 f ，表示第f 个工件在第，台机器上的操作，相应的操作时间t 玎为 已知，事先给定各工件在各机器上加工次序( 称为技术约束条件) ，要求确定 与技术约束条件相容的各机器上所有工件的加工次序，使加工的性能指标达到 最优口1 。 在典型的j o b s h o p 调度问题中，除技术约束条件之外，通常还假定以下 哙尔滨理工大学忑学矮士学使论文 条件： 1 各工件经过箕准备时闻蓐即可开始船工。 2 每一时刻每台机器只能加工一个工件，且每个工件只能被一台机器 所加工。闽时加工过程为不间断，整个加工过程中机器数均有效。 3 。整个加工过程孛每个工释在弱一台规器上只能加工一次。 4 各工件必须按工艺路线以指定的次序在机器上加工。 5 。不考虑工件加工优先权。 6 操箨允许等待，郎前一个操作来完成，则后面的操作需要等待。 7 所有机器处理的加工类型均不同。 寒。除菲特殊说骥，工释麴燕工时阕事先绘定，置在整个热工过程串僳 撩不变。 9 ，除葛# 特殊说唆，工l 孛烟工时闻态包含加王设置时闻。 车闻调度基本豹束条 牛是进行调度理论研究酶主要约束条件，能否有效韵 解决j s s p 基本约束条件满足问题是调度理论研究的关键。 1 2 2 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 s s p 的数学模型，先给出如下的定义勰1 t 定义羔。l 设代表斑个工件的集会，则了可以表示兔乒 文点，磊 定义1 2 设材代表r r i 台视器的集合，瑟| j 膨可以表示为m = m 1 , m 2 ，旃) 定义l - 3 称r 为加工时间矩阵，其中t o 表示工件f 进行第，道工序的加工 时阕。产重。，n ，。严1 0 ，。，舻，v = m a x k i ，魏为工待毒匏工序数羁。 定义1 4 称c 为加工完毕时间矩阵，其中g 表示工件f 的第，个工序的加 王完毕时阀。 哈尔滨理工大学工学硕士学位论文 定义1 5 若一个调度满足问题的各种约束条件，则称为可行调度，否则称 为不可行调度。 定义1 6 对一个可行的调度，设c 为它的加工完毕时间阵，则称 f ( c ) = m a ) ( m a x c ，) 为此调度的目标函数，其中v - - - m a x k , ，岛为工件 的工 l i ；f s ni sj s v 序数目。 基于上述定义，我们给出j s s p 数学模型的定义。 定义1 7 设j 为工件集合，m 为机器集合，f 为目标函数，r 为加工时间 矩阵。c 为j n - r 完毕时间矩阵，如果对于一个给定的可行调度和它的所对应的 加工完毕时间阵c 。，则满足下述关系式： f ( c o ) = m i n f ( c ) 则称此调度为j s s p 的最优解，称求解此调度的过程为车间作业调度。这 就是我们给出的j s s p 模型的定义阳1 。 1 2 3 j o b s h o p 调度问题的析取图模型 j o b s h o p 调度问题是指由们台机器加工n 个有特定加工路线的作业， 调 度的任务是如何安排每台机器的加工顺序，使目标函数最优。 对于j s s p 有多种不同的描述形式，通常有a d a m s 等的线形规划模型和 r o y 等析取图模型n 1 ，本文采用析取图模型g = ( ，4 ，d 来描述j s s p 。析取图 g _ ( ma ，e ) 定义如下：n 是所有工序组成的节点集，增加两个虚节点0 和 + 1 ，0 表示“起点”( 所有作业的开始工序) ，+ 1 表示“终点”( 所有作 业的结束工序) ；a 是联接同一工件连续工序间的合取弧集( 用单向弧表 示) ，e 是联接在同一机器上进行加工的工序间的析取弧集( 用双向弧表 示) 。如图1 1 所示。 图卜1j o b - s h o p ( ，l = 3 ，m = 2 ) 的析取图 f i g l 一1t h ed i s j u n c t i v eo f j o b - s h o p ( ”= 3 ，m = 2 ) 嗡尔滨理工大学工学硕士学位论文 对于j o b - s h o p 调度问题其目标函数定义为总完工时间最小，即 c 二= r a i n ( 1 ) = m i n ( m a x ( c l ，c 2 ，。，g ) ) ( 1 1 ) 式( 1 1 ) 中c ，g = 1 , 2 ，栉) 为第价工件加工完毕所需时间。 1 3 车间作业调度问题的研究方法 在对车间调度问题进行研究的方法上，最初是集中在整数规划、仿真和简 单豹规则上，这些方法不是调度结果不理想就是难以解决复杂的问题。随着各 种新的相关学科与优化技术的建立与发展，在调度领域也出现了许多新的优化 方法，比如神经网络、模拟退火法、遗传算法、禁忌搜索法等，使褥调度问题 的研究方法向多元化方向发展。总结起来，现有调度问题的研究方法大体上可 以分为以下几种类别。 数学规划法有线性规翔( l i n e a rp r o g r a m m i n g ) 方法、非线性规划w o n - l i n e a rp r o g r a m m i n d 法、动态规划( d y n a m i c a lp r o g r a m m i n g ) 法、拉格朗日乘子 法等，在这些算法中，线性规划法作为一种精确调度方法嘲，是较成熟的方法 之一，但很多问题都不能以简单的线性关系精确表达，且变量多为整数，因此 他的使用受到很大限制。 2 。缝合优化方法包括分支定界法( b r a n c ha n db o u n d ) 、割平面法等。其中 较常用的是分支定界法，它的效率与定界的方法以及搜索空间的结构密切相 关，如果能合理地利用这些因素，可将其用手中小规模问题的求解。瞧于调度 问题的复杂性，对于n p h a r d 题，上述算法的计算时间随规模的增大丽呈指数 增长。s c h a l l c r ，j 嘲提出了改进的分支定界法，其不同点主要在于分析规则、 定赛瓤制和上界的产生三方面的差异。这类方法虽然从理论上能求得最优解， 但由于其计算复杂性和搜索效率低下，难以解决大规模的调度问题。 3 。规则调度是指在一般的调度算法基础上引入有效的调度规则，以寻找 近优解。p a n w 越ks 等总结了1 1 3 条规则，并将它们分为了三类：简革规则、 复合规则、启发式规则。这一方法可以大大缩短寻优过程，具有很强的使用价 值。在选用调度规则时，入们必须对实际情况徽具体分析和必要的仿真实验 后，才可以适当选用。虽然启发式规则常被用于实际当中n ，但它们一般不具 有全局优化的特点。 4 人工智能方法剩耀知识表达技术把人的知识包括进去，同时使用各种 搜索技术以求给调度问题一个令人满意的解1 。它把调度过程描述成个在满 足约束的解空间中搜索的过程。根据系统遗前的状态和给定的优化星标，对知 4 - 哈尔滨理工大学工学硕士学位论文 识库进行有效的启发式搜索和并行模糊推理机制，避开了繁琐的计算，并选择 最优的调度策略，为在线决策提供支持。在基于知识穗规则的调度系统孛，常 用的知识表示法有产人工智能方法如专家系统的研制，为调度问题指明了一条 通向应用的途径。但是具有知识难于表达和难于获取等缺点。 。基于d e d s 的解析模型方法对于辜闻类型的d e d s ，同样可瘸其解析 模型与方法来解决车间调度问题，如q n 、极大代数法、动态规划法等。但它 们都只适合于制造系统的性能分析。p e t r i 网除了具有并发、动态、直观等优点 外，还有能够准确快速地反映制造系统实时调度的离散性与隧机性等特点，所 以它与其它方法相结合在调度问题中得到了广泛的应用“引。目前，p e t r i 网应用 予制造系统调度存在以下阀题：( 1 ) 节点语义的单义性，使得所携带的系统信息 不够丰富；( 2 ) 重用性差；( 3 ) 当调度规则或方法复杂时，建模困难。 6 基于模糊数学理论的方法客观现象具有确定性与不确定性两个基本方 面，经典数学表达的是现象的确定性；不确定性一方面表现为随机性，另一方 面表现为模糊性。正是利用此特点，许多学者把它引入了调度领域n 轴。但与专 家系统稳似，这种方法同样存在开发周期长、需要丰富的调度经验和知识等缺 点。 7 。禁忌搜索法 禁忌搜索法( t - a b us e a r c h ，t s ) 是一种通过邻域搜索以获取最 优解的方法稚射，它从一个可行解s 出发，产生s 的邻域g ，如果f 为蠢标蚕 数，选取所有邻域中使f ( s ) 为最优的状态作为下一个状态，并把这移动的 反向移动存入一个称为禁总移动( t a b um o v e ) 的表中。列在表中的移动在以后若 干步内不允许再产生，这样可避免搜索退回去。每搜索一次，更新一次禁忌移 动表。e l j 子禁忌移动表的限制，有可能跳出局部极小。t m l 跚d e 提如了解决 f l o w - s 酗p 调度问题的禁惑搜索算法，l a g t m a 最早将禁忌搜索策略应用于j o b s h o p 调度中；为了更有效地搜索解空间，m a n u e l l 引入了插入移动和移动相 结合的机制提高了搜索效率n 钉。 8 模拟退火法 模拟退火法( s i m u l a t e da n n e x i n g ，s a ) 将组合优化问题与传 统力学问题的热平衡问题类比n “，它模仿了晶体结晶的冷却过程，在较高温 度毁下，系统状态力s ，能量郎嚣标函数) 为互，选择s 的个邻域，如果 e ( s ) e ( s ) ，则接受s 为下一个状态，否则以概率2 一“( s ) 堪( r ) ) 珞接收s 。经 过一定次数的搜索，认为系统在此温度下达到平衡，则降低r ，再进行搜索， 壹到满足约束条件为止。 9 遗传算法遗传算法( g e n c t i c 烈g o f i t h m ，g a ) 是一种模仿生物群体进化过 程的种优化算法珏8 1 割，给定一组初始解作为一个群体，逶过选择、交叉和交 哈尔滨理正大学x 学硕士学位论文 异等遗传操作来搜索最优解。由于g a 原理和操作简单，通用性强，不受限制 条件的约束，且具有隐含并行性和全蜀解空闻搜索能力，在机器学习、模式识 别、控制工程、优化等领域，尤其是在生产调度领域得到广泛的应用心仉2 1 1 。张 长水等用遗传算法对j o b s h o p 零件排序问题进行优化搜索，并在算法中引进 了一些新的思想，戬有利子降低稀群昭规模，提高计算速度，改善优化结果。 张宏芳，李小平等研究了病毒遗传算法啦! ，从横向和纵向上同时搜索解空间， 提出一种新的病毒浓度以增强病毒群体模式的多样性，病毒遗传算法克服了遗 传算法的旱熟现象了加快收敛速度。 1 0 神经网络算法 神经网络( n e u r a ln e t w o r k , n n ) 是一种模拟人脑神经系 统的结构和功能，运用大量的处理部件经广泛互连而组成的网络系统勰朝。主要 瘸于求解调度闻题的神经嬲络结构有：搜索网络( h o f i e l d 网终) 、纠锩网络( 多 层感知器) 、随机网络( b o l t z m a n 机) 、竞争网络和自组织网络。然而对于求解 j o b s h o p 调度问题来说，主要有两种：一种是h o f i e l d 神经网络模型，另一种 是b p 神经网络模型。f o oys 等首先提出耀h o f i e l di x x j 终求解j o b - s h o p 调度 问题，同时为避免网络陷入局部极小，又提出了种随机h o f i e l d 网络。 r e m u s w 是最早研究用b p 神经网络求解j o b s h o p 调度问题的入之一，他通过 比较线性衰减规则改进了几个b p 网终模型。c h r y s s o l o u r i s 。ge ta l 等使b p 神 经网络方法在每个作业车间中心都要求确定资源数量的制造系统设计中得到了 应用渤1 。 11 蚁群算法蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) 是近几年才提出的一 种新型的模拟进化算法他瓠，通过模拟自然界中真实的蚂蚁搜索食物源的行为来 求解很多组合优化闻题，并且取得了一定的效果。与其它算法相比，蚁群算法 的主要优点是：正反馈和分布式计算，正反馈过程使得该方法能较快找到解； 分布式计算使得该方法并行操作以找到较优解。 1 4 车间作业调度问题存在的问题及发展趋势 1 4 1 车间作业调度问题存在的问题 分析车间调度问题近4 0 年的应用和发展现状，有丰硕的成果，同时也暴 露出许多尚未解决的问题洳1 。 与最优化算法相比，近似启发式算法的明显优势在于：启发式算法相对 比较简单、计算效率高、算法灵活多变；近似启发式算法有明显不足之处， 嗡尔滨理工大学工学硕士学位论文 即有可能出现所产生的解比全局最优解差很多的情况，而且差的程度总是不够 明确。嚣此，合理的计算时间和所求出的解的最优性就成为衡量启发式算法性 能的标准。邻域搜索以一定的概率接受劣解，从而逃离局部最优，但其主要缺 点是需要多步实现，如何选择从局部到全局最优的邻域结构，使其具有强化性 和多样姓的搜索机制这一点缀重要。遗传算法的停止条件设置为一个大数时， 会存在达到最优而算法不能停止的问题，关键是如何协调两者关系。蚁群算法 初期由予信息素匮乏丽导致求解速度缓慢，如何改善初始信息素的分布以提高 求解速率值得我们迸一步研究。对愆技术和神经溺络，如何通过内部的并行 分布处理能力快速找到搜索空间而减小计算量的大规模问题有待进一步研究。 可从以下凡个方程进行拓展研究： 1 j o b s h o p 问题的般框架、模型及研究方法对解决生产调度和其他复杂 的组合优化问题是有借鉴的，应展开对m h 和m 都是通过在 其所经过的路径上留下一定信息的方法进行间接的信息传递。 而“人工蚁群算法 同真实蚁群的活动不同在于以下几点： 1 人工蚁群具有记忆功能，它能够记忆澄经走过的节点。 2 人工蚁群在选择下条路经的时候并不是盲目的，而是按定的算法规 律有意识的寻找最短路径( 如在t s p 中，可以预先指导下一个目标的距离) 。 3 ，人工蚁群处在一个离散时间的环境中。 为了进一步说明蚂蚁群体的路径搜索原理和机制，下面我们引用 m 。d o r r i g o 、v m a n i e z o o 和a c o l o r n i 所举倒子来具体说赣蚁群系统的原理， 如图2 - 1 所示： 彳阀彳t 彳 d - - 1 v 5 t 形：八 h 二。5 慕乡c 5 躺 ：蕊彩。躺 il t 3 0 a n t s 降3 0 a n t s o i 。 i i a a 爻 如表明距离的初始亿图协在仁o 时刻，路径b c 移帮b 固上c ) 在l 时刻，在较短酌逐主 没有外激素，蚂蚁以相同的概率有较多的外激素，燮多的蚂 选择c 点和h 点 蚁将会选择较短的路径 圈2 - 1 蚁群寻找最筑路径酶过程 f i g 2 - 1s e a r c h i n go p t i m i z a t i o np a t hp r o c e s so f a n t s 假设蚂蚁在食物源a 和巢穴嚣之间运动，每单位时闻内爬行单位距离， 途中d 为距离，且每单位时间内备有3 0 只蚂蚁从巢穴和食物源出发，又两条 路径( a b c d e 和a b h d e ) ，如图2 1a ) 所示。 如图2 1b ) ，在t = 0 时刻，鸯3 0 只蚂蚁放a 运动到b 。由于此时路径上 无外激素( 蚂蚁留下的信息素) ，蚂蚁就以相同的概率走b h 和b c 两条路中的 一条，于是各有1 5 只蚂蚁分别选择路径b c 和b h 。在真实蚁群中，外激素的 数量会随时间的流逝而蒸发掉一部分，为说明方便，此处假设：( 1 ) 所有蚂蚁运 动的速度相等；( 2 ) 外激素蒸发量与时间成正比例，即路径上外激素的剩余量与 路径的长度成反比；( 3 ) 蚂蚁选路豹概率与所选路上外激素的数量成正比。因为 哈尔滨理工大学工学硕士学位论文 路径b h d 的长度是路径b c d 的2 倍，当b 点的蚂蚁到达d 点后，路径b c d 上的外激素是b h d 上的2 倍。如图2 2c ) ，在时刻t = l 另有3 0 只蚂蚁从a 到 达b 。因为路径b c 上的外激素量是b h 上的2 倍，根据蚂蚁选路的特点，将 会有2 0 只蚂蚁选择b c ，而只有l o 只蚂蚁选择b h 。以此类推，当t = 2 ，3 ，4 时，将会有更多的蚂蚁选择路径b c d 。经过较长时间运动后，蚁群最终会沿 着最优路径a b c d e 运动。 蚁群算法在优化过程中有两个重要的规则： 1 蚂蚁在众多的路径中转移路线的选择规则，蚂蚁总是倾向于选择含有较 多信息素的路径。 这里信息素( p h e r o m o n e ) 类似于一种分布式的长期记忆m ，这种记忆不是局 部地存在于单个的人工蚁，而是全局地分布在整个问题空间，这就导致了一种 间接联络方式。 2 全局化信息素更新规则，在路径上的信息素，有一部分会被蒸发散失， 这样没有被选择过的路径信息素越来越少，变得越来越不受欢迎。每只蚂蚁按 路径的长短( 或找到食物的质量) 成比例地在属于其经过的路径上留下一定数 量的信息素。 信息素更新的实质就是人工蚂蚁根据真实蚂蚁在访问过的边上留下的信息 素和蒸发的信息素来模拟真实信息素数量的变化，它使得越好的解答得到越多 的增强。这就形成了一种自催化强化学 - - j ( a u t o c a t a l y t i cr e i n f o r c e m e n tl e a r n i n g ) 机制。 2 1 2 基本蚁群算法 2 1 2 1 基本蚁群算法描述本节以t s p 蚁群算法求解为例，说明其思想和实 现d 3 1 。t s p 是组合优化领域中的一个著名的经典难题，迄今尚未彻底解决，现 已被归入n p 完备的问题类。其一般提法为：给定n 个城市，有个旅行商从 某一个城市出发，访问各个城市一次且仅有一次后再回到原出发城市，问应怎 样选择行走路线，才能使总行程最短( 各城市间距离4 ，为己知) 。 为了模拟蚂蚁的行为，引入以下记号： 扩一蚁群中蚂蚁的个数； b j ( r ) 一f 时刻位于城市f 的蚂蚁的个数，m = b ，( f ) ； 百 7 7 。，一路径( i ，歹) 的能见度，反映出城市f 到城市- 的启发程度，这个量在蚂 哈尔滨理工大学工学硕士学位论文 蚁系统的运行中不改变，即1 似 f ，( r ) 一f 时刻路径( f ，- ，) 上的信息量； 磷( r ) 一f 时刻蚂蚁k 由城市f 转移到城市f 的状态转移概率。 各参数的含义如下： 口为残留信息的相对重要程度( 口0 ) ； 为期望值的重要程度( 0 ) ； p 为残留信息的挥发部分，( 0 p 0 ) ，可以将( 1 一p ) 理解为残留信息的 保留部分； q 为体现蚂蚁所留信息素轨迹数量的一个常数。 初始时刻，将m 只蚂蚁放入玎个城市中，各条路径上的信息素量相等，设 f i ，( o ) = c ，其中c 为常数，蚂蚁k ( k = - 1 , 2 ，哟在运动过程中根据各条路径上 的信息素量决定转移方向，这里用数组t a b u k ( k = - i ，2 ，m ) 来记录蚂蚁k 当前所 走过的城市，集合随着t a b u 七进化作动态调整。在搜索的过程中，蚂蚁根据各 条路径上信息量及路径的启发信息来计算状态转移概率。在t 时刻蚂蚁七由城 市i 转移到城市，的状态转移概率硝( f ) 为： 相： 絮t ) r l o ( t ) 前印啪溉 。，咖) ： ( f ) 磋( f ) 刚一“( 2 1 ) 。 卜a l l a w e d k 1 0 ，否则 式( 2 - i ) 中，a l l o w e d k 表示蚂蚁k 下一步允许选择的城市的集合，口为信息 启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息 素在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁以前 经过的路线，蚂蚁之间的协作性越强；为期望启发式因子，表示能见度的相 对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中受到重视程 度，其值越大，则该状态转移概率越接近于贪心规则，也即蚂蚁选择离它近的 城市的可能性就越大。 为了避免残留信息素过多引起残留的信息量淹没启发式信息，在每一只蚂 蚁走完一步或者完成对所有, 个城市的遍历之后，要对残留信息进行更新处 理。因此，在每一只蚂蚁完成对n 个城市的访问后，新的信息量由下式确定： l - g o + ，z ) = ( 1 一p ) f 可o ) + f ；( f ) ( 2 2 ) 式( 2 2 ) 中，p 表示信息素残留因子，则( 1 一p ) 表示信息素挥发系数； f ：( f ) 表示第k 只蚂蚁在本次循环中留在路径( f ，_ ，) 上的信息素量。 哈尔滨理工大学工学硕士学位论文 根据信息素更新策略的不同，d o r i g om 提出了三种不同的基本蚁群算法模 型，分别为蚁周模型( a n t c y c l e ) 、蚁密模型( a n t d e s i t y ) 及蚁量模型( a n t - q u a n t i t y ) - - - - 种方式。其差别在于f ；，( f ) 的求法不同。 在a n t c y c l e 模型中 r 1 蜘：海若第职蚂蚁在本次循种经过路径( f ) ( 2 - 3 ) i - o ，否则 式( 2 3 ) 中，q 表示信息素强度，它在一定程度上影响算法的收敛速度； 丘表示第k 只蚂蚁在本次循环中所走的路径长度。 在a n t q u a n t i t y 模型中 瞄 ：睁若第职蚂蚁在f 嗽怪过路御 ( 2 _ 4 ) l o ，否则 式( 2 4 ) 中，d g 表示路径( f _ ) 之间的距离。 在a n t d e s i t y 模型中 叫w = 1 0 f o ，翥棚赃时刻鲋船( f ( 2 _ 5 ) a n t - c y c l e 模型中的更新方法很好的保证了残留信息素量不至于会无限积 累，如果一条路径没有被选中，那么该路径上残留的信息素会随着时间的推移 而逐渐减弱，这样能够使算法“忘记”不好的路径，即使一条路径经常被访问 也不至于会因为f o ) 的积累而产生f 。( f ) r 目0 ) ，使期望值的作用无法体现。 因此通常采用a n t c y c l e 作为蚁群算法的基本模型。 2 1 2 2 蚁群算法的基本步骤以t s p 为例，基本蚁群算法的具体实现步骤如 下： 1 初始化。生成一个仅包含初始条件的搜索图；令时间t = 0 和循环次 。= o ，设置最大循环次数。，将m 只蚂蚁放到，z 个城市中；另有向图上每 条边( f ，) 的初始化信息量f 豇( 0 ) = c ，其中c 表示常数，且初始时刻 勺( o ) = 0 ； 2 生成m 个初始值为空的t a b u 数组； 3 如果循环次数达到最大。并且不是所有蚂蚁选择同一条路径，则算 法停止，打印出最短路径。否则，转第4 步； 晗尔滨理工大学工学硕士学位论文 4 把每只蚂蚁的初始城市号放入到t a b u 数组中； 5 ，对于每只蚂蚁，根据概率露来选择下一步要访闷的城市，将第k 只蚂 蚁放到城市j ，并将，插入到t a b u 数组中，同时将，在a l l o w e & 中删除：计算 第k 只蚂蚁的总路径长度厶，更新找到的最短路径和每条边上的信息素浓度， 对每条边计算f ；串磅。渍空所有t a b u 数组； 6 转第3 步。 2 。圭- 3 蚁群算法总结 2 1 3 1 基本蚁群算法的优点蚁群算法的本质是一种并行算法，其优点如 下： 1 较强的鲁棒性，对该算法模型稍加修改，便可以应用于其它问题，蚂蚁 算法对初始路线要求不高，却蚂蚁算法的求解结果依赖于初始路线的选择，丽 且在搜索过程中不需要进行人工的调整，其次，蚂蚁算法的参数数目少，设置 简单，易于将蚂蚁算法应用到其它组合优化问题的求解任们。 2 。分布式计算，该算法是一种基于稀群豹拟生态系统算法，具有本质并行 性，易予并行实现。 3 。爨于与其它方法结合，该算法很容易与多种扇发式算法结合，以改善算 法的性能。 4 蚁群算法是一种本质上并行的算法，每只蚂蚁搜索的过程彼此独立，仅 透过傣息激素进行通信。它在闻题空闻觞多点同时开始进行独立的鳃搜索，不 仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。 2 1 - 3 。2 基本蚁群算法的缺点虽然蚁群算法有许多优点，但也存在一些问 题： 1 需要较长的计算时间，容易出现停滞现象。蚁群中各个体的运动是随机 的，虽然透过信息激素交换能够南着最优路径进纯，惶是当群体勰模较大时， 很难在较短时间肉从大量杂乱无章的路径中找到一条较好的路径。 2 所有通过路段的搜索路径对应的候选解均会对该路段带来信息素的增 量。蔼实际上，候选解并非都是最好解，这样计算信怠素的增量会导致错误的 弓l 导信息，从i 耐造成大量的无效搜索，使系统出现停滞现象。 3 采用了信息素均匀分配策略，即对鑫搜索路径中的所有路段采耀同样的 信息素增量，与路段的重要性无关，没有考虑当连续空间优化问题转换到有向 图搜索问题时，信息素分配给可行解带来的尺度变化对于连续解空间搜索效率 哈尔滨理工火学工学硕士学位论文 的影响。 众多研究已经证明蚁群算法具有很强的发现较好解的能力，这是因为该算 法不仅利用了正反馈原理，在一定程度上可加快进化过程，而且是一种本质并 行的算法，不同个体之间不断进行信息交流和传递，从而能够相互协作，有利 于发现较好解，蚁群算法可以解释隽一耪特殊豹强化学习算法。蚁群算法与 q 学习算法之间的联系。其中，信息素相当于学习中q 值，表示学习所得到 的经验。由某种扇发式算法确定，如何将这两者结合起来，是提高蚁群算法效 率的关键。虽然蚁群算法有许多优点，僵是，这种算法也存在一些缺陷，如： 与其它方法相比，该算法般需要较长的搜索时间，蚁群算法的复杂度可以反 映这一点；丽且该方法容易出现停滞现象。霹搜索进行到一定程度屠，所有个 体所发现的解完全一致，不能对解空间进步进行搜索，不利子发现更好的 解。 2 2 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是h o l l a n d 受生物进能论豹启发丽提出 的。遗传算法的提出一定程度上解决了传统的基于符号的处理机制的人工智能 方法在知识表示信息处理和解决组合爆炸等方面所遇到的困难，其自组织、自 适应、自学习和群体进化能力使其适合于大规模复杂优化问题。遗传算法是基 于“适者生存”的一种高度并行、随机和囱适应优化算法，它将问题的求解表 示成“染色体”的适者生存过程，透过“染色体”群的一代代不断进化，包括 复制、交叉和变异等操作，最终收敛到“最适应环境 的个体，从而求得阀题 的最优解或次优解嘲。 2 2 1 遗传算法基本思想 g a 的想法源于d a r w i n 的进纯论和m e n d e l 的遗传学说。d a r w i n 的进化论 认为每物种在不断的发展过程中都是越来越适应环境。物种的每个个体的基 本特征被后代所继承，瞧后代又不完全嗣于父代，这些薪的变化，若适应环 境，则被保留下来。在某一环境中也