張夢　陳仕軍　李嘉賓　劉朝陽

摘 要： 模擬退火算法是求解一維下料問題的有效方法之一。但傳統(tǒng)模擬退火算法具有易于陷入局部最優(yōu)解的缺點，其性能好壞除了與一些參數(shù)設(shè)置有關(guān)外，特別依賴于鄰域結(jié)構(gòu)設(shè)計和編碼機(jī)制的效率。為設(shè)計高效的求解一維下料問題的模擬退火算法，提出了新的基于一維下料問題特征的變異算子和解碼策略。通過實驗計算，與文獻(xiàn)中的3組案例進(jìn)行比較，結(jié)果優(yōu)于部分既有文獻(xiàn)的結(jié)果，驗證了所提算法的有效性。

關(guān)鍵詞： 一維下料； 模擬退火； 解碼； 改進(jìn)策略

中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2017）12-01-04

Research on one-dimensional cutting stock problem based on

simulated annealing algorithm

Zhang Meng， Chen Shijun， Li Jiabin， Liu Zhaoyang

（School of Mathematics & Computer Science， Hubei University of Arts and Science， Hubei， Xiangyang 441053， China）

Abstract： Simulated annealing is one of the most efficient algorithms to solve one-dimensional cutting stock problem. However， traditional simulated annealing algorithms have the weakness of obtaining local optimal solutions. In addition to some parameters， its performance relies on neighborhood structure and decoding strategy. Based on the problem-knowledge， the new mutation operator and decoding strategy are presented to improve simulated annealing algorithm. By computational experiments with three instances， some better results comparing to those of in literatures are obtained， and the efficiency of presented algorithm is verified.

Key words： one-dimensional cutting stock； simulated annealing； decoding； improvement strategy

0 引言

在實際生產(chǎn)生活中，經(jīng)常會遇到一維下料問題[1]，即將單一規(guī)格或者多種規(guī)格、數(shù)量若干的線性原材料，切割成滿足多種需求規(guī)格和數(shù)量的零件（即坯料）。一維下料問題的目標(biāo)就是，要找到最優(yōu)的可行下料方案，使得廢料盡可能少，以提高原材料的利用率，對建設(shè)資源節(jié)約型社會具有重要實際意義。

一維下料優(yōu)化問題是組合優(yōu)化領(lǐng)域著名的NP-hard問題，目前還不存在求最優(yōu)解的多項式時間算法。因此目前大多數(shù)的方法都基于啟發(fā)式或元啟發(fā)式算法，例如貪婪算法、模擬退火算法[2-3]、遺傳算法[4-6]、粒子群算法[7]、蟻群算法[8]等。這些算法雖然都取得了一定效果，但對于大規(guī)模的下料問題，仍然有很大的優(yōu)化空間。其中，模擬退火算法具有算法通俗易懂、易于實現(xiàn)的優(yōu)點。同時，模擬退火算法的性能除了依賴于初始解、退火溫度、局部搜索次數(shù)、劣解接受概率等因素外，特別依賴于編碼與解碼效率。在應(yīng)用模擬退火算法求解問題時，現(xiàn)有文獻(xiàn)對模擬退火算法的結(jié)構(gòu)和參數(shù)研究較多，而關(guān)于編碼和解碼的影響因素易于被忽略。

為此，本論文基于一維下料的問題特征，擬設(shè)計一種改進(jìn)的模擬退火算法，一方面提高解碼效率，即盡可能地在不影響解碼時間復(fù)雜度的前提下，生成具有更高質(zhì)量的解；另一方面，加強(qiáng)模擬退火算法的局部搜索能力，設(shè)計新的變異算子，使得算法生成的解群體具有更好的多樣性。

1 一維下料的數(shù)學(xué)模型

一維下料問題可以描述如下：設(shè)有足夠多的某種線型原材料數(shù)量為n，單個原材料的長度為L，現(xiàn)需要從原材料上切割出m種小坯料，小坯料的長度和數(shù)量分別為和di（i=1，2，…，m），目標(biāo)是尋找可行的下料方案，并且使得原材料的利用率最大（或使用原材料的根數(shù)最少）。記xji表示第j根原材料上切割第i個坯料的數(shù)量，yj表示是否使用第j根原材料即：，則一維下料問題的數(shù)學(xué)模型為：

由于模型⑴是非線性整數(shù)規(guī)劃模型，利用傳統(tǒng)的優(yōu)化軟件（如lingo）難于求解大規(guī)模問題；而利用智能優(yōu)化方法，非線性約束使得編碼和解碼難以有效設(shè)計。因此，考慮將該模型轉(zhuǎn)化成一種易于編碼和解碼的線性規(guī)劃模型。應(yīng)注意到，雖然原材料很多，但每種原材料的長度相同，故只需要考慮每種原材料的下料方式。若已知原材料的所有下料方式，則模型可以寫成更易于求解的線性規(guī)劃模型。記下料模式數(shù)為p，aij表示第j種下料模式下切割的第i種坯料的次數(shù)，zj表示使用第j種下料模式的使用次數(shù)。則一維下料的數(shù)學(xué)模型為：

由于模型⑵中的下料模式必須可行，因此aij必須滿足：

上述模型⑵的目標(biāo)函數(shù)是最小化所使用的原材料根數(shù)。為了考慮后續(xù)切割的方便，有時在考慮最小化總切割根數(shù)的條件下最大化最后一根原材料的余料長度。此時，目標(biāo)函數(shù)為：endprint

其中，為最后一根被切割原材料的余料長度。

為求解模型⑵，需要給出所有的下料模式。由于下料模式數(shù)量是所有坯料的整系數(shù)線性組合數(shù)，對于大規(guī)模問題，精確列出所有下料模式是及其困難的。為了求解該模型，利用模擬退火算法在只考慮部分合理高效的下料模式子集下，可以得到原問題的滿意（或最優(yōu)）解。

2 模擬退火算求解一維下料問題

2.1 傳統(tǒng)的模擬退火算法求解

⑴ 模擬退火算法流程

模擬退火算法[2]是一種常用于求解NP難組合優(yōu)化問題的智能算法，來源于模擬固體退火原理的過程。溫度升高，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大；隨著溫度逐漸降低分子逐步趨于穩(wěn)態(tài)，內(nèi)能減為最小。模擬退火算法的主要特點在于搜尋解的過程中，它采用Boltzmann接受準(zhǔn)則接收新解，能以一定概率接受比當(dāng)前最優(yōu)解劣的解，克服了爬山算法只接受好解而陷入局部最優(yōu)解的缺點。而且，模擬退火算法具有易于實現(xiàn)的優(yōu)點，其基本算法框架如圖1。

圖1 求解一維下料的模擬退火算法

上述算法流程圖1中，Δf=f（β'）-f（β）用于計算新解β'和當(dāng)前解β之間目標(biāo)函數(shù)的差值，從而判斷是否接受用新解β'取代原解β。記當(dāng)前的退火溫度為T，則接受新解β'的概率：

⑸

上述模擬退火算法具有如下特點：當(dāng)新解與當(dāng)前參照解的目標(biāo)值差Δf一定時，在模擬退火算法前期，退火溫度T較高，接受概率P相對比較大，容易接受比當(dāng)前解差很多的解，使得搜索算法加強(qiáng)全局搜索能力；在模擬退火算法后期，退火溫度T逐步降低，算法傾向于在當(dāng)前已得到較好解的鄰域內(nèi)做細(xì)搜索，漸漸使得算法收斂到滿意解（或最優(yōu)解）。模擬退火算法的終止條件為：當(dāng)內(nèi)循環(huán)次數(shù)達(dá)到上限或者概率選擇次數(shù)達(dá)到上限時結(jié)束內(nèi)循環(huán)；當(dāng)達(dá)到凝固溫度或達(dá)到外循環(huán)次數(shù)上限時，模擬退火算法結(jié)束。

⑵ 一維下料問題的編碼與解碼

利用智能算法求解最優(yōu)化問題時，需設(shè)計合理的編碼與解碼方法。對任意給定的編碼序，通過解碼得到原問題的可行解，從而對相應(yīng)編碼序進(jìn)行評價。智能算法求解的目標(biāo)在于不斷搜索最優(yōu)的編碼序，即對應(yīng)原問題的最優(yōu)解。

針對一維下料問題，常用編碼與解碼方法[4]如下：以坯料類型序號的自然排列作為編碼，解碼時基于坯料類型序號排列，從原材料上依次進(jìn)行切割小坯料，當(dāng)某根原材料被切完或不夠切下一個坯料（原材料的余料長小于當(dāng)前要切割的坯料）時，在新的原材料上繼續(xù)切割，如此循環(huán)，直到所有那些小坯料切割完畢。例如，對于序號排列為{2，3，1，5，4}的5種坯料，切割坯料時，先切割2，接著依次切割3、1、5，最后切割4。為了得到新解，常采用基于“隨機(jī)兩點交換”的鄰域結(jié)構(gòu)。例如，交換兩個坯料序號3、5的位置，即可得到新解{2，5，1，3，4}。以坯料類型序號的自然排列作為編碼時，n種坯料的排列數(shù)為n！，因此難以枚舉所有排列組合，需要利用模擬退火算法來優(yōu)化編碼序。

2.2 改進(jìn)的局部搜索與啟發(fā)式解碼策略

利用2.1節(jié)的模擬退火算法求解一維下料問題時，鄰域結(jié)構(gòu)和解碼策略對算法效率有著重要影響。鄰域結(jié)構(gòu)設(shè)計，能夠使當(dāng)前解在鄰域算子作用下形成新的可行解。當(dāng)需要切割的某類型坯料需求數(shù)較多時，常用的基于“隨機(jī)兩點交叉”的鄰域結(jié)構(gòu)，有很大概率出現(xiàn)無效操作的情況，即當(dāng)前解在鄰域操作算子之后仍然不變。因此，該方法具有較大的局限性。其次，在智能算法中，解碼的目的是將編碼序轉(zhuǎn)化成原問題的可行解，并進(jìn)行解評價，從而比較解的優(yōu)劣。對給定的編碼序，解碼策略不同，得到相應(yīng)原問題的解質(zhì)量也不同。顯然，高效的解碼方法能得到更高質(zhì)量的原問題解。同時，對于任何新解都需要評價，智能算法需要數(shù)千萬（甚至更多）的次數(shù)來調(diào)用解碼過程。因而，解碼也不能過于復(fù)雜，否則計算復(fù)雜性太高，直接影響整個算法的運行效率。

為了克服上述缺點，采用兩種改進(jìn)方法：①首先，設(shè)計分組跳變的鄰域結(jié)構(gòu)，即對隨機(jī)的編碼序進(jìn)行分組（例如10個一組），每組組內(nèi)隨機(jī)選取兩個元素交換位置，得到新解，克服了常用“隨機(jī)兩點交叉”得到解可能不變的局限性。②其次，基于一維下料問題特征，提出改進(jìn)的解碼方法。在基本不影響算法時間復(fù)雜度的條件下，提高解碼效率生成更高質(zhì)量的問題解。改進(jìn)的解碼方法如下：以坯料類型序號的自然排列作為編碼，即每次基于坯料類型序號排列，從原材料上依次進(jìn)行切割小坯料，當(dāng)某根原材料被切完或不夠切下一個坯料時，進(jìn)行一次回溯比較——即先記錄下當(dāng)前原材料的剩余余料長，同時取消最后一次加入的坯料，從編碼序中該坯料的后續(xù)坯料中逐次進(jìn)行切割，直到當(dāng)前余料無法利用，重新計算對應(yīng)原材料的剩余余料長，即得到回溯后的余料長。若回溯結(jié)果優(yōu)于原結(jié)果（回溯得到余料長小于回溯前的余料長），則利用回溯后的解替換回溯前的解。在新的原材料上繼續(xù)切割，如此循環(huán)，直到所有所需求的小坯料切割完畢。

3 算例分析

利用文獻(xiàn)中的3組算例，測試所提算法的有效性。在實現(xiàn)模擬退火算法時，相關(guān)參數(shù)如初始溫度、溫度衰減率、內(nèi)循環(huán)次數(shù)、外循環(huán)次數(shù)，通過多次試驗方法確定。

案例1 原材料長3m，需切割的零件坯料分別為長2.2m的3件、長1.8m的3件、長1.2m的4件、長0.5m的6件、長0.3m的6件。求最優(yōu)下料方案（不考慮切口損失）。案例1的計算結(jié)果見表1。

通過計算，使用原材料總數(shù)8根，總利用率為97.30%。最后一根的原材料剩余余料為1.8，其余的原材料余料均小于0.3。求得結(jié)果和祝勝蘭[1]所提啟發(fā)式算法的結(jié)果相同，優(yōu)于賈志新等[4]提出的遺傳算法。

案例2 已知40段網(wǎng)線的長度分別為4 m、6 m、10 m、13 m、14 m、19 m、20 m、21 m、22 m、28 m、32 m、33 m、36 m、38 m、38 m、40 m、41 m、42 m、48 m、48 m、50 m、55 m、57 m、60 m、64 m、66 m、67 m、72 m、76 m、77 m、83 m、84 m、85 m、86 m、91 m、91 m、94 m、94 m、99 m、100 m，求所需每箱長度為305m的網(wǎng)線箱數(shù)及分割方案。案例2的計算結(jié)果見表2。

通過計算，所需原材料總數(shù)為7，與王曉偉等提出的蜂群遺傳算法[6]的結(jié)果相同。最后一根余料長為10，略差于其結(jié)果，但總利用率為99.01%，也基本達(dá)到了最優(yōu)解。

案例3 已知原材料長度 L=1000m，需切割的零件坯料分別為長512m的5件、長321m的12件、長128m的8件、長247m的22件、長290m的6件。案例3的計算結(jié)果見表3。

通過計算，得到所需要的原材料總數(shù)16，優(yōu)于林建良[9]所提AB分類法得到的17根。所需原材料的根數(shù)與祝勝蘭所提的啟發(fā)式算法[1]相同，但本文的原材料利用率為92.38%，略高于祝勝蘭所提啟發(fā)式算法[1]得到的91.3%。

4 結(jié)論

針對一維下料問題，提出一種改進(jìn)模擬退火算法，并基于一維下料問題特征提出改進(jìn)的解碼方法、變異算子等。通過對文獻(xiàn)中的案例進(jìn)行計算，并與既有相關(guān)算法進(jìn)行比較，證實了所提算法的有效性。此外，本文算法主要針對一維下料問題，還無法直接應(yīng)用求解二維下料問題。對于如何將算法進(jìn)行調(diào)整和改進(jìn)應(yīng)用于求解二維甚至更高維的下料問題，還需要進(jìn)一步研究。

參考文獻(xiàn)（References）：

[1] 祝勝蘭，饒運清.一維下料問題的啟發(fā)式方法[J]. 機(jī)械制造與

自動化，2014.43（1）：52-55

[2] 陳華根，吳健生，王家林等.模擬退火算法機(jī)理研究[J].同濟(jì)大

學(xué)學(xué)報（自然科學(xué)版），2004.32（6）：802-805

[3] 鄭曉軍，楊光輝，滕弘飛.多規(guī)格一維下料問題基于滿意度模

擬退火算法[J].大連理工大學(xué)學(xué)報，2009.49（6）：865-871

[4] 賈志新，殷富強(qiáng)，胡曉兵等.一維下料方案的遺傳算法優(yōu)化[J].

西安交通大學(xué)學(xué)報，2002.36（9）：967-970

[5] 壽周翔，王琦暉，王李冬等.一維下料的改進(jìn)遺傳算法優(yōu)化[J].

計算機(jī)時代，2014.1：36-41

[6] 王曉偉，劉林，周謐.蜂群遺傳算法在一維下料問題中的應(yīng)用[J].

微型機(jī)與應(yīng)用，2012.31（6）：66-71

[7] 張建科，劉三陽，張曉清.改進(jìn)的粒子群算法[J].計算機(jī)工程與

設(shè)計，2007.28（17）：4215-4216

[8] 段海濱，王道波，于秀芬.蟻群算法的研究現(xiàn)狀及其展望[J].中

國工程科學(xué)，2007.9（2）：98-102

[9] 林建良.一維下料問題的AB分類法[J].計算機(jī)應(yīng)用，2009.29（5）：

1461-1466endprint