基于粒子群算法的多項目資源均衡方法研究

王秋全，李向，王嶺玲

1．中國交通建設股份有限公司西北區域總部，陜西西安 710065

2．中國地質大學計算機學院，湖北武漢 430074

3．武漢工程科技學院機械與電子信息學部，湖北武漢 430200

基于粒子群算法的多項目資源均衡方法研究

王秋全1，李向2，王嶺玲3

1．中國交通建設股份有限公司西北區域總部，陜西西安 710065

2．中國地質大學計算機學院，湖北武漢 430074

3．武漢工程科技學院機械與電子信息學部，湖北武漢 430200

針對傳統粒子群算法容易陷入局部最優的缺點，提出利用動態慣性權重參數和模擬退火算法修改突變概率，進而改進傳統粒子群算法，探討各項目工期最短情況下的多項目資源均衡分配問題。通過對比試驗表明，改進的粒子群優化（particle swarm optimization，PSO）算法很好地實現了多項目的資源均衡優化，通過同比試驗驗證了改進PSO算法在解決不同規模多項目的資源均衡問題時的算法時間復雜度的線性增長性，很好地表達了人們的調度意圖。

粒子群優化；調度網絡；均衡優化；多項目

工業設計中的優化問題經常遇到，許多問題最后都可以歸結為優化問題。解決優化問題主要涉及2個方面：一是要求尋找全局最小點，二是要求有較高的收斂速度。為了解決各種各樣的優化問題，人們提出了許多優化算法，比較著名的有爬山法、人工神經網絡、遺傳算法［1］、粒子群算法等。近些年國外對于研究優化的問題有很大進步。2009年Yen等［2］重點研究了動態調整粒子群的數量。在國內，2008年，建勛等［3］提出了基于熵權和粒子群解決資源均衡問題的新方法。同年，Li Xiang［4］提出了利用遺傳算法解決多項目資源均衡問題，取得了較好的效果。然而對于多資源任務調度，李間鋒等［5］針對云計算的編程模型框架，提出了一種具有雙適應度的遺傳算法，使調度結果的任務平均完成時間縮短，解決了一些重要的問題。許川佩等［6］采用量子粒子群算法在解決功耗約束下實現了SOC測試的調度優化，縮短了測試的時間，算法實現簡單。2013年，劉立冬［7］結合蟻群算法和遺傳算法優勢和特點，對TSP問題將2種算法按獨特的方式融合生成遺傳蟻群算法，實驗證明該融合算法的穩定性優于2種單獨的算法。本文針對傳統粒子群算法容易陷入局部最優的缺點，提出利用動態慣性權重參數和模擬退火算法修改突變概率方法改進傳統粒子群算法，探討各項目工期最短情況下的多項目資源均衡分配問題。

1 多項目并行調度資源均衡問題模型

調度是指對工程進行系統的編排、決策和控制，協調各道工序，合理安排各種資源，在滿足工程總工期的條件，發揮各種資源最大經濟效益。優化過程是利用時差，不斷改進初始網絡方案，在滿足既定條件下，按某一個或幾個衡量指標來尋求最優的方案。對資源均衡的優化目前主要采用“消峰填谷”法，利用工序的時差，反復調整，拉平資源消耗的高峰。這種方法計算過程復雜，對于工序繁多的大型工程，即使采用計算機求解也需要較長時間，而且計算結果是近似最優解，誤差比較大，下面討論多資源調度的數據模型。

1．1 數學建模的建立

設有P個獨立的項目，每個項目均包含不同件數的工作，即第i個項目包含Pi件工作；在資源庫中有M種資源，第m種資源的總量為Wm；T為所有項目的總的預定完成工期，Tk為第k個項目的預定完成工期；Wm（t）為第t件工作日所有項目對第m種資源的需求量；Wij，m（t）為第i個項目中第j件工作在第t件工作日對第m個資源的需求量；Tij為第i個項目中第j件工作的開始時間；dij為第i個項目中第j件工作的持續時間；Sij為第i個項目中第j件工作的的富余時間；Ri表示第i個項目的工作集；Rij表示第i個項目中第j件工作；Uij為它所有緊前工作的緊前工作集，i∈［1，n］，i∈［1，Pi］，ˉWm。 為所有項目的對第m種資源的平均消耗量。針對所述問題，文中采用取方差最小的方法，建立如下數學模型：

式（1）為目標函數，要求項目資源分配均衡，并且還要根據項目的優先級來合理分配資源，?為各個項目的優先級權重。式（2） ～（6）為約束條件，約束條件（2）表示第i個項目中第j件工作第t時刻的資源消耗量，必須小于該資源的的供應量；約束條件（3）保證t時刻進行的工作Uij沒有超出工期范圍；約束條件（4）保證決策變量為正整數；約束條件（5）ˉWm為第m種資源的平均需求量；約束條件（6）考慮到不同項目的重要程度不同，用?k表示第k個項目的權重，所有項目的權重的總和為1。

1．2 方差和峰差

一個項目在不同時刻t對某種資源的單需求量W（t）是不同的，t＝（0，1，…，T），T是項目的預定完成工期。在預定完成工期內，對某種資源在單位時間內的平均需求量稱為平均單需量，記為ˉW。則

式中：Q為項目對資源的需求總量；單需量W（t）圍繞平均單需量ˉW上下波動。波動幅度越大，表明資源利用越不均衡；反之則表明資源的利用較均衡。

衡量不均衡程度有2種標準：一是用方差σ2w，一是峰差dw。

2）峰差。資源利用不均衡的峰差dw由式（8）定義：為使資源均衡利用，dw要盡可能小，也就是使maxW（t）最小。

2 項目并行調度粒子群算法設計與優化

2．1 粒子的設計

由于本文的問題描述只是目標由工期最短改為資源最優，所以，在設計粒子時，只考慮資源的問題，建立一個粒子長度為Q的三維粒子，第1維表示項目，并以自然數1，2，3，…，Q表示不同的項目；第2維是粒子位置xj，第i個項目的工作號集合；第3維是粒子位置Yxj，表示資源分配。三維維粒子的表示如表1、2所示。

表1 項目數與工作編號的映射

表2 工作編號與資源分配的映射

表1為項目數與工作編號的映射關系。在表2中，xij為第i個項目第j件工作的工作編號，xij∈［1，Qi］，Qi第i個項目的工作數，第三維粒子Yxij，k為占用的第 Rk資源量，Yxij，k∈［1，Rm＋1］，k［1，m］。 在解碼過程中，對占用同種資源的工作進行比較，如果資源分配在占用同種資源的工作之間出現沖突，比較Yxij，k與?k相乘的結果，值最大的粒子位置不變，其他粒子更新粒子位置，否則粒子位置不變。

2．2 適應值函數

由于本節討論的是資源均衡的問題，所以目標函數有2種，分別是方差最小和峰差最小。在本節中，取方差最小為目標函數：

2．3 粒子群優化算法的改進

由于基本的PSO算法精度低、易發散等原因往往出現早熟收斂或收斂緩慢等缺點。因此，設計PSO算法的參數以及操作，應主要針對如何保證種群的多樣性，以提高算法精度，從而提高算法的搜索效率，避免早熟收斂現象。本文在前人研究成果的基礎上，借鑒文獻［6］關于混合算法和文獻［8］改進慣性權重的思想，設計了一種改進PSO算法，來平衡全局搜索能力和局部搜索能力，提高收斂速度，從而減少獲得最優解所需的運行代數。

2．3．1 結合模擬退火算法

模擬退火（simulated annealing，SA）算法是1982年由Kirkpatriek等提出的一種隨機優化方法，它模擬了物理中金屬的降溫過程。SA也被改進用于求解多目標優化問題，由于它具有很強的全局搜索能力，在搜索中具有概率突跳的特性，所以對搜索非劣解集非常有利，能夠有效避免搜索陷入局部極小解。簡單的說，就是SA算法在搜索過程中不但接受好的解，而且也允許以一定概率接受差的解。同時，可以通過溫度參數設置突跳概率，即突跳概率隨著溫度的下降而減小，當溫度趨于0時，突跳概率值也趨于0，理論上已經證明，SA算法在一定條件下以概率1收斂到全局最優解。

由于在基本粒子群算法中，速度更新采用了群體最佳位置，所有粒子都傾向于群體最佳位置。如果群體的最佳位置處于局部極小解，那么，所有的粒子都將趨向于局部極小解，從而導致搜索的分散性變差，使得全局探索能力減弱。為了使算法在運行過程中，盡可能少的陷入局部極小解，本文將從Pi中選取一個位置，記作Pgnew，來代替更新公式中的Pg。 改進后的更新公式為

為了性能好的Pi有較高的概率被選中，借用SA算法的機制，從而可計算問題t時Pi相對Pg的突跳概率——e－（fpi－fpg）／t，f為目標函數值，然后將此突跳概率值當做Pi的適配值，則Pi代替Pg的概率公式為

式中N為種群大小。根據上述替代概率，采用輪盤賭策略隨機確定哪個Pi將成為Pgnew。

2．3．2 慣性權重參數的修改

在PSO算法的參數中，慣性權重w用來調整全局和局部搜索的能力。w值越大越容易實現全局搜索，w值越小越有利于局部搜索算法進行初期，全局搜索能力較強，但是如果找不到最好點，隨著w的減小，局部搜索能力變強，容易陷入局部極值。為了既能在進化初期得到大的搜索空間避免陷入局部最優，又能在進化后期進行更精細的搜索以加快收斂速度，需用不斷更新慣性權重參數w：式中：i為當前迭代次數，imax為最大迭代次數，wn為初始慣性權重值，we為運行至最大迭代次數時的慣性權重值。在基本粒子群算法中，由于步長較小，w的變化幅度也較小，因此不易陷人局部最優。

2．3．3 改進后的粒子群算法

改進后的PSO算法的步驟：

1）在需要求解的問題的解空間中，初始化一個粒子群，即隨機產生各粒子的初始位置和速度；

2）根據目標函數計算每個粒子對應的“適應值”，用以衡量粒子在該位置所達到的優化程度；

3）令各粒子的自身最佳位置Pi及其適應值為當前位置及其適應值，令群體最佳位置 及其適應值為所有Pg中的最佳位置及其適應值；

4）確定初始溫度；

5）根據式（10）確定當前溫度下各Pi的適配值；

6）采用輪盤賭策略從所有Pi中確定NPg，然后根據公式（9）更新各粒子的速度和位置；

7）計算各粒子新位置對應的適應值；

8）更新各粒子的Pi及其適應值，更新群體的Pg及其目標值；

9）根據式（11）計算出慣性權重；

10）退溫操作；

11）如達到迭代終止條件（通常為一個預設的最大迭代代數），則程序終止輸出及其適應值，否則返回5）進行新一輪迭代。

要在資源限制條件下進行多項目調度優化，使各項目的工期最短，對所有項目進行資源均衡優化，即對所有工作的資源分配重新進行調整，使得最終的工期和資源分配趨向于均衡。基本步驟如下：

1）根據有項目的基本信息，求出各種相關參數；

2）運用改進的PSO算法，對項目進行優化，使工期最短；

3）將優化所得結果傳入時間／資源數學模型；

4）運用改進的PSO算法，根據時間／資源數學模型，對項目進行優化。求得最終的工期和資源分配解。

3 算法驗證與實驗結果分析

項目的雙代號網絡結構如圖1所示。但是由于實例中，許多工作的資源單需量與可提供資源的總量相比較大，而每種資源的提供量都限制在很小的范圍內，進行資源限制下調度優化后，再進行時間／資源綜合優化的效果不是很明顯。因此，需要對各種資源的供給量進行重新設置，其中選取設計、采購、工藝、程序員、熱處理、電加工、數控、裝配、數模等人員分別為40、24、12、10、21、48、32、15、12，重新設置后各項目的工作所需資源類型、需求量及工作持續時間如表3所示。

圖1 項目的雙代號網絡結構

表3 各項目工作所需資源類型、需求量及工作持續時間

圖2 平均響應時間

為驗證改進的PSO算法在大規模數據下的可實現性和優越性，用改進的PSO算法分別進行3、5、10直至100個項目同時運行，每個項目的工作數為50個左右，每組數據測試5次取平均值，然后用未改進的PSO算法進行相同的測試，再將2種算法所得結果相比較。

在圖2中，當同時執行的項目個數為5、10、20、40、60、80和100時，圖中標出了2種算法的平均響應時間。用10個、20個和40個項目進行比對時，改進的PSO算法比未改進的PSO的平均優化時間分別降低了4．1%、4．7%和5．3%，當用60個、80個和100個項目進行比對時，改進的PSO算法比未改進的PSO的平均優化時間分別降低了7．2%、8．15%和9．29%。從比較可以得出當項目數為1～40個時，改進的PSO算法的優勢并不明顯，相比未優化的PSO算法，求解時間只降低了4．7%左右，算法效率的提高不是很明顯；當項目數為60～100個時，求解時間降低了8%左右，并且隨著項目個數的增加，改進的PSO算法節約的時間呈遞增趨勢，這說明，改進的PSO的算法對于求解資源受限的多項目計劃調度問題的時間／資源綜合優化時適合的，并且，數據規模越大，改進的PSO的算法優勢就越明顯。

4 結束語

在調度工作中，為了節約成本，提高工作效率，充分利用各種資源，總希望每天資源使用量越均衡越好，以達到資源的最佳利用率。本文提出的改進粒子群優化算法很好地解決了多項目資源均衡問題，并驗證了不同數據規模對改進PSO算法性能的線性影響。

［1］SUN C L，ZENG J C，PAN J S．An improved vector particle swarm optimization for constrained optimization problems［J］．Information Sciences，2011，181（6）：1153-1163．

［2］YEN G G，LEONG W F．Dynamic multiple swarms in mul-tiobjective particle swarm optimization［J］．IEEE Transac-tions on Systems，Man and Cybernetics，Part A：Systems and Humans，2009，39（4）：890-911．

［3］乞建勛，王強，賈海紅．基于熵權和粒子群的資源均衡新方法研究［J］．中國管理科學，2008（1）：90-95．

［4］李向，譚偉，康立山．基于遺傳算法的資源均衡優化研究［J］．計算機工程與設計，2008，29（7）：4447-4449，4583．

［5］李建鋒，彭艦．云計算環境下基于改進遺傳算法的任務調度算法［J］．計算機應用，2011，31（1）：184-186．

［6］許川佩，胡紅波．基于量子粒子群算法的SOC測試調度優化研究［J］．儀器儀表學報，2011，32（1）：113-119．

［7］劉立東，蔡淮．融入遺傳算法的混合蟻群算法［J］．計算機工程與設計，2008，29（5）：1248-1249．

［8］樊瑋．粒子群優化方法及其實現［J］．航空計算技術，2004（9）：39-42．

The research for the multi-project resource equalized methods based on particle swarm optimization

WANG Qiuquan1，LI Xiang2，WANG Lingling3
1．West Section Headquarters，China Transportation Construction Co．，Ltd，Xi’an 710065，China
2．School of Computer，China University of Geosciences，Wuhan 430074，China
3．Mechanical and Electronic Information Department，Wuhan University of Engineering Science，Wuhan 430200，China

For the traditional particle swarm optimization easily falling into local optimum，this paper proposes a method that dynamic inertia weight parameter and simulated annealing algorithm are applied to modify the mutation probability to improve the traditional particle swarm optimization，and investigates the balanced allocation problem of multi-project resource under the circumstances that each project has the shortest duration．The comparative exper-iments indicate that the improved particle swarm optimization can nicely achieve the resource balanced optimization of multi-project，and year-on-year experiments verify the linear growth of time complexity of the improved PSO when solving resource balanced optimization of multi－project in different sizes，which can better express the inten-tion of scheduling．

particle swarm optimization；scheduling network；balanced optimization；multi-project

TP3．5

A

1009-671X（2014）03-0055-05

10．3969／j．issn．1009-671X．201312009

http：／／www．cnki．net／kcms／doi／10．3969／j．issn．1009－671X．201312009．html

2013-12-17．

日期：2014-06-05．

中國地質大學（武漢）橫向科研基金資助項目（2012196539）；湖北省自然科學基金資助項目（2012195075）．

王秋全（1962-），男，工程師；

王嶺玲（1989-），女，碩士。

王嶺玲，E-mail：2219887348＠qq．com．