蛙跳算法与批量无等待流水线调度问题的优化

蛙跳算法现有文献

第2 7卷第 8期21 0 0年 8月

计算机应用研究 A pi t nR sac f o ues p l ai eerho mp t c o C r

Vo . 7 No 8 12 .Au . 2 1 g 00

蛙跳算法与批量无等待流水线调度问题的优化声谢圣献潘全科潘玉霞。贾保先，,,(. 1聊城大学计算机学院，山东聊城 2 2 5 2海南大学三亚学院，南三亚 5 22 ) 5 0 9; .海 7 0 2

摘要：针对以 m ksa ae n为指标的批量无等待流水线调度问题，出了一种有效的离散蛙跳算法。首先采用 p提基于工序的编码方式使蛙跳算法直接应用于调度问题；次采用基于 N H与改进 N H和随机产生相结合的初其 E E

始化方法，保证了初始解的高质量和分布性；次采用交叉或变异方法产生新解，持了种群的优越性和多样再保性；对全局最优解执行快速局部搜索，效地降低了算法的时间复杂度，最后有平衡算法的全局和局部开发能力。 对随机生成不同规模的实例进行广泛的实验，仿真实验结果的比较，明所得蛙跳算法的有效性和高效性。通过表 关键词：批量无等待流水线调度；蛙跳算法；快速局部搜索中图分类号：T 8 P1文献标志码：A 文章编号：10— 6 5 2 1 ) 8 2 0—4 0 13 9 (0 0 0—9 9 0d i1 .9 9 ji n 10—6 5 2 1 . 8 0 6 oi0 3 6/.s .0 13 9 .0 0 0 .2 s

S u e r g- a ig ag rt m o o-te mig n - i h f d fo -e pn lo i l l h frltsr a n o- t - wa l f ws o c e u ig p o lm o h p s h d l r be nX E Segxa P NQ a-e, A ux JA B o i I hn-i, A unk P N Y—i, I a- a n a xn( . colfC m ue c ne La ceg U i n￣,Laceg S adn 50 9,C ia . colfS na an n U i rt,Sna 1Sho o o p t Si c, i hn n e i r e o v iohn hn og2 25 hn;2 Sho ay,H ia nv sy a y o eiHann5 2 2,C i ) i 7 0 2 hn a a

Abt c:T i ppr rp sda f c v

h fe r— ai l rh ( F A)f ov gt o s em n o hp sr t hs a e pooe ne etesu l f gl pn a oi m S L a f i fd o e g g t o sl n eltt a igf w so r i h r l sh dl gpol i e re o i mz gm x u o peo m ie, k sa )u dr ow ipo utnc— ceui rbe wt t i r no mn in ai mcm lt n ie(.. maepn n e—a r c o a n m h h c ti f i i m i t n t d i ss it, epooe F Arpeet ni id a o o sa o em t i k eo g a S L ut l f e.Fr l t r s S L r ne a dv u r r a bpr uao i maet r i l F A sibeo sy h p d e s d n i l fg j tn o h i n a rs h d l g p o lm.S c n l d sg e n i i ai t n me h d b s d o eNE h u s c h r l, s d ac o s v r p r— c e ui rbe n e o dy, e in d a t l a i t o a e n t H e r t .T i y u e r so e e a n i z o h i i d o t ro tt n o e ao r d c e d vd a .F n l i r e of r e n a c e ag r h o rmu ai p rt r op o u ea n w i ii u 1 i a y, n od r t re h n et lo t m’ x l i t n c p b l o t n l t u h h i S p ot i a a i— e ao i t n f ce c y a d e in y,e e d d a fs lc ls a c l o t m a e n t e i s r o w p n ih o h o n t e p o o e h f e i mb d e t o a e r h ag r h b s d o h n e t r s a eg b r o d i h r p s d s u l d a i f f g l a i g ag r h r—e p n lo t m.T i c n rd c P i . e c mp t t n lr s l n o aio s s o a h rp s d S L s o i hs a e u e C U t me T o u ai a e ut a d c

mp r n h w t t ep o o e F A i h o s s h t ef cie a d e ce t o n o i sa t n f d n etrs l t n rt e p o lm o sd r d f t n f i n rr d m tn si i ig b t o ui sf rb e c n i e e . e v i f a n n e o o h Ke r s o—te mig n— i f W h p s h d l g p o lm;s ufe r g la i g ag r h;fs lc l e r h y wo d:ltsra n o wat o s o c e u i r b e l n h f d f— p n o t m a t o a a c l o e l i s

批量无等待流水线调度问题是一个具有广泛应用背景和重要理论价值的组合优化问题，是许多实际生产调度过程的简

电场电力系统动态优化等方面，取得了良好的效果。基并于蛙跳算法的以上优点，出了一种离散蛙跳算法，提并嵌入快

化模型，广泛存在于炼钢、品加工、食化工和制药等工业领域。 目前，研究此类问题的文献很少。K m等人…于 20 ua r 0 0年用遗传算法解决批量无等待流水线调度问题， m n等人于 E mos 19 9 5年把批量无等待问题模拟成 T P进行解决。由于此类问 S题的复杂性，智能算法成为求解调度问题的主要方法。蛙跳算法 ( F A) 20年由 E sf和 Lne提出的一 S L是 00 uu asy

速局部搜索，有效地提高了蛙跳算法解决批量无等待流水线调度问题的性能。

1问题描述 批量无等待流水线调度问题 ( t t a n o a o so 1 -r mi n - if w hp o se g w t l

shdl polm,N S ) ceue rbe L F P可描述为：工件分成若干个等大的 将批量，每个批量在机床上的加工顺序相同，同一批量的两个工

种受自然生物模仿启示而产生的基于群体的协同搜索算法。 作为一种全新的生物进化算法，它结合了基于基因进化的模因演算法和基于群体行为的粒子群算法两者的优点 J具有概，

序之间没有等待时间，即要求任意批量在每台机床上的完成时间必须等于其在下一台机床上的开始时间。同时约定，每个批量某一时刻只能够在一台机床上加工，每台机床在某一时刻只能够加工一个批量。每个工件 N={,,,} 1 2

… n按某一工序

念简单、参数少、计算速度快、全局寻优能力强、易于实现等特点。最初应用于成品油管网设计、贴片机贴装顺序』含风、

收稿日期： 0 00—7 2 1—2 1;修回日期： 0 00—5 2 1— 3 1育厅资助项目(O L2 J8 J0)

基金项目：国家自然科学基金资助项目( 0 70 5 7 8 16 )数字制造装备与技术国 6 84 7,0 70 5;

家重点实验室开放课题(中科技大学)博士后科学基金资助项目(0 7 4 09 )华； 20 0 17 1;山东省软件科学研究计划资助项目(0 9 K 15;山东省教 20 R B 2 )作者简介：圣献 (9 7 )男，谢 15 -,山东聊城人，教授，主要研究方向为智能计算和信息安全(s@lue u c ) xx c .d .a;潘全科 (9 1 )男， 17一，山东阳谷人， 教授，博士后，主要研究方向为智能计算及其应用研究；潘玉霞 (9 3 )女，东德州人， 18一，山硕士研究生，主要研究方向为智能计算及其应用研究；贾保先 ( 92 )男，东阳谷人， 18一，山助教，要研究方向为本体与电子商务 .主

蛙跳算法现有文献

2l 9 0

计算机应用研究( )=n一1 bi时

第2 7卷

顺序通过每台机床 i∈M={,,,,了提高生产速度， 12… m}为 把工件划分成 z ) (个批量， 工件的批量在机床 i的加工时上间为 P i ) (√。每个批量加工完成后立即被传送到下一台机床上加工，这样能有效地减小调度的最大完工时间。假设工件的启动时间为 0则问题的调度模型如图 1,所示。m c ie a hn3 2 l

C戤( C a( )一8仃—, )一e丌， 1 m仃 )= x ( l丌1 ( f7+ )一T丌+ )+ r P( 1e仃。l仃+ )+e仃+,。 ( (一，。1 ( f17 )+ r仃) () 6

( )=,, 2时 c i 2… n一rC (~仃)一 (一， e仃.l丌 )一e7. )一 ( J丌. )+ (r, e丌， J1

ma hn cie

}O.,+(。+O J ) e rl一 ) e, ) er,+丌1

=+ i1

震(无批量划分 a ) (批量无等待 b )

.

c— c

{

,

- T P() 7

I一(一 (I,。一 (。… ) e—￣) e, 1+

) e丌—丌) e订， c l仃一 ( lr一(+ ,j / - )e丌.l丌 )+ ( J仃… )+e丌， )+e仃，+) ohr s (一，』 e丌， ( J1丌. ( 1 tewi e

图1批量无等待流水线调度模型

2计算调度的最大完工时间设定一个工序仃=(, 2…,r) e一，,代表工件 7, 7,( 仃) 7一

c i+1如果 i/终止算法， )=i,=7,否则执行步骤 b。 ) 32快速插入邻域搜索算法 .快速插入邻域搜索算法步骤如下： a设当前调度丌=(仃，,, i。 )仃， …仃 )令=1 b从仃中取出工件仃.得到调度丌 ),=(,r:…仃 7,仃 )。

和在第一台机床上的开工时间差， )代表工件 e(

各个批量在第一台机床上的开工时间差， e一，r和 e则 ( 7) ( ) 的计算公式如下：e一， ) P,一) m O m a ( 1 ( I, { x2^一

^

(,— )一^ 1

c )计算调度 7的最大完工时间： r

l

^

; (, )] h} p 2^

( 1 )(, )一^

C ( )= e( )×(( )一1+ 仃 z )

e( ) p 1乃) m x 0 m a (,+ a[, { x^一l

,

∑e—, ) (一)^ fI+ 1 (

() 8

d将工件仃插入到仃的第个位置， ) 得到调度 7√∈{, r” 1

p h )] (,}

,

} ii}^隹{,一1。f一 ( +e仃 )× z丌 )一 ) e 7, o c丌 ) (( 1+ (r ) ( J0=

假设各工件按机床 1~i n的顺序进行加工，工件丌在机 J床i上的完成时间 C (, ) T i的计算公式如下： = m

e计算调度丌的最大完工时间 )”I一 ( +霄 ) z丌 )一 ) e仃 17 ) c丌 ) e(。×(( 1+ ( .,.+ rc I仃 ) 丁 ( T (一) . ( = P丌 )一 P仃 蚰 Jn=

,

凹 m 1 ( )( 1一)善 (仃’ (, )丌 )+ 1, 丌 1 ( p l

{( ) 1 11)) e—f兰 ) ( c,= )(一+ (l)m。 3 r i丌 (1 丌，+1丌 ) m x丌 1 I丌 (J

pJ 历C(, ) ( (丌一) ( l+壬 ( ) Tm仃= ) I + , ) 1 ()仃 p工件最大完成时间 C (r=C ( 。 7) T m, ) 7 r

l一(+。× 1。一 ) e仃一仃) 丌) e仃) (丌) 1+(。 + c ( (,L (, )+e"'】 ) e ( j, f一 ohri tews e

() 9

f=+1如果 i n终止算法， )i i,>否则返回步骤 b。 )

3快速邻域搜索算法对于一个含有 n个工件的调度问题，其插入和交换邻域的规模为 (一1, t )计算最大完成时间的时间复杂度为 O( 。 t n ) C U消耗时间也是评价算法性能的一方面。所以， P在求得调度最小的最大完成时间的同时，尽量降低时间复杂度。采用快速邻域算法求解最大完工时间的时间复杂度为 0( 。T n) P

4蛙跳算法求解 L S NF P4 1算法编码 .由于传统蛙跳算法的模型具有连续性本质，以直接处理难

批量无等待流水线调度问题。为了有效利用蛙跳算法解决此类调度问题，对蛙跳的编码方式进行处理，使其适应批量无等待流水线调度问题。建立个体矢量与工序的映射关系，即用个

(代表工件仃的一个批量在所有机床上的加工时间和：仃) m

体矢量的每一维表示一个工件，这样每只青蛙就表示所有工件的一个排列，即一个调度。表 1为个体矢量与调度之间的对应关系。表 1位置矢量及对应的工件排序解维数 355

T( ) P f=王p i ) (,

() 4

3 1快速交换邻域搜索算法 .算法步骤如下： a设当前调度仃=( 丌，, , )仃， 2…仃 )则最大完工时间记为 C (r, i。 7)令=1度 7=( l…, 1仃， i1…,,l7i r, 7 ) r仃， 7一，,+,仃一，,『…, 。 r仃 r7 r计算当前调度最大完工时间 C ( ) 仃， . ()= a i 1时c丑( m x丌)一 ( l ) e,+ )+ (, )+ (r+ ) j i 1 e仃，一 ( 】 e er, 1 i=+C a(一e丌， i )一 (—, J ( J ) m x仃) (￣十1 e 1丌 )一 r丌 ) e, i ) e一， ) P ' ) (￣+1+ ( r 1仃‘+T ( i w c a(一 ( i

r+ )一 (一， )一 (,+ ) m x丌) e,, i 1 e/ q r 1 e 1 e,+1+ (一， ) (/,十 ) ( I ) e 1丌‘+e, 1 r . i o e i trs hw e

4l1

位置向量墨工件序列

b将工件与工件仃 ( ) =i,, )行交换，到调 4 2基于 N H方法的初始化+1… n进得 . E为了使 S L F A的初始群体具备一定的质量和分散度，在此采用基于 N H方法和改进的 N H【记为 N H ) E E ( E 1的种群初始

化方法，即首先利用 N H方法生成第一个解，用 N H E利 E 1生成第二个解，其余解在离散空间中随机产生。N H和 N H1的 E E伪代码如下：p o e u e NEH rc d rm

=

计算 P=g (,) Vj i p ij,∈N按降序排列得到

() 5

蛙跳算法现有文献

第8期耵=中

谢圣献，:等蛙跳算法与批量无等待流水线调度问题的优化

9 1 21

情况，有利于增加种群的多样性。组合优化问题中的置换编码

f rk=1 t o o on d

从 1中取出工件 k r 将工件 k放入竹中所有可能的位置进行测试

通常采用互换、逆序和插入变异。本文对执行插入变异，随机选择的两个位置为 2和 6p,w={,,,,,则产生的新 16 3 5 24个体 F:{,,,, 2。 14 6 35,}

将工件 k插人到中使得最大完工时间最小e dfr n oed n

5局部搜索m

p o e u e NEH1 rc d r

计算 P i p ij,∈N j (,) Vj 按 P降序排列；盯=中o f rk=1 t o ond

蛙跳算法具有较强的全局探索能力，局部开发能力较但差。为了增强算法的开发能力，提出了基于批量无等待的局部

搜索算法，并将其应用于全局最优解。执行局部搜索一方面可以避免循环搜索使算法陷入局部最优；另一方面，当新得到的解优于当前解时才更新，加速了算法向最优解进化。局部搜索算法流程如图 3所示。

j jb P[]= 0 ( lk )将工件 j插入到中所有可能的位置进行测试将工件 j插入到 1中使得最大完工时间最小 To f ri t o=1 o k d

从工序中取出工件 h 将工件 h插入到霄中所有

可能的位置进行测试将工件 h插入到叮中使得最大完工时间最小 re d fr n o

e d fr n oed n

4 3个体排序及分组 .

在蛙跳算法中，整个群体被分成多个子群，不同的子群被认为是具有不同思想的个体集合。子群中个体按照一定策略

在解空间中独立进化，得信息在个体间传递。为了划分子使群，对群体中的个体按性能指标递减的顺序进行排列，首先得到一个有序的群体。假设群体划分成 p m个子群，每个子群中有p n个个体，则整个群体中个体数量 p= n m。群体中第 p p一

个个体放人第一个子群中，二个个体放入第二个子群中，第图3局部搜索算法流程图

依此类推， p第 m个个体放入第 p m个子群中， p第 m+1个个体放入第一个子群中，如此分配下去直到所有个体都分配完毕。4 4新个体产生方式 .

6算法模块图基于以上设计，图4显示了算法设计的模块化示意图。

在每个子群中，最差个体经过进化过程提高个体质量，使整个群体朝最优方向进化。然而标准 S L F A中， p w位置公式的

更新仅为抽象概念，该模型本质不适合批量无等待流水线调度问题，因此设计新更新公式。随机产生的数 r 0执行交叉操=作， r则执行变异操作。若=14 4 1交叉操作 ..-

I于序的码I基工编上

l于 E的始 l基 NH初化

j个进排并组对体行序分 Il对全局最优解执行局部搜索

交叉操作用于组合出新的个体，在解空间中进行有效搜索，同时降低对有效模式的破坏概率。交叉操作公式为F- (, s/ bt e) (0 1)

l

其中：l为子群中性能最差个体；et表子群中最优个体或|￡ DJ bs代

l子独进 l各群立化——

全局最优个体 )为交叉操作。在中随机选择两个工件直接遗传到新个体相应的位置。其他个体按其在 bs中的位置 et

依次放入到新个体中。假定 p w={,,,,,}bs:{, 163 524,e t 315 42 6, p,,,,}在 w中随机选择的两个工件为 6和 2则新产生，的个体 F={, 152,, 36,,, 4}如图 2所示。pw

图4算法模块示意图

7算法伪代码基于以上设计，解决批量无等待流水线调度问题的蛙跳算法伪代码如下：

b gn e i

,

b s et

图2交叉操作产生新个体

设置参数 P和 p m初始化种群 w i不符合终止条件， n he l d

4 4 2变异操作 ..

当交叉操作产生的后代适配值不再进化且没有达到最优时，就意味着算法的早熟收敛。变异在一定程度上克服了这种

.

计算各个体的目标值排序并分组，录下全局最优个体记

蛙跳算法现有文献

2l 9 2 对全局最优个体执行局部搜索 fr 0对于每个子群，重复执行以下步骤记录性能最好和最差个体利用第 4 4节更新最差个体 .e d f r n o;

计算机应用研究

第2 7卷

上，提出了离散蛙跳算法，并通过对嵌入局部搜索增强算法深度开发的能力。仿真实验表明了所得算法的优越性、可行性和有效性。表 2 SL F A、A O、A、H A和 G比较 C T E AS IA F l AC O T A HE A GA

合并各个子群e d wh l n i e;

MRP l

S D

MR l P

S D

MRP l

S D

MRP I

S D

MRP I

S D

e d n.

1 0 0 0 0 0 . 0 5 1 3 O∞ s 5 23 0 0l 2 3 5 0 6 7 7 2 0 x5 . 0 0 0 0 0 0 0 0 l 51 . 8 7 O o 8 O 6 O. 2 5 73 1 0 0 0 0 0 0 . 0 3 l 0 7 O O 3 6 6 9 O o 3 5 9 8 0 O 5 9 0 9 0 x】 0 0 0 0 0 0 0 0 3 2 . 2 6 1 8 1 . 0 8 3 7 4 8 89 1 5 00 0 0 x1 0 0 0 O唧】 O 0 2 0 3 0 0 7 9 0 3 0 o 2 2 6 0 O 0 O 1 1 9 ol 2 0 8 . 0 9 . 5 4 0 3 9 9 3l 4 5 0 1 0 0x2 0. 0 0 ( 0 0l 6 2 4 l 21 l . 0 0 0 0 1 0 0 5 4 O 0 5 7㈣ 0 0 8 l 4 90 O 3 1 2 7 0 o 5 l 1 7 4 8 2 4 6

蛙跳算法中每个子群中青蛙按照一定策略执行解空间的局部深度搜索，使得信息在个体问传递。在已定义的局部搜索迭代次数结束后，思想在混合过程中进行交换，使得局部间的

2 0. 0 0 0 1 0 0 8 2 2 3 7 2 4 6 0 0 3 0 0 5 4 2 l

. 3 2 0 x5 0 0 0 3 5 0 0 5 6 2 0 Ol 5 . 8 7 3 4 l 4 8 0 0 5 0 3 O 2 1 0. O O 0 0 0x 0 1 0 0 0 0 0. 2 9 7 2 0 01 0 1 . 4 2 0 0 7 6 2 4 O. 6 0 1 8 8 3 01 3 5 6 9 4 8 4 4 3 1 6 4 0 8 7 3 6 2 】 0. O3 0 O.】 0x 5 0( 0 x O O. O 5 l 8 2 0. 2 3 8 8 9 0 0 2 2 5 0 2 2 . 0 6 O 9 l 2 9 0 6 2 . 6l 5 8 2 1 51O. 8 2 4 0 7 2 0 . 0 0 ∞ O . l 6 1 61 1 4 1 . 5 3 0. 5 2 2 7 9 0 O 8 2 5 9 0 x2 0 0 0 0 O O O 3 5 9 9 O 0 8 5 9 8 0 4 0 2 8 8 2 2 3 6 3 0 0 0 l 0 5 . 1 0 B 5 9 6 0 0 7 . 5 2 0 3 I 7 7 0 0 9 I 6 7 0 x5 . 0 0 9 2 0 0 4 0 9 1 3 7 5 5 3 0. 5 6 l9 6 . 5 8 l 78

思想得到交换。局部搜索和混合策略一直持续到定义的收敛条件结束为止。全局交换和局部深度搜索的平衡策略使得算法能够跳出局部极值点，向着全局最优的方向前进。

8仿真实验8 1实验设置 .

3 1 0 0 0 0 4 6 0 0 8 2 71 0 6 9 5 5 8 1 2 6 ( 0 0 6 l l O 0 x 0 0 0 6 0 . 1 9 2 510. 2 7 1: 6 8 0 0 5 7 3 33 . 9 7 9 1 1 3 1 0 0 0 1 8 3 0 0 3 2 2 8 2 5 2 . 0 3 O O 2 8 61 O 1 3 4l0 0x 5 0 0 . 1 4 . 2 7 2 . 0 0 0 0 6 O 9 5 9 5 2 1 4 0 l 6 2 3 3×2 0 0 0 l45 6 . 1 1 7 8 . 2 o 3 7 2 . 8 5 2 6 2 O 1 0 2 . 8 9 0 0 . 0 0 4 0 0 5l 3. 1 2 O 0 9 0. 7 0 O 0 4 7 4 7 . o o 5 4 6 4 0 0 0 1 5 4 . 1 I . 4 4 O O 1 0. 5 8 0 0 6 3 9 6 . 6 3 1 . 2 4 0x5 . 0 0 7 6 0 0 7l 1 5 4 2 8 1 5 0 6 4 l . 3 1 0 0 9 3 4 3

为测试本文提出

的算法的性能，与文献[]出的 G 1提 A算法、文献[] H A算法和文献[] A O和 T 8的 E 9的 C A算法进行比较，采用 Vsa C++编译工具，处理器为 P n u@ 1 6 i l u在 etm .0 i G z内存为 52MB的 P H、 1 C机上进行测试。随机产生 2 8个不

4 0 0 0 0 l 7 O . 3 2 2 4 8 0 0 5 3 9 2 9 8 2 4 9 0 1 3 2 l 2 0 x1 . 0 0 7 1 0 0 2 0 9 2 . 3 6 2 . 3 3 O O 8 8 2 1 . o 9 7 9 l 4 5 0 0 0 1 4 7 . 3 6 2 6 3 l 5 6 0 l 8 2 0 5 0 0 8 0 1 3 0 x1 0 0 8 5 0 0 4 5 4l 5 0 0 01 7 8 6 o0 8 5 8 l 9 3 8 7 4×2 0 0 0 7 7 8 . 4 2 2 2 5 0 0 0 6 0 5 2 6 l O 2 0 1 5 4 . 5 6 0 0 0 0 9 3 0 O 6 5 0 9 4 4 2 9 4 0 1 5 3 7 6 . 3 4 3 3 0 5 0 0 0 2 6 4 . 2 6 1 . 5 7 O O 8 4 7 9 8 0 i 5 8 5 l 2 9 0 x5 . 0 0 l 4 0 O 0 2 9 1 2 4 1 . 5 4 0 O 7 7 4 47 0 0 8 9 3 6 5 0 0 0 0 1 8 O 0 9 4 5 6 . 3 6 2 . 5 4 0 0 5 1 9 9 0 0 9 1 9 4 0 x1 . 0 0 4 8 2 . 2 6 1 5 9 0 0 8 7 1 6 1 8 2 4 l 9 3 1 5 5 5 O O o 2 3 0 0 0 9 4 5 5 4 2 2 .1 7 1 9 3 8 6 . 3l 3 3 81 0 x1 o 0 . 3 2 3 7 2 . 1 5 0 0 3 4 2 6 0 2 8 2 . 5 3 0 1 2 3 6 5 0 0 0 ( 3 6 4 0 0 9 5 3 2 . 41 6 5 4 . 3 7 t . 6 6 0 1 5 4 7 9 0 x2 . O3 0 4 5 .3 7 3 4 300 6 3. 5 6O 14 7 4 7 .3 6 4 4 6 7 0. 0 0 5 3 0. 2l 2 . 1 4 0. 3 5 4 1 7 9 6【 7 2 0 O 0 1 . 2 2 0 x5 0 0 3. 6 0 0 8 2 1 6 0 3 2 6 9 0 O O 9 9 0 9 3 8 9 9 7 1 0 0 0 3 21 9 0x 0

0 0 7 0. 2 0 2 9 7 0 0 2 8 4 2 1 6 9 7 5 1 7 3 3 O 8 4 9 3 4 4 2 . 9 4 0. 1 4 t 9 5 0. l4 4 31 6 7 1 0 0 0 5 4 0 0. 3 9 2 6 8 0 8 j . 6 20. 3 6 i 2 4 1 6 3 9 0x 5 0 0 9 3 0 7 3 1 30. 4 5 6 1 l 1 4 3 6 0 0. 3 8 8 51 5 7 0 0x2 0. 0 0 5. 7 7 0 0 8 5 0. 3 2 1 1 5 5 0 7 1 8 1 8 8 7 81O 4 3 5 1 0 8 3 . 7 9 0 0 4 l . 4 2 0 4 2 1 . 8 l 7 4 51 2

同规模的调度实例，工件 n:1,0 3,0,0 7, 02,0 4 5,0机床 m=5,1,5 2,量为等量分配，()∈U[,, i )EU[, O 1,O批 z 16] P(, 1

3]蛙跳算法的参数设置： 1。种群个体数 P=n子群个数 p , m=5。为了公平比较，各算法采用相同的 C U计算时间 T=1 P 0× mx n为终止条件，每个实例独立运行 3。以相对偏差作为 0次评价标准：R : x10 0 ( 1 1)

1 0 x5 . O( 4 0 8 0 0 6 I 8 7 4 4 4 4 6 9 6 6 5 7 9 3 0 0 0 3 O 8 2 . 1 5 3 0 7 0 0 1 1 7 8 0 0 1 1 7 0 0 0 3 21 2 l 9 2 1 0 x1 0 0 6 8 . 3 7 0 9 6 5 1 1 . 3 1 3 j 8 8 0 1 3 3 0 2 0 0 0 0 0 4 7 2 0 0 l 2 5 6 0 0 5 3 63 3 0 2 0 3 9 3 2 8 2. 1 5 i 0 x1 . o 0 0 5 O O 0 4. 7 0 0 6 2 . 9 2 O O 0; . 6 6 O 4 7 6 7 2】 16 51 2 4 3 02 . 3 7 7 9 7 6 l 8 1 4 1 5} 2 ( 0 4 0 .3 3

其中：代表算法 i行第个算例第 k次计算的性能指标； A运

1 0 x2 00 7 3 7 0 0 5 5 3 0 6 5 8 l0. 6 4 5 2 0 . 6 0 5 5 9 0 0 0 0 0 6 9 4 7 1 4l 5 0. 6 8 6 l l 1 7; o 8 O 1 8 6 4 9Ie n 0 (￣0 l 5 . 2 7 8 4l 6 0 0 2 t 7 8

85 I . 4 3 0 0 6 2 . 3 6/ a l KO 2 5 2 0 0 2【 3 3 8 4. 5 8 0 0 2 2 7 . 9 4 7 U 2

R I代表算法 i Po k运行第个算例时计算第 k次的相对偏差值；』 4代表运行第个算例第 k次时的最小指标值。MR I为算 P

参考文献：[] K MA 1 U R S,B G H A C IT P,S IKA D R J H C o semi R S N A A A .Lt￣ a n g a dshd l ghuits r mahn 0w ifw hp[] Co n ceui er i n sc f m— cieq一 a o sosj . r o t l n

法i运行第个算例时的平均相对偏差值，即P o RI k

M P I R I= _

(2 1)

p tr Id sr l n ie r g2 0,8 1:4— 7 . ues& n uta E gn ei,0 0 3 ( ) 19 12 i n

显然， P越小， MR I算法的优化质量越高。 8 2算法比较 .将文献提出的 A O、 A、 E和 G算法进行相应的修 C T H A A

[ 2] E MMO SH,MA HU N T R K.Ltsigi ow if w so[] o in an— a o hp J . z n t lOp rt n e e rhL t r,19 1 4:5 6 . eai sR s ac et s 95,7( ) 19 14 o e

[] E B L A IE, E A YT, R E S ND. o pr o mog v 3 L E T G H G Z G I R O C m ai na n e s i f eo t nr—ae pii tn lo tm J . A v n e E g— vl i ayb sd ot z i a rh s[] d a c d n i uo m ao g in eigIfr ts 20 1 ( ) 4— 3 e r omai,0 5,9 1:3 5 . n n c

改，用于解决批量无等待流水线调度问题，参数按照文献所述进行设置。几种算法的 MR I P和方差 ( D) S的比较如表 2所示。由表 2可见：

[]吴华丽， 4汪玉春，陈坤明，基于混合蛙跳算法的成品油管网优等.化设计[]石油工程建设，0 8( ) l - 6 J. 20 1:4 1 . []朱光宇， 5林蔚清.于改进混合蛙跳算法的贴片机贴装顺序优化基[]中国工程机械学报，0 8 6 4:2— 3 . J. 20,

( )4 8 4 2 []陈功贵， 6李智欢，陈金富，含风电场电力系统动态优化潮流的等.混合蛙跳算法[]电力系统自动化，09 4:5 3 . J. 20 ( )2 0

a对于所有的测试问题，F A算法获得的 M P和 S ) SL RI D均优于 A O、A、 E C T H A和 G A得到的 MR I S P和 D。

b SL ) F A的平均 M P和 S ( .0 0 25 2 ) R I D 0 0 0/ .15均优于 A O C( . 2 7 1 . 16、 A ( . 3 82 . 58) H A ( . 82 0 02/ 8 4 3 ) T 0 02/4 7 8、 E 0 05/

2 .4 3、 A( .9 4 2 .36,明 S L 62 7 ) G 0 06/ 70 2 )说 F A不仅有较高的求解质量，还具有较高的稳定性。

[] R D SF UZR,B R O E D A .N whg efr n e 7 A ,R I O O J R I N N e i p r mi h u h o g rt s o mnmin ksa pr tinfw hp[] T eI— ii r ii z gmaepni emuao o sosJ . h sc f i n t l ntrain l o ra o n g me tS ine, 09,7 2:3— en t a J un l fMa a e n ce c 20 3 ( ) 3 1 o 3 5. 4

c对于所有测试问题，F A算法的所有 MR I ) SL P均为 0说，明每次运行 SL FA均取得了最好的结果。

[ MARMU T ,P N AMB L 8 1 I L HU S O N A AM S G,J WA AR N E o - A H . vl ut n r lo ih rs h d ln ma hie f w h p w t o te m— i a y ag r msf c e u i gm— c n o s o i lt r a o t o l h s

i n g[J . R b ts n C mp trne rtd] o oi a d o ue tgae Ma ua tr g c I n fcui, n

9结束语SL F A是最近发展起来的一种群智能算法，对它的研究尚处于起步阶段，由于它所表现出来的优越性能正引起越来越但多的关注。根据 L F P的特点， NS在传统蛙跳算法模型的基础

20,4( ):2— 3 . 0 82 1 1 5 19[ M I L H,P N A AAM J 9 ARMU T US O N MB I 1 SG, AWAH R

N heh l A .T rsoda c p ig a d a t oo y o t z t n ag rt m r s h d l g m— - c e tn n n - l n p i ai oih f c e u i ma c mi o l o n

c ief w s o i o t a ig J .J u a o td l r - hn o h p w t lts e m n『 l h r 1 o r l f Mae a o n P

c s igT c n lg, 0 9 2 9 2:0 6 14 . e sn e h oo y 2 0,0 ( ) 12— 0 1

本文来源：https://www.bwwdw.com/article/9eoe.html