喻江平

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

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

喻江平

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

⑵決策變量：

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

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

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

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

2.1 解的構(gòu)造

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

2.2 啟發(fā)信息

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

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

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

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

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

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

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

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

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

2.4 選擇概率

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

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

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

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

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

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

初始化

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

⑵初始化所有邊的信息素?cái)?shù)量

⑶對(duì)于k=1到A

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

①選取所有不可能移步

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

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

④進(jìn)行分配

⑤更新可利用資源

評(píng)估

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

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

信息素更新

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

⑻更新信息素?cái)?shù)量。

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

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

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

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

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

表1 期望成本Cij

表2 期望效率Eij

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

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

4 結(jié)束語(yǔ)

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

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

(2)在相同問(wèn)題中比較了混合遺傳算法與該蟻群優(yōu)化算法的求解結(jié)果，實(shí)驗(yàn)結(jié)果表明蟻群算法會(huì)產(chǎn)生一半非支配解，其績(jī)效優(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é)任編輯/易永生）