第30卷第3期2006年6月南京理工大学学报
Journal of Nanjing U niversity of Science and Technology V o.l 30N o .3June 2006
收稿日期:2005-05-10 修回日期:2006-04-05
基金项目:国家/8630计划(2003AA 41302,2003AA 4Z3370)
作者简介:卫忠(1971-),男,吉林扶余人,博士生,主要研究方向:C I M S 、供应链优化、演化计算等,E -m a i:l
W e izhong @hit .edu .cn 。
基于演化多目标算法的混合流水作业调度优化
卫 忠,徐晓飞,邓胜春
(哈尔滨工业大学计算机科学与工程学院,黑龙江哈尔滨150001)
摘 要:针对供应链网络优化领域中的混合流水作业调度问题提出了一种新的多目标演化优化算法。给出了这类问题的通用优化模型,在此基础上,提出了基于流程的矩阵基因编码方案,动态适应度分配机制,并引入小生境保优策略构造了算法过程,利用收敛进程参数分析了算法的收敛性能。性能分析和算例实验表明算法对于高维多目标优化问题是有效的,且能够以较快的速度收敛。关键词:混合流水作业调度;多目标优化;演化计算;适应度分配机制
中图分类号:TP 393.07 文献标识码:A 文章编号:1005-9830(2006)03-0327-05
Hybri d F l ow Shop Sc heduli ng Proble m Base d on Evolutionary
M ult-i objective A lgorit h m
WE I Zhong ,XU X i ao -fe,i DENG Sheng -chun
(Schoo l o f Co mpu ter Science and Techno logy ,H ar b i n Institute of Techno l o gy ,H arb i n 150001,China)Abst ract :A ne w evo l u ti o nary al g orith m for so l v ing m u lt-i ob jective hybrid flo w shop scheduling proble m (H FSP)w hich is an i m portant top i c in supp l y cha i n net w or k opti m ization is presented.The genera lm odel for the H FSP is proposed ,and a m atrix gene encoding m ethod and a sort of fit n ess as -si g n m ent strategy w hich can approach the opti m um so lutions w ith dyna m ic w eighti n g are d iscussed .The a l g orithm process is presented by using e litist strategy .The conver gent perfor m ance of the algo -rit h m is analyzed by co m puti n g the prog ress m easure m en.t The perfor m ance analysis and t h e exper-i m ental resu lts sho w that the a l g orithm is effecti v e for h i g h -di m ensionalm ult-i ob jecti v e prob le m s and can conver ge to satisfactory so lutions at a h i g h speed .
K ey w ords :hybri d flo w shop schedu ling ;m ult-i ob jecti v e opti m izati o n ;evo l u ti o nary co m puti n g ;fi -t ness assignm en t
混合流水作业调度问题(H ybri d Flo w Shop Schedu ling Proble m,H FSP)是典型流水作业问题
的一种推广,它产生于复杂制造流程的生产计划优化。目前,针对H FSP 的研究已成为供应链网
南京理工大学学报第30卷第3期
络优化领域中的重要研究热点。B rah与H un-suchen[1]提出了小规模H FSP问题的一种分支定界算法,Brah和Loo[2]给出了求解HFSP的启发式方法,X iao等人[3]采用了遗传算法求解该问题。传统H FSP是一个单目标问题。但实际生产环境中的计划规划大多需要同时考虑多个冲突的目标,所以,有必要发展基于多目标规划理论的HFSP求解方法。在传统多目标优化理论的基础上,目前已发展了大量的现代启发式方法,其中演化多目标优化方法(Evo l u tionary M u lt-i Ob jecti v e Opti m ization,E MOO)得到了广泛的重视。Scha-f fer[4]实现了基于向量评价的遗传算法(VEGA),该方法通过比较向量形式表示的目标值来确定个体适应度,使用q次循环(q为给定问题目标数量)产生下一代种群,每循环一次用一个目标选出1/q部分的子种群。R ichar dson等人[5]指出,在VEGA中,实质上其个体适应度取决于目标权重的线性组合函数,这种基于向量评价的适应度分配机制导致了算法对非凸空间搜索的局限。Fonseca等人[6]提出的MOGA与Sri n i v as等人[7]实现的NSGA采用了基于Pareto优先关系排序的适应度分配策略,但在具有多个冲突目标的高维问题中,Pareto集会很大,可能随着问题规模增加而呈指数增长,并且因为Pareto交换面(Trade-o ff Surface)过长而不能得到满意解[8]。Ishibuchi等人[9,10]提出一种基于随机权重求和的适应度分配策略,这种方法表现出优于VEGA与MOGA的结果。但是该方法在应用随机选择获得平均方向压力的同时,导致了在处理高维问题时的低效率。为了避免这一问题,可以设计针对特定方向的可变压力调整策略,其实现关键是基于多目标演化技术的动态适应度评价。为了有效提高算法在HFSP高维超曲面上的快速收敛能力,本文提出了基于选择性权重的适应度函数评价方法,给出了基于该方法的演化多目标算法。并通过实验数据对算法进行性能分析和给出结论。
1多目标混合流水作业问题描述
设T={T1,T2,,,T n}表示容量为n的任务集合,加工环境有m个阶段,M j={M j1,M j2,,,M jl}表示第j阶段上l台机器的机器集。a ijk表示第i个任务在第j阶段的第k台机器上的一个操作,操作a ijk有属性集合{(a1ijk,b1ijk),(a2ijk,b2ijk),,,(a q ijk,b q ijk)},a q ijk表示操作在目标q下的静态指标,b q ijk表示由于操作等待而带来的动态指标,如在成本目标下由于工期等待而产生的单位托期惩罚成本等。w ijk 表示操作在机器M jk占用时的等待时间,
w i=E m j=1E l k=1w ijk即为任务T i的总加工等待时间。s ijk表示操作a ijk的开始时间,e ijk表示操作a ijk的结束时间,v jko表示机器M jk上的约束指标,机器M jk上有约束集合S jk={f(v jko)\0,o=1,,,O},在各项约束指标上,操作a ijk引起的结果集合为S c j k= {f(v jko)[0},则一个多目标H FSP可以描述为:
m i n z q=E n
i=1
E m
j=1
E l
k=1
(a q ijk+w ijk b q ijk)(1)
s..t b q ijk=0,z q与w ijk无关(2)
e ij[s i(j+1)(3) S jk H S c jk=ù(4) s ijk[e ijk(5)
以上模型中都有i=1,,,n;j=1,,,m;k= 1,,,l;q=1,,,Q。本文中所有目标函数取最小值,对于问题中的最大化指标,则通过相应的目标函数设计将其转化为最小指标,以便于目标值比较和适应度分配权重计算。根据问题描述,HFSP 上的一个调度可以表示为操作a ijk的一个排列J。
定义1如果J中所有操作a ijk满足次序性约束公式(3)并且同时满足合法性约束公式(4),则称J是H FSP的一个可行调度,记为J^。
2多目标HFSP调度的演化算法
2.1基因编码
对于上述HFSP调度问题,采用如下矩阵编码
A m@n=
a11,a1n
s s
a m1,a
mn
(6)
式中,a ij为区间(1,l)上的一个整数,表示任务i在阶段j的第k个节点上完成。基于矩阵编码构造的染色体可以表示为一个长度为(n@m+m-1)的字符串,按照矩阵各行顺序排列,不同行之间用符号/*0隔开,则设V表示种群中的染色体,有
V=|a11,a12,,,a1n,*,a21,a22,,,a2n,*,
,,*,a m1,a m2,,,a mn|(7)
每个染色体V对应一个a ijk的排列J,为保证J=J^,定义了预备算法。
328
总第148期卫 忠 徐晓飞 邓胜春 基于演化多目标算法的混合流水作业调度优化
预备算法PA (J ^):
(1)令j =1,输入V,建立初始操作序列
表A jk ;
(2)令i =1,k =1,计算e i(j -1)k (e i(j -1)k =0,j =1),基于FI FO 方式,确定操作序列,即在每个节点,按照任务前一阶段的完成时间e i(j -1)k 排定顺序,前阶段先完成的先加工,若e i(j -1)k 相等且a ij 相等,则随机确定加工顺序,计算w ijk ,s ijk =e i(j -1)k +w ijk ,更新A jk ;
(3)计算f (v jko ),若至少存在一个o ,o =1,2,,,O,使f (v jko )\0,则构造阶段j 内所有可实现a ij 的机器集合{k *
},随机选择,用a ijk *替换a ijk ,更新A jk ,生成V *
,否则V *
=V ;,i =i +1,k =k +1,重复直到i =n,k =l ;
(4)若j ,结束。 定理1 对于算法PA (J ^)输出的染色体V * 对应的调度J,必有J =J ^。 证明 (1)次序约束满足性 算法步骤(2)中,操作开始时间s ijk =e i(j -1)k +w ijk ,因为w ijk \0,则有s ijk \e i(j -1)k ,即等价于e ij [s i(j +1),公式(3)得证; (2)合法约束满足性 设在阶段1有f(v 1ko )\0,V 被V * 替换,则算法步骤(3)循环后,必有f (v 1k *o )[0,随着阶段j 不断增大至算法结束j =m,则有f (v jk *o )[0,即对V * 中所有的a ijk *,都有S jk H S c jk =ù,公式(4)得证;对于V * 映射的操作排列J,由定义1,J 必是一个H FSP 上的可行调度,即J =J ^,命题得证。2.2 基于多目标的适应度分配 为了让算法的选择压力根据每一代Pareto 解的改善作出适当的调整,必须维持一个全局Pareto 解集,设为E (t),t 为进化代数,最大进化代数设为m ax _gen ,第t 代的Pareto 解集设为E cur r ent (t),对有Q 个目标的最小化问题,第q 个目标在E cu rren t (t)中的最小值u m i n (t)q 和最大值u max (t) q ,定义如下: u m in (t) q =m i n {f q (x ),u m in (t -1) q |x =1,2,,, p o p _size} (8) u max (t)q =m ax {f q (x ),u max (t -1)q |x =1,2,,, p o p _size}(9) u m in (t) q ,u max (t) q 每代都会更新,则第t 代中目标 q 的选择性权重系数w q 由下式确定: w c q = u max (t) q -u m in (t) q u max (t) q w q = w c q E Q q=1 (w c q ) t =1,2,,,m ax _gen (10) 种群中每个染色体V in d i 的适应度为: G (V ind i )= E Q q =1 w q u max (t) q -u m in (t) q z (t)q ind i =1,2,,,p op _si z e (11)这种分配模式与随机分配模式 [11] 相比,算法 假设存在所有目标值都最大的理想调度,与之最接近的染色体被赋予最大适应度,每代都会更新理想解,使得算法保持对理想解方向的可变选择压力,基于这种评价函数的算法可以称作动态权重演化算法(DWEA )。 2.3 保优策略 为了保证算法不遗失Pareto 解,引入小生境保优策略(E litist Strategy ),策略可以描述为:对每代执行进化过程后,评价新染色体,确定Pareto 解,将其与前代更新的Pareto 解暂定集合进行比较,有三种情况,如果集合中任何Pareto 解优于它,则跳过;如果它优于部分Pareto 解,则将其增加入集合,并将集合中被其优超的解删除;如果它是一个新的Pareto 解,不优于任何存在解,则增加入集合。定义best _size 为保优变量,算法每代只产生(p o p _size -best _size)个进化后代,从Pareto 解集合选取best _size 个解合并构成新种群。通过保优策略,能够让最优解始终参与进化,从而保证算法的收敛性。2.4 多目标HFSP 调度的演化算法过程 设t 表示当前进化代数,P (t)为当前代的种群,C (t)为产生的后代种群,E (t)为全局Pareto 解集,max _gen 为最大进化代数。则算法过程有: (1)初始化参数m ax _gen,pop _size ,best _size ; (2)令t =0,生成初始种群P (t);(3)应用多目标适应度函数评价P (t),确定全局Pareto 解集E (t); (4)采用轮盘方式从P (t)选出(pop _size -best _size)个染色体作为父代个体,执行进化操作,产生后代C (t); (5)更新全局Pareto 解集E (t); (6)应用多目标适应度函数评价C (t); (7)应用保优策略,在E (t)中随机选择best _size 个Pareto 解,合并C (t),得到P (t +1); (8)若t 329 南京理工大学学报第30卷第3期 2.5算法性能分析 在多目标优化问题中,能够尽快地收敛到全 局最终Pareto解集是衡量算法性能的重要指标, 为了度量算法的收敛速度,需要定义独立的评价 参数,V eldhu izen等人[12]给出了一种度量方法, 设最终全局Pareto解集为E tr u e,每一代Pareto解 集为E cu rren t(t),则算法相对收敛进程RP= l n G1/G t,G1,G t表示第一代和第t代的Pare to解 集E cu rren t(t)与E tr u e中一点的距离,文献中对双目 标问题给出了计算过程,但对于大多数实际工程 问题,并不知道最终Pareto解集E true,所以使用理 想点z*={z m in1,z m in2,,,z m in q}代替,则有 d A=E Q q=1(z A q-z m i n q)2,A=1,2,,,B(12) G t=E B A=1 d2A = E B A=1 E Q q=1 (z A q-z m in q)2 (13) 式中:d A表示一个Pareto解与理想解之间的距离,B为E current(t)中Pareto解的数量。 3实验结果 为验证算法在一般问题和高维问题中的性能,选取了模拟实际生产环境的两个测试问题,用MOGA[8]、随机权重算法[11](R W EA)、本文算法(D W EA)进行了比较实验,为保证多种平台的兼容性,所有算法都采用标准C实现。加工数据为任务数100,阶段数10,节点数50,第一个问题目标为最小完工时间与最小成本,算法参数为最大代数50,种群规模20,保优数量2,杂交概率0195,变异概率011,得到数据如图1和图2,对问题进行50代搜索后,算法RWEA和DWEA找到了全部Pareto解,MOGA找到了绝大部分最优解,在实验中,算法继续进化到57代找到全部解。图1反映了3种算法对最优解的压力趋势,可以看到,DWEA选择的子代较集中于E cu rr ent(t)周围,另外两种算法选择的子代较分散,在进化到20代时,DWEA已经找到了60%的解,R W EA为40%, MOGA为30%,在代与代之间的染色体选择上, D W E A表现出有选择性的趋向性反应,对最优解附近进行密集搜索,对于算例给定双目标问题,算法在较短的时间内得到了较多的Pareto解。 算例第二个问题取最小完工时间、最小成本、最大完工数量、最大质量满意度4个目标,算法参数为最大代数100,种群规模100,保优数量10,杂交概率0195,变异概率011,在同等数据条件下,每种算法各运行20次,采集实验数据按照215给出的方法分析算法收敛性能,结果如图3 (横坐标为进化代数,纵坐标为E current(t)与z*的距离d A)和图4 (纵坐标为RP值),可以看到, D W E A的收敛速度快于MOGA与R W EA 。 图1t=20时种群中P areto解分布图 图2t=50时种群中P areto解分布图 图3算法进化过程中与E tr ue 的距离 图4算法演化过程的R P值 330 总第148期卫忠徐晓飞邓胜春基于演化多目标算法的混合流水作业调度优化 实验数据表明,D W E A算法具有在进化过程中的显著趋向性特性,在q较小(q[3)时,寻优能力不劣于随机权重方法和基于Pareto排序的方法,在高维问题中,由于DWEA保持了对理想解方向的选择压力,使得算法具有快速收敛能力。 4结论 本文对于一类面向生产优化领域的多目标混合流水作业调度问题进行了研究,给出了该类问题的通用优化模型,并针对这一模型提出了一种多目标优化演化算法。这一算法结合了传统启发式方法,并通过选择性的适应度分配机制保持对Pareto边界的非均匀搜索压力,理论分析和实验数据表明,算法能够以较高的速度收敛到全局Pareto解,对于解决实际生产调度中的高维多目标优化问题具有一定的理论和实用价值。 参考文献: [1]Brah S A,H unsucker J L.B ranch and bound a l go- rith m f o r the flo w shop w ith mu lti ple processo rs[J]. European Journal o fO perati onal R esearch,1991,51: 88-99. [2]Brah S A,L oo L L.H euristi cs f o r scheduli ng i n a fl ow shop w ith m ultiple processors[J].European Journa l of O pera ti ona l R esearch,1999,113:113-122. [3]X iao W endong,H ao Pe ifeng,Zhang Sen,X u X i nhe. H ybr i d fl ow s hop schedu li ng us i ng genetic algorith m s [A].IEEE P roceeding o f3rdW or l d Congress on In- te lli gen t Contro l and Au t om ati on[C].H efe:i Instit ute o f E l ec trical and E l ectronics Eng i neers Inc,2000. 537-541. [4]Scha ffer J D.M u ltiple ob j ec tive opti m ization w ith vec- tor evalua ted geneti c a l gor ith m s[A].P roceed i ngs of the F irst Internationa l Con ference on G ene tic A l go- rith m s and T heir A pp licati on[C].H illsda l e:L aw- rence Er l bau m A ssoc i a tes,1985.93-100. [5]R ichardson J T,P a l m erM R,L iep i ns G,et a.l Som e gu i deli nes f o r geneti c a l go rith m s w ith pena lty functions [A].Proceed i ng s o f the Th ird Internati ona l Con f e r- ence on G enetic A l go rith m s[C].W ash i ng ton:M o r- g an K au f m ann Pub li shers,1989.191-197. [6]Fonseca C M,F le m i ng P J.G eneti c algo rith m s for mu-l ti objecti ve opti m ization:For mu lati on,d iscussion and genera li za tion[A].G enetic A lgo rith m s:P roceed i ngs of t he F ifth International Conference[C].San M a teo: M o rgan K au f m ann,1993.416-423. [7]Sr i n i vas N,D eb K.M u lt-i objective opti m isati on us i ng non-do m i nated so rting geneti c a l go rith m[J].Evo l u- ti onary Co m putation,1994,2(3):221-248. [8]Fonseca C M,F l em ing P J.A n overv i ew o f evo l u tion- ary a l gor ith m s i n mu lt-i ob j ective opti m iza ti on[J]. Evoluti onary Co m putation,1995,3(1):1-16. [9]Ishi buch iH,Y o s h i da T,M ura ta T.Ba lance bet ween genetic search and local search i n m e m e tic algorith m s for m ultiob j ec tive per m utation flo w shop scheduli ng [J].IEEE T rans on Evoluti onary Com putation, 2003,7(2):204-223. [10]Ishibuch iH,M ura ta T.A m ult-i ob j ec ti ve geneti c l o- cal sea rch algor it h m and its appli ca tion to flo w s hop schedu ling[J].IEEE T ransacti ons on System s, M an,and Cybernetics-P art C:A pp licati ons and R e- views,1998.28(3):392-403. [11]V e l dhu i zen V,L a m ont G B.Evoluti onary co m puta ti on and conve rgence t o a pareto front[A].L ate Break i ng Papers at t he G enetic P rogra m.ru i ng1998Con ference [C].Stan f o rd,San F ranc isco:Stanford U n i v ers it y Bookstore.1998.221-228. [12]V e l dhu i zen V,Dav i d A,L a m ont G B.M u lti objecti v e evo l utionary algor it h m s:analyzi ng the sta te-o-f t he-art [J].Evo luti ona ry Compu tati on,2000,8(2):125- 147. 331 多目标优化算法 ——11级计算一班 20113745 陆慧玲 近年来,多目标优化问题求解已成为演化计算的一个重要研究方向,而基于Pareto 最优概念的多目标演化算法则是当前演化计算的研究热点。多目标演化算法的研究目标是使算法种群快速收敛并均匀分布于问题的非劣最优域。 最优化问题是工程实践和科学研究中主要的问题形式之一，其中，仅有一个目标函数的最优化问题称为单目标优化问题，目标函数超过一个并且需要同时处理的最优化问题称为多目标优化问题(multiobjectiveoptimizationprob- lems，简称MOPs)。对于多目标优化问题，一个解对于某个目标来说可能是较好的，而对于其他目标来讲可能是较差的，因此，存在一个折衷解的集合，称为Pareto 最优解集(Pareto optimal set)或非支配解集(nondominated set)。起初，多目标优化问题往往通过加权等方式转化为单目标问题，然后用数学规划的方法来求解，每次只能得到一种权值情况下的最优解。同时，由于多目标优化问题的目标函数和约束函数可能是非线性、不可微或不连续的，传统的数学规划方法往往效率较低，且它们对于权重值或目标给定的次序较敏感。进化算法通过在代与代之间维持由潜在解组成的种群来实现全局搜索，这种从种群到种群的方法对于搜索多目标优化问题的Pareto 最优解集是很有用的。 第一代进化多目标优化算法以Goldberg 的建议为萌芽。1989 年，Goldberg 建议用非支配排序和小生境技术来解决多目标优化问题。非支配排序的过程为：对当前种群中的非支配个体分配等级1，并将其从竞争中移去；然后从当前种群中选出非支配个体，并对其分配等级2，该过程持续到种群中所有个体都分配到次序后结束。小生境技术用来保持种群多样性，防止早熟。Goldberg 虽然没有把他的思想具体实施到进化多目标优化中，但是其思想对以后的学者来说，具有启发意义。随后，一些学者基于这种思想提出了MOGA，NSGA 和NPGA。 从20 世纪末期开始，进化多目标优化领域的研究趋势发生了巨大的变化，l999 年，Zitzler 等人提出了SPEA。该方法使精英保留机制在进化多目标优化领域流行起来。第二代进化多目标优化算法的诞生就是以精英保留策略的引入为标志。在进化多目标优化领域，精英保留策略指的是采用一个外部种群(相对于原来个体种群而言)来保留非支配个体。(1)SPEA 和SPEA2 SPEA 是Zitzler 和Thiele 在1999 年提出来的算法。在该算法中，个体的适应度又称为Pareto 强度，非支配集中个体的适应度定义为其所支配的个体总数在群体中所占的比 MOGA i x 是第t 代种群中个体，其rank 值定义为： () (,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值（fitness value ）分配算法： 1、 将所有个体依照rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值（从rank1到 rank * n N ≤），一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制（ranking scheme ）： 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector ：() 1,,q g g g =??? 分为以下三种情况： 1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???> 当a y 支配b y 时，选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时，选择b y 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法 NPGA 基本思想： 1、初始化种群Pop 2、锦标赛选择机制：随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配，而2x 没有被CS 中任一个体支配，则选择2x 。 3、其他情况一律称为死结（Tie ），采用适应度共享机制选择。 个体适应度：i f 小生境计数（Niche Count ）：(),i j Pop m Sh d i j ∈= ????∑ 共享函数：1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度（the shared fitness ）： i i f m 选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设置共享参数 MOGA i x 是第t 代种群中个体，其rank 值定义为： () (,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值（fitness value ）分配算法： 1、 将所有个体依照rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值（从rank1到 rank * n N ≤），一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制（ranking scheme ）： 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector ：() 1,,q g g g =??? 分为以下三种情况： 1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???> 当a y 支配b y 时，选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时，选择b y 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法 NPGA 基本思想： 1、初始化种群Pop 2、锦标赛选择机制：随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配，而2x 没有被CS 中任一个体支配，则选择2x 。 3、其他情况一律称为死结（Tie ），采用适应度共享机制选择。 个体适应度：i f 小生境计数（Niche Count ）：(),i j Pop m Sh d i j ∈= ????∑ 共享函数：1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度（the shared fitness ）： i i f m 选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设置共享参数 流水车间调度问题的研究 机械工程学院 2111302120 周杭超 如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进行合理调度排序就显得十分重要。 在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D 四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，那么在200分钟的时间内就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。 比较均衡的生产方式(图2 )是:在一条流水线上同时将四种产品 混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进行转换，那么单件流的生产方式是最好的。然而，在实际生产A, B, C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。 图1 图2 因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。 流水车间调度问题一般可以描述为n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为(1,,;1,,)ij t i n j m ==L L 。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。 用于约束多目标优化问题的双群体差分进化算 法精编 Document number：WTT-LKK-GBB-08921-EIGG-22986 用于约束多目标优化问题的双群体差分进化算法 孟红云 1 张小华2刘三阳1 (1.西安电子科技大学应用数学系，西安，710071； 2.西安电子科技大学智能信息处理研究所，西安，710071)摘要：首先给出一种改进的差分进化算法，然后提出一 种基于双群体搜索机制的求解约束多目标优化问题的差分 进化算法．该算法同时使用两个群体，其中一个用于保存 搜索过程中找到的可行解，另一个用于记录在搜索过程中 得到的部分具有某些优良特性的不可行解，避免了构造罚 函数和直接删除不可行解．此外，将本文算法、NSGA-Ⅱ和SPEA的时间复杂度进行比较表明，NSGA-Ⅱ最优，本文算法与SPEA相当.对经典测试函数的仿真结果表明，与NSGA-Ⅱ相比较，本文算法在均匀性及逼近性方面均具有一定的优势. 关键字：差分进化算法；约束优化问题；多目标优化问题； 中图分类号：TP18 1 引言 达尔文的自然选择机理和个体的学习能力推动进化算 法的出现和发展，用进化算法求解优化问题已成为一个研 究的热点[1-3]．但目前研究最多的却是无约束优化问题．然而，在科学研究和工程实践中，许多实际问题最终都归结 为求解一个带有约束条件的函数优化问题，因此研究基于 进化算法求解约束优化问题是非常有必要的．不失一般 性，以最小化问题为例，约束优化问题（Constrained Optimization Problem ，COP ）可定义如下： )(COP ()()()()q j x h p i x g t s x f x f x f x F j i k R x n ,,1,0)( ,,1,0)( ..,,,)(min 21 ===≤=∈ （1） 其中)(x F 为目标函数，)(),(x h x g j i 称为约束条件， n n R x x x x ∈=),,,(21 称为n 维决策向量．将满足所有约束条件的 解空间S 称为(1)的可行域．特别的，当1=k 时，(1)为单目 标优化问题；当1>k 时，（1）为多目标优化问题．)(x g i 为 第i 个不等式约束，)(x h j 是第j 个等式约束．另一方面，对于等式约束0)(=x h j 可通过容许误差（也称容忍度）0>δ将它转 化为两个不等式约束： ?????≤--≤-0)(0)(δδx h x h j j （2） 故在以后讨论问题时，仅考虑带不等式约束的优化问题．进一步，如果x 使得不等式约束0)(=x g i ，则称约束() x g i 在x 处是积极的．在搜索空间S 中，满足约束条件的决策变量x 称为可行解，否则称为不可行解． 定义1（全局最优解）()**2 *1*,,,n x x x x =是COP 的全局最优解，是指S x ∈*且)(*x F 不劣于可行域内任意解y 所对应的目标 函数)(y F ，表示为)( )(*y F x F ． 对于单目标优化问题， )( )(*y F x F 等价为)()(*y F x F ≤，而对于多目标优化问题是指不 存在y ，使得)(y F Pareto 优于)(*x F ． 目前，进化算法用于无约束优化问题的文献居多，与 之比较，对约束优化问题的研究相对较少[4-6]。文[7] 对当前基于进化算法的各种约束处理方法进行了较为详细的综述. 对于约束优化问题的约束处理方法基本上分为两类：基于 罚函数的约束处理技术和基于多目标优化技术的约束处理 高维多目标进化算法 二、文献选读内容分析及思考 （一）Borg算法 Borg算法是基于ε-MOEA算法（Deb，2003）的一种全新改进算法[32]，下面将从创新点、原理、算法流程和启发思考四方面进行阐述。 1.创新点 1）在ε支配关系的基础上提出ε盒支配的概念，具有能同时保证算法收敛性与多样性的特点。 2）提出了ε归档进程，能提高算法计算效率和防止早熟。 3）种群大小的自适应调整。 4）交叉算子的自适应选择。由于处理实际问题时，是不知道目标函数具有什么特性，前沿面如何，在具有多个交叉算子的池子里，根据进程反馈，选择不同的交叉算子，使产生的后代具有更好的特性针对要研究的问题。 2. Borg算法原理 1）ε盒支配：通过对目标空间向量的每一维除以一个较小的ε，然后取整后进行pareto支配比较。这样的支配关系达到的效果是把目标空间划分成以ε为边长的网格（2目标时），当点处于不同的网格时，按pareto支配关系比较；当处于同一网格时，比较哪个点距离中心点（网格最左下角）最近。这样一来，网格内都只有一个点。 2）ε归档进程 如图1所示，黑点表示已经归档的，想要添加到档案集的新解用×表示，阴影表示归档解支配的区域。当新解的性能提升量超过阈值ε才属于ε归档进程。比如解1、解2加入归档集属于ε归档进程，解3加入归档集就不属于ε归档进程。 图1 ε支配网格 在这个过程中设置了一个参数c，表示每一代中加入归档集解得个数，每隔一定迭代次数检测c有没有增加，如果没有增加表明算法停滞，重启机制启动。 3）重启 自适应种群大小：重启后的种群大小是根据归档集的大小设置。γ表示种群大小与归档集大小的比值，这个值也用于第二步中，如果γ值没超过1.25，重启机制也启动。启动后，γ人为设定为固定值，种群被清空，填充归档集的所有个体，不足的个体是随机选取归档集中个体变异所得。与之相匹配的锦标赛比较集大小是归档集大小乘以固定比值τ。 4）交叉算子的自适应选择 摒弃以往采用单一的交叉算子，采用包含各类交叉算子的池子，比如有K 1、问题描述： n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 2、问题分析 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N={1，2，…，n}。S是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 设π是所给n个流水作业的一个最优调度，它所需的加工时间为 aπ(1)+T’。其中T’是在机器M2的等待时间为bπ(1)时，安排作业 π(2)，…，π(n)所需的时间。 记S=N-{π(1)}，则有T’=T(S,bπ(1))。 证明：事实上，由T的定义知T’>=T(S,bπ(1))。若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。 则π(1)，π'(2)，…，π'(n)是N的一个调度，且该调度所需的时间为 aπ(1)+T(S,bπ(1)) 流水作业调度问题 描述: N个作业｛1,2, ..... ,n｝要在由两台机器M1和M2组成的流水线上完成加工。每个作业 加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi , 1 < i < n。流水作业高度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 可以假定任何任务一旦开始加工，就不允许被中断，直到该任务被完成，即非优先调度。输入: 输入包含若干个用例, 第一行为一个正整数K(1<=K<=1000), 表示用例个数, 接下来K 个用例,每个用例第一个为作业数N(1<=N<=1000)，接下来N行，每行两个非负整数，分别表 示在第一台机器和第二台机器上加工时间。 输出: 每个用例用一行输出采用最优调度所用的总时间，即从第一台机器开始到第二台机器结束的时间。 样例输入: 1 4 5 6 12 2 4 14 8 7 样例输出: 33 假定直接按顺序进行完成，则机器1 可以不用考虑，因为作业1 完成后就可以完成作业 2,直到作业n,需要的时间为所有作业在机器1上的时间总和。 但是，机器2 上完成的时间呢？ 机器2上完成的时间显示除了作业在机器2上完成的时间总和, 还要加上等待时间, 即要求先在机器1 上完成后,才能在机器2 上开始。 例如 5 6 12 2 两个作业,顺序如下： 按顺序,则在机器1 上进行作业1 需要5小时,后进行作业2, 需要12小时,和为17 小时； 机器2 上,作业1 只能从第5 小时开始,第11 小时完成,等待了5 小时,等到作业2 在机器1 上完成后(已经是第17时),再完成2小时,共19小时。机器2的等待时间总计为11 小时。 逆序,在机器1上进行作业2需要12小时,后进行作业1 需要5小时,和为17小时, 基于分解的多目标进化算法 //流水作业调度.cpp :定义控制台应用程序的入口点。 #i nclude"stdafx.h" #in elude JOB* rk = new JOB[c]; b = c = 0; for (int a = 0; a < NUM; a++)//divide { if (temp[a].type == 0) wo[b++] = temp[a]; else rk[c++] = temp[a]; } //sort wo for (int m = 0; m < b; m++) for (i nt n = m + 1; n < b; n++) if (wo[n].a < wo[m].a) { JOB job=wo[m]; wo[m] = wo[ n]; wo[n] = job; } //sort rk for (int m = 0; m < c; m++) for (int n = m + 1; n < c; n++) if (rk[n].b > rk[m].b) { JOB job = rk[m]; rk[m] = rk[ n]; rk[n] = job; } for (int m = 0; m < b; m++) temp[m] = wo[m]; for (int m = b ,n=0; m < NUM; m++,n++) temp[m] = rk[ n]; } void In put( JOB* temp ) { for (int a = 0; a < NUM; a++) { cout << a + 1 << ":\n A:"; cin >> temp[a].a; cout << " B:"; cin >> temp[a].b; or 0 temp[a].type = temp[a].a > temp[a].b ? 1 : 0;//a>b 1 temp[a].i ndex = a + 1; 0018算法笔记——【动态规划】流水作业调度问题与Johnson 法则 1、问题描述： n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业 在机器M2上加工完成所需的时间最少。 2、问题分析 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N={1，2，…，n}。S是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 设π是所给n个流水作业的一个最优调度，它所需的加工时间为 aπ(1)+T’。其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所需的时间。 记S=N-{π(1)}，则有T’=T(S,bπ(1))。 证明：事实上，由T的定义知T’>=T(S,bπ(1))。若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。则π(1)，π'(2)，…，π'(n)是N的一个调度，且该调度所需的时间为 aπ(1)+T(S,bπ(1)) x 是第 t 代种群中个体，其 rank 值定义为： rank (x ,t ) =1+p (t ) p (t )为第t 代种群中所有支配x 的个体数目 适应值 (fitness value )分配算法： 1、 将所有个体依照 rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值(从 rank1 到 rank n * N )，一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一 rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制(ranking scheme )： 向量y a =(y a ,1,,y a ,q )和y b =(y b ,1,,y b ,q )比较 分为以下三种情况： k =1,,q -1; i =1,,k ; j =k +1,,q ; (y a ,i g i )(y a ,j g j ) i =1, ,q ; (y a ,i g i ) 当 y a 支配 y b 时，选择 y a 3、j =1, ,q ; (y a ,j g j ) 当 y b 支配 y a 时，选择 y b 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的 大小影响 理论上给出了参数share 的计算方法 goal vector ： g = (g 1, ,g q ) 1、 2、 基本思想： 1、初始化种群 Pop 2、锦标赛选择机制：随机选取两个个体 x 和 x 和一个 Pop 的 子集 CS(Comparison Set)做参照系。若 x 被 CS 中不少于一 个个体支配，而 x 没有被 CS 中任一个体支配，则选择 x 。 3、其他情况一律称为死结(Tie )，采用适应度共享机制选择。 个体适应度： f i 小生境计数(Niche Count )： m =j Pop Sh d (i , j ) 共享适应度(the shared fitness )： 选择共享适应度较大的个体进入下一代 优点：能够快速找到一 些好的非支配最优解域 能够维持一个较长的种群更新期 缺 点：需要设置共享参数 需要选择一个适当的锦标赛机制 限制 了该算法的实际应用效果 1- 共享函数： Sh (d ) = d share 0, d share d share // 流水作业调度.cpp : 定义控制台应用程序的入口点。#include"stdafx.h" #include JOB* rk = new JOB[c]; b = c = 0; for (int a = 0; a < NUM; a++)//divide { if (temp[a].type == 0) wo[b++] = temp[a]; else rk[c++] = temp[a]; } //sort wo for (int m = 0; m < b; m++) for (int n = m + 1; n < b; n++) if (wo[n].a < wo[m].a) { JOB job=wo[m]; wo[m] = wo[n]; wo[n] = job; } //sort rk for (int m = 0; m < c; m++) for (int n = m + 1; n < c; n++) if (rk[n].b > rk[m].b) { JOB job = rk[m]; rk[m] = rk[n]; rk[n] = job; } for (int m = 0; m < b; m++) temp[m] = wo[m]; for (int m = b ,n=0; m < NUM; m++,n++) temp[m] = rk[n]; } void Input( JOB* temp ) { for (int a = 0; a < NUM; a++) { cout << a + 1 << ":\n A:"; cin >> temp[a].a; cout << " B:"; cin >> temp[a].b; temp[a].type = temp[a].a > temp[a].b ? 1 : 0;//a>b 1 or 0 temp[a].index = a + 1; } 龙源期刊网 https://www.doczj.com/doc/b29165160.html, 多目标优化进化算法比较综述 作者：刘玲源 来源：《决策与信息·下旬刊》2013年第07期 摘要多目标优化是最优化领域的一个重要研究方向，本文简要介绍了多目标优化的模型和几种多目标优化的进化算法，并对算法进行了简要比较。 关键词多目标优化粒子群遗传算法蚁群算法人工免疫系统 中图分类号：TP391 文献标识码：A 一、背景 多目标优化（Multiobjective OptimizaTionProblem，MOP）是最优化的一个重要分支，多目标问题中的各目标往往是有着冲突性的，其解不唯一，如何获得最优解成为多目标优化的一个难点，目前还没有绝对成熟与实用性好的理论。近年来，粒子群算法、遗传算法、蚁群算法、人工免疫系统、等现代技术也被应用到多目标优化中，使多目标优化方法取得很大进步。本文将其中四种多目标优化的进化算法进行一个简单的介绍和比较。 二、不同算法介绍 （一）多目标遗传算法。 假定各目标的期望目标值与优先顺序已给定，从优先级最高的子目标向量开始比较两目标向量的优劣性，从目标未满足的子目标元素部分开始每一级子目标向量的优劣性比较，最后一级子目标向量中的各目标分量要全部参与比较。给定一个不可实现的期望目标向量时，向量比较退化至原始的Pareto排序，所有目标元素都必须参与比较。算法运行过程中，适应值图景可由不断改变的期望目标值改变，种群可由此被引导并集中至某一特定折中区域。当前种群中（基于Pareto最优概念）优于该解的其他解的个数决定种群中每一个向量解的排序。 （二）人工免疫系统。 人工免疫算法是自然免疫系统在进化计算中的一个应用，将抗体定义为解，抗原定义为优化问题，抗原个数即为优化子目标的个数。免疫算法具有保持个体多样性、搜索效率高、群体优化、避免过早收敛等优点。其通用的框架是：将优化问题的可行解对应抗体，优化问题的目标函数对应抗原，Pareto最优解被保存在记忆细胞集中，并采取某种机制对记忆集进行不断更新，进而获得分布均匀的Pareto最优解。 （三）多目标PSO约束算法。 摘要：在传统的多目标优化问题上常常使用分解策略。但是，这项策略还没有被广泛的应用到多目标进化优化中。本文提出了一种基于分解的多目标进化算法。该算法将一个多目标优化问题分解为一组单目标优化问题并对它们同时优化。通过利用与每一个子问题相邻的子问题的优化信息来优化它本身，这是的该算法比MOGLS和非支配排序遗传算法NSGA-Ⅱ相比有更低的计算复杂度。实验结果证明：在0-1背包问题和连续的多目标优化问题上，利用一些简单的分解方法本算法就可以比MOGLS和NSGA-Ⅱ表现的更加出色或者表现相近。实验也表明目标正态化的MOEA/D算法可以解决规模范围相异的多目标问题，同时使用一个先进分解方法的MOEA/D可以产生一组分别非常均匀的解对于有3个目标问题的测试样例。最后，MOEA/D在较小种群数量是的性能，还有可扩展性和敏感性都在本篇论文中通过实验经行了相应的研究。 I.介绍 多目标优化问题可以用下面式子表示： Maximize F(x)=((f1(f)…...f f(f))f subject to x∈Ω 其中Ω是决策空间，F：Ω→f f，包含了m个实值目标方法，f f被称为目标区间。对于 可以得到的目标集合成为{F(x)|x∈Ω}。 如果x∈R m，并且所有的目标函数都是连续的，那么Ω则可以用 Ω={x∈f f|h f(x)≤0,j=1……m} 其中hj是连续的函数，我们可以称(1)为一个连续的多目标优化问题。 如果目标函数互斥，那么同时对所有目标函数求最优解往往是无意义的。有意义的是获得一个能维持他们之间平衡的解。这些在目标之间获得最佳平衡的以租借被定义Pareto最优。 令u, v∈Rm，如果f f≥f f对于任意的i，并且至少存在一个f f≥f f(i,j∈{1…..m})，那么u支配v。如果在决策空间中，没有一个点F(y)能够支配F(x)点，那么x就是Pareto最优，F(x)则被称为Pareto最优向量。换句话说，对于Pareto最优点在某一个目标函数上的提高，都会造成至少一个其余目标函数的退化。所有Pareto最优解的集合称为Pareto集合，所有最优向量的集合被称为Pareto前沿。 在许多多目标优化的实际应用中，通过选择器选择一个接近Pareto最优前沿的解作为最后的解。大多数多目标优化问题都有许多甚至是无穷个Pareto最优向量，如果想要获得一个完整的最优前沿，将是一件非常耗时的事情。另一方面，选择器可能不会专注于获得一个过于庞大的最优解向量集合来解决问题，因为信息的溢出。因此，许多多目标优化算法往往是获得一个均匀分布在Pareto最优前沿周围的最优解向量，这样就具有更好的代表性。许多研究人员也致力于使用数学模型来获得一个近似的最优前沿。 一般来说，在温和控制下多目标优化问题的Pareto最优解，可以看做是一个标量优化问题的最优解(其中目标函数是fi的集合)。因此，Pareto最优前沿的近似求解可以被分解为一组标量目标优化子问题。这个想法是建立在许多传统的对最优前沿求近似解的数学编程方法上的。现在有许多的聚合方法，最流行的是切比雪夫法和加权法。最近，边界交叉方法也引起了许多的关注。 如今多目标进化算法并没有将分解这一概念引入当前的主要发展领域。这些算法将多目标优化问题看成一个整体。他们并没有通过任何特别的标量优化将每一个解相互联系在一起。在一个标量目标优化问题中，所有的解都可以通过他们的目标函数值进行对比，而挑战 动态规划-流水作业调度报告 C1 问题描述和分析 N个作业{1,2,………,n}要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi，1≤i≤n。流水作业高度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 设全部作业的集合为N={1,2,…,n}, S?N,,一般情况下,机器M1开始加工作业S时,机器M2还在加工其他作业,要等时间t后才可利用.将这种情况下完成S中作业所需的最短时间记为T(S,t).流水作业调度的最优值为T(N,0) 即,设π是所给n个流水作业的一个最优调度,它所需的加工时间为a(π1)+T’.其中T’是在此机器M2的等待时间为b(π1)时,安排作业π1, π2,…πn所需时间. 所以S=N-{π1},有T’=T(S,b(π1)). 由T的定义知T’≥T(S,b(π1)).若T’＞T(S,b(π1)),设π’是作业集S在机器M2的等待时间为b(π1)情况下的一个最优调度.则π1, π’2,…, π’n是N的一个调度,且该调度所需的时间为a(π1)+T(S,b(π1))＜a(π1)+T’.这与π是N的最优调度矛盾.故T’≤ T(S,b(π1).从而T’=T(S,b(π1). 即当机器M1为空闲即未安排任何加工任务时，则任何一个作业的第一个任务（第一道工序）都可以立即在M1上执行，无须任何先决条件。因此容易知道，必有一个最优调度使得在M1上的加工是无间断的。实际上，如某个最优调度π在M1上安排的加工是有间断的，则我们可以把所有在M1上出现间断处的任务的开始加工时间提前，使得在M1上的加工是无间断的；而在M2上仍按π原先的安排。把这样调整之后的调度记作为π’。由于在调度π’下，任何一个任务在M1上加工的结束时间不晚于在调度π下的结束时间，故调度π’不会影响在M2上进行加工的任何一个任务的开始时间。由于调度π’在M1上的结束时间早于调度π，在M2上的结束时间与调度π相同，而π又是最优调度，所以π’也是最优调度。由此我们得到：一定有一个最优调度使得在M1上的加工是无间断的。另外，也一定有一个最优调度使得在M2上的加工空闲时间（从O时刻起算）为最小，同时还满足在M1上的加工是无间断的。（证明留作作业）因此，如果我们的目标是只需找出一个最优调度，我们可以考虑找：在M1上的加工是无间断的、同时使M2的空闲时间为最小的最优调度。（根据上述理由，这样的最优调度一定存在。）可以证明，若在M2上的加工次序与在M1上的加工次序不同，则只可能增加加工时间（在最好情况下，增加的时间为O）。也就是说，在M1上的加1多目标优化
多目标进化算法总结
多目标进化算法总结
流水车间调度问题的研究-周杭超
用于约束多目标优化问题的双群体差分进化算法精编
最新高维多目标进化算法总结
0018算法笔记——【动态规划】流水作业调度问题与Johnson法则
流水作业调度问题
MOEAD(基于分解的多目标进化算法)
摘要：在传统的多目标优化问题上常常使用分解策略。但是，这项策略还没有被广泛的 应用到多目标进化优化中。本文提出了一种基于分解的多目标进化算法。该算法将一个多目 标优化问题分解为一组？？？单目标优化问题并对它们同时优化。通过利用与每一个子问题 相邻的子问题的优化信息来优化它本身，这是的该算法比 MOGLS 和非支配排序遗传算法 NSGA-Ⅱ相比有更低的计算复杂度。实验结果证明：在 0-1 背包问题和连续的多目标优化问 题上，利用一些简单的分解方法本算法就可以比 MOGLS 和 NSGA-Ⅱ表现的更加出色或者 表现相近。实验也表明目标正态化的 MOEA/D 算法可以解决规模围相异的多目标问题，同 时使用一个先进分解方法的 MOEA/D 可以产生一组分别非常均匀的解对于有 3 个目标问题 的测试样例。最后，MOEA/D 在较小种群数量是的性能，还有可扩展性和敏感性都在本篇 论文过实验经行了相应的研究。
I. 介绍
多目标优化问题可以用下面式子表示：
其中 Ω 是决策空间， 以得到的目标集合成为
，包含了 m 个实值目标方法， 被称为目标区间。对于可 。
如果
，并且所有的目标函数都是连续的，那么 Ω 则可以用
其中 hj 是连续的函数，我们可以称(1)为一个连续的多目标优化问题。 如果目标函数互斥，那么同时对所有目标函数求最优解往往是无意义的。有意义的是获
得一个能维持他们之间平衡的解。这些在目标之间获得最佳平衡的以租借被定义 Pareto 最 优。
令 u, v∈Rm，如果
对于任意的 i，并且至少存在一个
，那
么 u 支配 v。如果在决策空间中，没有一个点 F(y)能够支配 F(x)点，那么 x 就是 Pareto 最优， F(x)则被称为 Pareto 最优向量。换句话说，对于 Pareto 最优点在某一个目标函数上的提高， 都会造成至少一个其余目标函数的退化。所有 Pareto 最优解的集合称为 Pareto 集合，所有 最优向量的集合被称为 Pareto 前沿。
在许多多目标优化的实际应用中，通过选择器选择一个接近 Pareto 最优前沿的解作为 最后的解。大多数多目标优化问题都有许多甚至是无穷个 Pareto 最优向量，如果想要获得 一个完整的最优前沿，将是一件非常耗时的事情。另一方面，选择器可能不会专注于获得一 个过于庞大的最优解向量集合来解决问题，因为信息的溢出。因此，许多多目标优化算法往 往是获得一个均匀分布在 Pareto 最优前沿周围的最优解向量，这样就具有更好的代表性。 许多研究人员也致力于使用数学模型来获得一个近似的最优前沿。
一般来说，在温和控制下多目标优化问题的 Pareto 最优解，可以看做是一个标量优化 问题的最优解(其中目标函数是 fi 的集合)。因此，Pareto 最优前沿的近似求解可以被分解为流水作业调度完整代码
0018算法笔记——【动态规划】流水作业调度问题与Johnson法则
多目标进化算法总结
流水作业调度完整代码
多目标优化进化算法比较综述
MOEAD(基于分解的多目标进化算法)
动态规划-流水作业调度报告
相关主题
文本预览