locatelli (1121215), страница 3
Текст из файла (страница 3)
11.The next theorem states that, under the introduced assumptions, it ispossible to guarantee also that the sequence {Xk } of candidate points converges with probability 1 to the global optimum.Theorem 4.2. Let 2̃ be the same as in Theorem 4.1. If Assumptions3.1–3.7 hold, and if in (4) and (6) 2̄∈(0, 2̃] is chosen, thenlim P[Xk ∈B2 ]G1,∀2H0.(14)Proof. See Theorem 4 in Ref. 11.hk→SAs already remarked in the previous section, a drawback of the aboveresult is that generally it is not possible to know in advance a suitable valuefor 2̄.
However, it is possible to prove that, for any fixed value 2̄, a weakerps893$p22710-01-:0 11:35:20JOTA: VOL. 104, NO. 1, JANUARY 2000131result holds, namely that, with probability 1, the sequence {Xk } will lie inthe limit in the set B22̄ .Theorem 4.3. If Assumptions 3.1–3.3 and Assumption 3.7 hold, thenlim P[Xk ∈B22̄ ]G1.k→SProof.
See Theorem 5 in Ref. 11.hIn this case, the value 2̄ acts like a predefined accuracy fixed by theuser. We also note that the choice of 2̄ is an important task. By choosing ittoo small, the algorithm may perform too many free steps (i.e., steps withtkXδ 1 and RkXδ 2 ), without exploring locally the feasible region. On theother hand, by choosing it too big, the algorithm may perform small stepseven when the current iterate is far away from the current record.There is still a lot of space for further research in this field.
In particular, it could be interesting to see whether it is possible to relax some of theassumptions. A partial answer is given in the following theorem, whoseresult is weaker than (11) and (14), but has been obtained by removingcompletely Assumptions 3.5–3.7.Theorem 4.4. If Assumptions 3.1–3.4 hold, thenilim (1yi) ∑ P[Y j ∉B22̄ ]G0.i→Sj G1Proof. See Theorem 6 in Ref. 11.h5. ConclusionsThis paper has dealt with the convergence problem of simulatedannealing algorithms for continuous global optimization.
After a shortintroduction about the simulated annealing approach to continuous globaloptimization, some recent convergence results from the literature have beenpresented. It has been noted that either these results are strong [both (11)and (14) hold], but proved under restrictive assumptions, or they are weak[only (11) holds], but proved under quite general assumptions. In this paper,strong convergence results have been derived without introducing assumptions which are too restrictive.
The main idea of the paper is that the temperatures as well as the support of the distribution of the next candidatepoints should depend on the current value of the iterate. In particular, theyps893$p22710-01-:0 11:35:20132JOTA: VOL. 104, NO. 1, JANUARY 2000should be decreased to zero if the current iterate has a value close to thecurrent record, while both can be arbitrarily chosen (but bounded awayfrom zero) when the value of the current iterate is sufficiently worse thanthe record.
While exploited only for the proof of convergence results, thisidea seems to be reasonable for the development of cooling schedules for theapplication of simulated annealing algorithms. Besides the cooling schedule,some other things have to be specified in order to define a practical simulated annealing algorithm belonging to the class for which convergence,under the given assumptions, has been proved above. In particular, the distribution of the next candidate point has to be specified. A possible idea isto employ the collected information zk in order to build a model of thefunction over the support sphere and then to define a distribution with adensity connected to the model (with higher values where the model haslower values).
In this way, the algorithm acts like a randomized local searchsimilarly, but without the differentiability requirement, to algorithms basedon stochastic differential equations (see e.g. Refs. 14, 16, 17), where eachstep is represented by the sum of an antigradient step and a randomperturbation.Finally, we remark that there are still many open questions in the fieldof convergence results for simulated annealing algorithms for continuousglobal optimization. In particular, relaxations of the assumptions underwhich the results have been proved could be searched for.References1.
METROPOLIS, N., ROSENBLUTH, A. W., ROSENBLUTH, M. N., and TELLER, A.H., Equation of State Calculations by Fast Computer Machines, Journal ofChemical Physics, Vol. 21, pp. 1087–1091, 1953.2. ČERNY, V., Thermodynamical Approach to the Travelling Salesman Problem: AnEfficient Simulation Algorithm, Journal of Optimization Theory and Applications, Vol. 45, pp. 41–51, 1985.3.
KIRKPATRICK, S., GELATT, C. D., and VECCHI, M. P., Optimization by Simulated Annealing, Science, Vol. 220, pp. 671–680, 1983.4. BOHACHEVSKY, I. O., JOHNSON, M. E., and STEIN, M. L., Generalized Simulated Annealing for Function Optimization, Technometrics, Vol. 28, pp. 209–217,1986.5. BROOKS, D.
G., and VERDINI, W. A., Computational Experience with Generalized Simulated Annealing over Continuous Variables, American Journal ofMathematical and Management Sciences, Vol. 8, pp. 425–449, 1988.6. COLEMAN, T., SHALLOWAY, D., and WU, Z. J., A Parallel Buildup Algorithmfor Global Energy Minimizations of Molecular Clusters Using Effective Energyps893$p22710-01-:0 11:35:20JOTA: VOL. 104, NO. 1, JANUARY 20007.8.9.10.11.12.13.14.15.16.17.133Simulated Annealing, Journal of Global Optimization, Vol.
4, pp. 171–185,1994.CORANA, A., MARCHESI, M., MARTINI, C., and RIDELLA, S., Minimizing Multimodal Functions of Continuous Variables with the Simulated Annealing Algorithm, ACM Transactions on Mathematical Software, Vol. 13, pp. 262–280,1987.JONES, A.
E. W., and FORBES, G. W., An Adaptive Simulated Annealing Algorithm for Global Optimization over Continuous Variables, Journal of Global Optimization, Vol. 6, pp. 1–37, 1995.ROMEIJN, H. E., and SMITH, R. L., Simulated Annealing for Constrained GlobalOptimization, Journal of Global Optimization, Vol. 5, pp. 101–126, 1994.VANDERBILT, D., and LOUIE, S.
G., A Monte Carlo Simulated AnnealingApproach to Optimization over Continuous Variables, Journal of ComputationalPhysics, Vol. 56, pp. 259–271, 1984.LOCATELLI, M., On the Convergence of Simulated Annealing Algorithms, Technical Report 01-99, Dipartimento di Sistemi ed Informatica, Universitá di Firenze,1999; also available at the web site http:yywww.dsi.unifi.ityusersylocatellydist4.psBELISLE, C. J. P., Convergence Theorems for a Class of Simulated AnnealingAlgorithms on R d, Journal of Applied Probability, Vol. 29, pp.
885–892, 1992.HAJEK, B., Cooling Schedules for Optimal Annealing, Mathematics of Operations Research, Vol. 13, pp. 311–329, 1988.GELFAND, S. B., and MITTER, S. K., Metropolis-Type Annealing Algorithms forGlobal Optimization in R d, SIAM Journal on Control and Optimization, Vol.31, pp. 111–131, 1993.LOCATELLI, M., Convergence Properties of Simulated Annealing for ContinuousGlobal Optimization, Journal of Applied Probability, Vol. 33, pp.
1127–1140,1996.GELFAND, S. B., and MITTER, S. K., Recursive Stochastic Algorithms for GlobalOptimization in R d, SIAM Journal of Control and Optimization, Vol. 29, pp.999–1018, 1991.ALUFFI-PENTINI, F., PARISI, V., and ZIRILLI, F., Global Optimization andStochastic Differential Equations, Journal of Optimization Theory and Applications, Vol. 47, pp. 1–16, 1985.ps893$p22710-01-:0 11:35:20.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
