一种结合结构特征求解诊断问题的PMS方法

发布时间：2021-09-07 17:11

　　部分最大可满足性问题（partial maximum satisfiability problem, PMS）是最大可满足性问题（maximum satisfiability problem, MaxSAT）的泛化问题,在很多领域中得到广泛应用.目前,在工业诊断实例方面PMS求解仍有待改进,在对基于随机搜索的PMS算法深入研究基础上,本文首次提出一种结合结构特征的随机搜索方法 （structure characteristics partial MaxSAT, SCPMS）.首先,依据单元传播规则结合问题结构特征逐步将PMS问题中硬单元子句分成两部分,从而构造出因缺乏部分硬单元子句使得问题可满足的子问题;提出结合结构特征的随机搜索指导策略,对新的子问题再次利用单元传播找出原问题中的硬单元子句中硬阻塞变量,再结合子句特征翻转相应软阻塞变量,从而提高随机搜索的求解效率.实验结果表明,提出的SCPMS与最新的两个算法DeciDist和DistUp相比,在基于模型诊断问题（model-based diagnosis, MBD）的工业实例上, SCPMS求得的不满足软子句数有较大程度的减少. 

【文章来源】：中国科学:信息科学. 2019,49(06)北大核心CSCD

【文章页数】：13 页


本文编号：3389933