Metaheuristics are randomised search algorithms that are e ective at nding "good enough" solutions to optimisation problems. However, they present no justi cation for the generated solutions, and are non-trivial to analyse. We propose that identifying which combinations of variables strongly in uence solution quality, and the nature of that relationship, represents a step towards explaining the choices made by the algorithm. Here, we present an approach to mining this information from a \surrogate tness function" within a metaheuristic. The approach is demonstrated with two simple examples and a real-world case study.
Metaheuristic algorithms exploit randomised search to approximate optimal
solutions to di cult optimisation problems such as workforce scheduling or
making thousands of design decisions for a house. Explainable AI has made
advances towards explaining the decisions of black-box systems like deep neural
networks [
For an optimisation problem, a decision maker might seek two key insights
to accept solutions found by metaheuristics. I1: Does the solution solve the
problem, or have we found an error or loophole in the problem's de nition? I2:
What characteristics of the solution are crucial to optimality, and which are
simply artefacts of the stochastic processes inherent to metaheuristics, that could
be amended for aesthetic or implementation purposes? In this paper, we
propose that such explanation can be achieved by identifying which combinations
of variables strongly in uence solution quality, and which can be ignored; the
ideal values for the variables; and interactions between variables. We do this by
following an approach to mining \surrogate tness functions" described in [
∗Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Surrogate tness functions [
This paper revisits the Markov network Fitness Model (MFM), a probabilistic
model for bit string encoded problems originally developed for the Estimation of
Distribution Algorithm, DEUM [
We begin with a brief recap of the Markov Network Fitness Model surrogate,
further detailed in [
K
With a large enough population of solutions and their tnesses, (1) yields a
system of equations that can be solved using a least-squares approximation to
estimate the K (this stage can be seen as a linear regression problem [
Mining the MFM
[
Two examples from [
The bio-control problem seeks to minimise insect larvae growth on mushrooms by choosing optimal times to spray the crop with nematode worms. Solutions are encoded as 50 bits representing times at which the bio-control spray is applied or not. Most of the univariate coe cients (each corresponding to one bit) (Figure 1) are positive, indicating no spraying. The few negative coe cients, when spray should be applied, coincide with growth points in the life cycle of the pest being targeted (represented by the blue dotted line).
For both problems, MFM coe cients, determined using only a few hundred randomly generated solutions, have a clear relationship with the underlying problem. The coe cients point towards optimal solutions and show sensitivity of the objective to particular variables or variable interactions. 4
Our case study seeks to optimise the location
of windows on a Chicago commercial
building's southern facade; the goal is a design
which minimises energy use and capital
construction cost. This was previously studied
in [
Objective 1: Minimise Energy. The unweighted sum of energy for heating, cooling and lighting over a year, computed by the EnergyPlus building simulation package. This is non-trivial: incoming sunlight reduces electric Fig. 2. Fully glazed facade lighting demand but solar gain increases cooling and decreases heating energy demand. Heat loss through glass at night has the opposite e ect. A single simulation run takes 1-2 minutes on an Intel i7 CPU: the original motivation for the use of surrogates to speed up the optimisation.
Objective 2: Minimise Cost. Construction cost for speci ed window con guration. A straightforward linear function of the number of windows. Variables and Encoding. The wall is divided into 120 cells in a 15 x 8 grid. Each cell may be glazed or unglazed. This translates into a 120 variable bit string. A bit is true for a glazed cell and false otherwise. 5
Comparisons and analysis of results from several multi-objective evolutionary
algorithms applied to this problem can be found in [
Minimal, median and maximal cost solutions from the approximated Pareto front from a typical run are plotted in Figure 3. The substantial range of capital costs re ect the extra expense of glazing. The range of energy consumption is more modest, but still around 6% of the maximal consumption, representing considerable savings in emissions and energy costs over the building's life.
The approximated Pareto-optimal trade-o and the speci c designs in each solution are already of great value to a decision maker, but themselves raise some questions. It would appear that, as a result of the algorithm's randomness, it missed the lowest cost solution (no glazing). It also produced odd glazing shapes on the higher-cost solutions. It would be helpful to know what the impact might be of making small aesthetic changes to these solutions.
One approach to explaining the contribution of individual glazing cells to
optimality is a local sensitivity analysis [
We constructed two MFMs for this problem; one each for energy and cost. We now mine these surrogates for explanations. The structure for the MFM (the neighbourhoods for each xi) was xed. Two sets of experiments were performed using di erent structures for the MFM.
Lattice structure. Initially, a grid
structure was adopted, based on the
intuition that glazing one cell would
impact neighbouring cells. The MFM
included 120 univariate VK (one term
per cell), and 240 pairwise VK
representing neighbouring cell pairs. Thus,
there are 361 parameters in the model
(including a constant), and a training
population of around 1.1x this value
should be used to obtain a good model
[
The mean and standard deviation for each K in the MFM was calculated over all the energy MFMs and all the cost MFMs. These values are plotted in Figure 5 for energy (for cost, the plot is similar, but with the higher points level rather than showing a gradual increase). The jump at 120 coincides with the change from univariate K s to the pairwise K s. For both energy and cost objectives, the pairwise K values are all near zero. This means that they have little to no in uence on either objective: it would seem that only the univariate
K have any in uence on the objectives (having non-zero values in the MFMs for both objectives) and our intuition on the appropriate structure was incorrect. Univariate structure. We repeated the process using a univariate structure (i.e., 120 K s, one per variable) for both MFMs. The model was trained on the ttest 140 of the rst 1000 solutions visited in the optimisation run. Median r2 for the models on 400 unseen solutions was 0.993 for energy and 0.998 for cost. The mean values for these coe cients for energy are shown in Fig 6 as a grid corresponding to the facade. Cell colour shows each coe cient's value relative to the others: high values being blue, through white to red. For both objectives, all k are positive.
For the energy objective, there is a clear (though small) bias towards the upper right (East) of the facade, also visible in the rising values in Fig 6, suggesting that glazing should be concentrated in that region. This matches the local sensitivity analysis (Fig 4), but has the bene t that no additional evaluations were needed, and is rooted in models representing solutions spanning several generations rather than just the last one. It is also concordant with the real-world problem: high central glazing allows maximum penetration of daylight with less glazing, balancing heat gain+loss, and lighting needs (although it is less clear speci cally how much glass there should be or precisely to place it, thus motivating the use of optimisation). A slight bias East also catches more early morning sunlight. Not illustrated due to space, for cost, the magnitudes of the k are highly similar, suggesting that optimal solutions should be unglazed and individual cells make equal contributions to cost. This matches with the problem de nition, whereby an equal cost is associated with each cell. 7
We can make a step toward explainability for optimisation by metaheuristics by reporting relationships between problem variables and sensitivity of the objectives to them. This brings several bene ts: { Knowing the sensitive variables, solutions can be adjusted for factors not considered by the optimisation, knowing the likely impact on optimality. e.g., odd window shapes made more visually appealing. { If the returned solutions match the conclusions drawn from the model, the decision maker can have added con dence in the optimality of the results. { The model can point towards global optima long before the algorithm converges. With the glazing problem, the model suggested the overall glazing shape after the rst 1000 of a 5000 solution run. This could show where algorithm has missed the global optimum, and with long-running simulations, make early suggestions of optima: particularly helpful if this indicates aws in the problem formulation.
We applied the MFM surrogate to a glazing optimisation problem. Analysis
of the model coe cients yields simple explanations for the optimisation results.
This builds on earlier work [