基于約束的離散粒子群算法求解大規模指派問題

[摘 要] 針對現有進化算法在求解傳統指派問題時因取整而影響優化效果的問題，采用了一種基于AllDifferent約束的置換離散粒子群優化算法，該算法針對指派問題中各變量不能重復取值的特點，改進了算法的迭代方式，并引入了模擬退火的差解接受準則以提高優化效果，仿真算例表明改進后的算法在質量上和時間上更具有效性。

[關鍵詞] 指派問題;粒子群優化算法;混合算法;大規模

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2009 . 21 . 032

[中圖分類號]F270.7[文獻標識碼]A[文章編號]1673 - 0194(2009)21 - 0102 - 03

1引言

指派問題(Assignment Problem，AP)是一類經典的組合優化問題，旨在將資源(人員、機器等)按某種方式分配到各項工作中，以使其效果達到最優。根據任務與人員的數目比對，指派問題可分為一對一、一對多及多對多幾種類型。本文研究一對一型，即被分配的任務數和人數相等，每個人僅承擔一項任務。指派問題屬于NP問題，精確算法(如動態規劃、分支定界法[1]等)雖然可以得到準確解，但時間復雜性與任務數成指數關系，而近年來出現的模擬退火算法[2]、遺傳算法[3]等則多采用小規模算例對算法進行驗證，無法說明算法求解大規模指派問題的有效性，文獻[4]對大規模的一對一指派問題進行了優化求解，但其采用實數域方法進行取整運算，對問題的依賴性較強[5]。

粒子群優化(Particle Swarm Optimization，PSO)算法[6]是一種基于群智能原理的進化算法，源于對自然界中鳥類等生物群體覓食過程的仿真研究，具有概念簡單、控制參數少、容易實現等優點，但最初針對的是連續優化問題。為使該算法能夠處理離散問題，Clerc于2000年對算法進行了改進，提出了離散粒子群優化(Discrete Particle Swarm Optimization，DPSO)算法[7]，并成功應用在求解旅行商問題等組合優化問題上。

本文采用了一種基于AllDifferent約束的置換DPSO算法對指派問題求解，同時為了提高優化性能，嵌入了模擬退火算法的差解接受準則，并對大規模的指派問題進行試算，經過大量的數據試驗，取得了較滿意的結果。

2問題描述

指派問題可簡述為:假設有n項任務需要分配給n個人去完成，每個任務只能分配給一個人處理，且每個人只能承擔一項任務，不同分配方案花費不同的代價，問題的目標旨在找到一種分配方案使得總的花費代價最小。設定Cij表示第i個人完成第j項任務的費用，則可構成費用矩陣Cn × n，另有決策變量

Xij = 1， 如果將第i項任務分配給第j個人;0， 否則。

則指派問題的數學模型[P]:

[P]minCij xij (1)

s. t. Xij = 1，i = 1，2，…，n (2)

Xij = 1，j = 1，2，…，n(3)

目標函數(1)使得完成所有任務的總費用最小，約束(2)要求任務i能且僅能由一個人承擔，約束(3)表示人員j能且僅能承擔一項任務。

3算法求解

經典的PSO算法求解連續函數優化問題的基本原理可用以下的迭代公式來表示:

vit + 1 = c1Rand1()(pit - xit) + c2Rand2()(pgt - xit)(4)

xit + 1 = xit + vit + 1(5)

粒子i在t + 1時刻的新位置是由其t時刻的位置xit、該粒子經過的最優位置pit 、當前全局粒子的最優位置ρgt 以及各項系數來共同決定的，其中c1和c2是加速系數(或稱學習因子)，分別調節向個體最好粒子和全局最好粒子方向飛行的最大步長，Rand()為(0，1) 之間均勻分布的隨機數。

PSO算法是針對連續域問題的，因此在求解組合優化問題時，具有幾個弊端:(1)算法的編碼結構無法保證迭代進化后解的可行性;(2)粒子位置矢量的更新方法如何選擇;(3)算法容易因取整過程而遺漏最優解，導致最終影響優化過程[8]。針對這一情況，本文分3步對算法進行改進:離散域上的重構、基于AllDifferent約束的置換和嵌入模擬退火算法的差解接受準則。

3.1離散域上的算法重構——問題解的表示

PSO算法的編碼設計，即建立位置矢量與指派方案之間的映射關系是設計PSO算法的首要問題。本文采用Hu X等[9]提出的離散方式構造粒子，其編碼規則與遺傳算法的順序編碼相同，可簡單描述為:若有n項任務待指派，粒子維度亦取n，將待分配的人員編號作為粒子的位置進行編碼，這樣一個粒子即對應一個可行的任務指派方案，其數學表示為:粒子pi = (pi1，…，pij，…，pin)，其中i表示種群的規模，pi1，…，pij，…，pin為1 ～ n的一個序列，若pij = 1即表示任務j由編號為1的人員來承擔。

3.2基于AllDifferent約束的置換——位置的迭代方式

文獻[4]采用取整PSO求解大規模指派問題，雖然簡單有效，但容易遺漏較優解，影響優化效果，因此本文采用Rameshkumar在文獻[10]中提出的置換DPSO算法，其最突出的應用就是求解帶有AllDifferent約束的離散問題。AllDifferent約束是一個典型的非二元約束，它要求約束中的變量具有各不相等的值，從費用矩陣角度分析，指派問題即帶有AllDifferent約束的特點，其優越性在于不是一種單純的取代方式，而是位置元素的順次交換，例如對粒子i而言，其t時刻的位置xit = (1，3，5，2，4，6)，它的局部最優位置pit = (2，6，3，5，4，1)，則基于AllDifferent約束的置換DPSO的位置速度迭代公式變為:

(1) 位置減法:兩個位置相減得到一個速度，即一個置換序列集合，其中的重復元素可以省略，即:pit- xit= (2，6，3，5，4，1) - (1，3，5，2，4，6) = vit = {(1→2)，(3→6)，(5→3)，…｝這個速度說明將2和1交換位置，3和6交換位置，依此類推;

(2) 位置加速度:把速度中的置換子集逐個作用到原位置上得到一個新的位置，即xit + vit 。首先用(1→2)作用到xit，有xit + 1 = (2，3，5，1，4，6)，依此類推最終得到xit + 1 = (5，1，3，6，4，2)，即為t + 1時刻粒子i的位置;

(3) 速度加法:把兩個速度的所有置換子集合并，且順序保持不變，實際上就是把兩個速度放在一個集合里;

(4) 速度數乘:系數看作概率選擇，在更新速度時以c1來確定從(pgt - xit)中選擇元素的個數，以c2來確定從(pgt - xit)中選擇元素的個數;

(5) 包含全局最優位置的算法迭代原理與上類似。3.3適應度函數的計算

根據3.1節，一個粒子即對應問題[P]的一個可行解，則可以從粒子位置矢量對應的費用矩陣中提取單位費用進行累加，這樣就把粒子的值轉換為目標函數的值。

3.4退火擾動

PSO算法在向最優粒子不斷靠近的過程中，其移動速度會越來越小，即整個粒子群表現出很強的趨同性，極易陷入局部極值點;另外在解空間內進行搜索時，粒子有時會出現在最優解附近振蕩的現象。為了能進一步提高算法的效率，本文擬用模擬退火算法作用于全局最優粒子的歷史最優值，旨在通過提高歷史最優位置的適應值來使算法跳出局部最優，以提高求解質量。

3.5算法步驟

Step 1:初始化模擬退火的初始溫度、終止溫度和下降速率以及DPSO算法的參數，隨機粒子位置矢量，初始速度為0，計算局部和全局最優粒子，分別記入pi和pg。

Step 2:算法迭代至滿足設定的參數。判斷每個粒子的適應值是否進行替換，根據3.2節中的置換方式，結合迭代公式更新粒子的速度和位置。

Step 3:采用模擬退火算法的差解接受準則對全局最優位置的歷史最優值進行擾動。

Step 4:如未達到結束條件，則返回Step 2;否則輸出全局最優位置pg作為優化后的任務指派方案。

4仿真實驗和分析

先以文獻[11]提供的7 × 7和10 × 10的兩個小規模算例來驗證算法的有效性。設定粒子數為10，迭代20次，均可求得費用代價的最優解167和29。

為進一步驗證置換DPSO算法求解大規模指派問題的性能，采用模擬數據測試，任務個數取20、50、100和300，每個機器完成不同任務的費用代價在[1，1 000]之間隨機生成。為了比較提出算法的性能，同時實現了遺傳算法和基本PSO算法，測試條件相同，均取種群大小30、最大迭代次數50次，遺傳算法的交叉和變異概率分別取0. 7和0. 01，重復實驗20次結果如表1所示。

從表1的計算結果得到如下結論:

(1) 在求解性能方面，基于置換的DPSO算法全部優于遺傳算法和基本PSO算法;

(2) 隨著任務數的增加，基于置換的DPSO算法較其他兩種算法的求解性能有了明顯的提高;

(3) 計算時間方面，由于嵌入了模擬退火的差解接受準則，基于置換的DPSO算法比遺傳算法消耗的時間多，但由于時差以秒記數，因此對于一些離線指派問題的影響不大。

5結論

本文采用基于AllDifferent約束的置換DPSO算法來求解大規模指派問題，算法將進化限制在整數空間內，減少了許多對不必要非可行解域的修正，提高了求解效率。此外通過加入模擬退火的差解接受準則對算法做了進一步的改進，避免了陷入局部極小，增強了全局搜索能力。通過數據仿真驗證了算法的優化性能和搜索效率均有大幅度提高。

主要參考文獻

[1] 符卓，肖雁. 求指派問題多重最優解的分支定界法[J]. 長沙鐵道學院學報，2000，18(1):69-72.

[2] 李冰，徐杰，杜文. 用模擬退火算法求解有順序約束指派問題[J]. 系統工程理論方法與應用，2002，11(4):330-335.

[3] 陶世群，蒲保興. 基于遺傳算法的多級目標非平衡指派問題求解.[J] 系統工程理論與實踐，2001(8):80-85.

[4] 談文芳，趙強，余勝陽，等. 改進粒子群優化算法求解任務指派問題[J]. 計算機應用，2007，27(12):2892-2895.

[5] 王筱萍，高慧敏，曾建潮. 微粒群算法及其在熱軋生產調度中的應用[J]. 運籌與管理，2007，16(1):154-158.

[6] Kennedy J， Eberhart R C. Particle Swarm Optimization. [C] // Proceedings of IEEE International Conference on Neural Networks Piscataway. NJ: IEEE Press， 1995: 1942-1948.

[7] Clerc M. 8 Discrete Particle Swarm Optimization， Illustrated by the Traveling Salesman Problem[M] // G C Onwubolu， B V Babu (eds). New Optimization Techniques in Engineering . Germany， Heidelberg : Springer， 2004: 219-239.

[8] Kennedy J， Eberhart R C. A Discrete Binary Version of the Particle Swarm Algorithm. [C] // 1997 IEEE International Conference on Computational Cyberntics and Simulation : Systems， Man，and Cybernetics，Orlando，USA，1997，Vol.5:4104-4108.

[9] Hu X， Shi Y， Eberhart R. Recent Advances in Particle Swarm[C] // IEEE Internatonal Congress on Evolutionary Computation，2004，Vol.1: 90-97.

[10] Rameshkumar K， Suresh R K， Mohanasundaram. Discrete Particle Swarm Optimization (DPSO) Algorithm for Permutation Flowshop Scheduling to Minimize Makespan[M] // Advances in Natural Computation， Berlin / Heidelberg:Springer，LNCS 3612， 2005: 572-581.

[11] 楊冬，王正歐. 改進的螞蟻算法求解任務分配問題[J]. 天津大學學報:自然科學與工程技術版，2004，37(4):373-376.

Solving Large-scale Assignment Problem by Constraint-based Discrete Particle Swarm Optimization

WANG Min， LI Tie-ke

(School of Economics and Management， University of Science and Technology Beijing-Beijing 100083，China)

Abstract: According to the limited optimization effect of the existing evolutionary algorithms on solving the traditional assignment problems， a method of replacement discrete particle swarm optimization based on AllDifferent constraint is adopted. The algorithm is aimed at the variable features of non-repeated in the assignment problems with an improved iterated mode， and in addition the worse-solution-acceptance criteria of simulated annealing algorithm is introduced to improve the optimal results. Numerical experiments show the feasibility of the improved algorithm for large-scale assignment problems.

Key words: Assignment Problem; Particle Swarm Optimization; Hybrid Algorithm; Large-scale

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文