- author = "Kevin Igwe and Nelishia Pillay and Christopher Rae",
- title = "Solving the 8-puzzle problem using genetic programming",
- booktitle = "Proceedings of the South African Institute for Computer Scientists and Information Technologists Conference, SAICSIT'13",
- year = "2013",
- editor = "John McNeill and Karen L. Bradshaw and Philip Machanick and Mosiuoa Tsietsi",
- pages = "64--67",
- address = "East London, South Africa",
- month = oct # " 7-9",
- publisher = "ACM",
- keywords = "genetic algorithms, genetic programming, game",
- bibdate = "2013-09-28",
- bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/saicsit/saicsit2013.html#IgwePR13",
- isbn13 = "978-1-4503-2112-9",
-
URL = "
http://dl.acm.org/citation.cfm?id=2513456",
-
URL = "http://doi.acm.org/10.1145/2513456.2513492",
-
DOI = "
doi:10.1145/2513456.2513492",
- acmid = "2513492",
- size = "4 pages",
- 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.",
-
notes = "Tree GP. Comparison between: depth first, breadth
first, A* (A-star) and
GP.
http://www.ict.ru.ac.za/saicsit2013/ Also known as \cite{Igwe:2013:SPU:2513456.2513492}",
