Proposals for chunking and tabu search

Chunking – grouping basic units of information to create higher level units – is a critical aspect of human intelligence. We identify special types of chunking to enhance tabu search memory structures, producing improved problem solving ability and giving useful supporting information for decision makers. Tabu search as proposed by Glover has proven to be a very effective meta-heuristic for hard optimization problems. The search is typically based on a local improvement scheme that involves alteration of one or more attributes of fully specified solutions at each iteration. In this paper we describe the use of, and search for, groupings of solution attributes. Although they are most natural in the context of the tabu search paradigm, many of the proposals can also be employed in genetic algorithms and simulated annealing based algorithms. Chunking enables a number of search improvements including a general purpose metric for decision vectors. The paper develops theory and proposals for learning about chunks and using them. Computational experience to date is summarized to support the contention that chunking can be an important part of effective optimization algorithms.