Analysis of convergence properties of a stochastic evolution algorithm

Author

Mao, Chi-Yu ; Hu, Yu Hen

Author_Institution

Cadence Design Syst. Inc., San Jose, CA, USA

Volume

15

Issue

7

fYear

1996

fDate

7/1/1996 12:00:00 AM

Firstpage

826

Lastpage

831

Abstract

In this paper, the convergence properties of a stochastic optimization algorithm called the stochastic evolution (SE) algorithm is analyzed. We show that a generic formulation of the SE algorithm can be modeled by an ergodic Markov chain. As such, the global convergence of the SE algorithm is established as the state transition from any initial state to the globally optimal states. We propose a new criterion called the mean first visit time (MFVT) to characterize the convergence rate of the SE algorithm. With MFVT, we are able to show analytically that on average, the SE algorithm converges faster than the random search method to the globally optimal states. This result Is further confirmed using the Monte Carlo simulation

Keywords

Markov processes; circuit CAD; circuit optimisation; combinatorial mathematics; convergence of numerical methods; mathematics computing; optimisation; stochastic processes; convergence properties; ergodic Markov chain; global convergence; globally optimal states; mean first visit time; state transition; stochastic evolution algorithm; stochastic optimization algorithm; Algorithm design and analysis; Convergence; Cooling; Data structures; High level synthesis; Optimization methods; Partitioning algorithms; Scheduling algorithm; Skeleton; Stochastic processes;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.503949

Filename

503949