基于模擬退火算法的一維下料研究

張夢(mèng)　陳仕軍　李嘉賓　劉朝陽(yáng)

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

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

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

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

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

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

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

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

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

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

其中，為最后一根被切割原材料的余料長(zhǎng)度。

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

2 模擬退火算求解一維下料問(wèn)題

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

⑴ 模擬退火算法流程

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

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

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

⑸

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

⑵ 一維下料問(wèn)題的編碼與解碼

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

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

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

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

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

3 算例分析

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

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

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

案例2 已知40段網(wǎng)線(xiàn)的長(zhǎ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，求所需每箱長(zhǎng)度為305m的網(wǎng)線(xiàn)箱數(shù)及分割方案。案例2的計(jì)算結(jié)果見(jiàn)表2。

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

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

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

4 結(jié)論

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

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

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

自動(dòng)化，2014.43（1）：52-55

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1461-1466endprint