Estimation-of-Distribution Algorithms: Theory and Applications

Jonathan L. Shapiro, Franz Rothlauf, Carsten Witt, Vanessa Volz, Jasmin Brandt, Timo Kötzing, Martin S. Krejca, Aishwarya Radhakrishnan, Andrew M. Sutton, Marcus Schmidbauer, Duc-Cuong Dang

To get everyone on the same page, Jonathan Shapiro highlighted the importance of exploitation and exploration as in the case of Reinforcement Learning (RL): at any time one always have to decide between using the current information to exploit immediate rewards, versus exploring the alternatives that may lead to better rewards later.

The first question we discussed is whether it is a good strategy to explore first and exploit later. This is the case with traditional Evolutionary Algorithms (EAs), the algorithms often converge in the end. Some participants noted that this is not the case for EDAs like BoA. Marcus Schmidbauer added that in the case of GOMEA, a multivariate model-building algorithm, it is a combination of extreme exploitation with extreme exploration. Timo Kötzing added a comment that there is a fundamental difference between RL and EA: in EAs, the rewards are not immediate. The notion of neighbourhood is also important: EAs seem to prefer having nearby good solutions over having random good solutions that are hard to recombine. Jasmin Brandt commented that we may need a proper definition of exploitation and exploration. According to Franz Rothlauf, exploitation means finding good solutions nearby the ones already explored, while doing anything else is exploration.

We then discussed different parameters that can influence the search towards either exploitation or exploration. In the case of EAs, it appears that that the mutation rate is often settled to one on average per mutation. However, one should be careful about which EAs are considered. In the case non-elitist EAs, the balance between mutation and selection does not necessarily lead to mutation rate of $1/n$ but it depends on which selection is used or how it is set. For example, in tournament selection of size $k$ the balance is found exactly at mutation rate $\ln (k)/n$. For EDAs, the following parameters can influence the search: the inverse of the population size $1/K$ in cGA; for UMDA, this is the ratio $\mu /\lambda$ when the ($\mu$,$\lambda$)-truncation selection is used to decide which solutions to keep in order to model the next distribution; the learning rate $\rho$ in PBIL and related algorithms like Ant Colony Optimisation. From the theory side, how to control these parameters optimally for simple problems remains an open question as the existing lower bound techniques and results are scarce.

A common set of parameters that is important for all the above-mentioned algorithms to avoid the possibility of premature convergence is the borders that limit the frequencies of bits to be strictly below $1$ and strictly above $0$. In practical applications, the use of these borders is essential as one may absolutely wants to avoid degenerated distributions, an example is the application Franz Rothlauf has in his talk. Related to this, Jonathan Shapiro asked, in practices how to avoid identify that the learned model is general enough and not over-fitted. This is a hard question, and often the case this comes back to a good engineering practice, or a familiarity with the problems and algorithms. Martin S. Krejca put forwards the following question: Is there any way to adjust the borders, somehow reflecting the amount of confidence on doing the right thing at any given time? Jasmin Brandt added that in the case of multi-arm bandit problems, the confidence interval is a well-defined concept. A related question we discussed is how to detect that the entropy of the model is too low early on, or are the techniques developed for stagnate detection in EAs useful for EDAs?

In summary, we all agree that the balancing exploitation and exploration is relevant to all areas of Evolutionary Computation, including EDAs. We know how to deal with them for practical problems, however formulating them as statements with rigorous proofs remains challenging. The good news is that even in a lack of recommendations, there is a technique from theory that allow selecting the values for parameters efficiently based on power-law distributions.

Jonathan L. Shapiro, John McCall, Joshua D. Knowles, Carola Doerr, Vanessa Volz, Nikolaus Hansen, Josu Ceberio Uribe, Valentino Santucci, Alistair Benford, Andrew M. Sutton, Martin S. Krejca, Roberto Santana, Duc-Cuong Dang

The breakout session began with a discussion of the trade-off between having an accurate model, at the expense of intensive computation, as in the case of building graphical models in EDAs, versus having less accurate models that are faster to learn, but at the risk of misleading or slowing down the search for optimal solutions.

We agree that in practical runs of EDAs, there may not be a clear separation between the phase of learning an accurate model and that of using that model to find optimal solutions as the model is often learned along the way. More importantly, as pointed out by Nikolaus Hansen, for solving an optimisation problem, finding an accurate model can be misleading: we only want to find the best solutions. In fact, we want models that can help the search in finding better solutions, or in finding improvements to the existing solutions, more efficiently. In other words, a good model should help guide the search towards the optimal solutions, and need not be an accurate description of those solutions.

We then discussed whether there are practical problems where there are clear interactions between variables, but the univariate model is still useful, as this is often argued by theory research (most existing theory papers only focus on univariate models). John McCall gave an example of such settings for a scheduling problem in chemotherapy. In this application, thousands of interactions between variables are detected between the variables, but univariate algorithms like PBIL/DEUM still outperform hBOA. The current hypothesis for the inefficiency of hBOA, which is stuck with medium quality solutions, is that this is due to the dominance of different terms in the objectives. It could be very interesting if there is a mathematical description that can capture this property.

As the discussion progressed, we asked the question whether the computational budget or parameter settings, like the sample size, can have some influence on the success of univariate models. This is because the univariate model is cheaper to learn, compared to models with interactions. From the practical side, practitioners have noticed that on some problems, the population or the sample size needs to be set above a certain threshold for the search to be successful. We then discussed the settings in which the computational budget is less of an issue, whether multivariate models are always the better choice. Nikolaus Hansen mentioned a counter-example of the sector-sphere function where univariate performs best. In addition, trying to adapt the step sizes on this function may worsen the progress of optimisation. Similar effects can be observed for the case of LongPath and SurfSamp in discrete optimisation, and this is related to the general issue of balancing exploitation and exploration.

We then discussed whether multivariate models might limit the diversity of solutions. In other words, in multivariate EDAs, how does the entropy of the model evolve as the search progresses? Nikolaus Hansen said that it tends to increase as we learn more about the models. He added that a good indicator of a good model is that the entropy of sampled solutions within a fitness level should be high. Carola Doerr drew the parallel with black-box complexity: if we know more about the problem at hand, we want to have higher entropy. For example, if we know that we are solving a OneMax-type problem, the best algorithm is to sample $O(n/\log n)$ solutions uniformly at random, and then infer a consistent target string based on the acquired fitness of these random solutions.

The following questions were also discussed during the breakout session.

1. 1.

   Is it always a good practice to first try univariate models first and then try the multivariate ones? There is no consensus among the participants on this question.

2. 2.

   What is the current state of theory research on multivariate models? As far as we know, the only theory research on multivariate models is about linkage-learning, e.g. the papers by Dirk Sudholt and co-authors.

3. 3.

   Should we model improvement moves (or directions) instead of that of solutions? After our discussion, we incline towards modelling the improvement moves.

4. 4.

   Is there any benefit for building a model from scratch instead of incremental learning, and vice-versa? This is open.

5. 5.

   Are the weights of detected interactions important to learn, and how to use them? This is open.

6. 6.

   Is there a way to learn the model implicitly, or somehow avoid the burden of building an explicitly accurate model? This is open, but there are related ideas about projecting the search into other spaces where there may be less deception.

Alistair Benford, Jasmin Brandt, Josu Ceberio Uribe, Duc-Cuong Dang, Benjamin Doerr, Carola Doerr, Martin Fyvie, Nikolaus Hansen, Joshua Knowles, Timo Kötzing, Martin S. Krejca

This breakout session discussed the phenomenon of genetic drift in estimation-of-distribution algorithms (EDAs). The discussion meandered a bit while it took place. The following summary rearranges it logically, grouping it in terms of different points that were discussed.

We started the session by Benjamin’s explanations of the mathematical results for genetic drift in univariate EDAs on binary problems, which mostly concerns the cGA and the PBIL. In this setting, genetic drift refers to the random movement of frequencies in the probabilistic model without any true signal from the objective function. In the case of constant objective functions, we have strong concentration bounds that tell us how long it takes until a frequency randomly moves by at least $\epsilon$. It was also mentioned that the resulting bounds can be used for a smart restart scheme, which recommends to restart an EDA whenever it is likely that a frequency could have moved too far due to genetic drift. When restarting, the step size of an update should be halved (which usually means that the population size should be doubled).

This explanation raised the question how realistic this analysis is, since real objective functions are not constant. It was clarified that genetic drift is usually superimposed by the true signal of an objective function, but that it is hard to analyze it in its generality, which is why the mathematical analysis assumes a constant objective function, which represents the full effect of pure genetic drift.

A natural question that followed was whether this phenomenon also shows up in practice and whether it is relevant. It was agreed upon that genetic drift does show up in practice, but it was less clear whether it is relevant. The consensus was ultimately that is is indeed relevant but that practitioners may not care about it due to other, more pressing issues, such as budgetary constraints or the wishes of the customer. A typical approach is to simply rely on best practices, which traditionally aim at reducing the impact of genetic drift (albeit without mathematical guarantees).

Afterward, the discussion moved to other types of search spaces. It was mentioned that genetic drift is also present for multi-valued discrete search spaces, where it is even easier to have a greater (detrimental) effect, due to generally smaller starting values of the frequencies. Afterward, the question came up to what extent genetic drift is visible in continuous search spaces. The conclusion was that it also shows up there and also poses a problem.

With genetic drift being a general problem, other questions were whether it is possible to detect genetic drift somehow and how it behaves in the presence of noise. Regarding the detection, it was mentioned that the sig-cGA operates on only updating a frequency when a statistical significance in the objective function is detected. This approach allows to directly measure (with a certain confidence) that genetic drift did not occur. This approach should not be largely affected by noise. Otherwise, more traditional EDAs are known to cope well with noise, but only if the step size is chosen sufficiently small (suggesting again a smart restart scheme in the general case).

These points were followed up by questions how genetic drift relates to similar phenomena in other settings, such as multi-armed bandits and reinforcement learning. For multi-armed bandits, it was not so clear how this directly translates to the setting of EDAs, since there is no real exploitation in the binary domain, as the two possible choices for a variable are either 0 or 1. However, assigning a confidence to each frequency is something that aligns well with multi-armed bandits and seems like a good strategy. As for reinforcement learning, the question was whether the approach of adding uniform samples periodically with a certain probability could prove promising to counteract genetic drift. The argument was brought forth that uniform samples are not a good choice. However, in continuous problems, it is not uncommon to add noise on purpose to the samples and to then assess whether the selection is affected by this choice. If it is, then the learning rate is increased. Something similar could potentially prove useful for EDAs as well.

In the same vein as the connection to reinforcement learning, the question came up whether it is smart to introduce an artificial bias into the update that explicitly counteracts genetic drift. This has been done before in theoretical studies to great effect, but the paper on the sig-cGA shows that this can also easily backfire. A static approach is not useful, as the bias can be stronger than the signal of the objective function, which renders optimization unsuccessful. However, a dynamically adjusting approach could maybe work.

In conclusion, genetic drift is a real and important problem that is hard to detect. Being able to detect it could tremendously improve the situation. The sig-cGA as well as the concept of adding noise on purpose and adjusting the step size based on whether this affects selection can be promising ways to reduce the impact of genetic drift. However, these details need to be worked out in greater detail analytically.

John McCall, Marcus Schmidbauer, Benjamin Doerr, Timo Kötzing, Martin Fyvie, Aishwarya Radhakrishnan, Andrew M. Sutton, Nikolaus Hansen, Carsten Witt, Duc-Cuong Dang.

The group considered the question “How much precision is needed in linkage learning?” More fully, for an EDA that learns linkage, either in the form of a PGM (Probabilistic Graphical Model) or more broadly as families of subsets of variables, to optimise a problem, is it necessary to incorporate in the EDA model all linkage that is detected.

The discussion focussed around a published paper comparing algorithm performance on a real world chemotherapy problem. The chemotherapy problem is based on binary strings encoding dosages of multiple drugs over a time period. The problem contains thousands of variable linkages based on tumour-size, dosage constraints and toxic side-effects on the patient. The paper compares a leading multivariate-PGM EDA, hBOA, against a GA and three univariate EDAs (UMDA, PBIL and a univariate version of DEUM).

The counter-intuitive result is that the univariate algorithms, led by UMDA, all converge to the (best-known) optimum much faster than hBOA, with far fewer fitness evaluations and massively less clock time. This is despite the fact that the univariate EDAs learn no interactions. The GA is outperformed on this problem by all of the EDAs.

There was discussion on the linkage detection method used – if there is no thresholding then spurious linkages can be detected that have no significance for the problem. hBOA uses internal linkage parameters that do use thresholding, and note that the inventor of hBOA (Martin Pelikan) collaborated on the paper. Moreover, a separate detection algorithm (LDA) was used to verify the linkages. The paper concludes that, in this example, multivariate linkage is inessential.

A contrasting example in the case of Concatenated Traps was discussed. Here it can be shown theoretically that P3 (Parameter-less Population Pyramid), a model-building EA related to EDAs, requires multivariate linkage-learning to solve the problem in polynomial time. If only univariate learning is allowed (i.e. no linkage) P3 is shown to require exponential time to solve Concatenated Traps. Therefore in this example, multivariate modelling is essential.

Some more general insight into when linkages are essential or inessential can potentially be gained through Walsh function decomposition of binary functions. More research is needed into how robust Walsh coefficients are in terms of detecting essential linkage, particularly under function scaling.

The original question on precision remains open.