Chung YeoI Lee , Sun Young Lee , Soo Min Lee , Jong Seok Lee , Cheol Hoon Park

The KIPS Transactions:PartB , Vol. 14, No. 7, pp. 541-548, Dec. 2007
10.3745/KIPSTB.2007.14.7.541,   PDF Download:

Abstract

Due to the mathematical convergence property, Simulated Annealing (SA) has been one of the most popular optimization algorithms. However, because of its problem of slow convergence in the practical use, many variations of SA like Fast SA (FSA) have been developed for faster convergence. In this paper, we propose and prove that Greedy SA (GSA) also finds the global optimum in probability in the continuous space optimization problems. Because the greedy selection does not allow the cost to become worse, GSA is expected to have faster convergence than the conventional FSA that uses Metropolis selection. In the computer simulation, the proposed method is shown to have as good performance as FSA with Metropolis selection in the viewpoints of the convergence speed and the quality of the found solution. Furthermore, the greedy selection does not concern the cost value itself but uses only dominance of the costs of solutions, which makes GSA invariant to the problem scaling.

Statistics
Cite this article