Understanding Simulated Annealing For Optimisation Problems
Optimisation problems ask us to find the best answer from a very large set of possibilities. The answer might be a short delivery route, a low-cost timetable, a compact machine learning model, or an efficient arrangement of tasks. In many useful cases, checking every candidate would take far too long, so we need a strategy that searches intelligently.
Simulated annealing is a probabilistic optimisation algorithm inspired by the way a material cools during annealing. At high temperatures, the algorithm explores freely and may accept a worse solution. As the temperature falls, it becomes increasingly selective and settles around a strong candidate.
This behaviour is valuable when the search landscape contains local optima. A greedy algorithm can find a solution that looks excellent nearby while missing a much better solution elsewhere. Simulated annealing can temporarily move downhill, escape that trap, and continue exploring.
The method is flexible enough for scheduling, routing, feature selection, packing, assignment, and many combinatorial problems. It is especially useful when a solution can be represented clearly and a small change can be evaluated without rebuilding the entire search from scratch.
| Method | Search behaviour | Strength | Main limitation |
|---|---|---|---|
| Greedy search | Always accepts an improvement | Simple and fast | Easily trapped in a local optimum |
| Hill climbing | Explores nearby candidates | Effective for smooth landscapes | Cannot usually move through worse states |
| Simulated annealing | Sometimes accepts worse candidates | Escapes local optima | Needs careful parameter tuning |
| Genetic algorithm | Combines populations of candidates | Good for broad, irregular searches | More complex and resource-intensive |
| Exhaustive search | Checks every candidate | Finds the exact optimum | Usually infeasible at scale |
The Core Idea Behind Thermal Search
A simulated annealing run begins with an initial solution and a temperature value. It then creates a neighbouring solution by making a small change. If the new candidate is better, it is accepted. If it is worse, it may still be accepted according to a probability controlled by the current temperature.
For a minimisation problem, let the current cost be (E), and let the candidate cost be (E'). The change is:
[ \Delta E = E' - E ]
When (\Delta E \leq 0), the candidate improves or preserves the objective and should be accepted. When (\Delta E > 0), the usual acceptance probability is:
[ P(\text{accept}) = e^{-\Delta E/T} ]
Here, (T) is the temperature. A high temperature makes uphill moves reasonably likely, while a low temperature makes them rare. The algorithm therefore shifts from exploration to exploitation over time.
Temperature, Moves, And Acceptance
The cooling schedule controls how quickly the search becomes conservative. A common rule is geometric cooling:
[ T_{k+1} = \alpha T_k ]
where (0 < \alpha < 1). For example, setting (\alpha = 0.95) reduces the temperature by five per cent after each iteration or cooling stage. Slower cooling usually gives the algorithm more time to explore, but it increases runtime.
The neighbourhood function is equally important. In a route problem, a neighbour might reverse a segment of a route or swap two stops. In a scheduling problem, it could exchange two jobs, move one job to another slot, or change a machine assignment. Poor moves can make the search ineffective even when the temperature schedule is sensible.
Randomness should be controlled during experiments. A fixed random seed makes runs reproducible, which helps when comparing schedules, neighbourhood rules, and stopping conditions. In production, several independent runs with different seeds often provide a more reliable estimate of the algorithm’s typical quality.
Building A Reliable Annealing Schedule
A practical implementation needs more than a temperature variable. It needs a clear objective function, a valid representation of a candidate, a method for generating neighbours, and a stopping rule. The objective should return a numeric cost where lower is better, or a score where higher is better after adapting the acceptance formula.
A useful high-level procedure looks like this:
- Create an initial valid solution and calculate its cost.
- Set the current solution, best solution, and starting temperature.
- Generate a neighbour and calculate its cost difference.
- Accept the neighbour when it improves the result or passes the probability test.
- Cool the temperature and stop after a limit, time budget, or frozen search.
The starting temperature can be estimated by observing typical cost changes from random moves. If almost every worse move is rejected immediately, the initial temperature is too low. If nearly every poor move is accepted for most of the run, cooling may be too slow or the initial value may be too high.
A stopping condition can combine several signals: a maximum number of iterations, a minimum temperature, and a period without improvement. For online systems, a time limit is often more useful than a fixed iteration count because it gives predictable resource usage.
Choosing A Useful Neighbourhood
The neighbourhood defines what the algorithm can reach in one step. It should be local enough to produce meaningful changes, yet broad enough that repeated moves can reach very different solutions. A route optimiser restricted to swapping adjacent stops may explore too slowly, while completely rebuilding a route at every step may destroy useful structure.
For a job scheduling example, a mixed neighbourhood may select among these operations:
- Swap two jobs assigned to different time slots.
- Move one job to a new slot or machine.
- Reverse a consecutive block of scheduled jobs.
- Replace a resource assignment while preserving constraints.
Hard constraints need careful treatment. One option is to generate only valid neighbours, although this can be difficult. Another is to assign a large penalty to invalid candidates. Penalties should be large enough to discourage violations without overwhelming all meaningful differences between valid solutions.
The objective function may combine several business concerns. A delivery schedule could include travel distance, late-arrival penalties, driver hours, and vehicle capacity. In an Australian logistics setting, a route between Sydney suburbs, regional New South Wales, and a depot may need to account for long distances and sparse service areas rather than relying on a city-only cost model.
Comparing Annealing With Other Search Methods
Simulated annealing is a strong general-purpose heuristic, but it is not automatically the best choice. Hill climbing can be faster when the landscape is smooth and local improvements reliably lead towards a good answer. Genetic algorithms can be useful when maintaining a population of diverse solutions matters. Integer programming may provide an exact optimum when the problem can be expressed efficiently and the solver can handle its size.
The algorithm also differs from clustering techniques. A clustering method such as DBSCAN clustering groups data points according to density, whereas annealing searches for a configuration that minimises or maximises an objective. They can still appear in the same project: DBSCAN might identify geographic demand zones, followed by simulated annealing to assign delivery routes.
A good comparison uses the same input data, objective definition, runtime budget, and constraint rules. Report the best result, average result, variability across random seeds, and time to reach a useful solution. A single impressive run does not establish that a stochastic optimiser is dependable.
Implementation In Python
A compact Python implementation can represent a candidate as a list and use a function such as cost(solution) to evaluate it. The main loop copies the current candidate, applies a random mutation, and calculates the difference in cost. Python’s random.random() can decide whether an uphill move is accepted.
For larger problems, avoid recalculating everything when a move changes only a small part of the candidate. In a route problem, a two-opt reversal affects only a limited number of edges, so the new route length can often be calculated incrementally. This can reduce the cost of each iteration substantially.
The algorithm’s time complexity is commonly described as (O(I \times C)), where (I) is the number of iterations and (C) is the cost of evaluating a candidate. If evaluation scans all (n) items, then (C) may be (O(n)), giving (O(In)). Incremental evaluation can reduce (C), while storing a full candidate generally requires (O(n)) space.
If solutions or audit records are persisted, data integrity also matters. An application that stores optimisation results could use a Merkle tree to verify that a result history has not been altered. This is separate from the search itself, but useful when decisions need an auditable record.
Testing Results In The Real World
Testing should begin with small, known cases. For a tiny routing or assignment problem, exhaustive search can calculate the true optimum and provide a baseline. Compare annealing’s result against that baseline across many random seeds, then increase the input size until exact enumeration becomes impractical.
Parameter experiments should vary the starting temperature, cooling rate, number of iterations per temperature, and neighbourhood mix. Plotting cost against iteration often reveals whether the search improves early and then freezes, or continues wandering without meaningful progress. Repeated runs can show whether the method is stable or highly sensitive to its random path.
Local context can influence the objective as much as the algorithm. A Melbourne timetable may need to reflect peak-hour congestion and tram interactions, while a regional Queensland delivery model may prioritise distance, depot availability, and limited charging infrastructure. Australian users may describe a workable result as “good enough” when it meets a strict operational deadline, even if it is not mathematically perfect.
In commercial software, the market often values predictable response times, explainable trade-offs, and easy integration over a theoretical guarantee. A simulated annealing service should therefore expose its runtime budget, objective components, constraint handling, and quality metrics. That makes the optimiser easier to trust, tune, and maintain as real data changes.