基于蟻群優化的多目標資源配置模型及應用

喻江平

(燕山大學經濟管理學院，河北秦皇島 0660044)

基于蟻群優化的多目標資源配置模型及應用

喻江平

(燕山大學經濟管理學院，河北秦皇島 0660044)

多目標資源配置問題就是將有限資源分配到不同事件來獲得預期目標。為滿足未來的特定要求，一般需同時對多個目標(如成本最小化或效率最大化)進行優化。為有效獲取一組帕累托解，提出一種改進蟻群算法，該方法可通過增加螞蟻的學習來提高求解效率。通過比較蟻群算法和混合遺傳算法所得的實驗結果，驗證了改進蟻群算法的可行性、有效性及正確性。

蟻群優化；多目標優化；資源配置

0 引言

20世紀60年代早期，多目標優化問題開始受到各領域研究者越來越多的關注。在多目標優化問題中，需同時優化多個目標。在多目標情況下，由于不同目標之間會相互沖突；對于所有目標而言，不一定存在一個最優解。一個目標中的最優解可能在另一個目標中卻是最劣解。在多目標情形下，通常存在一組彼此之間不能作簡單比較的問題解。這類解被稱為帕累托最優解，即除非至少犧牲一個其他目標函數，否則無法對任何函數進行改進。

針對多目標資源配置問題，本文基于蟻群算法提出了一種新的求解方法。為確保資源約束得以滿足，還提出了使用自適應資源界限。實驗結果證明這種基于蟻群算法的方法比遺傳算法更適合求解模擬多目標資源優化問題。

1 多目標資源配置問題

本文主要研究多目標人力資源配置問題的多階段決策模型。在不失一般性的情況下，優化是指在可能選擇上尋求問題解以優化某準則。

⑴符號及參數定義：

i：表示任務指標，i=1,2,…,N;

j：表示員工數量，j=0,1,2,…,M;

N：表示任務總數；

M：表示員工總數；

cij：表示分配到j個員工時任務i的成本；

eij：表示分配到j個員工時任務i的效益；

⑵決策變量：

目標函數(1)表示將所有任務的總效益最大化；目標函數(2)表示將所有員工的總成本最小化；約束(3)確保所分配員工的數量不超過員工總數量；約束(4)確保各個任務i只能獲得一次員工分配。帕累托最優解通常是多目標規劃問題的解。因此，在實施蟻群算法時，增加一個模塊來處理帕累托最優解。

2 求解多目標資源配置問題的蟻群優化算法

蟻群優化算法最早是由Dorigo提出并鼓勵其他學者開發處理NP-hard問題，如旅行商問題、二次分配問題、調度問題、最小權頂點覆蓋問題和曲線分割問題等。蟻群算法受到了對真實螞蟻覓食行為研究的啟發。研究者觀察到螞蟻可以利用信息素構建從蟻巢到食物源之間的最短路徑。

蟻群算法模仿真實螞蟻的覓食行為，這些螞蟻通過沿路分泌信息素的方式進行食物源的信息交流，當有螞蟻找到食物源后它便會返回蟻巢。由于較短路徑上的螞蟻將較快返回蟻巢，因此，這些路徑將聚集更多的信息素。行進中的螞蟻將根據信息素數量按照某概率進行路徑選擇，所以越多螞蟻經過的路徑則對其他螞蟻的吸引力越大，此外通過自我加強行為，會有更多螞蟻經過這些路徑。而且，信息素經過多次揮發，會使那些螞蟻經過次數較少的路徑上的信息素濃度變弱，而那些吸引力大的路徑上的信息素濃度則變強。人工螞蟻不僅模仿以上所述的學習行為，還會經常應用另外一些特定問題的啟發信息。當這種人工蟻群系統已成功應用于各種單一目標問題之后，為了能夠求解多目標問題，需要對其進行一些擴展。

2.1 解的構造

將多目標資源配置問題的可行解看作是資源分配置換，將解的各個部分稱為狀態。分配數量j的資源給第i個項目被稱為一個移步，表示為V(i,j)；移步Vk將螞蟻k從狀態S1移動到狀態S2，從而逐漸使局部解完整。一旦數量j的資源被分配到螞蟻k的解中第i個項目時，則必須根據新的資源數量對可利用資源數量進行更新，且所有不可行移步資源必須保存到禁忌表中，表示為Tabuk。該禁忌表是螞蟻k用來保存不可行分配指標的內存。除了表Tabuk，螞蟻k選出的所有移步都保存在內存中，表示為Vk。螞蟻k從當前狀態移動到下一個狀態，利用表Tabuk來避免所需資源已利用完的項目的分配問題。內存Vk在迭代最后被用來更新螞蟻所選出的移步的信息素。假設按照升序順序預定資源分配，也就是說，每只螞蟻首先將資源分配給項目1，然后分配給項目2，以此類推，直到獲得完整解。在每次分配中，會將不可行分配增加到那只螞蟻的禁忌表中。因此，約束方程式(3)-(5)得到滿足。這使得每只螞蟻都能產生可行解。

2.2 啟發信息

不同于真實螞蟻的盲目，人工螞蟻在不同項目中進行資源分配時，可以獲取一些啟發信息。適合移步V(i,j)的啟發信息表示為ηij。這種信息表示將數量j的資源分配給項目i的期望值，可采用啟發式方法進行計算。每個移步期望值都有幾種評估方法。由于所有螞蟻中的所有移步都要計算啟發信息，這樣可能會使算法效率極大地降低，因此應當提高計算效率。可以在螞蟻算法中考慮該要素的復雜性。從開始構造解到結束構造，在不考慮可行性問題的情況下，每只螞蟻都有可能將數量M的資源分配給所有項目，所以每只螞蟻在算法的每次迭代中應總共計算啟發信息M×N次。因此，對于整個算法而言，該要素的復雜性變成O(I×A×M×N)，其中，I表示迭代次數，A表示每次迭代的螞蟻數量。在較早實施螞蟻算法時，計算得出的啟發信息要么是先驗信息，要么是后驗信息。在實施第一種啟發信息時，首先計算啟發信息，剩下的在算法運行過程中保持不變；在實施第二種啟發信息時，該信息是動態的，主要由螞蟻的當前狀態決定。在計算啟發信息時，考慮這兩個方面，一個是計算效率；另一個是信息質量。先驗啟發信息的實施效率較高，但不能完全反映移步的期望值。相反地，在第二種實施方式中，雖然計算效率不令人滿意，但卻能獲得各個移步期望值的精確評估。本文試圖結合這些原理以開發出啟發信息的有效計算方法。這種方法選擇對第二種啟發信息進行計算，即后驗信息。但是，與其它一些類似方法相比，該方法的計算復雜性相對較低。這種公式考慮各個移步對目標函數值的局部貢獻量。p表示構建下的分配置換。由于要計算項目置換移步V(l,j)的期望值直到1，即p(1),p(2),…,p(l)已知，因此，可對移步V(l,j)的局部貢獻量進行以下計算：

移步V(l,j)對第一個目標函數的局部貢獻量為：

式中，ε表示小的正數，原因是在式(6)的分母中增加ε可以避免除0。移步V(l,j)對第二個目標函數的局部貢獻量為：

在O(L×N)中可獲得方程式(6)和(7)給定的啟發信息。可以采取多種方式結合多目標問題中的期望值以得到各個移步的總期望值，文中提出以下公式對V(l,j)的總期望值進行計算：

2.3 信息素更新規則

蟻群算法是依靠螞蟻個體間的相互協作。在每次迭代中，通過迭代地應用節點轉移規則，每只螞蟻從一個階段移動到下一個階段，直到進入匯聚節點并在此構建問題的候選解。在進行下一個迭代之前，根據信息素更新規則對各邊信息素數量進行更新，再根據求解單一目標函數問題中的原始蟻群算法，按照方程式(9)來更新各邊信息素數量：

其中，ρ∈(0 ,1)表示信息素的揮發率；τij(t)表示邊ij上信息素更新后的數量，即數量為j的資源分配給任務i；τij(t -1)表示這條邊上之后的信息素數量；Δτ(t -1)表示當前迭代過程中螞蟻在邊ij上所釋放的信息素數量。顯然，若螞蟻在當前迭代過程中沒有遍歷邊ij，則Δτ(t -1)=0。否則，須對Δτ(t -1)進行計算。現實世界中，絕大多數螞蟻會在經過的每條邊上釋放固定數量的信息素，但人工螞蟻所釋放的信息素則與所構造解的質量有關，在求解單一目標函數問題的原始蟻群算法中，采用以下公式計算Δτ(t -1)

其中，Xt表示螞蟻所構建的候選解。本文提出了另一種更加有效的計算方法。根據不可能存在一個所有目標函數的最優解這一事實，將所有帕累托解看作是多目標函數問題的最優解。假設所有非支配解具有相同、最好的質量，且忽略所有支配解，則可根據以下規則計算Δτ(t +1)

其中，δ表示小的正數，t表示當前迭代次數。式中，比較當前迭代中所構建的各個解與之前所有的非支配解，如果是非支配解，則所有邊上的信息素數量將增加t×δ。t乘以δ的原因是通過增加對應t的可行解集，發現非支配解更接近第一級（或最好的）非支配水平。在第N次迭代中的一些非支配解會受到第N+1次迭代中的一些解的支配。這條規則主要嘗試增加螞蟻的學習。

2.4 選擇概率

在螞蟻算法的所有實施過程中，通過結合兩個因素，即移步的期望值和所遍歷邊上的信息素數量，一只螞蟻可以選擇從當前狀態S1移動到下一個相鄰狀態S2。本文基于文獻所提出方法，在進行修改后，采用其對選擇概率進行計算。這里，采用并修改該方法的主要原因有兩個，一個是該方法只有一個控制參數α，用來映射信息素數量與各個移步期望值的相對重要性，比較簡單，而其它方法則每個因素需考慮一個參數；另一個原因是由于采用乘法而非求冪運算，該方法的計算效率較高。以下我們會解釋該方法的具體產生過程。根據文獻所提出的方法，螞蟻k按照以下概率選擇遍歷邊ij

應該方程式(11)可能會導致某個移步出現負概率。我們研究了兩種策略在處理負概率移步時所表現出來的性能。避免了負概率移步，只在正概率移步中進行選擇。如果沒有正概率移步，那么以同等機會選擇移步。在其它移步概率中增加最負的概率的絕對值，然后根據累計概率進行新概率的計算，從而使得所有概率都變成正概率。值得注意的是第一種策略中的搜索空間比第二種策略中的搜索空間更小。這與我們的實驗觀察相符，表明第二種策略比第一種策略更好。本文所提出方法的執行過程是：在應用方程式(12)對各個資源分配的概率進行計算之后，如果出現任何負概率，則采用第二種策略。

3 實例運算及其結果

3.1 數據來源及算法步驟

為了驗證本文方法的可行性及有效性，筆者采用國際上通用的測試實例來進行實例驗證工作。本文采用國際上通用的測試實例來驗證本文方法的可行性及有效性。該測試實例來自于參考文獻[3]，該實例主要是將10個員工分配給4個任務。本文章主要采用混合遺傳算法和蟻群優化算法來求解該問題。

蟻群優化算法的主要步驟如下：

初始化

⑴設置ρ、d、a和t0的參數值；A表示螞蟻數量；Max_Iter表示最大迭代次數

⑵初始化所有邊的信息素數量

⑶對于k=1到A

⑷對于i=1到任務

①選取所有不可能移步

②計算所有目標函數的所有可能移步

③按照第二種策略，計算所有可能移步的概率

④進行分配

⑤更新可利用資源

評估

⑸計算對應構造解的目標函數

⑹比較構造解與螞蟻k的其它解，確定其是否為帕累托解或非支配解

信息素更新

⑺比較所有螞蟻全部已標注“非支配”字樣的解，并選擇最終的非支配解

⑻更新信息素數量。

⑼若總迭代次數少于Max_Iter，則轉至步驟3，否則停止結束

3.2 實例運算結果

本文提出的螞蟻算法在Borland Delphi 7中加碼，采用型號1.8 GHz Centrino的計算機執行操作。該方法包含五個參數，A、ρ、α、d和t0。這些參數會對算法的性能產生影響。通過大量實驗研究，可以看出不同參數值對該螞蟻算法性能的影響。根據觀察，提出了以下實驗推導規則來設置參數值。

A=5×M，最大迭代次數(max_iteration)=N，α=0.5，δ=0.05/N，t0=0.01，ρ=0.3

表1和表2分別表示期望效率和期望成本。下面的表3和表4則分別采用混合遺傳算法和本文所提出的蟻群算法對帕累托解進行求解。實驗結果表明，本文所提出的蟻群算法比混合遺傳算法更適合求解多目標資源分配問題。

表1 期望成本Cij

表2 期望效率Eij

表3 采用混合遺傳算法求得的帕累托解

表4 采用蟻群優化算法求得的帕累托解

4 結束語

多目標資源配置問題就是將有限資源分配到不同事件來獲得預期目標。資源是指有限供應的人力、資產、原材料或其它任何可以完成目標的事物。資源配置問題的應用十分廣泛，包括產品分配、資源配置、項目預算、軟件測試、衛生資源配置等。

(1)提出了求解多目標資源配置問題的改進蟻群優化算法，該算法通過增加螞蟻在更新信息素規則中的學習和簡化概率計算來提高算法效率和有效性。

(2)在相同問題中比較了混合遺傳算法與該蟻群優化算法的求解結果，實驗結果表明蟻群算法會產生一半非支配解，其績效優于混合遺傳算法。

[1]CM Fonseca,PJ Fleming.An Overview of Evolutionary Algorithms in Multi-objective Optimization[J].Evolutionary Computation，1995，3(1).

[2]YC Hou,YH Chang.A New Efficient Encoding Mode of Genetic Algo?rithms for the Generalized Plant Allocation Problem[J].Journal of In?formation Science and Engineering,2004,20.

[3]Chi-Ming Lin,Mitsuo Gen.Multi-objective Resource Allocation Problem by Multistage Decision-based Hybrid Genetic Algorithm[J].Applied Mathematics and Computation,2007,187.

[4]M Dorigo.Optimization,learning,Natural Algorithms,Ph.D.Thesis,Dip.Elettronica e Informazione,Politecnico di Milano[Z].Italy,1992.

[5]Kalyanmoy Deb.Multi-Objective Genetic Algorithms:Problem Diffi?culties and Construction of Test Problems[R].Technical Report CI-49/98,Dortmund:Department of Computer Science/LS11,University of Dortmund,Germany,1998.

[6]DE Goldberg,J Richardson.Genetic Algorithms with Sharing for Mul?timodal Function Optimization[C].in:Proceedings of the First Interna?tional Conference on Genetic Algorithms and Their Applications,1987,(41).

F224

A

1002-6487（2013）14-0082-04

喻江平（1979-），男，湖南寧鄉人，碩士研究生，講師，研究方向：宏觀經濟學。

（責任編輯/易永生）