離散粒子群算法在矩形排樣問題上的應用研究

陳 釗

(安徽職業技術學院 實訓中心，安徽 合肥 230011)

關鍵字： 離散粒子群算法；矩形排樣；組合優化；

矩形件優化排樣是在給定的板材上將待排矩形件按照最優方式進行排布, 以便最大限度地利用材料, 其實質就是一個組合優化的二維布局問題, 但至今仍無法找到解決該問題的有效多項式時間算法。對于矩形優化排樣問題的研究，主要有啟發式算法的研究、基于人工智能算法的研究以及基于運籌學方法的研究，都取得了很多成果。近年來，基于人工智能算法對于排樣問題的研究是現在和未來研究的重點。

1 問題描述

粒子群優化算法( Particle Swarm Optimization) 是由Kennedy 和Eberhart[1，2]于1995 年在鳥群、魚群和人類社會行為規律的啟發下提出的一種基于群智能的演化計算技術。他們提出了PSO算法的離散二進制版，但這只是在對經典連續性PSO問題的針對性修改，并沒有考慮到離散型問題組合優化的特點。Clerc[3]提出的DPSO算法，說明了解決離散型問題的關鍵在于對于問題域的定義及其對于PSO算法相關的數學對象和運算規則的定義。鐘一文等[4]利用DPSO很好的解決了TSP問題。針對矩形優化排樣問題，由于排樣序列不是連續的序列而是一串不重復且屬于一定范圍內的離散型序列，因此屬于離散型組合優化問題。本文通過固定的排樣規則(剩余矩形排樣法)將原本復雜的二維排樣問題轉換成為可以求解組合優化的問題，對離散粒子群算法進行了改進，根據所求解問題及離散量運算的特點，對粒子的位置、速度等量及其運算規則進行了重新定義，取得了很好的結果。……