东北大学学报:自然科学版 ›› 2014, Vol. 35 ›› Issue (1): 29-32.DOI: 10.12068/j.issn.1005-3026.2014.01.007
郭莹,张长胜,张斌
GUO Ying, ZHANG Changsheng, ZHANG Bin
摘要: 针对SAT问题,提出一种求解该问题的离散人工蜂群算法——ABCSAT算法,建立了相应的优化算法模型,解决了问题编码和转化、适应度函数、蜜蜂觅食策略、离散操作等关键问题.不同于处理连续优化问题,ABCSAT将适应度函数定义为当前不可满足子句数.根据问题的特点设计了多种觅食策略,并利用各子句和变量之间约束关系的启发式信息对各阶段的候选解进行离散操作.最后在标准SATLIB测试集上对提出的算法进行了测试并与相关算法进行了比较,结果验证了ABCSAT算法在中小规模SAT问题上的有效性,表明算法能更加有效地解决该问题.
中图分类号: