ABSTRACT
CONTENTS 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694 11.2 Concepts of Metaheuristic Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 697
11.2.1 Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698 11.2.2 Classification of Metaheuristic Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 699 11.2.3 A Generic Metaheuristic Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701
11.3 Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703 11.4 Artificial Bee Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705 11.5 Artificial Immune System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708
11.5.1 Clonal Selection Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708 11.5.2 Immune Network Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 709
11.6 Differential Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 710 11.7 Evolution Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712
11.7.1 Self-Adaptive ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712 11.7.2 Covariance Matrix Adaptation-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714
11.8 Evolutionary Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715 11.9 Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718
11.9.1 Generational versus Steady-State GAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719 11.10 Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 720 11.11 Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723 11.12 Scatter Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 724 11.13 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725 11.14 Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728 11.15 Other Metaheuristic Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728 11.16 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737 Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 738 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739
ABSTRACT Most real-world search and optimization problems involve complexities such as nonconvexity, nonlinearities, discontinuities, mixed nature of variables, multiple disciplines and large dimensionality, a combination of which renders classical provable algorithms to be either ineffective, impractical or inapplicable. There do not exist any known mathematically motivated algorithms for finding the optimal solution for all such problems in a limited computational time. Thus, in order to solve such problems to practicality, search and optimization algorithms are usually developed using certain heuristics that, though lacking in strong mathematical foundations, are nevertheless good at reaching an approximate solution in a reasonable amount of time. These so-called
metaheuristic methods do not guarantee finding the exact optimal solution, but can lead to a nearoptimal solution in a computationally efficient manner. Owing to this practical appeal combined with their ease of implementation, metaheuristic methodologies are gaining popularity in several application domains. Most metaheuristic methods are stochastic in nature and mimic a natural, physical, or biological principle resembling a search or an optimization process. In this chapter, we discuss a number of such methodologies, specifically evolutionary algorithms, such as genetic algorithms and evolution strategy, particle swarm optimization, ant colony optimization, bee colony optimization, simulated annealing, and a host of other methods. Many metaheuristic methodologies are being proposed by researchers all over the world on a regular basis. It therefore becomes important to unify them to understand common features of different metaheuristic methods and simultaneously to study fundamental differences between them. Hopefully, such endeavors will eventually allow a user to choose the most appropriate metaheuristic method for the problem at hand.
