Computational complexity and simulation of rare events of Ising spin glasses Export

@misc{citeulike:1741584, abstract = {We discuss the computational complexity of random 2D Ising spin glasses, which represent an interesting class of constraint satisfaction problems for black box optimization. Two extremal cases are considered: (1) the +/- J spin glass, and (2) the Gaussian spin glass. We also study a smooth transition between these two extremal cases. The computational complexity of all studied spin glass systems is found to be dominated by rare events of extremely hard spin glass samples. We show that complexity of all studied spin glass systems is closely related to Frechet extremal value distribution. In a hybrid algorithm that combines the hierarchical Bayesian optimization algorithm (hBOA) with a deterministic bit-flip hill climber, the number of steps performed by both the global searcher (hBOA) and the local searcher follow Frechet distributions. Nonetheless, unlike in methods based purely on local search, the parameters of these distributions confirm good scalability of hBOA with local search. We further argue that standard performance measures for optimization algorithms--such as the average number of evaluations until convergence--can be misleading. Finally, our results indicate that for highly multimodal constraint satisfaction problems, such as Ising spin glasses, recombination-based search can provide qualitatively better results than mutation-based search.}, archivePrefix = {arXiv}, author = {Pelikan, Martin and Ocenasek, Jiri and Trebst, Simon and Troyer, Matthias and Alet, Fabien}, citeulike-article-id = {1741584}, citeulike-linkout-0 = {http://arxiv.org/abs/cs.NE/0402030}, citeulike-linkout-1 = {http://arxiv.org/pdf/cs.NE/0402030}, day = {15}, eprint = {cs.NE/0402030}, keywords = {bayesian-edas, boa, eda-theory, edas, ising}, month = {Feb}, posted-at = {2007-10-24 08:09:07}, priority = {2}, title = {Computational complexity and simulation of rare events of Ising spin glasses}, url = {http://arxiv.org/abs/cs.NE/0402030}, year = {2004} }

TY - ELEC ID - citeulike:1741584 L3 - citeulike-article-id:1741584 N2 - We discuss the computational complexity of random 2D Ising spin glasses, which represent an interesting class of constraint satisfaction problems for black box optimization. Two extremal cases are considered: (1) the +/- J spin glass, and (2) the Gaussian spin glass. We also study a smooth transition between these two extremal cases. The computational complexity of all studied spin glass systems is found to be dominated by rare events of extremely hard spin glass samples. We show that complexity of all studied spin glass systems is closely related to Frechet extremal value distribution. In a hybrid algorithm that combines the hierarchical Bayesian optimization algorithm (hBOA) with a deterministic bit-flip hill climber, the number of steps performed by both the global searcher (hBOA) and the local searcher follow Frechet distributions. Nonetheless, unlike in methods based purely on local search, the parameters of these distributions confirm good scalability of hBOA with local search. We further argue that standard performance measures for optimization algorithms--such as the average number of evaluations until convergence--can be misleading. Finally, our results indicate that for highly multimodal constraint satisfaction problems, such as Ising spin glasses, recombination-based search can provide qualitatively better results than mutation-based search. TI - Computational complexity and simulation of rare events of Ising spin glasses KW - bayesian-edas KW - boa KW - eda-theory KW - edas KW - ising AU - Pelikan, Martin AU - Ocenasek, Jiri AU - Trebst, Simon AU - Troyer, Matthias AU - Alet, Fabien PY - 2004/Feb/15/ UR - http://arxiv.org/abs/cs.NE/0402030 ER -