Estimating the Number of Local Optima in Multimodal Pseudo-Boolean Functions: Validation via Landscapes of Triangles

Abstract

Pseudo-Boolean functions are often multimodal, and it is of interest to find multiple optima. However, the problem of estimating the number of local optima has not been much studied in the combinatorial setting. Since exhaustive enumeration is generally prohibitive, we study an alternative in this paper. Our method, which uses the celebrated Birthday Paradox “in reverse,” enables us to estimate the number of local optima in fitness landscapes. We study the method analytically and experimentally, using a new synthetic problem, TRIANGLE. This problem allows us to vary the number of optima and its distribution easily but understandably, which enables analytical validation of our experiments. We conclude by discussing how the approach may be applied and extended in the future.

Xavier F. C. Sánchez Díaz

PhD candidate in Artificial Intelligence

PhD candidate in Artificial Intelligence at the Department of Computer Science (IDI) of the Norwegian University of Science and Technology