Title
Solving the 8-puzzle problem using genetic programming
Abstract
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.
Year
DOI
Venue
2013
10.1145/2513456.2513492
SAICSIT Conf.
Keywords
Field
DocType
classic artificial intelligence problem,genetic programming algorithm,problem instance,genetic programming,minimum number,traditional search method,breadth-first search,8-puzzle problem,genetic programming system,informed search
Partition problem,Genetic operator,Mathematical optimization,Crossover,Computer science,Genetic programming,Heuristics,Genetic representation,Cutting stock problem,Tournament selection
Conference
Citations 
PageRank 
References 
0
0.34
2
Authors
3
Name
Order
Citations
PageRank
Kevin Igwe110.70
Nelishia Pillay223733.72
Christopher Rae300.34