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

采用遺傳算法進行車間平面布置文章編號:100725429(2002)0420030204收稿日期:2001-11-22基金項目:清華大學985工程“數字化轎車”資助項目作者簡介:王昕巖(1977-),男,北京人,清華大學工業(yè)工程系碩士生。采用遺傳算法進行車間平面布置王昕巖,蔡臨寧,姚健(清華大學工業(yè)工程系,北京100084) 摘要:利用遺傳算法進行車間的平面布置。計算結果表明,應用遺傳算法求解車間布置問題 不僅可以獲得優(yōu)化程度高的近似最優(yōu)解,而且具有高的計算效率和很強的實際應用性。關鍵詞:遺傳算法;平面布置;車間中圖分類號:TH162.1 文獻標識碼:AApplication of G enetic Algorithms in Plant LayoutW 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 process 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 orkshop1引言車間平面布置是使車間內的人、設備和物料在空間上實現最合理的組合,使其總體物流費用最低。1957年K oopm ans 和Beckm ann 把布置問題模型化為二次分派問題(QAP ),引起了人們對布置問題的深入研究。解決平面布置的方法有很多,按照優(yōu)化程度,主要可分為兩大類:最優(yōu)化算法(optimal alg orithms )和啟發(fā)式算法(heuristic alg orithms )。前者能夠獲得問題精確的最優(yōu)解;而后者只能獲得滿足一定精確程度的近似最優(yōu)解。一般來說中小規(guī)模的問題(設施個數小于14個)可以通過最優(yōu)化算法來求解。但是隨著設施個數的不斷增加,問題的計算量呈指數遞增,最優(yōu)化算法就不能非常有效地解決問題。而啟發(fā)式算法卻能夠在小計算量的情況下獲得近似最優(yōu)解,從而有效地解決大規(guī)模的平面布置問題。啟發(fā)式算法有很多種,如:模擬退火算法、T ABU 尋優(yōu)算法、爬山算法、遺傳算法等。由于遺傳算法計算效率高,求解效果好,得到了廣泛的應用。平面布置中的遺傳算法由編碼方法、選擇、交叉算子、變異算子以及解碼調整等步驟組成。不同的編碼及算子組合會構成大量的遺傳算法。通過研究,本文選擇了賭盤選擇、基于順序的交叉和啟發(fā)式變異算子組合的遺傳算法進行了某制造車間的塊狀平面布置。2平面布置的數學模型平面布置問題數學模型是一種組合優(yōu)化問題。組合優(yōu)化問題有3個基本要素:變量、約束和目標函數。在求解過程中選定的基本參數稱為變量,對變量取值的種種限制稱為約束,表示可行方案衡量標準的函數稱為目標函數。平面布置問題的變量是各個設施在空間中的位置組成的向量;約束就是各個設施在空間中的位置約束;目標可以是單個的,也可以是多個的,大多數的車間布置問題都是以設施間物料搬運費用最小為目標。車間平面布置問題可以抽象為以下的數學模型:目標函數:f (x )=min ki j c ij (k )d ij (k )e ij (k )+jf j (k )(1)式中c ij (k )表示第k 種布局方案中,第i 個位置與第j 個位置的物流量;d ij (k )表示第k 種布局方案中,第i 個位置與第j 個位置間的距離;e ij (k )表示第k 種布局方案中,第i 個位置與第j 個位置間,單位距離單位物流量的物流運送費用;f j (k )表示第k 種布局方案中,設施布置在第j個位置所需的固定費用。一般來說對應于目標函數的遺傳算法的適值函數可由以下轉換機制實現:適值函數:fitf unc =C max -f (x ),f (x )C max0, f (x )>C max(2)式中C max 是預定的參數,保證大多數解的適值為正值。3遺傳算法3.1遺傳算法的基本流程與特點遺傳算法13是一種隨機性的全局搜索算法。它是模擬生物的進化過程中優(yōu)勝劣汰的過程來求解優(yōu)化問題。首先,它將問題的解轉化成一串數字(由自然數組成),把它類比為生物體基因的染色體,用它代表問題的某個解,稱作解的染色體(chrom os ome ,以下簡稱染色體)。這個將問題的解轉化成染色體的過程叫做編碼。其次,隨機產生一定數量的染色體組成一個染色體集合,把它稱為群落。群落中染色體的數目在計算過程當中始終是固定的,令它為P (即種群數量)。這個隨機產生的群落叫做遺傳算法的初始代。第三,制定評價解優(yōu)劣的準則適應性函數值(fitness ,以下簡稱適值)。它的值越高,染色體所代表的解就越“優(yōu)”。適值是對解的評價,當然也就代表了問題的目標,它與平面布置問題的目標函數有著密切的關系。最后,通過對初始代的選擇(selection )、交叉(cross over )、變異(mutation )計算產生子代個體新的一個染色體群落。對這新的一代繼續(xù)進行選擇、交叉、變異計算,它又產生自己的子代個體。就這樣循環(huán)操作,直到滿足循環(huán)一定代數為止。最后一代中最優(yōu)的染色體對應的解就是近似最優(yōu)解。遺傳算法就是這樣實現隨機尋優(yōu)搜索的,其基本步驟如圖1所示。圖1遺傳算法流程圖與傳統(tǒng)的優(yōu)化算法相比,遺傳算法具有以下特點:(1)直接對解編碼的集合進行操作,而不是對解集本身;(2)它的尋優(yōu)始于解的一個群落,而不是單個解;(3)它利用目標函數本身的信息建立尋優(yōu)方向,而不是利用其導數信息建立尋優(yōu)方向,不存在求導和函數連續(xù)性的限制,因此它對優(yōu)化設計問題的限制較少,僅要求問題是可計算的;(4)它采用概率化的尋優(yōu)方法,能自動獲取和指導優(yōu)化的搜索空間,自適應地調整搜索方向,不需要確定的規(guī)則。遺傳算法利用概率轉移規(guī)則,可以在一個具有不確定性的空間上尋優(yōu)。與一般的隨機型優(yōu)化方法相比,遺傳算法不是從一點出發(fā)沿一條線尋優(yōu),而是在整個解空間同時開始尋優(yōu)搜索,因此可以有效地避免陷入局部極小點,具備全局最優(yōu)搜索性。3.2平面布置問題解的編碼如何將問題的解轉化成染色體是應用遺傳算法解決平面布置問題的基礎。編碼方案的好壞也直接關系到遺傳算子的設計,進而影響問題解決的優(yōu)化程度。在一個二維平面布置中,本文采用圖2所示的編碼方式,即染色體為9|5|1|4|8|6|10|7|2|3|11|。圖2編碼方式圖3.3遺傳算法的算子遺傳算子是實現遺傳優(yōu)化的最基本的計算,也是影響算法計算效果的最大因素,它包括選擇算子、交叉算子和變異算子。目前在平面布置問題中應用較為廣泛的選擇算子有:賭盤選擇等;交叉算子有:單點交叉、OX 交叉、基于位置的交叉、基于順序的交叉等;變異算子有:反轉變異、移位變異、插入變異、互換變異、啟發(fā)式變異等。通過分析比較,發(fā)現賭盤選擇、基于順序的交叉和啟發(fā)式變異算子組合而成的遺傳算法在平面布置問題中具有較好的遺傳規(guī)律。下面對賭盤選擇、基于順序的交叉和啟發(fā)式變異算子三種算子進行簡單的介紹。3.3.1賭盤選擇算子賭盤選擇算子3選擇將適值大的個體選進準備進行交叉的個體隊伍中,而適值小的盡量避免被選中。它是以個體的適值占群落中所有個體的適值總和的比例為標準進行選擇的。這種算法可以直觀地用賭盤選擇圖(圖3)來闡釋。圖中扇形面積占圓面積的比例就是個體適值占適值總和的比例。每次選擇轉動一次圓盤,圓盤停下時指針指向的個體就是被選中的個體。因此個體所占扇形面積越大,被指針指中的可能性就越大。圖3賭盤選擇圖3.3.2基于順序的交叉算子基于順序的交叉算子3的基本步驟如下:步驟1:從第一個父代個體中隨機選若干個位置,存儲這些位置上對應的元素;步驟2:刪去第二個父代個體中這些元素,將第二個父代個體其他的元素復制到一個空字串的相應位置,產生一個原始子代個體;步驟3:將第一個父代個體中被存儲的元素按在第一個父代個體中的順序定位到子代個體的空缺位置上。步驟說明示例如下:父代個體1564321父代個體2241536子代個體642531 示例中,第一步,父代個體1中被存儲的元素及其相應順序為6,2,1;第二步,刪除父代個體2中6,2,1三個元素(圓圈內的3個元素),并將元素4,5,3按原來位置填入子代個體中,再將6,2,1三個元素按序填入。 3.3.3啟發(fā)式變異算子啟發(fā)式變異算子3對一個染色體按它的鄰域交換不多于n 個基因位,可獲得一組染色體,選擇其中適值最大的一個作為變異產生的子代個體。啟發(fā)式變異過程如下:步驟1:隨機地選出n 個基因;步驟2:按所有選出基因的可能的換位產生鄰域;步驟3:評估所有鄰域點,選出最好的作為變異產生的子代個體。步驟說明如下: 原始子代個體264135 子代個體鄰域2643152341652346152143652146354算例及結果通過上述的編碼及遺傳算子組合,利用C +實現了計算機輔助布置設計軟件TH 2C AFP 的核心計算模塊。需要指出的是,計算機輔助布置方法分為構建型及改進型方法。采用遺傳算法是一種對已有平面布置進行改進的改進型方法,其初始布置可以隨機生成也可以由構造型方法生成。本文算例由某制造廠的平面布置問題抽象而得來。這里將車間分為11個工作區(qū),用1至11來代表各工作區(qū)。其面積如表1所示,各工作區(qū)中心間的直線距離如表2所示。各區(qū)之間的物流量如表3所示。優(yōu)化目標以設施間的物料搬運費用最小為目標。計算中采用的參數為:種群數量P =100,交叉概率Pc =0.9,變異概率P m =0.05,最大代數maxgen =4000。采用以上參數重復進行10次計算。表1工作區(qū)面積工作區(qū)面積(m 2)1400220032004260520063407500840094001026011320王昕巖等:采用遺傳算法進行車間平面布置表2距離表12345678910111015253340424755353020215010182527324250453532510081517223252554543318807914244449535402515702717374252642271792051535405074732221475010303540855423224171510020253593550524437353020051510304555494240352550101120354553525040351510 表3物流量表12345678910111052211412912502512782383220744945654257087818515114803413366124730584757479845076328184118709489225834690531093653734505111851652835 計算結果如表4所示。其中獲得的最小費用為12202,染色體為:1|10|5|4|3|9|7|6|8|11|2|。經過 解碼調整后,與該解相應的布局圖如圖4所示。表4計算結果次數最小費用染色體11269011|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|1|2|10|10122021|10|5|4|3|9|7|6|8|11|2|圖4塊狀布置圖 通過遺傳算法對實際算例的計算,可以很明顯 地看出它不僅可以獲得優(yōu)化程度高的近似最優(yōu)解,而且計算效率也比較高。如果在同樣的情況下利用最優(yōu)化算法,需要搜索整個可行解空間,僅僅計算目標函數值就需要約n !=39916800次,而遺傳算法無需遍歷整個解空間,計算目標函數值僅需P 3maxgen =400000次,數量級相差102,大大節(jié)省了計算時間。另外,遺傳算法盡量使優(yōu)化程度高的解參與計算,從而保證近似最優(yōu)解的優(yōu)化程度。本文采用遺傳算法對某企業(yè)11個部門進行了布置設計。需要指出的是,該方法及程序完全可以應用到大規(guī)模的布置設計中,而且規(guī)模越大,越可以反映出該方法的效率。僅以目標函數計算次數為例,如果固定遺傳算法參數不變,n !/(P 3maxgen )將隨著n 的增長而快速增大。這證明設施個數越多,遺傳算法的計算效率越高。盡管設施個數的增大導致解空間變大,可能減弱求解精度,但是通過調整交叉率與編譯率能夠有效地彌補這一缺陷。因此基于遺傳算法的TH 2C AFP 具有很強的實際應用性。5結論采用遺傳算法編制了計算機輔助布置設計軟件TH 2C AFP 的核心模塊,并通過算例計算,說明了這種方法的計算效率及精度。Industrial Engineering and Management N o.4,2002工業(yè)工程與管理2002年第4期參考文獻:1T avakkoli2M oghaddain R,Shayan E.Facility Lay out Design by G eneticAlg orithmsJ.C om puters and Industrial Engineering,1998,35:527530.2G ero J S,K azav ov V A.Ev olving Design G enes in S pace Lay out Plan2ning ProblemsJ.Artificial Intelligence in Engineering,1998,(12): 163-176.3玄光男(日),程潤偉.遺傳算法與工程設計M.汪定偉,唐加福,黃敏譯.北京:科學出版社,2000.符合WT O規(guī)則的保護對策 熟悉并靈活運用WT O規(guī)則,維護國家及企業(yè)利益,是我國政府和企業(yè)界在“入世”后的過渡期乃至更遠的將來需要認真研究的問題。 1.發(fā)展中國家適用的條款WT O允許發(fā)展中國家為保護民族工業(yè)和本國經濟利益而使用保護措施,概括起來為以下3條:(1)關于保護幼稚工業(yè)的條款。WT O允許發(fā)展中國家為了加速某一特定產業(yè)的建立,即保護幼稚產業(yè),在與締約國和其他利害相關的締約國達成協議的基礎上,可以修改和撤銷關稅減讓表中的關稅減讓。也就是說,即使列入關稅減讓表的關稅仍然可以提高(修改和撤銷)。同時,若提高關稅后仍然不能滿足經濟發(fā)展需要,該國還可采取數量限制等措施。根據“東京回合”的決定,若拖延采取措施時會對執(zhí)行其經濟發(fā)展計劃和政策造成困難,該提出申請的進口締約國可以在通知締約國全體后立即臨時修改或撤銷有關關稅減讓。這一決定增加了發(fā)展中國家使用關稅措施的彈性,無需締約國全體事先同意,而在采取行動后進行談判。(2)關于維護國際收支的條款。WT O允許發(fā)展中國家在面臨國際收支困難時,采取限制進口商品數量或價值的辦法來控制它的一般水平。在一定條件下可以在歧視性限制基礎上實施。也就是說,發(fā)展中國家可以針對不同進口產品確定不同的限制方式,并可按其經濟發(fā)展政策的需要優(yōu)先進口急需的產品。這一規(guī)定使符合條件的國家在制訂進口配額措施時,可以更有針對性,而不受世貿組織無歧視原則的約束。(3)關于進口保障的條款。WT O允許締約國對特定進口產品采取緊急限制行動,前提是產品進口數量激增,給國內生產者造成嚴重損害和威脅。保障行動可以采取關稅措施,也可以采取非關稅措施。該條款同樣規(guī)定,若拖延采取措施會造成難以彌補的損害,該國可以先行動后談判。值得一提的是,該條款并未規(guī)定如何確定損害和如何進行確定損害的調查;也未就“國內生產者”下定義,進口國可以根據自己的標準來確定國內生產者的范圍。因而,援引該條款具有更強的靈活性。以上3條保護條款是對發(fā)展中國家的一種優(yōu)惠,我國應加以充分利用,它可以緩減“入世”過渡期外國企業(yè)給我國企業(yè)帶來的強大沖擊,并為我國經濟體制改革、產業(yè)結構調整提供一個緩沖的機會。2.關于反傾銷與反補貼反傾銷與反補貼是WT O賦予組織成員保護自己市場的重要手段,其中反傾銷是各國采用最多的手段。中國產品在國外遭到的第一例反傾銷調查為1979年8月,中國出口歐洲的糖精鈉遭到當時歐共體的反傾銷調查,迄今為止,中國產品已遭到來自29個國家和地區(qū)的400多起、涉及4000多種商品的反傾銷調查,位居全球之首。我國企業(yè)之所以在國際反傾銷訴訟中長期處于被動地位,一方面因為我國很多出口產品屬于勞動密集型產品,在與發(fā)達國家的同類產品的競爭中處于明顯有利地位,導致歐美等發(fā)達國家的貿易逆差不斷上升;另一方面因為我國以前一直被擋在世貿組織的大門外,被一些國家視為“非市場經濟國家”,因此企業(yè)的生產成本往往不被考慮。“入世”后,由于關稅與非關稅壁壘的削弱,我國企業(yè)面對的反傾銷訴訟會進一步增多。因此我國企業(yè)一定要在遭遇反傾銷指控時積極應訴,捍衛(wèi)自己的合法權益和正當市場。因為外國對我國某種產品傾銷的指控一旦認定,則所有來自中國的同一產品將被征收同樣的高額反傾銷稅,最終將導致我國企業(yè)自動放棄該國市場的嚴重后果。對于中國企業(yè)來說,應密切注意在國內市場銷售的同類外國產品的商情,一旦發(fā)現有傾銷或補貼嫌疑,應配合本行業(yè)和有關主管部門采取必要的反傾銷或反補貼措施,以維護自己的合法權益。3.關于技術性貿易政策技術性貿易政策是指商品進口國在實施貿易進口管制時,通過頒布法律、法令、條例、規(guī)定、建立技術標準、認證制度、衛(wèi)生檢驗檢疫制度等,提高對進口產品的技術要求,增加進口難度,以保障國家安全、保護消費者利益,最終保持國際收支平衡。WT O承認技術性壁壘存在的合理性和必要性,只是要求技術壁壘不要妨礙正常的國際貿易,不得具有歧視性。20世紀90年代以來發(fā)達國家不斷提高進口產品的環(huán)保標準。1992年5月歐共體正式實施所謂“生態(tài)標簽”制度,1993年7月正式推出歐洲環(huán)境標志,1995年4月,由發(fā)達國家控制的國際標準化組織開始實施國際環(huán)境標準監(jiān)察制度。這些“綠色壁壘”曾影響到我國產品出口。發(fā)達國家的技術壁壘,有的帶有明顯的歧視性,這是我們所不能接受的,也是違反WT O規(guī)則的。但是也應看到我國出口產品的品質、技術標準與國際市場要求之間的差距。因此,只有加強管理、提高質量,同時掌握國外市場的標準要求,加快我國產品的標準化建設才能不授人以柄;同時,我國政府和企業(yè)應密切配合,加強這方面的研究,做到既不違反WT O規(guī)定,又能有效地保護和促進我國的工業(yè)發(fā)展。在這方面,可以借鑒發(fā)達國家和其他發(fā)展中國家的經驗。例如,為了限制英法聯合研制的協和號超音速客機的進口,美國測定協和號客機進場噪音達到119.5分貝以上,超過了美國民航機噪音標準的規(guī)定而不允許該機在美國領土上降落,從而阻止了協和號客機進入美國航空市場。4.關于知識產權協議WT O與貿易有關的知識產權協議(簡稱TRIPS協議)規(guī)定,發(fā)展中國家和由計劃經濟向市場經濟過渡的國家“入世”后,在執(zhí)行該協議時允許有5年的過渡期。我國在1997年,為了促進加入世貿談判的進展,已經宣布放棄過渡期的優(yōu)惠。也就是說,中國在加入世貿組織的同時,就必須完全執(zhí)行TRIPS協議。中國已經修定了專利法、商標法和著作權法。在立法方面,中國已經基本符合該協議的要求。但是,在知識產僅的實施方面,我國還面臨許多問題,它不僅涉及到立法、行政和司法,還涉及全民族的知識產權意識?！叭胧馈焙?西方發(fā)達國家可能會以中國沒有認真完全地執(zhí)行TRIPS協議為由,發(fā)起世貿組織爭端解決程序,甚至以訴諸貿易制裁相威協。對此,應予以高度重視。(江蘇省鹽城市外經貿委金寧)王昕巖等:采用遺傳算法進行車間平面布置