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

摘要

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