敏捷制造中面向盟友選擇問(wèn)題的遺傳算法

朱 偉，徐克林，朱 易

(同濟(jì)大學(xué)機(jī)械工程學(xué)院，上海201804，zhwliuhui@163.com)

隨著全球經(jīng)濟(jì)一體化、網(wǎng)絡(luò)化的進(jìn)程，敏捷制造(Agile Manufacturing，AM)理念應(yīng)運(yùn)而生，敏捷制造中具有代表性的組織形式虛擬企業(yè)(Virtual Enterprise，VE)，即核心企業(yè)通過(guò)招投標(biāo)的形式聯(lián)合本地或異地的相關(guān)優(yōu)勢(shì)互補(bǔ)資源，為及時(shí)響應(yīng)市場(chǎng)機(jī)遇而結(jié)成的動(dòng)態(tài)聯(lián)盟成為全球?qū)W術(shù)界和企業(yè)界關(guān)注的焦點(diǎn)［1］.

盟友選擇是結(jié)成動(dòng)態(tài)聯(lián)盟的核心環(huán)節(jié)，它其實(shí)是一個(gè)多目標(biāo)組合優(yōu)化問(wèn)題［2］.隨著問(wèn)題規(guī)模的不斷擴(kuò)大，傳統(tǒng)的運(yùn)籌學(xué)方法及啟發(fā)式算法在盟友選擇問(wèn)題上的應(yīng)用受到限制，如文獻(xiàn)［3－4］提出了重復(fù)啟發(fā)式算法，算法有效但通用性不強(qiáng).遺傳算法(Genetic Algorithm，GA)受啟于自然界優(yōu)勝劣汰的自然法則，將問(wèn)題的求解過(guò)程表達(dá)為染色體的選擇、交叉和變異等遺傳操作，通過(guò)全局搜索求得問(wèn)題的最優(yōu)解或滿(mǎn)意解.文獻(xiàn)［5］提出了以代碼串表達(dá)基因的編碼方式，因代碼串長(zhǎng)度與候選資源的數(shù)量相關(guān)，故而易引發(fā)解空間爆炸膨脹問(wèn)題.文獻(xiàn)［6］提出的遺傳算法編碼簡(jiǎn)單，但遺傳算子操作復(fù)雜，而且容易產(chǎn)生非問(wèn)題解.

本文設(shè)計(jì)了面向敏捷制造盟友選擇問(wèn)題的遺傳算法.算法采用字母與數(shù)字混合編碼，直觀、簡(jiǎn)單且遺傳操作均在解空間進(jìn)行，因而不會(huì)產(chǎn)生非法解.實(shí)驗(yàn)結(jié)果表明，算法在解的質(zhì)量和穩(wěn)定性方面有良好性能.

1 盟友選擇問(wèn)題建模

1.1 問(wèn)題描述

盟友選擇問(wèn)題可以描述為:核心企業(yè)根據(jù)實(shí)際情況將制造任務(wù)分解為多個(gè)單元任務(wù)，把自己無(wú)優(yōu)勢(shì)或無(wú)能力完成的單元任務(wù)放于網(wǎng)上投標(biāo)，搜索參與競(jìng)標(biāo)的所有候選資源并對(duì)競(jìng)標(biāo)者考核選擇:首先根據(jù)實(shí)力、信譽(yù)、質(zhì)量、價(jià)格、交貨情況和時(shí)空等指標(biāo)進(jìn)行定性分析，選擇出可用資源;然后以最優(yōu)化某指標(biāo)為手段，選擇出完成任務(wù)的最滿(mǎn)意資源組合［7］.本文以成本最低為優(yōu)化目標(biāo).

1.2 模型假設(shè)

1)各制造單元任務(wù)內(nèi)容無(wú)重復(fù);

2)一單元任務(wù)能且只能被一資源投中;

3)一資源有且僅有一次投標(biāo)機(jī)會(huì);

4)某些單元任務(wù)間有制造聯(lián)結(jié)約束;

5)若單元任務(wù)i和j存在制造聯(lián)結(jié)，則其相應(yīng)競(jìng)標(biāo)資源間有物流聯(lián)結(jié)費(fèi)用發(fā)生.

1.3 模型建立

1.4 符號(hào)說(shuō)明

T=(t1，t2，…，tn)為單元任務(wù)的編碼向量，B=(b1，b2，…，bm)為可用資源的編碼向量，D= {(i，j)|i∈(1，2，…，n－1)，j∈(2，3，…，n)}為存在制造聯(lián)結(jié)的兩任務(wù)集合表示任務(wù) i的投標(biāo)向量，x'i為 xi的轉(zhuǎn)置向量，表示資源 k的投標(biāo)向量，xk'為xk的轉(zhuǎn)置向量，c表示資源k對(duì)單元任務(wù)i的投標(biāo)價(jià)格.

2 面向盟友選擇問(wèn)題的遺傳算法

2.1 個(gè)體編碼

采用字母和數(shù)字混合編碼方案，設(shè)單元任務(wù)i的投標(biāo)資源數(shù)為m，將單元任務(wù)i和投標(biāo)資源的對(duì)應(yīng)關(guān)系依次編碼為T(mén)i1，Ti2，…，Tim.用單元任務(wù)對(duì)應(yīng)染色體的基因，設(shè)單元任務(wù)數(shù)為n，則問(wèn)題空間可表達(dá)為一組編碼長(zhǎng)度為n的染色體(g1，g2，…，gn)，其中，gi∈(Ti1，Ti2，…，Tim)，(i=1，2，…，n).染色體結(jié)構(gòu)意義為:資源b1中標(biāo)單元任務(wù)1，資源b2中標(biāo)單元任務(wù)2，依此類(lèi)推，資源bn中標(biāo)單元任務(wù)n，基因的位置序列即相應(yīng)的任務(wù)序列.

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

步驟1 隨機(jī)產(chǎn)生n個(gè)Ti1～Tim之間的編碼作為染色體基因的值，生成一條長(zhǎng)度為n的染色體.

步驟2 重復(fù)步驟1，直到生成的染色體數(shù)目滿(mǎn)足群體規(guī)模.

2.3 適應(yīng)度函數(shù)［8］

在遺傳算法中個(gè)體的適應(yīng)度越大越好，而盟友選擇問(wèn)題是目標(biāo)函數(shù)越小越好，所以需要將目標(biāo)函數(shù)f(x)變換為個(gè)體的適應(yīng)度函數(shù)F(x).所采用的變換如下:

其中:Cmax為足夠大的實(shí)數(shù)且最好與群體無(wú)關(guān)，這里選取Cmax等于最大適應(yīng)度值.

2.4 遺傳操作

2.4.1 選擇操作

選擇操作采用基于排序的選擇方法，首先對(duì)種群個(gè)體適應(yīng)度值排序，按設(shè)定比率淘汰低適應(yīng)度值個(gè)體，剩余個(gè)體(最優(yōu)個(gè)體除外)按輪盤(pán)賭方法參與選擇.

2.4.2 交叉操作

為避免產(chǎn)生非法個(gè)體，交叉操作限制在等位基因之間進(jìn)行.選取兩父代體A和B，隨機(jī)產(chǎn)生兩個(gè)表示交叉點(diǎn)的自然數(shù)，不妨取n1=3，n2=7，互換兩點(diǎn)外等位段基因的值，形成表達(dá)問(wèn)題的子代體A1和B1.子代體A1、B1的結(jié)構(gòu)形成過(guò)程如下:

采用等位分段交叉算子，可以滿(mǎn)足資源和單元任務(wù)間的約束關(guān)系，保證了新個(gè)體的合法性.

2.4.3 變異操作

為避免產(chǎn)生表達(dá)非法解的個(gè)體，算法設(shè)計(jì)了如下的變異算子:任務(wù)號(hào)不變，資源號(hào)加1，用任務(wù)號(hào)和資源號(hào)的新對(duì)應(yīng)關(guān)系編碼取代原編碼而形成新基因.下面以父代染色體C為例說(shuō)明變異操作過(guò)程:取其兩基因T42和T73，分別用T43和T74取代它們而形成新個(gè)體C1，其結(jié)構(gòu)如下:

變異操作中，資源號(hào)采用循環(huán)取值.

2.5 面向盟友選擇問(wèn)題的遺傳算法［9］

綜合以上討論，結(jié)合局部搜索算法，下面給出求解面向盟友選擇問(wèn)題的遺傳算法.

輸入可用資源投標(biāo)價(jià)格表、各制造聯(lián)接資源物流費(fèi)用表、淘汰率Pe、種群規(guī)模Popsize，最大進(jìn)化代數(shù)M、交叉概率Pc、變異概率Pm;

輸出最優(yōu)選擇方案;

Begin

染色體編碼，根據(jù)單元任務(wù)規(guī)模產(chǎn)生N個(gè)初始個(gè)體，組成初始種群P(T);

代數(shù)T:=0;

利用局部搜索算法對(duì)初始種群改進(jìn)，并評(píng)估最終得到的初始種群，如滿(mǎn)足設(shè)定的終止條件，則輸出最優(yōu)選擇方案并退出算法;否則，執(zhí)行以下步驟;

T代最優(yōu)個(gè)體復(fù)制到T+1代;

用輪盤(pán)賭方法從T代中選擇父體，按交叉概率Pc操作產(chǎn)生交叉子體，按變異概率Pm操作產(chǎn)生變異子體;

交叉子體和變異子體加入T+1代種群P(T+1);

利用局部搜索算法對(duì)新種群改進(jìn)，并評(píng)估最終得到的新種群，如滿(mǎn)足設(shè)定的終止條件，則輸出最優(yōu)方案并退出算法;否則執(zhí)行以下步驟;

3 算例及分析

3.1 算例

本文以文獻(xiàn)［1］案例作為驗(yàn)證算例.某核心企業(yè)有一大型制造任務(wù)，需選擇合作伙伴共同完成.該企業(yè)對(duì)此任務(wù)進(jìn)行了分解，經(jīng)過(guò)招投標(biāo)和初步選擇考核，確定了完成各個(gè)單元任務(wù)的可用資源，現(xiàn)欲以制造成本最低為優(yōu)化目標(biāo)來(lái)確定最佳制造資源組合.

圖1為資源聯(lián)結(jié)圖，圖中bij表示任務(wù)i的第j個(gè)投標(biāo)者，箭頭方向表示制造任務(wù)聯(lián)結(jié)的投標(biāo)資源之間的物流發(fā)生方向.表1為各資源對(duì)相應(yīng)單元任務(wù)的投標(biāo)價(jià)格，表2～5為制造聯(lián)結(jié)資源之間發(fā)生的物流費(fèi)用.

圖1 資源聯(lián)接圖

表1 各資源投標(biāo)價(jià)格c 萬(wàn)元

表2 資源b1、b4至b5的物流費(fèi)用f14－5 萬(wàn)元

表3 資源b2、b3至b4的物流費(fèi)用f23－4 萬(wàn)元

表4 資源b5至b6的物流費(fèi)用f5－6 萬(wàn)元

表5 資源b6至b7的物流費(fèi)用f6－7 萬(wàn)元

3.2 結(jié)果及分析

算例中，單元任務(wù)數(shù)為7，因此，染色體長(zhǎng)度為7.取淘汰率Pe=0.2、種群規(guī)模為40、交叉概率Pc=0.7、變異概率Pm=0.2、進(jìn)化代數(shù)為80.

在Dell Inspiron1420 PC機(jī)、Windows XP環(huán)境下運(yùn)行算法50次，其中44次得到問(wèn)題最優(yōu)解，其染色體結(jié)構(gòu)為:T12T22T33T41T51T63T71，表示資源組合R12、R22、R33、R41、R51、R63和R71為最優(yōu)，對(duì)應(yīng)的總成本為45.5萬(wàn)元;6次得到問(wèn)題次優(yōu)解，其染色體結(jié)構(gòu)為:T12T22T31T41T51T63T71，表示資源組合R12、R22、R31、R41、R51、R63和R71為次優(yōu)，對(duì)應(yīng)的總成本為45.6萬(wàn)元.所得結(jié)論和文獻(xiàn)［1］一致，證明了算法的可行性和可靠性.

4 結(jié)論與展望

1)討論了面向敏捷制造動(dòng)態(tài)盟友選擇的遺傳算法，算法采用字母與數(shù)字混合編碼方式，在等位基因間進(jìn)行交叉與變異操作，克服了傳統(tǒng)遺傳算法操作復(fù)雜且易產(chǎn)生非法解等缺點(diǎn).

2)算法尋優(yōu)效果明顯，穩(wěn)定性強(qiáng).

3)下一步擬研究約束條件的智能自適應(yīng)，以增強(qiáng)算法的魯棒性和可進(jìn)化性［10］，以便操作復(fù)雜大型的制造任務(wù)和動(dòng)態(tài)盟友選擇問(wèn)題.

［1］張潔，高亮，李培根.多Agent技術(shù)在先進(jìn)制造中的應(yīng)用［M］.北京:科學(xué)出版社，2004.

［2］李靈能，羅中先，戴躍洪.敏捷制造平臺(tái)上動(dòng)態(tài)聯(lián)盟盟友的選擇［J］.機(jī)械設(shè)計(jì)與制造，2007(6):194－196.

［3］伍乃騏，蘇平.敏捷制造下合作伙伴選擇的有效算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2004，10(8):971－979.

［4］WU Nai-qi，MAO Ning，QIAN Yan-ming.An approach to partner selection in agile manufacturing［J］.Journal of Intelligent Manufacturing，1999(10):519－529.

［5］馮蔚東，陳劍，趙均純.基于遺傳算法的動(dòng)態(tài)聯(lián)盟伙伴選擇過(guò)程及優(yōu)化模型［J］.清華大學(xué)學(xué)報(bào):自然科學(xué)版，2000，40(10):120－124.

［6］郭懷瑞.敏捷制造系統(tǒng)的重構(gòu)算法［D］.武漢:華中科技大學(xué)圖書(shū)館，2000.

［7］張翠軍，賀毅朝，王金山.敏捷制造中制造資源選擇問(wèn)題的遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43 (10):217－218.

［8］王凌.智能優(yōu)化算法及其應(yīng)用［M］.北京:清華大學(xué)出版社，2001:154－159.

［9］柳林.基于遺傳算法的 Job－Shop調(diào)度問(wèn)題求解［J］.計(jì)算機(jī)應(yīng)用，2006(7):1695－1696.

［10］WU C G，XING X L，LEE H P，et al.Genetic algorithm application on the job shop scheduling problem［C］//Proceedings of 2004 International Conference on Machine Learning and Cybernetics.Shanghai，China:［s.n.］，2004:2102－2l06.