21408 Relaxation Property and its Application in Optimization by Search-Space Smoothing in Combination with the Metropolis Algorithm
Manabu Hasegawa, Chang Ju KIM · The Proceedings of Conference of Kanto Branch · 2013
The relaxation property of the local search dynamics in optimization by the Metropolis algorithm (MA) is examined on the smoothed landscapes introduced in the method of search-space smoothing (SSS) and the result is applied to the design of the MASSS method (the combination of the MA and the SSS method) with variable operating temperature. An experimental analysis is conducted on the random Euclidean traveling salesman problem. It is confirmed that the performance of the relaxation dynamics as an optimizer is improved by a single smoothing and more by a de-smoothing process with heating in the implementation of the MASSS method.