A comparative analysis and improvement of MaxSAT encodings for coalition structure generation under MC-nets
A comparative analysis and improvement of MaxSAT encodings for coalition structure generation under MC-nets
复制标题
MC-nets下联盟结构生成MaxSAT编码的比较分析与改进
DOI：
10.1093/logcom/exz017
复制
发表时间：
2019
影响因子：
0.7
通讯作者：
Miyuki Koshimura
中科院分区：
文献类型：
--
作者：
Xiaojuan Liao;Miyuki Koshimura
联盟结构生成（CSG）是多智能体系统中联盟博弈和加权部分MaxSAT（WPM）编码的主要研究内容之一，即基于规则关系的WPM（RWPM）和基于智能体关系的WPM（AWPM），这两种编码都是解决CSG问题的有效方法。现有的研究表明，AWPM优于RWPM，因为它实现了更紧凑的编码，它生成的变量和子句比RWPM少。然而，在本文中，我们专注于一个特殊的情况下，这两种编码生成相同数量的变量和子句。实验结果表明，RWPM在性能上比AWPM有明显的优势，这引起了我们的兴趣。我们挖掘了深层原因，发现这是冗余编码时的传递律在RWPM，导致这种情况。最后，我们删除了冗余条款的RWPM的传递律，并开发了一个改进的RWPM与细化传递律来解决CSG问题。实验表明，改进的编码是更紧凑和有效的比以前的WPM编码。
Coalition structure generation (CSG) is one of the main research issues in the use of coalitional games in multiagent systems and weighted partial MaxSAT (WPM) encodings, i.e. rule relation-based WPM (RWPM) and agent relation-based WPM (AWPM), which are efficient for solving the CSG problem. Existing studies show that AWPM surpasses RWPM since it achieves more compact encoding; it generates fewer variables and clauses than RWPM. However, in this paper, we focus on a special case in which the two encodings generate identical numbers of variables and clauses. Experiments show that RWPM surprisingly has a dominant advantage over AWPM, which aroused our interest. We exploit the deep-rooted reason and find that it is the redundancy when encoding transitive laws in RWPM that leads to this situation. Finally, we remove redundant clauses for transitive laws in RWPM and develop an improved RWPM with refined transitive laws to solve the CSG problem. Experiments demonstrate that refined encoding is more compact and efficient than previous WPM encodings.