一種新的離散粒子群算法在指派問題中的應用

摘要：指派問題在組合優化中屬NP-complete問題。提出了一種基于離散粒子群算法的求解方法。算法中每個粒子的位置代表了一種可行的指派方案，在迭代中通過交叉策略和局部搜索策略來更新粒子的位置，這既保證了粒子位置的可行性，又增加了粒子的多樣性，避免陷入早熟收斂。通過實例仿真可以看出DPSO算法簡潔，較以往算法具有更好的收斂性，能得到更優的解，能夠求解匈牙利法不能求解的指派問題。對不同的問題。通過影響參數的調整，可以取得好的收斂效果。

關鍵詞：指派問題；離散粒子群算法；交叉策略；局部搜索

中圖分類號：TP30I.6

文獻標志碼：A

文章編號：1001—3695(2009)11-4091-03