You are here

Mathematical Foundations of Nature-Inspired Algorithms

XIn-She Yang and Xing-Shi He
Publisher: 
Springer
Publication Date: 
2019
Number of Pages: 
107
Format: 
Paperback
Series: 
SpringerBriefs in Optimization
Price: 
59.99
ISBN: 
978-3-030-16935-0
Category: 
Monograph
[Reviewed by
Bill Satzer
, on
10/13/2019
]
This short book presents itself as an introduction to the rigorous mathematical analysis of algorithms used for optimization, data mining and machine learning, but it takes an unconventional path. While some traditional algorithms such as gradient-based search are considered, the emphasis is on analyzing and understanding nature-inspired optimization algorithms.
 
Nature-inspired algorithms are usually stochastic or non-deterministic. Work on these dates back at least to Alan Turing in the 1940s, and was reinvigorated in the 1960s with the development of genetic algorithms that attempted to emulate biological evolution by incorporating operations of mutation, crossover, and selection into the optimization process. Simulated annealing was first described in the 1980s. It mimics the annealing process of a metal as it cools and solidifies, and so attempts to avoid getting an optimization trapped in local minima.
 
The book begins with a short introduction that describes general principles of constrained and unconstrained optimization of univariate and multivariate functions. It then quickly summarizes several versions of gradient-based algorithms including the usual ones (steepest descent and conjugate gradient) as well as more advanced ones like stochastic gradient and subgradient methods.
 
Having set the stage with these more conventional algorithms, the authors describe a series of nature-inspired algorithms. They note that the “no-free-lunch” theorems proved in 1997 tell us that there is no best algorithm for solving all optimization problems because all algorithms are equally effective (or ineffective) when measured by average performance across all possible problems. Consequently, the authors consider nature-inspired algorithms that can be matched to specific kinds of applications. Algorithms they describe go by names such as particle swarm optimization, the bat algorithm, the firefly algorithm, and cuckoo search. Several of these algorithms are based on the idea of swarm intelligence. The aim of a swarming system is to allow the system to evolve and converge into stable states that include those with optimal performance. 
 
The firefly algorithm, for example, was inspired by the flashing behavior of tropical firefly species and the idea that the attractiveness of a firefly is linked to the brightness and the timing accuracy of its flashes. Its nonlinear optimization emulates the exponential decay of light absorption and the inverse-square law of light variation with distance to identify multiple local minima. Cuckoo search was developed to model the cuckoo’s reproductive strategy of searching for other birds’ nests in which to lay their eggs. It uses a random walk search based on the similarity between the cuckoo’s egg and the host’s egg and a discovery probability that the host bird discovers the cuckoo’s egg. 
 
Nature-inspired algorithms share a number of features. They use a population of multiple agents (particles, bees, ants, fireflies, bats, cuckoos). The population evolves under certain operators that are often iterative. All the algorithms perform some combination of local and global search. The downside of many of these nature-inspired algorithms is that they are often more computationally intensive than traditional algorithms because many more iterations are required.
 
The authors devote a couple of chapters to the analysis of algorithms. This has some general aspects (convergence, stability and robustness) as well as details that apply to the nature-inspired algorithms (determining and tuning of parameters and statistical characterization of performance). A final chapter describes some applications of nature-inspired algorithms that the authors have discovered. These include design optimization in engineering, image processing, vehicle routing and scheduling.
 
This is not a textbook and has no exercises. Most of the topics considered get very abbreviated treatments and many of the discussions of the algorithms are disappointingly sketchy. Even the algorithm analysis sections are short on detail. Critics have suggested that the elaborate metaphors of some nature-inspired algorithms have hidden their lack of novelty or effectiveness. There is just not enough detail in this book to allow any judgment in that direction.
 
The book is probably best suited as an inspiration for an independent project that might take one of the algorithms and fill out details of analysis and performance. The book’s level of sophistication varies, but most topics are accessible to upper level undergraduates.

 

Bill Satzer (bsatzer@gmail.com), now retired from 3M Company, spent most of his career as a mathematician working in industry on a variety of applications ranging from speech recognition and network modeling to optical films and material science. He did his PhD work in dynamical systems and celestial mechanics.