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

• 作者: 凌应标 吴向军 姜云飞
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: SAT问题 遗传算法 子句权重 早熟
• 年，卷（期）: 2005,（9）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1476-1482
• 页数: 7页
• 分类号: TP301
• 字数: 6735字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2005.09.008

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姜云飞	中山大学信息科学与技术学院	84	1013	18.0	28.0
2	吴向军	中山大学信息科学与技术学院	13	156	7.0	12.0
3	凌应标	中山大学信息科学与技术学院	5	61	3.0	5.0