基于子句权重学习的求解SAT问题的遗传算法

摘要：

该文提出了一种求解SAT问题的改进遗传算法(SAT-WAGA).SAT-WAGA算法有多个改进性特点:将SAT问题的结构信息量化为子句权重,增加了学习算子和判定早熟参数,学习算子能根据求解过程中的动态信息对子句权重进行调整,以便防止遗传进程的早熟,同时,算法还采用了最优染色体保存策略,防止进化过程的发散.该文最后描述了实现包括SAT-WAGA等多个算法的实验系统,对选择最佳早熟判定参数值给出了一些有效的建议.实验结果表明:与一般遗传算法相比,SAT-WAGA算法在求解速度、成功率和求解问题的规模等方面都有明显的改善.

关键词：SAT问题、遗传算法、子句权重、早熟

所属期刊栏目：28

分类号：TP301(计算技术、计算机技术)

资助基金："智能规划及其应用研究"和中山大学校科研和教改项目

在线出版日期：2005-11-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1476-1482