一維下料的基于貪心策略的多目標(biāo)自適應(yīng) 粒子群算法優(yōu)化

賈璐 楊樂 湯霽月 李友皝

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

關(guān)鍵詞： 一維下料; 粒子群算法; 算法優(yōu)化; 貪心策略; 自適應(yīng)策略; 仿真實(shí)驗(yàn)

中圖分類號： TN911?34; TP391.9? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： 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? 引? 言

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

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

1? 一維下料問題描述

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

2? 應(yīng)用貪心策略的PSO算法

2.1? GSMAPSO算法概述

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

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

2.2? 貪心策略的選擇

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

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

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

3） [i]自加1，重復(fù)步驟1）;當(dāng)i大于[t]時結(jié)束。

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

2.3? 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是PSO算法評價(jià)粒子當(dāng)前位置的優(yōu)劣根據(jù)，粒子根據(jù)自身適應(yīng)度來進(jìn)行一部分范圍的隨機(jī)搜索。由于優(yōu)化目標(biāo)為當(dāng)前下料方式的最優(yōu)解，因此選擇以下適應(yīng)度函數(shù)：

[Rp=L-UpL]? （1）

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

2.4? 自適應(yīng)策略

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

1） 取[h=0]。

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

3） 若[B′]等于[B]，[h=h+1]。當(dāng)[h≥M]時，適應(yīng)度[Rkp]小于[R′avg]的粒子，即過早收斂的粒子，動態(tài)減小其下一代的慣性權(quán)重，進(jìn)一步增強(qiáng)其局部尋優(yōu)能力，公式如下：

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

其余粒子動態(tài)增加其下一次迭代的慣性權(quán)重，增強(qiáng)其全局尋優(yōu)能力，以跳出局部最優(yōu)解，公式如下：

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

2.5? 下料方式的優(yōu)化

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

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

2.6? 算法步驟

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

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

step3：利用貪心策略優(yōu)化并得到每個粒子的適應(yīng)值。

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

[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的最優(yōu)位置[Bp]矢量的第[i]維分量;[c1，c2]為加速常數(shù);[r1，r2]為隨機(jī)函數(shù)，取值范圍在[0，1]。

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

3? 仿真實(shí)驗(yàn)對比與分析

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

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

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

4? 結(jié)? 語

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

參考文獻(xiàn)

[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的鋼筋下料優(yōu)化算法[J].建筑施工，2018，40（2）：292?294.

[9] 魯強(qiáng)，周新.基于在線檢測動態(tài)一維下料問題的GPU并行蟻群算法[J].儀器儀表學(xué)報(bào)，2015，36（8）：1774?1782.

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

[11] 劉在良，翁旭輝，王靜，等.基于遺傳算法的多規(guī)格管材或型材的優(yōu)化下料[J].計(jì)算機(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] 苗振華，孫旭東，邵誠.一種并行變異自適應(yīng)遺傳算法及其性能分析[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] 王耀雷，周步祥.基于自適應(yīng)粒子群算法的直流微網(wǎng)能量優(yōu)化管理[J].現(xiàn)代電力，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ī)放置算法[J].電信科學(xué)，2017（10）：96?104.

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

[20] 程浩.復(fù)雜下料問題的優(yōu)化模型及求解方法研究[D].合肥：合肥工業(yè)大學(xué)，2015.