Simple linkage: Analysis of a threshold-accepting global optimization method
Tóm tắt
In a recent paper the authors introduced an infinite class of global optimization algorithms based upon random sampling from the feasible region and local searches started from selected sample points, based upon an acceptance/rejection criterion. All of the algorithms of that class possess strong theoretical properties. Here we analyze a member of that family, which, although being significantly simpler to implement and more efficient than the well known Multi-Level Single-Linkage algorithm, enjoys the same theoretical properties. It is shown here that, with very high probability, our method is able to discover from which points Multi-Level Single-Linkage will decide to start local search.
Tài liệu tham khảo
Locatelli, M. and Schoen, F.: 1995, ‘Random Linkage: a family of acceptance/rejection algorithms for global optimisation’, Technical Report 156-96, DSI, University of Milano, submitted for publication, available through the www page of the 2nd author.
Lucidi, S. and Piccioni, M.: 1989, ‘Random Tunneling by Means of Acceptance-Rejection Sampling for Global Optimization’. Journal of Optimization Theory and Applications 62, pp. 255–276
Rinnooy Kan, A.H.G. and Timmer, G.T.: 1987, ‘Stochastic Global Optimization Methods. Part I: Clustering Methods’, Mathematical Programming 39, pp. 27–56
Rinnooy Kan, A.H.G. and Timmer, G.T.: 1987, ‘Stochastic Global Optimization Methods. Part II: Multi Level Methods’, Mathematical Programming 39, pp. 57–78