| Popis: |
The 8-puzzle problem is a classic artificial intelligence problem which has been well-researched. The research in this domain has focused on evaluating traditional search methods such as the breadth-first search and the A* algorithm and deriving and testing various heuristics for use with informed searches to solve the 8-puzzle problem. The study presented in this paper evaluates a machine learning technique, namely genetic programming, as means of solving the 8-puzzle problem. The genetic programming algorithm uses the grow method to create an initial population which is iteratively refined using tournament selection to choose parents which the reproduction, mutation and crossover operators are applied to, thereby producing successive generations. The edit operator has been used to exert parsimony pressure in order to reduce the size of solution trees and hence the number of moves to solve a problem instance. The genetic programming system was successfully applied to 20 problem instances of differing difficulty, producing solutions to all 20 problems. Furthermore, for a majority of the problems the solutions produced solve the problem instance using the known minimum number of moves. |
