王鑫 楊柳叢

摘 要：該文針對皮革排樣優(yōu)化中保持種群個(gè)體多樣性和全局尋優(yōu)存在的問題，研究了粒子群算法、基于小生境的粒子群算法及基于免疫原理的粒子群算法這3種方法，分別對其算法的原理和操作步驟進(jìn)行闡述，增強(qiáng)了研究者對粒子群算法的理解，提供了研究粒子群的比較系統(tǒng)的算法研究現(xiàn)狀，最后對粒子群的應(yīng)用方向進(jìn)行列舉，使學(xué)者對粒子群算法的應(yīng)用及發(fā)展有進(jìn)一步了解。

關(guān)鍵詞：皮革排樣 粒子群算法 改進(jìn)

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2015）12（a）-0270-02

排樣是指在一個(gè)平面（母版）內(nèi)排布多個(gè)面積小于母版的平面（子版），排樣優(yōu)化是指讓子版盡可能多地排進(jìn)母版內(nèi)，使母版利用率最高。母版利用率的提升對提高生產(chǎn)效率、經(jīng)濟(jì)效益和節(jié)省資源具有重要的現(xiàn)實(shí)意義和價(jià)值。排樣優(yōu)化問題是組合優(yōu)化領(lǐng)域中計(jì)算復(fù)雜性最高的一類NPC（Nondeterministic Polynomial Complete）問題，解決排樣優(yōu)化問題的主要途徑多趨向于現(xiàn)代優(yōu)化技術(shù)中的各種仿生學(xué)理論和智能算法。

粒子群優(yōu)化算法PSO（Particle Swarm Optimization）是源于鳥群覓食運(yùn)動行為的啟發(fā)，是動物個(gè)體之間集體合作與競爭的自組織體現(xiàn)。這種基于生物群體間的生物信息交流的共享機(jī)制進(jìn)行搜索更新的算法，可以得到當(dāng)前目標(biāo)函數(shù)的最優(yōu)解。同時(shí)這種算法也能夠在連續(xù)的定義域內(nèi)搜索函數(shù)極值[1]。對于比較簡單的粒子群可以較容易收斂到最優(yōu)解。而對于比較復(fù)雜的多重最優(yōu)解問題，這種方法也提供了較優(yōu)的解決辦法。該文介紹了粒子群優(yōu)化算法的應(yīng)用[2]、基于小生境的粒子群排樣優(yōu)化算法以及基于免疫原理的粒子群排樣優(yōu)化算法并且對粒子群新的應(yīng)用做了展望。

1 粒子群算法的應(yīng)用

1.1 粒子群算法在不規(guī)則件排樣中的應(yīng)用

首先以零件的入排交換序列和角度變異序列作為粒子運(yùn)動速度，以零件入排編碼值來表示粒子的位置，從而構(gòu)造粒子群算法，然后利用剩余矩形動態(tài)匹配算法完成解碼和局部尋優(yōu)任務(wù)，并結(jié)合不規(guī)則件的正交靠接算法完成自動排樣任務(wù)。

粒子群算法的基本程序如下。

（1）初始化粒子群，即隨機(jī)產(chǎn)生各個(gè)粒子的初始解和交換序列。

（2）依據(jù)粒子當(dāng)前位置得出其個(gè)體極值及群體最佳極值，并且計(jì)算新解：①推算當(dāng)前粒子和、的交換序列及旋轉(zhuǎn)角度變異序列；②根據(jù)式（1）計(jì)算粒子的速度，得到粒子新的解，如果有更好的解，更新。

（3）如果在整體粒子群中可以找到更優(yōu)的解，那么就更新。

（4）如果滿足跳出循環(huán)條件（足夠優(yōu)的位置或最大迭代次數(shù)），那么就終止計(jì)算并輸出結(jié)果；否則跳轉(zhuǎn)到步驟（2），繼續(xù)循環(huán)計(jì)算。

最后得到運(yùn)用粒子群算法的最終排樣結(jié)果。

1.2 基于小生境的粒子群排樣優(yōu)化算法

小生境技術(shù)源于遺傳算法，這種方法能夠讓基于群體的隨機(jī)優(yōu)化算法形成物種，然后使對應(yīng)的優(yōu)化算法可以解出多個(gè)最優(yōu)解 [3]。針對排樣優(yōu)化問題，基于小生境的粒子群優(yōu)化算法關(guān)鍵是在物種進(jìn)化過程中小生境技術(shù)具有保持物種多樣性的優(yōu)勢，可以達(dá)到避免陷入局部最優(yōu)的目的。在一定程度上使排版結(jié)果更優(yōu)。

基于小生境的粒子群算法（NPSO）步驟如下。

（1）初始化整個(gè)粒子群，隨機(jī)產(chǎn)生各個(gè)粒子的初始位置和速度。

（2）依據(jù)粒子間的歐式幾何距離把種群分成多個(gè)子群。

（3）利用式（2）更新每一個(gè)粒子的速度和位置參量。

（4）依據(jù)粒子位置使用BL算法（最下最左算法）進(jìn)行排樣，計(jì)算適應(yīng)度值F=1/排樣高度。

（5）依據(jù)F的值更新粒子、子群和整個(gè)種群的當(dāng)前最優(yōu)解。

（6）判斷在連續(xù)代內(nèi)子群是否有新的最優(yōu)解，若存在新的最優(yōu)解則跳到步驟（8）；否則進(jìn)行步驟（7）。

（7）重置該子群的速度和位置參量。

（8）迭代次數(shù)為，判斷是否為最大迭代值，如果是，則終止迭代過程，執(zhí)行結(jié)束；否則跳轉(zhuǎn)到步驟（3）繼續(xù)執(zhí)行。

1.3 基于免疫原理的粒子群排樣優(yōu)化算法

基于免疫原理的粒子群排樣優(yōu)化算法運(yùn)用生物免疫系統(tǒng)的自適應(yīng)能力，得到粒子群優(yōu)化的免疫機(jī)制策略，進(jìn)而用這種方法來解決排樣優(yōu)化問題，利用濃度機(jī)制實(shí)現(xiàn)多樣性度量來控制種群特征，進(jìn)而擴(kuò)大搜索空間，并且將個(gè)體的優(yōu)勢基因免疫儲備在免疫中增強(qiáng)。為了制定種群多樣性度量指標(biāo)和濃度計(jì)算，以基本的粒子群優(yōu)化算法為基礎(chǔ)。則該算法隨機(jī)生成 M+N個(gè)新粒子進(jìn)行免疫調(diào)節(jié)，擴(kuò)大搜索空間。

為了達(dá)到粒子群搜索的多樣性得到有效增強(qiáng)的目的，通過濃度概率的大小來降低濃度高的個(gè)體被選擇的概率，從而提高濃度低的個(gè)體被選擇的概率。從中選擇 N 個(gè)粒子形成新一代的粒子群。針對排樣優(yōu)化中保持種群個(gè)體多樣性及全域?qū)?yōu)存在的問題，此方法提高了算法的全域搜索速度并且保持了種群個(gè)體多樣性，從而更好地對不規(guī)則的零件進(jìn)行排樣。

2 結(jié)論

該文論述了粒子群優(yōu)化算法在二維不規(guī)則排樣問題中的應(yīng)用。粒子群優(yōu)化算法對現(xiàn)有的應(yīng)用實(shí)例進(jìn)行探討，并在構(gòu)造粒子飛行速度更新運(yùn)算上進(jìn)行研究；基于小生境的粒子群算法能夠在不改變時(shí)間復(fù)雜度的前提下，增加全局搜索能力，從而彌補(bǔ)粒子群算法的容易陷入局部最優(yōu)缺陷；基于免疫原理的粒子群排樣優(yōu)化算法是依據(jù)免疫信息處理機(jī)制的全域?qū)?yōu)策略，為了平衡粒子群算法中由于信息流動的單向性導(dǎo)致的種群多樣性弱化，該方法制定粒子濃度的多樣性度量標(biāo)準(zhǔn)。同時(shí)在粒子克隆變異過程中，使優(yōu)勢基因的記憶存儲得到加強(qiáng)；在保證粒子群信息共享機(jī)制的基礎(chǔ)上，增強(qiáng)了算法的全局尋優(yōu)能力并且提高了收斂精度。這3種方法都是在求解排樣優(yōu)化問題的基礎(chǔ)上，提出基于粒子群算法的解決方案，從而有效提高材料利用率。

3 粒子群算法研究的展望

（1）理論研究：自誕生以來其數(shù)學(xué)基礎(chǔ)一直不完備，特別是收斂性一直沒有得到徹底解決。因此，仍需要對PSO的收斂性等方面進(jìn)行進(jìn)一步理論研究。

（2）信息共享機(jī)制：基于鄰域拓?fù)涞牧Ｗ尤簝?yōu)化算法局部模型有效地提高了PSO的全局搜索能力，充分運(yùn)用和改進(jìn)現(xiàn)有拓?fù)浣Y(jié)構(gòu)并提出新的拓?fù)?，從而改善算法性能，是一個(gè)值得研究的問題。同時(shí)，PSO算法具有較快的收斂速度，而局部模型具有較優(yōu)的全局搜索能力，對兩者結(jié)合得到的算法作進(jìn)一步研究，保證新的算法不僅具有較優(yōu)的全局搜索能力，而且具有較快的收斂速度，也是一個(gè)很有意義的研究方向。

（3）應(yīng)用研究：算法的有效性和價(jià)值必須在實(shí)際應(yīng)用中才能得到充分體現(xiàn)。

參考文獻(xiàn)

[1] 楊建鋒，孟利民.視頻監(jiān)控系統(tǒng)中實(shí)時(shí)流媒體傳輸控制方法的設(shè)計(jì)[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2012，40（4）：454-457.

[2] 梁利東，鐘相強(qiáng).粒子群算法在不規(guī)則件排樣優(yōu)化中的應(yīng)用[J].中國機(jī)械工程，2010（17）：2050-2052，2069.

[3] 章軍.小生境粒子群優(yōu)化算法及其在分類器集成中的應(yīng)用研究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2007.