改進非支配排序進化算法在下料問題中的應用

闞方，劉林，2，方昶，裴軍，鄭明月

KAN Fang1,LIU Lin1，2,FANG Chang1,PEI Jun1,ZHENG Mingyue1

1.合肥工業(yè)大學管理學院，合肥230009

2.合肥工業(yè)大學管理學院過程優(yōu)化與智能決策教育部重點實驗室，合肥230009

1.School of Management,Hefei University of Technology,Hefei 230009,China

2.Key Laboratory of Process Optimization and Intelligent Decision-making,Ministry of Education,School of Management,Hefei University of Technology,Hefei 230009,China

1 引言

一維下料問題是一個在企業(yè)生產過程中普遍存在的問題，有效的下料方法可以使企業(yè)按照最優(yōu)的方式切割，提升企業(yè)的經(jīng)濟效益。近年來，隨著各種新的優(yōu)化算法的提出，對于一維下料問題的研究也越來越深入，例如，文獻[1]將順序啟發(fā)式算法和分支定界法相結合；文獻[2]提出并實現(xiàn)了非定長優(yōu)化和定長優(yōu)化相結合的兩階段優(yōu)化的下料方法；當問題規(guī)模大到一定程度時，一些元啟發(fā)式算法得到了應用，文獻[3]引入變異操作對蟻群算法進行改進；文獻[4]提出了一種多級混合式啟發(fā)算法MHA（Mixed Heuristic Algorithm）；文獻[5]提出的模擬退火算法、文獻[6]提出的一種多目標的改進禁忌搜索算法等都是這方面的研究成果；近兩年的研究還傾向于采用多種方法復合[7-10]。以上的研究成果多是以算法改進為研究目標，而在實際生產中更迫切地需要考慮原料使用與加工及余料回收的整體優(yōu)化問題，本文以馬鋼車輪公司的優(yōu)化下料決策系統(tǒng)的研究為背景，以減少廢料、減少下料設置時間和減少可回收余料為優(yōu)化目標，通過一種改進的快速非支配排序進化算法和多屬性決策方法構建適用于多目標優(yōu)化下料問題的算法并將其應用于實際中的生產優(yōu)化。

2 下料模型

馬鋼車輪公司車輪、輪箍生產過程的第一道工序是將原材料切割成料坯，再進行加熱、軋制成型和機械加工。為了提高原材料的利用率，切割必須按一定的優(yōu)化方案進行。本文假定原料等長、數(shù)量充足，且不同下料方式間的切換時間是相等的，確定了以下三個優(yōu)化目標并建立數(shù)學模型：

xij≥0，且為整數(shù)，?i，j；βi≥0，且為整數(shù)，?i；T≥0；Li≥0。

參數(shù)定義：N表示待切坯料的種數(shù)；M表示下料方案中包含的下料方式數(shù)；L表示原料的長度；lj表示第j種坯料的長度；j=1，2，…，N；Lmin表示可收回再利用的余料的最小長度；Li表示在第i個下料方式下配切一根原料所產生的余料長度；i=1，2，…，M；λi表示按第i個下料方式產生的余料是否可再利用（如果Li≥Lmin，則λi=1；否則λi=0）；βi表示按第i個下料方式重復下料的次數(shù)；qj表示第j種坯料的需要量；xij表示第i個下料方式中配切第j種坯料的數(shù)目；T表示下料方式間切換的單位時間。

式（1）為目標函數(shù)，3個目標分別是：（1）不可再利用的余料（浪費）最少；（2）下料切割時，下料方式的設置時間（加工成本）最少（原因是不同下料方式之間切換時，需要對刀具等重新進行設置）；（3）可回收再利用的余料最少（原因是回收需要增加運輸和庫存費用）；式（2）為原料長度約束；式（3）為坯料的需求約束。

3 一維下料決策過程

3.1 算法

3.1.1 編碼方法

用pi=(ai1，ai2，…，aij，…，aiN)表示第i種下料方式，其中aij表示在第i種下料方式中切第j種坯料的數(shù)目。例如有待切坯料6種，下料方式（2，1，0，3，2，1）就表示在原料上切2個1號坯料，1個2號坯料，0個3號坯料，3個4號坯料，2個5號坯料和1個6號坯料。

再用βi表示需要用第i種下料方式的重復使用次數(shù)（即所用原料的根數(shù)），則下料方案S就可表示為：S={p1*β1，p2*β2，…，pi*βi，…}。

3.1.2 初始種群

因為刀縫寬度是事先確定的，本文設計下料時將刀縫寬度加在坯料長度上，以簡化計算。按照下面方法生成下料方式，直到坯料的需求都被滿足，即形成一個下料方案。具體步驟如下：

步驟1初始化：將待切割的坯料放入集合π1中；

步驟2取一根原料L，從π1中隨機選擇一種坯料，在滿足L夠用和不超過該種坯料需求量的前提下隨機生成一個整數(shù)xj作為在該下料方式中該個坯料將要配切的數(shù)目。更新原料的剩余長度L′，從π1中再次隨機選擇長度小于L′的坯料進行配切，重復上述步驟直至L′不可再用，判斷L′不可用后需要考慮一種特殊情況，即L′和π1中減去刀縫寬度的某種坯料lx長度一致，則配切一個lx（因為此時所剩的余料正好被利用，不再產生刀縫寬度）。即得到第一個下料方式p1，將p1重復下料β1次，（K為此下料方式中所配切的坯料種數(shù)，qj為此下料方式中第j種坯料此時的剩余需求量，xj為此下料方式中配切第j種坯料的個數(shù)，為下取整函數(shù)），更新π1中還有需求量的坯料，將qj≤?j的坯料從π1中取出，放入集合π3中，?j=[L/lj]，j=1，2，…，N。其中[]為取整函數(shù)，該式表示每種坯料最多可在一根原料上切割的數(shù)目，當坯料的需求量小于或等于其對應的?值時，該種坯料就有可能在一根原料上切割以達到需求量，這會大大增加下料方式數(shù)。

步驟3取原料L，將π1中的坯料放入集合π2中，取出長度最大的坯料lmax進行配切（因為最長的坯料較難與其他坯料進行組合配切，故優(yōu)先考慮），配切的數(shù)量記為xmax，在滿足xmax小于或等于該坯料的需求量的前提下，使xmaxlmax≤L＜(xmax+1)lmax。更新π1中還有需求量的坯料，將qj≤?j的坯料從π1中取出，放入集合π3中，判斷π1是否為空，如果為空，轉步驟5，如果不為空，繼續(xù)下一步。

步驟4更新原料的剩余長度L′，（1）若L′小于π2中最小長度的坯料，結束配切（判斷時仍需考慮步驟2提到的特殊情況），即生成下料方式pi，將pi重復下料。（2）若L′大于π2中最小長度的坯料，把π2中的坯料按需求量進行降序排序（如果需求量一樣，則按坯料的長度降序排列），其對應的坯料長度分別為lm，lm-1，…，l1。從lm開始和已配切的坯料進行組合配切（因為需求量較大的坯料優(yōu)先配切可以有效減少下料方式數(shù)，需求量一樣時較長的坯料較難與其他坯料進行組合配切，故優(yōu)先考慮），在滿足xm小于或等于該坯料的需求量的前提下，使xmlm≤L′＜xm+1lm，其中xm≥0。更新π1中還有需求量的坯料，將qj≤?j的坯料從π1中取出，放入集合π3中，將配切過的坯料從π2中除去，如果π1、π2都不為空，返回步驟4；如果π2為空且π1不為空，輸出下料方式pi=xmaxlmax+xmlm+xm-1lm-1…，將pi重復下料βi次，2，…，K)，返回步驟3；如果π1為空，轉步驟5。

步驟5將π3中的坯料按上述算法配切生成下料方式，直至π3為空。輸出下料方案，結束算法。

初始種群算法如圖1所示。

圖1 初始種群生成方法

3.1.3 快速非支配排序和擁擠度計算

采用文獻[11]的方法對種群進行快速非支配排序并計算個體的擁擠度，這時種群中的每個個體i都得到非支配排序等級和擁擠度這兩個屬性。如果兩個個體的非支配排序等級不同時，優(yōu)先選擇等級低的個體；如果兩個個體的非支配排序等級相同，優(yōu)先選擇擁擠度較低的個體。用選出的個體構造新群體。

3.1.4 進化算子

步驟1對于生成的每個下料方案，將其中的下料方式按值由大到小排列，比例相等的按余料長度由小到大排列（式中Δ為一個較小的正數(shù)，目的是為了防止分母為0）。

步驟2對于按步驟1排序完成的一個下料方案，隨機生成一個基因位。保持該基因位及其前面的基因不變，把該基因位后面的基因刪除，將刪除的基因數(shù)據(jù)還原成待配切的坯料數(shù)據(jù)。

步驟3對還原成待配切的坯料，運行上述的算法，重新生成新的下料方式，將相同的下料方式合并。

3.1.5 精英策略

為避免進化過程中優(yōu)良個體的丟失，提高優(yōu)化結果的精度，將父代種群與所產生的子代種群合并，共同競爭產生新一代種群。

3.1.6 算法整體流程

步驟1初始化，生成規(guī)模為Npop的初始種群P。

步驟2執(zhí)行進化算子，產生規(guī)模為Npop的子代種群Q。

步驟3將P與Q合并，計算合并后的種群中個體的多目標適應值。

步驟4對合并后的種群進行快速非支配排序，確定Pareto解集的層次{F1，F(xiàn)2，F(xiàn)3，…}。

步驟5計算個體的擁擠度。

步驟6執(zhí)行擁擠選擇操作，產生規(guī)模為Npop的新父代種群P。

步驟7判斷終止條件是否滿足（是否達到迭代次數(shù)），如果滿足，結束算法，輸出Pareto最優(yōu)解集，否則返回步驟2。

3.2 基于理想點法的多目標下料決策

通過以上算法得到一個Pareto解集，決策者還面臨如何從這個解集的多個解中選出滿意方案的問題。在這里將解集當作備選方案集F={f1，f2，…，fm}，為了消除各指標間的不可公度性以及統(tǒng)一各指標的趨勢，在進行評價前對其進行規(guī)范化處理；將優(yōu)化目標集作為評價屬性集Z={z1，z2，z3}，運用CRITIC法[12]計算客觀權重；最后用逼近理想解法選出一個滿意解作為下料方案。

4 算例

本文用提出的算法對隨機產生的實例進行了實驗測試，算法使用Delphi 7語言編程，在英特爾奔騰2.4 GHz處理器上運行。下料所使用的原料鋼錠長度L=2 000 mm，可再利用余料的最小長度設為當前下料規(guī)模中坯料長度最小值，下料方式間的切換時間為20 min，進化算法的種群規(guī)模取2N，進化代數(shù)為100，各坯料的長度和需求量如表1所示。本文實驗設計分別對不同坯料規(guī)模的下料問題進行運算，10種下料規(guī)模為a1～a10，20種下料規(guī)模為a1～a20，以此類推，算法運行結果如表2所示。

表1 坯料重量與需求量

表2 算法運行結果

圖2顯示了下料規(guī)模為30時，Parteo最優(yōu)解對應的個體數(shù)在群體中所占比例在迭代過程中的變化情況。本文設定的迭代次數(shù)為100，由圖可知實際運行到40代左右時，Parteo最優(yōu)解對應的個體數(shù)已基本保持不變，收斂速度較快，運行到100代時，Parteo最優(yōu)解的個數(shù)為17。

圖2 Pareto解集中解的個數(shù)所占比例

表3顯示了下料規(guī)模為30時，運行該算法求出的Parteo最優(yōu)解集，其中的11號下料方案為運用多屬性決策方法選出的最終下料方案；圖3顯示了未運行算法前的初始種群的解空間分布；圖4顯示了初始種群經(jīng)過100次迭代后，Pareto最優(yōu)解集的分布（即表3中的17個下料方案的分布），通過比較可以發(fā)現(xiàn)，該算法具有良好的優(yōu)化效果。f1表示廢料（值均經(jīng)過歸一化處理）；f2表示下料設置時間（值均經(jīng)過歸一化處理）；f3表示返回余料根數(shù)（值均經(jīng)過歸一化處理）。

表3 Pareto最優(yōu)解集

5 結束語

（1）本文研究的是多目標一維下料問題，建立了減少廢料、減少下料設置時間和減少可回收余料三個目標的優(yōu)化下料模型，針對該問題的特點，設計了一種多目標啟發(fā)式進化算法來求Pareto解集，再采用多屬性決策方法對Pareto解集中的解進行評估排序，以獲取滿意的下料決策方案。

圖3 初始種群的解空間分布情況

圖4 迭代100次后Pareto最優(yōu)解集的分布情況

（2）實驗結果表明，本文算法對中等規(guī)模的下料問題是可行有效的，在種群規(guī)模合適的情況下，其迭代次數(shù)和所用時間是較優(yōu)的，且保證了較高的原料利用率，運用多目標優(yōu)化和多屬性決策相結合的方法可以有效地解決多目標下料的決策問題。

（3）此方法現(xiàn)已被應用于馬鋼車輪公司的下料決策系統(tǒng)，與公司原來使用的下料系統(tǒng)相比，不僅可以提高鋼材的利用率，縮減編制下料方案的工作時間，而且還大大簡化了下料決策過程和復雜程度。但隨著下料規(guī)模的持續(xù)擴大，如何提高該算法的優(yōu)化質量和運行時間，是需要進一步研究的課題。

[1] Gradisar M，Trkman P.A combined approach to the solution to the general one-dimensional cutting stock problem[J].ComputersandOperationsResearch，2005，32：1793-1807.

[2] 閻春平，宋天峰，劉飛.面向可制造性的兩階段一維下料優(yōu)化下料方法[J].計算機輔助設計與圖形學學報，2009，21（12）：1785-1790.

[3] Lu Qiang，Wang Zhiguang，Chen Ming.An ant colony optimization algorithm for the one-dimensional cutting stock problem with multiple stock lengths[C]//Fourth International Conference on Natural Computation，ICNC’08，2008：475-479.

[4] Huo Yingyu，He Kejing，Zhang Rengui，et al.MHA：a mixed heuristic algorithm for the cutting stock problem[C]//International Conference on Information and Automation，ICIA’09，2009：460-465.

[5] Chen Chuen-Lung，Hart S M，Tham W M.A simulated annealing heuristic for the one dimensional cutting stock problem[J].European Journal of Operation Research，1995，32：522-535.

[6] Yang C T，Sung T C，Weng W C.An improved tabu search approach with mixed objective function for one-dimensional cutting stock problems[J].Advances in Engineering Software，2006，37：502-513.

[7] Gradisar M，Resinovic G，Kljajic M.A hybrid approach for optimization of one-dimensional cutting[J].European Journal of Operational Research，1999，119（3）：719-728.

[8] Vasko F J，Newhart D D，Kenneth L，et al.A hierarchical approach for one-dimensional cutting stock problems in the steelindustry that maximizes yield and minimizes overgrading[J].European Journal of Operational Research，1999，114（1）：72-82.

[9] Paolo T.Optimization engineering techniques for exact solution of NP-hard combinatorial optimization problems[J].European Journal of Operational Research，2000，125（2）：222-238.

[10] 包奇金寶，姜靜清，宋初一，等.基于粒子群與模擬退火算法的板材優(yōu)化下料[J].計算機工程與應用，2008，44（26）：246-248.

[11] Deb K，Pratap A，Agrawal S，et al.A fast and elitist multi objective genetic algorithm：NSGA II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

[12] Diakoulaki D，Mavrotas G，Papayannakis L.Determining objective weights in multiple criteria problem：the CRITIC method[J].Computers and Operations Research，1995，22：763-770.