求解15数码问题的遗传算法设计  

Design of Genetic Algorithms for 15-Puzzle Problem

作　　者：崔桓睿 马燕[1] 刘逗逗 张娜 CUI Huan-rui;MA YAN;LIU Dou-dou;ZHANG NA(College of Mathematics and Computer Science,Yan′an University,Yan′an 716000,China)

机构地区：[1]延安大学数学与计算机科学学院,陕西延安716000

出　　处：《延安大学学报（自然科学版）》2018年第4期18-20,27,共4页Journal of Yan'an University：Natural Science Edition

摘　　要：提出了一种求解15数码问题的遗传算法。依据问题特征,设计了个体编码方法、高效的适应度评价函数和遗传操作算子,对遗传算法易于过早收敛和易于陷入局部极小的问题有所改善。测试结果表明该求解模型对解决15数码问题是有效的、稳定的,具有较高的搜索效率。Genetic algorithm was proposed for 15-puzzle problem.Based on the characteristics of the problem,encoding method for individual activity,an efficient fitness evaluation function and genetic operators were designed,which improves the problems of premature convergence and local minima in the genetic algorithm.The test results showed that the algorithm was effective and stable to solve the 15-puzzle problem,and it has an advantage of high searching efficiency.

关 键 词：15数码问题 遗传算法 交叉算子 变异算子 适应度函数 

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