（计算机应用技术专业论文）改进的粒子群算法在车间调度中的应用研究.pdf

摘要 摘要 生产调度闻题属于组合优化问题。将优化方法的理论研究引入到车间生产调度领域 中，改进算法性能、拓宽算法应用领域、完善算法体系，是一个同时具有理论意义和应 用价值的课题，具有重要的意义。 粒子群算法一直是智能体算法领域中的研究热点。本文在标准的粒子群算法的基础 上，提出了一种改进的粒子群算法。新算法主要在两个方面对标准的粒子群算法做出了 改进：引入均匀设计的思想，保证种群粒子的分布均匀，使粒子在解空间中均匀的分布， 然后在进化过程中对每一代的种群运行清除算法来保持粒子的多样性，基于c l e a r i n g 机制的小生境进化能有效的探索解空间的各个区域，避免了陷入局部最优。这些改进措 施对避免算法出现早熟、提高算法的收敛速度和全局搜索能力有重要意义。应用标准测 试集中的测试用例和实际调度中的问题对改进后的算法进行了测试，仿真程序表明，该 算法能以较快速度完成给定范围的搜索和全局优化任务。 同时，针对制造企业的实际情况，本文设计了一种新的适用于实际车间调度问题的 种群初始化方法一均匀初始化粒子种群，相对于标准粒子群算法随机划分初始种群的缺 点，本文提出的划分方法使种群具有了更高的多样性。 针对某工厂的实际问题，运用上述技术，本文设计并实现了一个车间调度知识库系 统平台，并将改进后的算法嵌入至系统平台中，运用改进后的算法，针对实际问题进行 求解，得到的结果是可行的和有效的。 关键词：粒子群算法；小生境；均匀设计；车间调度 大连交通人学f 。学硕+ 学f 节论艾 a b s t r a c t s c h e d u l i n gt h e o r yb e l o n g s t oc o m b i n a t i o no p t i m i z a t i o n p r o b l e m i n t r o d u c i n g t h e o p t i m i z a t i o nt h e o r yt ot h ef i e l do fj o bs c h e d u l i n gi nw o r k s h o pc a ni m p r o v et h ep e r f o r m a n c e o fa l g o r i t h m ，m a k et h ea l g o r i t h ma p p l yt ob r o a d e rf i e l d sa n dc o m p l e t et h ew h o l es y s t e mo f t h ea l g o r i t h m ，w h i c hi sas u b j e c ti n c l u d i n gb o t ht h e o r e t i c a lm e a n i n ga n dp r a c t i c a lv a l u e s t h ep a r a l l e lg e n e t i ca l g o r i t h mh a sa l w a y sb e e nt h eh o ts p o to ft h er e s e a r c ho ng e n e t i c a l g o r i t h m t h i sa r t i c l ep r o p o s e sa ni m p r o v e dp a r a l l e lg e n e t i ca l g o r i t h mb a s e du p o nt h e t r a d i t i o n a lc o a r s eg r a i ng e n e t i ca l g o r i t h m t h ep r o p o s e da l g o r i t h mi m p r o v e dt h et r a d i t i o n a l o n em a i n l yi nt w oa s p e c t s ：o no n eh a n d ，i te m p l o y sam e c h a n i s mw h i c hc a nd y n a m i c a l l y a d j u s te a c hi s l a n d sm i g r a t i o nr a t ea c c o r d i n gt oi t sa v e r a g ef i t n e s s t h e r e f o r e ，i fo n ei s l a n d s a v e r a g ef i t n e s si sh i g h ，i t sd i v e r s i f yw i l lb ei n c r e a s e db yi n c r e a s i n go t h e ri s l a n d s m i g r a t i o n r a t et ot h i si s l a n di no r d e rt oa v o i dp r e m a t u r i t y ；t h ei m p r o v e da l g o r i t h ma l s oc a l c u l a t e st h e s u r v i v i n gp e r i o d f o re a c hc h r o m o s o m ei n v o l v e di n m i g r a t i o n ，n o to n l y e n a b l et h e c h r o m o s o m ew i t hh i i g hf i t n e s st os u r v i v el o n g e rb u ta l s oa v o i dt h ee x p l o s i o no ft h ep o p u l a t i o n o fs o m ei s l a n d t h e s ei m p r o v e dm e a s u r e sa r eo fg r e a ts i g n i f i c a n c eo na v o i d i n gp r e m a t u r i t y o ft h ea l g o r i t h m ，a sw e l la si n c r e a s i n gg l o b a ls e a r c h i n ga b i l i t yo ft h ea l g o r i t h m t h ei m p r o v e d a l g o r i t h mi st e s t e dt h r o u g hu s i n ge x a m p l e si nt h es t a n d a r dt e s ts e ta n dt h ea c t u a lp r o b l e mi n s c h e d u l i n g t h es i m u l a t i o nr e s u l t so ft h et e s ts h o wt h a tt h i sa l g o r i t h mc a nc o m p l e t et h et a s k o ft h ef a s ts e a r c hi nt h eg i v e nr a n g ea n dg l o b a lo p t i m i z a t i o n i nt h em e a n t i m e ，a c c o r d i n gt ot h ep r a c t i c a ls i t u a t i o no ft h em a n u f a c t u r i n gb u s i n e s s ，t h i s a r t i c l ed e s i g n san e wm e t h o dt oi n i t i a l i z et h ep o p u l a t i o nw h i c hc a na p p l yt op r a c t i c a lj o bs h o p p r o b l e m i fc o m p a r e dw i t ht h ec o n v e n t i o n a lp o p u l a t i o ni n i t i a l i z i n ga l g o r i t h mw h i c ho n l y r a n d o m l yd i v i d e st h ei n i t i a lp o p u l a t i o nt om a n ys m a l l e rg r o u p s ，t h en e wa l g o r i t h mi sm u c h m o r ee f f e c t i v ei nt h ea s p e c to fi n c r e a s i n gt h ed i v e r s i t yo ft h ep o p u l a t i o n t h i sa r t i c l ed e s i g n e da n di m p l e m e n t e da ni n t e l l i g e n ts c h e d u l i n gk n o w l e d g eb a s es y s t e m p l a t f o r mf o rw o r k s h o p ，w h i c hi st a r g e t i n ga ts o m ef a c t o r y sp r a c t i c a lp r o b l e m f u r t h e r m o r e ， t h ei m p r o v e da l g o r i t h mh a sb e e ne m b e d d e di n t ot h ek n o w l e d g eb a s es y s t e m i fw eu s et h i s n e wm e t h o dt os o l v et h ep r a c t i c a lp r o b l e m ，t h er e s u l ts h o w st h es o l u t i o ni sb o t hf e a s i b l ea n d e f f e c t i v e 。 k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o n ；n i c h e ；u n i f o r md e s i g n ；j o b s h o ps c h e d u l i n g 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太整塞通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名：尹是良 日期：夕彳年住月弓日 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解太连交通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太整塞通太堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太羹塞通太堂。学校有权保留并向 国家有关部门或机构送交论文的一复印件及其电子文档，允许论文被查 阅和借阅。 本人授权太董塞通太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：尹违建 日期彳年，y 月日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电子信箱： 导师签名= 生l 叩 日期：年，y 月；日 电话： 邮编： 绪论 绪论 一、本课题研究学术背景和意义 科学技术和生产力的不断发展，使得生产领域对资源的依赖日趋严重，资源的紧缺 已成为阻碍生产发展和进步的一大难题。面对紧缺的资源，如何有效的优化资源配置， 成为当前社会关注的一个焦点。 调度作为生产领域中解决资源优化配置的一个有效途径，它的研究具有重大的意 义，研究调度问题即在众多的调度方案中寻找到最优的方案。从本质上讲，调度问题非 常复杂，是一个用传统方法难以求解的问题( n p 问题) 。早在几十年前，学者们就开 始对调度优化问题进行了探索和研究。经过几十年的对调度优化理论的不断研究，研究 人员在研究调度问题的理论基础上提出了许多求解方法，并利用这些求解方法产生了大 量的研究成果和学术著作。 车间调度问题作为调度问题的典型代表，它既是一个调度问题又是一个最困难的组 合优化问题。车问调度作为企业生产计划与理论控制的重要组成部分，在工业生产领域 中一直作为一个热点受到人们的关注，它是提升企业竞争力的重要途径。尤其在制造业、 计算机行业等领域，通过有效的调度方法与优化技术可以更好地解决车间中工件在机器 上的调度和资源分配，通过对工件作业加工顺序进行优化配置，使某项性能指标( 如机 器总的加工时间、延迟时间及加工成本等) 达到最优；同时还可以实现对生产过程中的 物流和信息流的综合管理，使前后工序紧密衔接，保持物流的一贯性；还可以提高设备 的生产效率，减少工序的等待时间，降低物料的消耗，减少库存，缩短交货期，降低成 本，提高产品竞争力。 随着时间的推移，许多新的优化算法不断提出，为作业车间调度问题的求解提供了 新的手段，粒子群算法作为近年来提出的一种新的算法被广泛的应用在调度问题求解 中，本文将对粒子群算法进行研究并改进，最后把改进后的算法应用到作业车间调度中， 寻找最优的求解策略，同时深入探索其理论基础并将丰富的理论成果应用于实际调度问 题中，本文具有很大的实践价值和经济效益。 二、课题研究的主要内容及工作 本文在总结了粒子群算法在车间调度中的应用情况之后，又着重研究分析了几种常 用的小生境技术，如基于预选择机制的小生境技术、基于普通适应值共享机制的小生境 技术以及自适应小生境技术，找出了当前基于小生境技术的粒子群算法的应用上的缺 陷，并提出了一种改进的小生境粒子群算法，将均匀设计思想、小生境进化策略等引入 人造交通大学t 学硕卜学何论文 到该算法中，同时设计了一个经典车间调度问题的仿真应用平台，对理论数据进行了验 证，结果表明该算法在作业车间调度中能有效地提高调度效率，优化资源配置，对解决 中小规模的作业车间调度问题非常有效。最后本文将经过仿真试验验证过性能的改进的 小生境粒子群算法应用到实际研究项目“车间调度系统 中，最后的结果表明该算法能 很好的应用到实际生产调度问题中，改进后的算法能有效的提高作业调度的效率，优化 资源配置，为企业提高竞争力。 本文共五章。首先对车间调度问题的相关理论知识进行了回顾。然后对粒子群算法 ( p s o ) 相关的基本理论进行了基本的介绍。接着介绍了本课题对粒子群算法的改进。 然后讲的是改进的粒子群算法的实际应用。最后一章给出了论文的总结。下面简要介绍 一下各个章节的内容。 第一章是对车间调度问题的相关理论知识的回顾，介绍了调度问题的发展历史和研 究的现状。针对现实生活中的一些实际问题对调度进行了分类。 第二章是对粒子群算法基础知识的介绍。p s o 作为一种仿生技术，与进化算法和群 智能有紧密的联系。本章首先介绍了粒子群算法的来源，它源于对鸟群捕食行为的研究， 接着介绍了算法的基本概念和流程，然后介绍了粒子群算法在处理一些实际问题时常用 的改进方法，最后介绍了粒子群算法在生产领域中的应用。 第三章主要介绍本文的创新思想，针对标准粒子群算法的一些缺陷做出改进。在标 准粒子群算法的基础上引入均匀设计的思想来初始化粒子种群，使粒子能有效的探索空 间的各个区域，接着对在遗传算法中取得很好应用的小生境思想进行改进，并将其应用 到标准粒子群算法中，改进后的算法能有效的避免早熟收敛，有利于算法跳出局部最优 值。最后在标准调度问题中，对算法的性能进行了对比，验证了改进粒子群算法的优越 性。 第四章是改进的粒子群算法的实际应用，将改进的粒子群算法应用到本课题的资金 来源的实际项目中去，通过在实际车间调度系统中的应用，证明了改进算法的切实可行 性和优越性。 第五章对全文进行了总结，并给出了一些关于未来研究的展望。 2 第一章卞问调度问题研究 第一章车间调度问题研究 调度问题通常是指在一定时f b j 内，对一些共享资源进行分配和对一些生产任务进行 排序，使其满足某项性能指标。车间调度问题作为调度问题的一个子集，是企业生产计 划与控制理论的重要组成部分，是提升企业竞争力的一个重要因素。 由于企业车间的生产计划与控制问题在所有调度问题中最具典型性，所以对车间调 度问题的研究一直在调度理论中占据主导地位。 1 1 车间调度问题描述 通常认为，j o h n s o n 于1 9 5 4 年对两台机器下作业排序问题的求解是经典调度理论产 生的重要理论i 。他通过对两台机器有序加工的调度研究，提出了针对特殊的和规模较小 问题的以工件加工完成时间极小为目标函数的解析优化方法，尽管这些方法仅适用于单 机和简单的流水车间( f l o w - s h o p ) 问题，且它的研究范围较窄i 对于复杂的n p 完全问题 并不适用，但他开启了对调度问题的研究，这些早期的工作为经典调度理论后来的发展 奠定了基础。 典型车间调度问题可以描述为：给定一个工件的集合和一个机器的集合。每个工件 包括多道工序，每个工序需要在特定的机器上不间断的加工事先指定的时间。每台机器 可以加工工件的若干工序，在不同的机器上这些工序可以不同，但同一时间最多可以加 工一道工序。另外，工件和机器还应该满足如下约束： ( 1 ) 一个工件不能两次访问同一机器； ( 2 ) 不同工件的工序之间没有先后约束； ( 3 ) 工序一旦进行不能中断； ( 4 ) 每台机器一次只能加工一个工件； 车间调度问题的目标就是寻找最短时间的调度，使完成所有工件的加工时间达到最 短。车间调度问题也可以表述为在等式或不等式的约束下，求目标函数的优化。用数学 公式可以描述如下： r1 m i n m a x m a xc 址 ( 1 1 ) k k ml l s i , a j s t c 政一气+ m ( 1 一a i 址) c 衲，i = 1 ，2 ，n ，h ，k = 1 ，2 ，m c 体一c + m ( 1 - x 班) p i k ，i ，j t 1 ，2 ，n ，kt 1 2 ，m c i k o ，i1 1 ，2 ，n ，kl 1 ，2 ，m f ，1 ，、 x i i l 【= o o r l ，i ，j - - - 1 , 2 ，n ，k = 1 , 2 ，m “7 3 人连交通人学t 学硕 ：学何论文 其中，式( 1 1 ) 表示问题的目标函数，式( 1 2 ) 表示工艺约束条件决定的各工件的各操 作的先后加工顺序以及加工各个工件的各机器的先后顺序。式中，符号c 呔和p i l 【分别为 i 工件在机器k 上的完成时间和加工时间；m 是一个足够大的正数，a i l l l 【和x i i k 分别为指 示系数和指示变量，其意义为： 阻若机器h 先于机器k 加工工件i a i h k 1 d 非上述情况 阻若工件i 先于工件j 在机器k 上加工 卜“7 独1 q 非上述情况 1 2 车间调度问题的分类 由于研究所侧重的方面不同，车间调度问题有很多不同的分类方法，本文将采用 g r a v e ss t e p h e nc 1 2 j 于1 9 8 1 年根据问题复杂性的分类方法把车间调度问题分为以下四种 类型： ( 1 ) 单机调度问题 在单机调度问题中，所有的操作任务都在一台机器上完成，车间内只有一台机器， 所有的工件都在一台机器上完成加工，通常根据工件的加工时间长短或者按照工件交货 期的长短，对各项作业进行排序。 ( 2 ) 多台并行机调度问题 在多台并行机调度问题中，所有的操作任务由车间里一组功能相同的机器完成，n 个待加工的工件有一致的加工操作和加工顺序，可以在任意一台机器上进行加工。通常 按照j o h n s o n 规则来安排作业： 假设有n 个工件，在第一台机器和第二台机器上的加工时间分别t i l 、t i 2 ，i = l ，2 ，n ， 则其最优调度可以通过下列j o h n s o n 规则确定。 j o h n s o n 规则：如果m i n t i l ，t j 2 ) t i 2 ，t j l ，则将工件i 排在工件j 之前。 ( 3 ) 流水车间调度问题( f l o w s h o ps c h e d u l i n gp r o b l e m ，f s s p ) 在流水车间调度问题中，所有的操作任务在一组同样的机器上加工完成，工件的所 有操作都有一致的加工顺序，所有的工件的加工路线都相同。流水车间一般是大批量生 产车间或是具有连续生产布局的车间。车间的布局，即机器、工作台及装配线等等的排 列方法，是为便于产品流动而设计的。 ( 4 ) 作业车间调度问题( 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 ) 4 第一章午问调嚏问题研究 在作业车问调度问题中，所有的操作任务由车问内一组功能不同的机器完成，不同 的工件有不同的加工操作和加工顺序，每一道加工操作将在一台机器上完成，所有的工 件的。 加工路线不相同。实际应用中的车间调度问题往往是i o bs h o p 型的。 j s s p 的任务就是在满足所有工件工序顺序的前提下，为各个工件寻找一条最优的加 工路线，并要求达到一定的性能指标，如最大化最小完工时间、最小设备占用率等。在 工件技术路线约束，设备能力约束以及人力资源等柔性资源的限制下，j s s p 成为迄今 为止n p 完全问题中最难的问题之一。生产车间中的大多数调度问题都是作业调度问题。 此外，实际车间调度中还存在着开放式车间调度，混合型车间调度等类型。 1 3 车间调度问题的研究方法 经过几十年的研究，研究人员在车间调度的领域里取得了很多丰硕的成果，产生了 许多好的研究方法。总结他们的研究思路，他们对车间调度问题的研究大致可以按照图 1 1 的思路进行，首先通过对调度问题进行建模、算法分析( 选择算法) 、试验仿真、” 然后对不同算法的仿真结果进行比较以选择最优的算法，或者对问题进行重新建模和构 建新的算法，最后得到最优的求解问题的方法。 图1 1 调度问题的研究思路 f i g 1 1p r o c e d u r eo fs t u d y i n gt os c h e d u l i n gp r o b l e m 总结研究人员对调度问题的研究成果，可以归纳出一些对求解调度问题行之有效的 研究方法，主要有以下几种方法： ( 1 ) 基于启发式调度规则的方法 由于启发式调度规则具有简单，易于实现，以及计算复杂度低的优点，在传统的生 产加工任务调度中被广泛的应用。但启发式规则一般不具备全局优化的缺点。为了克服 这一缺点，多年来，研究人员通过对其进行广泛的研究，并不断的改进和创造新的调度 5 人连交通人学_ r 学硕十学位论文 规则。综合他们的研究成果，这些调度规则主要分为：简单规则、复合规则、启发式规 则三大类【3 1 。 ( 2 ) 基于系统仿真的方法 制造系统一般都具有复杂性，很难用精确的解析模型进行描述，为解决这一问题，常常 通过运行仿真模型来收集数据，即可对实际系统进行性能、状态等方面的分析，从而对 系统采用合适的控制调度方法。尽管系统仿真与实际调度问题可能存在一定的差距，但 仿真的方法具有试验周期短，不受时空约束，可以进行重复建模分析的优点，因此，仿 真方法被广泛的应用。现在，系统仿真已逐渐发展为一种人机交互的柔性仿真工具，并 用来模拟实际的生产调度。 ( 3 ) 基于人工智能的方法 近年来受需求的推动，研究人员在基于知识的智能调度系统和方法的研究上取得了 很大的进展，他们利用模型和知识库，通过运用模拟和推理机制等手段来为人的决策行 为提供支持，人可以根据车间情况的变化做出不同的决策，它的当前应用主要包括智能 调度专家系统、基于智能搜索的方法及基于多代理技术( m u l t i a g e n ts y s t e m 简称m a s ) 的合作求解的方法等。 ( 4 ) 基于神经网络优化的方法 神经网络模型的出现是解决车间调度问题的一种新思路，它主要通过一下三种方式 用于车间调度：一是用其快速的并行计算能力，求解优化调度，以克服调度的n p 难问 题；二是用其学习能力，从优化轨迹中提取调度知识；三是用神经网络来描述调度约束 或调度策略，以实现对生产过程的可行或次优调度。由于是新出现的模型，目前还具有 很多的缺点如计算效率低，需要的计算参数繁多，实际应用复杂。 ( 5 ) 具有计算智能的局域搜索法 演化规划( e p ) e p 是上个世纪6 0 年代提出的。后来，f o r g el d b 1 4 j 借助于演化 策略的方法对e p 进行了改进，并用到数值优化和神经网络训练等问题之中。 遗传算法( g a ) 近年来，由于g a 在理论和经验上被证实在复杂空间中的具有鲁 棒性，它被广泛应用于机器学习、控制、优化等领域。g a 在实际生产调度中的应用已 经很多，大都以传统的j o bs h o p 5 域f l o ws h o p 6 l 为背景的应用。 禁忌搜索( t s ) t s 通常作为解决复杂组合优化问题的一种搜索策略和方法 7 1 ， 目前，t s 己在调度、交通运输、t s p 、电子电路设计等诸多领域中得到了应用【8 l 。 模拟退火( s a ) s a 可用于求解组合优化问题的最优解或次最优解。首次将s a 用于优化领域的是k i r k p a t r i c k 9 1 ，此外s a 在j o bs h o p 和f l o ws h o p 问题中也有一些应用 【1 0 】。s a 能够较好地避免局部最优，但同时却存在着收敛速度慢的问题。 6 第一章乍问调度问题研究 粒子群优化( p s o ) p s o 是由研究人员e b e r h a n 【1 1 】等人通过模拟鸟类的捕食行为 提出来的仿生算法，它具有简单、易行以及多点并行搜索的特性，适用于求解多目标车 间调度优化问题。尽管p s o 算法本身存在着早熟、收敛速度慢等缺点，但通过一系列 改进方法已被证明是一种高效、简单的全局优化算法。粒子群算法的应用已经遍及生产 调度的各个领域。 如机器人研究、优化问题求解、电力系统、交通运输、通讯、电力、计算机等。 1 4 车间调度问题的研究现状 在过去的几十年里，车间调度问题吸引了无数研究者的兴趣，大量的研究成果相继 问世，但由于调度问题的复杂性，其中大多数的研究集中在经典的作业调度问题。即： 给定一个工件的集合和一个工序的集合，每个工件包含多道工序，每道工序需要在一台 给定的机床上非间断的加工某一段时间；每台机器一次最多只能加工一道工序；调度就 是把工序分配给机器上某个时间段。问题的目标是找到最小时间长度的调度。从上面的 问题模型可以看出，经典的调度问题对真实的环境进行了大量的简化，忽略了很多重要 的因数，与实际应用尚有不少的差距【1 2 1 。 调度问题是一种典型的组合优化问题，求解调度问题的算法很多，到目前为止，主 要形成了三大类：精确算法、启发式方法和智能搜索算法。其中比较典型的算法有：调 度规则、禁忌搜索算法、启发式搜索算法、人工神经网络、模拟退火算法、遗传算法以 及粒子群算法等，这些算法各有不同的特点，它们在各种条件下的性能也各不相同，因 此对它们的比较分析非常重要。通过对尽可能多的算法研究成果进行了间接的比较分 析，分析的结果使得我们对这些算法有如下三个衡量准则：有效性、适应性和计算复杂 性【1 1 l 。 ( 1 ) 算法的有效性：有效性指的是算法的最优解逼近程度，也可以用达到最优解的 概率来表示，其中还包括同问题规模的关系。 ( 2 ) 算法的适应性：指的是某种算法的适用范围，也可以说是算法的通用程度。对 于各具体的问题，适用的算法往往不一样，有时候同样类型的问题，由于追求的目标函 数不同，应该采用的算法也不一致。 ( 3 ) 算法的复杂性：由于大多数调度问题都是组合优化的问题，所以计算效率问题 显得特别重要。对于一些简单的问题，可以用数学手段来表达算法的复杂性，然后再进 行比较；而对一些较复杂的算法，可能需要计算实验。算法的复杂性经常同前两个指标 发生冲突，即有效性和适用性较好的算法可能计算复杂性较差。 7 大连交通人学1 学硕十学伊论文 近年来，随着人类对大自然的研究越来越深入，研究人员开始运用模拟自然界一些自然 现象或生态现象发展出一系列仿生型的智能优化算法，并把它们应用于求解生产调度问 题。鱼群算法，蚁群算法，粒子群算法等就是典型的代表。 本章小结 本章主要对车间调度问题及其研究状况进行了介绍，首先对车间调度问题进行了描 述，然后根据研究对象的复杂性对车间调度问题进行了分类，并介绍了研究人员多年来 对车间调度问题常用的研究方法以及问题的研究现状。 8 第：章粒子群算法 第二章粒子群算法 群智能算法是指模拟群居生物的群体智能行为的计算方法，它源于人们对鸟群、蚁 群等生物群体行为的观察、分析与研究。目前，我国的群智能算法的研究尚处于初级阶 段，由于群只智能算法展示出了良好的性能和发展前景，在国外，群智能算法已成为一 个研究的热点。当前的群智能算法主要有两种：蚁群算法( a n tc o l o n yo p t i m i z a t i o n ) n 2 1 和粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) n 羽。另外还有鱼群算法、 蜂群算法等。本章将介绍粒子群算法起源、规则、基本原理、性能及改进方法，最后介 绍粒子群算法当前主要的应用领域。 2 1 粒子群算法的起源及基本规则 2 1 1 粒子群算法的起源 粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) ，又称微粒群算法作为群智能体算 法的一种实现形式，是由美国社会心理学博士j k e n n e d y 与电气工程学博士r e b e r t h a r t l l 4 j 于1 9 9 5 年提出的，它的基本思想是受他们早期对鸟群、鱼群和人类社会群体行为的启 发，通过建模和仿真研究，最后提出来的。粒子群算法作为一种新近出现的仿生算法和 一种基于群智能方法的演化计算技术。一经提出，就受到了广大研究者的关注。 生物学家f r a n kh e p p n e r 通过多年对鸟类聚集行为的观察，提出了鸟类模型1 5 j ，他 发现鸟类模型在反映群体行为方面与其他仿生模型有许多相同的地方，他在此基础上增 加了鸟类被吸引飞向栖息地的条件，构建了一种新的鸟群仿真模型，一开始每只鸟均没 有特定目的地的飞行，直到其中有一只鸟飞到了栖息地，当设置期望栖息比期望留在鸟 群中具有更大的期望值时，每一只鸟都离开原来的群体而飞向栖息地，随后其他的鸟也 将跟着飞到栖息地，从而就形成了鸟群。r e y n o l d s 通过对现实中鸟类运动的观察，并在 计算机中模拟这些鸟类群体的运动，通过对鸟类群体运动的抽象建模，提出了b o i d 模 型【1 6 1 。 j k e n n e d y 与r e b e r t h a f l 在研究f r a n kh e p p n e r 的鸟类仿真模型和r e y n o l d s 的鸟群 社会系统仿真的基础上，引入了一个新的特点。他把这个特点定义为食物，鸟根据自身 周围的鸟的觅食行为来进行扑食，这种通过模拟鸟群寻找食物的过程，蕴含着在多维空 间很强的寻优能力，为了更好的在计算机上实现这种鸟类觅食行为的模拟，他们用一个 点来表示一只鸟，即群体中的一个个体，于是得到了p s o 算法。该算法通过在个性和 社会性之间取得平衡，即让个体保持自己的个性，又能知道其他个体找到的好解并向他 9 夫连交通人学t 学硕十学位论文 们学习，因此粒子群算法是在保证个体自身特性的基础上，并利用群体中信息的共享原 理来构造的一种优化算法。 2 1 2 粒子群算法的基础规则 自然界中各种生物都有一些简单的群体行为，这些群体个体行为通常有几条简单的 规则进行建模，如鱼群、鸟群等。尽管这只是一些简单的行为规则，但研究人员通过对 这些行为规则的探索发现由简单个体行为组合而成的群体行为却非常复杂，仔细的研究 发现这些群体行为具有一定的规律可遵循。r e y n o l d s 在使用计算机动画对鸟类群体行为 进行仿真试验时，采用了以下三条基本的规则【1 7 l ： ( 1 ) 鸟群中的每只鸟均朝远离其最近的鸟的方向飞行，以避免碰撞： ( 2 ) 鸟群中的每只鸟均朝向目的地飞行； ( 3 ) 鸟群中的每只鸟均朝向鸟群的中心飞行。 上面是粒子群算法思想关于个性的一个基本规则。研究学者b o y d 与r i c h e r s o n 在对 人类的决策过程进行探索时，提出了个体学习和文化传递的概念。根据他们的研究结果， 人们在使用算法的过程中应用以下两种信息进行决策： ( 1 ) 自身的经验： ( 2 ) 其他人的经验。 人们在行为的发生过程中通常结合自身的经验，又同时参考其他人的经验，最终做 出自己的决策。这是粒子群算法思想的关于社会性的另一个基本规则。 2 2 基本粒子群算法概述 2 2 1 粒子群算法的基本原理 作为群体智能算法中的一员，粒子群优化( p a r t i c a l es w a r mo p t i m i z a t i o n ，p s o ) 算法 是近年来发展起来的一种新的进化算法( e v o l u t i o n a r ya l g o r i t h m e a ) p s o 算法属于进 化算法的一种，它和遗传算法相似，也是从随机解出发，通过迭代寻找最优解，它也是通过 适应度来评价解的品质但是它比遗传算法规则更为简单，它没有遗传算法的“交 叉”( c r o s s o v e r ) 和“变异”( m u t a t i o n ) 操作它通过追随当前搜索到的最优值来寻找全局最 优。为了代替传统的遗传操作，每个“粒子 ( 个体) 根据其自身的经验和同伴的经验来 调整自身的“飞行 方向和速度。粒子群优化算法由于运行它所要求的内存和c p u 速 度并不高，它不需要梯度信息，所以实现起来很容易。粒子群优化算法只要得到目标函 数的值就行了，不需要做求导，用到的只是一些基本的数学运算，目前已经能够证明粒 子群算法能有效的解决全局优化问题并且能有效避免一些其它优化方法的缺点。 1 0 第二：章粒子群算法 r e y n o l d s 通过对鸟群飞行的研究发现，鸟只追踪它有限数量的邻居，根据它们的位 置。调整自己的飞行方向，但最终的整体结果使得整个鸟群好像处于一个中心的控制之 下，即复杂的全局行为是由简单规则的相互作用而引起的。粒子群算法源于对鸟群捕食 行为的研究，一群乌在一定区域内随机搜寻食物，如果这个区域里只有一块食物，那么 找到食物的最简单有效的策略就是搜寻当前离食物最近的鸟的周围区域。p s o 算法就是 从这种模型中得到启示而产生的，并被用于解决一系列优化问题。另外，人类的行为通 常是以总结他们自己的经验和学习他人的经验来作为决策的依据，这就构成了p s o 的一 个基本概念。 模拟动物行为是为了更好的模拟人的社会行为，虽然人类与鸟群、鱼群等动物的行 为有很大的不同。其中最大的区别在于人的主观能动性。动物群体行为的意图是为了回 避敌人、寻找食物或优化周围环境等。而人类除此以外，还会不断根据变化来调整认知 和总结经验，以此来保持社会群体的一致性。 粒子群算法正是模拟了鸟群对物理环境的反应，并结合了人类对社会的感知。它将 每个个体看作多维寻优空间中的一个没有质量没有体积的粒子，在搜索空间中以随机的 初速度，通过对周围环境的学习和适应，并根据个体与群体经验的综合分析来动态调整 自身的加速度和飞行方向。在整个寻优的过程中，每个粒子的适应度值取决于所选优化 问题计算所得的优化函数值，历史最佳位置被视为粒子自身的飞行经验，整个群体所有 粒子目前为止所发现的最好位置被视为粒子群的整体共享的经验。粒子根据自身和群体 的历史最优位置来对粒子当前的运动方向和运动速度施加影响，它能很好的协调粒子自 身运动和群体运动之间的关系。 2 2 2 粒子群算法的数学描述 粒子群算法与其他的优化算法类似，都是以“群体”与“进化”的思想为基础，根 据个体适应度大小进行操作。不同的是，粒子群算法在求解过程中，每个粒子都都是n 维空间中没有质量与体积的微粒，在搜索空间范围内以一定速度飞行。p s o 被用来求解 优化问题时，问题的解对应于n 维搜索空间中一个粒子的位置，每个粒子都有自己的位 置和速度( 决定粒子飞行的方向和距离) ，以及一个由被优化函数决定的适应值。各个粒 子记忆自己经历过的最优位置、并朝着当前的最优粒子的方向飞行，在解空间范围内搜 索。每次迭代的过程不是完全随机的，如果找到较好解，将会在此基础上来寻找下一个 解。 在p s o 的求解优化问题的过程中，首先在搜索空间内随机初始化为一定数量的粒子 种群，在对种群的每一次迭代中，粒子通过跟踪两个“极值”来更新自己：第一个是粒 人连交通火学f + 学硕十学付论文 子本身所找到的最好解，叫做个体极值点( 用p b e s t 表示其位置) ，另一个是当前整个种 群找到的最优解或一定范围内找到的最优解，称为全局最优解( 用g b e s t 表示其位置) 或 者局部最优解( 用l b e s t 表示其位置) 。 d 维搜索空间中每一个粒子的个体信息，可以用数学向量表示如下： 彳；= 。，毛：，) r k 一( u 。，u ：，u ，) r e 一( 只。，只：，既) r ( 2 1 ) ( 2 2 ) ( 2 3 ) 置为粒子i 在搜索空间中的当前位置，k 为粒子i 的当前飞行速度，只为粒子i 所经历过的最好位置，也就是粒子i 所经历过的具有最好适应值的位置，称作粒子i 的 最优位置p b e s t 。 在找到个体的最优位置p b e s t 和种群的全局最优位置g b e s t 这两个最好解后，粒子 可以根据如下的公式( 2 4 ) 和( 2 5 ) 来更新自己的速度和位置。 速度和位置的更新方程为 嘭”一嘭+ q r a n d ：( p b e s 4 一) + c ：m ，z d ：( 驴部t 一) 1 一+ 1 ( 2 4 ) ( 2 5 ) 也是粒子i 在第k 次迭代中第d 维的速度：c 1 ，c ，是加速系数( 或称学习因子) ，分 别用来调节向全局最优粒子和个体最优粒子飞行的最大步长，若太小，则粒子可能远离 目标区域，不能向目标区域靠近；若太大则会导致突然向目标区域飞去，或飞过目标区 域。因此，选择合适的c 1 ，岛可以加快收敛且不易陷入局部最优，通常令加速系数 c 1 - c 2 - 2 ，r a n d ，r a n d ，是 o ，1 之间的随机数：屯是粒子i 在第k 次迭代中第d 维的 当前位置；p d 缈乞是粒子i 在第d 维的个体极值点的位置( 即坐标) ：g b e s t a 是整个种群在 第d 维的全局极值点的位置。为防止粒子远离搜索空间，粒子的每一维速度都会被限 制在一个范围卜屹一，+ 屹一j 之间，但若屹一太大，粒子将飞离最好解，太小则易陷入 局部最优，得不到全局最优解。因此常常加上另外一个限制条件，将搜索空间的第d 维 定义在区间【一屹一，+ 屹一j ，则通常使速度和位置关系满足屹一2 舡0 一，0 1 s ks 1 0 ，每 一维都用相同的设置方法。在二维的空间中粒子的移动如图所示： 1 2 第：章粒子群算法 图2 1 粒子的移动原理 f i g2 1t h em o v i n gp r i n c i p l eo fp a r t i c l e 2 2 3 粒子群优化算法的基本流程 基本粒子群算法的流程可以描述为： s t e p l ：种群初始化，设定加速常数c l 和c ：，最大的进化代数，在搜索空间内随机初， 始化m 个种群粒子的初始位置f 及其速度f ，其中x ，i e ( 1 , m ) 组成初始种群x o ) ； v o , i e ( 1 , m ) 组成速度矩阵v ( o 。 s t e p 2 ：评价种群x ( t ) ，计算每一个粒子的适应值。 s t e p 3 ：比较粒子的适应值和自身的最优值p b e s t ，如果优于该粒子当前的个体极值，则 将p b e s t 设置为该粒子的当前位置，且更新个体极值，否贝l j p b e s t 保持原来的位置不变。 s t e p 4 ：比较粒子个体极值与种群最优值。如果当前粒子的个体极值优于当前的全局极 值g b e s t ，则将g b e s t 设置为该粒子的当前位置，记录该粒子的序号，并更新全局极值。 s t e p 5 ：粒子的更新，按照上面公式( 2 4 ) 和式( 2 5 ) 对每一个粒子的速度和位置进行更 新，产生新一代种群x ( t + 1 ) 。 s t e p 6 ：条件判别，判断是否符合结束条件，如果当前的迭代次救达到了预先设定的最大 次数已一或者适应值已经达到要求精度e ，则停止迭代，输出最优解，否则，t = t + l ，转至l j s t e p 2 。 综合以上的步骤，把粒子群算法的整个流程用流程图实现如下： 人连交通人学i ：学硕十学何论文 图2 2 粒子群算法流程图 f i g2 2t h ef l o wc h a r to fp a r t i c a l es w a r mo p t