基于遗传算法的数码问题求解  

Solution of Puzzle Problem Using Genetic Algorithm

作　　者：王斌[1] 李元香[1] 

机构地区：[1]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《计算机工程》2003年第10期45-46,101,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(69703011)

摘　　要：在人工智能研究中，数码问题常被用来作为一些搜索算法的测试实例。数码问题的搜索空间巨大，对于24数码问题，目前最好的启发式搜索算法找到最优解(最少移动步数)通常也至少需要2.25小时[1]。遗传算法具有简单、通用、鲁棒性强的特点，适合于在复杂而庞大的搜索空间中寻找最优解。该文给出了求解该问题的遗传算法，并针对遗传算法容易过早收敛的问题，对传统遗传算法进行了改进。通过用多个随机生成的15数码和24数码问题作为测试实例，本算法均在较短的时间内找到了问题的解，从而证明了算法的有效性。Characterized by large search space, Puzzle problem is often used in AI research to test the performance of kinds of searching algorithms. For 24 Puzzle problem as example, it often takes at least 2.25 h to find the optimal solution even using the available best heuristic searching algorithm. As so far, genetic algorithm (GA) has seldom been seen to find its application in solving such a kind of problem. As an easy-of-use and robust searching algorithm, GA is highly fitted for solving the searching problem that has large and complex searching space. In this paper, a kind of genetic algorithm is designed to solve the puzzle problem. To avoid traditional GAs premature convergence problem, some modifications are made. Experiments on 15 and 24 Puzzle problem show that this algorithm can reach satisfying optimal solutions in much less time, which proves its validity and efficiency.

关 键 词：数码问题 遗传算法 杂交算子 变异算子 

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