Sequential drug decision problems in long-term medical conditions: a case Study of Primary Hypertension Eunju Kim ba, ma, msc

3.3Simulated annealing

SA was motivated by the traditional annealing process of metals^[203]. During the annealing process, the system state heats up to a high temperature and then cools down slowly until it converges to a steady ‘frozen’ state. Kirkpatrick et al mapped the behaviour of the physical cooling process onto the elements of a discrete optimisation problem, with the objective of solving an optimisation problem^[173].

The algorithm starts from an initial solution that is either randomly or heuristically selected (see Figure ‎3.). Incorporating knowledge into the initial solution can save a substantial amount of computational time; however, if the initial solution is too good, the algorithm may never fully escape from the neighbourhood of the starting state^[53].

The neighbourhood is a set of candidate solutions which can be generated by a small perturbation to the current solution. They can be defined in various ways depending on the characteristics of a given problem. However, it should be noted that there is an implicit trade-off between the size of the neighbourhood and the efficiency of the search^{[53, 121, 153]}. That is, if the size of the neighbourhood is large, it is more likely to converge nearer to the global optimum, but to take a long time to complete the required calculations. If the size of the neighbourhood is small, the algorithm is able to search the neighbourhood quickly, but more likely to become trapped at a local optimum. In general, small simple neighbourhoods are preferable to large complex ones^[53].

The method used to decrease the temperature is generally called cooling schedule, which consists of four components: initial temperature, final temperature, temperature decrement and iterations at each temperature. The choice of an appropriate cooling schedule is crucial for the performance of SA. The initial temperature T should be hot enough to allow most neighbours to be accepted and to have the final solution, which is independent of the starting solutions^[173]. There are a few studies that suggest a method for finding a suitable initial temperature^[204-207]. In this thesis the initial temperature is 1, which is the highest temperature. The temperature T is gradually decreased to a value close to zero during the search process. Temperature decrement may be consistent or vary during the search, with the aim of tuning the balance between diversification and intensification. For example, at the beginning of the search T might be constant or linearly decreasing in order to explore the search space, and then follow a geometric rule to converge to a local minimum at the end of the search^[208].

SA is a variant of the traditional descent methods in which the search always moves in a direction of improvement. The weakness of the traditional descent methods is that the final solution is dependent on the starting solution(s) employed and often results in convergence to a local optimum as it always move to a better solution in the neighbourhood^[53]. However, SA offers a way to escape from a local optimum by allowing some uphill moves (i.e., moves to a solution inferior to the current solution) in a controlled manner. The probability of accepting a move to a worse solution is governed by a probability function, which follows the Boltzmann distribution:
Equation 3.3.

where δE is f(π’)-f(π), t is temperature and k is a physical constant known as Boltzmann’s constant.

A solution π’N(π) is randomly sampled at each iteration and accepted as the new current solution depending on f(π), f(π’) and T. That is, π’ replaces π if f(π’)>f(π) or, in the case of f(π’)≤ f(π), with a probability, which is a function of T and f(π’)-f(π). At the beginning of the search, the probability of accepting a worse solution is high but gradually decreases to zero.

The stopping criteria can include a minimum value of the temperature parameter, a maximum number of total iterations^{[60, 209]}, a maximum number of non-improving iterations^[102] or a maximum number of accepted worse solutions^[210]. These rules need to be carefully tuned with the other parameters to ensure convergence at a sufficiently low temperature.

Select the initial solution π. Initialize the temperature T.