计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (15): 9-11.

• 博士论坛 • 上一篇    下一篇

求解24数码问题的改进遗传退火算法

杨卫波1,2,王万良2   

  1. 1.温州大学 物理与电子信息工程学院,浙江 温州 325035
    2.浙江工业大学 信息工程学院,杭州 310023
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-21 发布日期:2011-05-21

Improved genetic simulated annealing algorithm for 24 puzzle problem

YANG Weibo1,2,WANG Wanliang2   

  1. 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
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-05-21 Published:2011-05-21

摘要: 针对具有巨大搜索解空间的24数码问题,提出了一种基于改进遗传模拟退火算法的求解方法。依据问题特征,设计了个体编码方法、高效的适应度评价函数和遗传操作算子,通过在遗传算法中引入模拟退火的Boltzmann更新机制,克服了传统遗传算法易于过早收敛和易于“卡住”陷入局部极小的问题。仿真实验结果表明,提出的算法能够快速搜索到问题的解,算法对其他组合优化问题也具有应用价值。

关键词: 数码问题, 遗传算法, 模拟退火算法, Manhattan距离

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.

Key words: puzzle problem, Genetic Algorithm(GA), Simulated Annealing algorithm(SA), Manhattan distance