可满足性问题的高效遗传算法

摘要：

在本文中,首先给出一些相关定义和将SAT问题转换为一元函数求最大值的方法,然后阐述SAT-GA算法的基本思想,以及与算法相关的染色体编码、适应值函数、遗传算子的设计、早熟和发散的控制方法,简单分析了该算法的平均复杂度,最后对本文算法和其它算法进行了性能比较,结果表明:在求解同样测试条件下,SAT-GA在求解速度、成功率和求解能力等方面都要明显优于其它算法.

关键词： 计算机计算 遗传算法 适应值函数 遗传算子 命题逻辑

作者: 凌应标 吴向军

作者单位: 中山大学计算机科学系(广州)

会议类型: 国内会议

会议名称: 2003年全国理论计算机科学学术年会

会议地点: 青岛

会议语种:中文

页码: 167-171

在线出版日期: 2003-08-01（万方平台首次上网日期，不代表论文的发表时间）