基于改進(jìn)人工蜂群算法的機(jī)器人任務(wù)最優(yōu)指派

張 翔，朱范炳

（信陽學(xué)院 大數(shù)據(jù)與人工智能學(xué)院，河南 信陽 464000）

0 引言

任務(wù)分配問題也稱為指派問題，是一類典型的0-1 型規(guī)劃問題，屬于組合優(yōu)化問題中的NPComplete 問題，并在諸多領(lǐng)域中有很強(qiáng)的適用性。生產(chǎn)和生活中的很多實(shí)際問題，如工作分配、車輛調(diào)度、航班安排、車間設(shè)備分布和生產(chǎn)安排等都屬于指派問題的范疇。移動救援機(jī)器人的任務(wù)分配是以取得最大時效為目標(biāo)，也可運(yùn)用指派問題模型來進(jìn)行求解。求解指派問題最有效的標(biāo)準(zhǔn)計(jì)算方法是庫恩提出的匈牙利算法，但是匈牙利算法的適用條件比較嚴(yán)格，一些場景下的任務(wù)分配研究可能會導(dǎo)致算法不收斂；且不利于用計(jì)算機(jī)來做編程處理。因此，研究者提出了求解指派問題的改進(jìn)算法。近年來，自從仿生計(jì)算和群體智能問世以來，許多研究者用智能計(jì)算成功求解了指派問題。文獻(xiàn)［3］提出改進(jìn)粒子群優(yōu)化算法求解任務(wù)指派問題。文獻(xiàn)［4-5］提出用蟻群算法和改進(jìn)的蟻群算法求解指派問題。文獻(xiàn)［6］提出最優(yōu)指派問題的DNA 算法。文獻(xiàn)［7-8］在用蟻群和蜂群算法求解離散解問題上做了一些指導(dǎo)性工作。

人工蜂群算法（Artificial Bee Colony，ABC）由土耳其學(xué)者Karaboga 于2005 年提出，是一種模擬自然界蜜蜂采蜜、尋找優(yōu)良蜜源行為的元啟發(fā)式算法，能夠有效求解連續(xù)數(shù)值優(yōu)化問題。Karaboga 等人的研究指出，相比遺傳算法、差分進(jìn)化算法及粒子群算法，ABC 算法在數(shù)值函數(shù)尋優(yōu)中有更出色的表現(xiàn)。也有研究表明，ABC 算法具有設(shè)置參數(shù)少、操作簡單、工程通用性強(qiáng)的優(yōu)點(diǎn)，隨著對算法討論的深入，現(xiàn)在已將ABC 算法運(yùn)用到組合優(yōu)化問題中。

考慮到ABC 算法的優(yōu)點(diǎn)，本文采用離散編碼方法對可行解進(jìn)行編碼，提出一種改進(jìn)的人工蜂群算法（Improved Artificial Bee Colony，IABC），用來求解移動機(jī)器人救援任務(wù)的指派問題。通過對指派問題的建模，運(yùn)用IABC 算法進(jìn)行求解，并與其它方法加以比較，最后得出結(jié)論。

1 指派問題描述與建模

典型的指派問題是把項(xiàng)任務(wù)分配給個執(zhí)行者來完成。由于任務(wù)性質(zhì)和每個執(zhí)行者的實(shí)操能力各有不同，面對不同任務(wù)所花費(fèi)的成本和取得的收益c也有所不同，一般要求分配方案實(shí)現(xiàn)最小的成本和最大的收益。本文將個搜救任務(wù)區(qū)域指派給個移動機(jī)器人，要求一個機(jī)器人只搜索一個區(qū)域，一個搜救區(qū)域只由一個機(jī)器人搜索，這是一類標(biāo)準(zhǔn)的指派問題。

對救援問題，最大的時效性是首要考慮的目標(biāo)，f表示指派問題的成本函數(shù)，一般要求取得最小成本，因此可以建立靜態(tài)單目標(biāo)的救援機(jī)器人任務(wù)指派模型，推導(dǎo)得出的數(shù)學(xué)公式為：

其中，x＝1 表示安排第個機(jī)器人搜索第個區(qū)域； x＝0 表示不安排第個機(jī)器人搜索第個區(qū)域；c為指派問題的成本系數(shù)矩陣。

2 人工蜂群算法原理

ABC 算法的基本要素包括蜂群、蜜源和蜜源適應(yīng)度，將蜂群分為采蜜蜂、觀察蜂和偵察蜂三種。ABC 算法的關(guān)鍵問題是適應(yīng)度函數(shù)設(shè)計(jì)和解搜索策略的選擇，一般通過較大的適應(yīng)度值引導(dǎo)算法向全局最優(yōu)進(jìn)化，適應(yīng)度大的食物源對應(yīng)解的質(zhì)量好。對于最大值優(yōu)化問題，可用待優(yōu)化問題的目標(biāo)函數(shù)代表適應(yīng)度函數(shù)；對于最小值優(yōu)化問題，適應(yīng)度函數(shù)的數(shù)學(xué)定義式可寫為：

ABC 算法的初始化階段，設(shè)置最大迭代次數(shù)蜂群中蜜蜂數(shù)量的二分之一和食物源數(shù)量相等，且所有蜜蜂都是偵察蜂模式。研究中，隨機(jī)產(chǎn)生個解并計(jì)算其適應(yīng)度，將適應(yīng)度按由大到小的順序排列，前一半作為采蜜蜂，后一半作為觀察蜂和偵察蜂。此處需要用到的公式為：

對于任一解x的任一分量x（1，2，…，）都進(jìn)行初始化， x代表可行解空間分量的最小值，x代表可行解空間分量的最大值。

接下來，對各研究階段擬展開闡釋分述如下。

（1）采蜜蜂搜索階段：采蜜蜂在初始階段的蜜源附近，通過式（4）搜索產(chǎn)生一個新解，作為候選蜜源進(jìn)行開采：

其中，∈｛1，2，…，｝，≠表示在個蜜源中隨機(jī)選取一個不同于x的蜜源。計(jì)算新解的適應(yīng)度fit并進(jìn)行適應(yīng)度大小評價，采用貪心算法在v和x中選擇。

（2）觀察蜂跟隨階段：所有采蜜蜂完成搜索后，采蜜蜂會把解的信息及適應(yīng)度分享給觀察蜂。觀察蜂通過選擇概率P決定每只采蜜蜂被跟隨的概率，對此可表示為：

若新解的適應(yīng)度比之前的好，觀察蜂會將其用新解更新；反之，觀察蜂會將其保留，同時解的迭代搜索次數(shù)加1。

（3）偵察蜂階段：如果某一食物源在被搜索可重復(fù)開采次數(shù)后仍未做更新，相應(yīng)的采蜜蜂和觀察蜂則會放棄該蜜源，轉(zhuǎn)換為偵察蜂模式，按式（3）隨機(jī)搜索，尋找一個新的蜜源代替被舍棄的蜜源。接下來將返回到采蜜蜂的搜索階段，3 種蜜蜂依次工作，重復(fù)循環(huán)搜索，最終找到待優(yōu)化問題的最優(yōu)解。

3 求解指派問題的改進(jìn)人工蜂群算法

本文提出的改進(jìn)人工蜂群算法是在標(biāo)準(zhǔn)人工蜂群算法原理的基礎(chǔ)上，在生成食物源時采用離散數(shù)據(jù)編碼的形式，提出了一種列狀態(tài)移動交換的方法，保證了生成的候選食物源對應(yīng)解的可行性。

3.1 食物源位置的編碼

ABC 算法中每一個食物源代表優(yōu)化問題的一個可行解。本文針對移動救援機(jī)器人任務(wù)指派問題解的特點(diǎn)進(jìn)行編碼，設(shè)計(jì)離散的IABC 算法。設(shè)有個待救援區(qū)域需要分配給個移動機(jī)器人去搜索，任一食物源的位置x是一個的矩陣，代表一種指派方案，排序形式如式（7）所示：

矩陣x的行標(biāo)表示機(jī)器人編號，列標(biāo)表示救援區(qū)域編號； x是一個經(jīng)過初等變換的單位對角矩陣，其特征是任意一行和任意一列只有一個元素“1”，其余位置均為“0”。x＝1 表示指派第個機(jī)器人去搜索第個區(qū)域。

3.2 食物源位置更新方式

ABC 算法在優(yōu)化連續(xù)型數(shù)值函數(shù)時，采蜜蜂和觀察蜂都是按照公式（4）來更新食物源位置。本文中IABC 算法食物源x是一個特殊矩陣，為了滿足指派問題解決方案的要求，矩陣元素只包含0 和1。為了保證更新解的離散性，以及在指派問題模型上的可行性，采用基于矩陣列交換的列狀態(tài)轉(zhuǎn)移方法。以6 個救援區(qū)域搜索任務(wù)為例來說明生成候選解的列狀態(tài)轉(zhuǎn)移方法，如式（8）所示：

其中，數(shù)字是任務(wù)編號的排序，即可行解矩陣列的排序，x表示當(dāng)前食物源， v表示更新得到的候選解。隨機(jī)選擇一個位置的列，令其與不同位置的列進(jìn)行轉(zhuǎn)移。每一次的列狀態(tài)轉(zhuǎn)移都能得到新的可行解，二次轉(zhuǎn)移是指在一次轉(zhuǎn)移的基礎(chǔ)上，按照一次轉(zhuǎn)移的方式生成新的可行解，二次轉(zhuǎn)移能夠增加食物源的多樣性。對于高維指派問題，列狀態(tài)轉(zhuǎn)移更新可行解時可以增加隨機(jī)選擇列位置的個數(shù)，每個位置的狀態(tài)轉(zhuǎn)移方法和單個列位置交換方法相同。

3.3 適應(yīng)度函數(shù)設(shè)計(jì)

ABC 算法中用適應(yīng)度值評價食物源質(zhì)量，即對應(yīng)解的優(yōu)劣；一般根據(jù)較大適應(yīng)度原則引導(dǎo)算法收斂。在救援機(jī)器人任務(wù)指派問題中，要求一個指派方案完成搜索任務(wù)的時效最高，即花費(fèi)的時間成本目標(biāo)函數(shù)f值最小。因此，設(shè)計(jì)IABC 求解救援機(jī)器人任務(wù)指派問題的適應(yīng)度函數(shù)具體如下：

4 實(shí)驗(yàn)及結(jié)果分析

本文采用10 維和22 維任務(wù)的成本矩陣模擬救援機(jī)器人搜索任務(wù)分配的時效成本矩陣，進(jìn)行IABC 算法驗(yàn)證。

4.1 實(shí)驗(yàn)一

實(shí)驗(yàn)一選用10 維的指派問題，成本矩陣的數(shù)學(xué)表達(dá)式為：

這是一個匈牙利算法收斂的矩陣。本實(shí)驗(yàn)中分別用匈牙利算法和IABC 算法對10 維指派問題求解，IABC 算法參數(shù)設(shè)置如下：蜂群數(shù)量40，食物源數(shù)量20，最大迭代次數(shù)50。運(yùn)行IABC 算法30 次求取平均值并記錄時間，迭代尋優(yōu)收斂過程如圖1 所示，數(shù)據(jù)結(jié)果見表1。

圖1 實(shí)驗(yàn)一中IABC 算法迭代收斂過程Fig.1 IABC algorithm iterative convergence process in the first test

表1 實(shí)驗(yàn)一中3 種算法所得結(jié)果數(shù)據(jù)對比Tab.1 Comparison of the results obtained by the three algorithms in the first test

4.2 實(shí)驗(yàn)二

實(shí)驗(yàn)二選用22 維的指派問題，成本矩陣的數(shù)學(xué)表達(dá)式為：

這個矩陣對匈牙利算法不收斂。本實(shí)驗(yàn)中用IABC 算法對22 維指派問題求解，IABC 算法參數(shù)設(shè)置如下：蜂群數(shù)量60，食物源數(shù)量30，最大迭代次數(shù)100。運(yùn)行IABC 算法30 次求取平均值并記錄時間，迭代尋優(yōu)收斂過程如圖2 所示，數(shù)據(jù)結(jié)果記錄見表2。

圖2 實(shí)驗(yàn)二中IABC 算法迭代收斂過程Fig.2 IABC algorithm iterative convergence process in the second test

表2 實(shí)驗(yàn)二中3 種算法所得結(jié)果數(shù)據(jù)對比Tab.2 Comparison of the results obtained by the three algorithmsin the second test

5 結(jié)束語

匈牙利算法是任務(wù)指派問題的標(biāo)準(zhǔn)算法，但該算法對大規(guī)模指派問題不收斂；蟻群算法也是較早應(yīng)用在任務(wù)指派問題中的群體智能算法，但該算法設(shè)置參數(shù)多、計(jì)算量大。本文以救援機(jī)器人搜索區(qū)域分配問題為背景，建立以時效性能為目標(biāo)的指派數(shù)學(xué)模型；提出改進(jìn)的人工蜂群算法（IABC）求解該模型；采用2 個不同規(guī)模的指派算例模擬救援機(jī)器人任務(wù)指派問題。仿真結(jié)果表明：IABC 算法在求解指派問題時，設(shè)置參數(shù)少，通用性強(qiáng)，收斂速度快，算法穩(wěn)定性好，是一種優(yōu)秀的算法。