Simulated Annealing with Deterministic Decisions

Abstract

Problem statement: Simulated Annealing (SA) algorithms have been used in solving a wide range of discrete optimization problems for many years, with well know drawbacks like the computational time and difficulties related to the parameters settings. One of the other issues that open the door for research is the acceptance decision that provides for hill climbing; the standard SA algorithms use a stochastic method which fails to justify the acceptance of a cost increasing solutions while rejecting mildly cost increasing ones. Approach: To resolve this dilemma, the reversible deformation mechanism we developed earlier replaced the stochastic decision with a deterministic one; by deforming the problem structure and gradually reforming it towards the original one. This provides for hill climbing in the real domain while applying a simple downhill search in the virtual sense. Unlike the standard SA algorithm, the number of iterations must be known in advance and it is the only stopping criteria, because the scaling functions parameters are selected based on the number of iterations. Results: This method had produced better solutions and the new enhancement to the algorithm improves the overall performance by examining each state more thoroughly through a set of perturbations and thus securing a move towards a better neighborhood, the same set of tests used in the original methods are repeated for comparison. Conclusion: The significance of this research comes from eliminating the unpredictability of the stochastic decisions in the standard SA algorithms which might yield less than acceptable solutions in some cases.