基于Agent圖的聯(lián)盟形成算法研究.pdf

1、眾所周知，智能體或稱為Agent可以通過相互協(xié)作來實(shí)現(xiàn)他們的共同目標(biāo)，以提高其整體的性能。在多Agent系統(tǒng)中，這種相互協(xié)作通常采用Agent聯(lián)盟的形式來完成。所謂聯(lián)盟就是多個(gè)同意協(xié)作的Agents在一起解決某個(gè)共同的問題，這些問題可能是單個(gè)Agent很難完成的或者完成的效率沒有Agent組合的高。當(dāng)多個(gè)Agent作為Agent聯(lián)盟形式時(shí)，每個(gè)Agent都能從聯(lián)盟獲得額外的收益。因此可以看出，聯(lián)盟形成(CF)是一種將分布的自治的多個(gè)Ag

2、ents聯(lián)合起來共同解決某個(gè)問題有效機(jī)制，在這個(gè)聯(lián)盟中，每個(gè)Agent個(gè)體都有它們自身的能力，當(dāng)Agents作為聯(lián)盟工作時(shí)，每個(gè)Agent在聯(lián)盟中都有實(shí)現(xiàn)了自己的功能價(jià)值。由此，在多Agent系統(tǒng)(MAS)中，聯(lián)盟形成(CF)是十分必要及有用的交互協(xié)作形式，它能夠以一種有效的方式提高Agent完成任務(wù)和實(shí)現(xiàn)目標(biāo)的能力。已經(jīng)證實(shí)，多Agent聯(lián)盟已經(jīng)被運(yùn)用到很多領(lǐng)域，比如:資源分配，合作問題求解，商業(yè)交易等多個(gè)領(lǐng)域。在資源分配問題中，資源

3、Agents組成聯(lián)盟來完成服務(wù)任務(wù)，能完成單個(gè)資源Agent不能完成或不能高效完成的服務(wù)任務(wù)。在合作問題求解時(shí)，多個(gè)Agents組成聯(lián)盟共同完成任務(wù)，使完成任務(wù)的同時(shí)能爭取整體利益最大化。在商業(yè)交易中，Agent與其他個(gè)體相互合作，形成聯(lián)盟，可獲得批量折扣，增加自身收益。然而，在實(shí)際的應(yīng)用中面臨的主要問題是，怎樣在單個(gè)Agent的能力有限不能單獨(dú)完成任務(wù)時(shí)，通過相互合作的Agent形成聯(lián)盟的合作形式，從而使Agent更好的實(shí)現(xiàn)目標(biāo)，并實(shí)

4、現(xiàn)整體利益的最大化。
　　聯(lián)盟形成問題是MAS研究領(lǐng)域中挑戰(zhàn)性問題之一。這個(gè)問題的關(guān)鍵是，如何高效的在多Agents之間構(gòu)建聯(lián)盟，這也是本論文著力研究的主要內(nèi)容。對聯(lián)盟形成的研究主要從兩個(gè)方面進(jìn)行，一個(gè)是聯(lián)盟如何形成，它的形成過程，形成方法，形成的模型等，另一個(gè)是聯(lián)盟評估。其中，前者涉及到的是聯(lián)盟形成方面的（如聯(lián)盟的結(jié)構(gòu)，聯(lián)盟值），后者提到的是聯(lián)盟形成的結(jié)果（如收益分配等）。當(dāng)前大多數(shù)研究工作將聯(lián)盟形成看成一個(gè)優(yōu)化問題，主要是尋找

5、擁有最大效用值的最優(yōu)聯(lián)盟，而不是關(guān)注聯(lián)盟的形成問題以及通過哪些有效的方法獲得那些合適的聯(lián)盟結(jié)構(gòu)。毋庸置疑，采用窮盡搜索方式可以找到使Agent組合的全局效用值（比如社會(huì)福利）最大化的Agent聯(lián)盟結(jié)構(gòu)，然而，實(shí)際情況是，多Agent系統(tǒng)中的這些Agent都是以分散的形式存在。
　　為了某個(gè)特定的目標(biāo)，需要將這些分散的Agent形成聯(lián)盟來解決問題時(shí)，當(dāng)每個(gè)agent都只有其鄰居的局部信息時(shí)，形成聯(lián)盟時(shí)很難通過窮盡搜索方式找到全局的最

6、優(yōu)聯(lián)盟結(jié)構(gòu)。在這些情況下，我們無法找到或者及時(shí)的找到全局的最優(yōu)解，我們不得不考慮次最優(yōu)解，這些次最優(yōu)解雖然不能達(dá)到聯(lián)盟的最高性能，但是能滿足形成聯(lián)盟的最低要求。因此，本文致力于提高這類多Agent聯(lián)盟形成的質(zhì)量的研究。
　　本文的主要貢獻(xiàn)也都集中于此，本文主要呈現(xiàn)了多Agent系統(tǒng)中基于Agent圖的聯(lián)盟形成算法。該算法是在分布式多Agent系統(tǒng)中，對來自一個(gè)Agent圖中的智能體構(gòu)建聯(lián)盟。其中，所謂Agent圖是指Agent互相

7、關(guān)聯(lián)的拓?fù)浣Y(jié)構(gòu)圖。這種系統(tǒng)是由一些自治Agent構(gòu)成，這些Agent可以在沒有控制中心的情況下自發(fā)的與其他Agent對話以及實(shí)現(xiàn)它們的功能。因?yàn)?，真?shí)世界環(huán)境中，Agent都是只有局部的不完全信息，在這種情況下要為某個(gè)特定的目標(biāo)形成聯(lián)盟，我們必須提出并實(shí)現(xiàn)一些可行的高效的算法形成聯(lián)盟?；谏鲜龅姆治?，它可以通過搜索agent圖中的聯(lián)盟伙伴來實(shí)現(xiàn)，這不僅可以提高聯(lián)盟形成的質(zhì)量也可以提高聯(lián)盟形成的效率。
　　據(jù)此，本文從四個(gè)方面進(jìn)行闡

8、述上述的聯(lián)盟形成算法研究。第一，提出了一種新型的聯(lián)盟形成機(jī)制，這種聯(lián)盟機(jī)制從一種新的角度考慮了Agent之間的聯(lián)盟，同時(shí)對價(jià)值不斷變化的Agent之間如何形成聯(lián)盟也進(jìn)行考慮。它的優(yōu)點(diǎn)不在于形成一個(gè)最優(yōu)聯(lián)盟，而是通過Agent與它的鄰居們的協(xié)商過程，從協(xié)商的Agent集中獲得一個(gè)有效的聯(lián)盟集，這些鄰居是從Agent圖中的鄰接點(diǎn)（如，直接相鄰的）獲取的。在有些情況下，Agent具有完成任務(wù)所需的所有功能，因而它可以完全靠自己來完成自己的目標(biāo)

9、。然而，有些時(shí)候Agent的功能有限，不能單個(gè)的完成某個(gè)任務(wù)，或者對某些任務(wù)它就無法像其他Agent那樣有效的完成。這種情況下，Agent可以通過交流將任務(wù)分配給它的鄰居。這種分配就可以通過Agent之間的協(xié)商來完成，通過協(xié)商分配任務(wù)給他的鄰居以致使任務(wù)的完成質(zhì)量更高。第二，本論文擴(kuò)展了Agents之間的協(xié)作關(guān)系，除了Agent圖中直接相連的Agents的協(xié)作，還包括了間接相連的Agents之間的協(xié)作。該協(xié)作關(guān)系是通過搜索帶有權(quán)值函數(shù)的

10、Agent圖實(shí)現(xiàn)的。所謂的帶有權(quán)值函數(shù)的圖是用來標(biāo)記聯(lián)盟的，這種聯(lián)盟是為了實(shí)現(xiàn)特定的目標(biāo)而存在的。當(dāng)Agent并沒有實(shí)現(xiàn)目標(biāo)所需要的所有能力時(shí)，Agent需要和那些能夠?qū)崿F(xiàn)一些子任務(wù)的Agents形成聯(lián)盟，進(jìn)而完成整個(gè)任務(wù)。否則，Agent將無法完成整個(gè)任務(wù)。第三，論文研究自治的Agent如何獲得批量的折扣。作為聯(lián)盟的成員，Agents可以以折扣價(jià)的成本實(shí)現(xiàn)部分或者全部的目標(biāo)，從而使Agent獲得收益。這表明Agent聯(lián)盟是根據(jù)聯(lián)盟價(jià)值

11、的特定約束形成的。第四，是第三方面的擴(kuò)張，討論了如何獲得穩(wěn)定的聯(lián)盟。本文假設(shè)agent是同構(gòu)的，共享相同的目標(biāo)，它們可以形成穩(wěn)定的聯(lián)盟通過在核中心的收益回報(bào)分布。它的穩(wěn)定性指的是Agent滿足一定穩(wěn)定性條件的花銷分擔(dān)規(guī)則。綜上，本文重點(diǎn)在于找到實(shí)用的解決算法，在現(xiàn)實(shí)環(huán)境中，通過搜索Agent圖中的聯(lián)盟伙伴形成聯(lián)盟，以改善聯(lián)盟的形成過程和聯(lián)盟形成的質(zhì)量，這就是本文的主要的研究內(nèi)容。
　　根據(jù)前段的闡述，本文首先在Agent和它的鄰居

12、之間提出了一種新穎實(shí)用的基于模糊邏輯的決策理論的分布式協(xié)商模型。運(yùn)用這種模型可以自動(dòng)克服復(fù)雜的談判過程，并且可以在Agent擁有鄰居的不完全信息的情況下，幫助Agent形成聯(lián)盟。這種談判模型是形成有效聯(lián)盟的基礎(chǔ)。該模型包括三個(gè)主要的內(nèi)容:(1)分布式協(xié)商模型形成聯(lián)盟;(2)基于模糊邏輯的評價(jià)模型和(3)一組最佳的有效聯(lián)盟集。
　　其中，分布式協(xié)商模型采用基于交替提議協(xié)商協(xié)議，Agent和它們的直接鄰居之間可以協(xié)商多個(gè)議題（如，價(jià)格

13、和質(zhì)量等）。每一方在此過程中都是通過提供建議和反建議進(jìn)行協(xié)商，最終都想達(dá)到對自己是最低價(jià)格的協(xié)議（比如，一個(gè)聯(lián)盟伙伴）。依賴于推理組件模型的模糊評價(jià)方式，該部分主要是專注于評估Agent所提的建議，從而決定接受還是拒絕對方的提議，并生成提議，/反提議。它利用一個(gè)集合的模糊隸屬函數(shù)（即低或高）來推理相關(guān)數(shù)據(jù)以及If-Then決策規(guī)則來支持靈活的協(xié)商過程。用模糊模型做出的決策是依賴于一系列的提議接收的程度，這使得決策更能貼近現(xiàn)實(shí)的真實(shí)世界，

14、并且擁有更好的靈活性?；谀：碚摰脑u估包含三個(gè)步驟（即模糊化步驟、推理步驟和去模糊化步驟），它能夠決定提議是否接收和接受的程度。在模糊化步驟中，定義輸入變量的隸屬函數(shù)應(yīng)用它們的實(shí)際價(jià)值來決定真實(shí)的程度。在推理步驟中，每個(gè)規(guī)則的真實(shí)值會(huì)被計(jì)算出來，然后應(yīng)用到每個(gè)規(guī)則的結(jié)論部分。在一個(gè)模糊子集中的結(jié)果將會(huì)被分配給每個(gè)規(guī)則的輸出變量中，在去模糊化的步驟中，模糊輸出結(jié)果將會(huì)被去模糊化變成一個(gè)清晰的數(shù)。然后根據(jù)每個(gè)協(xié)商Agent的行為制定相應(yīng)的

15、協(xié)商策略，決定每次提議是接受或拒絕還是重來。比如，Agent利用時(shí)間依賴策略與其他Agent協(xié)商，當(dāng)一個(gè)協(xié)商發(fā)生是，Agent都會(huì)有一個(gè)時(shí)間期限。應(yīng)用時(shí)間限制策略的重點(diǎn)在于保證Agent的協(xié)商不能是無限期的，相反的，要讓協(xié)商在一個(gè)合理的時(shí)間范圍（或者是最大回合數(shù)）內(nèi)完成。因此，當(dāng)一些Agent經(jīng)過成功的協(xié)商完成某個(gè)目標(biāo)后，最有效的聯(lián)盟集能夠在這些Agents中形成。
　　利用基于模糊邏輯的方法的原因在于，需要處理關(guān)于對手的有限的信

16、息和談判對手的不同偏好，而模糊邏輯能夠很好的解決利用不完整的信息進(jìn)行推理的問題。采用傳統(tǒng)的模型來評估一個(gè)多議題的協(xié)商提議，太過復(fù)雜。而基于模糊邏輯的方法在克服評估提議復(fù)雜性上有更突出的實(shí)際意義。因此，在本文所提出的這個(gè)基于模糊邏輯的模型中，我們應(yīng)用模糊邏輯建立議題之間的關(guān)系（比如價(jià)格，交貨期限等），并且允許Agent表達(dá)它們的偏好，評估系統(tǒng)也是充分考慮Agent的需求（即Agent的效用最大化）。協(xié)商的核心是用一個(gè)最低價(jià)格達(dá)成協(xié)議并幫助

17、形成一個(gè)有效的聯(lián)盟。我們要考慮的問題在于，協(xié)商模型的有效性、實(shí)用性，以及如何在Agent圖中，以一種分散的形式找到潛在的聯(lián)盟伙伴。
　　本文提出的基于模糊邏輯的協(xié)商模型的性能評估通過與其他的傳統(tǒng)模型的對比來進(jìn)行。文章中提到的傳統(tǒng)模型包括:1）戰(zhàn)術(shù)策略模型和2）得分函數(shù)模型。在戰(zhàn)術(shù)模型中，該模型是根據(jù)Agent自身的標(biāo)準(zhǔn)來評估和決策提議的接受與否，但這個(gè)并不能保證最佳的交易結(jié)果，因?yàn)樗鼪]有考慮Agent在協(xié)商過程中的偏好，而且還允許

18、Agent快速讓步到它們的保留值以達(dá)成協(xié)議。雖然在得分函數(shù)模型中，Agent在計(jì)算提議評估的得分函數(shù)時(shí)考慮了每個(gè)議題的權(quán)重，但是它沒有考慮在協(xié)商過程中所有提出的議題和推理之間的關(guān)系。
　　仿真實(shí)驗(yàn)表明，本文提出的基于模糊邏輯的協(xié)商模型，可以在協(xié)商Agent中獲得更好的協(xié)商結(jié)果。實(shí)驗(yàn)證明基于模糊理論協(xié)商模型的協(xié)商成功率比戰(zhàn)術(shù)模型的高了12％，比得分模型的成功率高了34％到48％。并且，它動(dòng)態(tài)的提高了獲得有效聯(lián)盟集的機(jī)會(huì)，它的最高效率

19、比戰(zhàn)術(shù)模型提高了27％到70％。在有大量的Agent參入的情況下，與得分模型相比效率高出98％以上。在一個(gè)合理分配的時(shí)間范圍內(nèi)，模糊理論的決策者協(xié)商模型獲得的最高效率比得分模型的最高效用值高了44％到86％，通過設(shè)置談判進(jìn)程的最后期限，以避免無休止的協(xié)商，模糊理論的決策者協(xié)商模型節(jié)省的協(xié)商時(shí)間與戰(zhàn)術(shù)模型相比高了35％到65％。在社會(huì)福利方面，在大量有Agents參入的情況下，基于模糊理論的模型獲得社會(huì)福利比戰(zhàn)術(shù)協(xié)商模型高出至少70％在比

20、小數(shù)量Agents的情況下，比得分模型高出至少29％的。綜上，可以得出結(jié)論，本文提出的分布式基于模糊邏輯協(xié)商模型比其他模型在提高聯(lián)盟的形成質(zhì)量上更加的有實(shí)用和高效。
　　某些時(shí)候聯(lián)盟伙伴是可以擴(kuò)展的，也就是聯(lián)盟的伙伴可以從Agent的直接相鄰鄰居擴(kuò)展到它的間接相鄰鄰居，這樣可以為Agent提供更多的機(jī)會(huì)來實(shí)現(xiàn)它們的任務(wù)或者求得子任務(wù)的解。參入考慮的Agents的數(shù)量越多，所組成的聯(lián)盟的可能性就越多，還有就是每個(gè)Agent都有自己的

21、功能，這樣整個(gè)聯(lián)盟的功能集就會(huì)相應(yīng)增強(qiáng)了。尤其是當(dāng)在解決一個(gè)任務(wù)或者理解為一個(gè)實(shí)現(xiàn)某個(gè)功能時(shí)，如果它的直接鄰居的資源或能力有限，不通過擴(kuò)展可能會(huì)導(dǎo)致任務(wù)的失敗，因?yàn)樵谶@個(gè)集合中沒有Agent有能力解決問題。因此，構(gòu)建一個(gè)可行的聯(lián)盟的聯(lián)盟伙伴不僅可以從直接鄰居獲得也可以從有用的間接鄰居中獲得。我們知道可以從帶有加權(quán)值的Agent圖中可以得到這些鄰居，其中有些Agent扮演經(jīng)紀(jì)人的角色，推薦相關(guān)Agent，并且獲得了一些獎(jiǎng)勵(lì)。如何構(gòu)建支持間

22、接鄰居的多Agent聯(lián)盟算法，將是本文呢闡述的第二個(gè)內(nèi)容。
　　基于上述想法，本文提出的算法是找到次最優(yōu)可行解算法來實(shí)現(xiàn)某個(gè)特定的目標(biāo)，這種次最優(yōu)可行解它是接近最優(yōu)最小成本的解，這時(shí)Agent不得不找到合適的聯(lián)盟伙伴來共同完成任務(wù)，并形成可行的聯(lián)盟(FC)。這個(gè)可行聯(lián)盟指的是，為了實(shí)現(xiàn)某個(gè)特定的任務(wù)或目標(biāo)，聯(lián)盟中所有的成員可以是間接關(guān)聯(lián)的。在加權(quán)Agent圖中進(jìn)行搜索聯(lián)盟伙伴，形成可行聯(lián)盟獲得最好的或者次最優(yōu)的解取決與這個(gè)搜索過程

23、。求最優(yōu)最小成本解，搜索過程需要完成對整個(gè)圖的搜索——完全搜索。雖然，這個(gè)最優(yōu)解保證了全局最小值（即最小成本），但是這是一種不考慮時(shí)間和空間復(fù)雜度的窮盡搜索方法。市級存在這樣的環(huán)境因素（比如在有大量的agent和大量的任務(wù)的情況下）制約這種最優(yōu)聯(lián)盟形成。但是這些因素會(huì)促進(jìn)所有參與聯(lián)盟的Agent，通過搜尋臨近最優(yōu)可行解來構(gòu)建協(xié)作聯(lián)盟。這種臨近最優(yōu)可行方案，通過使用一個(gè)貪婪算法，在每個(gè)搜索階段，試圖從下一個(gè)的搜索階段放棄不良的Agent，

24、從而保證達(dá)到在計(jì)算復(fù)雜度上局部的最小值（相對于它的鄰居成本來說是最小的）。
　　文章中提到的最優(yōu)最小成本算法是基于廣度優(yōu)先搜索的(BFS)，通過完全搜索層次化的Agent權(quán)重圖能夠找到全局最優(yōu)解。其算法的核心思想是:首先，是給出一個(gè)Agent的請求，訪問與請求動(dòng)作相關(guān)的第一層Agents;然后一層層的檢查所有的于此相鄰的Agent，這些Agents都是遠(yuǎn)離訪問Agent的;最后將這些訪問過的遠(yuǎn)距離Agents分配到一個(gè)新的層。然后

25、繼續(xù)以相同的方式搜索，檢查那些與請求的Agent相鄰的Agents，對于那些先前分配到一個(gè)層的Agents不做動(dòng)作。當(dāng)Agent圖中的所有的Agents都被遍歷到了，這個(gè)過程將會(huì)終止，這時(shí)用最低成本實(shí)現(xiàn)任務(wù)的聯(lián)盟伙伴就已經(jīng)被找到了。
　　本文提出的臨近最優(yōu)可行解算法同樣也是基于廣度優(yōu)先搜索方法的，通過擴(kuò)展那些最接近目標(biāo)的結(jié)點(diǎn)來實(shí)現(xiàn)局部最優(yōu)。在這種方法中，搜索的深度是根據(jù)最有可能的結(jié)點(diǎn)的深度來的決定的。首先，它有一個(gè)提出請求的Age

26、nt，作為訪問點(diǎn)在第一層訪問與請求動(dòng)作相關(guān)的Agent，然后檢查那些遠(yuǎn)離訪問Agent的邊緣有效Agents（即可以承擔(dān)請求動(dòng)作的Agent）。從檢查過的Agents中選擇出最有前途的Agent（即可以提供最低成本的Agent），進(jìn)而擴(kuò)展它的分支作為下個(gè)搜索區(qū)域，忽略其他的分支Agents。一直重復(fù)這個(gè)過程，當(dāng)沒有有效的Agent或者沒有遺留下需要檢查的Agent時(shí)，我們將停止搜索，這時(shí)，可以為請求動(dòng)作提供最小成本的可行聯(lián)盟伙伴已經(jīng)被找

27、到。臨近最優(yōu)方案算法通過采用子圖的形式，在搜索的每一步中，及時(shí)在每個(gè)子圖中（即以最少的成本，提供動(dòng)作）消除沒有用Agents（頂點(diǎn)）?？梢缘贸?，臨近最優(yōu)解算法在降低計(jì)算復(fù)雜度方面比最優(yōu)最低開銷的算法更加實(shí)用。通過最可行的Agent鄰居進(jìn)行搜索，集中根據(jù)這個(gè)目標(biāo)，可以通過臨近最優(yōu)解決方案實(shí)現(xiàn)局部最優(yōu)解。這種解相對于全局最優(yōu)解具有較低的平均處理時(shí)間和較小的區(qū)域復(fù)雜性，它更適用于現(xiàn)實(shí)世界中構(gòu)建協(xié)作聯(lián)盟。
　　通過實(shí)驗(yàn)的仿真和驗(yàn)證，本文提

28、出的臨近最優(yōu)可行解算法獲得的平均效用值為最優(yōu)最小成本解算法得到平均效用值的91％至97％之間。根據(jù)性能比，臨近最優(yōu)的可行解，可以保證解的質(zhì)量不遜于最優(yōu)解的91％。雖然，最優(yōu)最小成本的解能夠得到全局最優(yōu)效用值，但臨近最優(yōu)可行算法解決方案在實(shí)現(xiàn)局部最優(yōu)上是非常有效和實(shí)用的。隨著Agents數(shù)目增加，臨近最優(yōu)可行算法具有較低的處理時(shí)間形成可行的聯(lián)盟，其時(shí)間復(fù)雜性是最優(yōu)最低成本算法的42％到57％，之間下降到32％。這些結(jié)果表明，本文的第二個(gè)研

29、究內(nèi)容已經(jīng)完成，并且證明了所提出的臨近最優(yōu)可行解方案的有效性。
　　通過考慮與聯(lián)盟形成相關(guān)的搜索成本，我們提出了一個(gè)稱為次優(yōu)折扣聯(lián)盟形成（次優(yōu)DGF）的算法。該算法允許Agent以一個(gè)折扣價(jià)獲取它們部分或者全部的目標(biāo)（例如，請求操作）。在這種情況下，聯(lián)盟成員通過Agents之間的合作取得折扣價(jià)可以增加Agents的效益。這種合作從直接的Agent鄰居擴(kuò)展到間接Agent鄰居，其中可以通過在對Agent圖中的Agents分布式搜索來

30、發(fā)現(xiàn)潛在的合作機(jī)會(huì)。考慮到搜索成本，Agent的目標(biāo)是找到潛在的機(jī)會(huì)的最佳集合，該集合在形成的聯(lián)盟的最大整體功用上以分散的方式用滿足聯(lián)盟請求。這正是本文第三個(gè)研究工作的主要內(nèi)容。
　　具體來說，在次優(yōu)DGF算法中的每一個(gè)Agent將每個(gè)提供的操作都與一個(gè)價(jià)格計(jì)劃相關(guān)聯(lián)，并通過搜索有價(jià)值的聯(lián)盟來提供基于請求的操作數(shù)目（即數(shù)量）的折扣價(jià)。Agent使用一個(gè)聯(lián)盟價(jià)值約束條件(CVC)在繼續(xù)搜索（可能會(huì)由于擴(kuò)展聯(lián)盟而導(dǎo)致更好的機(jī)會(huì)）與接受

31、當(dāng)前聯(lián)盟的形成（從當(dāng)前有價(jià)值的聯(lián)盟之中獲得即時(shí)收益）之間進(jìn)行權(quán)衡。它尋求一個(gè)合作機(jī)會(huì)通過分派來自Agent圖中的請求Agent子集來給所有的聯(lián)盟成員產(chǎn)生最大效用，該子集在可能的聯(lián)盟中擁有最大的聯(lián)盟價(jià)值。DGF的次優(yōu)解決方案算法應(yīng)該保證在與其他的解決方案相比時(shí)獲得更好的結(jié)果，包括:1）單獨(dú)的Agent搜索，其中的每個(gè)Agent都比在團(tuán)體中更高的成本獲得其目標(biāo)（即不享受團(tuán)體折扣）;2）優(yōu)化算法是在效用的基礎(chǔ)上計(jì)算最優(yōu)聯(lián)盟;3）通過考慮搜索成

32、本作為一個(gè)參數(shù)來影響一個(gè)最優(yōu)解的形成。
　　第三個(gè)研究工作的主要成就之一是從團(tuán)隊(duì)中搜索得到收益。這種搜索可以利用被單獨(dú)Agent拋棄的搜索機(jī)會(huì)。通過這樣的收益，少量Agent實(shí)現(xiàn)目標(biāo)的失敗率能夠從24％減少到4％，如果有大量Agents參入，則失敗率幾乎為零。同時(shí)，次優(yōu)DGF算法也表現(xiàn)出其高效性，在實(shí)現(xiàn)一個(gè)目標(biāo)的平均處理時(shí)間上它比單獨(dú)Agent搜索快了15％到34％。通過不同數(shù)量的agent形成的聯(lián)盟的實(shí)驗(yàn)分析，提出的解決方案獲得

33、了在時(shí)間上比其他優(yōu)化模型快5％到24％。隨著Agents數(shù)量的增長，次優(yōu)DGF算法的平均效用以98％的比率接近最優(yōu)效用，并且在考慮搜索成本作為一個(gè)影響最優(yōu)聯(lián)盟的搜索的參數(shù)時(shí)高于平均聯(lián)盟價(jià)值6％。因此，DGF的次優(yōu)解決方案算法在與搜索成本相關(guān)的真實(shí)世界的環(huán)境中有它的優(yōu)勢。Agent更傾向于通過合作搜索折扣價(jià)朝向特定的目標(biāo)形成聯(lián)盟而不是通過單獨(dú)搜索的方式。
　　最后，我們進(jìn)一步的擴(kuò)展上述的研究內(nèi)容，即不僅要獲得一組聯(lián)盟的形成，還要根據(jù)

34、收益分配的核心值來獲得穩(wěn)定的聯(lián)盟形成(SCF)。一個(gè)聯(lián)盟的穩(wěn)定要求根據(jù)成本分?jǐn)傇瓌t在聯(lián)盟成員之間進(jìn)行收益分配，要對拒絕參與并形成自己的聯(lián)盟的Agent團(tuán)體不予分配收益。該核心值是用來描述這個(gè)屬性的最常用概念。當(dāng)形成聯(lián)盟時(shí)，Agents由于實(shí)現(xiàn)一個(gè)目標(biāo)而收到獎(jiǎng)勵(lì)或者回報(bào)，并且要決定如何以一個(gè)穩(wěn)定的方式在成員Agents中劃分獎(jiǎng)勵(lì)。我們考慮的情況是，Agents在一定意義上是同質(zhì)的，每個(gè)Agent都有相同的目標(biāo)（以折扣價(jià)—最低價(jià)獲得操作動(dòng)作

35、）。形成這樣的穩(wěn)定聯(lián)盟時(shí)與搜索成本有關(guān)的。這個(gè)搜索成本反映了在搜索活動(dòng)中需要投入的資源，例如尋找其他Agents以及確定最有價(jià)值的穩(wěn)定聯(lián)盟。因此，一個(gè)基于聯(lián)盟價(jià)值的策略(CVS)以及成本分?jǐn)傄?guī)則用于在對SCF進(jìn)行搜索的過程中評估不同的形成聯(lián)盟的機(jī)會(huì)。為了這個(gè)目的，我們?yōu)镾CF提出了一個(gè)半最優(yōu)解決方案算法。該解決方案應(yīng)該保證通過尋找可行的聯(lián)盟伙伴集合來達(dá)成一個(gè)穩(wěn)定的聯(lián)盟（即核心值在聯(lián)盟內(nèi)的收益分配是穩(wěn)定的）。這些聯(lián)盟伙伴可以在Agent圖

36、中從直接鄰居（Agent的鄰居）擴(kuò)展到間接鄰居（臨近Agent鄰居的Agent）來獲得批量折扣。聯(lián)盟形成與成本分?jǐn)傄?guī)則應(yīng)該給在聯(lián)盟中的Agent提供激勵(lì)使其不是被強(qiáng)迫使其留在聯(lián)盟中，這是作為個(gè)人理性(IR)與預(yù)算平衡(BB)的合理結(jié)果。根據(jù)IR，聯(lián)盟成員的所有個(gè)人花費(fèi)都不大于相應(yīng)底價(jià)。與此同時(shí)在BB中，聯(lián)盟掌管在聯(lián)盟中產(chǎn)生的花費(fèi)。因此，agent的花費(fèi)是其底價(jià)的非減函數(shù)。
　　SCF的半最優(yōu)解決方案算法應(yīng)根據(jù)其核心保證一個(gè)高效的收

37、益分配結(jié)果相對于其他解決方案，包括:1）導(dǎo)致最佳收益的最優(yōu)算法;2）通過考慮搜索成本作為一個(gè)參數(shù)來影響穩(wěn)定最優(yōu)聯(lián)盟的搜索方法。另外，在核心中形成穩(wěn)定聯(lián)盟依賴于聯(lián)盟內(nèi)的成本分?jǐn)傄?guī)則。根據(jù)提出的成本分?jǐn)傄?guī)則，本文通過實(shí)驗(yàn)證明SCF能夠獲得以95％到99.98％的比率接近最佳收益的平均收益。同時(shí)在考慮搜索成本作為一個(gè)參數(shù)影響最有價(jià)值穩(wěn)定聯(lián)盟的決定時(shí)，它比平均的聯(lián)盟價(jià)值高了9％。在考慮搜索成本時(shí)，本文提出的SCF算法依據(jù)Agents數(shù)量的不同也

38、相應(yīng)減少了15％至24％的平均處理時(shí)間，并且以比最優(yōu)時(shí)間快不少于75％的時(shí)間證明該方法形成穩(wěn)定聯(lián)盟的效率。這樣的解決方案的實(shí)驗(yàn)結(jié)果表明，Agent更傾向于把它們的決策建立在價(jià)格優(yōu)勢、能夠達(dá)到的折扣數(shù)以及它們之中公平的收益分配上，由此，本文提出的半最優(yōu)解決方案通過最大化可行聯(lián)盟的價(jià)值來搜索最有價(jià)值穩(wěn)定聯(lián)盟，該方案在核心也應(yīng)該是穩(wěn)定的。
　　綜上所述，本文為多Agent系統(tǒng)中聯(lián)盟形成提出了一系列新型的算法，它們一個(gè)共同的特點(diǎn)是有效且快