《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 嵌入式技術(shù) > 業(yè)界動(dòng)態(tài) > 改進(jìn)的蟻群算法求解置換流水車間調(diào)度問題

改進(jìn)的蟻群算法求解置換流水車間調(diào)度問題

2015-05-19
作者:張麗萍
來源:2014年微型機(jī)與應(yīng)用第12期

  摘  要: 針對(duì)螞蟻算法在求解置換流水車間調(diào)度問題時(shí)易陷入局部最優(yōu)以及計(jì)算時(shí)間較長(zhǎng)的缺點(diǎn),對(duì)最大最小螞蟻系統(tǒng)(MMAS)進(jìn)行了改進(jìn)。在該算法中,采用NEH啟發(fā)式算法提高初始解質(zhì)量,并通過自適應(yīng)的調(diào)節(jié)策略進(jìn)一步提高蟻群算法的搜索能力。運(yùn)用提出的混合算法求解Taillard基準(zhǔn)測(cè)試集,并將測(cè)試結(jié)果與其他算法進(jìn)行比較,驗(yàn)證了該調(diào)度算法的有效性。

  關(guān)鍵詞: 置換流水車間調(diào)度問題;自適應(yīng); NEH啟發(fā)式算法

  置換流水車間是很多實(shí)際流水線生產(chǎn)調(diào)度問題的簡(jiǎn)化模型,是目前研究最廣泛的一類經(jīng)典的調(diào)度問題。由于置換流水車間調(diào)度問題屬于NP-hard難題,不存在多項(xiàng)式精確求解算法,因此,對(duì)這類問題的研究具有重要意義。

  求解置換流水車間調(diào)度問題的方法大致可以分為三類[1]:經(jīng)典算法(如線性規(guī)劃、動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃、分枝定界等)、啟發(fā)式算法(如Gupta法、Palmer法、Johnson法、CDS法、NEH法等)和基于人工智能的元啟發(fā)式算法(如模擬退火、禁忌搜索、遺傳算法、螞蟻算法等)。經(jīng)典算法的計(jì)算復(fù)雜性一般很大,只適合求解小規(guī)模置換流水車間調(diào)度問題,在工程中往往不實(shí)用。啟發(fā)式算法通過一定的規(guī)則可以快速地構(gòu)造出問題的解,但通常解的質(zhì)量較差[2]?;谌斯ぶ悄艿脑獑l(fā)式算法能夠較快地構(gòu)造出問題的解,因此,在置換流水車間調(diào)度問題中被廣泛使用。

  蟻群算法是受到自然界中真實(shí)螞蟻的啟發(fā),由意大利學(xué)者DORIGO M于1991年提出的一種元啟發(fā)式算法。該算法具有魯棒性和通用性等良好特性,在求解作業(yè)車間、流水車間等調(diào)度問題上取得了較好的效果。但是,傳統(tǒng)的蟻群算法存在計(jì)算時(shí)間長(zhǎng)和易陷入停滯的問題,故本文從結(jié)合NEH算法和自適應(yīng)調(diào)節(jié)策略兩方面來改善蟻群算法的性能,經(jīng)Taillard基準(zhǔn)測(cè)試驗(yàn)證,改進(jìn)后的蟻群算法有效。

  1 問題描述

  置換流水車間調(diào)度問題研究的是n個(gè)工件在m臺(tái)機(jī)器上的流水加工過程,所有工件以相同的順序在每一臺(tái)機(jī)器上加工完成,同時(shí)約定每個(gè)工件在每臺(tái)機(jī)器上只加工一次,每臺(tái)機(jī)器每次最多只能加工一個(gè)工件,各工件在各機(jī)器上所需的加工時(shí)間已知,要求得到某調(diào)度方案使得總加工時(shí)間最小。定義J=(j1,…,jn)為所有機(jī)器上的一個(gè)加工排序,ti,j為操作的執(zhí)行時(shí)間,Ci,j表示操作的完成時(shí)間。則加工任務(wù)jk在機(jī)器i上的完成時(shí)間C按式(1)計(jì)算:

  1.png

  2 蟻群算法

  2.1 蟻群算法簡(jiǎn)介

  螞蟻是一種沒有視覺的動(dòng)物,但是它們可以通過信息素,協(xié)同找到食物和巢穴之間的最短路徑[3]。螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)的存在及其強(qiáng)度,并以此指導(dǎo)自己的運(yùn)動(dòng)方向,使螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向運(yùn)動(dòng)。這樣,由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種自催化的正反饋行為,較短路徑上會(huì)有較多的信息素累積,越來越多的螞蟻選擇信息素濃度高的路徑,而其他路徑上的信息素濃度卻會(huì)隨時(shí)間衰減,最終蟻群能找到一條從食物源到巢穴的最短路徑[4]。

  蟻群算法最初用于解決旅行商問題,之后陸續(xù)滲透到其他領(lǐng)域中。較早把蟻群算法應(yīng)用到置換流水車間問題的是YING K C和LIAO C J,后者在Tailard的benchmark問題上做了測(cè)試,證實(shí)該方法非常有效。

  2.2 蟻群算法

  本文以求解置換流水車間問題說明MMAS模型。求解這類問題有兩種解構(gòu)造模式,分別為弧模式和節(jié)點(diǎn)模式[5]。本文采用的是節(jié)點(diǎn)模式。

  在解構(gòu)造的結(jié)點(diǎn)模式下,代表流水車間調(diào)度問題的有向圖G=(N,A),如圖1所示。其中,N={Oij}是圖中的節(jié)點(diǎn)集合,節(jié)點(diǎn)Oij代表作業(yè)j 位于作業(yè)處理序列π的第i個(gè)位置;A是圖G中部分連接節(jié)點(diǎn)集N中各節(jié)點(diǎn)的有向弧的集合,連接節(jié)點(diǎn)Oij和O(i+1),l的有向弧方向?yàn)閺腛ij~O(i+1),l。這里的路徑選擇概率為:

  16BDH58ABN0HID(HXW1NWH3.png

001.jpg

  在節(jié)點(diǎn)模式下,式(2)中Nk(Oij)={O(i+1),l|l?埸π′}代表節(jié)點(diǎn)Oij的可行領(lǐng)域集合。其中τij和ηij分別代表對(duì)應(yīng)于節(jié)點(diǎn)Oij的信息素濃度和基于問題的啟發(fā)式信息。p表示人工蟻搜索過程中從節(jié)點(diǎn)O(i-1)π(i-1)移到節(jié)點(diǎn)Oij的概率。

  從虛構(gòu)節(jié)點(diǎn)job0出發(fā),按照式(2)給出的狀態(tài)遷移規(guī)則,在G圖中一步步地構(gòu)造出問題的解,蟻群算法的流程如下:

  (1)設(shè)置參數(shù)。設(shè)置迭代次數(shù)counter=0,設(shè)置最大迭代次數(shù)Ncmax。計(jì)算每個(gè)工件的總加工時(shí)間Si(i=1,…,n),定義能見度ηij=Si。按照工件總加工時(shí)間Si最大優(yōu)先的原則計(jì)算出最大流程時(shí)間makespan,設(shè)置信息素賦初始值τ0=1/((1-ρ)·makespan);τmax=τ0,τmin=τmax/5。

  (2)初始化m個(gè)螞蟻,將m個(gè)螞蟻放在虛擬節(jié)點(diǎn)job0上。

  (3)每個(gè)螞蟻都按照式(2)選擇下一步路徑。

  (4)將新選擇的工序添加到禁忌表中,判斷是否遍歷了所有的工件,是則執(zhí)行步驟(5),否則執(zhí)行步驟(3)。

  (5)按照式(3)更新信息素。

  τij=ρ·τij+?駐τij(3)

  其中,ρ為信息素殘留系數(shù)(1-ρ為揮發(fā)系數(shù));Δτij=1/Cbest,令Cbest為迭代以來最優(yōu)解,|Cbest|為Cbest的makespan值,如果Cbest中位置j上工件不為i,則Δτij為0,否則Δτij=1/|Cbest|。信息素取值區(qū)間為[τmin,τmax],若τij>τmax,則設(shè)定τij=τmax;若τij>τmin,則設(shè)定τij=τmin。這樣可以較好地防止早熟現(xiàn)象。

  (6)count++。如果count<Ncmax,則清空禁忌表,返回步驟(2)繼續(xù)執(zhí)行;否則,結(jié)束循環(huán)。

  3 MMAS的優(yōu)化

  3.1 NEH啟發(fā)式算法

  NEH啟發(fā)式算法是由NAWAZ M、ENSCORE E、和HAM I共同提出的算法[6],該算法步驟如下:

  (1)按n個(gè)工件在機(jī)器上總加工時(shí)間遞減的順序排列各個(gè)工件。

  (2)取前兩個(gè)工件調(diào)度使部分最大流程時(shí)間達(dá)到極小。

  (3)從k=3~n把第k個(gè)工件插入到k個(gè)可能的位置,求得最小部分的最大流程時(shí)間。

  3.2 與NEH算法的結(jié)合

  (1)獲取初始解。利用NEH啟發(fā)式算法計(jì)算得到最大流程時(shí)間makespan,并定義τ0=1/((1-ρ)·makespan)。

  (2)部分NEH局部搜索。在使用MMAS構(gòu)造出路徑之后,對(duì)構(gòu)造的工件順序按照NEH啟發(fā)式算法的步驟(2)、(3)構(gòu)造出解。利用NEH啟發(fā)式算法進(jìn)行局部尋優(yōu),可以進(jìn)一步提高M(jìn)MAS的求解質(zhì)量。但是為了保證算法的時(shí)間效率,在此只對(duì)Nmax次迭代中的前N次迭代利用NEH啟發(fā)式算法對(duì)迭代最優(yōu)螞蟻進(jìn)一步局部尋優(yōu)。

  3.3 自適應(yīng)信息素?fù)]發(fā)系數(shù)

  與NEH算法相結(jié)合,雖然極大程度地提高了MMAS解質(zhì)量,但是也從一定程度上加速了MMAS的局部收斂速度。為此,本文引入自適應(yīng)改變揮發(fā)度系數(shù)的方法,以進(jìn)一步提高M(jìn)MAS的全局搜索能力。

  在算法模型中,信息素?fù)]發(fā)系數(shù)ρ的大小直接關(guān)系到蟻群算法的全局搜索能力及收斂速度[3]。ρ過小,從未被搜索到的節(jié)點(diǎn)的信息量會(huì)減少到接近于0,降低了算法的全局搜索能力;而ρ過大,以前搜索過的解被選擇的可能性過大,也會(huì)影響到算法的全局搜索能力。因此可以自適應(yīng)地改變?chǔ)训闹担?dāng)最優(yōu)值在一定循環(huán)次數(shù)內(nèi)沒有明顯改變時(shí),降低ρ的值。公式如下:

  ρnew=0.95ρold    0.95ρold≥ρmin

  ρmin            其他(4)

  其中,ρmin為ρ的最小值,用來防止ρ過小,降低算法收斂速度。

  3.4 改進(jìn)MMAS的實(shí)現(xiàn)流程

  改進(jìn)后的MMAS算法求解置換流水車間問題的流程圖如圖2所示。

002.jpg

  (1)初始化各個(gè)參數(shù)。設(shè)置螞蟻數(shù)量為m、迭代次數(shù)counter=0、最大迭代次數(shù)為Ncmax、局部搜索次數(shù)為N。計(jì)算每個(gè)工件的總加工時(shí)間Si(i=1,…,n),定義能見度ηij=Si。設(shè)置信息素殘留系數(shù)為ρ,ρmin為ρ的最小值,定義Nm次迭代最優(yōu)解相同,則判定陷入局部最優(yōu)。

  (2)利用NEH啟發(fā)式算法得到總加工時(shí)間的初始值makespan,設(shè)置τ0=τmax=1/((1-ρ)·makespan),τmin=1/5·τmax。

  (3)將各只螞蟻放在虛擬節(jié)點(diǎn)job0上,對(duì)于每只螞蟻,按照式(2)選擇下一步路徑,直到所有螞蟻均構(gòu)造出解。

  (4)若count<N,則利用NEH啟發(fā)式算法的后兩步對(duì)最優(yōu)迭代螞蟻選擇的路徑做進(jìn)一步局部尋優(yōu);否則,執(zhí)行步驟(5)。

  (5)判斷迭代最優(yōu)解相同次數(shù)小于Nm,則執(zhí)行步驟(6);否則,按照式(4)改變揮發(fā)系數(shù)的值,再執(zhí)行步驟(6)。

  (6)按照式(3)進(jìn)行信息素的更新,檢查信息素的邊界,使其保持在[τmin,τmax]的范圍內(nèi)。

  (7)count++。如果count<Ncmax,清空禁忌表,返回步驟(3)繼續(xù)向下執(zhí)行;否則,結(jié)束循環(huán),輸出結(jié)果。

  4 仿真實(shí)驗(yàn)

  本文測(cè)試數(shù)據(jù)采用Taillard在1993年提出的基準(zhǔn)測(cè)試問題,并將運(yùn)行結(jié)果與其他參考文獻(xiàn)提出的算法進(jìn)行比較,以此驗(yàn)證提出的改進(jìn)蟻群算法是有效的。

  本文算法各參數(shù)設(shè)置如下:螞蟻個(gè)數(shù)na=20,揮發(fā)系數(shù)ρ=0.99,揮發(fā)系數(shù)最小值ρmin=0.5,α=1.0,β=4.0,最大迭代次數(shù)為300,局部搜索次數(shù)為10。本文選取每種規(guī)模系列問題中的第一個(gè)問題進(jìn)行計(jì)算,并與NEARCHOU A C[5]提出的算子遺傳算法(GA)、Lian Zhigang[7]提出的NPSO粒子群算法進(jìn)行比較,每個(gè)算例連續(xù)運(yùn)行20次,記錄其中的最優(yōu)結(jié)果,如表1所示。其中,BS表示運(yùn)行結(jié)果中的最優(yōu)解,RPD(Relative Percentage Deviation)表示相對(duì)誤差百分率。由表1可知,相比其他兩種算法,本文提出的算法在求解Taillard系列問題方面能夠更好地收斂在最優(yōu)解附近。

003.jpg

  本文針對(duì)解置換流水車間調(diào)度問題提出了一種改進(jìn)的蟻群算法。在該算法中,采用NEH算法產(chǎn)生初始解,并利用自適應(yīng)揮發(fā)系數(shù)的方法避免算法早熟,使分散搜索和集中搜索達(dá)到有效平衡,提高了算法的搜索能力。Taillard系列基準(zhǔn)問題測(cè)試表明,本文的算法是有效的。

  參考文獻(xiàn)

  [1] 高海兵,周馳.廣義粒子群優(yōu)化模型[J].計(jì)算機(jī)學(xué)報(bào),2005,28(12):1980-1987.

  [2] 王凌.車間調(diào)度及其遺傳算法[M].北京:清華大學(xué)出版社,2003.

  [3] 李士勇.蟻群算法及其應(yīng)用[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2004.

  [4] 吳啟迪,汪鐳.智能蟻群算法及其應(yīng)用[M].上海:上??萍冀逃霭嫔纾?004.

  [5] NEARCHOU A C.The effect of various operators on the genetic search for large scheduling problems[J].InternationalJournal of Production Economy,2004,88(1):191-203.

  [6] NAWAZ M,ENSCORE E,HAM I.A heuristic algorithm forthe mmachine,n job flow shop[J].The International Journalof Management Sciences,1983,11(1):91-95.

  [7] Lian Zhigang,Gu Xingsheng,Jiao Bin.A Novel particle swarmoptimization algorithm for permutation flow shop scheduling to minimize makespan[J].Chaos,Solitons and Fractals,2008,35(5):851-861.


本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點(diǎn)。轉(zhuǎn)載的所有的文章、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者。如涉及作品內(nèi)容、版權(quán)和其它問題,請(qǐng)及時(shí)通過電子郵件或電話通知我們,以便迅速采取適當(dāng)措施,避免給雙方造成不必要的經(jīng)濟(jì)損失。聯(lián)系電話:010-82306118;郵箱:aet@chinaaet.com。