Performance Analysis of Immune Inspired B-Cell Algorithm for the SAT Problem

XIA Xiao-yun; ZHOU Yu-ren

Chinese

您当前的位置：

首页 >

文章列表页 >

Performance Analysis of Immune Inspired B-Cell Algorithm for the SAT Problem

更新时间：2026-09-04

- Performance Analysis of Immune Inspired B-Cell Algorithm for the SAT Problem
- Vol. 33, Issue 7, Pages: 5-10(2016)
- 作者机构：
  
  1. 嘉兴学院机构数理与信息工程学院,浙江,嘉兴,314001
  2. 江西理工大学机构信息工程学院,江西,赣州,341000
  3. 中山大学数据科学与计算机学院,广东,广州,510006
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2016
- 稿件说明：
移动端阅览
夏小云, 周育人. 基于免疫B-Cell算法求解可满足性问题的性能分析[J]. 微电子学与计算机, 2016, 33(7): 5-10.

XIA Xiao-yun, ZHOU Yu-ren. Performance Analysis of Immune Inspired B-Cell Algorithm for the SAT Problem[J]. 2016, 33(7): 5-10.
夏小云, 周育人. 基于免疫B-Cell算法求解可满足性问题的性能分析[J]. 微电子学与计算机, 2016, 33(7): 5-10. DOI：

XIA Xiao-yun, ZHOU Yu-ren. Performance Analysis of Immune Inspired B-Cell Algorithm for the SAT Problem[J]. 2016, 33(7): 5-10. DOI：

摘要

可满足性问题(SAT) 是计算机科学和人工智能研究中的核心NP-完全问题.构造了两类SAT问题实例

易解和难解实例.从理论上分析了B-Cell算法求解该两个实例的运行时间

并证实了B-Cell算法在某些问题上有效而在一些问题上无效.进一步提出了一个简单的基于免疫的多目标优化算法(IBMO)

对于一个双目标的SAT问题

证明了IBMO能够有效地找到整个Pareto前沿.这些分析结果从理论上证实和说明了人工免疫系统的有效性.

Abstract

The satisfiability problem is a basic core NP-complete problem in computer science and artificial intelligence. We construct two classes of SAT instances

and analyze the runtime of the B-Cell algorithm for these two instances. We proved that there exist situations where the BCA is efficient or inefficient. On the other hand

we develop a simple immune-based multi-objective optimizer (IBMO) and reveal that IBMO can find the whole Pareto front for a bi-objective sat problem in expected polynomial runtime. These analysis results exemplify and strengthen the usefulness of artificial immune systems from a theoretical perspective.

关键词

Keywords

references

Jansen T, Oliveto P S, Zarges C. On the analysis of the immune-Inspired B-Cell algorithm for the vertex cover problem[C]//ICARIS 2011. Springer, Heidelberg, 2011: 117-131.

Garey M R, Johnson D S. Computers and intractability-a guide to the theory of NP-completeness[M]. New York, Freeman, 1979.

Baca Raton Dasgupta D, NIñO L F. Immunological computation: theory and applications[M]. Baca Raton: CRC Press, 2008.

Beame P, Kautz H, Sabharwa A. Towards understanding and harnessing the potential of clause learning[J]. Journal of Artificial Intelligence Research, 2004, 22(2): 319-335. DOI: 319

Cook S. The complexity of theorem-proving procedures[C]//Proc of the 3rd Ann. ACM Symp. on Theory of Computing, Assoc. Comput. Mach. New York, 1971: 151.

Neumann F, Witt C. Bioinspired computation in combinatorial optimization-algorithms and their computational complexity[M]. Series, Natural Computing Springer, 2010.

Jansen T, Zarges C. A theoretical analysis of immune inspired somatic contiguous hypermutations for function optimization[C]//Proc of the International Conference on Artificial Immune Systems, ICARIS. Berlin, Springer, 2009: 80-94.

Wegener I. Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions[C]//In Evolutionary Optimization. Norwell, USA, Kluwer Academic Publishers, 2002: 349-369.

Droste S, Jansen T, Tinnefeld K, et al. A new framework for the valuation of algorithms for black-box optimization[C]//Foundations of Genetic Algorithms 7 (FOGA). Morgan Kaufmann, San Francisco, CA, 2003: 253-270.

Kelsey J, Timmis J. Immune inspired somatic contiguous hypermutation for function optimization[C]//Genetic and Evolutionary Computation Conference. Heidelberg, Springer, 2003: 207-218.

HIirsch E A, Kojevnikov a. UnitWalk: A new SAT solver that uses local search guided by unit clause elimination[J]. Annals of Mathematics and Artificial Intelligence, 2005, 43(1): 91-111. DOI: 91

Jansen T, Zarges C. Computing longest common subsequences with the B-Cell algorithm[C]//Proc of the 11th International Conference on Artificial Immune Systems (ICARIS'12). Italy, Taormina, 2012: 111-124.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A feature-oriented context understanding and slice analysis network for tuberculosis detection

Aerial small object detection algorithm based on improved RT-DETR

Implementation and verification of a dual-chain power gating strategy for low power design

Research on the design of blockchain-based AI-generated content traceability framework

High gain stability high temperature operational amplifier based on reverse body bias

Related Author

No data

Related Institution

No data

AI问答

Postal code：100079
Tel：（010）53879206 Email：tmw@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09082226号-64 京公网安备11010602201714号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰