Pattern discrete and mixed Hit-and-Run for global optimization |
| |
Authors: | Huseyin Onur Mete Yanfang Shen Zelda B Zabinsky Seksan Kiatsupaibul Robert L Smith |
| |
Institution: | 1.Industrial and Systems Engineering,University of Washington,Seattle,USA;2.Citigroup Alternative Investments,New York,USA;3.Faculty of Commerce and Accountancy,Chulalongkorn University,Bangkok,Thailand;4.Department of Industrial and Operations Engineering,University of Michigan,Ann Arbor,USA |
| |
Abstract: | We develop new Markov chain Monte Carlo samplers for neighborhood generation in global optimization algorithms based on Hit-and-Run.
The success of Hit-and-Run as a sampler on continuous domains motivated Discrete Hit-and-Run with random biwalk for discrete
domains. However, the potential for efficiencies in the implementation, which requires a randomization at each move to create
the biwalk, lead us to a different approach that uses fixed patterns in generating the biwalks. We define Sphere and Box Biwalks that are pattern-based and easily implemented for discrete and
mixed continuous/discrete domains. The pattern-based Hit-and-Run Markov chains preserve the convergence properties of Hit-and-Run
to a target distribution. They also converge to continuous Hit-and-Run as the mesh of the discretized variables becomes finer,
approaching a continuum. Moreover, we provide bounds on the finite time performance for the discrete cases of Sphere and Box
Biwalks. We embed our samplers in an Improving Hit-and-Run global optimization algorithm and test their performance on a number
of global optimization test problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|