多Agent系統(tǒng)聯(lián)盟及任務(wù)分配的研究.pdf

1、在多Agent系統(tǒng)中，多個(gè)Agent可以通過聯(lián)盟的形式完成單個(gè)Agent不能完成的任務(wù)，集中體現(xiàn)了多Agent系統(tǒng)設(shè)計(jì)的初衷。有關(guān)聯(lián)盟的研究是多Agent系統(tǒng)的一個(gè)關(guān)鍵問題。學(xué)術(shù)界現(xiàn)已進(jìn)行了大量研究，并取得了豐富的成果。 單任務(wù)聯(lián)盟生成問題是一個(gè)復(fù)雜的組合優(yōu)化問題，進(jìn)化算法和群智能算法是常見的解決方法。但現(xiàn)有的研究僅僅從進(jìn)化算法或群智能算法的角度出發(fā)，研究單任務(wù)聯(lián)盟生成的求解，而忽略了問題本身的特點(diǎn)，因此在問題的求解質(zhì)量上還存在

2、著改進(jìn)的必要和可能。另外目前尚沒有研究提出本問題的多項(xiàng)式時(shí)間近似算法來適應(yīng)實(shí)時(shí)性要求高的場合。 聯(lián)盟特征函數(shù)是聯(lián)盟問題的基礎(chǔ)。現(xiàn)有的聯(lián)盟特征函數(shù)定義基于能力向量或資源向量的描述，但這兩種方式都存在著不足：無論能力或資源，用簡單的數(shù)字來描述都是不切實(shí)際的；能力的增強(qiáng)或資源的累加也不一定可以用簡單的加減法來計(jì)算。 基于合同網(wǎng)的任務(wù)分配是多Agent系統(tǒng)常見的任務(wù)分配機(jī)制。但傳統(tǒng)的合同網(wǎng)存在著待選Agent范圍大、通信代價(jià)大、

3、對自私Agent的惡意投標(biāo)缺乏防范等不足，現(xiàn)有的相關(guān)的改進(jìn)也缺乏較全面的考慮。 針對以上問題，本文做了相關(guān)研究。主要貢獻(xiàn)在于： (1)提取單任務(wù)Agent聯(lián)盟生成的先驗(yàn)知識(shí)，用于指導(dǎo)相關(guān)進(jìn)化算法和群智能算法求解單任務(wù)聯(lián)盟生成問題(2.1節(jié)內(nèi)容)，提高了算法求解質(zhì)量；提出一種求解單任務(wù)Agent聯(lián)盟生成的貪婪算法(3.1節(jié)內(nèi)容)；提出一種求解單任務(wù)Agent聯(lián)盟生成的多項(xiàng)式時(shí)間近似算法(3.2節(jié)內(nèi)容)，更適合于實(shí)時(shí)性要求高

4、的場合。 (2)對現(xiàn)有的Agent信任與名譽(yù)的FIRE模型進(jìn)行改進(jìn)，提出基于Agent組織的半分布式FIRE模型(4.2節(jié)內(nèi)容)；提出了一種基于服務(wù)觀點(diǎn)和改進(jìn)的FIRE模型的新聯(lián)盟特征函數(shù)定義，并考察了在此定義下的單任務(wù)聯(lián)盟和多任務(wù)聯(lián)盟問題的求解(4.3節(jié)內(nèi)容)；設(shè)計(jì)了一種求解在新聯(lián)盟特征函數(shù)定義下的多任務(wù)聯(lián)盟生成問題的貪婪算法(4.4節(jié)內(nèi)容)。 (3)提出基于改進(jìn)FIRE模型的合同網(wǎng)運(yùn)行機(jī)制，將其運(yùn)用于任務(wù)分配。相比現(xiàn)