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

Improved genetic simulated annealing algorithm for 24 puzzle problem

作　　者：杨卫波[1,2] 王万良[2] 

机构地区：[1]温州大学物理与电子信息工程学院,浙江温州325035 [2]浙江工业大学信息工程学院,杭州310023

出　　处：《计算机工程与应用》2011年第15期9-11,共3页Computer Engineering and Applications

基　　金：温州市科技计划项目(No.G20100204);浙江省重大科技专项项目(No.2009C11039)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]