基于混合粒子群算法的任務分配策略

張 琰，包少彬，涂雙平，楊衛星

（1.南京熊貓漢達科技有限公司，江蘇 南京 210014；2.南疆軍區信息保障隊，新疆 喀什 844200；3.聯勤保障部隊駐湘某預備役旅，湖南 衡陽 421216）

0 引言

多智能體系統（Multi-Agent System，MAS）是由多智能體組成的有機集合，是智能體之間的協調與協作。多智能體系統中，各智能體資源和知識是有限的，處理能力也不相同，對不同類型任務也表現出不同的適應性，所以面向多智能體的任務分配策略問題直接影響到系統的執行效率和任務目標的完成質量，所以任務分配問題也越來越受到關注[1]。

任務分配問題的研究從20世紀70年代后期逐漸展開。1980年Smith和Davis率先提出合同網模型[2]，1981年首次探討了基于合同網的任務分配方法，對發現任務和分配任務做了定位，并討論了解決該問題的基本思想和實現該思想的合同網技術。由此引發對合同網的研究，文獻[3]在合同網模型中引入了多級協商理念，在合同網投標和評標決策過程中引入邊界成本計算，文獻[4]在合同網中引入熟人聯盟策略，文獻[5]中利用商業活動中的拍賣機制改進了合同網協議模型。1982年，Efe等人提出一種試探式的啟發式任務分配模型，該方法通過綜合和調整兩個階段試圖得到更合理的任務分配方案[6]。1988年Lo，V.M.提出一種改進的基于圖論的任務分配算法，該算法由迭代、歸納和貪心三個階段組成，算法終止時可獲得最優的分配方案[7]。1997年武漢大學何炎祥教授等人提出了基于遺傳算法和模擬退火算法的任務分配算法，借鑒此兩種算法的思想來解決任務分配的組合優化問題[8]。本文通過對MAS中任務分配特點的分析和研究，探討基于混合粒子群算法的任務分配優化策略。

1 問題的提出

基本策略是先對任務或者需求進行分析和分解，再對子任務進行分配，子任務簡單和較低的能力與資源要求使得原本無法解決的任務得以順利進行。子任務往往既有依賴性的務，也存在可并行的子任務，如圖1所示。

圖1 子任務并行與依賴示例圖

Rij表示任務j完成依賴于任務i輸出，為順序或依賴關系，任務1、4表現為該關系。任務1、2、8等任務間無依賴關系，屬獨立任務，為并行關系。

2 數學建模

2.1 問題描述

MAS中多目標問題可歸為規劃問題，可描述為：n個待完成任務T = {1，2，...，n}，需在MAS系統的m個智能體（Agent）A = {1，2，...，m}上處理完成。調度優化目標是n 個子任務在m個Agent上的運行或完成順序最優，以使整個MAS系統總體目標（含多個目標）達到最優。為滿足研究需要，做如下假設和約束條件：

⊙ 每個Agent上任務的完成順序相同。

⊙ 給定時間內一個Agent只能處理一個子任務。

⊙ 每個子任務只能由一個Agent完成。

⊙ 每個子任務在任意Agent上處理時間已知。

2.2 數學模型

為研究需要，定義一些符號和變量下：

（1）Ti：i=1，…，n。Ti第i個子任務，T可看作任務集合。

（2）Rij：Rij=，如Rij為1表示是任務Ti優先于任務Tj，意味著任務Tj的執行必須以子任務Ti的完成為前提，可表示為Ti＞Tj（1≤i≤n，1≤j≤n），否則為0。

（3）Sij：任務Ti在智能體Ai上的執行開銷。

（4）Wi：任務Ti等待處理的時間。

（5）Cij：任 務Ti所屬的Agent與 任 務Tj所屬的Agent之間的通信開銷。

（6）Ai：i = 1，…，m。m表示Agent的總數。

（7）Dij：Dij= ，如果Dij為1，表示任務Ti分配給智能體Aj處理，否則Dij為0。

從以上定義和說明看出Ti和Ai可看作數組元素，Rij，Sij，Cij和Dij可看作矩陣中元素，所以把T和A看作數組，分別是任務集合和智能體集合，P，S，C和D分別看作矩陣，R和C是n×n矩陣，S和D是m×n矩陣。

為優化方便設計目標函數如下：

（1）執行開銷目標函數：

（2）通信開銷目標函數：

式中，如果k=ι，則Ck，ι=0。

（3）任務等待開銷目標函數：

（4）任務完成總開銷目標函數：

約束條件：

公式（4）由公式（1）和（2）組合而成，選公式（1）和（2）作為本文兩個目標函數。可見把對任務分配的優化轉變為對公式（4）的函數優化，Cost 值越小表明總開銷越小，系統效率愈高。

3 算法設計與描述

3.1 基本的粒子群算法

基本粒子群算法中，粒子根據如下公式更新速度和新位置：

pbest（i）指個體極值，是粒子本身目前所找的最優解；gbest（i）指全局極值，是整個種群目前找的最優解。v（i）當前粒子的速度，x（i）當前粒子的位置，w慣性權重。r1和r2介于（0，1）之間的隨機數。c1和c2學習因子，通常c1=c2=2。

公式（5）（粒子速度的更新公式）由三部分構成：代表粒子上一次的速度v（i）影響；代表當前粒子個體最優值pbest（i）對粒子更新速度的引導；代表當前種群全局最優值gbest（i）對粒子更新速度的引導。

3.2 改進方案

（1）基本的粒子群算法中，隨著迭代次數增加，粒子更新速度越小，逐漸集中，很有可能造成局部搜索。為了一定程度上克服，參考文獻[9]作出不同改進，改進公式（5）：

式中，ve代表擴展速度；λ是一個決定ve是否有效的系數，它取值為0或1，為1時ve有效，為0則無效，它以一定的概率β 取值為1。（β一般情況下值很小）。

（2）引入遺傳算法中的交叉操作[10][11]。為了較快的向Pareto最優解集收斂，一定概率的選取精英庫中的粒子a和粒子b做交叉操作得到粒子c，這樣使得優秀粒子的優秀基因組合以可能獲得更優的粒子，如果粒子c支配了精英庫中的某些或某個粒子，則刪除被支配粒子，加入新粒子c；如果互不支配，則加入精英庫，如果精英庫已滿，則采用小生境策略更新精英庫；如果粒子c被支配，則放棄該粒子。

本文引入PMX交叉算子作為更新方式，實現過程如下：

①已知兩個父代粒子P 1和P 2（10個任務，5個智能體），從基因編碼中隨機取兩個交叉位置點進行交叉，假定選中2，5。

父代粒子P1

父代粒子P2

②交換交叉位置點之間的基因得到兩個新解C1和C2，即兩個子代粒子。

子代粒子C1：

子代粒子C2：

（3）遺傳算法中的變異操作[10][11]。以一定概率δ取粒子群中的小部分粒子，進行重新初始化操作來完成變異，能夠一定程度上避免陷入局部極值，隨著迭代次數的增加δ值逐漸變小至0。

（4）精英策略。為克服優化過程中由隨機因素而導致優質解丟失問題引入了精英策略。

（5）擁擠策略。為每一個粒子從精英庫中選定全局極值gbest 時，采用擁擠策略。

3.3 算法流程描述

圖2 多目標粒子群算法流程圖

算法的基本流程：

①初始化粒子群。包括粒子群P和精英庫E得規模，并初始化粒子初始位置和初始速度； 計算粒子群P中每個粒子的目標向量值。

②根據粒子的目標向量值，選取其中的Pareto非支配解放入精英庫。

③為每個粒子初始最優個體位置pbest，即粒子的初始化位置。

④采用擁擠策略從精英庫中隨機為每一個粒子選擇全局極值gbest 。

⑤采用三種方式更新粒子。采用公式3.7和3.8 更新粒子位置和速度；引入交叉操作，以一定概率選取粒子群中的粒子，隨機從精英庫中選取一個粒子，對兩個粒子作交叉操作，獲得子代粒子并替代父代P中的粒子；引入變異操作思想，從粒子群P中隨機的以較小的概率選取粒子，對其進行重新初始化，已完成變異操作，在迭代后期，不再進行變異操作。

⑥約束粒子的搜索空間。如果粒子飛出了某個決策變量的界限，則粒子取該邊界值，并改變速度方向。

⑦計算粒子群P中的每個粒子的目標向量。比較新粒子的位置與其自身最優位置pbest，如果新解支配了pbest，則更新pbest為當前位置； 如果pbest支配了當前粒子位置，則保持原來的pbest；如果當前位置與pbest互不支配，則隨機選擇其中一個作為自身的最優位置。

⑧在粒子群P中選擇Pareto最優解與gbest 比較，如果存在解與gbest互不支配，或支配了gbest，則把該粒子放入精英庫，然在精英庫中再選擇Pareto最優解留在精英庫中，支配解則再次放入粒子群P中，如果來精英庫已滿，則采用擁擠策略刪減精英庫中的粒子。

⑨如果達到終止條件，則停止搜索，否則，跳轉到④。

4 測試和分析

設定任務數N=20，智能體數M=10，則可能的分配策略有2010種，有使用智能算法的必要。隨機初始化執行開銷矩陣Execute，通信開銷矩陣Comm，任務關系矩陣Rel，初始化粒子群pop，粒子數規模sizepop=30，精英庫的規模為sizepop/3，迭代次數i retat ions=500，粒子的最大更新速度Vmax=M/4，最小更新速度Vmin=-M/4，粒子各個維度的邊界相同，最大邊界popmax=M，最小邊界popmin=1。測試數據隨機生成。

由圖3可以明顯看出粒子的初始化具有隨機性，符合仿真測試的要求。

圖3 初始化粒子群的適應度值分布圖

圖4 初始粒子群的精英粒子目標函數值分布

圖5 優化后的精英粒子目標函數值分布圖

可以明顯看出，多目標混合粒子群算法進行優化后的精英粒子的目標函數值分布均勻，質量較高。

從收斂效果看，改進后的多目標粒子群算法優化后的結果優于標準的多目標粒子群算法優化后所得到的結果。未改進的粒子群算法迭代結束后得到的粒子群的目標函數值的分布有些凌亂，改進后的多目標粒子群算法所得到的粒子群的目標函數值的分布則明顯比標準的粒子群算法均勻，表明了改進后算法的有效性和優越性。

圖6 標準多目標粒子群算法粒子目標函數值分布圖

5 結束語

基于混合粒子群算法的任務分配策略在針對任務分配上擁有優于單獨使用傳統任務分配算法的巨大潛力。首先，粒子群算法本身具有特點使得在優化過程中可以較快的收斂；其次，對原公式（5）的改進，一定程度上避免了陷入局部搜索；最后，引入精英策略和交叉操作，在某種程度上保持了優質粒子，并一定程度上克服了由于隨機性可能帶來的優質解的丟失問題，且沒有減慢算法的收斂速度。

圖7 多目標混合粒子群算法優化后的粒子目標函數值分布圖