基于遷移學(xué)習(xí)的多任務(wù)分配算法

王夢嬌，尹 翔，黃寧馨

揚州大學(xué) 信息工程學(xué)院，江蘇 揚州 225009

1 引言

隨著現(xiàn)代社會與科學(xué)技術(shù)的飛速發(fā)展，人們面臨的問題變得日趨復(fù)雜。分布式系統(tǒng)成為解決復(fù)雜問題的有效手段和方法。通過將復(fù)雜任務(wù)分解為相對簡單的子任務(wù)，再將子任務(wù)分配給各智能體（agent），可以有效提高任務(wù)求解效率[1-2]。因此，任務(wù)分配問題已經(jīng)引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。

任務(wù)分配的目的是找到一種合理的子任務(wù)分配方式，使得子任務(wù)能夠被高效、合理地分配給各智能體。已有眾多學(xué)者對該問題展開深入研究。Smith 等人[3]提出了合同網(wǎng)協(xié)議，通過在多個智能體間訂立合同，以協(xié)商的方式實現(xiàn)任務(wù)的分配。以合同網(wǎng)協(xié)議為基礎(chǔ)，劉海龍等人[4]基于集合覆蓋理論提出了一種在合同網(wǎng)框架下解決子任務(wù)分配的嚴(yán)格啟發(fā)式搜索算法，并分析了算法的收斂性及時間復(fù)雜度。Cano 等人[5]研究了如何將軟件分配給硬件處理器的問題，將該問題建模為一個多目標(biāo)優(yōu)化問題，并給出了一個基于約束優(yōu)化的算法。

近年來，隨著人工智能技術(shù)的飛速發(fā)展，已有學(xué)者將強化學(xué)習(xí)的相關(guān)理論和方法用于求解任務(wù)分配問題。Liu 等人[6]給出了一種基于強化學(xué)習(xí)的云資源分配機制，該策略通過在線學(xué)習(xí)實現(xiàn)了云資源的自動管理和分配，提高了系統(tǒng)效益。廖曉閩等人[7]針對移動通信中的蜂窩網(wǎng)資源分配多目標(biāo)優(yōu)化問題，提出了一種基于深度強化學(xué)習(xí)的網(wǎng)絡(luò)資源分配算法。這類方法將任務(wù)分配問題建模為一個馬爾科夫決策過程，通過最大化回報函數(shù)來獲得最優(yōu)策略。

現(xiàn)有的大部分研究都是將任務(wù)分配問題建模為多目標(biāo)優(yōu)化問題，通過求解最優(yōu)解來獲得最優(yōu)分配策略。然而，作為一類NP-complete問題，計算最優(yōu)解將耗費大量資源，在問題規(guī)模較大時，甚至是不可能的。另一方面，對一個系統(tǒng)而言，其所面對的任務(wù)通常具有一定的相似性，如果能夠利用這種相似性來指導(dǎo)任務(wù)的分配，可以提高新任務(wù)分配的效率，獲得更多收益。

遷移學(xué)習(xí)作為機器學(xué)習(xí)的一個重要分支，已在任務(wù)規(guī)劃[8-9]、圖像處理[10-11]以及眾包[12-13]等領(lǐng)域有廣泛應(yīng)用。遷移學(xué)習(xí)的核心思想是找到源任務(wù)與目標(biāo)任務(wù)之間的相似度，從而將一個或多個與目標(biāo)任務(wù)相似的源任務(wù)的知識或策略進行遷移[14-15]。可見，通過遷移學(xué)習(xí)，可以使agent 在面對新任務(wù)時充分利用已有的經(jīng)驗和知識，在一個較高的起點上對問題進行求解，提高任務(wù)求解的效率。

基于此，本文討論了多智能體環(huán)境下的任務(wù)分配問題。所提出的算法利用遷移學(xué)習(xí)找到與目標(biāo)任務(wù)最匹配的源任務(wù)，將其任務(wù)分配方案遷移到目標(biāo)任務(wù)中，加速任務(wù)的分配。同時，在智能體尋找最優(yōu)路徑的過程中利用遷移學(xué)習(xí)，通過歷史經(jīng)驗加速學(xué)習(xí)過程。實驗表明，相比于傳統(tǒng)的強化學(xué)習(xí)方法，本文算法運行時間大幅度降低且性能明顯提升。

2 問題描述

本文算法解決的是在一個目標(biāo)任務(wù)中，有多個子任務(wù)需要由多個智能體來完成的問題。本文算法將遷移學(xué)習(xí)的思想引入多任務(wù)分配的問題中，目的是為了在保證任務(wù)分配質(zhì)量的情況下，提高任務(wù)分配的效率。如圖1所示，在本文的模型中，有多個智能體（數(shù)字表示）和多個子任務(wù)（Δ 表示），中央控制器將子任務(wù)分配給智能體，智能體需要找到一條到子任務(wù)位置的最優(yōu)路徑。智能體的狀態(tài)集合用S表示，包含智能體能到達的任意位置。智能體的動作集合用A表示，包含上、下、左、右四個動作。每次智能體只能移動一步。在這里，子任務(wù)的坐標(biāo)或智能體的狀態(tài)由離散坐標(biāo)表示，黑色實心部分表示障礙，智能體無法到達或穿過。

圖1 多智能體完成多子任務(wù)

下面是對本文所解決的問題的形式化描述：假設(shè)系統(tǒng)中有一定數(shù)量的智能體，其集合記為Agent，即Agent=，其中，n表示智能體的數(shù)量，源任務(wù)的子任務(wù)集合為SourceTask，即有其中，m表示源任務(wù)中子任務(wù)的數(shù)量，目標(biāo)任務(wù)的子任務(wù)集合為TargetTask，即有其中，g表示目標(biāo)任務(wù)子任務(wù)的數(shù)量。智能體數(shù)量與子任務(wù)數(shù)量的關(guān)系是n≥m，且一個智能體最多只能完成一項子任務(wù)。算法的目標(biāo)是最大化平均帶折扣回報，即，其中，k表示片段數(shù)，H表示一個片段結(jié)束所用的步數(shù)或所允許的最大步數(shù)，γ表示折扣因子，ri,h表示第i個片段的第h步得到的立即回報。

3 算法設(shè)計

本章闡述本文提出算法的基本思想，算法中遷移的知識是策略。首先，將一定數(shù)量的源任務(wù)對應(yīng)的策略構(gòu)成一個策略庫表示策略庫中策略的數(shù)量，即源任務(wù)的數(shù)量；接著，在解決目標(biāo)任務(wù)時，中央控制器要根據(jù)相似性度量找到與目標(biāo)任務(wù)相似程度最高的源任務(wù)，將該源任務(wù)的智能體分配策略遷移到目標(biāo)任務(wù)中；得到目標(biāo)任務(wù)分配策略之后智能體將該源子任務(wù)的知識進行遷移來學(xué)習(xí)一條到達目標(biāo)子任務(wù)狀態(tài)的最優(yōu)路徑，提高了學(xué)習(xí)效率并減少損耗。

3.1 算法介紹

本文算法分為兩步：首先找到與目標(biāo)任務(wù)最相近的源任務(wù)，將源任務(wù)的任務(wù)分配方式遷移到目標(biāo)任務(wù)中，再使用遷移學(xué)習(xí)來學(xué)習(xí)并獲得各智能體到其對應(yīng)的目標(biāo)狀態(tài)的最優(yōu)策略。具體算法如下：

首先，讓智能體學(xué)習(xí)一組具有代表性的、可以充分表示各種類型任務(wù)的源任務(wù)。源任務(wù)的作用是與目標(biāo)任務(wù)相匹配，進行子任務(wù)分配策略的遷移。源任務(wù)庫的構(gòu)造方法：計算當(dāng)前源任務(wù)與源任務(wù)庫中已有的任務(wù)的相似性，若相似性較差，將當(dāng)前源任務(wù)加入源任務(wù)庫中，并將已學(xué)習(xí)的策略存入策略庫StrategyLibrary中。當(dāng)目標(biāo)任務(wù)到來時，中央控制器要分別計算目標(biāo)任務(wù)中各個子任務(wù)與源任務(wù)中的子任務(wù)的考慮障礙的最小哈夫曼距離和，距離和最小的源任務(wù)判定為與目標(biāo)任務(wù)最相似的源任務(wù)，記為most_matched。將策略庫中該源任務(wù)的策略πmost_matched（即子任務(wù)的分配策略）遷移到目標(biāo)任務(wù)中，其中，距離和的計算還考慮到了目標(biāo)子任務(wù)與源子任務(wù)和障礙的相對位置。最后，中央控制器根據(jù)目標(biāo)任務(wù)中子任務(wù)的坐標(biāo)和對應(yīng)智能體之前處理過的子任務(wù)的坐標(biāo)之間的哈夫曼距離判定源子任務(wù)與目標(biāo)子任務(wù)之間的相似度，將相似度最高的源子任務(wù)的策略遷移到目標(biāo)子任務(wù)中。算法的整體思路如算法1所示。

算法1 帶遷移的多智能體多任務(wù)分配算法

輸入：

1.源任務(wù)庫對應(yīng)的策略庫StrategyLibrary

2.一組目標(biāo)任務(wù)的集合Ω

初始化：

forj=1 togdo

1.分別計算目標(biāo)任務(wù)中的子任務(wù)與各源任務(wù)的子任務(wù)的（考慮障礙的）距離，再求和得到distance

2.most_matched=arg minsource_taskdistance即選取距離和最短的源任務(wù)作為被遷移的任務(wù)

3.πtarget←πmost_matched將選定的源任務(wù)對應(yīng)的策略遷移給目標(biāo)任務(wù)的智能體

4.利用遷移學(xué)習(xí)算法找到智能體到其對應(yīng)子任務(wù)的目標(biāo)位置的最優(yōu)路徑

end for

算法2的重點是如何比較任務(wù)之間的相似度，通過子任務(wù)之間的相似性度量找到與目標(biāo)任務(wù)最相似的源任務(wù)。若將與目標(biāo)任務(wù)相似度不高的源任務(wù)的策略進行遷移，則很有可能會產(chǎn)生負(fù)遷移，即進行遷移之后的策略反而比從頭學(xué)習(xí)策略效果更差。為了減少負(fù)遷移的產(chǎn)生，計算距離的公式如（1）所示，其中，distanceij表示目標(biāo)任務(wù)中第j個子任務(wù)與源任務(wù)中第i個子任務(wù)之間的距離。

如圖2所示，當(dāng)兩個子任務(wù)之間存在障礙，則distanceij會被賦予很大的值，表示源任務(wù)中的子任務(wù)i與目標(biāo)任務(wù)中的子任務(wù)j相似度不高。若只考慮哈夫曼距離，那么這兩個子任務(wù)的哈夫曼距離是比較小的，但實際上因為智能體不能穿過障礙，故要繞開障礙，說明這兩個任務(wù)的相似度不高。比較源任務(wù)與目標(biāo)任務(wù)的相似度的偽代碼見算法2。

圖2 任務(wù)相似性度量

算法2 計算源任務(wù)與目標(biāo)任務(wù)的相似度

找到包含所有best_agent的源任務(wù)

目標(biāo)任務(wù)中的各個子任務(wù)分配好之后，進入算法的第二階段，即利用遷移學(xué)習(xí)計算各智能體到目標(biāo)子任務(wù)的最優(yōu)路徑。這里，各智能體之前處理過的源子任務(wù)與其對應(yīng)的目標(biāo)子任務(wù)的相似度的計算方法與算法2 類似，不做贅述。算法3表示的是利用遷移學(xué)習(xí)找到一條從智能體到目標(biāo)子任務(wù)的最優(yōu)路徑的偽代碼。其中，Episodes表示尋找最優(yōu)路徑的最大片段數(shù)。

在算法3 中，源任務(wù)的子任務(wù)的策略被保存在pai中。為了平衡“利用”和“探索”，使用了pt和p_t兩個變量進行控制。pt表示片段的第一步“利用”歷史經(jīng)驗的概率，其隨片段數(shù)的增加不斷減小，即隨著片段數(shù)的增加，智能體越少地“利用”歷史經(jīng)驗，也就是智能體更多地“利用”自身學(xué)習(xí)的知識。原因在于使用遷移學(xué)習(xí)的目的是在前期給智能體一個較好的指導(dǎo)，但由于源任務(wù)和目標(biāo)任務(wù)是不完全相同的，故不能一直“利用”源任務(wù)中的策略。pt的更新公式如式（2），分母中的參數(shù)500是針對本實驗嘗試不同參數(shù)值之后效果最好的參數(shù)值。不同參數(shù)值的性能比較見實驗部分。

算法3 學(xué)習(xí)智能體到目標(biāo)子任務(wù)的最優(yōu)路徑

輸入：

與目標(biāo)子任務(wù)最相似的源子任務(wù)most_match_source

初始化：

1.每個片段的第一步利用歷史經(jīng)驗的概率p_t=1

2.帶折扣的獎勵之和sum_rewards_transfer=0

在一個片段中，“利用”歷史經(jīng)驗的概率p_t也是隨步數(shù)的增長下降的。該變量的意義在于在一個片段中“利用”歷史經(jīng)驗的頻率逐漸降低。兩個變量共同作用下，使得智能體隨著片段數(shù)、步數(shù)的逐漸增加，“利用”歷史經(jīng)驗的頻率逐漸下降。

3.2 算法分析

本節(jié)對本文提出的算法與基于Q 學(xué)習(xí)的基本搜索算法從時間復(fù)雜度方面進行比較和分析。

假設(shè)源任務(wù)有m個，每個源任務(wù)中平均有s個子任務(wù)，目標(biāo)任務(wù)中有g(shù)個子任務(wù)，系統(tǒng)中有n個智能體，k表示學(xué)習(xí)最優(yōu)路徑過程中的迭代次數(shù)。那么在帶遷移學(xué)習(xí)的情況下，第一步將子任務(wù)分配給合適的智能體所需要的時間復(fù)雜度為，第二步學(xué)習(xí)智能體到對應(yīng)子任務(wù)位置的最優(yōu)路徑所需要的時間復(fù)雜度為，故總的時間復(fù)雜度為。而用基于Q學(xué)習(xí)的基本搜索算法進行迭代求解，那么時間復(fù)雜度為，這里有m?k，故相比較而言，本文提出的算法的時間復(fù)雜度要遠低于基于Q 學(xué)習(xí)的基本搜索算法。

4 實驗與結(jié)果

為了驗證算法的性能，本文實驗的環(huán)境建立在“格子世界”模型之上。從算法運行時間、平均帶折扣回報等方面將文中的算法與基于Q 學(xué)習(xí)的基本搜索算法進行對比。本章首先介紹了實驗?zāi)Ｐ停又故玖藘煞N算法的性能并進行分析。

4.1 實驗?zāi)Ｐ图皡?shù)設(shè)置

實驗?zāi)Ｐ腿鐖D1所示，環(huán)境被分為18×27個小格，黑色部分表示障礙，若智能體執(zhí)行某動作之后遇到障礙則停在原地。智能體每走一步只要不到達終點所獲得的立即回報為?1，智能體碰到障礙得到?10 的懲罰，到達終點得到+10 的立即回報。圖中數(shù)字部分表示智能體的位置，本實驗中一共有14 個智能體且智能體的位置固定，圖中Δ 表示子任務(wù)的位置，子任務(wù)的位置是不斷變動的，每個任務(wù)中子任務(wù)的位置不同，且子任務(wù)的數(shù)量也不一定相同。此處假設(shè)智能體最多只能完成一個子任務(wù)，故子任務(wù)總數(shù)小于智能體總數(shù)，并且本實驗考慮子任務(wù)數(shù)較多的情況，因為子任務(wù)少的情況下，可選擇的智能體較多，不科學(xué)的選擇對結(jié)果的影響較小，故子任務(wù)數(shù)最小為10，若表示子任務(wù)的數(shù)量，設(shè)。為了表示實驗的一般性，目標(biāo)任務(wù)的子任務(wù)位置是隨機產(chǎn)生的。在實驗中，源任務(wù)中各子任務(wù)位置是隨機生成的，均勻分布在圖1 所示的各子區(qū)域中。

傳統(tǒng)Q學(xué)習(xí)算法中使用的是ε-greedy策略，參數(shù)的設(shè)置考慮到實際情況和Fernando[16]文中的參數(shù)，具體如下：ε=0.01 表示Q 學(xué)習(xí)算法有1%的概率進行“探索”，99%的概率進行“利用”；γ=0.9 表示折扣因子為0.9；α=0.05 表示學(xué)習(xí)速率為0.05，Episodes=2 000 表示智能體最多迭代2 000 次學(xué)習(xí)最優(yōu)路徑，該迭代次數(shù)可以保證算法收斂到最優(yōu)路徑。在實驗中，由于本文提出的算法解決的是多智能體環(huán)境下的多任務(wù)分配問題，其本質(zhì)是一個序列決策問題，而Q學(xué)習(xí)是解決這類問題的經(jīng)典算法，故此處與基于傳統(tǒng)Q 學(xué)習(xí)的任務(wù)分配方法進行比較，以驗證本文算法的性能。相較于其他路徑規(guī)劃算法，如A*算法，基于遷移學(xué)習(xí)的算法的優(yōu)勢在于其不需要知道環(huán)境的準(zhǔn)確模型，而通過不斷試錯得到最優(yōu)路徑。實驗環(huán)境：Intel i5 CPU，4 GB RAM 以及Python 3.5。

4.2 實驗結(jié)果與分析

第一組實驗的目的是比較基于Q 學(xué)習(xí)的基本搜索算法與本文提出的算法之間的算法運行時間和準(zhǔn)確度。本組實驗共有21 個目標(biāo)任務(wù)，每個目標(biāo)任務(wù)中的子任務(wù)個數(shù)是隨機的，表1展示了21組目標(biāo)任務(wù)找到對應(yīng)的智能體所需要的平均時間。

表1 算法運行時間比較

從該組實驗可以得出，利用基于Q學(xué)習(xí)的基本搜索算法所消耗的時間遠高于本文提出的算法，其原因在于利用歷史經(jīng)驗，目標(biāo)任務(wù)的解決無需窮舉每種情況，而基于Q 學(xué)習(xí)的基本搜索算法由于每次獲得最優(yōu)路徑的消耗時間較多，再加上該過程要迭代多次，故時間較長。本文提出算法的最大優(yōu)勢是大大降低了算法的運行時間，對于實時性要求較高的任務(wù)，其性能比基于Q學(xué)習(xí)的基本搜索算法好。

第二組實驗分析了不同子任務(wù)數(shù)對任務(wù)分配算法的運行時間的影響。圖3 展示了兩種算法的運行時間的對比。從圖中可以看出，當(dāng)目標(biāo)任務(wù)的子任務(wù)數(shù)為10時，基于Q 學(xué)習(xí)的基本搜索算法的運行時間為800 s 左右，子任務(wù)數(shù)為11 時，運行時間波動不是很大，子任務(wù)數(shù)為12時，運行時間接近950 s，當(dāng)任務(wù)數(shù)為13時，運行時間接近1 200 s，而本文提出的算法在運行時間上花費較少且波動不大。原因在于基于Q 學(xué)習(xí)的基本搜索算法在計算每個智能體到目標(biāo)任務(wù)的最短路徑之后再選出可以到子目標(biāo)任務(wù)最快的智能體，從而找到能解決目標(biāo)任務(wù)最優(yōu)的智能體集合，故受子任務(wù)數(shù)的影響較大。而本文提出的算法利用了歷史經(jīng)驗進行任務(wù)分配，僅通過比對任務(wù)之間的相似度，將最相似的源任務(wù)的分配方案遷移到目標(biāo)任務(wù)中，故任務(wù)分配的耗時較少且?guī)缀醪皇茏尤蝿?wù)數(shù)的影響。

圖3 不同任務(wù)數(shù)的運行時間

第三組實驗顯示了pt更新公式中不同參數(shù)值的性能比較，結(jié)果如圖4 所示。其中，參數(shù)的范圍值為50 至1 000。

圖4 不同參數(shù)值的性能比較

第四組實驗顯示了在學(xué)習(xí)最優(yōu)路徑中，使用遷移學(xué)習(xí)和不使用遷移學(xué)習(xí)的對比，從第一個片段和最后一個片段的平均帶折扣回報方面進行對比與分析。圖5 顯示了某個隨機產(chǎn)生的目標(biāo)子任務(wù)的最優(yōu)路徑學(xué)習(xí)過程中，使用不帶遷移學(xué)習(xí)和帶遷移學(xué)習(xí)的平均帶折扣回報的對比。從圖中可以看出，帶遷移學(xué)習(xí)的算法在初始時就有比較好的平均帶折扣回報，且在執(zhí)行過程中，該值都比不使用遷移學(xué)習(xí)要高，這表明本文提出的算法縮短了智能體找到最優(yōu)路徑所需的時間。

圖5 子任務(wù)帶遷移與不帶遷移的平均帶折扣回報

表2 顯示了一個目標(biāo)任務(wù)中各子任務(wù)在帶遷移學(xué)習(xí)和不帶遷移學(xué)習(xí)上平均帶折扣回報的對比。從表中可以看出，使用遷移學(xué)習(xí)可以在初期給智能體較好的行為指導(dǎo)。其中，[9，6]這個子任務(wù)在第2 000個片段的帶遷移平均帶折扣回報比不帶遷移的低，這是由于在分配任務(wù)階段，分配給的智能體不同而導(dǎo)致的。對于任務(wù)分配的準(zhǔn)確度問題也是以后需要進一步研究、改進之處。

表2 帶遷移與不帶遷移的平均帶折扣回報對比

5 總結(jié)與未來工作

本文主要研究了多智能體系統(tǒng)中的多任務(wù)分配問題。提出了一種基于遷移學(xué)習(xí)的任務(wù)分配機制。首先將目標(biāo)任務(wù)與源任務(wù)庫中的任務(wù)進行比較，找到與目標(biāo)任務(wù)最相似的源任務(wù)，將策略庫中對應(yīng)的智能體的分配方案遷移到目標(biāo)任務(wù)中，給目標(biāo)任務(wù)較好的初始化，加速目標(biāo)任務(wù)的分配。本文還利用遷移學(xué)習(xí)加快智能體學(xué)習(xí)最優(yōu)路徑的速度，即將智能體之前處理過的子任務(wù)的策略遷移到目標(biāo)子任務(wù)的完成上。通過實驗可以看出，本文提出的算法在運行時間和平均帶折扣回報上均優(yōu)于基于Q學(xué)習(xí)的任務(wù)分配算法。

未來的研究方向包括：首先是要解決魯棒性不夠的問題，可從相似度的比較方法方面進行改進；其次，若目標(biāo)任務(wù)的狀態(tài)空間和行為空間產(chǎn)生變化，要如何將源任務(wù)的策略進行遷移，如何防止因狀態(tài)空間或行為空間的變化而帶來的負(fù)遷移情況。