求解可满足性问题的一种高效遗传算法

AN EFFICIENT GENETIC ALGORITHM FOR SOLVING SATISFIABILITY PROBLEM

本文将可满足性问题(SAT)转化为一个优化问题,应用遗传算法来求解.为了提高遗传算法的求解效率,我们提出并采用了一种新的个体进化策略.这种个体进化策略不能用简单的爬山过程来概括,它允许个体进行多次爬山.在求解随机3-SAT问题时,这种遗传算法表现了优于同类算法的良好性能.

In this paper, satisfiability (SAT) problem is transformed into an optimization problem, we use Genetic Algorithms (GA) to solve it. To improve the performance of GA, we propose a new strategy of individual evolution. This kind of strategy is not similar to simple hill-climbing, for it allows individuals to ' clirnb hill ' more than one time. This kind of GA shows a better performance for solving random 3-SAT problem.