給定限界勢結(jié)構(gòu)生成算法的改進?

李少芳，車 艷

(莆田學(xué)院信息工程學(xué)院，福建莆田 351100)

給定限界勢結(jié)構(gòu)生成算法的改進?

李少芳?，車 艷

(莆田學(xué)院信息工程學(xué)院，福建莆田 351100)

尋求最優(yōu)聯(lián)盟結(jié)構(gòu)是NP-完全的，建立限界k＝n/2的最小搜索是搜索聯(lián)盟結(jié)構(gòu)圖的最底二層及頂層，在最小搜索之后，不同算法采用不同的搜索單位和路徑進行有選擇地部分搜索，以盡快達到給定限界值。在實際應(yīng)用中，充分利用同勢的兩個聯(lián)盟同值或值相差不大的特征，研究最優(yōu)勢結(jié)構(gòu)生改進算法效率。文中通過分析勢結(jié)構(gòu)間的關(guān)系，指出了給定限界的勢結(jié)構(gòu)生成算法中一些可以去除的冗余搜索集合，從兩個方面改進了算法，并進行了相關(guān)結(jié)果的證明。

勢結(jié)構(gòu)(CCS);給定限界;多agent系統(tǒng);算法改進

隨著信息產(chǎn)業(yè)和經(jīng)濟全球化的加速發(fā)展，科技的進步與創(chuàng)新大大推動了企業(yè)之間的合作。企業(yè)合作創(chuàng)新不僅可以降低風(fēng)險和減少成本，也能提高自身的創(chuàng)新能力，創(chuàng)造和開拓新市場，獲取單個企業(yè)無法達到的協(xié)同效應(yīng)。不同聯(lián)盟結(jié)構(gòu)下企業(yè)合作創(chuàng)新的利益分配問題是不同的。單個agent參加一個聯(lián)盟的動機是為了更有效地完成任務(wù)，增加收益。投標者往往將多個拍賣品進行組合競拍，既可以降低競拍成本，又可以通過不同的商品組合來產(chǎn)生更好的價值。組合拍賣是銀行不良資產(chǎn)的處置最有效率的方法[1]。在實際應(yīng)用中，同勢的兩個聯(lián)盟值相同或相差不大，例如，在任務(wù)分配問題中，根據(jù)不同的任務(wù)需要將員工分組，對于多數(shù)員工而言，被分配到哪一組區(qū)別并不大。因此，研究最優(yōu)勢結(jié)構(gòu)生成問題具有很好的實際應(yīng)用價值。

限界表示最壞情況下已搜索的局部最優(yōu)解和全局最優(yōu)解的距離。文[2]已經(jīng)證明搜索聯(lián)盟結(jié)構(gòu)圖的最底二層和頂層可以建立限界k＝n/2，這也表明限界k隨著n的增大而增大。在這之后，若沒有啟發(fā)信息，應(yīng)怎樣進行進一步的部分搜索來降低限界k呢?文[3]最早提出一種以層為單位以最少的搜索層數(shù)達到給定限界要求的最優(yōu)聯(lián)盟結(jié)構(gòu)生成算法。對于奇數(shù)限界k≥3，文[4]提出在搜索最底兩層及頂層后，需要進一步搜索最大聯(lián)盟的勢大于或等于「n(k-1)/(k+1)?的所有聯(lián)盟結(jié)構(gòu)。文[5]提出了基于勢結(jié)構(gòu)的搜索算法，其在搜索最底兩層及頂層后，只需進一步搜索CCS(n，k)所對應(yīng)的的所有聯(lián)盟結(jié)構(gòu)。這三個算法[3-5]采用了不同的搜索單位，都可以用于勢結(jié)構(gòu)生成。

1 聯(lián)盟結(jié)構(gòu)與勢結(jié)構(gòu)

設(shè)n個agent的集合A＝{a1，a2，…，an}，聯(lián)盟C是A的一個非空子集，聯(lián)盟C中agent的個數(shù)稱為聯(lián)盟C的勢。一個聯(lián)盟結(jié)構(gòu)CS是agent集的一個完全劃分，稱所有聯(lián)盟結(jié)構(gòu)的集合為M。設(shè)聯(lián)盟結(jié)構(gòu) CS有 p個聯(lián)盟 C1，C2，…Cp，且。令，，則把稱為勢結(jié)構(gòu)(CCS)。6個agent的勢結(jié)構(gòu)圖，如圖1所示。

圖1 6個agent的勢結(jié)構(gòu)圖

表1 4個agent的勢結(jié)構(gòu)及其對應(yīng)的聯(lián)盟結(jié)構(gòu)

在算法描述中，以勢結(jié)構(gòu){n1，n2，…，np}為搜索單位，指的是搜索{n1，n2，…，np}所對應(yīng)的所有聯(lián)盟結(jié)構(gòu)的集合。整數(shù)n的每一種劃分對應(yīng)一種勢結(jié)構(gòu)，例如正整數(shù)4有5種不同的劃分，4個agent存在5個勢結(jié)構(gòu)，它們與15個可能的聯(lián)盟結(jié)構(gòu)的對應(yīng)情況見表1。

2 勢結(jié)構(gòu)生成算法描述

定義1 取h＝?n/k」，余數(shù)m≡n mod k，顯然m＜k。若m≥h，令CCS(n，k)＝?，否則CCS(n，k)為滿足以下條件的所有勢結(jié)構(gòu)集合[5]:

(1)若m＝0，令s＝n1+n2+…+ni，滿足s≥h且s-ni＜h(ni≥2且ni+1＝1)；

(2)若m＝1，令s＝n1+n2+…+ni，滿足s≥h且s-ni＜h(ni≥2且ni+1＝1)，另外CCS(n，k)還包含{h，1，…，1}勢結(jié)構(gòu)；

(3)若m≥2，令s＝n1+n2+…+ni，滿足s≥h+1且s-ni＜h+1(n1＜h，ni≥2且 ni+1＝1)，另外 CCS (n，k)還包含{h，2，1，…，1}，…，{h，m，1，…，1}勢結(jié)構(gòu)。

例如:當n＝12，k＝3時，h＝4，m＝0；CCS (12，3)＝{{2，2，1，…，1}，{3，2，1，…，1}，{3，3，1，…，1}}；當n＝13，k＝3時，h＝4，m＝1；CCS (13，3)＝{{2，2，1，…，1}，{3，2，1，…，1}，{3，3，1，…，1}，{4，1，…，1}}；當n＝14，k＝3時，h＝4，m＝2；CCS(14，3)＝{{2，2，2，1，…，1}，{3，2，1，…，1}，{3，3，1，…，1}，{4，2，1，…，1}}。

算法描述如下:

Step 1 獲得所要求的限界k，搜索聯(lián)盟結(jié)構(gòu)圖的最底二層和頂層:L1，L2，Ln。若k≥「n/2?，轉(zhuǎn)Step 3；若1≤k＜2，搜索整個聯(lián)盟結(jié)構(gòu)圖，轉(zhuǎn)Step 3；

Step 2 搜索勢結(jié)構(gòu)集合CCS(n，k)(若CCS (n，k)為空，k←k-1，直到CCS(n，k)不為空)對應(yīng)的聯(lián)盟結(jié)構(gòu)；

Step 3 返回至今為止所得到的最優(yōu)的聯(lián)盟結(jié)構(gòu)。

有以下結(jié)果:

定理1 對給定的限界k(2≤k≤「n/2?-1)，若算法2剛搜索完勢結(jié)構(gòu)集合CCS(n，k)(非空)對應(yīng)的聯(lián)盟結(jié)構(gòu)，則限界為k。

3 算法改進

本節(jié)主要通過分析勢結(jié)構(gòu)生成算法中勢結(jié)構(gòu)間的關(guān)系，指出了該算法中一些可以去除的冗余搜索集合，從兩個方面改進了算法，并進行了相關(guān)結(jié)果的證明。

3.1 算法的第一個改進

設(shè)agent個數(shù)為n，給定限界k，2≤k≤「n/2?-1，設(shè)V為任一給定的特征函數(shù)，記最優(yōu)聯(lián)盟結(jié)構(gòu)CS?＝{C1，C2，…，Ct}，已搜索過的最優(yōu)聯(lián)盟結(jié)構(gòu)為CS?N，若t≤k，記CS?中值最大的聯(lián)盟為C?，則C?在L1，L2中已搜索過，因此，

從而限界是k。

下面設(shè)t＞k，討論算法的CCS(n，k)(參見第2節(jié)中定義1)中哪些勢結(jié)構(gòu)可以不搜，限界仍為k?

若CS?中大小為1的聯(lián)盟個數(shù)≥h，則它們分為一組；大小≥h的聯(lián)盟每個單獨分為一組。因此不失一般性，不妨假設(shè)CS?中每個聯(lián)盟的大?。糷，且聯(lián)盟大小為1的聯(lián)盟個數(shù) ＜h，即h-1≥

定理2 設(shè)h＝?n/k」，m＝n mod k，當m＝0時，n＝kh，若ik＜h-i(i≥1)，則算法的CCS(n，k)中sub s≥2h-2i的勢結(jié)構(gòu)可以不搜，限界仍為k。

證明 CS?中大小≥h-i的聯(lián)盟每個單獨分為一組，設(shè)有k1組，剩下的的聯(lián)盟將滿足s＝n1+n2+…+ ni，≥h且s-ni＜h(ni≥2且ni+1＝1)的聯(lián)盟分為一組，這樣的聯(lián)盟組數(shù)為k2，每組的聯(lián)盟大小之和≥h，余下的聯(lián)盟(如果有的話)分成一組，這最后一組的聯(lián)盟大小之和記為m?，顯然m?＜h。這k1+k2組中除了符合定理5所提條件的組不搜索外，其他每一組已被搜索過。

若k1＝0或m?＝0，則n＝kh≥k2h+m?，從而k2≤k，且若k2＝k，則m?＝0，這樣n最多分成k組，限界為k。

若k1≠0且m?≠0，由ik＜h-i，有

(k+1)(h-i)＞n＝kh≥k1(h-i)+k2h+m?≥(k1+k2)(h-i)+m?。

由(k+1)(h-i)＞(k1+k2)(h-i)+m?，得k1+k2＜k+1，即有k1+k2≤k。

若k1+k2＜k，則總共不超過k組，限界為k，下設(shè)k1+k2＝k，有(k+1)(h-i)＞k(h-i)+m?，即m?＜h-i。

取k1組中的最后一組聯(lián)盟，記為，則該組可與最后余下的聯(lián)盟大小之和為m?的組合并為一組，這新的一組聯(lián)盟大小之和＜2h-2i，已被搜索過。否則，若，則有

當m≠0時，算法3的CCS(n，k)中哪些勢結(jié)構(gòu)可以不搜，存在與定理2類似的結(jié)論，由此得出以下定理3。

定理3 設(shè)h＝?n/k」，m＝n mod k，當0≤m＜h時，對于算法中的CCS(n，k)，令sub s＝n1+n2，則當ik＜h-i-m-1時，sub s≥2h-2i-1的勢結(jié)構(gòu)可以不搜，限界仍為k；否則，當ik＜h-i-m時，sub s≥2h-2i的勢結(jié)構(gòu)可以不搜，限界仍為k。

不妨設(shè)t＞k，h＝?n/k」，m＝n mod k，n＝k·h+ m，我們希望將CS?中的t個聯(lián)盟分成至多k個組合，使每個組合均已搜索過，這樣限界就會≤k。證明過程類似于定理2，這里不再說明。

注意到，只要k＞0(實際上我們討論的是k≥2)，當ik+m＜h-i-1時，一定滿足ik+m＜h-i；對較小的i上式成立，則對較大的i上式也成立。舉例來說，當滿足3k＜h-4時，一定滿足2k＜h-3，k＜h-2，3k＜h-3，2k＜h-2和k＜h-1，因此，應(yīng)取滿足條件的最大的i值。

例如 當n＝50，k＝2時，h＝?50/2」＝25，m＝0，滿足8k＜h-8，不滿足8k＜h-9和9k＜h-9，算法的CCS(50，2)所包含的勢結(jié)構(gòu)中sub s≥2h-16＝34的勢結(jié)構(gòu)都可以不搜，即共64個勢結(jié)構(gòu){24，24，1，…，1}，…，{24，10，1，…，1}，{23，23，1，…，1}，…，{23，11，1，…，1}，{22，22，1，…，1}，…，{22，12，1，…，1}，{21，21，1，…，1}，…，{21，13，1，…，1}，{20，20，1，…，1}，…，{20，14，1，…，1}，{19，19，1，…，1}，…，{19，15，1，…，1}，{18，18，1，…，1}，…，{18，16，1…，1}，{17，17，1…，1}無須搜。

3.2 算法的第二個改進

給出n，k，h＝?n/k」，余數(shù)m＜k。 情況1:m≥h時，蘇射雄等人的算法為避免討論這種情況，令CCS(n，k)＝?，接著討論下一個較小的k(k從「n/2?-1到2)。當k變小，h＝?n/k」變大，逐步降低k，這可使得m＜h，變成情況2:m＜h。例如:當n＝100，k＝32時，h＝?100/32」＝3，m＝4，有m＞h，k從32逐次降到26時，h＝3，m＝22，CCS(n，k)均為空集，直到k＝25，h＝4，m＝0。

為使對k的調(diào)整一次到位，對情況1:m≥h，我們改進如下:取h?＝「n/k?，搜相應(yīng)的CCS?(n，k)，這時得到的限界為「n/h??不大于原來的k。例如:當n＝100，k＝32時，由于m≥h，取h?＝「100/32?＝4，搜相應(yīng)的CCS?(n，k)后，得到的限界k＝「100/4?＝25(小于給出的k＝32)，這樣可以一步調(diào)整到位。 又如:當n＝120，k＝11時，h＝「120/11?＝10，m＝10，有m＝h，CCS(n，k)為空集，當原算法k從11降到10時，h＝12，m＝0，搜相應(yīng)的CCS?(n，k)，達到限界k＝10，這也表明原算法對k＝11沒有給出解。這時我們改進的算法取h?＝「n/k?＝「120/11?＝11，搜相應(yīng)的CCS?(n，k)之后得到的限界k＝「n/h??＝「120/11?＝11(和所要求的限界k一樣)，這樣就給出了k＝11時的解，這樣就改進了原算法當m≥h時的不足:原算法CCS(n，k)為空集，無直接解。

4 相關(guān)算法的比較

對于給定的較小的限界要求k，算法在搜索完L1，L2和Ln層后，需要進一步搜索的勢結(jié)構(gòu)數(shù)的比較數(shù)據(jù)示例如下:

當n＝50，k＝3時，文[2]的算法需要搜索第28至49層共4507個勢結(jié)構(gòu)所對應(yīng)的聯(lián)盟結(jié)構(gòu)數(shù)。文[3]的算法需要搜索第28層共1002個勢結(jié)構(gòu)所對應(yīng)的聯(lián)盟結(jié)構(gòu)數(shù)。文[4]的算法需要搜索最大聯(lián)盟的勢≥25的9296個勢結(jié)構(gòu)所對應(yīng)的聯(lián)盟結(jié)構(gòu)數(shù)。文[5]的算法需要搜索257個勢結(jié)構(gòu)數(shù)，它們所對應(yīng)的聯(lián)盟結(jié)構(gòu)數(shù)為 s＝4488694148454579188284988，lg s＝24.6521。而改進后的算法減少的12個勢結(jié)構(gòu)為{15，15，1，…，1}，{15，14，1，…，1}，{15，13，1，…，1}，{15，12，1，…，1}，{15，11，1，…，1}，{15，10，1，…，1}，{14，14，1，…，1}，{14，13，1，…，1}，{14，12，1，…，1}，{14，11，1，…，1}，{13，13，1，…，1}，{13，12，1，…，1}，這些勢結(jié)構(gòu)對應(yīng)的聯(lián)盟結(jié)構(gòu)數(shù)為 s＝14236151842773330300000，lg s＝22.153393。

當n＝50，k＝2時，改進后的算法減少的64個勢結(jié)構(gòu)分別為{24，24，1，…，1}，…，{24，10，1，…，1}，{23，23，1，…，1}，…，{23，11，1，…，1}，{22，22，1，…，1}，…，{22，12，1，…，1}，{21，21，1，…，1}，…，{21，13，1，…，1}，{20，20，1，…，1}，…，{20，14，1，…，1}，{19，19，1，…，1}，…，{19，15，1，…，1}，{18，18，1，…，1}，…，{18，16，1…，1}，{17，17，1…，1}，這些勢結(jié)構(gòu)對應(yīng)的聯(lián)盟結(jié)構(gòu)數(shù)為s＝90145645776100288100000，lg s＝22.954945，而原算法需搜索的聯(lián)盟結(jié)構(gòu)數(shù)為 s＝340283128981380143981052949884594687517，lg s＝38.5318。當n＝100，k＝2時，改進后的算法減少了272個勢結(jié)構(gòu)，這里不再一一列出。

5 結(jié)語

在分布式傳感器網(wǎng)絡(luò)中，多個傳感器可以組成聯(lián)盟以共同跟蹤感興趣的目標。最優(yōu)聯(lián)盟結(jié)構(gòu)生成是聯(lián)盟形成中的一個關(guān)鍵問題。近年來，勢結(jié)構(gòu)生成算法[6]的研究工作有了一定進展。本文深刻分析了勢結(jié)構(gòu)間的關(guān)系，并論證了如何去除一些冗余的搜索，從兩個方面提出對文[5]中算法的改進，進一步完善了文[3]和[5]的算法對于m≥h情況的解，并給出相關(guān)結(jié)果的證明具有很好的理論意義和實用價值。今后的工作擬在已有成果的基礎(chǔ)上，進一步探討算法所構(gòu)造的勢結(jié)構(gòu)是否冗余，勢結(jié)構(gòu)每個所對應(yīng)的全部聯(lián)盟結(jié)構(gòu)是否都必須搜索，并且可以嘗試將勢結(jié)構(gòu)的有關(guān)算法思想應(yīng)用到組合拍賣、網(wǎng)格計算等實際應(yīng)用中，并考察除層和勢結(jié)構(gòu)外，是否可以構(gòu)造更小的搜索單位優(yōu)化現(xiàn)有聯(lián)盟結(jié)構(gòu)生成算法，使所搜索的聯(lián)盟結(jié)構(gòu)數(shù)進一步減少。也可以研究如何利用給定聯(lián)盟值[7-8]減少搜索空間，或者考慮引入群智能算法(遺傳算法、蟻群算法、粒子群算法等)來求解次優(yōu)聯(lián)盟結(jié)構(gòu)[9-10]。

[1]謝輝斯.基于組合拍賣處置我國國有銀行不良資產(chǎn)的研究[D].重慶:重慶師范大學(xué)，2013.

[2]Sandholm TW，Larson K，Andersson M，et al.Coalition structure generation with worst case guarantees[J].Artificial Intelligence，1999，111(1-2):209-238.

[3]胡山立，石純一.給定限界要求的聯(lián)盟結(jié)構(gòu)生成[J].計算機學(xué)報，2001，24(11):1285-1290.

[4]Dang V D，Jennings N R.Generating coalition structures with finite bound from the optimal guarantees[C]//In Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multi-Agent Systems(AAMAS2004)，New York，USA，564-571.

[5]SU Shexiong，HU Shanli，ZHENG Shengfu，et al.Coalition structure generation with given required bound based on cardinality structure[C]//In Proceedings of the 6th International Conference on Machine Learning and Cybernetics in Hong Kong，Hong Kong. 2007:2505-2510.

[6]李少芳，胡山立，石純一.一種基于勢結(jié)構(gòu)分組思想的任一時間聯(lián)盟結(jié)構(gòu)生成[J].計算機研究與發(fā)展，2011，48(11):2047-2054.

[7]劉驚雷，張偉，劉兆偉，等.聯(lián)盟結(jié)構(gòu)圖的性質(zhì)及應(yīng)用[J].計算機研究與發(fā)展，2011，48(4):602-609.

[8]Rahwan T，Jennings N R.An algorithm for distributing coalitional value calculations among cooperating agents[J].Artificial Intelligence，2007，171(8/9):535-567.

[9]Rahwan T，Ramchurn SD，Dang V D，et al.Near-optimal anytime coalition structure generation[C]//Proc of the 20th Int Joint Conf on Artificial Intelligence(IJCAI2007).San Francisco:Morgan Kaufmann，2007:2365-2371.

[10]Tang，P.and Sandholm，T.Approximating Optimal Combinatorial Auctions for Complements Using Restricted Welfare Maximization [C]//In Proceedings of the International Joint Conference on Artificial Intelligence(IJCAI)，2011.

(責(zé)任編輯:曾 晶)

Im provement of Cardinality Structure Generation Algorithm w ith Given Required Bound

LIShao fang?，CHE Yan

(College of Information Engineering，Putian University，Putian 351100，China)

Finding the optimal coalition structure is NP-complete.Theminimal search that can establish a bound k＝n/2 is searching the lowest two levels and the top level of the coalition structure graph.Afterminimal search，different algorithms adopt the different search units and path tomake selectively part search，as soon as possible to achieve a given bound value.In practice，making full use of the characters of the same or similar value in two coalitionswith the same cardinality to study themost optimal cardinality structure generation to improve algorithm efficiency.The paper analyzes the relations between cardinality structures，and points out some redundancy search set than can be removed in cardinality structure generation algorithm with given required bound，improves the algorithm from two aspects and proves the related result.

cardinality structure(CCS)；given required bound；multi-agents system；algorithm improvement

TP18

A

1000-5269(2016)04-0069-05

10.15958/j.cnki.gdxbzrb.2016.04.14

2015-10-24

福建省教育廳資助項目(JA15440)

李少芳(1971-)，女，副教授，碩士，研究方向:計算機算法，人工智能應(yīng)用基礎(chǔ)，多agent系統(tǒng)，Email:LSF9808＠163.com.

?通訊作者:李少芳，Email:LSF9808＠163.com.