Event Will Never Forget
Comparison of Di erent Neighbourhood Sizes in Simulated Annealing
Xin Yao Department of Computer Science University College, University of New South Wales Australian Defence Force Academy Canberra, ACT, Australia 2600
Abstract
Neighbourhood structure and size are important parameters in local search algorithms. This is also true for generalised local search algorithms like simulated annealing. It has been shown that the performance of simulated annealing can be improved by adopting a suitable neighbourhood size. However, previous studies usually assumed that the neighbourhood size was xed during search. This paper presents a simulated annealing algorithm with a dynamic neighbourhood size which depends on the current \temperature" value during search. A method of dynamically deciding the neighbourhood size by approximating a continuous probability distribution is given. Four continuous probability distributions are used in our experiments to generate neighbourhood sizes dynamically, and the results are compared.
combinatorial optimisation. A method of generating dynamic neighbourhood sizes by approximating continuous probability distributions is given in this section. Section 4 compares the experimental results of using di erent continuous probability distributions to generate dynamic neighbourhood sizes. Finally, Section 5 concludes with some remarks and directions of future research.
2 General Simulated Annealing
Although SA can be used in both continuous and discrete cases, this paper only considers combinatorial optimisation by SA unless otherwise indicated explicitly. A combinatorial optimisation problem can be informally described as nding an optimal con guration X from a nite or in nite countable con guration space S . Each con guration X 2 S can be represented by its n (> 0) components, i.e., X = (x1; x2; ; xn ), where xi 2 Xi , i = 1; 2; ; n. An excellent discussion of combinatorial optimisation and its complexity can be found in Garey and
Xin Yao Department of Computer Science University College, University of New South Wales Australian Defence Force Academy Canberra, ACT, Australia 2600
Abstract
Neighbourhood structure and size are important parameters in local search algorithms. This is also true for generalised local search algorithms like simulated annealing. It has been shown that the performance of simulated annealing can be improved by adopting a suitable neighbourhood size. However, previous studies usually assumed that the neighbourhood size was xed during search. This paper presents a simulated annealing algorithm with a dynamic neighbourhood size which depends on the current \temperature" value during search. A method of dynamically deciding the neighbourhood size by approximating a continuous probability distribution is given. Four continuous probability distributions are used in our experiments to generate neighbourhood sizes dynamically, and the results are compared.
combinatorial optimisation. A method of generating dynamic neighbourhood sizes by approximating continuous probability distributions is given in this section. Section 4 compares the experimental results of using di erent continuous probability distributions to generate dynamic neighbourhood sizes. Finally, Section 5 concludes with some remarks and directions of future research.
2 General Simulated Annealing
Although SA can be used in both continuous and discrete cases, this paper only considers combinatorial optimisation by SA unless otherwise indicated explicitly. A combinatorial optimisation problem can be informally described as nding an optimal con guration X from a nite or in nite countable con guration space S . Each con guration X 2 S can be represented by its n (> 0) components, i.e., X = (x1; x2; ; xn ), where xi 2 Xi , i = 1; 2; ; n. An excellent discussion of combinatorial optimisation and its complexity can be found in Garey and
References: 1] P. J. M. van Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory and Applications, D. Reidel Publishing Co., 1987. 2] D. H. Ackley, A Connectionist Machine for Genetic Hillclimbing, Kluwer Academic Publishers, Boston, 1987. 3] X. Yao, Optimization by genetic annealing," In M. Jabri, editor, Proc. of ACNN '91, pages 94{97, Sydney, 1991. 4] D. R. Greening, Parallel simulated annealing techniques," Physica D, 42:293{306, 1990. 5] X. Yao, Simulated annealing with extended neighbourhood," International J. of Computer Math., 40:169{189, 1991. 6] X. Yao and G.-J. Li, General simulated annealing," J. of Computer Sci. & Tech., 6:329{ 338, 1991. 7] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing," Science, 220:671{680, 1983. 8] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman Co., San Francisco, 1979. 9] S. Anily and A. Federgruen, Ergodicity in parameteric nonstationary Markov chains: an application to annealing methods," Oper. Res., 35:867{874, 1987. 10] L. Goldstein and M. Waterman, Neighborhood size in the simulated annealing algorithm," Amer. J. of Math. and Management Sci., 8:409{423, 1988. 11] K. M. Cheh, J. B. Goldberg, and R. G. Askin, A note on the e ect of neighborhood structure in simulated annealing algorithm," Computers and Oper. Res., 18:537{547, 1991. 12] H. H. Szu and R. L. Hartley, Nonconvex optimization by fast simulated annealing," Proc. of IEEE, 75:1538{1540, 1987. 13] W. Feller, An Introduction to Probability Theory and Its Applications, volume 2, John Wiley & Sons, Inc., 2nd edition, 1971. 4 Table 2: SA with a dynamic neighbourhood size which is generated by the Cauchy function (CauSA), Normal function (NorSA), Exponential function (ExpSA), and Stable function with index 1=2 (StableSA). research issue in search theory, i.e., the issue of exploration versus exploitation or global search versus local search. Although local search based on some heuristics can be quite e cient under many circumstances, the problem of local optima is very hard to deal with. Some kind of global search has to be used if a global optimum or near optimum is required. However, the computational cost of global search is often prohibitively high for most real-world applications due to the vast search space. It is bene cial to combine global and local search together. An open question here is how to decide when global or local search should be performed. It is also di cult to draw the line strictly between local and global search in practice. Dynamic neighbourhood size offers a way to deal with the problem by transferring from global search to local search smoothly based on a control parameter, temperature in SA. However, more work has to be done on deciding which kind of generation functions is most suitable for an application, i.e., what is the optimal rate of reducing the neighbourhood size. As indicated before, Fast SA 12] o ers a big improvement over classical SA 7] due to the adoption of Cauchy distribution. An interesting topic is to investigate whether the discrete version of Fast SA can o er similar improvement over classical SA. Our preliminary experiments seem to give a negative answer. Acknowledgement | The author is grateful to Drs. B. Marksjo and R. Sharpe for their support of his work while he was with CSIRO Division of Building, Construction and Engineering.