Artificial intelligence, heuristic frameworks and tabu search

Abstract

This paper examines some of the characteristics of AI‐based heuristic procedures that have emerged as frameworks for solving difficult optimization problems. Consideration of attributes shared to some degree by human problem solvers leads to focusing in greater detail on one of the more successful procedures, tabu search, which employs a flexible memory system (in contrast to “memoryless” systems, as in simulated annealing and genetic algorithms, and rigid memory systems as in branch and bound and A* search). Specific attention is given to the short‐term memory component of tabu search, which has provided solutions superior to the best obtained by other methods for a variety of problems. Our development emphasizes the principles underlying the interplay between restricting the search to avoid unproductive retracing of paths (by means of tabu conditions) and freeing the search to explore otherwise forbidden avenues (by aspiration criteria). Finally, we discuss briefly the relevance of a supplementary framework, called target analysis, which is a method for determining good decision rules to enable heuristics to perform more effectively.