东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2014, Vol. 35 ›› Issue (1): 29-32.DOI: 10.12068/j.issn.1005-3026.2014.01.007

• 信息与控制 • 上一篇    下一篇

一种求解SAT问题的人工蜂群算法

郭莹，张长胜，张斌   

  1. (东北大学 信息科学与工程学院， 辽宁 沈阳110819)
  • 收稿日期:2013-05-20 修回日期:2013-05-20 出版日期:2014-01-15 发布日期:2013-07-09
  • 通讯作者: 郭莹
  • 作者简介:郭莹(1979-)，女，山东泰安人，东北大学博士研究生；张斌(1964-)，男，辽宁本溪人，东北大学教授，博士生导师.
  • 基金资助:
    国家自然科学基金资助项目(61073062，61100090)；中央高校基本科研业务费专项资金资助项目(N11024006).

An Artificial Bee Colony Algorithm for Solving SAT Problem

GUO Ying， ZHANG Changsheng， ZHANG Bin   

  1. School of Information Science & Engineering， Northeastern University， Shenyang 110819， China.
  • Received:2013-05-20 Revised:2013-05-20 Online:2014-01-15 Published:2013-07-09
  • Contact: ZHANG Bin
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

740

摘要： 针对SAT问题，提出一种求解该问题的离散人工蜂群算法——ABCSAT算法，建立了相应的优化算法模型，解决了问题编码和转化、适应度函数、蜜蜂觅食策略、离散操作等关键问题.不同于处理连续优化问题，ABCSAT将适应度函数定义为当前不可满足子句数.根据问题的特点设计了多种觅食策略，并利用各子句和变量之间约束关系的启发式信息对各阶段的候选解进行离散操作.最后在标准SATLIB测试集上对提出的算法进行了测试并与相关算法进行了比较，结果验证了ABCSAT算法在中小规模SAT问题上的有效性，表明算法能更加有效地解决该问题.

关键词: 可满足性问题, 人工蜂群算法, 遗传算法, 群体智能, 启发式策略

Abstract: For SAT problem， a discrete artificial bee colony algorithm named ABCSAT algorithm was proposed. The corresponding optimization model was established， and the key issues such as problem encoding and transition， fitness function， bee’s foraging strategy， discrete operation etc. were solved. Different from dealing with continual optimization problem， fitness function was defined as the number of unsatisfied clauses in the ABCSAT algorithm. According the character of SAT problem， series of foraging strategy were designed and discrete operations on candidate solutions were performed by using the heuristic information of constraint relations among each clause and variable. Through experiments on the standard SATLIB benchmarks， the algorithm was tested and compared with related algorithms. The results validated the effectiveness of ABCSAT algorithm on middle/smallscale SAT problems， and showed that the algorithm could be more effectively on solving this problem.

Key words: SAT, artificial bee colony algorithm, genetic algorithm, swarm intelligence, heuristic strategy

中图分类号: