A metaheuristic is a general-purpose optimization strategy that guides the search toward good solutions without guaranteeing the optimum. It is useful when straightforward downhill improvement can become trapped in a local minimum or when a single solution is not enough to explore the search space. section 18.1.1 section 17.1.1
Common mechanisms illustrate different ways to balance exploration and improvement:
- Simulated annealing keeps a single solution and sometimes accepts an uphill move, with that probability reduced during cooling. section 17.1.1
- Genetic algorithms maintain a population of encoded solutions and generate new candidates through biologically inspired operators such as crossover and mutation. section 18.1.1
- Evolutionary algorithms generalize population-based metaheuristics, while particle swarm optimization moves a population using rules inspired by flock dynamics. section 18.4.3
Planning supplies for a Mars mission
A supplies table lists food types with their weights and calorie totals. Such a practical optimization scenario can represent candidate plans as solutions and search for a strong plan under the mission’s competing considerations, without assuming that the first locally improving choice is globally best. section 18.1.1
Figure 18.2 An example of how genetic algorithms would tackle the scenario in figure 18.1. At a generic iteration (in the figure, we assume we are at the i-th iteration), which could indifferently be toward the beginning or the end of the simulation, the algorithm maintains a pool of possible solutions. At the next iteration, the pool (as a whole) will transition to a new set of candidate solutions (based on the current ones—we’ll see how later in this section). Usually the new solutions can be anywhere in the domain.
Trace how a genetic algorithm transitions an entire pool of candidate solutions from one iteration to the next. section 18.1.1
