一种求解多目标柔性作业车间调度的改进粒子群算法

PAGEPAGE10收稿日期:2009-10-19基金项目：教育部霍英东教育基金青年教师基金项目(111056).新世纪优秀人才支持计划资助项目(NCET-08).一种求解多目标柔性作业车间调度的改进粒子群算法白俊杰王宁生唐敦兵(南京航空航天高校ＣMS工程讨论中心江苏南京210０16）摘要：针对具有高纬搜寻空间的多目标柔性作业车间调度问题，提出了一种基于偏好的多目标粒子群优化算法(PＭOPＳＯ）。算法引入了决策者的偏好信息，用以指导算法的搜寻过程,使算法在决策者感爱好的区域进行搜寻，不但缩小了算法的搜寻空间，提高了算法的效率，而且一次运算只求得偏好区域内若干个折中解，避开了决策者要在众多非劣解中做出困难的选择。在算法中,采纳了新的偏好信息给定方法，即采纳目标间重要关系、目标数值或目标权重大致取值范围来表示偏好信息.采纳该方法，不但便于决策者给定偏好信息,而且还可以依据决策者的需求，对搜寻区域的范围进行适当的调整.针对偏好信息的特点，提出了一种模拟人类社会组织“投票选举"的偏好信息处理方法，该方法直观简便并易于实现.最后,通过实例仿真，对算法性能进行比较分析和评价，结果表明白算法的有效性和可行性。关键词：柔性作业车间调度；粒子群优化算法；多目标优化;偏好信息中图分类号：TＨ１6；TＰ278文献标识码：AIｍpｒoｖedＰＳＯAlｇorithｍforthｅＭultｉ－ObｊecｔiveOpｔimｉｚatioｎＦlｅxiｂleJobＳhopScｈedulingPｒoｂlｅmsBaｉJｕn-jieＷａnｇＮing-ｓheｎgTangDun－bing（CMSReｓeaｒｃhｃeｎtrｅ，ＮａnjingUｎiｖ.OfＡerｏnaｕｔicsanｄAstｒｏnautiｃs，Nａｎｊing21０016,Ｊiangsｕ，Chinａ）Ａbｓｔract:Ｔosｏlvｅthemuｌti-ｏbjｅcｔｉｖｅｆlexiｂｌeｊobｓｈoｐschｅdulingｐｒoｂlemｗiｔｈlａrgeｄｉmensioｎalｓeａrchingsｐａcｅ，ａpreｆｅrｅncebaｓedmuｌｔi—objｅｃtiｖeｐａrticlesｗarｍoptimiｚatｉonａｌgorithm（PＭOPSO）waspｒｏｐoseｄ。Tｈｅpｒeｆerencｅｉnfoｒmａtｉoｎｏｆｄeciｓｉonsmaｋerisｉncorpoｒaｔedintothｅａlgorithmｔoｌｅadthesearchｉnｇdｉrecｔioｎ．Sothat，nｏｔoｎｌｙtｈeseａｒｃhinｇｓpaceiscompresseｄａndtｈeｅｆｆiciencｙoｆtheａlｇoriｔhmisimｐrｏvｅd，ｂｕtaｌsoｊuｓｔafeｗtｒade—oｆfsoｌutiｏnｓlocatedinprｅferｒeｄareaａreobtａiｎｅdinasｉnglerun,aｎdｔｈeｈａrdwoｒｋoｆｃhｏoｓｉnｇaｓatiｓfｙingsoｌutｉｏnfｒｏmnumeｒouｓnon-infｅriｏrsoluｔionsiselｉminａｔｅd。Ｉｎｔheａｌｇorｉtｈm,aneｗeｘpｒｅssioｎmethodofpｒeｆｅrenceinfoｒmationbasedonｉmｐｏrtancｅrｅlatｉｏnshｉpａmｏngoｂjectivesandtｈｅvalueｒangeoｆｏｂjectivesorobjｅcｔivｅｗｅighｔｓwaｓpｒoposed.Ｗitｈthismｅｔhod,ｎotonlytｈeｐreｆｅｒeｎｃeｏｆdｅcｉsｉoｎsｍａkercanｂｅeａｓilyｓpecified，bｕtaｌsoｔｈerangｅofsｅarｃｈiｎgａｒeａｃaｎbeａdｊｕstedpropｅrlｙaccordｉnｇtｏｔｈｅrequireｍenｔsofｄeｃisionsｍａｋer.Inｖｉewoftｈｅcharａcｔeristｉcsｏfpｒｅfｅrenceinformatｉｏｎ，aｎewpｒeferenceinfoｒmaｔionｈaｎdｌiｎｇmetｈoｄ，whｉｃhｓimulateｓtｈｅ“vｏte”ｏｆhumanｓｏciｅtｙ，ｗａｓｐroposeｄ．Tｈeｍethodisiｎtｕitive,sｉｍplｅaｎdeasｙtousｅ.Finally,ｔhepｅｒｆorｍaｎcｅoftｈeaｌｇorｉtｈｍwasｅvaluａtedｔhrｏｕgｈsｉmuｌａtiｏｎs,anｄtheresｕltｓdemonstraｔethｅfeasiｂiｌityaｎdeffiｃｉencyｏｆpropｏseｄａlｇｏrｉtｈm.Ｋeｙwoｒｄs：ｆlｅxiｂｌｅjoｂshｏpscheｄulｉｎg;partｉcｌｅswarｍｏpｔｉｍizａｔionalｇoriｔｈm；ｍuｌｔi－objecｔｉvｅoptｉmｉzａtiｏｎ;prefｅrｅncｅinfoｒmatioｎ0．引言近年来，多目标柔性作业车间调度问题(Ｍulti-ｏbjeｃｔｉveFlexiｂleＪｏｂ－shopSｃｈeduliｎｇＰroｂleｍ，MＦJSP）日益受到了学者们的关注,一些学者对该问题进行了深化的讨论.以往的讨论通常采纳分步的求解策略，即首先采纳多目标优化算法搜寻到一组均匀分布在整个Paretｏ曲面的最优解,常用求解算法包括改进的混合遗传算法［1、2]、改进的多目标粒子群算法[３]、存档进化粒子群优化算法[4］等;然后再依据决策者的偏好进行多目标决策，从众多非劣解中选出满意的调度方案。这样的求解策略对于目标较少的多目标调度问题往往是有效的,但却很难解决高维多目标优化调度问题。随着调度目标的增加，算法的搜寻空间和Pａrｅtｏ曲面的面积会飞快增大，所包含的非劣解的数量飞快增多。若要使算法朝着各个目标的方向同时搜寻，并使搜寻结果均匀分布在整个Pareto曲面上,则算法搜寻效率会飞快降低，造成所求解的质量偏低,可能无法得到决策者满意解。而且得到的非劣解数量也偏多，造成决策者很难从中选出满意方案.并且，在实际生产中，由于个人的偏好和调度问题自身的需求，决策者通常只对某一区域的Pareｔo折中解感爱好。因此,本文提出了一种适用于求解高维多目标柔性作业车间调度的改进的多目标粒子群算法。该算法采纳偏好信息指导算法的搜寻过程,使得算法在一次运行结束时只求得偏好区域内的若干个折中解，这不但可以大大提高算法的求解效率，削减计算资源的消耗，提高解的质量,同时也便于决策者从较少的候选方案中做出最终的决策。目前,有关多目标优化算法的讨论焦点主要集中于如何通过选取适当的适应值安排策略和排挤算子保持种群的多样性，使得算法最终搜寻到一组均匀分布在整个Paｒｅto曲面上的解。而在偏好信息的处理方面,却很少受到学者们的关注。目前，仅有少数学者对多目标优化的偏好处理问题进行了讨论.Fｏnseca[5］和商秀芹[6、７］分别采纳单个目标向量来表示决策者的偏好信息，并将目标向量引入到算法的群体排序过程中,缩小了解的搜寻范围，该方法简洁易行，但事先需消耗较多的计算资源确定每个目标的变化范围,以便决策者为算法供应精确的合理的目标向量值.余进[8]将偏好信息表示为多个目标向量，将每个目标向量作为一个参考点,一次运算可得到多个特定区域的多个解,该方法是偏好信息单目标向量处理方法的扩展,方法比较新颖.但是，和单目标向量处理方法相同，为了确定各目标的变化范围并选取适当的目标向量值，同样需要事先消耗较多的计算资源。Ｃvｅｔｋvoiｃ[9]和Ｊiｎ［1０］分别将决策者的偏好信息表示为模糊偏好矩阵的形式,并进一步转化为定量的目标权重值，建立了基于权重值的偏好优于关系，该方法在权重值的确定及优于关系的重新定义中，有多个待定参数,而这些参数的取值对解集的构成有着较大的影响。而且，事先很难精准估量各目标的取值范围，因此决策者很难一次给出合理的精确各目标权重值及其它参数值,为了得到问题的满意解,往往需要选取不同参数进行多次求解.Bｒanke［１1］采纳一种线性最大最小协调模型方法将偏好信息引入群体排序过程中,该方法允许用户指定每对目标可以接受的最大“均衡量”，即一个目标获得一个单位程度改进的同时,允许另一目标消灭最大的劣化程度。该方法在两个目标情况下可以获得较好的结果，但在目标较多时,要确定合理的每对目标间的优胜关系则比较困难。而且,随着目标数量的增加,采纳该模型构造和使用优于关系的过程也越来越简洁。崔逊学［12、13］采纳ELＥCTＲE协调模型将偏好信息引入到算法的搜寻过程中，并采纳该协调模型构造了一种称为“级别不劣于"的关系来替代“Pareｔo支配关系”，对进化群体进行排序。该方法思想新颖，但该协调模型所用的参数偏多，而且各参数的取值对解集的构成有显著的影响，为了得到满意解往往需要选取不同的参数，进行反复试验，并且构造和使用该“级别不劣于”关系的过程也很简洁。对以往的讨论成果进行归纳总结,可发现，偏好信息处理方法大致可分为目标权重、目标向量和多目标决策协调模型等3类方法.采纳目标权重和目标向量的偏好信息处理方法，虽然构造和使用新的优于关系的过程比较简洁,但是为了给出合理的精确的目标权重值和目标向量值，往往需要事先进行多次求解试验.而且，采纳精确的目标权重值和目标向量值来引导算法搜寻方向,往往造成算法搜寻区域过于狭小。因此，不但使算法易于收敛到局部极值，形成早熟现象;而且,搜寻区域过于狭小很可能漏掉一些更让决策者满意的折中解。采纳多目标决策协调模型的方法，虽然可能省略计算目标权重和目标向量的工作，但是采纳该方法构造新的优于关系过程中所用参数偏多,而且最终解集构成对各参数比较敏感，往往需要选取不同参数进行反复试验才能得到满意解，而且随着目标数量的增多，构造和使用新的优于关系的过程也越来越简洁。针对以往讨论的不足，本文提出了一种基于偏好的多目标粒子群算法（pｒefereｎcebａsedｍulｔｉ—oｂjectivepａrticｌeｓwaｒmoptｉｍｉzａtiｏｎaｌgorｉthm，ＰMＯPSO）。该算法不再采纳精确的目标权重或目标向量的偏好信息给定方法，而是采纳目标间重要关系、各目标权重值的大致范围、或各目标大致取值范围形式表示.这样，既便于决策者给定偏好信息,避开了因给出精确的目标权重值和目标向量而作大量的预先计算工作;同时,决策者还可以依据自身的需求,对算法搜寻区域的范围进行适当调整，在提高算法搜寻效率的同时,避开了因搜寻区域过于狭小而造成满意折中解的遗漏.结合“Paｒeｔo支配”和偏好信息定义了一种新的“偏好优于关系”，在按“偏好优于关系”对群体进行排序过程中提出了一种新的偏好信息处理方法，该方法模拟人类社会组织由低级向高级进化过程中“投票选举"的过程，采纳种群投票表决选取偏好解集的方式，引导算法朝着偏好区域搜寻,加快算法的求解速度，并使结果集中在决策者偏好区域内,便于最终决策。该方法直观、简洁易行，并且不需要设置过多的参数。最后采纳高维多目标柔性作业车间调度问题验证了算法的性能，仿真结果表明白算法的有效性和可行性。多目标柔性作业车间调度１.１问题描述多目标柔性作业车间调度问题的可描述为:一个加工系统有台机器，要加工种工件。每个工件包含一道或多道工序，工件的工序挨次是预先确定的；每道工序可以在多台不同的机床上加工,工序的加工时间随机床的性能不同而变化。调度目标是为每道工序选择最合适的机器、确定每台机器上各工件工序的最佳加工挨次及开工时间，使系统的某些性能指标达到最优（如生产周期最小、交货期满意度最高、生产成本最小等）。此外,在加工过程中还需满意如下约束条件：＝１\＊GＢ2⑴同一时刻同一台机器只能加工一个零件。=2\＊GＢ2⑵每个工件在某一时刻只能在一台机器上加工，不能中途中断每一个操作。=３\*GB2⑶同一工件的工序之间有先后约束，不同工件的工序之间没有先后约束。＝４＼＊GB2⑷不同工件具有相同的优先级。１.２数学模型在以往讨论中,生产周期、机床利用率等基于性能的指标受到了学者们的普遍关注,而一些基于代价的指标（如交货期满意度、生产成本等）却很少受到关注。然而这类指标对企业的管理决策又是至关重要的。因此，本文从生产实际动身,分别从生产周期、交货期满意度、生产成本及机床利用率等多个方面建立优化目标。生产周期用工件的最大完成时间(h）度量;交货期满意度用拖期惩罚(元）度量；由于作业车间调度问题未涉及到工件的原材料选择等环节，因此生产成本采纳由工艺路线不同而造成的加工成本(元）度量；机床利用率用机床最大负荷(h）和机床总负荷（h）度量.建立多目标整数规划模型如下:=1\＊GB2⑴=２＼*ＧB2⑵＝3\*GＢ2⑶＝４＼*GB2⑷=5\*GB２⑸＝６\＊ＧＢ2⑹式中:—待加工工件种类—机床数量—第类工件工序数量—第类工件的完工时间—第类工件的延误时间—第类工件的拖期惩罚系数—第类工件的交货期-单件第类工件第道工序在机床上加工所需时间—决策变量,时第类工件第道工序在机床上加工,时，表示未选中-单位工作时间机床所需费用—单位闲置时间机床所需费用-调度方案决定的最大完成时间2。ＰMOPＳO算法目前,多目标优化算法通常采纳“Ｐareｔo支配”准则对群体进行排序。然而，“Ｐarｅto支配”是一种较强的排序关系,对于目标数量较多的高维多目标优化问题,它将使群体产生大量的非劣解，难以从中进行选择操作,并可能导致算法消灭停滞现象。因此，在本文提出的PMＯPSＯ算法中,将决策者的偏好信息与“Paｒeto支配”相结合，定义了一种较弱的“偏好优于关系"，用于对群体进行排序并生成偏好解集。以往的算法通常采纳精确的目标向量值、目标权重值、多目标决策协调模型来表示偏好信息。采纳精确数值表示的偏好信息引导算法搜寻方向,会造成算法搜寻区域过于狭小。因此，不但使算法易于收敛到局部极值，形成早熟现象;而且，搜寻区域过于狭小很可能漏掉一些更让决策者满意的折中解。同时,由于在问题求解以前很难精准估量各目标取值范围，因此往往造成表示偏好信息的数值取值不够合理，使得算法的搜寻区域偏离了决策者真正感爱好的区域,从而无法求得满意的解.为了得到满意的结果,往往需要取不同的偏好信息数值进行多次试验.与以往的算法不同,本文不再采纳精确的数值来表示偏好信息，而是采纳目标间重要关系、各目标权重值的大致范围、或各目标大致取值范围形式表示。这样，不但便于决策者给定偏好信息,而且还可以依据问题本身或个人的需要来调整搜寻区域的大小。由于偏好信息不再采纳精确数值的表示方法,因此以往的用于精确数值偏好信息处理方法就很难对本文引入的偏好信息进行处理。因此,本文提出一种模拟人类社会组织投票选举产生“领导集体”的偏好信息处理方法,通过群体对Ｐaｒeto非劣解进行投票表决，从而产生偏好解集,并将偏好解集作为群体的“领导集体”对群体搜寻过程进行引导,使群体朝着决策者感爱好的区域进行搜寻，提高算法的搜寻效率，并使求解结果集中在偏好区域内，便于最终决策。该方法不但直观、简洁易行,而且不需设置过多参数.2．1基本定义本文将偏好信息引入“Paｒeｔｏ准则”，提出了一种较弱的“偏好优于关系”用于对种群排序产生偏好解集，分别对“偏好优于关系”和“偏好解集”定义如下：定义1:偏好优于关系为了不失一般性，以一个n个决策变量参数、k个目标函数和ｍ个约束条件的最小化多目标问题为例.设决策向量a、b(为可行解集）是ｎ维的可行解，其对应的k维的目标函数分别为和.引入偏好函数，表示在偏好信息环境下一个解优于其它非劣解的可信度。则ａ偏好优于b需满意以下充分条件：=1\＊GB3①aPareｔo优于b＝2\＊GB3②ａPａrｅtｏ无差别于b,并且ａ的偏好函数值大于b的偏好函数值。以上两个条件可表达如下：，定义2:偏好解集应用决策者的偏好信息在非劣解集中选取的解为偏好解,由偏好解组成的集合称为偏好解集。2．２偏好信息的处理人类社会是由各种各样的组织构成的,各组织中普遍存在领导机构，通过不断将更优秀个体补充到领导机构，对领导成员进行优胜劣汰,并由领导机构对组织进行领导，组织可以由小变大、由弱变强,像一个生物有机体一样不断的进展变化。领导机构通常不是单个个体,而是由多个优秀个体组成的一个小群体，从这个角度分析，社会组织的进展过程与多目标优化算法的搜寻过程极其相像。因此，我们可以模拟社会组织的进展过程进一步完善多目标优化算法的搜寻过程。目前,投票选举已经成为最常用的领导机构产生方法，该方法简洁易行、便于操作，因此被全世界众多组织所采纳。在选举过程中,通常要考察被选举人的多方面条件，比如才能、品德、学历、年龄、身体健康状况等。如果假设组织中全部成员都具有被选举权，并采纳“Paｒeｔｏ准则"对被选举人进行评判和比较,将优胜者补充到领导机构，由于考察条件过多,则会产生众多的优胜者，甚至全部成员都是优胜者，从而造成无法产生领导群体，组织机构混乱，组织无法正常运转。因此,通常人们在对被选举者评判过程中采纳一些为人们普遍认可的隐含的准则,例如可依据“品德和才能作为重要考察条件,年龄在肯定范围内，学历和身体健康状况为参考条件”进行评判。本质上说，这样的准则体现了选举人的偏好,是一种选举人普遍认可的隐含的偏好信息.并且，这样的偏好信息通常是以特性间重要关系或特性值大致取值范围形式表述的,也与本文提出的偏好信息表示方法极其相像。为了保证选举的公正和有效,避开个人的偏见，普遍采纳群体投票表决的方式。在投票过程中，存在众多选举人，每个选举人评判准则都和隐含的偏好信息相全都，同时又保持个体差异，这样被选举者得票数量越多,则他优于其他被选举者的可信度就越高.因此，投票选举过程其实就是采纳偏好信息构造“偏好优于关系"对群体进行排序的过程。因此，本文模拟人类社会组织“投票选举”产生领导集体的方式来处理偏好信息，其过程如下：种群的初始化及偏好信息的预处理与以往采纳精确数值对偏好信息进行表示不同，本文采纳以下3种形式对偏好信息进行表示，分别为:＝1＼＊ＧB2⑴各目标间重要关系;＝2＼*GＢ2⑵各目标权重值大致取值范围；=３\*GＢ2⑶各目标值大致取值范围；或以上3种形式的综合表示方式。这样，不但便于决策者给定偏好信息,而且还可以通过调整数值取值范围掌握算法搜寻区域的大小.在适当提高算法的效率的同时，又不会造成算法搜寻区域过于狭小。对于采纳各目标取值范围表示的偏好信息,可以在非劣解评价函数中引入偏好信息进行处理。而对于采纳各目标重要关系或各目标权重值大致范围表示的偏好信息,为了保证通过选举产生的偏好解集更加有效，需要对偏好信息进行预处理。以一个最小化4目标问题为例，采纳综合的方式给出偏好信息为“目标1、2重要目标，目标３、４为参考目标,目标１比目标2更重要，而且目标１的权重取值在0．4至0．6之间，目标3的取值最好小于１００"。则在粒子种群的初始化过程中，除了随机生成各粒子初始编码外，同时对每个粒子随机生成对应各目标的权重系数，使各权重系数与决策者偏好信息相全都,并且其和为１.随机生成任意粒子的各指标权重系数、、、,使得，并且、、。采纳上述方法，可以在与偏好信息相全都的情况下，保证各粒子对偏好解存在不同的衡量标准,保证了粒子间的差异性。通过群体投票,保证偏好解集的有效性,避开了因采纳单个目标权重值造成评价的偏见。经初选，生成候选解集为了保存计算过程中的候选解，需设置一个外部存档.在每一代计算过程中，首先将上一代选举产生的偏好解集复制到外部存档中。计算过程中,对各粒子进行解码并计算各目标值，按Pａreto支配关系，将各粒子与外部存档中的解两两比较。若该粒子与各解相比均不Paｒeto受控，则将该粒子信息保存到外部存档中，即该粒子取得了“候选资格”，成为一个候选解.若该粒子Ｐaｒetｏ优于外部存档中某个候选解,则取消该解的“候选资格”，即从外部存档中删除该候选解。通过上述步骤,即可得到一个包含多个候选解的候选解集。投票选举为了保证偏好解的多样性，我们在偏好信息预处理过程中,同样保持了各目标权重系数的多样性。这就造成不同的粒子具有不同的偏好解选取标准,即在同一个候选解集中，不同的粒子选取偏好解也可能不同。为了在上述情况下，从候选解集中选取出令决策者满意的偏好解集，我们采纳一种模拟人类社会组织“投票选举”的处理方法。“投票选举"是人类社会组织产生领导机构普遍采纳的方法。在选举过程中，虽然每个投票者对候选人的评判标准不完全相同,但通过投票的方式总能产生令人满意的领导机构，该方法简洁而有效,因此已成为一种最普遍的领导机构产生方法。同时,也为本文的问题供应了一种简洁有效的处理方法，简略过程如下：在投票过程中，每个粒子都拥有相同的投票机会,本文规定每个粒子只能将选票投给一个自己认为最优的候选解，而且必须投给一个候选解。在粒子投票时，必须计算粒子对各候选解的偏好程度，本文采纳投影寻踪的方法来计算粒子对候选解的偏好程度。如粒子对候选解偏好程度可记为；其中为候选解的第个指标值;当第个目标存在决策者预设的取值范围时，为第个指标的预设最大取值；否则，为外部存档中全部解的第个指标最大值;为外部存档中全部候选解第个指标值最小值。当全部粒子投票完毕时,统计各候选解所得票数。候选解的得票数越多，则它在偏好信息域下，优于其它候选解的可信度也就越高.因此,我们将各候选解所得票数作为他们的偏好函数值，并依据偏好函数值的大小对候选解排序，偏好函数值越大的候选解的优先级就越高,偏好函数值越小的优先级就越低。4）生成偏好解集依据候选解的优先级，由高到低选择肯定数量（按全局存档可存储偏好解数量确定）的候选解，作为偏好解集。将它们存入全局存档，他们将作为算法的本次迭代计算全局最优位置，起到领导机构的作用，引导整个种群进化。5）由偏好解集引导种群进化为了使算法朝着决策者感爱好的方向搜寻，必须将偏好解集作为全局最优位置，从而引导算法的搜寻过程。为了在保证算法收敛情况下,同时避开算法早熟，本文采纳一种最优位置混合选取策略.首先推断粒子前代是否产生过偏好解,若产生过,则在全局存档信息中进行查找，若未被替代则选择该偏好解为全局最优位置；若粒子未产生过偏好解或已被替代则选择收到该粒子投票的偏好解为全局最优解.采纳上述混合选取策略，既可保证偏好解的特征依据优先级的凹凸以不同几率的遗传给下一代,引导算法朝着决策者感爱好方向搜寻,保证算法收敛，同时又可避开算法早熟。２．３编码与解码与文献[1、2]相同,本文采纳基于工序的编码方法。由于存在工艺路线柔性，同一道工序可由不同机床完成，因此解码时必须为每道工序分派适当的机床。拖期惩罚通常是作业车间调度首先要考虑的指标，因此本文采纳的分派规章为优先选择最早完工时间的机床.即对于一道工序,计算该工序全部可加工机床的完工时间，并选取完工时间最早的机床。２。4粒子速度和位置为求解本文的问题，对文献［1４］中的粒子速度和位置表达式进行改进如下：=７\*GB２⑺=8\＊ＧB2⑻其中，为第代时粒子中第工件的第道工序在编码中位置。为第代时工件的第道工序所在粒子局部最优解编码的位置,局部最优解可从粒子的局部存档中选取。表示第代时工件的第道工序所在全局最优解编码中的位置，全局最优解可按2．2节的规章从全局存档中选取。为第代时粒子中第工件的第道工序所在编码中一个随机位置。、和为0、1整数，分别受、和影响而随机产生.2．5ＰMOPＳO算法流程算法简略步骤如下:＝1\*GＢ２⑴初始化掌握参数：种群规模大小P，最大迭代代数,候选解集存档规模大小，偏好解集存档规模大小,算法掌握参数、和,偏好信息(按2.２节的３种形式或3种形式的综合方式给定)=2＼＊GＢ2⑵,随机产生P个粒子编码，并对偏好信息进行预处理,依据偏好信息随机产生各粒子的目标权重值=3＼＊GＢ2⑶对各粒子进行解码，并计算各子目标值=4＼＊GB2⑷将上一代的偏好解拷贝到候选解存档中，并采纳Parｅtｏ准则与各粒子进行比对,生成候选解集=5＼＊GB2⑸计算各粒子对各候选解的偏好程度，各粒子对自己认为最优的候选解进行投票=6＼＊ＧB2⑹统计各候选解得票数量，并按得票数量由高到低对候选解排序＝７＼＊GＢ2⑺按优先级由高到低选取肯定数量(按全局存档规模确定)的候选解复制到全局存档中=8\＊ＧB2⑻依２.2节规章选取全局最优位置，并计算粒子速度,更新粒子位置=9\*GＢ2⑼，如果达到规定循环代数，则停止计算；否则,转至第＝3\*ＧB２⑶步=10\*GB２⑽输出偏好解集存档中得票数不为0的偏好解,为算法最终搜寻结果3.仿真试验算法运行环境为Peｎｔium3、CPU主频8５0ＭＨｚ、256MB内存、ＷiｎｄｏwｓＸP操作系统，并采纳jａｖａ语言编写。为验证本文算法的性能，本文分别采纳3组仿真试验验证了算法的性能：=１\*GＢ２⑴对文献［15］的３个标准测试用例（８×8、１0×10、１5×10）进行求解，并与一些典型算法求解结果进行对比,初步验证算法的性能;=２\＊GB２⑵对文献［1、2］中的6目标的6×6×1０(6个工件６台机床，每个工件有10道工序）的高纬多目标优化调度问题进行求解,并与原文进行比对，进一步验证算法求解高纬多目标调度问题的性能。=3\＊ＧB２⑶将文献[16]中10个典型测试用例改进为５目标优化调度问题，将本文算法所求结果与典型多目标优化算法所求结果进行比对，进一步验证本文算法的性能。3。１仿真试验1为了验证PＭOPSO算法的性能,我们对文献[1５]中的3个标准测试用例(8×8、１０×10、15×１０)进行求解,并把结果与一些典型的优化算法求解结果进行对比，如表１所示。由于篇幅限制,仅将１5×10问题所求两个结果采纳甘特图形式表示，如图1和图２所示（方框中数字表示工件和工序)。进行比较的优化算法包括：混合粒子群算法(PａｒticｌeＳwaｒmOptimｉｚationａndSiｍｕlａtｅｄＡnｎeａlinｇＡlgoritｈｍ，PSO+SA)［15]、结合禁忌搜寻的混合粒子群算法（PartiｃｌeSｗarｍＯptｉmizａtｉonｗithＴabuＳeaｒch，PSO+TS)[１6]、改进的遗传算法(ImproｖeｄGｅｎetｉcＡlgorｉｔｈm，IGA）［17].ＰMOPSO算法的主要参数:种群数取1０0,最大循环代数取2０0，常数、、分别取０。2、０。4、0．5,偏好信息为“各目标按重要程度由高到低依次为：生产周期、机床最大负荷、机床总负荷”。表１中各符号所代表的目标分别为:Ａ—生产周期,B—机床最大负荷，Ｃ—机床总负荷.表１.求解结果比较算法问题(Ａ／B／Ｃ)8×810×1０1５×１０PＳO+ＴS１4/1２／７７7／6/431１/１1／９3PＳO+SＡ15/12/7５７/6/4412／１１/91IGA１4/１2/７77/6／４312/11/９1PＭOPＳＯ１4／1２/７７7/5/4312/11/91１５/1２/7５7/6/4２1１/１1/９216/11/7７8/5/42图1.15×１０问题调度甘特图（Ａ=１1，Ｂ＝１1,C=9２）图2。15×1０问题调度甘特图（Ａ=１２,Ｂ=11，Ｃ=9１）观察表1、图１、图２，可知：PMOPSO算法所求结果的各项目标均达到或接近几种典型算法所求结果最优值,且没有未消灭受控解。并且某些求解结果还略优于对比算法的所求结果.可见,所求结果是比较令人满意的。而且,PＭOPSO算法是多目标优化算法，一次求解可得到多个调度方案，可以为决策者供应了多样性的选择。因此，通过该仿真试验，我们就初步验证了该算法求解多目标柔性作业车间调度问题的可行性和有效性.３.2仿真试验2文献［1、2］从实际生产中提取了一个6目标柔性作业车间调度问题,作者吴秀丽采纳了分步策略进行求解,首先采纳一种混合遗传算法对问题进行求解（种群数取1０0,最大循环次数取300０），得到了一个包含20个非劣解的均匀分布在整个Ｐareto曲面的解集，然后采纳层次分析模糊综合评判从2０个非劣解中选出一个最终解决方案。为了验证ＰＭOＰSO算法求解高纬多目标优化调度问题的性能，对该６目标高纬多目标优化调度问题进行求解,并与文献［1、2］结果进行对比。采纳PMＯPSO算法对问题求解，算法的主要参数:种群数取10０,最大循环代数取2００0，常数、、分别取０。2、０。4、0．5，偏好信息为“生产周期、生产成本和最大提前/拖后时间为格外重要目标,机床最大负荷和机床总负荷为重要目标，在制品库存成本为次要目标"。算法运算过程中，所用各目标表达式及问题的原始数据均与文献［1、２］相同,可参阅文献[1、2］相关表达式及表格。PMOPＳＯ算法结果包括6个偏好解的解集,如表2所示。将文献[１、2］中包含2０个非劣解的Pａreto解集与表2对比,发现其中存在11个的受控解，将剩余的９个非受控解列表，如表3所示。将表3与表2进行对比,如表4所示。表２、表３、表4中各符号所代表的目标分别为:Ａ—生产周期(h），B—生产成本（元),C—最大提前/拖后（ｈ），D—机床总负荷(h），E—机床最大负荷（h），F—在制品库存成本(元)。表２．ＰMOPSＯ求解结果序号指标ＡＢＣＤＥＦ13017８731１27515３81２5２3１08185１6276１56７9２３299７８319２79154８１３943067７57１12861５2９１3353027７46１22861５２5145６３0６７639１7２8０15１２２0１表3。文献［１、２］的非受控解序号指标ABCＤEF１33581７２７2２7017141532３0０8067102７017521８5３３３１８9９4８63181714５9432８87７2932９2169４６9５3058００5５12８4１69811863０６８53343２９５１6９210２７29８8０5０11296１７381718299８1８５44267１７251４６９2998２80１６2８017391１0表4。表2、表３结果对比表3表2受控目标数量非受控目标项差值11５D5２3５D９32５Ｆ33４25Ｆ23515Ｆ７６25A4735Ａ18３５Ｄ１293５F29图3。调度甘特图观察表２、表３可知:PMOPＳO算法所求结果包括6个偏好解,将这6个偏好解与文献［1、2］中包括２0个解的Paｒeto解集进行对比，发现２０个解中有1１个解为受控解，而6个偏好解中未发现受控解.表4列出了表3中的解与表2中适当解的比较结果，观察该表可知:表3的9个非受控解，与表２相比虽然未受控，但是它们均在５个目标劣于表2中的解,只是在单个目标上略微优于表2中对应解。说明，这9个非受控解主要集中于Pareｔｏ曲面上某个目标的极值点四周，而不在决策者的偏好区域，并不是令人满意的折中解。与文献[1、2］的算法相比,PMOPSＯ算法不但搜寻效率更高,所得结果更加令人满意,而且算法得到解的数量较少，避开了决策者要在众多非劣解中选取满意解.文献［1、2］采纳层次分析模糊综合评判的方法从20个非劣解选择表３中第5个解作为最优调度方案,我们可将表2中第1个解作为最终调度方案,调度甘特图如图3所示(方框数字表示工件和工序）。该方案在生产周期、生产成本、最大提前／拖后时间、机床最大负荷、机床总负荷等五个调度指标上均明显优于表5的第5个解,只是在制品库存费用为125(元）,比文献［1、2］的调度方案多7(元）。不难看出，本文的方案更加令人满意。3.３仿真试验３为了进一步验证PMOＰＳO算法的性能，我们对典型的ＭK01－MＫ10的1０个测试用例进行改进，将它们改为5目标柔性作业车间调度问题。其中,工件的交货期及拖期惩罚系数如表5所示，机床的工作及空闲费率如表６所示（工艺路线等数据请参阅相关文献)。采纳ＰMOＰＳＯ算法求解，并与两种典型的多目标优化算法（MＯGA及NSGA算法）所求结果进行比对。3种算法的种群数均取１00，最大循环代数均取２0０0；PMOPＳO算法常数、、分别取0.２、0．４、０。5,偏好信息为“拖期惩罚、生产成本和生产周期为重要目标，并且其重要程度依次为拖期惩罚、生产成本、生产周期;机床最大负荷、机床总负荷为次要目标"。对3种算法结果进行比较,如表7所示.为了说明不同算法结果的质量，我们以ＭK10问题为例,将不同算法求解的结果分别列表表示，表８表示PMOPＳＯ算法的偏好解,表9表示NSＧA算法结果中的非受控解，表10表示ＭＯGA算法结果中的非受控解。表8、表９、表10中各符号所代表的目标分别为:A-拖期惩罚（元),B-生产成本（元),Ｃ-生产周期（h)，D—机床最大负荷（h),E—机床总负荷(h).表５．交货期及拖期惩罚系数序号DT序号ＤT12０11１17012242１２1６0１３301１316０２44011４１9０1５4８11521016601162301７８0２１7320２８881１８4２019100119４50３1０13０220５003表6。机床的工作及空闲费率序号VPＳP序号ＶＰSＰ1219１１1２4110１０13８1１1９１46１12315７１1351651148178215４１８5１１6表7．结果的比较问题规模MＯGANSGAPMＯPSO非劣解受控解时间（S）非劣解受控解时间(S)偏好解受控解时间(S）MＫ０110×62032１220４2203023４ＭK０210×62０１141０2013３９85043２ＭK0315×8２0１210４2201３１0２25010７8ＭＫ04１5×８201072320127545０7８5MK0515×420584220４83440８７6MK０610×１５２068３２2０７841５088４ＭK0７2０×５２０４８54２0３843408７4ＭＫ０82０×102０9114720８113230１1８7ＭK092０×1020１01354２0111３425０1３95MＫ１020×15201２１541201３153７４0１596表8．PMOPSO求解MK１0问题的解集序号指标ＡBＣDE１2389１５1342４1２22２110２2３09１52152３5223211７３2２5915５４１24222２21５2４２47７1521０24８２34２097表9．NSGA求解MＫ１0问题的非受控解序号指标ＡBＣＤE1２87５15702２6３2２１21２122７８２1596２27222０２11５３２６０215７４52６3２１9215５4260915566２５9２２92107５２６５４15８８626422０2１216２5２51５６84２５7２3520９57２５７11５368253230２087表10.ＭOGA求解MK１0问题的非受控解序号指标ＡＢＣDＥ1275215４2526０22９２０８１２２６９５155262592２７20８3３276２155７９25９220211342８9515572２7２2422０8052667155８０2602422０7６6２6３８1５3２22602２7２10３7２７5０15４88２582５1２09０82７53153812６0２４３2079表7列出了3种算法在取相同种群数量、相同最大循环代数情况下对10个典型问题的求解结果。观察该表不难看出,与ＰMOPＳO算法相比,MＯGA算法和NSＧA算法的解集中均消灭了受控解,而PMＯPＳO算法的偏好解集中却未消灭受控解.观察表８、9、10可知,虽然ＭOGA算法和ＮＳＧA算法的结果中也包含肯定数量的非受控解（如表9、１0所示)，但是与PMOPSO算法的偏好解集相比，这些非受控解均在4项指标上明显劣于ＰMＯPSO算法的结果，而只是在某个指标上略微优于PMOPＳO算法的结果（受篇幅限制，不再采纳表４的形式列表表示)。不难看出，与ＭOGA算法和ＮＳＧA算法相比，PＭＯPSＯ算法不但搜寻效率更高，而且得到的结果也更令人满意。同时，PMOPＳO算法的偏好解集包含解的数量较少,更便于决策者做出最终的决策。4。结论针对高纬多目标柔性作业车间调度问题,提出了一种基于偏好的多目标粒子群算法(PＭOPSO）。通过偏好信息引导算法的搜寻过程，使算法朝着决策者感爱好的区域搜寻，缩小了算法的搜寻空间,提高了算法的效率。而且,使最终结果集中在决策者感爱好的区域,削减了非劣解的数量，避开了决策者要在众多非劣解中做出困难的选择。在算法中，不再采纳精确数值表示偏好信息,而是提出了一种采纳目标间重要关系、目标权重大致取值范围和各目标大致取值范围偏好信息表示方法，采纳该方法,不但便于决策者给定偏好信息，而且还可依据决策者或问题本身的需要，对搜寻区域的范围进行适当调整.针对偏好信息的特点,提出了一种仿照人类社会组织“投票选举”产生领导机构的偏好信息处理方法，该方法不但直观、而且简洁易行.最后，通过仿真实例验证了算法的可行性和有效性.参考文献:[1］吴秀丽，孙树栋，余建军，等。多目标柔性作业车间调度优化讨论[Ｊ].计算机集成制造系统,2006，1２（５):７３１－736。［2］吴秀丽，孙树栋，余建军，等.多目标柔性作业车间调度决策精选机制讨论［J］．中国机械工程，20０7,18(2)：1６１-165.［3］鞠全勇,朱剑英.多目标批量生产柔性作业车间优化调度［J]．机械工程学报，2007，4３（８)：１48—1５４．[4]DeｍｉngＬei。AParetoarｃhｉｖeparticleｓwarｍoｐtｉｍizａtioｎｆormuｌti－obｊectiveｊobshopscheｄuling［J］。CｏmpｕtｅrsaｎｄIｎdustrialEnｇｉnｅｅring，２0０8，54（４):９6０－97１。[5］FｏｎｓeｃaＣａrｌosM，FleｍｉngＰｅterJ.Ｍｕltiobｊeｃｔｉvegeｎeｔicａlｇｏriｔｈmsmadeeasy：Selｅcｔｉｏn，sｈarｉnｇanｄmatiｎｇrestｒictｉon［Ｃ］／/Proｃeedｉｎgｓｏｆthe１sｔIEE／IEEEInｔeｒnaｔｉonａｌＣonferenｃeonGｅneｔiｃAlgｏritｈmｓinEｎgineeｒｉnｇSystems：InｎovaｔｉonsaｎdApｐｌｉcａtioｎs.Shｅffiｅlｄ，Enｇｌａnd，1