Estimation-of-Distribution Algorithms: Theory and Applications

According to the observation made by Gordon Moore that the number of transistors in a dense integrated circuit doubles about every two years [1], it has been projected that general purpose computers may struggle to cope with computational demand in the future. There has therefore been research interests in the use of other specialised hardware such as quantum computers. Within the context of solving optimisation problems, quantum computers and quantum-inspired hardware have been developed. Quadratic Unconstrained Binary Optimisation (QUBO) is a common formulation used by quantum and quantum-inspired solvers. Examples of quantum or quantum-inspired QUBO solvers are D-wave’s Advantage released in 2020, which uses quantum hardware and has the capability of 5,000+ quantum bits (qubits) [2], IBM’s Eagle which is being extended from a 27-qubit solver to 127-qubit [3] and Fujitsu’s Digital Annealer (DA) which uses application specific CMOS to find optimum or sub-optimum solution to problems formulated with up to 100,000 bits [4]. The DA has advantages over other quantum-based algorithms such as scale (up to 100,000 bits), precision (64bit gradations), stability (stable operation at room temperature with digital circuits) and connectivity (easy to use with total bit coupling) [4].

Estimation of Distribution Algorithms (EDAs) have been applied to many problem classes including QUBOs. Quantum-inspired EDA (QiEDA) [5] have also been designed for and applied to problems formulated as QUBO e.g., TSP [6] and feature selection [7]. It is however unclear how these algorithms compare to other QUBO solvers such as the DA. The need to design EDAs that are not problem specific and that take advantage of specialised hardware is therefore motivated.

This talk is on the long-running theme of “structure” in EDAs. I will introduce Markov network EDAs, which use an undirected probabilistic graphical model relating binary decision variables to the fitness distribution. This model’s accuracy and, in turn, algorithm efficiency, depend on the neighbourhood structures that are captured within it. That is, does the model treat variables independently, or are bivariate or higher order interactions considered. I will briefly recap some early results looking at the impact of problem and algorithm structure in this context, covering well-known benchmarks including Onemax, Trap, and MAX3SAT, before looking at a systematic study covering 2 and 3 bit problems which shows that not all structure is essential to problem solution.

We propose a general model for univariate EDAs that encompasses the four classic EDAs. We prove a genetic drift result for the general model that implies the corresponding known results for the particular algorithms. Finally, we show that the general class of algorithm contains EDAs which are more powerful than the existing ones (with optimal parameters).

Genetic drift, that is, the random movement of sampling frequencies not justified by a fitness signal, usually leads to an inferior performance of EDAs. In this talk, we quantify how the parameters of the four common univariate EDAs lead to genetic drift. This allows to set the parameters in a way that during the desired runtime, the genetic drift is low enough to avoid the undesired effects. We also describe how to use this quantification to define a smart-restart mechanism that, provably, leads to a performance asymptotically equal to the one obtainable from optimal parameter values.

With invariance as major design principle, we present a canonical way to turn any smooth parametric family of probability distributions (on an arbitrary search space) into a continuous-time black-box optimization method and into an “IGO algorithm” through time discretization. The construction is based upon (i) the natural gradient over the family of distributions to express (intrinsic) update directions and (ii) the cumulative distribution function of the f-values under the current sample distribution to express (invariant) preference weights. The construction recovers well-known algorithms like cGA, PBIL or Natural Evolution Strategies and major aspects of CMA-ES.

In this tutorial we show some known and new results in statistical properties and methods for permutations

• $\mathrm{■}$

  Uniform sampling : in this section we show how to generate permutations uniformly (where all the possible permutations have the same probability of being generated) among all those at a given distance for the identity.

• $\mathrm{■}$

  Distributions on permutations: We show the different and most common distribution for permutation data, motivation, main statistics and inference algorithms.

• $\mathrm{■}$

  Depth function: we show a typical function for real-valued data (its novel adaptation for permutation spaces)

• $\mathrm{■}$

  Experiments: in order to contribute we present an easy to use code with the above mentioned methods and operations.

The problem of permutation-aggregation (PA) is the main optimization problem in statistical community. It is equivalent to the median computation in the real-valued vector spaces. It can be posed under different distances and the complexity varies for these cases: it is known to be NP-hard for some distances, polynomial for others and unknown (although conjetured to be NP-hard for other)

This talk introduces a current work on the problem of aggregating permutations. We introduce an aggregation algorithm that is valid for several distance. This is an approximated algorithm for PA for which we can characterize the conditions for convergence. Moreover, we bound the expected error and the expected run-time. We also introduce simulations that confirm the theoretical results.

The theoretical analysis of estimation-of-distribution algorithms (EDAs) has gained a lot of momentum during the last decade. In this talk, I introduce the basic concepts and terminology used in the analysis of EDAs, and I summarize most of the latest results. The aim is to provide the audience with a solid foundation for understanding theoretical analyses of EDAs and to give it a good overview about the state of the art.

Recently, there have been mixed theoretical and empirical evidence as to whether univariate estimation of distribution algorithms (EDAs) such as the UMDA perform worse than classical EAs on multimodal/deceptive problems. We discuss empirical investigations of a range of EAs and EDAs on NK-landscapes, as well as theoretical analyses of UMDA end EAs on the Deceptive Leading Ones problem. These results point to the limitation of univariate EDAs under certain parameter regimes.

This talk pickes up the topic of Andrew Sutton’s previous discussion of EDAs on noise. I discussed several instances in which Evolutionary Algorithms (EAs) struggle in noisy or dynamic environments. All examples have the fact at their heart that the mutation generator of EAs is intrinsincally biased. In contrast, EDAs are unbiased (except for the boundaries, which are exceptional for EDAs). This is the reason why EDAs are often much more robust to noise than EAs.

In this flash talk, I will present some recent interpretations of low-level conscious processing that resemble the way EDAs operate. Unconscious perceptions have local inconsistencies that can be interpreted as a probability distribution. A conscious perception is then simply a sample from this distribution. Episodic memory seems to be based (or to consist) purely on these samples, while the probabilistic model is also updated by unconscious perceptions.

Although there is a large amount of research in black-box optimization problems in the continuous domain, there is far fewer algorithms designed for permutation spaces, where the input points in the decision space represent a ranking or an ordering, in particular, when the number of evaluations is extremely limited, e.g., to a number of function evaluations between 100 and 1000. We describe two alternative approaches: CEGO, which is a Bayesian (i.e., surrogate-based) optimiser using Kriging (i.e., Gaussian Processes) regression and a distance metric between permutations, and UMM, an Estimation-of-Distribution algorithm based on the Mallows model. We discuss results on classical combinatorial problems and a real-world-like benchmark inspired by an application to Space exploration and on the effect of starting from a very good initial solution versus completely random ones. We conclude by discussing that there is still room for improvement in existing Bayesian and EDA optimisers in this particular context.

An EDA constructs a probabilistic model that estimates the distribution of good solutions / fitness. Typically the model is a probabalistic graphical model (PGM) composed of structure components with weights. Bayesian and Markov networks are two widely used PGMs [1, 2]. EDAs select good quality solutions from the current population, use them to estimate the topology and parameters of a PGM and them sample the PGM to create a successor population.

That part of the modelling process that relates to learning the topology of the PGM is known as structure learning. Structure components relate directly to subsets of variables (graph components of the PGM) and can be thought of as indicating patterns that make a contribution to fitness depending on the values of the variables. This is strongly related to the concept of epistasis which means strong interactions in determining individual fitness between separated genes. Repeated runs of an EDA may learn different structure and different structure elements may be present in models generated at different stages of a single run. A mainstream outcome of EDA research was to develop a series of EDAs for a wide range of problems that used PGMs with increasingly complex structure to tackle challenging problems with high degrees of epistasis and with a range of representations e.g. MAXSAT, Ising problems, NK landscapes, continuous benchmark sets, QAP, PFSP, TSP, etc. EDAs that use PGMs are classified as univariate, bivariate or multivariate according to the structural complexity of their models.

A key observation is that fitness may be thought of as a mass distribution and so by normalising, or other means, we can create “true” probabilistic graphical models of the fitness distribution, examine their structure and explore the relationship between this structure and the structure estimated by EDAs. While it is not always possible to determine all of the true structure of a fitness function, structure discovery algorithms exist – e.g. Heckendorn and Wright [3]. It is possible at reasonable cost in evaluations to “probe” for structure of a certain complexity by evaluating carefully selected solutions. One can ask for a given problem, what structure does an EDA need to discover to optimise efficiently?

A folklore intuition exists that, on optimisation problems with a complex true structure, algorithms that can detect and model complex structure will exhibit superior performance to algorithms that cannot do so. Many papers exist showing multivariate algorithms outperforming univariate or bivariate algorithms on benchmarks. In the talk, we present a real world cancer chemotherapy optimisation problem with a high degree of bivariate structure on which univariate EDAs, despite being incapable of detecting this structure, outperform hBOA, one of the most powerful and widely applied multivariate EDAs [4].

The result is important because a drawback of multivariate EDAs is that the computational cost of model building can quickly become significant compared to overall function evaluation costs as structural complexity increases. An understanding of when structure learning is unnecessary to, or even impedes, optimisation may lead to important insights for the design of EDAs that use PGMs. A key observation is that most PGM EDAs operate invariantly to order-preserving function transformations, that is to say they are invariant across welldefined function classes. In this talk we share some results from [5] where we algebraically characterise inessential structure for such EDAs on pseudo-boolean problems.

In this talk four different applications of the Estimation of Distribution Algorithms (EDAs) have been shown. The first application [1] is a complex multivariate optimization problem where a Gaussian Bayesian network is used a probabilistic model where some prior knowledge is involved and fixed as evidence in the model to restrict the search space. The second one is a Feature Subset Selection problem with time series, where not only the optimum subset of variables are chosen, but also de ideal time series transformation that improves the model. An EDA as a wrapper approach is implemented. The third one is a Real Estate portfolio optimization problem where it is aimed to minimize the risk of the investment and to maximize the profit of the portfolio. It is presented how EDA deal with large scale data in this problem. The last optimization problem [2] consists of optimizing some hyperparameters of a concrete quantum circuit. This talk leads to discussion about the probabilistic model complexity needed to approach the real-world optimization problems.

Some real applications involve leading with variables that do not fit a normal distribution in the continuous space. Thus, some more complex algorithms should be used rather than the well-known Gaussian Bayesian network. A novel method is presented where EDA decides whether the variables will fit or not a Gaussian distribution during runtime. Some results are shown comparing the approach with some other state-of-the-art methods such as EGNA, JADE or CMA-ES for some specific benchmarks, and also explaining the performance of the approach during runtime.

This is a bit about automated algorithm configuration. It is divided in two aspects. The first highlights the main advantages of addressing algorithm design and configuration by algorithmic techniques and describes the main existing techniques. We show as one of the various available ones the irace algorithm for automated configuration. The second highlights the advantages of automated configuration. In particular, we show how flexible algorithm frameworks can support the automatic design of high-performing hybrid stochastic local search algorithms. We show this by the example of nine permutation flow shop problems for which we obtained in each one of these a new state-of-the-art algorithm even though they have on average around 500 parameters.

Understanding the dynamics of the underlying probabilistic model is a fundamental problem in estimation-of-distribution algorithms. We consider the compact Genetic Algorithm (cGA) on the function OneMax and show how the choice of the update strength $1/K$ affects performance. For small $K$ updates have a large impact and genetic drift leads to chaotic behaviour and exponential times. For large $K$, genetic drift is negligible since updates are small and the algorithm slowly learns good bit values. For medium $K$, frequencies may hit their lower borders, but these wrong decisions can be reverted efficiently. The parameter landscape has a bimodal shape with two asymptotically optimal parameter values. A similar, but more extreme effect is observed for the multimodal Cliff function where the cGA is inefficient for all values of $K$ and the best (exponential) runtime is obtained for exponential values of $K$ that prevent genetic drift.

A search algorithm scales gracefully with noise when a polynomial increase in noise intensity can be overcome by at most a polynomial increase in resource usage. In this talk, I outline a few results related to graceful scaling on additive posterior noise and estimation of distribution algorithms.