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

Solution of Puzzle Problem Using Genetic Algorithm

在人工智能研究中，数码问题常被用来作为一些搜索算法的测试实例。数码问题的搜索空间巨大，对于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.