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

来源期刊：东北大学学报(自然科学版)2014年第1期

论文作者：郭莹 张长胜 张斌

文章页码：29 - 74

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

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