Trajectory-based search explores an optimization problem by moving from one candidate solution to the next. Those successive moves trace a path through the search space. In a trajectory-based metaheuristic, one search agent follows that path; a population-based method instead searches with multiple agents. The single-agent approach tends to emphasize exploitation of the area it is already exploring. section 5.1 section 7.1
Why move away from a good solution?
Imagine reaching a low valley but suspecting that a lower one lies beyond the hills. Staying put protects the solution you have; climbing temporarily makes another valley reachable. Simulated annealing uses this intuition: in a minimization problem, it accepts improving moves and can sometimes accept a move that worsens the objective. section 5.1
Two trajectory-based techniques make different choices about subsequent moves:
- Simulated annealing uses temperature to control its willingness to accept non-improving moves. Higher temperature favors exploration; gradual cooling shifts the search toward exploitation. At very low temperature, its behavior approaches hill climbing. section 5.7
- Tabu search combines local search with memory of recently explored solutions. Avoiding a quick return to those solutions helps keep the search from getting stuck in a local optimum. section 6.0
The choice is practical rather than a guarantee of success. Simulated annealing can seek an optimal or near-optimal solution when derivatives are unavailable, unreliable, or too costly, but it does not guarantee feasibility or a particular degree of optimality. Trajectory-based techniques are applied to continuous and discrete problems, including function optimization, Sudoku, traveling-salesperson problems, delivery routing, and assembly-line balancing. section 5.7 section 5.0 section 6.0
