2021采用遺傳算法進行車間平面布置

《2021采用遺傳算法進行車間平面布置》由會員分享，可在線閱讀，更多相關(guān)《2021采用遺傳算法進行車間平面布置（19頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、采用遺傳算法進行車間平面布置 文章編號:100725429(2002)0420030204 收稿日期:2001-11-22 基金項目:清華大學985工程“數(shù)字化轎車”資助項目 作者簡介:王昕巖(1977-),男,北京人,清華大學工業(yè)工程系碩士生。 采用遺傳算法進行車間平面布置 王昕巖,蔡臨寧,姚　健 (清華大學工業(yè)工程系,北京100084) 摘要:利用遺傳算法進行車間的平面布置。計算結(jié)果表明,應用遺傳算法求解車間布置問題 不僅可以獲得優(yōu)化程度高的近似最優(yōu)解,而且具有高的計算效率和很強的實際應用性。 關(guān)鍵詞:遺傳算法;平面布置;車間 中圖分類號:TH162.1 文獻標識

2、碼:A Application of G enetic Algorithms in Plant Layout W ANG X in 2yan ,C AI Lin 2ning ,Y AO Jian (Dept.of Industrial Engineering ,Tsinghua University ,Beijing 100084,China ) Abstract :G enetic alg orithm is a kind of global stochastic research method that simulates biological ev olu 2tion proc

3、ess to achieve optimal results.The result shows that genetic alg orithms can not only get excellent near optimal s olutions ,but als o have high com puting efficiency and practicability. K ey w ords :genetic alg orithm ;plant lay out ;w orkshop 1　引言 車間平面布置是使車間內(nèi)的人、設備和物料在空 間上實現(xiàn)最合理的組合,使其總體物流費用最低。1

4、957年K oopm ans 和Beckm ann 把布置問題模型化為二次分派問題(QAP ),引起了人們對布置問題的深入研究。 解決平面布置的方法有很多,按照優(yōu)化程度,主要可分為兩大類:最優(yōu)化算法(optimal alg orithms )和啟發(fā)式算法(heuristic alg orithms )。前者能夠獲得問題精確的最優(yōu)解;而后者只能獲得滿足一定精確程度的近似最優(yōu)解。一般來說中小規(guī)模的問題(設施個數(shù)小于14個)可以通過最優(yōu)化算法來求解。但是隨著設施個數(shù)的不斷增加,問題的計算量呈指數(shù)遞增,最優(yōu)化算法就不能非常有效地解決問題。而啟發(fā)式算法卻能夠在小計算量的情況下獲得近似最優(yōu)解,從而有效地

5、解決大規(guī)模的平面布置問題。啟發(fā)式算法有很多種,如:模擬退火算法、T ABU 尋優(yōu)算法、爬山算法、遺傳算法等。由于遺傳算法計算效率高,求解效果好,得到了廣泛的應用。 平面布置中的遺傳算法由編碼方法、選擇、交叉算子、變異算子以及解碼調(diào)整等步驟組成。不同的編碼及 算子組合會構(gòu)成大量的遺傳算法。通過研究,本文選擇了賭盤選擇、基于順序的交叉和啟發(fā)式變異算子組合的遺傳算法進行了某制造車間的塊狀平面布置。 2　平面布置的數(shù)學模型 平面布置問題數(shù)學模型是一種組合優(yōu)化問題。組合優(yōu)化問題有3個基本要素:變量、約束和目標函數(shù)。在求解過程中選定的基本參數(shù)稱為變量,對變量取值的種種限制稱為約束,表示可行方案衡量

6、標準的函數(shù)稱為目標函數(shù)。平面布置問題的變量是各個設施在空間中的位置組成的向量;約束就是各個設施在空間中的位置約束;目標可以是單個的,也可以是多個的,大多數(shù)的車間布置問題都是以設施間物料搬運費用最小為目標。 車間平面布置問題可以抽象為以下的數(shù)學模型: 目標函數(shù): 　f (x )=min k ρi ρj c ij (k )d ij (k )e ij (k )+ρj f j (k )(1) 式中c ij (k )表示第k 種布局方案中,第i 個位置與第j 個位置的物流量; d ij (k )表示第k 種布局方案中,第i 個位置與第j 個位置間的距離; e ij (k )表示第k 種布

7、局方案中,第i 個位置與第j 個位置間,單位距離單位物流量的物流運送費用; f j (k )表示第k 種布局方案中,設施布置在第j 個位置所需的固定費用。 一般來說對應于目標函數(shù)的遺傳算法的適值函數(shù)可由以下轉(zhuǎn)換機制實現(xiàn): 適值函數(shù): fitf unc = C max -f (x ),　f (x )ΦC max 　0, f (x )>C max (2) 式中C max 是預定的參數(shù),保證大多數(shù)解的適值為正值。 3　遺傳算法 3.1　遺傳算法的基本流程與特點 遺傳算法[1～3]是一種隨機性的全局搜索算法。它是模擬生物的進化過程中優(yōu)勝劣汰的過程來求解 優(yōu)化問題。首先,它將問

8、題的解轉(zhuǎn)化成一串數(shù)字(由自然數(shù)組成),把它類比為生物體基因的染色體,用它代表問題的某個解,稱作解的染色體(chrom os ome ,以下簡稱染色體)。這個將問題的解轉(zhuǎn)化成染色體的過程叫做編碼。其次,隨機產(chǎn)生一定數(shù)量的染色體組成一個染色體集合,把它稱為群落。群落中染色體的數(shù)目在計算過程當中始終是固定的,令它為P (即種群數(shù)量)。這個隨機產(chǎn)生的群落叫做遺傳算法的初始代。第三,制定評價解優(yōu)劣的準則———適應性函數(shù)值(fitness ,以下簡稱適值)。它的值越高,染色體所代表的解就越“優(yōu)”。適值是對解的評價,當然也就代表了問題的目標,它與平面布置問題的目標函數(shù)有著密切的關(guān)系。最后,通過對初始代的選擇

9、(selection )、交叉(cross over )、變異(mutation ) 計算產(chǎn)生子代個體———新的一個染色體群落。對這新的一代繼續(xù)進行選擇、交叉、變異計算,它又產(chǎn)生自己的子代個體。就這樣循環(huán)操作,直到滿足循環(huán)一定代數(shù)為止。最后一代中最優(yōu)的染色體對應的解就是近似最優(yōu)解。遺傳算法就是這樣實現(xiàn)隨機尋優(yōu)搜索的,其基本步驟如圖1所示。 圖1　遺傳算法流程圖 與傳統(tǒng)的優(yōu)化算法相比,遺傳算法具有以下特點:(1)直接對解編碼的集合進行操作,而不是對解集本身;(2)它的尋優(yōu)始于解的一個群落,而不是單個解;(3)它利用目標函數(shù)本身的信息建立尋優(yōu)方向,而不是利用其導數(shù)信息建立尋優(yōu)方向,不存在求

10、 導和函數(shù)連續(xù)性的限制,因此它對優(yōu)化設計問題的限制較少,僅要求問題是可計算的;(4)它采用概率化的尋優(yōu)方法,能自動獲取和指導優(yōu)化的搜索空間,自適應地調(diào)整搜索方向,不需要確定的規(guī)則。遺傳算法利用概率轉(zhuǎn)移規(guī)則,可以在一個具有不確定性的空間上尋優(yōu)。與一般的隨機型優(yōu)化方法相比,遺傳算法不是從一點出發(fā)沿一條線尋優(yōu),而是在整個解空間同時開始尋優(yōu)搜索,因此可以有效地避免陷入局部極小點,具備全局最優(yōu)搜索性。 3.2　平面布置問題解的編碼 如何將問題的解轉(zhuǎn)化成染色體是應用遺傳算法解決平面布置問題的基礎(chǔ)。編碼方案的好壞也直接關(guān)系到遺傳算子的設計,進而影響問題解決的優(yōu)化程度。 在一個二維平面布置中,本文采用圖

11、2所示的編碼方式,即染色體為9|5|1|4|8|6|10|7|2|3|11|。 圖2　編碼方式圖 　 3.3　遺傳算法的算子 遺傳算子是實現(xiàn)遺傳優(yōu)化的最基本的計算,也 是影響算法計算效果的最大因素,它包括選擇算子、交叉算子和變異算子。 目前在平面布置問題中應用較為廣泛的選擇算子有:賭盤選擇等;交叉算子有:單點交叉、OX 交叉、基于位置的交叉、基于順序的交叉等;變異算子有:反轉(zhuǎn)變異、移位變異、插入變異、互換變異、啟發(fā)式變異等。 通過分析比較,發(fā)現(xiàn)賭盤選擇、基于順序的交叉和啟發(fā)式變異算子組合而成的遺傳算法在平面布置問題中具有較好的遺傳規(guī)律。下面對賭盤選擇、基于順序的交叉和啟發(fā)式變異算

12、子三種算子進行簡單的介紹。 3.3.1　賭盤選擇算子 賭盤選擇算子[3]選擇將適值大的個體選進準備進行交叉的個體隊伍中,而適值小的盡量避免被選中。它是以個體的適值占群落中所有個體的適值總和的比例為標準進行選擇的。這種算法可以直觀地用賭盤選擇圖(圖3)來闡釋。圖中扇形面積占圓面積的比例就是個體適值占適值總和的比例。每次選擇轉(zhuǎn)動一次圓盤, 圓盤停下時指針指向的個體就是被選中的個體。因此個體所占扇形面積越大,被指針指中的可能性就越大。 圖3　賭盤選擇圖 3.3.2　基于順序的交叉算子 基于順序的交叉算子[3]的基本步驟如下: 步驟1:從第一個父代個體中隨機選若干個位置,存儲這些位置上對

13、應的元素; 步驟2:刪去第二個父代個體中這些元素,將第二個父代個體其他的元素復制到一個空字串的相應位置,產(chǎn)生一個原始子代個體; 步驟3:將第一個父代個體中被存儲的元素按在第一個父代個體中的順序定位到子代個體的空缺位置上。 步驟說明示例如下: 父代個體15　6　4　3　2　1父代個體2○24○153○6子代個體 6 4 2 5 3 1 示例中,第一步,父代個體1中被存儲的元素及其相應順序為6,2,1;第二步,刪除父代個體2中6,2,1三個元素(圓圈內(nèi)的3個元素),并將元素4,5,3按原來位置填入子代個體中,再將6,2,1三個元素按序填入。 3.3.3　啟發(fā)式變異算子

14、 啟發(fā)式變異算子[3]對一個染色體按它的鄰域交換不多于n 個基因位,可獲得一組染色體,選擇其中 適值最大的一個作為變異產(chǎn)生的子代個體。啟發(fā)式變異過程如下: 步驟1:隨機地選出n 個基因; 步驟2:按所有選出基因的可能的換位產(chǎn)生鄰域; 步驟3:評估所有鄰域點,選出最好的作為變異產(chǎn)生的子代個體。 步驟說明如下: 原始子代個體264135 子代個體鄰域 2643152341652346152143652 1 4 6 3 5 4　算例及結(jié)果 通過上述的編碼及遺傳算子組合,利用C ++實現(xiàn)了計算機輔助布置設計軟件TH 2C AFP 的核心計算模塊。 需要指出的是,計算機輔助布

15、置方法分為構(gòu)建型及改進型方法。采用遺傳算法是一種對已有平面布置進行改進的改進型方法,其初始布置可以隨機生成也可以由構(gòu)造型方法生成。 本文算例由某制造廠的平面布置問題抽象而得來。這里將車間分為11個工作區(qū),用1至11來代表各工作區(qū)。其面積如表1所示,各工作區(qū)中心間的直線距離如表2所示。各區(qū)之間的物流量如表3所示。優(yōu)化目標以設施間的物料搬運費用最小為目標。 計算中采用的參數(shù)為:種群數(shù)量P =100,交叉概率Pc =0.9,變異概率P m =0.05,最大代數(shù)maxgen =4000。采用以上參數(shù)重復進行10次計算。 表1　工作區(qū)面積 工作區(qū) 面積(m 2) 1400 22003200

16、4260520063407500840094001026011 320 王昕巖等:采用遺傳算法進行車間平面布置 表2　距離表 1 2345678910111 0152533404247553530202150101825273242504535325100815172232525545433188079142444495354025157027173742526422717920515354050747322214750103035408554232241715100202535935505244373530200515103045554942403525501011 20 3

17、5 45 53 52 50 40 35 15 10 表3　物流量表 1 2345678910111 05221141291250251278238322074494565425708781851511480341336612473058475747984507632818411870948922583469053109365373450511 1 8 5 1 6 5 2 8 3 5 計算結(jié)果如表4所示。其中獲得的最小費用為12202,染色體為:1|10|5|4|3|9|7|6|8|11|2|。經(jīng)過 解碼調(diào)整后,與該解相應的布局

18、圖如圖4所示。 表4　計算結(jié)果 次數(shù) 最小費用 染色體 1 1269011|5|6|4|9|8|7|3|2|1|10|2122021|10|5|4|3|9|7|6|8|11|2|3126286|11|8|2|7|9|3|4|5|1|10|4124965|1|10|4|3|6|7|9|8|11|2|5131185|2|11|8|6|9|7|10|3|1|4|6126101|10|3|4|9|7|8|6|2|11|5|71281211|6|3|5|4|7|9|8|2|1|10|8124482|1|10|5|4|7|3|9|6|8|11|91267211|8|6|3|9|7|4|5|

19、1|2|10|10 12202 1|10|5|4|3|9|7|6|8|11|2| 圖4　塊狀布置圖 通過遺傳算法對實際算例的計算,可以很明顯 地看出它不僅可以獲得優(yōu)化程度高的近似最優(yōu)解, 而且計算效率也比較高。如果在同樣的情況下利用最優(yōu)化算法,需要搜索整個可行解空間,僅僅計算目 標函數(shù)值就需要約n !=39916800次,而遺傳算法無需遍歷整個解空間,計算目標函數(shù)值僅需P 3maxgen =400000次,數(shù)量級相差102,大大節(jié)省了計算時間。另外,遺傳算法盡量使優(yōu)化程度高的解參與計算,從而保證近似最優(yōu)解的優(yōu)化程度。 本文采用遺傳算法對某企業(yè)11個部門進行了布置設計。需要指

20、出的是,該方法及程序完全可以應用到大規(guī)模的布置設計中,而且規(guī)模越大,越可以反映出該方法的效率。僅以目標函數(shù)計算次數(shù)為例,如果固定遺傳算法參數(shù)不變,n !/(P 3maxgen )將隨著n 的增長而快速增大。這證明設施個數(shù)越多,遺傳算法的計算效率越高。盡管設施個數(shù)的增大導致解空間變大,可能減弱求解精度,但是通過調(diào)整交叉率與編譯率能夠有效地彌補這一缺陷。因此基于遺傳算法的TH 2C AFP 具有很強的實際應用性。 5　結(jié)論 采用遺傳算法編制了計算機輔助布置設計軟件TH 2C AFP 的核心模塊,并通過算例計算,說明了這種方法的計算效率及精度。 Industrial Engineering a

21、nd Management N o.4,2002工業(yè)工程與管理　2002年第4期 參考文獻: [1]T avakkoli2M oghaddain R,Shayan E.Facility Lay out Design by G enetic Alg orithms[J].C om puters and Industrial Engineering,1998,35:527～530.[2]G ero J S,K azav ov V A.Ev olving Design G enes in S pace Lay out Plan2 ning Problems[J].Artificial Int

22、elligence in Engineering,1998,(12): 163-176. [3]玄光男(日),程潤偉.遺傳算法與工程設計[M].汪定偉,唐加 福,黃敏譯.北京:科學出版社,2000. 符合WT O規(guī)則的保護對策 熟悉并靈活運用WT O規(guī)則,維護國家及企業(yè)利益,是我國政府和企業(yè)界在“入世”后的過渡期乃至更遠的將來需要認真研究的問題。 1.發(fā)展中國家適用的條款 WT O允許發(fā)展中國家為保護民族工業(yè)和本國經(jīng)濟利益而使用保護措施,概括起來為以下3條: (1)關(guān)于保護幼稚工業(yè)的條款。WT O允許發(fā)展中國家為了加速某一特定產(chǎn)業(yè)的建立,即保護幼稚產(chǎn)業(yè),在與締約國和其他利害相

23、關(guān)的締約國達成協(xié)議的基礎(chǔ)上,可以修改和撤銷關(guān)稅減讓表中的關(guān)稅減讓。也就是說,即使列入關(guān)稅減讓表的關(guān)稅仍然可以提高(修改和撤銷)。同時,若提高關(guān)稅后仍然不能滿足經(jīng)濟發(fā)展需要,該國還可采取數(shù)量限制等措施。根據(jù)“東京回合”的決定,若拖延采取措施時會對執(zhí)行其經(jīng)濟發(fā)展計劃和政策造成困難,該提出申請的進口締約國可以在通知締約國全體后立即臨時修改或撤銷有關(guān)關(guān)稅減讓。這一決定增加了發(fā)展中國家使用關(guān)稅措施的彈性,無需締約國全體事先同意,而在采取行動后進行談判。 (2)關(guān)于維護國際收支的條款。WT O允許發(fā)展中國家在面臨國際收支困難時,采取限制進口商品數(shù)量或價值的辦法來控制它的一般水平。在一定條件下可以在歧視性

24、限制基礎(chǔ)上實施。也就是說,發(fā)展中國家可以針對不同進口產(chǎn)品確定不同的限制方式,并可按其經(jīng)濟發(fā)展政策的需要優(yōu)先進口急需的產(chǎn)品。這一規(guī)定使符合條件的國家在制訂進口配額措施時,可以更有針對性,而不受世貿(mào)組織無歧視原則的約束。 (3)關(guān)于進口保障的條款。WT O允許締約國對特定進口產(chǎn)品采取緊急限制行動,前提是產(chǎn)品進口數(shù)量激增,給國內(nèi)生產(chǎn)者造成嚴重損害和威脅。保障行動可以采取關(guān)稅措施,也可以采取非關(guān)稅措施。該條款同樣規(guī)定,若拖延采取措施會造成難以彌補的損害,該國可以先行動后談判。值得一提的是,該條款并未規(guī)定如何確定損害和如何進行確定損害的調(diào)查;也未就“國內(nèi)生產(chǎn)者”下定義,進口國可以根據(jù)自己的標準來確定國

25、內(nèi)生產(chǎn)者的范圍。因而,援引該條款具有更強的靈活性。 以上3條保護條款是對發(fā)展中國家的一種優(yōu)惠,我國應加以充分利用,它可以緩減“入世”過渡期外國企業(yè)給我國企業(yè)帶來的強大沖擊,并為我國經(jīng)濟體制改革、產(chǎn)業(yè)結(jié)構(gòu)調(diào)整提供一個緩沖的機會。 2.關(guān)于反傾銷與反補貼 反傾銷與反補貼是WT O賦予組織成員保護自己市場的重要手段,其中反傾銷是各國采用最多的手段。中國產(chǎn)品在國外遭到的第一例反傾銷調(diào)查為1979年8月,中國出口歐洲的糖精鈉遭到當時歐共體的反傾銷調(diào)查,迄今為止,中國產(chǎn)品已遭到來自29個國家和地區(qū)的400多起、涉及4000多種商品的反傾銷調(diào)查,位居全球之首。我國企業(yè)之所以在國際反傾銷訴訟中長期處于被

26、動地位,一方面因為我國很多出口產(chǎn)品屬于勞動密集型產(chǎn)品,在與發(fā)達國家的同類產(chǎn)品的競爭中處于明顯有利地位,導致歐美等發(fā)達國家的貿(mào)易逆差不斷上升;另一方面因為我國以前一直被擋在世貿(mào)組織的大門外,被一 些國家視為“非市場經(jīng)濟國家”,因此企業(yè)的生產(chǎn)成本往往不被考慮?！叭胧馈焙?由于關(guān)稅與非關(guān)稅壁壘的削弱,我國企業(yè)面對的反傾銷訴訟會進一步增多。因此我國企業(yè)一定要在遭遇反傾銷指控時積極應訴,捍衛(wèi)自己的合法權(quán)益和正當市場。因為外國對我國某種產(chǎn)品傾銷的指控一旦認定,則所有來自中國的同一產(chǎn)品將被征收同樣的高額反傾銷稅,最終將導致我國企業(yè)自動放棄該國市場的嚴重后果。對于中國企業(yè)來說,應密切注意在國內(nèi)市場銷售的同類

27、外國產(chǎn)品的商情,一旦發(fā)現(xiàn)有傾銷或補貼嫌疑,應配合本行業(yè)和有關(guān)主管部門采取必要的反傾銷或反補貼措施,以維護自己的合法權(quán)益。 3.關(guān)于技術(shù)性貿(mào)易政策 技術(shù)性貿(mào)易政策是指商品進口國在實施貿(mào)易進口管制時,通過頒布法律、法令、條例、規(guī)定、建立技術(shù)標準、認證制度、衛(wèi)生檢驗檢疫制度等,提高對進口產(chǎn)品的技術(shù)要求,增加進口難度,以保障國家安全、保護消費者利益,最終保持國際收支平衡。WT O承認技術(shù)性壁壘存在的合理性和必要性,只是要求技術(shù)壁壘不要妨礙正常的國際貿(mào)易,不得具有歧視性。20世紀90年代以來發(fā)達國家不斷提高進口產(chǎn)品的環(huán)保標準。1992年5月歐共體正式實施所謂“生態(tài)標簽”制度,1993年7月正式推出歐

28、洲環(huán)境標志,1995年4月,由發(fā)達國家控制的國際標準化組織開始實施《國際環(huán)境標準監(jiān)察制度》。這些“綠色壁壘”曾影響到我國產(chǎn)品出口。發(fā)達國家的技術(shù)壁壘,有的帶有明顯的歧視性,這是我們所不能接受的,也是違反WT O規(guī)則的。但是也應看到我國出口產(chǎn)品的品質(zhì)、技術(shù)標準與國際市場要求之間的差距。因此,只有加強管理、提高質(zhì)量,同時掌握國外市場的標準要求,加快我國產(chǎn)品的標準化建設才能不授人以柄;同時,我國政府和企業(yè)應密切配合,加強這方面的研究,做到既不違反WT O規(guī)定,又能有效地保護和促進我國的工業(yè)發(fā)展。在這方面,可以借鑒發(fā)達國家和其他發(fā)展中國家的經(jīng)驗。例如,為了限制英法聯(lián)合研制的協(xié)和號超音速客機的進口,美國

29、測定協(xié)和號客機進場噪音達到119.5分貝以上,超過了美國民航機噪音標準的規(guī)定而不允許該機在美國領(lǐng)土上降落,從而阻止了協(xié)和號客機進入美國航空市場。 4.關(guān)于知識產(chǎn)權(quán)協(xié)議 WT O《與貿(mào)易有關(guān)的知識產(chǎn)權(quán)協(xié)議》(簡稱TRIPS協(xié)議)規(guī)定,發(fā)展中國家和由計劃經(jīng)濟向市場經(jīng)濟過渡的國家“入世”后,在執(zhí)行該協(xié)議時允許有5年的過渡期。我國在1997年,為了促進加入世貿(mào)談判的進展,已經(jīng)宣布放棄過渡期的優(yōu)惠。也就是說,中國在加入世貿(mào)組織的同時,就必須完全執(zhí)行TRIPS協(xié)議。中國已經(jīng)修定了專利法、商標法和著作權(quán)法。在立法方面,中國已經(jīng)基本符合該協(xié)議的要求。但是,在知識產(chǎn)僅的實施方面,我國還面臨許多問題,它不僅涉及到立法、行政和司法,還涉及全民族的知識產(chǎn)權(quán)意識。“入世”后,西方發(fā)達國家可能會以中國沒有認真完全地執(zhí)行TRIPS協(xié)議為由,發(fā)起世貿(mào)組織爭端解決程序,甚至以訴諸貿(mào)易制裁相威協(xié)。對此,應予以高度重視。 (江蘇省鹽城市外經(jīng)貿(mào)委　金寧) 王昕巖等:采用遺傳算法進行車間平面布置