| 求解24数码问题的改进遗传退火算法 |
| |
| 引用本文： | 杨卫波,王万良. 求解24数码问题的改进遗传退火算法[J]. 计算机工程与应用, 2011, 47(15): 9-11. DOI: 10.3778/j.issn.1002-8331.2011.15.003 |
| |
| 作者姓名： | 杨卫波 王万良 |
| |
| 作者单位： | 1.温州大学 物理与电子信息工程学院，浙江 温州 325035 2.浙江工业大学 信息工程学院，杭州 310023 |
| |
| 基金项目： | 温州市科技计划项目,浙江省重大科技专项项目 |
| |
| 摘 要： | 针对具有巨大搜索解空间的24数码问题，提出了一种基于改进遗传模拟退火算法的求解方法。依据问题特征，设计了个体编码方法、高效的适应度评价函数和遗传操作算子，通过在遗传算法中引入模拟退火的Boltzmann更新机制，克服了传统遗传算法易于过早收敛和易于“卡住”陷入局部极小的问题。仿真实验结果表明，提出的算法能够快速搜索到问题的解，算法对其他组合优化问题也具有应用价值。
|
| 关 键 词： | 数码问题 遗传算法 模拟退火算法 Manhattan距离 |
| 修稿时间： | |
Improved genetic simulated annealing algorithm for 24 puzzle problem |
| |
| YANG Weibo,WANG Wanliang. Improved genetic simulated annealing algorithm for 24 puzzle problem[J]. Computer Engineering and Applications, 2011, 47(15): 9-11. DOI: 10.3778/j.issn.1002-8331.2011.15.003 |
| |
| Authors: | YANG Weibo WANG Wanliang |
| |
| Affiliation: | 1.College of Physics & Electronic Information Engineering，Wenzhou University，Wenzhou，Zhejiang 325035，China 2.College of Information Engineering，Zhejiang University of Technology，Hangzhou 310023，China |
| |
| Abstract: | Hybrid genetic simulated annealing algorithm is proposed for 24 puzzle problem which has a huge solution search space.According to characteristics of the problem, the algorithm designs individual encoding methods, efficient fitness evaluation function and genetic operators.It introduces Boltzmann upgrade mechanism into traditional genetic algorithm to overcome premature convergence problem and local minima.Computational results show that the algorithm can quickly find optimal solution.The proposed algorithm can also be applied to other combinatorial optimization problems. |
| |
| Keywords: | puzzle problem Genetic Algorithm （GA） Simulated Annealing algorithm（SA） Manhattan distance |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
