An Extension Rule Algorithm Based on Local Search with IAPS Strategies

WANG Jin-yan; HU Chun; NIU Dang-dang; LI Xian-xian

doi:10.3969/j.issn.0372-2112.2020.05.009

您当前的位置：

首页 >

文章列表页 >

An Extension Rule Algorithm Based on Local Search with IAPS Strategies

更新时间：2025-07-16

- An Extension Rule Algorithm Based on Local Search with IAPS Strategies
- Acta Electronica Sinica Vol. 48, Issue 5, Pages: 899-905(2020)
- 作者机构：
  
  1. 广西多源信息挖掘与安全重点实验室(广西师范大学),广西,桂林,541004
  2. 西北农林科技大学信息工程学院, 陕西杨凌,712100
  4. 广西师范大学计算机科学与信息工程学院,广西,桂林,541004
  5. 西北农林科技大学信息工程学院陕西杨凌,712100
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2020.05.009
  CLC： TP181TP301
- Published Online：25 May 2020，
  
  Published：2020
- 稿件说明：
移动端阅览
WANG Jin-yan, HU Chun, NIU Dang-dang, et al. An Extension Rule Algorithm Based on Local Search with IAPS Strategies[J]. Acta Electronica Sinica, 2020, 48(5): 899-905.
DOI：

WANG Jin-yan, HU Chun, NIU Dang-dang, et al. An Extension Rule Algorithm Based on Local Search with IAPS Strategies[J]. Acta Electronica Sinica, 2020, 48(5): 899-905. DOI： 10.3969/j.issn.0372-2112.2020.05.009.

摘要

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）启发式策略，为极大项中格局信息未发生变化的变量对应文字提供一定的翻转机会.同时，为进一步提高扩展规则推理算法在

-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多倍.

Abstract

The algorithm ERACC proposed by Yang et al. has high reasoning efficiency. To further improve performance o

f ERACC algorithm in solving large-scale SAT problem

firstly

IMOM is used to generate the initial maximum term. Then a CCA_ER is designed to provide certain opportunities for the literals of variables whose configurations have not been changed since their last flips in maximal terms. At the same time

in order to further improve the performance of extension rule-based reasoning algorithm on the

-SAT problem

PAWS_ER is designed. Then the

Subscore_ER

CScore_ER

and

HScore_ER

attributes for variables are further designed. Finally

ERACC_IAPS and CERACC_ER algorithms are proposed. The experimental results show that the efficiency of ERACC_IAPS and CERACC_IAPS algorithms is obviously better than that of ERACC algorithm

and the maximum solution efficiency can be improved by more than 1000 times.

关键词

Keywords

references

Views

123

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on Feature Selection Based on Hybrid Evolutionary Algorithm

Internet Routing Optimization Control Algorithm with Multiple Objectives

An Unsatisfiable Subformula Computing Algorithm to Accelerate FPGA Routing

A Multi-Objective Discrete Particle Swarm Optimization Algorithm for SLA-Aware Service Composition Problem

Test Case Generation Based on Orthogonal Exploration and Particle Swarm Optimization

Related Author

GAO Hui-min

WANG Yun-he

BIAN Chuang

LI Xiang-tao

ZENG Zhi-min

DING Wei

BAI Dong

LIU Hong

Related Institution

School of Artificial Intelligence， Jilin University

School of Artificial Intelligence， Hebei University of Technology

Satellite Communication LabPeking UniversityBeijing 100871China

Broadband Communication Network Lab,Beijing University of Posts and Telecomm

Satellite Communication Lab,Peking University

⁰