基于MACR和CAL启发式的求差知识编译算法

doi:10.3969/j.issn.0372-2112.2020.02.009

电子学报 ›› 2020, Vol. 48 ›› Issue (2): 285-290.DOI: 10.3969/j.issn.0372-2112.2020.02.009

基于MACR和CAL启发式的求差知识编译算法

牛当当^1,3, 吕帅^2,5, 王金艳⁶, 刘斌^1,3,4

1. 西北农林科技大学信息工程学院, 陕西杨凌 712100;
2. 吉林大学计算机科学与技术学院, 吉林长春 130012;
3. 陕西省农业信息感知与智能服务重点实验室(西北农林科技大学), 陕西杨凌 712100;
4. 农业农村部农业物联网重点实验室(西北农林科技大学), 陕西杨凌 712100;
5. 符号计算与知识工程教育部重点实验室(吉林大学), 吉林长春 130012;
6. 广西师范大学计算机科学与信息工程学院, 广西桂林 541004

收稿日期:2019-04-26 修回日期:2019-09-09 出版日期:2020-02-25
- 通讯作者:
- 牛当当
- 作者简介:
- 吕帅男,1981年7月出生,吉林公主岭人.现为吉林大学计算机科学与技术学院副教授,博士生导师,主要研究方向为人工智能、智能规划与自动推理.E-mail:lus@jlu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61602388，No.61763003）; 吉林省科技发展计划资助项目 (No.20180101053JC）; 陕西省自然科学基础研究计划项目 (No.2017JM6059）; 中央高校基本科研业务费专项资金 (No.2452019064）; 中国博士后科学基金 (No.2017M613216）; 陕西省博士后基金 (No.2016BSHEDZZ121）; 陕西省重点研发计划项目 (No.2019ZDLNY07-06-01）; 广西省自然科学基金 (No.2016GXNSFAA380192）; 西北农林科技大学博士科研启动基金 (No.Z109021813）; 广西多源信息挖掘与安全重点实验室开放基金 (No.MIMS19-05）

Knowledge Compilation Algorithm of Computing Difference Based on MACR Heuristics and CAL Heuristics

NIU Dang-dang^1,3, LV Shuai^2,5, WANG Jin-yan⁶, LIU Bin^1,3,4

1. College of Information Engineering, Northwest A&F University, Yangling, Shaanxi 712100, China;
2. College of Computer Science and Technology, Jilin University, Changchun, Jilin 130012, China;
3. Shaanxi Key Laboratory of Agricultural Information Perception and Intelligent Service (Northwest A&F University), Yangling, Shaanxi 712100, China;
4. Key Laboratory of Agricultural Internet of Things, Ministry of Agriculture and Rural Affairs (Northwest A&F University), Yangling, Shaanxi 712100, China;
5. Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun, Jilin 130012, China;
6. School of Computer Science and Information Engineering, Guangxi Normal University, Guilin, Guangxi 541004, China

Received:2019-04-26 Revised:2019-09-09 Online:2020-02-25 Published:2020-02-25
- Corresponding author:
- NIU Dang-dang
- Supported by:
- National Natural Science Foundation of China (No.61602388, No.61763003); Science and Technology Development Project of Jilin Province (No.20180101053JC); Supported by the Natural Science Basis Research Plan in Shaanxi Province of China (No.2017JM6059); Fundamental Research Funds for the Central Universities (No.2452019064); China Postdoctoral Science Foundation (No.2017M613216); Postdoctoral Foundation of Shaanxi Province (No.2016BSHEDZZ121); Key Research and Development Program of Shaanxi Province (No.2019ZDLNY07-06-01); Natural Science Foundation of Guangxi Zhuang Autonomous Region, China (No.2016GXNSFAA380192); Doctoral Research Fund of Northwest A&F University (No.Z109021813); Open Fund for Guangxi Key Lab of Multi-source Information Mining and Security (No.MIMS19-05)

摘要/Abstract

摘要： DKCHER算法是基于超扩展规则的求差知识编译算法.本文首先研究了DKCHER算法的执行流程，并定义了互补量的概念，然后设计了启发式策略MACR（maximum complementary amount of clauses with middle result），用于动态选择与中间结果互补量最大的子句.针对互补展开过程，设计了动态启发式策略CAL（optimal sequence sorted by complementary amount of literals），将互补展开中的文字按照与输入公式互补量的大小进行排序并展开.将上述两种启发式策略与DKCHER算法相结合，分别设计了MACR_DKCHER算法、CAL_DKCHER算法和MACR_CAL_DKCHER算法.实验结果表明，MACR启发式策略能够提升DKCHER算法的编译效率和编译质量，编译效率最高可提升9倍，编译质量最高可提升1.9倍；CAL启发式策略在子句数和变量数比值较大的实例上，能够提高DKCHER算法的编译效率，但会降低DKCHER算法的编译质量；MACR_CAL启发式最高可将DKCHER算法的编译效率提高12倍，但会导致DKCHER算法的编译质量有所降低.

关键词: 知识编译, 扩展规则, 超扩展规则, EPCCL理论, 启发式策略

Abstract: DKCHER is a knowledge compilation algorithm of computing difference based on hyper extension rule. We study on the executing process of DKCHER algorithm in this paper, and define the concept of complementary amount. We design MACR (maximum complementary amount of clauses with middle result) heuristics based on complementary amount, which is used to dynamically select the clause of maximum complementary amount with middle result. For complementary unfolding in DKCHER, we design dynamic heuristics CAL (optimal sequence sorted by complementary amount of literals), which sort the literals in complementary unfolding based on their complementary amounts. Combining the above two heuristic methods with DKCHER, MACR_DKCHER algorithm, CAL_DKCHER algorithm and MACR_CAL_DKCHER algorithm are designed. Experimentally, MACR heuristics improves the compilation efficiency and compilation quality of DKCHER. MACR heuristics can improve the efficiency of DKCHER by 9 times in the best case. CAL heuristics can significantly improve the compilation efficiency of DKCHER on the instances with big ratio of clause number with variable number. MACR_CAL heuristics can improve the efficiency of DKCHER by 12 times in the best case. But MACR_CAL heuristics reduces the compilation quality of DKCHER.

Key words: knowledge compilation, extension rule, hyper extension rule, EPCCL theory, heuristic strategy

中图分类号:

TP301
TP181

牛当当, 吕帅, 王金艳, 等. 基于MACR和CAL启发式的求差知识编译算法[J]. 电子学报, 2020, 48(2): 285-290.

NIU Dang-dang, LV Shuai, WANG Jin-yan, et al. Knowledge Compilation Algorithm of Computing Difference Based on MACR Heuristics and CAL Heuristics[J]. Acta Electronica Sinica, 2020, 48(2): 285-290.

参考文献

[1] Newton J,Verna D.A theoretical and numerical analysis of the worst-case size of reduced ordered binary decision diagrams[J].ACM Transactions on Computational Logic,2019,20(1):6:1-6:36.
[2] Jabbour S,Ma Y,Raddaoui B,Sais L.Quantifying conflicts in propositional logic through prime implicates[J].International Journal of Approximate Reasoning,2017,89:27-40.
[3] Salhi Y.Approaches for enumerating all the essential prime implicants[A].In Proceedings of Artificial Intelligence:Methodology,Systems,and Applications-18th International Conference (AIMSA)[C].Varna,Bulgaria,2018.228-239.
[4] Uña D,Gange G,Schachte P,Stuckey PJ.Compiling CP subproblems to MDDs and d-DNNFs[J].Constraints,2019,24(1):56-93.
[5] Darwiche A,Marquis P.A knowledge compilation map[J].Journal of Artificial Intelligence Research,2002,17:229-264.
[6] Lai Y,Liu DY,Wang SS.Reduced ordered binary decision diagram with implied literals:A new knowledge compilation approach[J].Knowledge and Information Systems,2013,35(3):665-712.
[7] Lai Y,Liu DY,Yin MH.New canonical representations by augmenting OBDDs with conjunctive decomposition[J].Journal of Artificial Intelligence Research,2017,58:453-521.
[8] Lin H,Sun JG,Zhang YM.Theorem proving based on the extension rule[J].Journal of Automated Reasoning,2003,31(1):11-21.
[9] Lin H,Sun JG.Knowledge compilation using the extension rule[J].Journal of Automated Reasoning,2004,32(2):93-102.
[10] 谷文祥,王金艳,殷明浩.基于MCN和MO启发式策略的扩展规则知识编译方法[J].计算机研究与发展,2011,48(11):2064-2073. Gu WX,Wang JY,Yin MH.Knowledge compilation using extension rule based on MCN and MO heuristic strategies[J].Journal of Computer Research and Development,2011,48(11):2064-2073.(in Chinese)
[11] 刘大有,赖永,林海.C2E:一个高性能的EPCCL理论编译器[J].计算机学报,2013,36(6):1254-1260. Liu DY,Lai Y,Lin H.C2E:An EPCCL compiler with good performance[J].Chinese Journal of Computer,2013,36(6):1254-1260.(in Chinese)
[12] 刘磊,牛当当,吕帅.基于超扩展规则的知识编译方法[J].计算机学报,2016,39(8):1681-1696. Liu Lei,Niu Dang-Dang,Lü Shuai.Knowledge compilation methods based on the hyper extension rule[J].Chinese Journal of Computer,2016,39(8):1681-1696.(in Chinese)
[13] Niu DD,Liu L,Lü S.Knowledge compilation methods based on the clausal relevance and extension rule[J].Chinese Journal of Electronics,2018,27(5):1037-1042.
[14] Li HB,Liang YC,Zhang N,Guo JS,Xu D,Li ZS.Improving degree-based variable ordering heuristics for solving constraint satisfaction problems[J].Journal of Heuristics,2016,22(2):25-145.

基于MACR和CAL启发式的求差知识编译算法

Knowledge Compilation Algorithm of Computing Difference Based on MACR Heuristics and CAL Heuristics

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	王金艳, 胡春, 牛当当, 李先贤. 基于IAPS的扩展规则局部搜索算法[J]. 电子学报, 2020, 48(5): 899-905.
[2]	牛当当, 吕帅, 王金艳. 基于MOVR启发式的求差知识编译算法[J]. 电子学报, 2019, 47(11): 2299-2303.
[3]	牛当当, 刘磊, 吕帅. EPCCL理论的并行知识编译算法[J]. 电子学报, 2018, 46(3): 537-543.