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

被引:9
作者
田奕
刘涛
李国杰
机构
[1] 国家智能计算机研究开发中心
基金
国家攀登计划;
关键词
SAT问题; 遗传算法; 个体进化; 局部搜索; 回溯算法;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
本文将可满足性问题(SAT)转化为一个优化问题,应用遗传算法来求解.为了提高遗传算法的求解效率,我们提出并采用了一种新的个体进化策略.这种个体进化策略不能用简单的爬山过程来概括,它允许个体进行多次爬山.在求解随机3-SAT问题时,这种遗传算法表现了优于同类算法的良好性能.
引用
收藏
页码:209 / 212
页数:4
相关论文
共 1 条
[1]  
一种求解合取范式可满足性问题的数学物理方法[J]. 李未,黄文奇.中国科学(A辑 数学 物理学 天文学 技术科学). 1994(11)