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

AN EFFICIENT GENETIC ALGORITHM FOR SOLVING SATISFIABILITY PROBLEM

作　　者：田奕[1] 刘涛[1] 李国杰[1] 

机构地区：[1]国家智能计算机研究开发中心,北京100080

出　　处：《模式识别与人工智能》1996年第3期209-212,共4页Pattern Recognition and Artificial Intelligence

基　　金：国家攀登计划支持项目

摘　　要：本文将可满足性问题(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.

关 键 词：遗传算法 可满足性 数理逻辑 机器学习 

分 类 号：O212[理学—概率论与数理统计]