一維下料的基于貪心策略的多目標自適應 粒子群算法優化

賈璐 楊樂 湯霽月 李友皝

摘? 要： 針對一維下料問題，提出一種基于貪心策略的多目標自適應粒子群算法，在余料率最低和下料方式數量最少兩個目標上進行優化。通過將貪心策略應用于粒子群算法，把一維下料問題分割成多個子問題，對每個子問題依次求全局最優解，有效縮小單次處理問題的規模，由所有子問題的最優解取得原問題的近似最優解。為解決種群過早收斂而因此陷入局部最優，設計一種自適應策略。此外，考慮到切換下料方式會產生一定成本，通過最大化當前下料方式使用次數優化下料方式數量。仿真實驗結果表明，該算法收斂速度快，取得的下料方案利用率高且下料方式數量較少，具備較好的實用性，并能夠為企業帶來顯著的經濟效益。

關鍵詞： 一維下料; 粒子群算法; 算法優化; 貪心策略; 自適應策略; 仿真實驗

中圖分類號： TN911?34; TP391.9? ? ? ? ? ? ? ? ?文獻標識碼： A? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）14?0086?04

Multi?objective adaptive particle swarm algorithm optimization based on greedy strategy for one?dimension cutting stock problem

JIA Lu1， YANG Le2， TANG Jiyue2， LI Youhuang2

（1. School of Architecture and Engineering， Nanchang University， Nanchang 330031， China;

2. School of Software， Nanchang University， Nanchang 330047， China）

Abstract： The multi?objective adaptive particle swarm algorithm optimization based on greedy strategy is proposed for the one?dimension cutting stock problem， which is optimized in the two aspects of the lowest surplus rate and the minimum number of cutting stock ways. By applying the greedy strategy into the particle swarm algorithm， the one?dimension cutting stock problem is divided into multiple sub?problems， the global optimal solution of each sub?problem are found in turn （which can effectively reduce the scale of single processed problem）， and the approximate optimal solution of the original problem is obtained from the optimal solution of all sub?problems. An adaptive strategy is designed to prevent the population is trapped into local optimum due to the premature convergence. In consideration of the cost of switching cutting stock ways， the quantity of cutting stock way is optimized by maximizing the number of times that the current cutting stock way is used. The simulation experimental results show this algorithm has fast convergence speed， the utilization rate of the obtained cutting stock plan is high， and the used cutting stock ways are fewer. It has a certain practicability and can bring significant economic benefits to enterprises.

Keywords： one?dimension cutting stock; particle swarm algorithm; algorithm optimization; greedy strategy; adaptive strategy; simulation experiment

0? 引? 言

粒子群優化算法（Particle Swarm Optimization，PSO）是由Eberhart和Kennedy于1995年提出的群智能算法[1]。相比傳統優化算法，粒子群算法具備并行、信息共享等特性，能夠更快逼近最優解。因此，目前已普遍應用于函數優化、神經網絡優化[2]、圖像分割[3]以及提高工業生產效率[4]等方面。相比遺傳算法（GA），粒子群算法（PSO）無需進行交叉和變異操作，原理更簡單，無需調整眾多參數，實現更容易。與GA的信息共享機制不同的是，PSO種群在搜索中朝著當前最優解的方向更新。因此大多數情況，種群所有粒子會更早收斂于最優解。貪心算法是解決最優化及近似最優化問題的經典算法[5]，與全局優化算法不同，并非從整體最優考慮，而是只關注當前子問題的最優解，廣泛用于優化路徑選擇[6]和調度問題[7]。本文針對一維下料問題，將貪心策略應用于粒子群算法，加入自適應策略和下料方式優化方法，提出一種基于貪心策略的多目標自適應粒子群算法（GSMAPSO）。仿真實驗結果表明，該算法收斂速度快，求解精度高，且下料方式較少。

由于一維下料問題的普遍存在，大量學者對其進行了研究，并提出各自的優化算法[8]。針對一維下料問題，結合分支定界法的整數線性規劃[9]，理論上可以得到最優解。然而該方法必須首先列出所有的下料方式，再進行線性規劃。在數據規模較大時，有效的下料方式數量巨大，全部遍歷并不現實，因此只適合小規模下料優化問題。文獻[10]提出一種貪心算法優化方法，試圖利用子集和思想尋找一組近似于最佳的下料組合方式。該算法雖然在一定程度上減少了下料方式數，但是問題規模較大時，尋找余料率低的下料方式耗時長，且由于貪心算法在求解局部最優時只是逐步從一個方向逼近理想最優值，不能并行比較，導致求解精度較低。進化算法如遺傳算法也被用于一維下料優化[11]，但遺傳算法需要對問題編碼和解碼，編程實現復雜，不能及時利用種群網絡的反饋信息。因此得出較優的下料方案需要較多訓練時間，且算子的實現依賴于多個參數[12]，參數的選擇較大程度上決定了解的品質。目前對于這些參數的選擇大多憑借經驗，仍未有較為成熟的研究。

1? 一維下料問題描述

某工程施工單位有某種原材料，每根原材料長度為[L]，原材料充足。現需要[t]種長度為[li（i=1，2，…，t）] 的零件，對應數量為[ni]，如何下料使得需要的原材料根數[S]最少，末根（余料最長的一根）余料長度最長。[S]相同時，比較余料長度，余料更長者較優。

2? 應用貪心策略的PSO算法

2.1? GSMAPSO算法概述

一維下料優化問題，目標為得到總體余料最少的下料方案，本文的GSMAPSO算法結合貪心策略，將每種下料方式看成單個子問題，逐步求出各子問題的全局最優解。從而有效地縮小了單次問題處理規模，提升了算法效率。最終，得出整體下料方案的近似最優解。

粒子群算法雖然具有并行搜索、實現簡單等優點，但與遺傳算法等全局優化算法相同，在處理高維復雜問題時，同樣存在早熟收斂、陷入局部最優的缺點，導致求解精度降低。針對該問題，文獻[13]提出了一種種群過早收斂程度的定量評價指標。Shi Y等最早提出了一種線性遞減慣性權值的策略[14]，此方法雖然在一定程度上能夠改善早熟收斂，但線性遞減策略卻不能體現PSO算法的優化搜索過程。目前，研究者大多針對不同優化問題采用對應的自適應策略[15?17]。本文針對應用貪心策略后的粒子群算法特點，設計了一種動態改變慣性權值的自適應策略。

2.2? 貪心策略的選擇

單一下料方式中，下料零件總長不能大于原材料長度，而適應度在一定范圍內具有隨機性，由此可能產生無效粒子。本文在貪心策略中加入首次適應算法[18]，使得適應度從大于0的方向不斷逼近于0，避免了粒子的無效性，使每個粒子取得一個可行解。本文的貪心策略步驟如下：

1） 若[xpili≤L]， [Up=Up+xpili]。

2） 否則，[xpi=L-U÷li]，[Up=Up+xpili]。

3） [i]自加1，重復步驟1）;當i大于[t]時結束。

式中：[Up]為粒子[p]位置矢量對應下料方式的原料使用長度;[xpi]為粒子[p]位置矢量的第[i]維分量。

2.3? 適應度函數

適應度函數是PSO算法評價粒子當前位置的優劣根據，粒子根據自身適應度來進行一部分范圍的隨機搜索。由于優化目標為當前下料方式的最優解，因此選擇以下適應度函數：

[Rp=L-UpL]? （1）

式中：[Rp]指粒子[p]的位置對應下料方式的余料率;[xpi]為粒子[p]的位置的第[i]維分量。顯然，R越接近于0，該下料方式越優。

2.4? 自適應策略

設種群規模為[Q]，最大迭代次數為[G]，則第[k]代種群由粒子[xkp] [p=1，2，…，Q]組成，對應的適應度為[Rkp]，慣性權重為[wkp]，則所有粒子的平均適應度[Ravg=1Qp=1QRkp]。當前最優粒子的適應度為[B′]，全局最優適應度為[B]，將適應度大于[Ravg]的粒子適應度再求和平均得[R′avg]，[M]為允許陷入早熟收斂后的最大迭代次數，[h]為當前陷入早熟收斂的次數。本文粒子的慣性權重初值均為[wmax]。

1） 取[h=0]。

2） 若[B′]小于[B]，重置[h=0]，[B=B′]。當[B=0]，已找到全局最優解，終止迭代，采用其對應的下料方式;否則繼續搜索，直到迭代次數等于最大值[G]。

3） 若[B′]等于[B]，[h=h+1]。當[h≥M]時，適應度[Rkp]小于[R′avg]的粒子，即過早收斂的粒子，動態減小其下一代的慣性權重，進一步增強其局部尋優能力，公式如下：

[wk+1p=wmax-（wmax-wmin）R′avg-RkpR′avg-B] （2）

其余粒子動態增加其下一次迭代的慣性權重，增強其全局尋優能力，以跳出局部最優解，公式如下：

[wk+1p=wmax·Rkp-BRkp]? ? （3）

2.5? 下料方式的優化

考慮到實際工程下料方式的切換將產生一定成本，本文在得到當前下料方式的全局最優解后，通過對比待下料零件的數量，最大化當前下料方式使用次數。在減小下料方式的同時，也進一步縮小了下一次求解的問題規模。[resulti]為全局最優解對應下料方式中第[i]種零件的個數，[fre]為下料方式使用次數，計算公式為：

[fre=minni÷resulti，? i=1，2，…，t] （4）

2.6? 算法步驟

step1：輸入原材料長度[L]和[t]種零件數據[li，ni]。

step2：將種群粒子初始化為隨機粒子，為所有粒子分配起始位置和起始速度。

step3：利用貪心策略優化并得到每個粒子的適應值。

step4：當前種群最佳適應度若小于全局最優適應度，則更新全局最優適應度。同理，各粒子通過當前適應度與歷史最優適應度的比較，來決定是否更新自身歷史最優適應度。然后，更新每個粒子的位置和速度，更新公式為：

[vk+1pi=wk+1p·vkpi+c1·r1·（Bpi-xkpi）+c2·r2·（B-xkpi）]? （5）

[xk+1pi=xkpi+vk+1pi]? ?（6）

式中：[vk+1pi]為種群在[k+1]次迭代后，粒子[p]速度矢量的第[i]維分量;[xk+1pi]指種群在[k+1]次迭代后，粒子[p]位置矢量的第i維分量;[Bpi]為粒子p的最優位置[Bp]矢量的第[i]維分量;[c1，c2]為加速常數;[r1，r2]為隨機函數，取值范圍在[0，1]。

step5：若達到最大迭代次數[G]，則取全局最優解對應的下料方式[result]，并更新待下料零件數[ni=ni-resulti（i=1，2，…，t）]，跳轉至step2，尋找下一種下料方式;否則，跳轉至step3。直到待下料各零件數均為0，求解結束，形成整體下料方案。

3? 仿真實驗對比與分析

本文仿真實驗共2個算例，運行在Windows 10系統、i5?7200U CPU環境下的Matlab R2018a，設定粒子群大小為50，最大迭代次數為300，獨立運行15次，[wmax=0.8]，[wmin=0.4]，所有算例單次運行時間均小于50 s。其中，大部分時間用于前面的下料方式計算，后續下料方式的運算速度將隨著問題規模的縮小進一步加快。表1中，次數均表示該下料方式的使用次數。

算例1：實驗數據來自文獻[11，19]。文獻[11]采用改進的自適應遺傳算法，最佳下料方案共需要原材料24根，總利用率97.41%，下料方式為24種，前23根總余料為2 436，末根余料長度為5 032。文獻[19]采用自適應廣義粒子群優化算法得到的最佳下料方案共需要原材料24根，下料方式24種，前23根總余料長度為764，末根余料長度為6 704。本文采用GSMAPSO算法得出的下料方案共需原材料24根，下料方式20種，前23根總余料長度為88，末根余料長度為7 380，前23根原材料利用率高達99.97%，各項數據均優于上述兩個文獻。

算例2：實驗數據源自文獻[10，20]。文獻[20]通過建立一種多目標的優化模型，提高了利用率并改進了下料方式。在不優化下料方式數量的情況下，得出的下料方案共需原材料809根，下料方式為71種，廢料總長度為32 274;在使用加權求解減小下料方式后，共需原材料811根，下料方式66種，廢料總長度為38 239。本文采用GSMAPSO算法計算后，得出的下料過程原材料余料率變化折線圖如圖1所示。共需原材料795根，下料方式60種，總余料10 012，總利用率達99.58%，各項數據均更優，且十分接近該問題的理論最優解792。文獻[10]利用貪心算法優化，雖然在下料過程中加入了切割損耗，但在計算利用率時并未將切割損耗納入廢料當中。在將切縫損耗計入廢料后，共需原材料807根，下料方式為51種，廢料總長度46 012，總利用率98.1%。本文的GSMAPSO算法，在考慮下料時的切割損耗后，得出的下料過程原材料余料率變化折線圖如圖2所示。共需原材料800根，下料方式為55種，總余料長度25 012，總利用率為98.96%。除下料方式偏多外，其余數據均優于貪心算法。

4? 結? 語

針對一維下料問題，本文提出一種基于貪心策略的多目標自適應粒子群算法。通過仿真實驗對比現有多種優化算法表明，該算法收斂速度快，求解精度高，下料方式切換次數較少，適用于中大規模一維下料。

參考文獻

[1] KENNEDY J， EBERHART R C. Particle swarm optimization [C]// Proceedings of IEEE International Conference on Neural Networks. Perth： IEEE， 1995： 1942?1948.

[2] LIN C H， CHANG K T. SCRIM drive system using adaptive backstepping control and mended recurrent Romanovski polynomials neural network with reformed particle swarm optimization [J]. International journal of adaptive control and signal processing， 2019， 33（5）： 802?828.

[3] SAEED Mirghasemi， PETER Andreae， ZHANG Mengjie. Domain?independent severely noisy image segmentation via adaptive wavelet shrinkage using particle swarm optimization and fuzzy C?means [J]. Expert systems with applications， 2019， 133（6）： 542?558.

[4] ZOU Jing， CHANG Qing， OU Xinyan， et al. Resilient adaptive control based on renewal particle swarm optimization to improve production system energy efficiency [J]. Journal of manufacturing systems， 2019（50）： 650?667.

[5] TSAMARDINOS Ioannis， BORBOUDAKIS Giorgos， KATSOG?RIDAKIS Pavlos， et al. A greedy feature selection algorithm for Big Data of high dimensionality [J]. Machine learning， 2019（2）： 338?347.

[6] SAMUEL Nucamendi?Guillén， FRANCISCO Angel?Bello， IRIS Martínez?Salazar， et al. The cumulative capacitated vehicle routing problem： new formulations and iterated greedy algorithms [J]. Expert systems with applications， 2018， 11（7）： 36?43.

[7] WU Chin?Chia， YANG Tzu?Hsuan， ZHANG Xingong， et al. Using heuristic and iterative greedy algorithms for the total weighted completion time order scheduling with release times [J]. Swarm and evolutionary computation， 2018（6）： 456?468.

[8] 漏家俊.基于MATLAB的鋼筋下料優化算法[J].建筑施工，2018，40（2）：292?294.

[9] 魯強，周新.基于在線檢測動態一維下料問題的GPU并行蟻群算法[J].儀器儀表學報，2015，36（8）：1774?1782.

[10] 壽周翔，王琦暉，王李冬，等.一維下料的改進遺傳算法優化[J].計算機時代，2014（1）：36?37.

[11] 劉在良，翁旭輝，王靜，等.基于遺傳算法的多規格管材或型材的優化下料[J].計算機時代，2018（12）：71?74.

[12] YAN Chun， LI Meixuan， WEI Liu， et al. Improved adaptive genetic algorithm for the vehicle insurance fraud identification model based on a BP neural network [J]. Theoretical computer science， 2019（7）： 783?792.

[13] 苗振華，孫旭東，邵誠.一種并行變異自適應遺傳算法及其性能分析[J].信息與控制，2016，45（2）：142?150.

[14] SHI Y H， EBERHART R. A modified particle swarm optimizer [C]// 1998 IEEE International Conference on Evolutionary Computation Proceedings. Anchorage： IEEE， 1998： 69?73.

[15] 王耀雷，周步祥.基于自適應粒子群算法的直流微網能量優化管理[J].現代電力，2017，34（1）：37?43.

[16] MANIKANDAN Subramaniyan， SASITHARAN Subramaniyan， MOORTHY Veeraswamy， et al. Optimal reconfiguration/distributed generation integration in distribution system using adaptive weighted improved discrete particle swarm optimization [J]. Compel， 2019， 38（1）： 226?249.

[17] ATEFEH N， MOHAMMAD H M. Missing value imputation for breast cancer diagnosis data using tensor factorization improved by enhanced reduced adaptive particle swarm optimization [J]. Journal of King Saud University， 2018（9）： 89?96.

[18] 姜棟瀚，林海濤.基于布谷鳥搜索的虛擬機放置算法[J].電信科學，2017（10）：96?104.

[19] 文笑雨，羅國富，李浩，等.基于廣義粒子群優化模型的工藝規劃方法研究[J].鄭州大學學報（工學版），2018，39（6）：65?69.

[20] 程浩.復雜下料問題的優化模型及求解方法研究[D].合肥：合肥工業大學，2015.