基于遺傳算法的多Agent任務(wù)分配問(wèn)題研究.pdf

1、多Agent理論及相關(guān)技術(shù)為分布式系統(tǒng)的研究提供了一個(gè)嶄新的途徑。多Agent系統(tǒng)理論是分布式人工智能體系的一個(gè)分支,目前多Agent技術(shù)已經(jīng)成為了當(dāng)今人工智能領(lǐng)域研究的熱點(diǎn)之一。而多Agent任務(wù)分配問(wèn)題是多Agent系統(tǒng)研究的基礎(chǔ)性問(wèn)題,體現(xiàn)了系統(tǒng)高層組織形式與運(yùn)行機(jī)制,是多Agent系統(tǒng)實(shí)現(xiàn)目標(biāo)的基礎(chǔ)。一方面,任務(wù)分配的好壞直接影響到整個(gè)系統(tǒng)的運(yùn)行效率,并且直接關(guān)系到系統(tǒng)中各Agent能否最大限度發(fā)揮自己的能力,避免占用更多的資源

2、。另一方面,當(dāng)一個(gè)Agent沒(méi)有能力完成當(dāng)前任務(wù)時(shí),如何在現(xiàn)有機(jī)制的基礎(chǔ)上,通過(guò)有效地對(duì)話、協(xié)商使多Agent合作完成此項(xiàng)任務(wù)已經(jīng)成為越來(lái)越多研究者關(guān)注的問(wèn)題。
　　 本文在此著重分析多Agent系統(tǒng)中的任務(wù)分配過(guò)程,首先說(shuō)明了多Agent系統(tǒng)任務(wù)分配問(wèn)題是一種典型的組合優(yōu)化問(wèn)題,由于傳統(tǒng)的任務(wù)分配問(wèn)題的目標(biāo)是充分利用分布式系統(tǒng)多處理機(jī)的并行性,將一個(gè)任務(wù)分解成多個(gè)子任務(wù),通過(guò)子任務(wù)的并行執(zhí)行使問(wèn)題能夠在最短的時(shí)間內(nèi)解決。本文在

3、此對(duì)任務(wù)的分解問(wèn)題不再做詳細(xì)闡述,只對(duì)在任務(wù)分配的過(guò)程中如何將各個(gè)任務(wù)分配給擁有完成相應(yīng)任務(wù)能力的Agent,同時(shí)對(duì)沖突進(jìn)行合理的優(yōu)化進(jìn)行分析,然后通過(guò)對(duì)影響任務(wù)分配問(wèn)題的因素進(jìn)行分析,將遺傳算法、蟻群算法和模擬退火算法進(jìn)行比較,得出結(jié)論:隨著問(wèn)題規(guī)模的不斷增大,遺傳算法在解決任務(wù)分配問(wèn)題中的優(yōu)越性得到了充分體現(xiàn),遺傳算法相比其他常見(jiàn)的啟發(fā)式算法有較高的性能,能夠用較少的時(shí)間得到更優(yōu)的解。
　　 很多傳統(tǒng)技術(shù)對(duì)多Agent任務(wù)分

4、配問(wèn)題的應(yīng)用領(lǐng)域常常無(wú)能為力,而遺傳算法卻提供了一條解決復(fù)雜任務(wù)分配問(wèn)題的新途徑,然而標(biāo)準(zhǔn)遺傳算法在解決任務(wù)分配問(wèn)題上存在著局部搜索能力較差、收斂速度低等缺點(diǎn),所以需要進(jìn)一步對(duì)遺傳算法進(jìn)行改進(jìn),才能使遺傳算法在解決任務(wù)分配問(wèn)題中發(fā)揮更加重要的作用。針對(duì)遺傳算法這些缺點(diǎn),本文提出了兩種改進(jìn)方法,一種是將局部搜索能力強(qiáng)的算法引入到遺傳算法,同時(shí)設(shè)計(jì)出能適應(yīng)新的編碼方式的遺傳算子,并在遺傳算子中融入與問(wèn)題相關(guān)的啟發(fā)式知識(shí),這樣可以使混合遺傳算

5、法既能保持遺傳算法的全局最優(yōu)特點(diǎn),又能夠提高其運(yùn)行效率;另一種方法是提出一種基于二叉樹(shù)編碼的遺傳算法。首先將任務(wù)分配問(wèn)題轉(zhuǎn)化為等效的AOV圖,并將其轉(zhuǎn)化成二叉樹(shù),然后進(jìn)行遍歷編碼,最后用改進(jìn)的遺傳算子進(jìn)行算法優(yōu)化,該算法克服了一維編碼的局限性,比普通的一維編碼遺傳算法有更高的執(zhí)行效率。
　　 最后設(shè)計(jì)出一個(gè)多Agent任務(wù)分配問(wèn)題的實(shí)例,建立任務(wù)分配的目標(biāo)函數(shù),指導(dǎo)Agent與任務(wù)進(jìn)行組合優(yōu)化,利用改進(jìn)的遺傳算法來(lái)求解該多Age