Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Theory and principled methods for the design of metaheuristics
Borenstein Y., Moraglio A., Springer Publishing Company, Incorporated, Berlin, Germany, 2014. 284 pp. Type: Book (978-3-642332-05-0)
Date Reviewed: Jul 10 2014

In choosing to place the word “principled” in the title of this book, the editors signal their intention to address the issue of how one can devise heuristics given the “no free lunch” theorem (NFL). This result implies that under fairly general circumstances any search algorithm averaged over all problems is equally good (or bad). Indeed, chapter 1 gives an exposition of the NFL that describes the circumstances under which it applies. The majority of the papers in the book, therefore, address themselves to ways in which the NFL theorem can be either finessed or avoided. For example, in the case of function optimization, knowing that the functions to be optimized belong to a particular class can allow the algorithm designed to do better than a nonrepeating random search (which search the NFL assures us is typical).

Although not formally broken up into parts, the ordering of the chapters does group them into themes. These are described in the introduction as “Theory for Drawing the Line,” “Relevant Scope of Problems,” “Top-Down Principled Design of Search Algorithms,” and “Principled Practice.” Each chapter includes an extensive bibliography.

Chapter 1, “No Free Lunch Theorems: Limitations and Perspectives of Metaheuristics,” reviews the no free lunch theorem with particular emphasis on the conditions under which it applies. Thus marking out the possibilities for improved algorithms, concluding that in most cases the conditions of the NFL theorem do not apply. In chapter 2, “Convergence Rates of Evolutionary Algorithms and Parallel Evolutionary Algorithms,” the authors consider a large family of search algorithms that use comparisons rather than absolute fitness values. Among the practical implications are results on speed-up for algorithms on parallel machines.

The next two chapters discuss the landscapes in which a search problem operates. The idea is that if one can determine something about the shape of the search space then the search can be improved. Chapter 3, “Rugged and Elementary Landscapes,” shows how the fitness landscape can be represented by a graph. This enables a spectral decomposition of the fitness function, which leads to a definition of a notion of an elementary landscape that includes many problems of practical interest. Chapter 4, “Single-Funnel and Multi-Funnel Landscapes and Subthreshold-Seeking Behavior,” examines the subthreshold-seeking behavior of algorithms for parameter optimization, where the majority of sampling points have an evaluation less than some target threshold. Black box algorithms are discussed in chapter 5, “Black Box Complexity for Bounding the Performance of Randomized Search Heuristics.” These are algorithms that seek to optimize an unknown objective function that can only be explored by sampling the function. The chapter shows ways in which focusing on specific classes of problems can lead to improved algorithms.

Chapters 6 to 8 are on top-down design. They explore ways in which one can derive optimal algorithms for classes of functions using methods such as experimentation, Markov decision processes, and the covariance matrix adaptation evolution strategy. Chapter 6, “Designing an Optimal Search Algorithm with Respect to Prior Information,” considers the case where the function to be optimized is drawn from a collection of functions that has a known probability distribution. Chapter 7, “The Bayesian Search Game,” is a joint discussion of the NFL theorem, partially observable Markov processes, and the use of Gaussian processes as a representation of belief. In chapter 8, “Principled Design of Continuous Stochastic Search: From Theory to Practice,” the authors derive a stochastic search procedure from first principles, imposing the least prior assumptions and exploiting all available information. The resulting search algorithm is the covariant matrix adaptation evolution strategy.

How the parsimony pressure method can be used to control the growth of programs in a population is the topic of chapter 9, “Parsimony Pressure Made Easy: Solving the Problem of Bloat in GP.“ Chapter 10, “Experimental Analysis of Optimization Algorithms: Tuning and Beyond,” provides a series of checklists for experiment design and evaluation. This is a particularly noteworthy chapter and should be read by all graduate students (almost regardless of discipline) and senior undergraduates.

Chapter 11, “Formal Search Algorithms + Problem Characterizations = Executable Search Strategies,” is a revised and extended version of an earlier paper that describes how algorithms can be specified with respect to a formal representation. The chapter describes a formal search algorithm, and uses a suitable characterization of the problem domain to deduce a practical executable search strategy for the domain. It concludes with a useful glossary of terms used in the chapter and indeed elsewhere in the book.

This is a valuable addition to the literature on heuristics for search. Both practitioners and theoreticians should read it.

Reviewer:  J. P. E. Hodgson Review #: CR142494 (1410-0837)
Bookmark and Share
  Featured Reviewer  
 
Heuristic Methods (I.2.8 ... )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Heuristic Methods": Date
Embedding decision-analytic control in a learning architecture
Etzioni O. (ed) Artificial Intelligence 49(1-3): 129-159, 1991. Type: Article
Sep 1 1992
The complexity of the Lin-Kernighan heuristic for the traveling salesman problem
Papadimitriou C. SIAM Journal on Computing 21(3): 450-465, 1992. Type: Article
May 1 1993
Toward combining empirical and analytical methods for inferring heuristics
Mitchell T. (ed)  Artificial and human intelligence (, Lyon, France,1031984. Type: Proceedings
Aug 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy