梁勤歐，周曉艷

(1.浙江師范大學(xué)地理與環(huán)境科學(xué)學(xué)院，浙江金華321004;2.武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北武漢430079)

設(shè)備布局問題［1］是指在制造環(huán)境中，合理安排機(jī)器設(shè)備的位置，使生產(chǎn)消耗達(dá)到最小，生產(chǎn)效益最大化。機(jī)器設(shè)備科學(xué)合理地布局至少能節(jié)省10% ～30%的物料運(yùn)輸費(fèi)用［2］。

設(shè)備布局問題屬于組合優(yōu)化中的NP難題，即隨著問題的規(guī)模增加，約束條件的復(fù)雜化，其求解難度迅速增加。針對設(shè)備布局問題的特點(diǎn)，許多學(xué)者引入各種優(yōu)化算法對其進(jìn)行求解，其中應(yīng)用較多的是遺傳算法［3－4］。

人工免疫系統(tǒng)(artificial immune system，AIS)是近年來興起的一個新的智能計算方法［5］。免疫系統(tǒng)的記憶功能(疫苗)常被作為遺傳算法種群更新中的一種機(jī)制被使用，以便改進(jìn)遺傳算法的性能［6］。采用免疫系統(tǒng)與遺傳算法相結(jié)合的新算法進(jìn)行設(shè)備布局問題的研究，因其吸收了兩種算法的優(yōu)點(diǎn)，在研究效率上應(yīng)該比傳統(tǒng)的遺傳算法有所提高。在借鑒免疫記憶功能與信息熵相結(jié)合的免疫遺傳算法［7］基礎(chǔ)上，提出了一種改進(jìn)的免疫遺傳算法，并通過單行、多行機(jī)器設(shè)備布局問題的實(shí)驗來驗證該算法的有效性。

1 設(shè)備布局問題的數(shù)學(xué)模型

設(shè)備布局問題根據(jù)機(jī)器的不同排列方式可劃分成多種類型，如單行線性排列、雙行線性排列、多行線性排列和環(huán)行排列等。為研究方便，假設(shè)機(jī)器都是矩形，且機(jī)器都水平放置，下面對單行線性排列和多行線性排列設(shè)備布局問題分別建模［8］。

對于單行機(jī)器設(shè)備布局問題，其數(shù)學(xué)模型可以描述如下:

函數(shù)目標(biāo)為最小化機(jī)器之間的必要訪問次數(shù)下的總費(fèi)用。n為機(jī)器數(shù);fij為機(jī)器間訪問頻率;cij為機(jī)器間訪問時每單位距離的費(fèi)用;li為機(jī)器的長度;dij為機(jī)器間最小間距;xi為機(jī)器的中心線相對垂直參考線的距離。式(1)為目標(biāo)函數(shù);式(2)約束機(jī)器不重疊;式(3)保證坐標(biāo)為正值。

對于多行機(jī)器設(shè)備布局問題，其數(shù)學(xué)模型可以描述如下:

函數(shù)目標(biāo)為最小化機(jī)器之間的必要訪問次數(shù)下的總費(fèi)用。n為機(jī)器數(shù);m為行數(shù);fij為機(jī)器間訪問頻率;cij為機(jī)器間訪問時每單位距離的費(fèi)用;li為機(jī)器的長度;l0為兩個相鄰行的中心距;dij為機(jī)器間最小間距;xi為機(jī)器的中心線相對垂直參考線的距離;yi為機(jī)器的中心線相對水平參考線的距離。式(4)分配機(jī)器到不同行;式(6)保證機(jī)器不重疊;式(7)～式(9)保證一臺機(jī)器只放在一行上;式(10)保證坐標(biāo)為正值。

2 免疫遺傳算法的改進(jìn)與設(shè)備布局問題求解

2.1 免疫遺傳算法的改進(jìn)

基于信息熵的免疫遺傳算法考慮了抗體濃度，并利用信息熵公式計算每個個體基因位置的信息熵大小，通過設(shè)定抗體濃度閾值來保證抗體的多樣性。許多學(xué)者利用該算法進(jìn)行了相關(guān)問題的研究，得到了不錯的結(jié)果。但該算法的缺點(diǎn)是運(yùn)行時間長，搜索速度較慢，且比較容易早熟收斂。為了克服這些缺點(diǎn)，采用新的簡化種群選擇策略，提出一種改進(jìn)的免疫遺傳算法。

改進(jìn)的免疫遺傳算法的計算過程如下:(1)初始化種群。即系統(tǒng)初始化為一組隨機(jī)解。(2)計算所有個體的適應(yīng)度，并選擇適值最好的兩個個體存入抗體記憶庫。

(3)對種群進(jìn)行遺傳算法操作并產(chǎn)生新種群。遺傳算法操作包括選擇、交叉和變異等。選擇操作按照抗原—抗體之間親和力k1，抗體—抗體之間親和力k2進(jìn)行。假設(shè)有N個種群個體，則定義第i個個體被選擇的概率SP(i)為:

SP(i)=a·k1i+b·k2i(12)式中，a，b∈(0，1)為調(diào)節(jié)系數(shù)。a，b 可以按照實(shí)驗經(jīng)驗來確定。

(4)更新抗體記憶庫。如果抗體記憶庫未滿，選擇最好的兩個新個體補(bǔ)充記憶庫。如果抗體記憶庫已滿，選擇最好的兩個新個體替換抗體記憶庫中最差的兩個個體。

(5)產(chǎn)生新種群。抗體記憶庫替換同等數(shù)量種群中最差個體組成新種群。

(6)達(dá)到最大迭代次數(shù)則算法停止，最優(yōu)秀的個體即為最優(yōu)解。否則轉(zhuǎn)回第(3)步。

以上改進(jìn)的免疫遺傳算法最大特點(diǎn)是簡化了種群個體的選擇機(jī)制，采用了新的親和力組合計算的步驟。其計算量比傳統(tǒng)的基于信息熵的免疫遺傳算法大大減小。

2.2 改進(jìn)的免疫遺傳算法求解設(shè)備布局問題

根據(jù)以上改進(jìn)的免疫遺傳算法，圖1列出了應(yīng)用該算法解決設(shè)備布局問題的簡要流程。

圖1 改進(jìn)免疫遺傳算法求解設(shè)備布局問題的算法流程

(1)設(shè)備布局基本數(shù)據(jù)輸入。輸入的數(shù)據(jù)包括機(jī)器設(shè)備的尺寸、機(jī)器間最小距離、物流操作頻率和物流操作費(fèi)用等;同時也包括改進(jìn)免疫遺傳算法的參數(shù)初始設(shè)置，如交叉率、變異率、記憶庫容量參數(shù)、迭代次數(shù)和種群個數(shù)等。

(2)隨機(jī)生成種群。由于機(jī)器設(shè)備布局問題有不同的編碼方式生成種群，筆者采取整數(shù)編碼方案進(jìn)行實(shí)驗，即隨機(jī)生成機(jī)器排列序列，如有6臺機(jī)器，則隨機(jī)排列為1到6之間的整數(shù)。

(3)產(chǎn)生凈間距序列，進(jìn)行行分配。這一步主要是針對多行機(jī)器布局而言。對于兩行機(jī)器排列，首先產(chǎn)生初始可用空間，計算如下:

式中:KL為每個初始個體生成的可用空間;L為布局區(qū)域最大寬度;li、di，i+1分別為機(jī)器寬度和兩臺機(jī)器間的必需間距;d10、dn0分別為機(jī)器與布局區(qū)域邊界的必需間距。

式(13)對文獻(xiàn)［8］中的公式進(jìn)行了糾正。按照文獻(xiàn)［8］中的公式，d10、dn0是沒有乘2的。但經(jīng)過實(shí)驗發(fā)現(xiàn)，如果不乘以2，對于兩行機(jī)器布局初始可用空間是不成立的，因為每行機(jī)器都有一個距離區(qū)域邊界的必需間距。

在計算出的初始可用空間區(qū)域內(nèi)，隨機(jī)生成凈間距序列，生成的凈間距序列之和等于可用空間長度。

機(jī)器布局行分配采取的方法是，首先依次選取機(jī)器排列及其凈間距、必需間距進(jìn)行總距離的計算，如果總距離沒有超出L，再增加下一個緊鄰機(jī)器;如果總距離超出L，則把超出的機(jī)器去除，直到總距離滿足L的約束。其余機(jī)器則依次排列在下一行。

(4)親和力適值計算與評估。在該過程中需要微調(diào)凈間距序列，使得親和力適值達(dá)到最優(yōu)。微調(diào)方法是在凈間距序列每一行中的任意兩個不同個體分別加減一個很小的數(shù)，這個數(shù)采用可用空間與給定整數(shù)r的比值求得。如果該行凈間距序列為奇數(shù)，則剩余單一的序列數(shù)不進(jìn)行任何操作，循環(huán)操作次數(shù)為種群個體數(shù)與變異率的乘積。這里的凈間距序列微調(diào)方法不同于文獻(xiàn)［8］采用的交叉、變異方法，因為文獻(xiàn)［8］的交叉方法會產(chǎn)生大量不可行解，原因是一般任何兩個種群個體的可用凈間距是不同的，交叉后常出現(xiàn)凈間距序列和超出可用凈間距的現(xiàn)象。

每一次凈間距序列微調(diào)后，都要計算每臺機(jī)器的坐標(biāo)位置，然后應(yīng)用式(1)或式(5)求出機(jī)器之間的必要訪問次數(shù)下的總費(fèi)用，在所有微調(diào)過程中選擇出最優(yōu)凈間距序列下的總費(fèi)用，即為親和力適值。由于采用凈間距序列，因此不會產(chǎn)生機(jī)器重疊現(xiàn)象。對于機(jī)器超出布局區(qū)域的情況，采取懲罰的方法把不可行解淘汰。

由于機(jī)器設(shè)備布局問題是求總目標(biāo)的最小值，為了程序設(shè)計方便，用總費(fèi)用的倒數(shù)表示抗體與抗原之間的親和力，即F=1/f，這樣，程序的目標(biāo)就轉(zhuǎn)化為求最大值問題，不可行解懲罰為一個較小實(shí)數(shù)。

(5)抗體記憶庫初始化?？贵w記憶庫大小是根據(jù)種群個體多少決定的，一般設(shè)定為種群大小的20%～40%。記憶庫每次從種群中選擇最好的兩個個體進(jìn)行存儲?？贵w記憶庫初始化是結(jié)合初始化種群和凈間距序列，選擇抗體抗原親和力適值最好的兩個個體進(jìn)行存儲。

(6)種群選擇。按照式(12)計算遺傳操作的個體選擇概率，然后采用輪盤賭的方式進(jìn)行種群選擇。

(7)交叉變異產(chǎn)生新種群。對選擇出的機(jī)器排列個體采取循環(huán)交叉［9］的方法產(chǎn)生新的種群。在交叉產(chǎn)生的新種群中，再以變異率為選擇機(jī)制，對每個個體進(jìn)行隨機(jī)點(diǎn)變異，產(chǎn)生新的種群。

(8)產(chǎn)生凈間距序列，進(jìn)行行分配。對于新種群再進(jìn)行凈間距序列和行分配的操作。

(9)親和力適值計算，評估，再微調(diào)凈間距序列產(chǎn)生最優(yōu)解。

(10)更新抗體記憶庫。如果抗體記憶庫未滿，更新補(bǔ)充記憶庫;如果抗體記憶庫已滿，選擇最好的兩個新個體替換抗體記憶庫中最差的兩個個體。

(11)記憶庫替代最差個體，產(chǎn)生新種群。抗體記憶庫代替遺傳操作后產(chǎn)生的新種群的最差個體，從而組成新的種群。

(12)如果達(dá)到設(shè)定的最大迭代次數(shù)則停止迭代。否則，在新產(chǎn)生的種群中重新開始選擇、遺傳等操作。

3 實(shí)驗研究

為了便于研究結(jié)果的對比，下面選擇文獻(xiàn)［8］中的實(shí)例進(jìn)行實(shí)驗研究。各機(jī)器的尺寸如表1所示。fij、cij、dij分別為機(jī)器間操作頻率、機(jī)器間操作費(fèi)用和

對于多行布局，工作區(qū)域?qū)挾燃s束為22，行間中心距離為8，d10=2，dn0=2。

表1 機(jī)器尺寸

對于單行布局問題:初始種群數(shù)量為50;交叉率pc=0.8;變異率pm=0.3;抗體記憶庫容量為 RM=20;調(diào)節(jié)系數(shù)分別為 a=0.7，b=0.2;停止迭代次數(shù)為20。

對于多行布局問題:初始種群數(shù)量為50;交叉率pc=0.8;變異率pm=0.3;抗體記憶庫容量為 RM=20;調(diào)節(jié)系數(shù)分別為 a=0.7，b=0.2;停止迭代次數(shù)為100。文獻(xiàn)［8］采用遺傳算法進(jìn)行求解，初始種群數(shù)量為20，交叉率pc=0.4;變異率pm=0.4;迭代次數(shù)為500。

圖2為改進(jìn)免疫遺傳算法求解機(jī)器設(shè)備布局適值變化。圖3為機(jī)器布局的實(shí)驗結(jié)果。表2列出了多行機(jī)器設(shè)備布局的5個隨機(jī)實(shí)驗結(jié)果和文獻(xiàn)［8］的實(shí)驗值。

圖2 改進(jìn)免疫遺傳算法求解機(jī)器設(shè)備布局適值變化

表2 多行機(jī)器設(shè)備布局實(shí)驗結(jié)果

圖3 機(jī)器布局的實(shí)驗結(jié)果

對于單行機(jī)器設(shè)備布局實(shí)驗，計算結(jié)果和文獻(xiàn)［8］相同，最優(yōu)適值為19 531，且在第2代就收斂，如圖2(a)所示，機(jī)器排列序列如圖3(a)所示。

對于多行機(jī)器設(shè)備布局實(shí)驗，文獻(xiàn)［8］計算結(jié)果為16 735。而表2實(shí)驗結(jié)果表明，應(yīng)用改進(jìn)免疫遺傳算法求得的結(jié)果都小于16 735，最小值達(dá)到16 573。實(shí)驗1結(jié)果還搜索到每行排列3臺機(jī)器的一個優(yōu)秀解。每行3臺機(jī)器排列的最優(yōu)解由于數(shù)量少，其搜索難度較大。從圖2(b)可以看出，最優(yōu)解搜索是比較穩(wěn)定的。綜合以上說明免疫遺傳算法在進(jìn)行多行機(jī)器設(shè)備布局研究中是有效的。圖3(b)為最優(yōu)實(shí)驗結(jié)果的機(jī)器排列序列圖。

4 結(jié)論

人工免疫系統(tǒng)作為一種新興算法，還有許多待研究的問題［10］，其應(yīng)用領(lǐng)域也需要進(jìn)一步拓寬。對機(jī)器設(shè)備布局這個組合優(yōu)化難題進(jìn)行了實(shí)驗研究，說明了人工免疫系統(tǒng)算法的明顯優(yōu)勢。下一步的研究工作將在大規(guī)模組合優(yōu)化問題的實(shí)驗中展開，并把人工免疫系統(tǒng)模型拓展應(yīng)用到其他設(shè)施規(guī)劃問題中。

［1］KUSIAK A，HERAGU S.The facility layout problem［J］.European Journal of Operational Research，1987，29(3):229－251.

［2］MARCELLOB，SIMONE Z，LUCIO Z.Layoutdesign in dynamic environments:strategies and quantitative indices［J］.International Journal of Production Research，2003，41(5):995 －1016.

［3］常建娥，馬立坤.基于GA的計算機(jī)輔助車間設(shè)備布局設(shè)計［J］.武漢理工大學(xué)學(xué)報:信息與管理工程版，2008，30(4):548 －550.

［4］閻長罡，曹戰(zhàn).基于遺傳算法的車間設(shè)備布局設(shè)計［J］.大連交通大學(xué)學(xué)報，2007，9(3):33 －37.

［5］DE CASTRO LN，VON ZUBEN F J.Artificial immune systems:basic theory and applications［R］.Campinas:State University of Campinas，1999.

［6］焦李成，杜海峰.免疫優(yōu)化計算、學(xué)習(xí)與識別［M］.北京:科學(xué)出版社，2006:59－90.

［7］CHUN J，KIM M，JUN H.Shape optimization of electromagnetic devices using immune algorithm［J］.IEEE Transactions on Magnetics，1997，33(2):1876 －1879.

［8］玄光男，程潤偉.遺傳算法與工程設(shè)計［M］.北京:科學(xué)出版社，2000:208－219.

［9］OLIVER IM，SMITH D J，HOLLAND JR C.A study of permutation crossover operators on the traveling salesman problem［C］//Proceedings of the second international conference on genetic algorithm.New Jersey: ［s.n.］，1987:224 －230.

［10］TIMMIS JA，HONE T S，CLARK E.Theoretical advances in artificial immune systems［J］.Theoretical Computer Science，2008，403(1):11 －32.