粒子群優化算法在皮革排樣中的應用

王鑫 楊柳叢

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

關鍵詞：皮革排樣 粒子群算法 改進

中圖分類號：TP391 文獻標識碼：A 文章編號：1672-3791（2015）12（a）-0270-02

排樣是指在一個平面（母版）內排布多個面積小于母版的平面（子版），排樣優化是指讓子版盡可能多地排進母版內，使母版利用率最高。母版利用率的提升對提高生產效率、經濟效益和節省資源具有重要的現實意義和價值。排樣優化問題是組合優化領域中計算復雜性最高的一類NPC（Nondeterministic Polynomial Complete）問題，解決排樣優化問題的主要途徑多趨向于現代優化技術中的各種仿生學理論和智能算法。

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

1 粒子群算法的應用

1.1 粒子群算法在不規則件排樣中的應用

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

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

（1）初始化粒子群，即隨機產生各個粒子的初始解和交換序列。

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

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

（4）如果滿足跳出循環條件（足夠優的位置或最大迭代次數），那么就終止計算并輸出結果；否則跳轉到步驟（2），繼續循環計算。

最后得到運用粒子群算法的最終排樣結果。

1.2 基于小生境的粒子群排樣優化算法

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

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

（1）初始化整個粒子群，隨機產生各個粒子的初始位置和速度。

（2）依據粒子間的歐式幾何距離把種群分成多個子群。

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

（4）依據粒子位置使用BL算法（最下最左算法）進行排樣，計算適應度值F=1/排樣高度。

（5）依據F的值更新粒子、子群和整個種群的當前最優解。

（6）判斷在連續代內子群是否有新的最優解，若存在新的最優解則跳到步驟（8）；否則進行步驟（7）。

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

（8）迭代次數為，判斷是否為最大迭代值，如果是，則終止迭代過程，執行結束；否則跳轉到步驟（3）繼續執行。

1.3 基于免疫原理的粒子群排樣優化算法

基于免疫原理的粒子群排樣優化算法運用生物免疫系統的自適應能力，得到粒子群優化的免疫機制策略，進而用這種方法來解決排樣優化問題，利用濃度機制實現多樣性度量來控制種群特征，進而擴大搜索空間，并且將個體的優勢基因免疫儲備在免疫中增強。為了制定種群多樣性度量指標和濃度計算，以基本的粒子群優化算法為基礎。則該算法隨機生成 M+N個新粒子進行免疫調節，擴大搜索空間。

為了達到粒子群搜索的多樣性得到有效增強的目的，通過濃度概率的大小來降低濃度高的個體被選擇的概率，從而提高濃度低的個體被選擇的概率。從中選擇 N 個粒子形成新一代的粒子群。針對排樣優化中保持種群個體多樣性及全域尋優存在的問題，此方法提高了算法的全域搜索速度并且保持了種群個體多樣性，從而更好地對不規則的零件進行排樣。

2 結論

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

3 粒子群算法研究的展望

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

（2）信息共享機制：基于鄰域拓撲的粒子群優化算法局部模型有效地提高了PSO的全局搜索能力，充分運用和改進現有拓撲結構并提出新的拓撲，從而改善算法性能，是一個值得研究的問題。同時，PSO算法具有較快的收斂速度，而局部模型具有較優的全局搜索能力，對兩者結合得到的算法作進一步研究，保證新的算法不僅具有較優的全局搜索能力，而且具有較快的收斂速度，也是一個很有意義的研究方向。

（3）應用研究：算法的有效性和價值必須在實際應用中才能得到充分體現。

參考文獻

[1] 楊建鋒，孟利民.視頻監控系統中實時流媒體傳輸控制方法的設計[J].浙江工業大學學報，2012，40（4）：454-457.

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

[3] 章軍.小生境粒子群優化算法及其在分類器集成中的應用研究[D].合肥：中國科學技術大學，2007.