Efficient Optimization Using Metaheuristics

Metaheuristics Concepts: Definition and Classification

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 (including shaking, construction/deconstruction, adaptation, swarming and collective behavior, hybridization, etc.) applied to improve the search.

The heuristic components in a metaheuristic are conceived to be applied in an intelligent way, providing accurate and balanced methods for diversification and intensification. These two concepts are very important to guarantee the efficacy of the search: diversification refers to achieving a good exploration pattern for the search space, providing a reasonable coverage and avoiding stagnation in local optima; intensification means exploiting or improving already found accurate solutions to increase their quality.

Regarding the number of solutions handled, metaheuristics are classified in two classes: trajectory-based and population-based. Trajectory-based 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. On the other hand, population-based 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, because having multiple solutions allows significantly increasing the exploration capabilities.

Other classification criteria for metaheuristics are related to specific features of the search strategy, for example: memory vs. memory-less, or dynamic vs. static objective function.