| 求解SAT问题的退火遗传算法 |
| |
| 引用本文： | 孙强,马光胜,刘晓晓.求解SAT问题的退火遗传算法[J].小型微型计算机系统,2008,29(7). |
| |
| 作者姓名： | 孙强 马光胜 刘晓晓 |
| |
| 作者单位： | 哈尔滨工程大学,计算机科学与技术学院,黑龙江,哈尔滨,150001 |
| |
| 摘 要： | 提出一种将遗传算法与模拟退火算法相结合的SAT问题求解算法SAT-SAGA.该算法以遗传算法流程为主体,并把模拟退火机制融入其中,用以调整优化群体,防止陷入局部最优和出现早熟;在进化过程中算法采用了最优染色体保存策略,防止进化过程的发散.实验表明:该算法在求解速度、成功率和求解问题的规模等方面都有明显的改善.
|
| 关 键 词： | SAT问题 遗传算法 模拟退火算法 求解问题 退火遗传算法 Problem Genetic Algorithm Annealing 改善 规模 成功率 速度 实验 保存策略 染色体 进化过程 最优 局部 优化群体 调整 退火机制 模拟退火算法 主体 |
Simulated Annealing Genetic Algorithm for Solving SAT Problem |
| |
| SUN Qiang,MA Guang-sheng,LIU Xiao-xiao.Simulated Annealing Genetic Algorithm for Solving SAT Problem[J].Mini-micro Systems,2008,29(7). |
| |
| Authors: | SUN Qiang MA Guang-sheng LIU Xiao-xiao |
| |
| Affiliation: | SUN Qiang,MA Guang-sheng,LIU Xiao-xiao(Department of Computer Science , Technology,Harbin Engineering University,Harbin 150001,China) |
| |
| Abstract: | A novel algorithm,SAT-SAGA,is proposed for solving SAT problems based on the combination of the genetic algorithm and simulated annealing algorithm.The genetic algorithms are served as the main flow of the new algorithms which involve the mechanism of simulated annealing to adjust the optimization population,avoid trapping in local optimum and prevent precocity.The strategy of keeping the best chromosomes prevents the problem of convergence in the evolution iteration.The experimental results show that the S... |
| |
| Keywords: | SAT problem genetic algorithm simulated annealing algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
