n South African Computer Journal - Intelligent system design using hyper-heuristics




Determining the most appropriate search method or artificial intelligence technique to solve a problem is not always evident and usually requires implementation of different approaches to ascertain this. In some instances a single approach may not be sufficient and hybridization of methods may be needed to find a solution. This process can be time consuming. The paper proposes the use of hyper-heuristics as a means of identifying which method or combination of approaches is needed to solve a problem. The research presented forms part of a larger initiative aimed at using hyper-heuristics to develop intelligent hybrid systems. As an initial step in this direction, this paper investigates this for classical artificial intelligence uninformed and informed search methods, namely depth first search, breadth first search, best first search, hill-climbing and the A* algorithm. The hyper-heuristic determines the search or combination of searches to use to solve the problem. An evolutionary algorithm hyper-heuristic is implemented for this purpose and its performance is evaluated in solving the 8-Puzzle, Towers of Hanoi and Blocks World problems. The hyper-heuristic employs a generational evolutionary algorithm which iteratively refines an initial population. On each iteration the evolutionary algorithm uses tournament selection to select parents. The mutation and crossover operators are applied to the chosen parents to produce offspring for the next generation. The hyper-heuristic was able to identify a search or combination of searches to produce solutions for the twenty 8-Puzzle, five Towers of Hanoi and five Blocks World problems. Furthermore, admissible solutions were produced for all problem instances. A different search or combination of searches was evolved for each problem instance. This study has highlighted the potential of hyper-heuristics for the automated design of intelligent systems. Given this success, future work will investigate the use of hyper-heuristics for the design of intelligent hybrid systems for high-level reasoning, which will combine genetic algorithms, tabu search, variable neighbourhood search and simulated annealing. The automated design of intelligent systems has long term benefits for the software industry as a means of reducing the man hours needed for system design.


Article metrics loading...

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error