基于IAPS的扩展规则局部搜索算法

作     者：王金艳 胡春 牛当当 李先贤 WANG Jin-yan;HU Chun;NIU Dang-dang;LI Xian-xian

作者机构：广西多源信息挖掘与安全重点实验室(广西师范大学)广西桂林541004 广西师范大学计算机科学与信息工程学院广西桂林541004 西北农林科技大学信息工程学院陕西杨凌712100 

出 版 物：《电子学报》 (Acta Electronica Sinica)

年 卷 期：2020年第48卷第5期

页      面：899-905页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金(No.61763003,No.61672176,No.61941201) 广西多源信息挖掘与安全重点实验室系统性研究课题基金(No.19-A-02-01) 广西多源信息挖掘与安全重点实验室开放基金(No.MIMS19-05) 广西高等学校千名中青年骨干教师培育计划 “八桂学者”工程专项经费资助项目 广西大数据智能与应用人才小高地 广西区域多源信息集成与智能处理协同创新中心。 

主　　题：扩展规则 自动推理 局部搜索 格局检测 

摘      要：ERACC(Extension Rule Based on Accurate Configuration Checking)算法由杨洋等人基于扩展规则和格局检测提出,具有较高的推理效率.为进一步提高ERACC算法在大规模SAT(Satisfiability)问题求解上的性能,本文在搜索由极大项组成的空间时,首先利用IMOM(Improved Maximum Occurrences on Clauses of Maximum Size)思想生成初始极大项,接着设计了适用于扩展规则推理的CCA_ER(Configuration Checking with Aspiration for Extension Rule-Based Reasoning)启发式策略,为极大项中格局信息未发生变化的变量对应文字提供一定的翻转机会.同时,为进一步提高扩展规则推理算法在k-SAT问题求解上的性能,设计了适用于扩展规则推理的PAWS_ER(Pure Additive Weighting Scheme for Extension Rule-Based Reasoning)策略,并且给出变量的Subscore_ER(Subscore for Extension Rule-Based Reasoning),CScore_ER(Comprehensive Score for Extension Rule-Based Reasoning)和HScore_ER(Hybrid Score for Extension Rule-Based Reasoning)属性.在此基础上,提出了ERACC_IAPS(ERACC with IMOM,CCA_ER,PAWS_ER and Subscore_ER)和CERACC_IAPS(ERACC with IMOM,CCA_ER,PAWS_ER,CScore_ER and HScore_ER)算法.实验结果表明:ERACC_IAPS和CERACC_IAPS算法的效率明显优于ERACC算法,最高可将其求解效率提高1000多倍.