[發(fā)明專(zhuān)利]一種基于MaxSAT最優(yōu)解的聯(lián)盟結(jié)構(gòu)形成方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810040196.5
• 申請(qǐng)日: 2018-01-16
• 公開(kāi)（公告）號(hào): CN108256649A
• 公開(kāi)（公告）日: 2018-07-06
• 發(fā)明（設(shè)計(jì)）人: 廖曉鵑;劉明哲;張輝;李冬芬
• 申請(qǐng)（專(zhuān)利權(quán)）人: 成都理工大學(xué)
• 主分類(lèi)號(hào): G06N99/00
• 分類(lèi)號(hào): G06N99/00
• 代理公司: 成都眾恒智合專(zhuān)利代理事務(wù)所(普通合伙) 51239
• 代理人: 劉華平

本發(fā)明公開(kāi)了一種基于MaxSAT最優(yōu)解的聯(lián)盟結(jié)構(gòu)形成方法，該方法包括如下步驟：確定CSG問(wèn)題，用MC?nets框架將CSG問(wèn)題的特征函數(shù)表示為一組規(guī)則的集合；將集合中每?jī)蓚€(gè)規(guī)則之間的關(guān)系劃分為四種互斥的類(lèi)型；將集合分為互斥的游離集與核心集，分別在其上構(gòu)造一個(gè)CSG問(wèn)題的子問(wèn)題；將游離集上所有帶有正值權(quán)重的規(guī)則集合表示最優(yōu)解；將核心集上的每個(gè)規(guī)則編碼為軟子句，規(guī)則間的關(guān)系編碼為硬子句，從而將核心集上的子問(wèn)題轉(zhuǎn)化為可求解的表達(dá)式，并通過(guò)MaxSAT解算器計(jì)算出最優(yōu)解；合并最優(yōu)解，得到CSG問(wèn)題的最優(yōu)解。本發(fā)明具有很強(qiáng)的可擴(kuò)展性和執(zhí)行效率，具有很高的實(shí)用價(jià)值和推廣價(jià)值。

技術(shù)領(lǐng)域

本發(fā)明屬于本發(fā)明屬于計(jì)算機(jī)應(yīng)用領(lǐng)域，具體涉及一種基于MaxSAT最優(yōu)解的聯(lián)盟結(jié)構(gòu)形成方法。

背景技術(shù)

聯(lián)盟形成是多Agent系統(tǒng)(Multi-Agent System:MAS)中的一種重要協(xié)作方式。在MAS中，主體通過(guò)形成聯(lián)盟的方式進(jìn)行合作，以最小的代價(jià)執(zhí)行任務(wù)，從而獲得最大的收益。聯(lián)盟結(jié)構(gòu)形成問(wèn)題(Coalition Structure Generation:CSG)是聯(lián)盟形成中的關(guān)鍵問(wèn)題之一，其目標(biāo)是將一個(gè)集合劃分為相互獨(dú)立的聯(lián)盟，使得聯(lián)盟的總收益最大，通常情況下，聯(lián)盟的收益由特征函數(shù)進(jìn)行表達(dá)，在包含n個(gè)成員的集合中，要表示所有可能的聯(lián)盟收益則需要O(2ⁿ)個(gè)特征函數(shù)，引入的特征函數(shù)較多，針對(duì)此問(wèn)題，具有更強(qiáng)表達(dá)能力的MC-nets框架被提出，并將CSG問(wèn)題中聯(lián)盟與收益的關(guān)系表示為一組帶實(shí)數(shù)權(quán)重的規(guī)則，結(jié)合Ohta與Ueda等人的理論研究，可通過(guò)MaxSAT解算器對(duì)整個(gè)集合進(jìn)行求解，但在求解的過(guò)程中需要引入大量冗余子句，尤其是在規(guī)模為n的CSG問(wèn)題中，因關(guān)系的傳遞性而引入的子句數(shù)目高達(dá)O(n³)，大量的冗余子句使得MaxSAT解算器在求解問(wèn)題時(shí)不得不進(jìn)行額外的推理步驟，這在一定程度上增加了計(jì)算成本，同時(shí)降低了求解效率，不利于大規(guī)模推廣。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種基于MaxSAT最優(yōu)解的聯(lián)盟結(jié)構(gòu)形成方法，主要解決現(xiàn)有技術(shù)中存在的現(xiàn)有MaxSAT編碼引入冗余子句數(shù)量太多，增加了計(jì)算成本的同時(shí)造成求解效率低下的問(wèn)題。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用的技術(shù)方案如下：

一種基于MaxSAT最優(yōu)解的聯(lián)盟結(jié)構(gòu)形成方法，包括如下步驟：

(S1)確定聯(lián)盟結(jié)構(gòu)形成問(wèn)題CSG問(wèn)題，用MC-nets框架將CSG問(wèn)題的特征函數(shù)表示為一組帶權(quán)重的規(guī)則的集合R；

(S2)將集合R中每?jī)蓚€(gè)規(guī)則之間的關(guān)系劃分為四種互斥的類(lèi)型，并且每?jī)蓚€(gè)規(guī)則間的關(guān)系有且僅能滿(mǎn)足其中一種類(lèi)型；

(S3)將所有規(guī)則中同時(shí)滿(mǎn)足條件的規(guī)則的集合表示為游離集R_f，將游離集R_f在集合R上的補(bǔ)集表示為核心集R_c，分別在游離集R_f和核心集R_c上構(gòu)造一個(gè)CSG問(wèn)題的子問(wèn)題；

(S4)針對(duì)游離集R_f上的子問(wèn)題，將其上所有帶有正值權(quán)重的規(guī)則集合表示為游離集R_f的最優(yōu)解

(S5)針對(duì)核心集R_c上的子問(wèn)題，將核心集R_c上的每個(gè)規(guī)則編碼為軟子句，然后將規(guī)則間的關(guān)系編碼為硬子句，從而將核心集R_c上的CSG問(wèn)題的子問(wèn)題轉(zhuǎn)化為可求解的MaxSAT問(wèn)題的表達(dá)式，并通過(guò)MaxSAT解算器計(jì)算出核心集R_c上的最優(yōu)解

(S6)將游離集R_f和核心集R_c上的最優(yōu)解進(jìn)行合并，得到CSG問(wèn)題的最優(yōu)解R^*，即R^*＝R^*_f∪R^*_c。