基于改进的遗传算法求解可满足性问题

Solving Satisfiability Problem Based on Modified Genetic Algorithm

遗传算法(GA)是由Holland提出的一种基于进化论的仿生算法,非常适于求解最优化问题。为了更好地利用SGA求解SAT问题,在将SAT问题等价转换为{0,1}n上的多项式是否存在零点的判断问题基础上,将局部搜索算法(LSA)与SGA相结合,给出一种求解3-SAT问题的改进混合遗传算法(MHGA),并通过对随机大规模3-SAT问题实例的实际求解验证了MHGA的可行性与有效性。

Genetic algorithm （GA） is a kind of intelligence algorithm based on the theory of evolution proposed by Holland, which is suitable for solving optimization problem. For solving the Satisfiability problem （SAT） using SGA, combines SGA with Local Search Algorithm, proposes a modified hybrid genetic algorithm （MHGA） to solve 3-SAT. First, transformes 3- SAT to the computation problem of polynomial function on {0, 1}^n, whether exists a zero point. The results of numerical computation show that MHGA is feasible and effective for solving hard SAT.