  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.
