Semester 1, 2024-25

The SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary Algorithms

Per Kristian Lehre, University of Birmingham

Tuesday 8 October 2024, 15:00-16:00
Nuffield, G13

Many real-world problems require finding optimal solutions within complex, high-dimensional spaces Evolutionary Algorithms (EAs) are popular optimisation heuristics inspired by natural selection. Theory of evolutionary computation defines the runtime of an EA as the number of times it evaluates the fitness function until a solution with satisfactory quality is evaluated. Runtime analysis is the mathematical study of the distribution of the runtime of EAs. For many EAs, it is fairly well understood how the runtime depends on algorithmic parameters such as population size, mutation rate, and selective pressure.

The runtime of EAs depends critically on the structure of the "fitness landscape" (optimisation problem). The impact of certain structural properties such as plateaus and gaps are now well understood. However, the more general relationship between fitness landscape structure and the runtime of EAs is still poorly understood. Recently, Dang et al. (2021) introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs. However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy.

We generalise the previous work to a novel, complete hierarchy for all pseudo-Boolean functions. The hierarchy is consistent with existing results for the runtime of EAs. The hardest part of the hierarchy consists of problems satisfying the No Free Lunch theorem. The easiest part contains well-known theoretical benchmark problems, easy for EAs. The intermediary parts contain instances of NP-hard problems. Problem classes where local optima sparsity exceed fitness valley density are shown to have exponential black-box complexity. We study how random perturbations of a function can change its classification. E.g, randomly perturbing search points in OneMax with constant probability leads to a problem class that can still be optimised efficiently with appropriately tuned non-elitist EAs. Our work provides a significant step towards a comprehensive theory of EA performance, with implications for algorithm design and the analysis of complex optimisation problems.

This is joint work with Duc-Cuong Dang and Anton Eremeev.

Can We Successfully Approximate Large Sparse Hessian Matrices?

Jennifer Scott, Rutherford Appleton Laboratory

Tuesday 26 November 2024, 14:30-15:30
Arts 103

The success of large-scale optimization algorithms frequently depends on the availability of (approximate) Hessian matrices. If we are extremely fortunate, an analytic expression may be available. But this is not generally the case and it is frequently difficult to provide second derivatives. Therein lies our challenge.

Existing methods for approximating Hessian matrices either do not impose sparsity and their computational cost is prohibitive for large problems. To overcome these limitations, we propose two novel approaches. Both are based on using data from a sequence of previous iterates to build the approximation. The first reformulates the problem as a large-scale linear least squares problem while the other seeks to satisfy as many componentwise secant equations as necessary to define each row of the Hessian matrix. A naive application of this idea is prohibitively expensive when the Hessian has some relatively dense rows but by carefully taking into account the symmetry and connectivity of the Hessian matrix, we are able devise an approximation algorithm that is fast and efficient with scope for parallelism. Sparse Hessian matrices taken from the CUTEst test problem collection for optimization illustrate the effectiveness and robustness of the new ideas.

This is joint work with Jaroslav Fowkes and Nick Gould.