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

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

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

杨卫波1，2，王万良2

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.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

摘要/Abstract

摘要： 针对具有巨大搜索解空间的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

杨卫波1，2，王万良2. 求解24数码问题的改进遗传退火算法 [J]. 计算机工程与应用, 2011, 47(15): 9-11.

YANG Weibo1，2，WANG Wanliang2. Improved genetic simulated annealing algorithm for 24 puzzle problem[J]. Computer Engineering and Applications, 2011, 47(15): 9-11.

[1]	李昱奇，刘志乾，程凝怡，王莹莹，朱春丽. 多约束条件下无人机航迹规划[J]. 计算机工程与应用, 2021, 57(4): 225-230.
[2]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[3]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[4]	杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.
[5]	曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.
[6]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[7]	马艳芳，李保玉，杨屹夫，冯翠英. 客户分类下生鲜配送两级路径问题与算法研究[J]. 计算机工程与应用, 2021, 57(20): 287-298.
[8]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[9]	代江涛，韩晓龙. 考虑作业状态能耗的集装箱码头设备协调调度[J]. 计算机工程与应用, 2021, 57(19): 290-298.
[10]	童文林，陈德旺，黄允浒，吕宜生. 结合模拟退火与规则约简的模糊系统优化方法[J]. 计算机工程与应用, 2021, 57(16): 142-150.
[11]	姜良重，雷航，李贞昊，钱伟中，施甘图. 采用自适应优化权重的出库货位优化方法研究[J]. 计算机工程与应用, 2021, 57(15): 271-278.
[12]	贺娇，谭代伦. 基于视野范围和遗传算法的三维地形路径规划[J]. 计算机工程与应用, 2021, 57(15): 279-285.
[13]	冯晓东，黄世荣，戴冠鸥，杨伟家，罗尧治. 天牛须遗传杂交算法的研究与应用[J]. 计算机工程与应用, 2021, 57(15): 90-100.
[14]	苏庆，林华智，黄剑锋，林志毅. 结合CNN和Catboost算法的恶意安卓应用检测模型[J]. 计算机工程与应用, 2021, 57(15): 140-146.
[15]	王秀丽，周鹏，侯静楠，王仕俊，林霞. 面向变电站机器人巡检路径规划中的算法研究[J]. 计算机工程与应用, 2021, 57(14): 245-250.