（控制理论与控制工程专业论文）基于混合微粒群算法求解加工时间不确定的flowshop鲁棒调度问题.pdf

山东大学硕士学位论文 摘要 随着全球经济一体化的发展，企业之间的竞争日益激烈。在企业中合理 规划生产的运作方式，节约生产成本，成为提高企业竞争力的一个核心问题。 而合理规划生产运作方式的核心是能够得到一个最佳的调度方案。因此，研 究生产调度问题具有非常重要的理论意义和现实意义。 f l o w s h o p 调度问题( f s s p ) 即流水车间调度问题，是生产调度问题中一 类重要的问题。由于各种原因，在实际生产过程中存在很多不确定性，本文 所研究的是一种加工时间不确定的f s s p 。在研究的问题中不仅考虑到不确定 性存在，而且还能尽量减少在有干扰发生时对结果产生的影响。微粒群算法 ( 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 ) 是一种新兴的智能优化算法，具有原理 简单，参数少，操作少，容易实现的特点，是一种高效的并行搜索算法。目 前微粒群算法已经广泛用于函数优化、人工神经网络训练、组合优化等领域， 成为目前进化计算研究的一个新热点。微粒群算法的研究领域不断扩大，也 不断深入。本文根据对微粒群算法和其它智能优化算法的研究，提出一种混 合微粒群算法，用来处理加工时间不确定的f s s p ，主要做了以下工作： ( 1 ) 分析了当前微粒群算法的原理和特点以及参数选择等，总结了已有 的改进方法。针对微粒群算法的特点提出了一种混合微粒群算法，该算法利 用其他两种算法的优势弥补了微粒群算法的缺陷。 ( 2 ) 针对加工时间不确定的f s s p ，提出了一种鲁棒m a k e s p a n 指标，通过 这个指标，对两个相互冲突的目标进行折衷，从而能够得到既有鲁棒性又兼 顾m a k e s p a n 的调度方案。基于提出的鲁棒m a k e s p a n 指标，对单目标和双目 标的f s s p 做了研究，用混合微粒群算法做了仿真实验，并和其他算法做了对 比。仿真结果验证了该算法的优势。 关键词：f l o w s h o p 调度问题；微粒群算法；遗传算法；变邻域搜索：不确 定性；鲁棒性 山东大学硕士学位论文 a b s t r a c t w i t ht h e d e v e l o p m e n to fg l o b a l e c o n o m i ci n t e g r a t i o n ，c o m p e t i t i o nh a s b e c o m em o r ea n dm o r ef i e r c e l ya m o n gt h eb u s i n e s se n t e r p r i s e s t op r o g r a m o p e r a t i o nw a yf o rp r o d u c t i o nr e a s o n a b l ya n de c o n o m i z ep r o d u c t i o nc o s ta l et h e k e y sf o rac o m p a n y t os u r v i v ea n dg r o wl a r g e r h o w e v e r , ab e s ts c h e d u l i n gi sv e r y i m p o r t a n tt op r o g r a mo p e r a t i o nw a yf o rp r o d u c t i o nr e a s o n a b l y t h e r e f o r e ，t h e r e s e a r c ho np r o d u c ts c h e d u l i n gh a sn o to n l yt r e m e n d o u sa c a d e m i cv a l u e ，b u ta l s o h a sg r e a tp r a c t i c a lm e a n i n g f l o w s h 叩s c h e d u l i n g ( f s s p ) i sak i n do fp r o d u c t i o ns c h e d u l i n g i nt h er e a l p r o d u c t i o np r o c e s s ，m u c hu n c e r t a i n t ye x i s t sd u et o v a r i o u sf a c t o r s t h i sp a p e r m a i n l yr e s e a r c h o nf s s pw i t hu n c e r t a i np r o c e s s i n gt i m e s ，c o n s i d e r i n gb o t h u n c e r t a i n t ya n dr e d u c i n gt h ea f f e c to ft h ed i s t u r b a n c ea sm u c ha sp o s s i b l e p a r t i c l e s w a r mo p t i m i z a t i o n ( p s o ) i san e w l yi 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 m ，a n di th a s n o t a b l ec h a r a c t e r i s t i c s ，s u c ha ss i m p l ep r i n c i p l e ，l e s sp a r a m e t e r sa n do p e r a t i o n s ， m o r e o v e r , i ti se a s i l yr e a l i z e d s oi ti sa k i n do fe f f i c i e n tp a r a l l e ls e a r c ha l g o r i t h m p r e s e n t l y , p s oh a sb e e nw i d e l yu s e d i nm a n yf i e l d s ，f o re x a m p l e ，f u n c t i o n o p t i m i z a t i o n ，m a n u a ln e u r a ln e t w o r kt r a i n i n g ，c o m b i n a t i o no p t i m i z a t i o n ，e t c a n di t h a sb e e nan e wf o c u so fe v o l u t i o na l g o r i t h m sr e s e a r c h t h ed o m a i no fr e s e a r c ho n p s oi sl a r g e ra n dd e e p e r b a s e do nt h er e s e a r c ho np s oa n do t h e ri n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s ，ah y b r i dp s o w a sp r o p o s e d ，w h i c hw a su s e dt od e a lw i t h f s s pw i t hu n c e r t a i np r o c e s s i n gt i m e s t h em a i nt a s k so f t h ep a p e ra r ea sf o l l o w s ： ( 1 ) t h ep r i n c i p l e sa n dc h a r a c t e r i s t i c s o fp s ow e r ea n a l y z e d ，i n c l u d i n g p a r a m e t e r si np s o i m p r o v e dm e t h o d sa n da p p l i c a t i o n so ft h ec u r r e n tp s o w e r e s u m m a r i z e d b a s e do nt h ec h a r a c t e r i s t i c so fp s o ，a ni m p r o v e dp s oa l g o r i t h mw a s p r o p o s e d w h i c hu s e dt h ed o m i n a n c eo fo t h e ra l g o r i t h m st or e m e d y t h e s h o r t c o m i n g so ft h ep s o ( 2 ) ar o b u s tm a k e s p a nc r i t e r i o nw a sp r o p o s e db a s e do nt h ef s s pw i t h u n c e r t a i np r o c e s s i n gt i m e s t h r o u g hc o m p r o m i s i n gt h et w oc o n f l i c to b j e c t i v e s ，a 3 山东大学硕士学位论文 m o r er o b u s ts c h e d u l i n gw i t hm i n i m i z i n gm a k e s p a ni so b t a i n e d b a s e do nt h e r o b u s t m a k e s p a nc r i t e r i o n ，e x t e n s i v ee x p e r i m e n t sw e r ep e r f o r m e d 0 1 1 s i n g l e 。o b j e c t i v ea n db i o b j e c t i v ep r o b l e m su s i n gt h eh y b r i dp s o ，w h i c hi sv e r y e f f e c t i v e ，c o m p a r e dw i t ho t h e ra l g o r i t h m s k e y w o r d s ：f l o w s h o ps c h e d u l i n gp r o b l e m s ；p a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h m ；g e n e t i ca l g o r i t h m ；v a r i a b l en e i g h b o r h o o d s e a r c h ；u n c e r t a i n t y ； r o b u s t n e s s 4 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均己在文中以明确方式标 明。本声明的法律责任由本入承担。 期：燮墨蟹 关于学位论文使用授权的声明 本入完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：麴鏊导师签名：， 稳定性原则：群体不应在每次环境变化时都改变自身的行为。 ( 5 ) 适应性原则：在能够接受的计算代价内，群体必须能够在适当的时候 合理改变自身的行为。 通过这些原则可以看出，群体中的个体能够在环境中表现出自主性、反 应性、学习性和自适应性等智能特性。但是组成群体的每个个体并不具有复 杂的行为，只具有简单的智能，它们通过简单的相互合作表现出复杂的智能 行必。 群智能优化算法具有以下特点【1 3 】f 3 4 】f 3 5 】： ( 1 ) 无集中控制约束。不会因为个别个体的故障影响整个群体对问题的 求解，具有较强的鲁棒性。 ( 2 ) 可扩充性。以非直接的信息交流方式确保了系统的扩展性。由于系 统中个体的增加而增加的系统开销较少。 ( 3 ) 并行分靠式算法。虽然令体的信息是局部的，但通过个体闯的信息 交流，整个群体的信息却是全局的。 ( 4 ) 筠单性。每个个体的能力十分篱单，执行时间较短，容易实现。 ( 5 ) 自组织性，即群体表现出来的复杂行为是通过简单个体的交互丽凸 现出来的智能。 正是由于群算法的这些特点，使它能够为解决些复杂难题提供了一种 有效的方法。 2 1 2 微粒群算法的起源 c a r a i gr e y n o l d 在1 9 8 6 年所提出的一个用于模拟鸟类聚集飞行行为的仿 真模型b o i d 。这个模型对个体设定了简单的运动规则来模拟鸟群的复杂行为， 进行计算机仿真。可以说是最早研究鸟禽模型的。后来f r a n kh e p p n e r 在此基 础上增加了目的地对鸟吸弓l 的仿真条件，改进了鸟群模型。 生物群体的活动虽然复杂，但是人们经过长期的观察总结癌一篓规律。 r e y n o l d 总结出y _ - - 条简单的行为艘则3 4 l ： ( 1 ) 向远离个体最近的同伴的方向运动； ( 2 ) 朝目标的方向运动； 1 2 山东大学硕士学位论文 ( 3 ) 朝群体的中心运动。 “社会行为有两个主要的目的：是每个个体能够在搜索食物的过程中 协助其他群内成员，二是群体合作能够提高搜索效掣1 3 】【3 6 1 。通过这种群体的 行为特征，信息之间的相互交流，能够从群中的其他个体上获得经验。 经过长期观察和研究，社会心理学博士j a m e sk e n n e d y 和电器工程师 r u s s e l le b e r h a r t 于1 9 9 5 年提出了微粒群算法。该算法模拟鸟群寻觅食物或憩 息地的活动，把食物或憩息地描述为解空间上的解。该算法把个体抽象为没 有质量没有体积的微粒，以一定的速度在解空间中飞行，通过个体之间的探 索和信息交流，能够使整个种群为发现更好的解提供可能。 2 1 3 微粒群算法的基本原理 微粒群算法把每一个微粒看作是没有体积，质量和大小的质点，在玎维空 间中以一定的速度飞行。每一个微粒都有一个历史最优位置p ，( p b e s t ) ，整个 种群也有一个群最优位置p 。( g b e s t ) 。微粒在飞行的过程中，结合自身的个体 经验和群体的社会经验，调整飞行速度的大小和方向，寻找最优解。 = ( i ，_ ：，吒) 表示在n 维空间中的微粒i 的位置，v = ( 嵋，v f 2 ，i v ，t 。) 表示微粒 f 的对应每一维的速度，= ( 。，p ：2 ，以) 表示微粒i 的当前最好位置， p ：= ( p ：，p 一) 表示种群当前最好位置，t 代表第t 代。1 ，2 ，玎代表疗维空间 的变量。 微粒根据公式( 2 1 ) 来更新速度： v o ( t + 1 ) = w v o ( t ) + c i ，( f ) ( 岛( f ) 一x o ( t ) ) + c 2 r 2 ，( f ) ( p ( f ) 一勤( f ) ) ( 2 1 ) 其中w 代表为惯性权重( 惯性权重是后来y u h u is h i t 3 9 】等作为改进加上去的) ， c j 为微粒自身经验的学习因子，c 2 为社会经验学习因子。v o ( t ) 4 i 个微粒 的第维分量。) ，眨心) 均为0 到1 之间的随机数。另外还要对速度限制 嘭( f ) 一。，。】，防止速度过大，微粒的收敛速度过快，影响微粒在解空间 中搜索最优解的精度，容易陷入局部最优。 公式( 2 2 ) 代表微粒的位置的更新方式，通过微粒上一代的位置和下一代 的速度来调整自身的位置，得到下一代微粒的位置。 山东大学硕士学位论文 x f i ( t 1 ) = x o ( t ) + v o ( t + 1 ) ( 2 。2 ) 公式( 2 1 ) 可以看成三个部分f 3 7 】网。第一部分是w v o ( t ) ，毪，( 磅是微粒豹先 前速度，它维持着微粒的运动，象一个物体具有惯性一样，可称为惯性部分， 体现了全局搜索能力。第二部分为q r 3 簿) ( 岛( f ) 一专( ) ) ，是微粒的基于自身经 验的速度调整部分，称为认知部分，它是一种自身经验的总结，微粒能够从 自身的经验中调整当前的速度，是微粒具有学习能力的种体现。第三部分 为岛吒，( f ) ( 乃( f ) 一( f ) ) ，是微粒的基于群体经验的速度调整部分，称为社会部 分，微粒群算法中的每一个个体，通过信息交流和信息共享，能够从群体中 的其他微粒学习到经验，使算法的收敛能力加快。 如栗没有惯性部分，只有自身经验的学习和社会经验的学习，微粒将迅 速向当前蜀部最优和全局最好解靠近，容易收敛委局部最优。如果没有认知 部分，则速度的调整出惯性部分和社会部分控制，微粒能够迅速收敛到当前 全局最好解，因此很容易陷入局部最优。如果没有社会部分，则速度的调整由 惯性部分和认知部分控制。这时每个微粒都在自己的局部最优附近徘徊，这 只会加强在每个微粒邻域的搜索能力。由于微粒之间没有信息共享，收敛速 度变慢，也很难达到全局最优。这三部分缺一不可。 微粒群算法的基本流程如下： ( 1 ) 季露始纯种群规模，随机产生微粒的初始位置和速度，把每个微粒的 初始值设为p b e s t ，把整个种群的最好位值赋给g b e s t ； ( 2 ) 计算通过每个微粒得到的懈的髫标函数筐； ( 3 ) 对于每个微粒，将其目标函数值和其历史最好位置p b e s t 的目标函数 值比较，如果优于p b e s t ，则用当的位置替换p b e s t ，否则不替换； ( 4 ) 对于每个微粒，将其目标函数值和其整个种群的最好位置g b e s t 的目 标函数值比较，如栗优于g b e s t ，则用当前位置替换g b e s t ，否则不替换； ( 5 ) 根据公式( 2 1 ) ( 2 2 ) 迭代，更新微粒的速度和位置； ( 谚检查是否满足终止条件，如果满足则运出，否则转向( 2 ) 。 基本微粒群算法的流程图如图2 一l 所示： 1 4 山东大学硕士学位论文 图2 - 1 基本微粒群算法流程图 2 1 4 微粒群算法参数设定原则 ( 1 ) 惯性因子的设计 y u h u is h i 等【3 9 】【4 0 1 提出了带有惯性权重的微粒群算法，即速度公式中带有 惯性权重w 。在文献1 3 9 】中建议w 的取值范围是 0 ，1 4 。但实验表明w 的取 值范围是 0 8 ，1 2 时效果更好。较大的 1 4 i 有较好的全局收敛能力，较小的w 有较强的局部收敛能力。y u h u is h i 等1 4 1 】又提出了惯性权重线性变化的改进方 法： “f ) = 0 9 一l 一0 5 ( 2 3 ) 、7 m a x n u m b e r 其中，m a x n u m b e r 为最大截止代数，t 为当前的代数。 j i a o 等【4 2 】提出了一种非线性的惯性因子不断递减的方法，如公式( 2 4 ) 所示： w - w t d ，w e o ，1 】，“( 1 0 0 0 1 ，1 0 0 0 5 ) ( 2 4 ) 山东大学硕士学位论文 并瓣b e n c h m a r k 趣题作了仿真实验，效果有所改善。 ( 2 ) 蠡身经验学习因子壤和社会经验学习因子岛的设计 j 嚣e n 秘e d y 豳l 对自身经验学习毽子q 褰社会经验学习嚣子岛作了进步的 研究，建议q = 乞竺2 ，0 ，但是最近韵实验结采表明选择相对比毪大一些的q 效 果可能更好些，德是q + q 4 o 潲j 。从理论上分析，q ，q 相差太大都片丽 地强调了局部最优和当前全局最好解。而局部最优和尚前全局最好解是可以 相互转化的。当前全局最好解一定是某个或某凡个微粒的局部最优。片面的 强调岛，会影响种群寻找全局最优的能力，因为当前全局最好解未必是整个 问题的全局最优；片面强调q ，则强调了每个微粒的局部最优邻域的搜索，削 弱了向全局最优邻域搜索的能力。 2 1 5 微粒群算法的改进 微粒群算法在连续优化领域已经得到广泛应用，在离散优化领域也在进 步深入。针对微粒群算法的缺点和在离敝优化领域的不断应用，许多研究 者提出了改进算法，本文针对这些改进算法归纳为以下几类： ( 1 ) 对微粒位置的改进 通常微粒代表解空间中的一个解，在文献滓跫箨壤中，徽粒代表解空闻中具 有一定速度飞行翦质点，在处理生产调度翔题时，每一个微粒的链置又对或 着一个调度。文献f 4 1 5 d p m t h es m a l e s tp o s i t i o nv a l u e s p y ) 救则把一个微 粒位置转换成一个调度，文献【4 6 1 用r a n k e d o r d e rv a l u e ( r o v ) r u l e 规则把 个微粒位置转换成一个调度。这鹾个规则都是把微粒在刀维空间的速度等按 照大小排列，把小的排列到调度的前面。这种方式是利用微粒群在连续空间 中的优势来处理离散问题。 l i a d 4 7 1 提确了一种j o b - t o - p o s it i o n 的方法，即把一个微粒( 假设调度中 有嚣个工件) 看成个筇幸茬的一个矩阵，矩阵熬行栈表撵个王韩，矩阵懿列代 表工件在调度中翡位置。工件歹稷如在调度中的第k 个健置的话，那么裁在矩 阵的第，行第k 列上标l ，第歹捌中其他位鬣标0 。逶过某种转换，使得矩簿中 1 6 山东大学硕士学位论文 的第七列上的值代表甩个工件在调度中第k 个位置上的概率。概率高的工件最 有可能安排在调度中的第k 个位置。通过这种方式，能够更快的找到更好的 调度。但是由于微粒构造方式复杂，因此需要花费较多的时间。 ( 2 ) 对速度更新公式的改造 黄岚掣4 8 1 在微粒群算法中引入了交换子和交换序的概念，重新定义了微 粒的迭代和更新公式： v o ( t + 1 ) = ( f ) o ( f ) ( 岛( f ) 一嘞( f ) ) 0 吃，( f ) ( p ( f ) 一勺( f ) ) ( 2 5 ) o + 1 ) = 而( f ) o o + 1 ) ( 2 6 ) 把速度定义为一系列交换，对微粒的位置做交换来得到新的位置。但是 从实验结果看，算法的收敛较慢。 何庆元等4 9 1 提出了一种带有扰动项的改进微粒群算法，对速度公式进行 改进： ( f + 1 ) = w v o ( t ) + q r , ( f ) ( 既( f ) 一毛( f ) ) + c 2 吒( f ) ( p g ( f ) 一x o ( t ) ) + a x ( r 3 ，( f ) 一o 5 ) ( 2 7 ) 即在速度的更新公式后加了扰动项。口是一个较小的数，r 3 m ) 也是一个o 到i 之间的随机数。在算法计算中、后期，当由于粒子的“趋同性”使得粒子速 度越来越小时，扰动项确保了粒子搜索速度不至于下降到0 ，局部搜索能持 续进行，为粒子跳出局部最优提供了可能。 杨亚平【5 0 1 等提出了二次微粒群算法及其参数自适应策略。即 ( + 1 ) = w v j ( t ) + q r l j ( t ) s g n ( p i j 7 ) 一掣( 既( ) 一删) 2 ( 2 8 ) e 2 r 2 ) s g n ( 如( f ) 一矗( f ) ) ( ( f ) 一( f ) ) 2 并在搜索前期适当增大c j 和c 2 ，搜索后期适当减小c i 和c 2 。引入平方项后，当 平方项中的数小于1 时，可以加速收敛，大于1 时，还可以提高种群的多样性， 提高全局搜索能力。 文献【5 l 】在p s o 速度更新公式中，通过引入被动聚集项，实现种群内信息充 分共享，防止了微粒因缺乏足够的信息而判断失误导致陷入局部极小，但由于 附加项的加入，降低了算法的收敛速度。 文献【5 2 1 改进了位置的更新公式，利用k a l m a n 滤波更新微粒位置，使在有效 1 7 山东大学硕士学位论文 减少算法迭代次数豹同时不损坏p s o 快速的收敛能力f 娟。 黪多释群 鹾。l 套v b j e r g 等 5 3 1 在p s o 孛孳1 x t 子秘群熬概念。v a nd e nb e r g h 提出 了m u l t i s t a r tp s o ，每次迭代若干次后，保鳃微粒群的历史最优位置，微粒 全部初始化以提高种群的多样性f 州，但是这样会完全破坏微粒的结构。陈国 初等1 5 5 提出了两种群替代微粒群优化算法。该方法将微粒分成飞彳亍方向不同 的两分群，其中一分群微粒朝着最优微粒飞行，勇分群朝着相反的方向飞 行。接着剃卓待等f 蚓，名琴梅等5 鞠剃用类钕的思想提出了三种群豹微粒群算 法。n i ub e n 等潜提逛了主一从耪群摸型，扶斡群用柬维持种群多样性，主种 群依靠自身经验和从耱群的焦患进傀。 引入多个种群可以保持种群多样性。多种群法的缺点是，在初期的搜索效 率低于标准p s o ，且多个子种群的引入加大了算法的计算量f 3 8 】。一般子种群微 粒个数为2 0 - 3 0 。 ( 4 ) 混合算法 混合算法一般是把冀袍一种或者几种的算法或者其中的操作用捌另种 算法孛，这样熊够弥脊这种算法兹劣势，提褰这种算法的性麓，毙镬焉单一 的算法更商优势。 有些是把模拟退火引入微粒群算法1 5 9 1 _ 【6 ，让微粒在执行微粒群算法操l 乍 后并行执行模拟退火操作；有些是引入遗传操作1 6 2 1 ，或者和遗传算法并行搜 索i 6 3 】；有的引入惩罚函数f 硐；有的引入差分进化【6 s 】l 谰；有的和进化算法结合 钢；有的和交邻域搜索结合 4 s i 德】 蚓。 这些方法有翁子微粒跳毒满都最耄荛，增加种群多样往，性能毙只使用微 粒群算法好。 除了以上算法，还有诲多其绝改进算法，在这鼙不一赘述。微粒群算 法的研究成果不断涌现，相信以后还会有更大的成果。 2 。1 6 微粒群算法的特点 微粒群算法是一种群智能黧法，具有以下优点： ( 1 ) 微粒群算法是一种并行算法，学习麓力强。微粒具畜学习缝力秘记忆 能力，笺够保甓个体最优和当前全局最好解的信息，蒡在搜索最优解过程中 1 8 山东大学硕士学位论文 微粒之间相互交流，信息共享，收敛速度快。 ( 2 ) 原理简单，参数少，操作少，易实现。 ( 3 ) 算法的通用性强，不依赖问题的信息。 微粒群算法也有其缺点： ( 1 ) 微粒群算法从理论上能够找到最优解，但是由于其收敛速度过快容 易陷入局部最优，不容易找到全局最优解。算法在迭代后期种群趋于一致， 失去多样性，搜索精度变低，这也是大多数进化算法的缺点，但是相对来说 微粒群算法还是具有较高的效率。 ( 2 ) 算法的理论基础还不是太强。微粒群算法在连续问题优化方面优势特 别强，在离散问题优化方面也越来越引起更多学者的关注。本文就针对微粒 群算法的优势和缺点，提出了一种适合于离散问题的混合微粒群算法。 2 2 混合微粒群算法设计 2 2 1 算法的提出 微粒群算法作为一种群智能算法，学习能力强，微粒在搜索最优解过程 中微粒之问相互交流，信息共享，收敛速度快；原理简单，参数少，操作少， 易实现等优点，但是在搜索过程中也容易陷入局部最优，种群多样性也慢慢 丧失。 定义2 1 微粒种群多样性微粒群中的微粒因在解空间飞行所到达的位 置不同而搜索到的可行解，即因微粒的位置不同而表现出的多样性称为种群 多样性。它是评价微粒群搜索可行解能力的重要尺度，由下式给出( 2 。9 ) 【7 0 】： 。i v p 坶砂= 去善 f i l 蔷a ( ，一i ) 2 ( 2 9 ) 其中，为微粒群的中心位置，它的第维向量是i 。 如果一个微粒的当前位置与该微粒的当前最优值和整个种群的当前最优 值一致，则该微粒就会以它以前的速度保持不变，导致算法不能收敛，并且 不容易找到最优解。如果以前的微粒的速度非常小，接近于零，一旦接近微 粒群的最优位置，种群的多样性就会慢慢丧失1 7 0 1 。在算法搜索的中后期，微 1 9 山东大学矮士学位论文 粒容易收敛予局部最优，不容易找到全局最优解。 善先用l p s o ( 由l i a o 4 7 】提塞的改迸徽粒群算法不妨麓称为l p s o ) 对加工 时阀不确定的f s s p 佟了仿真实验。虽然l p s o 具有一定的优势，但是在仿真 过程中也发现了一些缺陷。例如在收敛过程中跳出局部最优的能力芳不是很 强，有时候陷入局部最优跳不燃来，种群的多样性也慢慢丧失。同时由于采 用了这种微粒的复杂结构，相同的迭代代数虽然能尽快找到最优解，但是会 耗费更多c p u 时间。另外通过仿真实验褥出了在每个微粒的局部最优来寻找 毙筠部最优更姆酶解也是非常必要，也是菲常有效的。如果增强对局部最优 解邻域蕊攘索，得到更好酶解的撬会就会更大，更容易找到全鼹最钱解。 针对微粒群算法的缺陷和l p s o 的缺陷，结合对微粒群算法秘其它智辘优 化算法的研究，取长补短，设计了一种混合微粒群算法。酋先，针对微粒群 算法陷入局部最优的缺陷，引入了遗传算法，用基于遗传算法搜索。遗传算 法也是种并行群算法，不容易陷入局部极小，能将搜索重点集中于性能高 的部分，通过交叉和变异操作，能够在种群搜寻更好的解的同时，保持种群 的多样性。其次，针对仿囊过程中的经验，对每个微粒的局部最优解邻域局 部搜索，弓l 入变邻域搜索。交邻域搜索算法具裔缀强翡邻域搜索麓力。这样， 一方蘑麓够增大全弱搜索能力，扩大种群的多样性，另一方蟊能够增大局部 搜索能力，从蕊改善解的质量。 通过以上分析，设计了混合微粒群算法g v p s o ( g e n e t i ca l g o r it h m v a r i a b l en e i g h b o r h o o ds e a r c h p a r t i c l es w a r mo p t i m i z a ti o na 1 9 0 r it h i n ) ， 具体设计如下： 2 2 2 算法的舆体设计 ( 1 ) 基于矩阵的微粒结构 基于畦d k e n n e d y 和e b e r h a r t 提出来的离散微粒群算法，l i a oe ta 1 1 4 7 】提 出了一种改进的微粒群算法( l p s o ) 。通过和连续的微粒群算法，遗传算法和 局部搜索对毙，对b e n c h m a r kf s s p 仿真实验，取得了不错的效果，本文采用 这种微粒梅造和迭代祝制。 矩阵采熏稗j o b t o p o s i t i o 羚的结构。善先把一个微粒( 铡懿嚣个王佟) 看成一个嚣奎拜的一个矩阵，矩阵的行代表工件，矩阵的列代表工件在调度中的 山东大学硕士学位论文 位置。工件j 如果在调度中的第k 个位置，那么就在矩阵的第，行第七列上标1 ， 第_ ，行和第k 列中其他位置标o 。因为对于工件_ ，来说安排在调度中的第k 个位 置意味着不能安排到排序中的其他位置；对于一个调度，工件_ ，安排到了第k 个位置意味着别的工件就不能安排在这个位置。微粒i 在第t 代定义为 l = ( ，x 1 ：，乇) ，喙 o ，1 ) 。如图2 2 是微粒的位置和调度的对应关系。 工件j “ n q 位置k l23 4 olo0 100o o001 o01o 图2 - 2 微粒i 的位置x i 的一个排序( 2 ，1 ，4 ，3 ) 微粒位置中的每一位只有两个取值，一个是0 ，一个是l 。例如矩阵第1 行 第一列为0 ，代表工件1 不在调度中的第一个位置；矩阵中第四行第三列为1 代 表工件4 在调度中的第三个位置。图2 2 的微粒位置代表一个调度排序 2 1 4 - 3 。 每个工件在每个位置上都有对应的速度q = ( 嵋，i ：，v m n ) 。通过速度的迭 代公式进行更新： 7 k = 噶1 + c i 吒( p 缸一x t i j k ) + c 2 吒( p 矢一i ) ( 2 1 0 ) 其中和吃是( o ，1 ) 之间的随机数，w 是微粒自身速度的加权因子，c i 是自身 经验的学习因子，c 是社会经验学习因子。由于微粒的位置只取0 和】两个值， 微粒的速度定义为微粒的位置取1 的可能性。 通过s i g m o i d 函数( 2 1 1 ) 把速度转化为概率。 ( 2 1 1 ) s ( 略) 代表在下一代微粒的位置x i ； k 上的值为i 的概率( 值为1 代表工件在 山东大学硕士学位论文 调度中的第k 个位嚣，o 代表不在这个位置) 。速度越大，表明在这个位置的概 率越大。例如s 吃，) = g 8 5 则说明工件2 在调度中第1 个位置的概率是o 8 5 。如 图2 3 所示。 位鬣k l234 工件j n 铲 o 重o0 9 90 。3 3o 6 6 o 8 50 2 0o 6 50 2 8 o 3 lo 1 20 9 2o 5 1 o 。6 4o ，8 3o 。1 70 。9 8 图2 - 3 微粒速度转换线的一个概率s f 咳) 下面还要做的就是构造新的排序。对于每一个微粒都需要重新构造一个 排序。从当前最优调度中按一定规则来重新安排工件在调度中的顺序。 积似) = 盏 ( 2 1 2 ) 酋先设定一个最优调度集会f ，集会大小为，最多能存放，个工件。 构造新排序时，先把最优调度中的翁，个工件放入罗。然后通过( 2 1 2 ) 来看 f 中豹工件安撵在薪调度中第一个位置的可能性。积蠢) 越大，说明安排在 第一个位置的概率越大。安撵完第一个工件瑟，把这个工件移毒，再把最 优调度中的第f + 1 个工件加入f 。褥通过( 2 1 2 ) 选怒最适合安排在新调度中 的第二个工件。依次类推，直到安排完整个调度。当最优调度中没有工件再 加入罗中时，就只从f 中选择合适的工件，然后再把这个工件移出f 。通过 新调度就得到了下一代的一个微粒。用这种方法来生成新种群，通过不断的 迭代寻找最优解。 这种微粒构造方法和迭代方式显然要比用定义在，维空间的微粒迭代起 来会用更多的c p u 时间，但是能够更好更快的找到最优或者接近最优的调度。 为了使算法具有更好的性能，加入了两种局部搜索。在执行搜索之前都 需要根据微粒的位置( 如图2 - 2 所示的方法，即微粒位置翻调度排序的对应关 山东大学硕士学位论文 系) 找到对应调度的排序，根据排序来执行局部搜索，执行完再对应着得到 微粒的位置。 ( 2 ) 基于遗传算法的搜索 遗传算法也是一种并行群算法，不容易陷入局部极小，能将搜索重点集 中于性能高的部分，能够在种群搜寻最优解的同时，保持种群的多样性。利 用遗传算法的优势，每隔一定迭代代数对种群执行一次遗传算法搜索流程， 即选择交叉变异等，通过交叉操作能够有利于产生优良个体，变异有助于增 加种群的多样性，跳出局部最优。这样能够在种群搜寻最优解的同时，保持 种群的多样性。而传统的微粒群算法到了搜索后期容易陷入局部最优，种群 趋于一致。 由于微粒的复杂构造，基于遗传算法搜索之前需要找到微粒对应的工件 排序。遗传算法搜索时，首先通过微粒的位置得到调度，遗传算法采用基于 工序的编码，即用工件的序号来编码，这样就把微粒表示的调度和遗传算法 使用的个体结合在一起了，一个个体就是一个排序，即一个调度，然后再执 行的交叉变异操作。执行完再把排序对应着转换成微粒的位置。 常用的交叉操作利7 1 】：部分映射交叉( p m x ) 、次序交叉( o x ) 、循环交叉( c x ) 、 基于位置的交叉( p x ) 、线形次序交叉( l o x ) 等交叉方式。这旱采用线形次序 交叉。举例说明，假设有两个个体，p j = 264 7358 91 ，只= 452 1876 193 ，交叉中间的四个工件，则首先把中间的部分交叉，然后对异中 的和只交叉部分不冲突的工件按顺序依次放在剩余的位置，对于只操作类似。 即n e w p , = 1876 ，然后再看264 73 58 91 这些工件中如果和 1876 冲突的删掉，剩下的24359 依次放入剩下的5 个位置，得到n e w p i = 2 43l876 59 ，n e w g = 421 73 58 69 。 常用的变异操作有： 互换操作( s w a p ) ，即随机交换个体中两不同基因的位置。 逆序操作( i n v ) ，即将个体两不同随机位置间的工件串逆序。 山东大学硕士学位论文 插入操佟( i n s ) ，即随杌选择某个点插入到排痔中的不同随机位置。 在这里变异操馋用互换操作。 假如只用微粒群算法和基于遗传算法的搜索，通过处理一个加工时间不 确定的f s s p 仿真，可以看出跳出局部最优的能力，如图2 - 4 所示记录了一个微 粒跳出局部最优的过程。图中的曲线中突然上升的地方就表示跳出了局部最 优。 洌 裁 闭 蓬 丑 迭找代数 豳2 - 4随着迭代代数增加算法跳出局部最优 ( 3 ) 变邻域搜索 v n s 方法是i ：l ：l h a n s e n 等于2 0 0 1 年提出的一种后启发式算法1 9 】1 7 2 1 。它用两个 或更多的邻域结构搜索。v n s 不同于其他的局部搜索方法，它是基于在搜索过 程中的系统变化的机制来运行的。另外，为了避免花费太多的计算代价，一 般采用两种邻域结构5 7 朝。 实验表明，组合优化阔题的局部最优解、全局最优解和邻域结构之间具有 如下性质1 6 9 1 。 一种邻域结构的局部最优解不一定是另一种邻域结构的局部最优解。 全局最优解是所有邻域结构的局部最优解。 种邻域结构的局部最优解往往处在另一种邻域结构的局部最优解 附近。 使得变邻域搜索成为有效算法的原阂是：当在一种邻域下遘到蜀部最优 时，可以通过改变邻域定义的方法来继续搜索过程，在搜索过程中当蘸解的 目标函数值是不断改善的，而不必像模拟退火，禁怨搜索等方法需要暂时接 受目标值较差的解柬跳出局部最优。 2 4 山东大学硕士学位论文 采用变邻域算法的目的是为了在每个微粒的局部最优解邻域寻找更好的 解。一方面原因可能是因为问题本身是一个离散的问题，微粒在迭代过程中 可能跳过了最优解，另一方面最优解可能就在局部最优解的邻域，微粒并没 有搜索到。因此对局部最优解邻域进行搜索是很有必要的。采用的两个变邻 域结构如下【7 5 】： 箱交换操作( s w a p ) 定义2 2k 一邻域结构f s s p 的解用一个排序来表示，k 个工序的交换产生 的所有解的集合就定义为一个调度解的k 一邻域结构。 交换操作是在一个解的k 一邻域内进行搜索，为了搜索这个解邻域中更好 的解。 娃插入操作( i n s e r t ) 插入操作是从一个排序中随机产生两个位置，然后把一个的位置的工件 插入到另一个位置的前面。 同基于遗传算法的搜索一样，执行变邻域搜索之前需要先把局部最优微 粒转换成调度。这里局部最优的邻域解即局部最优解任意k 个工序相交换得到 的解，邻域范围即要搜索的邻域解的个数。先对每个微粒的局部最优表示的 调度执行交换操作邻域的搜索，然后执行插入邻域的搜索。如果找到更好的 解，就取代原来的局部最优解，否则不取代。搜索完毕后把最后得到的局部 最优再转换成微粒的位置。 2 2 3 算法流程 整个g v p s o 算法流程如图2 5 所示： 山东大学硕士学位论文 黼2 5g v p s o 箨法流程 山东大学硕士学位论文 具体步骤如下： s t e p l 初始化种群和微粒的速度，设定加权因子w ，自身的学习因子c l ， 社会经验学习因子c ； s t e p 2 计算每一个微粒i 对应调度解的目标函数值，如果微粒i 的目标函 数值比微粒局部最优位置的目标函数值优，则当前微粒位置就取代，否 则不取代； s t e p 3 把每一个微粒的当前局部最优位置b t 和群最优位置砖对应调度 解的目标函数值比较，如果比群最优位置岛t 好，则取代群最优位置，否则不 取代； s t e p 4 通过速度公式( 2 1 0 ) 更新速度，得到下一代的速度，并且加上速 度限制防止速度过大v ； k 卜v ，】； s t e p 5 通过s i g m o i d 函数( 2 1 1 ) 来计算每一个工件在新调度中每一个位 置上的概率s ( 吃) ，通过这个概率，根据公式( 2 1 2 ) 来判断工件j 是否在新调 度中的位置七，具体方法如下：产生一个( 0 ，1 ) 之问的随机数f ，如果 f ( ，后) ，那么工件- ，就在位置七上，否则继续寻找属于f 中的合适的工件 安排在第后个位置为止。然后再寻找新调度中下一个位置排哪个工件，直到安 排完所有的工件。得到了新的调度就得到了微粒的新的位置。用这种方法生 成新种群； s t e p 6 判断是否满足局部搜索条件，如果满足，则转向s t e p7 ，否则执 行s t e p1 0 ： s t e p 7 执行基于遗传算法的搜索。执行局部搜索之前，首先从微粒中得 到调度，一个调度看成一个个体。对比较好的个体( 因为是最小化问题，即目 标函数值小的个体) 在下一代中复制自身的概率大，然后用线性次序交叉根据 交叉概率对个体执行交叉操作；最后对交叉后的个体进行变异( 基因互换) 操作，最后把调度转换成微粒的位置； s t e p 8 对每一个微粒的局部最优进行变邻域搜索，搜索局部最优邻域中 山东大学硕士学位论