Metaheuristics are high-level soft computing strategies that define algorithmic frameworks and techniques to find approximate solutions for optimization problems (Blum & Roli, 2003; Talbi, 2009). Many efficient and accurate metaheuristics have been proposed, which can be applied to solve a variety of optimization problems underlying many applications in science/technology, industry, and commerce.
Metaheuristics were originally proposed as high-level problem-independent strategies to coordinate several heuristic search methods, which can be instantiated to solve hard problems. This definition has broadened to include a wide range of search and learning processes (shaking, construction/deconstruction, adaptation, swarming/collective behavior, hybridization, etc.) applied to improve the search.
Metaheuristics are conceived to apply the heuristic components in an intelligent way, providing accurate and balanced methods for diversification and intensification. These two concepts are crucial for any successful search method: diversification refers to achieving a good exploration pattern for the search space, providing a reasonable coverage and avoiding stagnation in local optima, while intensification means exploiting accurate solutions to increase their quality. By providing different trade-offs between diversification and intensification, metaheuristics have emerged as robust methods for optimization.
Regarding the number of solutions handled, metaheuristics are classified in trajectory and population based. Trajectory metaheuristics work with a single solution, which is replaced by another (often the best) solution found in its neighborhood. The search is characterized by a trajectory in the space of solutions. Trajectory metaheuristics allow quickly exploiting solutions, thus they are referred as intensification-oriented methods. Population metaheuristics work with a set of candidate solutions, which are modified and/or combined following some common guidelines. Some solutions in the population are replaced by newly generated solutions (often the best). These methods are characterized as diversification-oriented.
Other classification criteria for metaheuristics are related to the search strategy, memory vs. memory-less, and dynamic vs. static objective function.