黃秀玲，李 宸，董 浩

（南京林業(yè)大學 機械電子工程學院，南京 210037）

0 引言

目前鋁合金是應用較為普遍的一類合金。鋁合金型材具有低密度、高強度且可塑性強的特點，并且其導熱性、導電性和抗腐蝕性都很優(yōu)秀，所以廣泛應用于工業(yè)，僅次于鋼[1]。鋁合金型材的切割問題屬于一維下料問題。關于下料問題，它主要指是利用規(guī)格相同或不同的原材料，將其切割成大小不同的零件[2]，這是制造業(yè)典型的加工方式之一。在下料的過程中，對相關工序進行優(yōu)化能夠帶來很多好處[3]。

“一維下料問題（One-dimensional Cutting-stock Problem，簡稱 1CSP）”[4]可以簡單描述為：有不同規(guī)格的原材料，生產目標是將這些不同規(guī)格的原材料加工為所需求的不同規(guī)格的零件，在保證零件形狀和尺寸滿足要求的情況下，對原材料進行充分利用，最大限度地減少材料損失。對于本文的研究而言，就是建立在以下料問題求解最優(yōu)的基礎上展開分析。本文針對這一問題結合某門窗公司的實例對鋁合金型材的切割方法進行研究，從而得出提高利用率的有效方法。

一維下料問題也是一種典型的NP（非確定多項式）問題，問題中還有原材料數(shù)量和種類限制，使得這類問題求解起來較為復雜，目前還不存在一個精確的方法用于解決這類問題。求解小規(guī)模下料問題，通常用線性規(guī)劃、動態(tài)規(guī)劃、分支界定法求得全局最優(yōu)解[5]，而對于大規(guī)模的下料問題，通常使用一些啟發(fā)式算法或者智能算法求得近似最優(yōu)解。在對一維下料問題進行求解時，有很多種常見的求解問題方法。其中有數(shù)學模型，比如：常規(guī)線性整數(shù)規(guī)劃模型和基于切割損失的模型；還有算法求解，比如：順序啟發(fā)式算法、遺傳算法等等[6]。

1 數(shù)學模型的建立

在對鋁合金型材進行切割時，由于型材的長度主要取決于工廠的標準，所以有不同長度的原材料，長度用Lk（k=1，2，…，K）表示。每種數(shù)量表示為Dk（k=1，2，…，K）。這里的零件指切割后未加工的型材，在鋁合金門窗下料中即為窗框，由于有不同長度的需求，長度用li（i=1，2，…，n）表示，需要數(shù)量表示為為di（i=1，2，…，n）。對于切割完成后的剩余原材料，按照計算，已經滿足切割需求，無需繼續(xù)下料，稱之為余料。余料中尺寸如若有可以用于下次繼續(xù)下料的，可以回收使用，其他的則為廢料。

對于一維下料問題通常以所用原材料數(shù)量最少，即消耗原材料總長度最少或者余料最少為目標函數(shù)。對于鋁合金門窗下料的問題，結合某門窗廠實際情況，本文采用以消耗原材料總長度最少作為目標函數(shù)。

假設零件按順序編號，零件需求的總數(shù)為d。鋁合金原材料按長度順序排列，D個鋁合金型材原材料可以滿足d個零件的切割需求。滿足min{lk}>max{li}，k=（1，2，…，K），i=（1，2，…，n）。求解怎樣下料使得用到的原材料最少，使用原材料最少的目標函數(shù)表示如下：

其中：

k表示為原材料的種類；

j表示為切割方式；

Xjk表示第k種原材料采用第j種切割方案的重復次數(shù)，Xjk≥0，且為整數(shù)。

對于鋁合金型材而言，其原來的長度必須大于切割長度，除此之外，切割重復次數(shù)也必須少于原材料數(shù)目，并且在切割完成時，所得到的零件數(shù)量需滿足客戶需求的零件數(shù)量。約束條件表示如下：

其中：

式(2)表示原材料的切割重復次數(shù)小于等于原材料的數(shù)量。

式(3)表示產生的總零件數(shù)量等于客戶需求數(shù)量。

式(4)表示單根原材料上切割長度不超過其本身長度。

2 算法求解

2.1 改進的蟻群算法

蟻群算法應用于尋優(yōu)問題的基本思路簡單描述為[7]：在求解相關問題最優(yōu)時，將整個問題視為螞蟻覓食路徑，所以問題的解空間就對應螞蟻走過的路徑。蟻群算法在解決單目標函數(shù)優(yōu)化問題時效果較好，但是解決多目標函數(shù)優(yōu)化較困難[8]。因為本文是解決多規(guī)格下料的問題，所以利用啟發(fā)式算法思想將多目標轉換為單目標進行求解。每只螞蟻基于信息素的概率來進行路徑的選擇。針對一維下料優(yōu)化的相關問題，對其進行合理的編碼，同時認為所有零件都有獨立性，將所有下料方案模擬成螞蟻行走所有的路徑。

在具體處理時首先是從第一個零件開始，在零件消耗總長度和原材料長度十分接近但是不超過原材料長度的情況下，此時可以得到其中的一個下料方案，基于此，可以進一步計算出更多的下料方案，按照這樣的方式繼續(xù)進行計算可以得到這一路徑上全部的零件，從而獲得該路徑消耗的原材料總長度、余料長度以及下料方案的數(shù)目。

step1：輸入原材料和零件的信息，并對其升序排列。

step2：初始化參數(shù)。令迭代次數(shù)Nc=0，設最大迭代次數(shù)為Nmax=200，賦予參數(shù)α，β，ρ初始值，設α=1，β=1，ρ=0.2。

step3：將D個零件從1到D進行編碼，相同的零件由于編碼也記為不同的零件。

step4：計算候選節(jié)點集合。

step5：開始進入循環(huán)Nc=Nc+1。若滿足Nc≥Nmax，則結束循環(huán)。

step6：停止計算，輸出下料方案及余料。

流程圖如圖1所示。

圖1 蟻群算法解一維下料問題流程圖

2.2 遺傳混合模擬退火算法

遺傳混合模擬退火算法在遺傳算法中引入一種代溝策略，根據(jù)適應度的值設置一個代溝值，大于這個值的保留為精英個體，不進入輪盤賭選擇，將模擬退火算法使用到其余個體之中，應用Metropolis準則來判斷是否被接受為新的種群，進而使得遺傳算法尋優(yōu)效果更好，避免了早熟問題的發(fā)生。

step1：對適應度函數(shù)進行合理設置，這里使用原材料利用率來表示：

step2：將不同零件進行合理編碼，同時將原材料編號，編為類似地，將全部零件編號為中，隨機選擇個數(shù)字，構成不同個體的染色體編碼。比如，（1，4，5，…，2）表示的是零件號為1需要通過1號原材料來切割，……，第di號零件需要從2號原材料上切割。

step3：對種群進行初始化處理，得到隨機的N個個體，設N=100。

step4：計算個體適應度。

step5：根據(jù)適應度函數(shù)設置一個代溝值，因為適應度函數(shù)為材料的利用率，故本文將這個值設置為0.9，大于這個適應度值的個體不進入輪盤賭選擇，直接保留為精英個體參與接下來的流程，其他的個體進行輪盤賭選擇后運用模擬退火算法中的Metropolis準則，通過公式exp（-（fit（i）-fit（best）/T）計算接受概率來判斷接受或拒絕。

step6：合理設置基本參數(shù)。對于交叉算子而言，使用雙點交叉的方式，在染色體上隨機選擇兩個點，兩點間不變，對兩端基因片段進行交叉。設置交叉率為0.8，變異算子變異率是0.1；迭代次數(shù)為1000次。模擬退火設置初始溫度T=1000；退火系數(shù)設置為0.9。

step7：不斷進行迭代，滿足結束條件結束迭代并且將最優(yōu)解輸出，若不滿足條件返回step4。

流程圖如圖2所示。

3 實例計算分析

本文所有計算的例子均在主頻2.50GHz，內存為8GB的計算機上完成，通過MATLAB進行編程并設計下料軟件。根據(jù)在某門窗有限公司采集的數(shù)據(jù)和實例進行分析，再根據(jù)所采集數(shù)據(jù)的規(guī)模，分別給予不同的計算和分析。

實例：倉庫有鋁合金原材料3200mm的30根，3600mm的30根，4000mm的20根。現(xiàn)在需要切割外窗框長為1390mm，寬為790mm，中柱框為735mm，內開窗框長為962mm，寬為736mm，扇壓線長為837mm，270mm。扇壓線寬為611mm，654mm的窗戶15套。

窗戶圖紙如圖3所示。

原材料長度如表1所示，下料尺寸表如表2所示。

圖2 遺傳混合模擬退火算法流程圖

圖3 窗戶圖紙

表1 原材表

表2 下料尺寸表

3.1 蟻群算法

計算結果如表3所示。

表3 蟻群算法切割方案

表3 （續(xù)）

表3 （續(xù)）

經過計算得實例的原材料利用率為91.91%，消耗了30根3200mm鋁合金型材，30根3600mm鋁合金型材，3根4000mm鋁合金型材，總共216000mm。余料為17475mm。對于個別原材料來說還是存在余料較長的結果，可以收集繼續(xù)下料。但是計算時間變長。由結果可以看到蟻群算法在計算較大規(guī)模多規(guī)格下料問題時候尋優(yōu)的效果明顯下降，計算時間變長。

3.2 遺傳混合模擬退火算法

具體切割方案如表4所示。

表4 遺傳混合模擬退火算法切割方案

表4 （續(xù)）

表4 （續(xù)）

經過計算，運用遺傳混合模擬退火算法的原材料利用率為94.17%，相比蟻群算法的利用率91.91%提升了2.26%。消耗了30根3200mm鋁合金型材，23根3600mm鋁合金型材，8根4000mm的鋁合金型材，余料為12275mm，總計210800mm。與蟻群算法消耗材料總長為216000mm進行對比，遺傳混合模擬退火算法節(jié)省材料的同時提高了整體原材料利用率，且余料中沒有出現(xiàn)余料過長的情況，遺傳混合模擬退火算法具有良好的計算效果。

4 結語

本文對于一維下料問題，提出了一種遺傳混合模擬退火算法，使算法尋優(yōu)效果更好，避免了早熟問題的發(fā)生。結合某門窗有限公司的下料實例建立數(shù)學模型，為了使材料利用率得到有效提高，文中利用蟻群算法與遺傳混合模擬退火算法對下料問題進行分析，結果表明，使用基于遺傳混合模擬退火算法來提高材料的利用率具有重要的現(xiàn)實意義。