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

?

改進(jìn)遺傳算法求解作業(yè)車間提前/拖期調(diào)度問題

2013-09-06 01:57:58葛安華周晏明李權(quán)章
森林工程 2013年3期
關(guān)鍵詞:染色體遺傳算法車間

葛安華,周晏明,李權(quán)章

(東北林業(yè)大學(xué)工程技術(shù)學(xué)院,哈爾濱 150040)

作業(yè)車間調(diào)度問題,是一類滿足任務(wù)配置和順序約束要求的資源分配問題,其目的是對作業(yè)進(jìn)行有效排序,是最難解決的組合優(yōu)化問題之一[1]。在實(shí)際的制造企業(yè)加工車間中所面臨的問題大多為作業(yè)車間調(diào)度,如車間生產(chǎn)自動化水平相對較低,憑計劃員經(jīng)驗(yàn)調(diào)度,頻繁調(diào)整生產(chǎn)計劃,設(shè)備利用率不均衡,生產(chǎn)周期加長以及人員與設(shè)備的浪費(fèi)[2]。對作業(yè)車間調(diào)度問題的研究有助于提高生產(chǎn)車間自動化水平,改善設(shè)備利用的均衡性,具有重要理論意義和工程價值。

隨著近年來智能優(yōu)化技術(shù)的發(fā)展,許多求解作業(yè)車間調(diào)度問題的啟發(fā)式方法被提出,如禁忌搜索算法、模擬退火算法、遺傳算法等,國內(nèi)外的專家學(xué)者在相關(guān)方面也做了大量的研究工作[3-5]。文獻(xiàn)[3]研究了一種基于禁忌搜索技術(shù)解決作業(yè)車間調(diào)度最短完工時間的算法。禁忌搜索算法偏向于局部搜索,對初始解的依賴性較強(qiáng),不好的初始解會造成計算時間過長。文獻(xiàn) [4]闡述了模擬退火算法在作業(yè)車間調(diào)度問題上的應(yīng)用。雖然理論上模擬退火算法可以在足夠長的時間后跳出局部最優(yōu),但在實(shí)際應(yīng)用中往往會陷入到優(yōu)化效果與計算時間的矛盾中。遺傳算法,因其通用性強(qiáng),全局搜索性能較好,在求解過程中可同時保留多個方案而得到廣泛的應(yīng)用。但因其固有特征,在求解作業(yè)車間調(diào)度問題時仍具有局部尋優(yōu)能力差,搜索效率不高等現(xiàn)象。文獻(xiàn) [5]通過改進(jìn)遺傳算法的編碼方式、交叉、變異策略等方法提高了算法求解總加工時間最短的作業(yè)調(diào)度問題的能力。

在實(shí)際的車間調(diào)度問題中,企業(yè)的生產(chǎn)調(diào)度多以產(chǎn)品的訂單交貨期為主要依據(jù)[6],故本文將最小化產(chǎn)品的提前/拖期懲罰作為目標(biāo)函數(shù),以提高遺傳算法在作業(yè)車間調(diào)度問題中的求解質(zhì)量和收斂速度為目標(biāo),提出一種帶有記憶功能的改進(jìn)遺傳算法,并利用爬山算法提高其局部搜索能力,通過與其他算法計算結(jié)果的對比分析驗(yàn)證其優(yōu)越性。

1 問題描述

作業(yè)車間提前/拖期調(diào)度問題可以描述為:

(1)在m臺機(jī)器上生產(chǎn)n個相互獨(dú)立的產(chǎn)品,產(chǎn)品集合表示為N={1,2,……,n},機(jī)器集合表示為M={1,2,……,m},每個產(chǎn)品需經(jīng)過若干道工序才能完成,且每道工序在特定的機(jī)器上加工;

(2)sijk和tijk分別表示第i個產(chǎn)品的第j道工序在機(jī)器k上的開始加工時間和加工時數(shù),產(chǎn)品i的最后一道工序的開始加工時間和所需加工時數(shù)分別是siek和tiek,則產(chǎn)品i的完工時間ci=siek+tiek;

(3)產(chǎn)品i的交貨時間窗口為 [ei,di],產(chǎn)品i單位時間的提前懲罰為ωi,拖期懲罰為αi,若產(chǎn)品在時間窗口之內(nèi)完成生產(chǎn),則不受懲罰,否則對產(chǎn)品i進(jìn)行懲罰;

目標(biāo)函數(shù)為最小化產(chǎn)品的總懲罰,表示為:

公式 (1)表示的是目標(biāo)函數(shù),即最小化所有產(chǎn)品的提前/拖期懲罰。公式 (2)表示工藝約束條件決定的各產(chǎn)品的各道工序的先后加工順序以及各道工序在相應(yīng)機(jī)器上的加工順序。其中,若機(jī)器h先于機(jī)器k加工產(chǎn)品i,則aihk為1否則為0,若產(chǎn)品i先于工件j在機(jī)器k上加工,則bijk為1否則為0;sik和tik分別表示產(chǎn)品i在機(jī)器k上的開始加工時間和加工時數(shù);G是一個足夠大的正數(shù)。

2 遺傳算法的設(shè)計

為提高遺傳算法的收斂速度,采用一種可以保留較高適應(yīng)度個體的記憶功能,并利用爬山算法對記憶種群進(jìn)行局部搜索,從而增強(qiáng)算法的局部搜索能力。改進(jìn)遺傳算法的具體步驟如下:

(1)設(shè)置種群尺寸為PS,記憶庫尺寸為MS。

(2)產(chǎn)生初始種群P(t),從初始種群中選取MS個較優(yōu)個體保存在記憶庫M(t)中。

(3)分別以交叉概率Pc和變異概率Pm對個體進(jìn)行交叉和變異操作,將得到的子代個體保存到種群O(t)中。

(4)以記憶庫M(t)中的染色體為初始解,利用爬山算法進(jìn)行局部搜索,得到更新后的記憶庫M’(t)。

(5)評價種群P(t),O(t)和M’(t),從中選擇出種群P(t+1)。

(6)進(jìn)行記憶庫的第二次更新,從種群P(t+1)中選取其中較優(yōu)的MS個個體更新記憶庫。

(7)如果滿足終止條件 (達(dá)到最大迭代次數(shù)N)則結(jié)束計算,否則轉(zhuǎn)向 (3)。

2.1 編碼設(shè)計

遺傳算法在進(jìn)行編碼時,必須要考慮染色體的合法性、有效性、冗余性以及表征解空間的完全性[7]。編碼設(shè)計的優(yōu)劣對算法的各子階段都有重大影響。好的編碼設(shè)計可以保證在交叉、變異后依然保持染色體的有效性和完全性。目前已提出的編碼方法有,基于優(yōu)先規(guī)則的表達(dá)法、基于工序的表達(dá)法、基于優(yōu)先表的表達(dá)法、基于工件的表達(dá)法、基于工件對關(guān)系的表達(dá)法、基于機(jī)器的表達(dá)法等[8]。

將基于工序表達(dá)法與機(jī)器表達(dá)法的實(shí)數(shù)編碼方法相結(jié)合,形成一種新的雙染色體矩陣編碼方式。對于m臺機(jī)器生產(chǎn)n種產(chǎn)品的問題,基于工序表達(dá)的實(shí)數(shù)編碼,染色體有n×m個基因,每個代表產(chǎn)品的十進(jìn)制數(shù)都在基因中重復(fù)出現(xiàn)m次,工序調(diào)度的順序由染色體基因的順序決定;同樣基于機(jī)器表達(dá)的實(shí)數(shù)編碼,其染色體也有n×m個基因,每個染色體基因分別表示相應(yīng)產(chǎn)品的各道加工工序所在的機(jī)器編號。

2.2 種群的初始化及適應(yīng)度函數(shù)的確定

依據(jù)上述編碼方式的種群初始化很簡便,首先建立一個隨機(jī)分配個體基因的循環(huán),生成個體的第一行基因,再利用產(chǎn)品的工序順序約束生成個體的第二行基因。如此重復(fù)進(jìn)行,直至達(dá)到設(shè)定的種群規(guī)模。

根據(jù)目標(biāo)函數(shù)定義的適應(yīng)度函數(shù)如下所示:

式中:F為適應(yīng)度函數(shù),F(xiàn)取值越大,總懲罰越小,其對應(yīng)調(diào)度方案的適應(yīng)度越高。

2.3 遺傳算子

2.3.1 復(fù)制

2.3.2 交叉

考慮到基于雙染色體矩陣編碼交叉后子代的調(diào)度可行性,基于部分映射雜交 (PMX)和染色體分離的思想提出一種部分映射交叉重排算子[9-10]。這種交叉方法的具體過程如下:

(1)分別在兩個父代染色體上選擇兩個步數(shù)相同的交叉點(diǎn)。

(2)兩個父代交換彼此交叉點(diǎn)之間的子串。

(3)確定被交換的子串間基因的映射關(guān)系。

(4)消除掉染色體中多余的基因,以相應(yīng)的缺失基因補(bǔ)充。

(5)根據(jù)產(chǎn)品相應(yīng)工序所需加工機(jī)器的約束,重新排列染色體中的第二行基因。舉例說明部分映射交叉重排算子,如圖1所示,A、B為兩個父代染色體,經(jīng)交叉后得到兩個子代個體A’、B’。

2.3.3 變異

為保證變異后的個體仍為可行解,基于前面交叉算子的設(shè)計思想,采用互反變異重排方法進(jìn)行個體的變異操作。首先在染色體上隨機(jī)選擇兩個位置,然后交換這兩處的基因,再根據(jù)產(chǎn)品各工序所需加工機(jī)器的約束重排第二行的染色體基因[11]。

圖1 交叉算子Fig.1 Crossover operator

2.4 爬山操作

爬山算法,又稱局部搜索算法,是一種基于鄰域搜索技術(shù)的、沿著可能改進(jìn)解的質(zhì)量的方向進(jìn)行單方向搜索 (爬山)的搜索方法,其局部搜索能力很強(qiáng),是一種常用的尋找局部最優(yōu)解的方法[12]。它在解的空間內(nèi),以當(dāng)前節(jié)點(diǎn)為中心和其鄰域的節(jié)點(diǎn)值相比較,若其鄰域節(jié)點(diǎn)更優(yōu),則用其替換當(dāng)前節(jié)點(diǎn)繼續(xù)搜索;反之則返回當(dāng)前節(jié)點(diǎn)繼續(xù)搜索。如此循環(huán)直至到達(dá)終止條件。

為彌補(bǔ)傳統(tǒng)遺傳算法局部搜索能力較弱的不足,采用基因逆轉(zhuǎn)算子來實(shí)現(xiàn)爬山操作,更新種群記憶庫。具體步驟如下:

(1)對于記憶庫中的每個個體,隨機(jī)選擇個體上的兩個點(diǎn),再將兩點(diǎn)之間的元素逆序插回到原來的位置中。

(2)判斷逆轉(zhuǎn)后的個體適應(yīng)值是否增加,若增加則以逆轉(zhuǎn)后的個體替換原個體,否則仍保留原個體。

(3)重復(fù) (1)、(2)的操作,直至達(dá)到設(shè)定的迭代次數(shù)為止。

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

本節(jié)的仿真實(shí)驗(yàn)在Genuine Intel(R)T2130 1.87GHz處理器,2.0GB RAM,MATLAB R2011a環(huán)境下進(jìn)行。

3.1 仿真分析

為驗(yàn)證文中改進(jìn)遺傳算法的優(yōu)越性,將本文算法與文獻(xiàn)[2]中的遺傳算法 (IGA)進(jìn)行比較。取種群規(guī)模100,記憶庫規(guī)模20,交叉概率0.5,變異概率0.05,在不同規(guī)模 (n×m)下進(jìn)行實(shí)驗(yàn)對比。實(shí)驗(yàn)中生產(chǎn)機(jī)器的集合,各工序所需加工時間隨機(jī)產(chǎn)生,且滿足平均分布。由于篇幅有限在此僅列出6組實(shí)驗(yàn)結(jié)果,見表1,每種規(guī)模仿真實(shí)驗(yàn)20次,其中最優(yōu)值為所有運(yùn)算結(jié)果中目標(biāo)函數(shù)最小的值,平均值為每次運(yùn)行所得最優(yōu)值的平均值。

表1 方法比較Tab.1 Method comparison

從表1中可以看出,本文算法所求得的最優(yōu)值和平均值均優(yōu)于IGA,而且隨著規(guī)模的不斷擴(kuò)大,效果更加明顯,體現(xiàn)了本文算法的優(yōu)越性。

3.2 實(shí)例應(yīng)用

以某加工制造企業(yè)為例,驗(yàn)證本文算法在實(shí)際應(yīng)用中的可行性和有效性,設(shè)提前懲罰為0.8,拖期懲罰設(shè)為1.4,產(chǎn)品各生產(chǎn)工序所需的加工時間、加工機(jī)器以及各產(chǎn)品的交貨時間窗口見表2。

表2 加工數(shù)據(jù)Tab.2 Machining data

設(shè)定遺傳算法的參數(shù)為:交叉概率Pc=0.4,變異概率Pm=0.02,種群尺寸PS=100,記憶庫尺寸MS=20,最大迭代次數(shù)N=100,爬山算法的最大迭代次數(shù)N’=5。分別采用不帶記憶功能的普通遺傳算法和文中的改進(jìn)算法,進(jìn)行20次仿真實(shí)驗(yàn),兩種算法的實(shí)驗(yàn)結(jié)果見表3,圖2為兩種算法的收斂情況比較。

表3 實(shí)驗(yàn)結(jié)果Tab.3 Experimental results

圖2 兩種算法收斂情況Fig.2 Convergence situation of the two algorithms

從表3中可以看出,本文算法求解出了問題的最優(yōu)解0,在20次仿真中搜索到最優(yōu)解的次數(shù)為18次,而且搜索到最優(yōu)值的平均迭代次數(shù)和平均計算時間都要優(yōu)于普通遺傳算法,說明改進(jìn)遺傳算法的運(yùn)算性能穩(wěn)定,搜索能力強(qiáng)。通過圖2的比較則可以進(jìn)一步看出,在整個搜索過程中,本文算法的收斂速度較快,在41代左右達(dá)到全局最優(yōu)解0,而普通遺傳算法的收斂速度明顯較慢,且在43代左右以后逐步陷入局部最優(yōu)。綜上所述可知,無論是在求解質(zhì)量還是收斂速度上,文中的改進(jìn)遺傳算法都優(yōu)于不帶記憶功能的普通遺傳算法。

仿真結(jié)果表明,通過本文算法可以求解出懲罰值為0的最佳調(diào)度方案,即所有產(chǎn)品均可在交貨窗口內(nèi)按時完成生產(chǎn)。求解出的最優(yōu)個體如下:

4 結(jié)論

為求解作業(yè)車間提前/拖期調(diào)度問題,文中提出一種基于雙染色體矩陣編碼的改進(jìn)遺傳算法,并利用記憶庫和爬山算法提升算法的尋優(yōu)能力和搜索速度。改進(jìn)遺傳算法的編碼簡潔、直觀,收斂性能好,并能較好地解決相關(guān)的車間調(diào)度問題,滿足大規(guī)模此類調(diào)度問題的需要。下一步將繼續(xù)研究結(jié)合其他啟發(fā)式方法的改進(jìn)遺傳算法在多目標(biāo)作業(yè)車間調(diào)度問題中的應(yīng)用,并進(jìn)一步提高算法的性能。

【參 考 文 獻(xiàn)】

[1]王萬良,吳啟迪.生產(chǎn)調(diào)度智能算法及其應(yīng)用[M].北京:科學(xué)出版社,2007.

[2]蘇 瑩,李 杰,陰慧輝,等.改進(jìn)遺傳算法求解作業(yè)車間調(diào)度問題[J].制造技術(shù)與機(jī)床,2010,10:104 -108.

[3]黃 志,黃文奇.一種基于禁忌搜索的作業(yè)車間調(diào)度算法[J].計算機(jī)工程與應(yīng)用,2006,03:12 -14.

[4]趙良輝,鄧飛其.用于作業(yè)車間調(diào)度的模擬退火算法[J].制造業(yè)自動化,2006,28(3):10 -23.

[5]蘇 春,王大俠.基于改進(jìn)遺傳算法的偏柔性作業(yè)車間調(diào)度[J].工業(yè)工程,2010,13(6):61 -65.

[6]陳 杰,張力菠.供應(yīng)鏈環(huán)境中交貨期問題的研究[J].中國制造業(yè)信息化,2005,34(4):105 -107.

[7]潘全科,朱劍英.多工藝路線的作業(yè)車間模糊調(diào)度優(yōu)化[J].中國機(jī)械工程,2004,15(24):2199 -2202.

[8]呂文閣,劉志勇,成思源,等.基于競選算法的生產(chǎn)調(diào)度問題的研究[J].機(jī)床與液壓,2009,37(10):33 -36.

[9]玄光男,程潤偉.遺傳算法與工程優(yōu)化[M].北京:清華大學(xué)出版社,2004.

[10]韓冰源,肖生苓.配送中心線路優(yōu)化方法的探討[J].森林工程,2005,21(2):67 -68.

[11]郎茂祥.配送車輛優(yōu)化調(diào)度模型與算法[M].北京:電子工業(yè)出版社,2009.

[12]郎茂祥,胡思繼.用混合遺傳算法求解物流配送優(yōu)化問題的研究[J].中國管理科學(xué),2002,10(5):51 -56.

猜你喜歡
染色體遺傳算法車間
100MW光伏車間自動化改造方案設(shè)計
智能制造(2021年4期)2021-11-04 08:54:28
多一條X染色體,壽命會更長
招工啦
為什么男性要有一條X染色體?
“扶貧車間”拔窮根
基于自適應(yīng)遺傳算法的CSAMT一維反演
一種基于遺傳算法的聚類分析方法在DNA序列比較中的應(yīng)用
基于遺傳算法和LS-SVM的財務(wù)危機(jī)預(yù)測
把農(nóng)業(yè)搬進(jìn)車間
能忍的人壽命長
闽侯县| 密云县| 西乌珠穆沁旗| 汉中市| 宜丰县| 梧州市| 临沭县| 赣榆县| 府谷县| 东阳市| 石屏县| 永济市| 平果县| 福贡县| 玉树县| 东台市| 从化市| 万宁市| 云阳县| 军事| 和田市| 承德县| 汾阳市| 余庆县| 理塘县| 会泽县| 罗源县| 滁州市| 涞水县| 云安县| 汤原县| 清河县| 越西县| 邯郸县| 鄂托克旗| 禄丰县| 锡林浩特市| 汝城县| 南溪县| 湖北省| 桐柏县|