求解混流裝配線調(diào)度的疫苗共生克隆選擇算法*

劉冉 樓佩煌 唐敦兵 楊雷

(1.南京航空航天大學(xué)機(jī)電學(xué)院,江蘇南京 210016;2.江蘇天奇物流系統(tǒng)工程股份有限公司,江蘇無錫 214187)

在實(shí)際應(yīng)用中,混流裝配線(MMAL)經(jīng)常需要同時(shí)考慮幾種互相存在沖突的目標(biāo)函數(shù).因此,混流裝配線調(diào)度優(yōu)化問題的理論研究逐漸從單目標(biāo)優(yōu)化問題轉(zhuǎn)變?yōu)槎嗄繕?biāo)優(yōu)化問題.部分學(xué)者采用目標(biāo)權(quán)重法解決混流裝配線的多目標(biāo)調(diào)度優(yōu)化問題,如Bard等[1]考慮了最小化生產(chǎn)線長(zhǎng)度和平順化零件消耗率兩個(gè)優(yōu)化目標(biāo),并用禁忌搜索對(duì)加權(quán)后的目標(biāo)函數(shù)求解,Tavakkoli-Moghaddam等[2]加權(quán)處理了最小化總公共作業(yè)時(shí)間成本,平順化生產(chǎn)率,最小化設(shè)備更換成本3個(gè)目標(biāo)函數(shù),并用Memetic算法解決了兩種規(guī)模的調(diào)度優(yōu)化問題.但是,用加權(quán)目標(biāo)函數(shù)法解決多目標(biāo)優(yōu)化問題需要依賴先驗(yàn)知識(shí)確定權(quán)重系數(shù),且只能找到解空間的部分解,有一定的局限性.為彌補(bǔ)這個(gè)缺陷,基于Pareto最優(yōu)的多目標(biāo)優(yōu)化算法得到了廣泛應(yīng)用.比較有代表性的有:Hyun等[3]提出了層次小生境遺傳算法,用于解決最小化總效用時(shí)間等 3個(gè)目標(biāo)函數(shù)的排序問題,基于小生境的選擇機(jī)制可以維持解的多樣性,從而得到更均勻的Pareto前端;McMullen等[4]用多目標(biāo)遺傳算法,研究了以最小化設(shè)備更換成本和平順化零件使用率為目標(biāo)函數(shù)的排序問題;Mansouri[5]結(jié)合非支配搜索策略和小生境選擇機(jī)制,提出一種遺傳算法重新研究了McMullen的問題模型;蘇平等[6]提出改進(jìn)的遺傳模擬退火算法同時(shí)優(yōu)化了最小生產(chǎn)循環(huán)周期和零部件消耗率兩個(gè)目標(biāo)函數(shù).該算法借助模擬退火算法對(duì)適應(yīng)度尺度進(jìn)行調(diào)整,以改善遺傳算法的早熟收斂問題.

以上分析可以看出,多目標(biāo)遺傳算法作為解決混流調(diào)度問題的主要方法得以廣泛研究.但是遺傳算法一直存在早熟收斂這個(gè)缺陷,多目標(biāo)優(yōu)化算法最后要得到一個(gè)多樣解群體,這個(gè)缺陷會(huì)嚴(yán)重影響算法的結(jié)果質(zhì)量.盡管針對(duì)這個(gè)缺陷的各種改善方法被大量提出,但是其本身依然有局限性,即采用小生境選擇機(jī)制的遺傳算法[3,5],其結(jié)果的優(yōu)劣過于依賴小生境參數(shù)的選取,遺傳模擬退火算法對(duì)適應(yīng)度差異的拉伸會(huì)導(dǎo)致潛在最優(yōu)解的丟失等[6].通過借鑒自然免疫系統(tǒng)而得到的克隆選擇算法,因?yàn)槠渥陨砀哳l變異及抗體評(píng)價(jià)的特性,可以抑制相似解的大量繁殖,能有效避開遺傳算法的早熟收斂問題[7],更適于多目標(biāo)優(yōu)化問題的求解.文中針對(duì)多目標(biāo)的混流裝配線調(diào)度優(yōu)化問題,提出一種疫苗協(xié)同進(jìn)化的免疫克隆選擇多目標(biāo)優(yōu)化算法(MO-VECSA).此算法不僅有抗體群,還設(shè)計(jì)了疫苗種群,并定義了相關(guān)進(jìn)化操作;針對(duì)目標(biāo)函數(shù)之間存在沖突的問題,采取從最優(yōu)個(gè)體中提取疫苗,進(jìn)化后又去注射給抗體群,以提高抗體群質(zhì)量;針對(duì)待求問題的離散性,改進(jìn)了克隆選擇算法中抗體親和度的評(píng)價(jià)方式.最后,通過兩組不同的數(shù)值仿真實(shí)驗(yàn),驗(yàn)證了文中提出算法的有效性.

1 多目標(biāo)混流裝配線調(diào)度模型

在一個(gè)計(jì)劃周期內(nèi),混流裝配線上共裝配M種產(chǎn)品,第m種產(chǎn)品的需求量為Dm,則M種產(chǎn)品總需求量為在實(shí)際生產(chǎn)中,采用MPS (Minimum Part Set)法.如果M種產(chǎn)品總需求量的最大公約數(shù)為h,MPS為一向量集(d1,…,dm)=(D1/.在調(diào)度過程中,只對(duì)位產(chǎn)品進(jìn)行排序,重復(fù) h次,即可得到所有產(chǎn)品的投產(chǎn)順序.

文中選擇最小化零部件消耗率及最小化設(shè)備更換成本這兩個(gè)較為常見的目標(biāo)進(jìn)行優(yōu)化.這兩個(gè)標(biāo)準(zhǔn)在很多文獻(xiàn)中都作為混流裝配線排程優(yōu)化的目標(biāo)函數(shù)[2,5,8].表達(dá)式如下:

(1)最小化零部件消耗率

如果序列中第1個(gè)產(chǎn)品是m型,二元決策變量xlm值為 1,其它情況為 0.式中第 1項(xiàng)為到第 i個(gè)已裝配的產(chǎn)品為止,m型產(chǎn)品出現(xiàn)的比率;第2項(xiàng)為m型產(chǎn)品的數(shù)量占所有產(chǎn)品的比率,也即期望生產(chǎn)率.

(2)最小化生產(chǎn)準(zhǔn)備成本

式中:Cjmr為在工作區(qū)間j生產(chǎn)m型產(chǎn)品轉(zhuǎn)換成r型產(chǎn)品所消耗的生產(chǎn)成本;J為工作區(qū)間總數(shù).在一個(gè)生產(chǎn)序列中,當(dāng)?shù)趇位產(chǎn)品模型為m而i+1位為r時(shí),二元決策變量 ximr為 1,其余情況則為 0.

2 MO-VECSA的算法設(shè)計(jì)

在人工免疫系統(tǒng)中,對(duì)于某特定抗體 a,給其接種疫苗是指按照先驗(yàn)知識(shí)來修改 a的某些基因位上的基因或者分量,使得此抗體以較大的概率具有更高的適應(yīng)度[7].某些情況下,針對(duì)待求問題很難獲得較為準(zhǔn)確的先驗(yàn)知識(shí),例如文中列舉目標(biāo)模型,從直觀上分析,如果想降低設(shè)備更換成本,那么同種模型的生產(chǎn)應(yīng)該越密集越好,但是這樣的生產(chǎn)模式勢(shì)必引起出產(chǎn)率的不均勻,從而影響零部件消耗率的平順化.因此,文中采取另一種方式,從最佳個(gè)體基因中提取疫苗.MO-VECSA算法的具體設(shè)計(jì)如下.

2.1 抗體和疫苗的編碼

2.1.1 抗體編碼

針對(duì)混流調(diào)度這一特定問題,采用產(chǎn)品的投產(chǎn)順序直接編碼,每個(gè)基因位對(duì)應(yīng)一個(gè)產(chǎn)品的品種,如最小生產(chǎn)循環(huán)(d1,d2,d3)=(5,3,2)的一種排序方式的抗體編碼為:“AABBBCCAAA”.

2.1.2 疫苗編碼

文中依據(jù)目標(biāo)函數(shù)的特點(diǎn),設(shè)計(jì)隨機(jī)抽取最佳抗體的基因片段生成疫苗,如圖 1所示.“*”為通配符,僅為記錄疫苗片斷在主抗體中的位置而設(shè)計(jì),不參加任何操作.

圖1 疫苗的生成Fig.1 Generation of vaccine

2.2 產(chǎn)生初始種群

因?yàn)樗惴ㄩ_始時(shí)并沒有優(yōu)良抗體提供必要信息,這里定義初始疫苗種群為一空的集合,即 V0←,疫苗種群的大小取為抗體群大小的 10%.抗體群A0則隨機(jī)生成.

2.3 抗體種群的進(jìn)化

2.3.1 抗體的評(píng)價(jià)并生成自適應(yīng)克隆算子

免疫算法中,克隆比率一般取為抗體的抗體親和度和抗原親和度的函數(shù).抗體親和度衡量抗體之間的相似程度,抗原親和度度量解與目標(biāo)的匹配程度.標(biāo)準(zhǔn)的克隆免疫算法只把抗體編碼的相似程度作為抗體親和度的評(píng)價(jià)參數(shù)[8],而混流裝配線調(diào)度問題的決策變量和目標(biāo)函數(shù)之間并不是一一映射的關(guān)系,即不同的編碼方式可能產(chǎn)生相同的目標(biāo)函數(shù)值,單從抗體的基因型來評(píng)價(jià)是不夠的,還需要考慮目標(biāo)函數(shù)值的影響.因此文中算法提出把抗體的基因型(編碼)和表現(xiàn)型(目標(biāo)函數(shù))同時(shí)作為抗體親和度的參數(shù).

抗體解碼后,可以將抗體群基于非支配分級(jí)[9],第一級(jí)的抗體集即為全種群的非支配集.設(shè)抗體群依據(jù)目標(biāo)函數(shù)的非支配關(guān)系,共被分為 R個(gè)質(zhì)量等級(jí).ai和aj同為質(zhì)量級(jí)r內(nèi)的兩個(gè)抗體.r值越小,抗體質(zhì)量越高,則抗體與抗原匹配程度越高.抗體ai抗原親和度ξai設(shè)計(jì)為

基因型親和力定義為

式中:HD(ai,aj)為ai和aj的海明距離.

表現(xiàn)型親和力設(shè)計(jì)為

式中:dai為抗體ai的擁擠距離[9].dmax為ai所在質(zhì)量級(jí)所有抗體的擁擠距離最大值.抗體的擁擠距離小,說明其與相鄰抗體的目標(biāo)函數(shù)取值接近,這樣不利于得到分布均勻的pareto前端,應(yīng)該抑制其大量繁殖.

綜上所述,ai的自適應(yīng)克隆算子Cai為

式中:Int(?)為上取整函數(shù);φ為與克隆規(guī)模有關(guān)的可調(diào)系數(shù).

2.3.2 抗體的變異

抗體自適應(yīng)變異率εt設(shè)計(jì)如下:

式中:δ為衰退因子;ε0為初始變異率;t為進(jìn)化代數(shù); ri為質(zhì)量級(jí)數(shù).這種動(dòng)態(tài)的選取可在進(jìn)化早期維持較高的變異率,而在后期種群趨于成熟時(shí)減小擾動(dòng),有利于算法的收斂.這種變異率還賦予質(zhì)量等級(jí)較低的抗體更高的活性,增大其轉(zhuǎn)化為優(yōu)秀抗體的幾率.

2.3.3 產(chǎn)生新抗體群

抗體群At經(jīng)過克隆,變異操作后,種群空間得以擴(kuò)張.由于變異后子代個(gè)體質(zhì)量參差不齊,有必要淘汰劣質(zhì)個(gè)體,以維持種群大小的衡定.算法采取按照質(zhì)量等級(jí)依次對(duì)每層的抗體進(jìn)行局部非支配分級(jí)并保存每層抗體的非支配解集,以生成新抗體群 At+1.算法在每次迭代過程中都采取這種局部尋優(yōu)操作,加快了算法的收斂速度,同時(shí)又考慮到非最優(yōu)解集中的優(yōu)秀個(gè)體并將其保留至新抗體群,增強(qiáng)了種群的多樣性,防止算法早熟收斂.

2.4 疫苗種群的進(jìn)化

2.4.1 疫苗注射

疫苗注射操作如圖 2所示.對(duì)抗體 ai和疫苗vi,注射疫苗定義為,將vi的基因替換 ai中相應(yīng)位置的基因片斷,并修改 ai其余部分的基因,使其滿足最小生產(chǎn)循環(huán)的比率;如果注射后的抗體a′i支配ai,則a′i取代ai.

圖2 疫苗注射操作Fig.2 Operator of vaccination

2.4.2 疫苗評(píng)價(jià)與更新

設(shè)疫苗vi有Γvi次注射機(jī)會(huì),注射后有個(gè)新抗體支配并替代了老抗體,則疫苗vi的適應(yīng)度值定義如下:

式中:γ為小于 1的衰退系數(shù);Ω為疫苗注射成功率的期望閾值.進(jìn)化過程中,適應(yīng)度低于 0的疫苗將被淘汰.新疫苗則在抗體群非支配集的不同個(gè)體中隨機(jī)抽取.在算法運(yùn)行過程中,每經(jīng)歷一定代數(shù),適應(yīng)度值最高的疫苗有進(jìn)化的機(jī)會(huì),在此定義為注射次數(shù)的增加,即Γi=Γi+1.

2.5 MO-VECSA算法流程

圖3是MO-VECSA的算法流程,實(shí)線箭頭表示種群自身的進(jìn)化過程,而虛線箭頭表示種群之間信息的傳遞.疫苗種群從抗體種群中獲得最優(yōu)解的部分基因信息,經(jīng)過自身評(píng)價(jià)并進(jìn)化后又去注射給抗體種群,以提高抗體種群的整體質(zhì)量.兩者相互影響又獨(dú)立成長(zhǎng),最終實(shí)現(xiàn)協(xié)同進(jìn)化.

圖3 MO-VECSA流程圖Fig.3 Flowchart of MO-VECSA

3 實(shí)例仿真與算法比較分析

3.1 疫苗種群對(duì)克隆選擇算法的影響

為了對(duì)疫苗種群對(duì)算法的影響進(jìn)行分析,文中設(shè)計(jì)了只有一個(gè)抗體群的克隆選擇算法(MOCSA)并與之進(jìn)行比較.MOCSA沒有接種疫苗的操作,其余進(jìn)化過程則與MO-VECSA類似.

某企業(yè)一混流裝配線生產(chǎn)3種產(chǎn)品,MPS比例為 6∶2∶2.為計(jì)算方便,假設(shè)生產(chǎn)成本只發(fā)生在第一工作區(qū)間,具體數(shù)值見表1.Pareto最優(yōu)解集見表2. MO-VECSA抗體種群大小為50,迭代次數(shù)為50,ε0= 0.1,δ=0.02,γ=0.8,Ω=0.5.MOCSA種群大小、迭代次數(shù)、變異率等均與MO-VECSA相同.

表1 設(shè)備更換成本Table 1 Setup costof differentmodels

表2 Pareto最優(yōu)解Table 2 Pareto optimal solutions

圖4為兩種算法均運(yùn)行 20次,得到的近似最優(yōu)解集中所含個(gè)體數(shù)的比較.圖 5為所得解集中屬于Pareto最優(yōu)解的個(gè)數(shù)的比較.從圖4和5中可以看出無論是在解集數(shù)量還是在解集質(zhì)量上,MO-VECSA所得的算法結(jié)果均優(yōu)于MOCSA,且MO-VECSA所得結(jié)果更穩(wěn)定.圖 6為兩算法迭代 20次結(jié)果的平均值,可以直觀地看出,采用了疫苗種群協(xié)同進(jìn)化的克隆選擇算法的確可以得到更好的結(jié)果.

圖4 所得解集的大小Fig.4 Size of the solution set

圖5 Pareto最優(yōu)解的個(gè)數(shù)Fig.5 Number of Pareto solutions

圖6 平均結(jié)果值的比較Fig.6 Comparison of the average results

3.2 MO-VECSA算法整體性能評(píng)價(jià)

為了全面評(píng)價(jià)MO-VECSA的整體性能,文中采用CSMOA[10]、NSGA-II[9]、SPEA2作為比較算法[11].NSGA-II和SPEA2是兩種經(jīng)典的多目標(biāo)遺傳算法,CSMOA是一種只有抗體種群進(jìn)化的多目標(biāo)免疫克隆選擇算法.因?yàn)榉抡鎸?shí)例規(guī)模較大,無法得到Pareto最優(yōu)解集,文中從常用的幾種多目標(biāo)優(yōu)化算法的評(píng)價(jià)準(zhǔn)則中選擇前端范圍FS(S)和覆蓋評(píng)價(jià)函數(shù)?C作為評(píng)價(jià)函數(shù).

(1)前端范圍:

式中:S為非支配解集P在目標(biāo)空間的像;K為目標(biāo)函數(shù)的個(gè)數(shù);fi(x0)、fi(x1)分別為解x0和x1的目標(biāo)函數(shù)值.FS(S)用來測(cè)量近似集覆蓋目標(biāo)空間的大小.前端范圍的值越大,解的多樣性越好.

(2)覆蓋評(píng)價(jià)函數(shù):

式中:?C測(cè)度計(jì)算了解集Q中被P占優(yōu)的解的比例;p、q為P、Q解集中的解個(gè)體.

某企業(yè)一汽車總裝線共組裝5種車型,MPS比例為 3∶4∶6∶6∶1.為計(jì)算簡(jiǎn)便,假設(shè)設(shè)備更換成本均發(fā)生在第一工作站,且值為1.MO-VECSA抗體種群大小取 500,疫苗種群為 50,迭代次數(shù)為 100.其余算法的參數(shù)均取與MO-VECSA相當(dāng)?shù)臄?shù)值.所有算法均運(yùn)算 30次,對(duì)兩個(gè)評(píng)價(jià)準(zhǔn)則取平均值,見圖 7和表 3.

圖7 覆蓋評(píng)價(jià)函數(shù)柱形圖Fig.7 Histogram of the function coverage evaluation

表3 前端范圍平均結(jié)果比較Table 3 Comparison of FS(S)

圖7表明,MO-VECSA的近似集支配NSGA-II和SPEA 2得到大量非劣解,解集覆蓋均在50%左右,對(duì)CSMOA也有近40%的支配率.而NSGA-II和SPEA 2只支配MO-VECSA的非劣面的很小一部分,均低于20%,CSMOA略高.這說明MO-VECSA得到的近似Pareto解集的質(zhì)量要高于其余幾種算法.表3中數(shù)據(jù)表明,對(duì)于前端范圍評(píng)價(jià)函數(shù),MO-VECSA也優(yōu)于其余3種算法,這證明了MO-VECSA可以得到分布范圍更廣闊的近似最優(yōu)解集.

圖8是幾種算法得到的平均結(jié)果比較圖,從圖中可以看出,MO-VECSA曲線最低,算法結(jié)果略優(yōu)于CSMOA,對(duì)NSGA-II和SPEA2則有了較大改進(jìn).

圖8 四種算法平均結(jié)果比較Fig.8 Comparison of the average results of the four algorithms

4 結(jié)語(yǔ)

文中針對(duì)混流裝配線調(diào)度優(yōu)化問題的平順化零件使用率和最小化設(shè)備更換成本兩個(gè)優(yōu)化目標(biāo),提出一種疫苗協(xié)同進(jìn)化的多目標(biāo)免疫克隆選擇算法.通過對(duì)兩組實(shí)例仿真以全面測(cè)度算法的性能.第一組仿真通過易于得到Pareto前端的小規(guī)模實(shí)例證明了文中算法提出的疫苗種群對(duì)免疫克隆選擇算法性能的改善,得到的近似最優(yōu)集無論是在解集數(shù)量還是質(zhì)量上都比單抗體種群進(jìn)化的算法有所提高.第二組仿真選擇了NSGA-II、SPEA 2、CSMOA 3種算法作為比較算法,算法結(jié)果證明了文中提出的算法可以得到非支配占優(yōu)比例更高,且分布更廣闊的Pareto近似解集,更適于大規(guī)?；炝餮b配線調(diào)度優(yōu)化的求解.

[1] Bard J F,Shtub A,Joshi S B.Sequencing m ixed-model assembly lines to level parts usage and m inimize line length[J].Int JProd Res,1994,32(1):2431-2454.

[2] Tavakkoli-Moghaddam R,Rahimi-Vahed A R.Multi-criteria sequencing prob lem for am ixed-model assemb ly line in a JIT production system[J].Applied Mathematics and Computation,2006,181(2):1471-1481.

[3] Hyun C J,Kim Y,Kim Y K.A genetic algorithm formultiple objective sequencing problems in mixed model assembly lines[J].Comput Oper Res,1998,25(7/8):675-690.

[4] McMullen P R.An efficient frontier approach to addressing JIT sequencing problemswith setups via search heuristics[J].Comput Ind Eng,2001,41(3):335-353.

[5] Mansouri S A.A multi-objective genetic algorithm for mixed-model sequencing on JIT assembly lines[J].Eur J Oper Res,2005,167(3):696-716.

[6] 蘇平,于兆勤.基于混合遺傳算法的混合裝配線排序問題研究 [J].計(jì)算機(jī)集成制造系統(tǒng),2008,14(5): 1001-1007.

Su Ping,Yu Zhao-qiu.Hybrid genetic algorithms for sequencing problems in mixed model assemb ly lines[J]. Computer Integrated Manufacturing Systems,2008,14(5): 1001-1007.

[7] 焦李成,杜海峰,劉芳,等.免疫優(yōu)化計(jì)算,學(xué)習(xí)與識(shí)別[M].北京:科學(xué)出版社,2006.

[8] Rahimi-Vahed A,Mirzaei A H.A hybrid mu lti-objective shuffled frog-leaping algorithm for am ixed-model assembly line sequencing problem[J].Computers＆Industrial Engineering,2007,53(4):642-666.

[9] Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transaction on evolutionary Computation,2002,6(2):182-197.

[10] 尚榮華,馬文萍,焦李成,等.用于求解多目標(biāo)優(yōu)化問題的克隆選擇算法 [J].西安電子科技大學(xué)學(xué)報(bào), 2007,34(5):716-721.

Shang Rong-hua,Ma Wen-ping,Jiao Li-cheng,et al.Conal selection algorithm for multi-ob jective optimization problems[J].Journal of Xidian University,2007,34 (5):716-721.

[11] Zitzler E,Laumanns M,Thiele L.SPEA2:Imp roving the strength pareto evolutionary algorithm for mu ltiobjective optim ization[C]∥Proceedings of the Third Conference on Evolutionary and Determ inistic Methods for Design, Optim ization and Control with App lications to Industrial and Societal Problems(EUROGEN 2001).Athens:[s. n.],2002:95-100.