張 翔，朱范炳

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

0 引言

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

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

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

1 指派問(wèn)題描述與建模

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

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

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

2 人工蜂群算法原理

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

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

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

接下來(lái)，對(duì)各研究階段擬展開(kāi)闡釋分述如下。

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

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

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

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

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

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

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

3.1 食物源位置的編碼

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

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

3.2 食物源位置更新方式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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