Simulated annealing
Simulated annealing is a stochastic optimization method that gradually reduces the probability of accepting worse solutions to escape local optima.
Advanced Algorithms and Data Structures
Simulated annealing is a randomized optimization algorithm that probabilistically accepts some worsening transitions while gradually reducing that probability to escape local optima and approach a global optimum.
- How it is used
- Optimizes routes and graph embeddings when local minima or nondifferentiable costs make downhill-only search unsuitable.
- How deep it goes
- Develops a generic pseudocode loop, acceptance behavior, cooling schedule, transition design, and tuning trade-offs without proving convergence.
- Examples
- Works through traveling-salesperson tour costs and swaps, then applies vertex moves to minimum-crossing and force-directed graph drawings.
- What you can do after
- Build it from scratch by supplying a cost function, candidate transition, acceptance rule, cooling schedule, and iteration limit.
Read how Advanced Algorithms and Data Structures explains simulated annealing →
Optimization Algorithms: AI techniques for design, planning, and control problems
The original form of simulated annealing that uses a temperature-controlled probability of accepting worsening moves.
- How it is used
- Uses temperature-controlled stochastic moves to seek low-cost solutions in continuous optimization and discrete routing problems.
- How deep it goes
- Works through acceptance probability, pseudocode, parameter tuning, and hand iterations, without promising an optimal or feasible result.
- Examples
- Works through a bounded quadratic, five-city and Berlin52 traveling-salesman tours, and a delivery route visiting 18 stores.
- What you can do after
- Apply it via optalgotools’ SimulatedAnnealing to a defined objective and neighborhood, then tune temperature and cooling settings.
Machine Learning Algorithms in Depth
Simulated annealing is a heuristic optimization method that probabilistically accepts higher-energy states according to a temperature-controlled schedule to escape local optima.
- How it is used
- Uses temperature-controlled search to minimize energy while allowing moves that can escape local optima.
- How deep it goes
- Develops the acceptance and cooling loop into pseudocode and a from-scratch implementation; does not establish a global-optimum guarantee.
- Examples
- Uses a two-dimensional energy landscape, sampled energies, and a traveling salesman problem application.
- What you can do after
- Build it from scratch to search a two-dimensional energy function, and consider restarts when seeking better optima.
Read how Machine Learning Algorithms in Depth explains simulated annealing →
Related concepts
- objective functionuses · An objective function assigns values to candidate solutions, predictions, or parameter settings according to a criterion to be minimized or maximized.
- trajectory-based searchkind of · A search approach that generates a sequence of candidate states by repeatedly moving from one state to another.
- update ruleuses · An update rule specifies how a current state, estimate, or representation is revised using newly available information or an iteration step.
- Traveling Salesman problemaddresses · The Traveling Salesman problem is a combinatorial optimization problem that seeks a minimum-cost tour visiting each specified location exactly once and returning to the starting location.
- locally optimal solutionaddresses · A locally optimal solution is a feasible point whose objective value is no worse than those of sufficiently nearby points, though a better solution may exist elsewhere.
- gradient descentalternative to · Gradient descent is an iterative optimization method that updates parameters opposite the gradient of an objective function to reduce its value.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.