基于混沌粒子群算法的多目標(biāo)二維切割問(wèn)題

摘要

多維切割問(wèn)題是木材加工、機(jī)加工和造紙等行業(yè)在生產(chǎn)中經(jīng)常遇見的實(shí)際問(wèn)題。排樣切割完成后，往往都會(huì)有一些大小不等、數(shù)量不同的剩余材料。本文優(yōu)化利用這些材料，進(jìn)一步減少浪費(fèi)。通過(guò)和貪心啟發(fā)式^法的比較，證明該混合算法對(duì)解決多目標(biāo)二維切割問(wèn)題是行之有效的。

【關(guān)鍵詞】多目標(biāo)切割問(wèn)題 粒子群算法 混沌粒子群算法

二維切割問(wèn)題在輕 工、排版、玻璃切割等行業(yè)的廣泛應(yīng)用，國(guó)內(nèi)外對(duì)矩形件排樣優(yōu)化的問(wèn)題己經(jīng)做了相當(dāng)深入的研究，實(shí)現(xiàn)了提高板材利用率、縮短排樣時(shí)間的目的。但在排樣切割完成后，往往都會(huì)有一些大小不等，數(shù)量不同的剩余材料，如何更好地再次利用這些材料，這就是本文所要討論的內(nèi)容。

1多目標(biāo)二維切割問(wèn)題數(shù)學(xué)模型

l.1問(wèn)題描述及建模

本文只考慮剩余的材料是矩形的情況，針對(duì)一定數(shù)量和大小的零件需求，建立數(shù)學(xué)模型。由于所剩余的材料大小不等，這類切割問(wèn)題被定義為多目標(biāo)的切割問(wèn)題。

解決復(fù)雜的排樣問(wèn)題的二維優(yōu)化下料模型一般都是構(gòu)造成線性規(guī)劃的數(shù)學(xué)模型，以原材料消耗的總面積最小為目標(biāo)，但是對(duì)于我們所要討論的情況，僅僅考慮消耗的總面積最小是不夠的，還要考慮所用原料的種類最少。

設(shè)原材料板材，其長(zhǎng)、寬、數(shù)量分別記為（Li，Wi，di），其中i=1，2，…，n，待下料的零件的長(zhǎng)、寬、數(shù)量記為（li，wi，bi），求如何下料使所用原材料的總消耗最小且所用原材料的種類最少?？捎萌缦聰?shù)學(xué)模型來(lái)描述：

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

2混沌粒子群算法

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

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

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

該混合算法步驟如下：

Step1首先設(shè)置參數(shù)，初始化所有粒子（設(shè)群規(guī)模為N），隨機(jī)設(shè)置粒子的初始速度和初始位置，計(jì)算其中每個(gè)粒子的適應(yīng)度，設(shè)置其中每個(gè)粒子的個(gè)體最優(yōu)點(diǎn)Pbest，Pbest里的最好設(shè)為gbest。

Step2計(jì)算粒子新的飛翔位置和飛翔速度，同時(shí)更新粒子的最初位置和速度。檢驗(yàn)粒子新位置是否在所設(shè)置的約束區(qū)域內(nèi)，如果在，就將粒子的位置和速度更新為新計(jì)算出的值；否則不更新。

Step3檢驗(yàn)每個(gè)粒子的適應(yīng)值，若現(xiàn)值優(yōu)于Pbest，，就用當(dāng)前的位置替換Pbest；若所有粒子中有優(yōu)于gbest的，就重新設(shè)置gbest。

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

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

Step6檢查終止條件，若己經(jīng)達(dá)到所設(shè)置的最大迭代次數(shù)或最優(yōu)解不再變化，就跳出當(dāng)前迭代，輸出最優(yōu)值。否則，轉(zhuǎn)Step2。

3混沌粒子群算法求解多目標(biāo)二維切割問(wèn)題與貪心啟發(fā)式算法[6]的比較

文獻(xiàn)6中，通過(guò)貪心啟發(fā)式算法解決了一個(gè)多目標(biāo)二維切割的實(shí)際問(wèn)題，但是容易陷入局部最優(yōu)，而該混沌粒子群算法更容易跳出局部最優(yōu)，如圖1所示。

4結(jié)論

本文重點(diǎn)討論了多目標(biāo)二維下料問(wèn)題的解法，即采用混沌粒子群算法的近似求解，該算法簡(jiǎn)明，易于編程。實(shí)踐證明，采用該算法能得到很好的解。

參考文獻(xiàn)

[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切割的插補(bǔ)算法[J].重慶大學(xué)學(xué)報(bào)（自然科學(xué)版），2002（10）.

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

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

[6]熊慧，黃菊永.基于貪心啟發(fā)式算法的多目標(biāo)二維切割問(wèn)題[J].電子技術(shù)與軟件工程，2017.endprint