A stochastic algorithm uses randomness in its parameters, decisions, or both to explore candidate solutions. Repeated runs can follow different paths, making results and runtime non-repeatable, while helping the search avoid becoming trapped in local optima. section 2.2
Use these distinctions to understand how stochastic search behaves:
- Contrast deterministic algorithms, which follow repeatable procedures, with stochastic algorithms, which incorporate random choices. section 2.2
- Separate local search, which exploits neighborhoods, from global search, which explores more of the search space. section 2.2
- Expect acceptable or near-optimal solutions rather than predictable optimality: improvements are not guaranteed, runtimes are difficult to forecast, and feasibility or optimality may remain uncertain. section 2.2 section 5.7
- Recognize simulated annealing, tabu search, genetic algorithms, differential evolution, particle swarm optimization, and ant colony optimization as stochastic or related metaheuristic approaches. section 2.2 section 5.1
Simulated annealing
Imagine searching for the lowest valley in a rugged landscape. Move that improves the objective is accepted, but some worsening moves are also accepted probabilistically. Start with a high temperature to encourage exploration, then lower it gradually to favor exploitation; near zero, the method behaves like hill climbing, while very high temperature resembles a random walk. section 5.1 section 5.7
Figure 2.16 Deterministic vs. stochastic algorithms. Deterministic algorithms follow a set procedure, and the results are repeatable, while stochastic searches have elements of randomness built into the algorithms.
Compare repeatable deterministic procedures with stochastic searches that build randomness into their decisions. section 2.2
