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

王秋全，李向，王嶺玲

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

2．中國地質(zhì)大學(xué)計算機(jī)學(xué)院，湖北武漢 430074

3．武漢工程科技學(xué)院機(jī)械與電子信息學(xué)部，湖北武漢 430200

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

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

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

2．中國地質(zhì)大學(xué)計算機(jī)學(xué)院，湖北武漢 430074

3．武漢工程科技學(xué)院機(jī)械與電子信息學(xué)部，湖北武漢 430200

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

粒子群優(yōu)化；調(diào)度網(wǎng)絡(luò)；均衡優(yōu)化；多項目

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

1 多項目并行調(diào)度資源均衡問題模型

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

1．1 數(shù)學(xué)建模的建立

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

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

1．2 方差和峰差

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

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

衡量不均衡程度有2種標(biāo)準(zhǔn)：一是用方差σ2w，一是峰差dw。

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

2 項目并行調(diào)度粒子群算法設(shè)計與優(yōu)化

2．1 粒子的設(shè)計

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

表1 項目數(shù)與工作編號的映射

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

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

2．2 適應(yīng)值函數(shù)

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

2．3 粒子群優(yōu)化算法的改進(jìn)

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

2．3．1 結(jié)合模擬退火算法

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

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

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

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

2．3．2 慣性權(quán)重參數(shù)的修改

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

2．3．3 改進(jìn)后的粒子群算法

改進(jìn)后的PSO算法的步驟：

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

2）根據(jù)目標(biāo)函數(shù)計算每個粒子對應(yīng)的“適應(yīng)值”，用以衡量粒子在該位置所達(dá)到的優(yōu)化程度；

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

4）確定初始溫度；

5）根據(jù)式（10）確定當(dāng)前溫度下各Pi的適配值；

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

7）計算各粒子新位置對應(yīng)的適應(yīng)值；

8）更新各粒子的Pi及其適應(yīng)值，更新群體的Pg及其目標(biāo)值；

9）根據(jù)式（11）計算出慣性權(quán)重；

10）退溫操作；

11）如達(dá)到迭代終止條件（通常為一個預(yù)設(shè)的最大迭代代數(shù)），則程序終止輸出及其適應(yīng)值，否則返回5）進(jìn)行新一輪迭代。

要在資源限制條件下進(jìn)行多項目調(diào)度優(yōu)化，使各項目的工期最短，對所有項目進(jìn)行資源均衡優(yōu)化，即對所有工作的資源分配重新進(jìn)行調(diào)整，使得最終的工期和資源分配趨向于均衡?；静襟E如下：

1）根據(jù)有項目的基本信息，求出各種相關(guān)參數(shù)；

2）運(yùn)用改進(jìn)的PSO算法，對項目進(jìn)行優(yōu)化，使工期最短；

3）將優(yōu)化所得結(jié)果傳入時間／資源數(shù)學(xué)模型；

4）運(yùn)用改進(jìn)的PSO算法，根據(jù)時間／資源數(shù)學(xué)模型，對項目進(jìn)行優(yōu)化。求得最終的工期和資源分配解。

3 算法驗證與實驗結(jié)果分析

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

圖1 項目的雙代號網(wǎng)絡(luò)結(jié)構(gòu)

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

圖2 平均響應(yīng)時間

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

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

4 結(jié)束語

在調(diào)度工作中，為了節(jié)約成本，提高工作效率，充分利用各種資源，總希望每天資源使用量越均衡越好，以達(dá)到資源的最佳利用率。本文提出的改進(jìn)粒子群優(yōu)化算法很好地解決了多項目資源均衡問題，并驗證了不同數(shù)據(jù)規(guī)模對改進(jìn)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］乞建勛，王強(qiáng)，賈海紅．基于熵權(quán)和粒子群的資源均衡新方法研究［J］．中國管理科學(xué)，2008（1）：90-95．

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

［5］李建鋒，彭艦．云計算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法［J］．計算機(jī)應(yīng)用，2011，31（1）：184-186．

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

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

［8］樊瑋．粒子群優(yōu)化方法及其實現(xiàn)［J］．航空計算技術(shù)，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．

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

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

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

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