基于蟻群優(yōu)化的多目標(biāo)資源配置模型及應(yīng)用

喻江平

(燕山大學(xué)經(jīng)濟(jì)管理學(xué)院，河北秦皇島 0660044)

基于蟻群優(yōu)化的多目標(biāo)資源配置模型及應(yīng)用

喻江平

(燕山大學(xué)經(jīng)濟(jì)管理學(xué)院，河北秦皇島 0660044)

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

蟻群優(yōu)化；多目標(biāo)優(yōu)化；資源配置

0 引言

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

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

1 多目標(biāo)資源配置問題

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

⑴符號及參數(shù)定義：

i：表示任務(wù)指標(biāo)，i=1,2,…,N;

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

N：表示任務(wù)總數(shù)；

M：表示員工總數(shù)；

cij：表示分配到j(luò)個員工時任務(wù)i的成本；

eij：表示分配到j(luò)個員工時任務(wù)i的效益；

⑵決策變量：

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

2 求解多目標(biāo)資源配置問題的蟻群優(yōu)化算法

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

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

2.1 解的構(gòu)造

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

2.2 啟發(fā)信息

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

移步V(l,j)對第一個目標(biāo)函數(shù)的局部貢獻(xiàn)量為：

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

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

2.3 信息素更新規(guī)則

蟻群算法是依靠螞蟻個體間的相互協(xié)作。在每次迭代中，通過迭代地應(yīng)用節(jié)點(diǎn)轉(zhuǎn)移規(guī)則，每只螞蟻從一個階段移動到下一個階段，直到進(jìn)入?yún)R聚節(jié)點(diǎn)并在此構(gòu)建問題的候選解。在進(jìn)行下一個迭代之前，根據(jù)信息素更新規(guī)則對各邊信息素數(shù)量進(jìn)行更新，再根據(jù)求解單一目標(biāo)函數(shù)問題中的原始蟻群算法，按照方程式(9)來更新各邊信息素數(shù)量：

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

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

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

2.4 選擇概率

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

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

3 實(shí)例運(yùn)算及其結(jié)果

3.1 數(shù)據(jù)來源及算法步驟

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

蟻群優(yōu)化算法的主要步驟如下：

初始化

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

⑵初始化所有邊的信息素數(shù)量

⑶對于k=1到A

⑷對于i=1到任務(wù)

①選取所有不可能移步

②計算所有目標(biāo)函數(shù)的所有可能移步

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

④進(jìn)行分配

⑤更新可利用資源

評估

⑸計算對應(yīng)構(gòu)造解的目標(biāo)函數(shù)

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

信息素更新

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

⑻更新信息素數(shù)量。

⑼若總迭代次數(shù)少于Max_Iter，則轉(zhuǎn)至步驟3，否則停止結(jié)束

3.2 實(shí)例運(yùn)算結(jié)果

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

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

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

表1 期望成本Cij

表2 期望效率Eij

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

表4 采用蟻群優(yōu)化算法求得的帕累托解

4 結(jié)束語

多目標(biāo)資源配置問題就是將有限資源分配到不同事件來獲得預(yù)期目標(biāo)。資源是指有限供應(yīng)的人力、資產(chǎn)、原材料或其它任何可以完成目標(biāo)的事物。資源配置問題的應(yīng)用十分廣泛，包括產(chǎn)品分配、資源配置、項(xiàng)目預(yù)算、軟件測試、衛(wèi)生資源配置等。

(1)提出了求解多目標(biāo)資源配置問題的改進(jìn)蟻群優(yōu)化算法，該算法通過增加螞蟻在更新信息素規(guī)則中的學(xué)習(xí)和簡化概率計算來提高算法效率和有效性。

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

[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-），男，湖南寧鄉(xiāng)人，碩士研究生，講師，研究方向：宏觀經(jīng)濟(jì)學(xué)。

（責(zé)任編輯/易永生）