基于混沌粒子群算法的多目標二維切割問題

摘要

多維切割問題是木材加工、機加工和造紙等行業在生產中經常遇見的實際問題。排樣切割完成后，往往都會有一些大小不等、數量不同的剩余材料。本文優化利用這些材料，進一步減少浪費。通過和貪心啟發式^法的比較，證明該混合算法對解決多目標二維切割問題是行之有效的。

【關鍵詞】多目標切割問題 粒子群算法 混沌粒子群算法

二維切割問題在輕 工、排版、玻璃切割等行業的廣泛應用，國內外對矩形件排樣優化的問題己經做了相當深入的研究，實現了提高板材利用率、縮短排樣時間的目的。但在排樣切割完成后，往往都會有一些大小不等，數量不同的剩余材料，如何更好地再次利用這些材料，這就是本文所要討論的內容。

1多目標二維切割問題數學模型

l.1問題描述及建模

本文只考慮剩余的材料是矩形的情況，針對一定數量和大小的零件需求，建立數學模型。由于所剩余的材料大小不等，這類切割問題被定義為多目標的切割問題。

解決復雜的排樣問題的二維優化下料模型一般都是構造成線性規劃的數學模型，以原材料消耗的總面積最小為目標，但是對于我們所要討論的情況，僅僅考慮消耗的總面積最小是不夠的，還要考慮所用原料的種類最少。

設原材料板材，其長、寬、數量分別記為（Li，Wi，di），其中i=1，2，…，n，待下料的零件的長、寬、數量記為（li，wi，bi），求如何下料使所用原材料的總消耗最小且所用原材料的種類最少。可用如下數學模型來描述：

上述模型是一個大型整數線性規劃模型，隨著原板材種類的增加，下料方式總數也將急劇增加，導致用單純形法或分支定界法很難求解。

2混沌粒子群算法

粒子群優化（PSO）算法是在1995年由Kennedy和Eberhart提出的，它是一種集群智能方法的演化計算技術。PSO算法思想就是跟蹤最的好點，并逐漸向最好的點靠近。該算法收斂速度快，但和其它全局優化算法一樣，PSO算法同樣存在容易收斂早熟的現象。

混沌則是一種普遍的非線性現象，它的基本思想是把變量從混沌空間變換到解的空間，它的行為復雜并且類似隨機，混沌變量具有遍歷性、隨機性、規律性特點。尤為重要的是，該算法的遍歷性特點可以用做算法搜索過程中避免陷入局部最優的一種優化機制。

綜上所述，根據粒子群算法和混沌優化方法各自的優缺點，本文提出了將混沌算法迭代引入粒子群算法中，組成新的混合算法一_混沌粒子群優化算法（CPSO）。該混合算法的主要思想是將混沌融合到粒子運動中，避免陷入局部最優，可以達到較好的效果。

該混合算法步驟如下：

Step1首先設置參數，初始化所有粒子（設群規模為N），隨機設置粒子的初始速度和初始位置，計算其中每個粒子的適應度，設置其中每個粒子的個體最優點Pbest，Pbest里的最好設為gbest。

Step2計算粒子新的飛翔位置和飛翔速度，同時更新粒子的最初位置和速度。檢驗粒子新位置是否在所設置的約束區域內，如果在，就將粒子的位置和速度更新為新計算出的值；否則不更新。

Step3檢驗每個粒子的適應值，若現值優于Pbest，，就用當前的位置替換Pbest；若所有粒子中有優于gbest的，就重新設置gbest。

Step4根據公式Pi，n+1=Pi，n+citi，n-di更新每個粒子的Pbest的位置，并計算它的函數值。如果比之前的值優，就更新Pbest。再遍歷出所有粒子中Pbest的函數值優于gbest的，并且重置gbest。根據式ti，n+1=μti，n（1-ti，n）更新ti，n+l。

Step5根據公式g*=g*+citn-di重新確定gbest的位置，并計算出它的函數值。若這個值比更新前的優就重置；否則，不更新。根據公式tn=μtn（1-tn）更新tn的值。

Step6檢查終止條件，若己經達到所設置的最大迭代次數或最優解不再變化，就跳出當前迭代，輸出最優值。否則，轉Step2。

3混沌粒子群算法求解多目標二維切割問題與貪心啟發式算法[6]的比較

文獻6中，通過貪心啟發式算法解決了一個多目標二維切割的實際問題，但是容易陷入局部最優，而該混沌粒子群算法更容易跳出局部最優，如圖1所示。

4結論

本文重點討論了多目標二維下料問題的解法，即采用混沌粒子群算法的近似求解，該算法簡明，易于編程。實踐證明，采用該算法能得到很好的解。

參考文獻

[1]Beasley J.E.Algorithms for Unconstrained two-dimensional Guillotine Cutting，Journal on Operation Research Society，Vol36，pp.297-306，1985.

[2]Beasley J.E.An Exact two-dimensional Non-guillotine cutting Tree Search Procedure，Journal of Operation Research Society，Vo33，pp.49-64，1985.

[3]李友如，閻春平，劉飛.基于二維約束Non-Guillotine切割的插補算法[J].重慶大學學報（自然科學版），2002（10）.

[4]KwnndeyJ，Eberhart R.Particle swarm optimization.In：Proc IEEE International conference on Neural Networks，Perth，Australia，1995，1942-1948.

[5]李兵，蔣慰孫.混沌優化方法及其應用[J].控制理論與應用，1997，14（04）：613-615.

[6]熊慧，黃菊永.基于貪心啟發式算法的多目標二維切割問題[J].電子技術與軟件工程，2017.endprint