Rayward-Smith V.J., Osman I.H., Reeves C.R., Smith G.D. (eds.) Modern Heuristic Search Methods

John Wiley, 1996, -367 p.The last few decades have been an exciting time for those of us working in optimisation. The theoretical foundations of complexity have been laid starting with Cook's theorem in the seventies and followed by a plethora of results on NP-Completeness and the definition of yet more complexity classes. Added to this, we have had remarkable progress in mathematical programming. In Linear Programming, we have had Khachiyan's polynomial time algorithm and a whole spectrum of more practical, interior point algorithms. Together with techniques such as branch-and-cut and polyhedral combinatorics and the very significant advances in computer technology, these greatly enhance the prospect of finding exact solutions to difficult optimisation problems. Nevertheless, the vast majority of large scale, commercial optimisation problems pose a real challenge and their exact solution usually remains computationally intractable. The Artificial Intelligence community has also made considerable advances and many of the methods that they espouse are now coming to fruition and can be used for practical applications. For example, expert systems, case-based reasoning, constraint satisfaction programming and genetic algorithms have all come from the AI stable and are now widely used by industry to solve large real-world problems.
Local search is a more mundane technique, at heart quite naive, but nevertheless, for many of the most difficult real-world problems, it provides one of the very best ways of obtaining a near optimal solution with reasonable computational effort. During the last three decades, local search has also been developed and powerful variants of the simple neighbourhood search paradigm have emerged. The problem with neighbourhood search is its propensity to prematurely converge to a local optimum. One way of avoiding this is to use variable depth search which allows the exploration of a more complex neighbourhood in an attempt to find an improved solution. Other recent methods, sometimes known as 'modern heuristic techniques', are also designed to escape from the local optima traps. In general, they still do not guarantee an optimal solution nor even to meet given performance bounds. However, as this book shows, they often work exceptionally well in practice and have many advantages including versatility, efficiency and simplicity.
Three of the main modern heuristic methods are simulated annealing, tabu search and genetic algorithms but, with the wider use of hybrid methods, the distinctions will become increasingly blurred. Simulated annealing uses a probability function which allows a move from a solution to a worse solution with a decreasing probability as the search progresses. Tabu Search uses a deterministic rather than stochastic search. Tabu Search moves to the best admissible solution even if this causes the objective function to deteriorate but, to avoid cycling, a short term adaptive memory is used. With genetic algorithms, a pool of solutions is used and the neighbourhood function is extended to act on pairs of solutions (using the so-called crossover operator. The pool is then maintained according to the 'survival of the fittest' principle. These methods can be hybridised with each other or with more traditional Operational Research techniques. Moreover, they have considerable scope for parallel or distributed implementation.
Anyone working in practical operational research, artificial intelligence or any area of decision support needs to be a polymath. Modern heuristic techniques have to be part of his or her weaponry. To meet the need for training in this area, UNICOM have run a series of conferences, workshops and seminars on this and related topics. These conferences have brought together academic researchers and those working in commerce and industry. The result has been most fruitful. In the Spring of 1995, a particularly successful meeting on 'Adaptive Decision Technologies' was held at Brunel University. One of the three main streams was on modern heuristic methods. This book grew out of this meeting but it is not simply the conference proceedings. It comprises one specially written introductory chapter and a carefully refereed selection of extended versions of the best papers presented at that meeting.Modern Heuristic Techniques.
Localized Simulated Annealing in Constraint Satisfaction and Optimization.
Observing Logical Interdependencies in Tabu Search: Methods and Results.
Reactive Search: Toward Self-tuning Heuristics.
Combinatorial Optimization by Genetic Algorithms: The Value of the Genotype/Phenotype Distinction.
Integrating Local Search into Genetic Algorithms.
Local Search for Steiner Trees in Graphs.
Local Search Strategies for the Vehicle Fleet Mix Problem.
SA Solutions for Timetabling.
A Tabu Search Algorithm for Some Discrete-Continuous Scheduling Problems.
The Analysis of Waste Flow Data from Multi-Unit Industrial Complexes Using Genetic Algorithms.
The Evolution of Solid Object Designs Using Genetic Algorithms.
The Convoy Movement Problem with Initial Delays.
A Comparison of Heuristics for Telecommunications Traffic Routing.
A Brief Comparison of Some Evolutionary Optimization Methods.
When 'Herby' met 'ElViS' Experiments with Genetics Based Learning Systems.