Skip to main content

2016 | Buch

Search and Optimization by Metaheuristics

Techniques and Algorithms Inspired by Nature

insite
SUCHEN

Über dieses Buch

This textbook provides a comprehensive introduction to nature-inspired metaheuristic methods for search and optimization, including the latest trends in evolutionary algorithms and other forms of natural computing. Over 100 different types of these methods are discussed in detail. The authors emphasize non-standard optimization problems and utilize a natural approach to the topic, moving from basic notions to more complex ones.
An introductory chapter covers the necessary biological and mathematical backgrounds for understanding the main material. Subsequent chapters then explore almost all of the major metaheuristics for search and optimization created based on natural phenomena, including simulated annealing, recurrent neural networks, genetic algorithms and genetic programming, differential evolution, memetic algorithms, particle swarm optimization, artificial immune systems, ant colony optimization, tabu search and scatter search, bee and bacteria foraging algorithms, harmony search, biomolecular computing, quantum computing, and many others. General topics on dynamic, multimodal, constrained, and multiobjective optimizations are also described. Each chapter includes detailed flowcharts that illustrate specific algorithms and exercises that reinforce important topics. Introduced in the appendix are some benchmarks for the evaluation of metaheuristics.
Search and Optimization by Metaheuristics is intended primarily as a textbook for graduate and advanced undergraduate students specializing in engineering and computer science. It will also serve as a valuable resource for scientists and researchers working in these areas, as well as those who are interested in search and optimization methods.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
This chapter introduces background material on global optimization and the concept of metaheuritstics. Basic definitions of optimization, swarm intelligence, biological process, evolution versus learning, and no-free-lunch theorem are described. We hope this chapter will arouse your interest in reading the other chapters.
Ke-Lin Du, M. N. S. Swamy
Chapter 2. Simulated Annealing
Abstract
This chapter is dedicated to simulated annealing (SA) metaheuristic for optimization. SA is a probabilistic single-solution-based search method inspired by the annealing process in metallurgy. Annealing is a physical process where a solid is slowly cooled until its structure is eventually frozen at a minimum energy configuration. Various SA variants are also introduced.
Ke-Lin Du, M. N. S. Swamy
Chapter 3. Genetic Algorithms
Abstract
Evolutionary algorithms (EAs) are the most influential metaheuristics for optimization. Genetic algorithm (GA) is the most popular form of EA. In this chapter, we first give an introduction to evolutionary computation. A state-of-the-art description of GA is then presented.
Ke-Lin Du, M. N. S. Swamy
Chapter 4. Genetic Programming
Abstract
Genetic programming (GP) is a variant of GA whose chromosomes have variable length and data structure in the form of hierarchical trees. It is an automated method for evolving computer programs from a high-level statement of a problem. This chapter is dedicated to GP.
Ke-Lin Du, M. N. S. Swamy
Chapter 5. Evolutionary Strategies
Abstract
Evolutionary strategy (ES) paradigm is one of the most successful EAs. Evolutionary gradient search and gradient evolution are two methods that use EA to construct gradient information for directing the search efficiently. Covariance matrix adaptation (CMA) ES [11] accelerates the search efficiency by supposing that the local solution space of the current point has a quadratic shape.
Ke-Lin Du, M. N. S. Swamy
Chapter 6. Differential Evolution
Abstract
Differential evolution (DE) is a popular, simple yet efficient EA for solving real-parameter global optimization problems [30]. DE is an elitist EA. It creates new candidate solutions by a multiparent reproduction strategy. DE uses the directional information from the current population for each individual to form a simplex-like triangle.
Ke-Lin Du, M. N. S. Swamy
Chapter 7. Estimation of Distribution Algorithms
Abstract
Estimation of distribution algorithm (EDA) is a most successful paradigm of EAs. EDAs are derived by inspirations from evolutionary computation and machine learning. This chapter describes EDAs as well as several classical EDA implementations.
Ke-Lin Du, M. N. S. Swamy
Chapter 8. Topics in Evolutinary Algorithms
Abstract
This chapter continues to introduce topics on EAs. Convergence of EAs is first analyzed by using scheme theorem, building-block hypothesis, and then by using finite and infinite population models. Various parallel implementations of EAs are then described in detail. Some other associated topics including coevolution and fitness approximation are finally introduced.
Ke-Lin Du, M. N. S. Swamy
Chapter 9. Particle Swarm Optimization
Abstract
PSO can locate the region of the optimum faster than EAs, but once in this region it progresses slowly due to the fixed velocity stepsize. Almost all variants of PSO try to solve the stagnation problem. This chapter is dedicated to PSO as well as its variants.
Ke-Lin Du, M. N. S. Swamy
Chapter 10. Artificial Immune Systems
Abstract
EAs and PSO tend to converge to a single optimum and hence progressively lose diversity. This is not the case for artificial immune systems (AISs). AISs are based on four main immunological theories, namely, clonal selection, immune networks, negative selection, and danger theory. This chapter introduces four immune algorithms inspired by the four immunological theories.
Ke-Lin Du, M. N. S. Swamy
Chapter 11. Ant Colony Optimization
Abstract
Ants are capable of finding the shortest path between the food and the colony using a pheromone-laying mechanism. ACO is a metaheuristic optimization approach inspired by this foraging behavior of ants. This chapter is dedicated to ACO.
Ke-Lin Du, M. N. S. Swamy
Chapter 12. Bee Metaheuristics
Abstract
This chapter introduces various algorithms that are inspired by the foraging, mating, fertilization, and communication behaviors of honey bees. Artificial bee colony (ABC) algorithm and marriage in honeybees optimization are described in detail.
Ke-Lin Du, M. N. S. Swamy
Chapter 13. Bacterial Foraging Algorithm
Abstract
This chapter describes bacterial foraging algorithm inspired by the social foraging behavior of Escherichia coli present in human intestine. Several algorithms inspired by molds, algae, and tumor cells are also introduced.
Ke-Lin Du, M. N. S. Swamy
Chapter 14. Harmony Search
Abstract
Harmony search and melody search are population-based metaheuristic optimization techniques inspired by the improvisation process of music players or group improvisation. They represent the vertical aspect and the horizontal aspect of music space.
Ke-Lin Du, M. N. S. Swamy
Chapter 15. Swarm Intelligence
Abstract
Nature-inspired optimization algorithms can, generally, be grouped into evolutionary approaches and swarm intelligence methods. EAs try to improve the candidate solutions (chromosomes) using evolutionary operators. Swarm intelligence methods use differential position update rules for obtaining new candidate solutions. The popularity of the swarm intelligence methods is due to their simplicity, easy adaptation to the problem, and effectiveness in solving the complex optimization problems.
Ke-Lin Du, M. N. S. Swamy
Chapter 16. Biomolecular Computing
Abstract
Biomolecular computing studies the potential of using biological molecules to perform computation. DNA (deoxyribonucleic acid) computing [49] and membrane computing [46] are two natural computing techniques at the biomolecular level. This chapter gives a conceptual introduction to these computing paradigms.
Ke-Lin Du, M. N. S. Swamy
Chapter 17. Quantum Computing
Abstract
Quantum computing is inspired from the theory of quantum mechanics, which describes the behavior of particles of atomic size. Quantum computing is involved with the research on quantum computers and quantum algorithms. Quantum algorithms perform exponentially faster than any of the traditional algorithms [30]. Quantum computers were proposed in the 1980s [1, 6]. This chapter introduces some basic quantum computing algorithms and quantum-based hybrid metaheuristic algorithms.
Ke-Lin Du, M. N. S. Swamy
Chapter 18. Metaheuristics Based on Sciences
Abstract
This chapter introduces dozens of metaheuristic optimization algorithms that are related to physics, natural phenomena, chemistry, biogeography, and mathematics.
Ke-Lin Du, M. N. S. Swamy
Chapter 19. Memetic Algorithms
Abstract
The term meme was coined by Dawkins in 1976 in his book The Selfish Gene [7]. The sociological definition of a meme is the basic unit of cultural transmission or imitation. A meme is the social analog of genes for individuals. Universal Darwinism draws the analogy on the role of genes in genetic evolution to that of memes in a cultural evolutionary process [7]. The science of memetics [3] represents the mind-universe analog to genetics in cultural evolution, ranging the fields of anthropology, biology, cognition, psychology, sociology, and sociobiology. This chapter is dedicated to memetic and cultural algorithms.
Ke-Lin Du, M. N. S. Swamy
Chapter 20. Tabu Search and Scatter Search
Abstract
Tabu search is a single-solution-based stochastic metaheuristic global optimization method. It is a hill-climbing method that imitates human memory structure to improve decision-making. Scatter search is a population-based metaheuristic algorithm. Scatter search and its generalized form called path relinking are intimately related to tabu search, and they derive additional advantages by using adaptive memory mechanism.
Ke-Lin Du, M. N. S. Swamy
Chapter 21. Search Based on Human Behaviors
Abstract
Human being is the most intelligent creature on this planet. This chapter introduces various search metaheuristics that are inspired by various behaviors of human creative problem-solving process.
Ke-Lin Du, M. N. S. Swamy
Chapter 22. Dynamic, Multimodal, and Constrained Optimizations
Abstract
This chapter treats several hard problems associated with metaheuristic optimization, namely, dynamic, multimodal, and constrained optimization problems.
Ke-Lin Du, M. N. S. Swamy
Chapter 23. Multiobjective Optimization
Abstract
Multiobjective optimization problems (MOPs) involve several conflicting objectives to be optimized simultaneously. The challenge is to find a Pareto set involving nondominated solutions that are evenly distributed along the Pareto Front. Metaheuristics for multiobjective optimization have been established as efficient approaches to solve MOPs.
Ke-Lin Du, M. N. S. Swamy
Backmatter
Metadaten
Titel
Search and Optimization by Metaheuristics
verfasst von
Ke-Lin Du
M. N. S. Swamy
Copyright-Jahr
2016
Electronic ISBN
978-3-319-41192-7
Print ISBN
978-3-319-41191-0
DOI
https://doi.org/10.1007/978-3-319-41192-7