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

3) Heuristics: Local search methods

Within the local search method category, five single solution meta-heuristic methods and eight population-based meta-heuristic methods were identified. The rank of these meta-heuristic methods (in terms of the number of times that a method was identified in the 512 studies) was more related to the age of the algorithm rather than the accuracy or efficiency.

Most meta-heuristic methods such as tabu search, SA and evolutionary methods are primarily to be viewed as repetitive improvement methods based on local search. These methods have their own subjective strategy, which differentiates themselves from each other. For example, SA has a mechanism to move to the worse solution to overcome the problem of descent strategies, which always move towards the bottom of the valley containing the starting point^[173]. A distinctive feature of the tabu search is the tabu list, which stores the short and long-term search history to restrict the moves to the areas placed in the tabu list^{[174, 175]}. In the guided local search, the objective function is modified depending on the solution features, which is associated with a penalty, while the set of solutions and the neighbourhood structure are kept fixed^[176]. Variable neighbourhood search changes neighbourhoods where no improvement is observed^[177]. Greedy randomised adaptive search uses a constructive heuristics for solution construction and a local search for solution improvement^[178]. Evolutionary algorithms are different with the algorithms mentioned above in the sense that evolutionary methods maintain a population of solutions^[179]. At each iteration a number of operators, which are called recombination, mutation and selection, are applied to the individuals of the current population to generate the fitted individuals of the population of the next iteration. All these characteristics of meta-heuristics are associated with intensification, which searches carefully and intensively around good solutions found in the past search, and diversification, which guides the search to unvisited regions. Although meta-heuristics cannot guarantee the globally optimal solution, they can escape from local minima and proceed to the ‘global’ optima successfully where the intensification and diversification are well balanced.

Recently, interest in hybrid meta-heuristics, which cooperatively use the strengths of different methods, has increased considerably^[180]. SA was supplemented with a tabu list^[181], and variable neighbourhood search was used as an improvement procedure in the last step of the GA^[182]. In Roach and Nagi’ study, the GA randomly generated candidate solutions, while the SA focused these to "local" optima^[183]. Ho and Ewe used a GA within the search procedure of ant colony optimisation to quickly achieve adaptation by refocusing the search process around promising areas of the search space^[184]. Behnamian et al hybridised ant colony optimisation for initial population generation, SA for solution evolution and a variable neighbourhood search to improve the population^[185]. Tseng and Liang proposed a hybrid meta-heuristic called ANGEL, which combines the ant colony optimisation, the GA and a local search method^[186]. Experimental results showed that these hybrid heuristics enhance the performance of individual heuristics in terms of the quality of solution and computational time.