国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

敏捷制造中面向盟友選擇問題的遺傳算法

2010-03-24 06:10:40徐克林
關(guān)鍵詞:盟友投標(biāo)染色體

朱 偉,徐克林,朱 易

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

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

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

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

1 盟友選擇問題建模

1.1 問題描述

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

1.2 模型假設(shè)

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

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

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

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

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

1.3 模型建立

1.4 符號說明

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對單元任務(wù)i的投標(biāo)價格.

2 面向盟友選擇問題的遺傳算法

2.1 個體編碼

采用字母和數(shù)字混合編碼方案,設(shè)單元任務(wù)i的投標(biāo)資源數(shù)為m,將單元任務(wù)i和投標(biāo)資源的對應(yīng)關(guān)系依次編碼為Ti1,Ti2,…,Tim.用單元任務(wù)對應(yīng)染色體的基因,設(shè)單元任務(wù)數(shù)為n,則問題空間可表達(dá)為一組編碼長度為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,依此類推,資源bn中標(biāo)單元任務(wù)n,基因的位置序列即相應(yīng)的任務(wù)序列.

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

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

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

2.3 適應(yīng)度函數(shù)[8]

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

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

2.4 遺傳操作

2.4.1 選擇操作

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

2.4.2 交叉操作

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

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

2.4.3 變異操作

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

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

2.5 面向盟友選擇問題的遺傳算法[9]

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

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

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

Begin

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

代數(shù)T:=0;

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

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

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

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

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

3 算例及分析

3.1 算例

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

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

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

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

表2 資源b1、b4至b5的物流費用f14-5 萬元

表3 資源b2、b3至b4的物流費用f23-4 萬元

表4 資源b5至b6的物流費用f5-6 萬元

表5 資源b6至b7的物流費用f6-7 萬元

3.2 結(jié)果及分析

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

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

4 結(jié)論與展望

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

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

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

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

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

[3]伍乃騏,蘇平.敏捷制造下合作伙伴選擇的有效算法[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]馮蔚東,陳劍,趙均純.基于遺傳算法的動態(tài)聯(lián)盟伙伴選擇過程及優(yōu)化模型[J].清華大學(xué)學(xué)報:自然科學(xué)版,2000,40(10):120-124.

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

[7]張翠軍,賀毅朝,王金山.敏捷制造中制造資源選擇問題的遺傳算法[J].計算機(jī)工程與應(yīng)用,2007,43 (10):217-218.

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

[9]柳林.基于遺傳算法的 Job-Shop調(diào)度問題求解[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.

猜你喜歡
盟友投標(biāo)染色體
冬天的盟友
青年文摘(2021年4期)2021-12-15 17:19:09
造價信息管理在海外投標(biāo)中的應(yīng)用探討
國務(wù)院明確取消投標(biāo)報名
淺析投標(biāo)預(yù)算風(fēng)險的防范
多一條X染色體,壽命會更長
為什么男性要有一條X染色體?
軍工企業(yè)招標(biāo)投標(biāo)管理實踐及探討
好好玩創(chuàng)意營盟友唯我獨尊
童話世界(2017年26期)2017-12-18 00:31:00
是對手,更是盟友
航空模型(2017年2期)2017-05-22 18:25:11
好好玩創(chuàng)意營 盟友唯我獨尊
童話世界(2017年11期)2017-05-17 05:28:16
绥阳县| 修武县| 九龙坡区| 安龙县| 汝城县| 平泉县| 饶平县| 承德市| 阳谷县| 马龙县| 崇文区| 南开区| 迁安市| 调兵山市| 西峡县| 潼南县| 乐昌市| 枞阳县| 苏州市| 英超| 中江县| 昌乐县| 黎城县| 凤庆县| 博罗县| 南宫市| 石屏县| 哈尔滨市| 罗平县| 拜泉县| 陆河县| 延安市| 霍邱县| 广安市| 永寿县| 友谊县| 扬中市| 金寨县| 鹤岗市| 木里| 西乡县|