Modern Heuristic Search Methods

Citation

Andrew, A.M. (1998), "Modern Heuristic Search Methods", Kybernetes, Vol. 27 No. 5, pp. 582-585. https://doi.org/10.1108/k.1998.27.5.582.3

Because of the appearance of the word “heuristic”, the title might suggest that this book is concerned with artificial intelligence, as usually understood. The focus is more accurately indicated by the reference to “search”, and the concern is with the application of modern heuristic methods to problems of search and optimisation arising mainly in the operations‐research context. Such problems, exemplified by the travelling salesman problem, can be solved by algorithmic methods and usually, in principle, by exhaustive enumeration and evaluation, but the computational complexity becomes prohibitive with increasing task complexity. The introduction of heuristics allows methods that often find near‐optimal solutions with relatively small computational cost.

The coverage of the book is in a fringe area between AI and operations research, where, according to the synopsis on the back cover, “research in this exciting area is progressing apace spurred on by the needs of industry and commerce”. Although a distinction is made between this area and that of mainstream AI, it is entirely possible that the new methods model human thought in a useful way and so contribute to AI in a wider sense. In particular, the method referred to as “tabu search” is explicitly intended to model human search.

The book stems from a topic stream in a meeting in Brunel University in the Spring of 1995, with the overall title of “Adaptive decision technologies”. It is made clear that the book is not simply a set of proceedings, but is a selected and thoroughly edited set of contributions, supplemented by a specially‐prepared introductory chapter.

In many tasks of optimisation it is necessary to avoid being trapped at local optima (maxima or minima, depending on how the task is formulated), and so a balance has to be struck between straightforward hill‐climbing and wider exploration. Three strategies are described in the introductory chapter, all of them susceptible to considerable variation, as well as combination to produce hybrid methods. The three strategies are, respectively, simulated annealing (SA), tabu search (TS) and genetic algorithms (GA).

The first and last of these are fairly well known. I was pleased to find that “tabu” is not an acronym, but is in fact the well‐known word of the language more commonly shown as “taboo”. TS refers to a search procedure in which a record is kept of recent moves and a set of rules is used to derive from this sets of possible subsequent moves to be “tabu”. By a suitable choice of rules it is possible to ensure that the search is unlikely to become circular or otherwise to backtrack over already‐explored ground, and yet has adequate exploratory capacity. In the introductory chapter all three of the methods are illustrated by application to the maximisation of a polynomial function. The task is simple because the possible answers are limited to the integers from zero to 31, but is made artificially discontinuous by operating on the five binary digits as distinct variables. All three methods find the optimum remarkably quickly, the GA one so much so that it is impossible not to feel it is by a fluke, but the illustration is instructive.

A very minor blemish in this admirable chapter is in the explanation of a particular GA crossover operation near the middle of page 22. I must admit I spent some time puzzling over this before I realised that the two “chromosomes” are treated symmetrically, a point that is not made clear in the book. The two chromosomes start with the respective sets of values [2 1 3 4 5 6 7] and [4 3 6 2 7 1 5] and the operation with respect to a crossover point after the first two pairs of values gives [2 1 4 3 6 7 5] and [4 3 2 1 5 6 7]. The rule is that values prior to the crossover point remain unchanged, and thereafter each chromosome is filled with values taken in sequence from the initial contents of the other, omitting values that have already appeared in pre‐crossover positions of the chromosome being filled.

Following the introduction, the book has five chapters under the heading of “Techniques”, and ten under the heading of “Case studies”. The total number of contributors is 32, with several countries represented. Of the five papers under “Techniques”, the first is about strategies for determining the time‐course of “temperature” change, or “annealing schedule” in SA, which has to be problem‐dependent. The next deals very thoroughly with TS, including a review of the history of the method. The next again is a review of ways of achieving reactive search, or self‐tuning search heuristics. For example, a search procedure must divide its resources between intensification, or local optimisation, and diversification, or wider search, and the appropriate mix is task‐dependent and can be adjusted by self‐tuning. The biological parallels are not stressed in the chapter, but are intriguing since psychologists readily acknowledge the phenomenon of “learning‐to‐learn”, and biological evolution is often seen as having recursive character.

The remaining two chapters under this heading are both concerned with GA, the first with the application of GA to combinatorial optimisation, acknowledging that it is more readily applicable to the quantitative kind. The authors deprecate the introduction of problem‐specific functions like the special crossover already mentioned and instead advocate reformulation of the task. The other paper is on a related theme since it deals with the integration of local search into GA, which has sometimes been used for only the early stages of a search, with a switch to another method for local optimisation.

Although these chapters have been placed under “Techniques” all of them refer to applications and hence include case studies. The range of applications includes flight scheduling, freight train regrouping, network design, warehouse location, and line balancing in automated assembly.

In the chapters under the heading of “Case studies”, applications to a further set of problem areas are described. Attention is given to the search for Steiner Trees in graphs, having relevance to the design of telephone, pipeline, and transportation networks, as well as to integrated circuits. Other papers treat a vehicle fleet mix problem, timetabling and scheduling, analysis of waste flow data from an industrial complex, a convoy movement problem, and telecommunications traffic routeing. These chapters are by no means devoid of contributions to technique, and for example that dealing with the vehicle fleet mix problem introduces a novel TS metaheuristic. Results of this on test problems improve on the best solutions previously published.

Chapters 12 and 16 do not fit the general pattern. The former describes a technique for the computer design of solid objects to meet given requirements, using GA. Schemes to improve on existing designs have been described previously, but this is the first to innovate from nothing. The results represent only a tentative beginning, and although objects to serve the purpose of a table were generated, it is acknowledged that the technique as it stands would be unlikely to generate a table in the familiar four‐legged form.

Chapter 16, the final offering, has the enigmatic heading “When Herby met Elvis” and reports experiments with a simulated ecology that embodies not only the predator‐prey type of interaction but also evolution of visual capabilities in the predators. The name “Herby” refers to the predator‐prey (or, here, herbivore‐plant) aspect and “Elvis” is an abbreviation of Ecological Vision System. Unlike the other chapters in the book, this one is not directly relevant to operations research as such, but simulation results are reported that are significant for the understanding of biological evolution.

For a complicated work such as this a review can only indicate main headings and a general flavour, but probably enough has been said to show that this is an extremely valuable and well‐presented source of information on the state‐of‐the‐art in the area it purports to cover.