Metaheuristic algorithms are powerful tools for tackling complex optimization problems, but their black-box nature often hinders user trust and understanding. This paper presents a novel methodology for enhancing the explainability of metaheuristics by employing decision trees with splitting criteria based on Partial Solutions. These represent beneficial sub-structures of solutions and provide insights into the problem landscape and solution characteristics. By constructing decision trees that consider the presence or absence of specific patterns in solutions, we produce a transparent model capable of predicting solution fitness.

Abstract Ever since the first large language models (LLMs) have become available, both academics and practitioners have used them to aid software engineering tasks. However, little research as yet has been done in combining search-based software engineering (SBSE) and LLMs. In this paper, we evaluate the use of LLMs as mutation operators for genetic improvement (GI), an SBSE approach, to improve the GI search process. In a preliminary work, we explored the feasibility of combining the Gin Java GI toolkit with OpenAI LLMs in order to generate an edit for the tool. Here we extend this investigation involving three LLMs and three types of prompt, and five real-world software projects. We sample the edits at random, as well as using local search. We also conducted a qualitative analysis to understand why LLM-generated code edits break as part of our evaluation. Our results show that, compared with conventional statement GI edits, LLMs produce fewer unique edits, but these compile and pass tests more often, with the model finding test-passing edits 77% of the time. The and LLMs are roughly equal in finding the best run-time improvements. Simpler prompts are more successful than those providing more context and examples. The qualitative analysis reveals a wide variety of areas where LLMs typically fail to produce valid edits commonly including inconsistent formatting, generating non-Java syntax, or refusing to provide a solution.

Abstract Explaining the decisions made by population‐based metaheuristics can often be considered difficult due to the stochastic nature of the mechanisms employed by these optimisation methods. As industries continue to adopt these methods in areas that increasingly require end‐user input and confirmation, the need to explain the internal decisions being made has grown. In this article, we present our approach to the extraction of explanation supporting features using trajectory mining. This is achieved through the application of principal components analysis techniques to identify new methods of tracking population diversity changes post‐runtime. The algorithm search trajectories were generated by solving a set of benchmark problems with a genetic algorithm and a univariate estimation of distribution algorithm and retaining all visited candidate solutions which were then projected to a lower dimensional sub‐space. We also varied the selection pressure placed on high fitness solutions by altering the selection operators. Our results show that metrics derived from the projected sub‐space algorithm search trajectories are capable of capturing key learning steps and how solution variable patterns that explain the fitness function may be captured in the principal component coefficients. A comparative study of variable importance rankings derived from a surrogate model built on the same dataset was also performed. The results show that both approaches are capable of identifying key features regarding variable interactions and their influence on fitness in a complimentary fashion.

Artificial intelligence methods are being increasingly applied across various domains, but their often opaque nature has raised concerns about accountability and trust. In response, the field of explainable AI (XAI) has emerged to address the need for human-understandable AI systems. Evolutionary computation (EC), a family of powerful optimization and learning algorithms, offers significant potential to contribute to XAI, and vice versa. This article provides an introduction to XAI and reviews current techniques for explaining machine learning (ML) models. We then explore how EC can be leveraged in XAI and examine existing XAI approaches that incorporate EC techniques. Furthermore, we discuss the application of XAI principles within EC itself, investigating how these principles can illuminate the behavior and outcomes of EC algorithms, their (automatic) configuration, and the underlying problem landscapes they optimize. Finally, we discuss open challenges in XAI and highlight opportunities for future research at the intersection of XAI and EC. Our goal is to demonstrate EC’s suitability for addressing current explainability challenges and to encourage further exploration of these methods, ultimately contributing to the development of more understandable and trustworthy ML models and EC algorithms.

No abstract available.

Abstract Profiling is an important tool in the software developer’s box, used to identify hot methods where most computational resources are used, to focus efforts at improving efficiency. Profilers are also important in the context of Genetic improvement (GI) of software. GI applies search-based optimisation to existing software with many examples of success in a variety of contexts. GI generates variants of the original program, testing each for functionality and properties such as run time or memory footprint, and profiling can be used to target the code variations to increase the search efficiency. We report on an experimental study comparing two profilers included with different versions of the Java Development Kit (JDK), HPROF (JDK 8) and Java Flight Recorder (JFR) (JDK 8, 9, and 17), within the GI toolbox Gin on six open-source applications, for both run time and memory use. We find that a core set of methods are labelled hot in most runs, with a long tail appearing rarely. We suggest five repeats enough to overcome this noise. Perhaps unsurprisingly, changing the profiler and JDK dramatically change the hot methods identified, so profiling must be rerun for new JDKs. We also show that using profiling for test case subset selection is unwise, often missing relevant members of the test suite. Similar general patterns are seen for memory profiling as for run time but the identified hot methods are often quite different.

Explainable Artificial Intelligence (XAI) has recently emerged as one of the most active areas of research in AI. While Evolutionary Computation (EC) is also a very active research area, the intersection between XAI and EC is still rather unexplored. This topic was the subject of our Workshops on Evolutionary Computing and Explainable Artificial Intelligence(ECXAI), organized at GECCO 2022 and GECCO 2023. This special issue collects four articles further exploring the intersection between XAI and EC, including both the use of EC for XAI as well as the use of explainability techniques to better understand EC methods.

Abstract Automated program modification underlies two successful research areas — genetic improvement and program repair. Under the generate-and-validate strategy, automated program modification transforms a program, then validates the result against a test suite. Much work has focused on the search space of application of single fine-grained operators — copy, delete, replace, and swap at both line and statement granularity. This work explores the limits of this strategy. We scale up existing findings an order of magnitude from small corpora to 10 real-world Java programs comprising up to 500k LoC. We decisively show that the grammar-specificity of statement granular edits pays off: its pass rate triples that of line edits and uses 10% less computational resources. We confirm previous findings that delete is the most effective operator for creating test-suite equivalent program variants. We go farther than prior work by exploring the limits of delete ’s effectiveness by exhaustively applying it. We show this strategy is too costly in practice to be used to search for improved software variants. We further find that pass rates drop from 12–34% for single statement edits to 2–6% for 5-edit sequences, which implies that further progress will need human-inspired operators that target specific faults or improvements. A program is amenable to automated modification to the extent to which automatically editing it is likely to produce test-suite passing variants. We are the first to systematically search for a code measure that correlates with a program’s amenability to automated modification. We found no strong correlations, leaving the question open.

Airports and their related operations have become the major bottlenecks to the entire air traffic management system, raising predictability, safety, and environmental concerns. One of the underpinning techniques for digital and sustainable air transport is airport ground movement optimization. Currently, real ground movement data is made freely available for the majority of aircraft at many airports. However, the recorded data is not accurate enough due to measurement errors and general uncertainties. In this article, we aim to develop a new interval type-2 fuzzy logic-based map matching algorithm, which can match each raw data point to the correct airport segment. To this aim, we first specifically design a set of interval type-2 Sugeno fuzzy rules and their associated rule weights, as well as the model output, based on preliminary experiments and sensitivity tests. Then, the fuzzy membership functions are fine-tuned by a particle swarm optimization algorithm. Moreover, an extra checking step using the available data is further integrated to improve map matching accuracy. Using the real-world aircraft movement data at Hong Kong airport, we compared the developed algorithm with other well known map matching algorithms. Experimental results show that the designed interval type-2 fuzzy rules have the potential to handle map matching uncertainties, and the extra checking step can effectively improve map matching accuracy. The proposed algorithm is demonstrated to be robust and achieve the best map matching accuracy of over 96% without compromising the run time.

Genetic Improvement of software applies search methods to existing software to improve the target program in some way. Impressive results have been achieved, including substantial speedups, using simple operations that replace, swap and delete lines or statements within the code. Often this is achieved by specialising code, removing parts that are unnecessary for particular use-cases. Previous work has shown that there is a great deal of potential in targeting more specialised operations that modify the code to achieve the same functionality in a different way. We propose six new edit types for Genetic Improvement of Java software, based on the insertion of break, continue and return statements. The idea is to add shortcuts that allow parts of the program to be skipped in order to speed it up. 10000 randomlygenerated instances of each edit were applied to three opensource applications taken from GitHub. The key findings are: (1) compilation rates for inserted statements without surrounding “if” statements are 1.3-18.3%; (2) edits where the inserted statement is embedded within an “if” have compilation rates of 3.2-55.8%; (3) of those that compiled, all 6 edits have a high rate of passing tests (Neutral Variant Rate), >60% in all but one case, and so have the potential to be performance improving edits. Finally, a preliminary experiment based on local search shows how these edits might be used in practice.

Genetic improvement (GI) is a young field of research on the cusp of transforming software development. GI uses search to improve existing software. Researchers have already shown that GI can improve human-written code, ranging from program repair to optimising run-time, from reducing energy-consumption to the transplantation of new functionality. Much remains to be done. The cost of re-implementing GI to investigate new approaches is hindering progress. Therefore, we present Gin, an extensible and modifiable toolbox for GI experimentation, with a novel combination of features. Instantiated in Java and targeting the Java ecosystem, Gin automatically transforms, builds, and tests Java projects. Out of the box, Gin supports automated test-generation and source code profiling. We show, through examples and a case study, how Gin facilitates experimentation and will speed innovation in GI.

Employee scheduling problems are of critical importance to large businesses. These problems are hard to solve due to large numbers of conflicting constraints. While many approaches address a subset of these constraints, there is no single approach for simultaneously addressing all of them. We hybridise 'Evolutionary Ruin & Stochastic Recreate' and 'Variable Neighbourhood Search' metaheuristics to solve a real world instance of the employee scheduling problem to near optimality. We compare this with Simulated Annealing, exploring the algorithm configuration space using the irace software package to ensure fair comparison. The hybrid algorithm generates schedules that reduce unmet demand by over 28% compared to the baseline. All data used, where possible, is either directly from the real world engineer scheduling operation of around 25,000 employees, or synthesised from a related distribution where data is unavailable.

With increasing demand for air travel and overloaded airport facilities, inefficient airport taxiing operations are a significant contributor to unnecessary fuel burn and a substantial source of pollution. Although taxiing is only a small part of a flight, aircraft engines are not optimised for taxiing speed and so contribute disproportionately to the overall fuel burn. Delays in taxiing also waste scarce airport resources and frustrate passengers. Consequently, reducing the time spent taxiing is an important investment. An exact algorithm for finding shortest paths based on A* allocates routes to aircraft that maintains aircraft at a safe distance apart, has been shown to yield efficient taxi routes. However, this approach depends on the order in which aircraft are chosen for allocating routes. Finding the right order in which to allocate routes to the aircraft is a combinatorial optimization problem in itself.

Metaheuristics assume some kind of coherence between decision and objective spaces. Estimation of Distribution algorithms approach this by constructing an explicit probabilistic model of high fitness solutions, the structure of which is intended to reflect the structure of the problem. In this context, “structure” means the dependencies or interactions between problem variables in a probabilistic graphical model. There are many approaches to discovering these dependencies, and existing work has already shown that often these approaches discover “unnecessary” elements of structure - that is, elements which are not needed to correctly rank solutions. This work performs an exhaustive analysis of all 2 and 3 bit problems, grouped into classes based on mononotic invariance. It is shown in [1] that each class has a minimal Walsh structure that can be used to solve the problem. We compare the structure discovered by different structure learning approaches to the minimal Walsh structure for each class, with summaries of which interactions are (in)correctly identified. Our analysis reveals a large number of symmetries that may be used to simplify problem solving. We show that negative selection can result in improved coherence between discovered and necessary structure, and conclude with some directions for a general programme of study building on this work.

Fitness modeling has received growing interest from the evolutionary computation community in recent years. With a fitness model, one can improve evolutionary algorithm efficiency by directly sampling new solutions, developing hybrid guided evolutionary operators or using the model as a surrogate for an expensive fitness function. This paper addresses several issues on fitness modeling of discrete functions, particularly how modeling quality and efficiency can be improved. We define the Markov network fitness model in terms of Walsh functions. We explore the relationship between the Markov network fitness model and fitness in a number of discrete problems, showing how the parameters of the fitness model can identify qualitative features of the fitness function. We define the fitness prediction correlation, a metric to measure fitness modeling capability of local and global fitness models. We use this metric to investigate the effects of population size and selection on the tradeoff between model quality and complexity for the Markov network fitness model.

Learning a good model structure is important to the efficient solving of problems by estimation of distribution algorithms. In this paper we present the results of a series of experiments, applying a structure learning algorithm for undirected probabilistic graphical models based on statistical dependency tests to three fitness functions with different selection operators, proportions and pressures. The number of spurious interactions found by the algorithm are measured and reported. Truncation selection, and its complement (selecting only low fitness solutions) prove quite robust, resulting in a similar number of spurious dependencies regardless of selection pressure. In contrast, tournament and fitness proportionate selection are strongly affected by the selection proportion and pressure.

Surrogate models of fitness have been presented as a way of reducing the number of fitness evaluations required by an evolutionary algorithm. This is of particular interest with expensive fitness functions where the cost of building the model is outweighed by the saving of using fewer function evaluations. In this paper we show how a Markov network model can be used as a surrogate fitness function in a genetic algorithm. We demonstrate this applied to a number of well-known benchmark functions and although the results are good in terms of function evaluations the model-building overhead requires a substantially more expensive fitness function to be worthwhile. We move on to describe a fitness function for feature selection in Case-Based Reasoning, which is considerably more expensive than the other benchmark functions we used. We show that for this problem using the surrogate offers a significant decrease in total run time compared to a GA using the true fitness function.

Structure learning is a crucial component of a multivariate Estimation of Distribution algorithm. It is the part which determines the interactions between variables in the probabilistic model, based on analysis of the fitness function or a population. In this paper we take three different approaches to structure learning in an EDA based on Markov networks and use measures from the information retrieval community (precision, recall and the F-measure) to assess the quality of the structures learned. We then observe the impact that structure has on the fitness modelling and optimisation capabilities of the resulting model, concluding that these results should be relevant to research in both structure learning and fitness modelling.

Distribution Estimation Using Markov network (DEUM) algorithm is a class of estimation of distribution algorithms that uses Markov networks to model and sample the distribution. Several different versions of this algorithm have been proposed and are shown to work well in a number of different optimisation problems. One of the key similarities between all of the DEUM algorithms proposed so far is that they all assume the interaction between variables in the problem to be pre given. In other words, they do not learn the structure of the problem and assume that it is known in advance. Therefore, they may not be classified as full estimation of distribution algorithms. This work presents a fully multivariate DEUM algorithm that can automatically learn the undirected structure of the problem, automatically find the cliques from the structure and automatically estimate a joint probability model of the Markov network. This model is then sampled using Monte Carlo samplers. The proposed DEUM algorithm can be applied to any general optimisation problem even when the structure is not known.

Selection is one of the defining characteristics of an evolutionary algorithm, yet inherent in the selection process is the loss of some information from a population. Poor solutions may provide information about how to bias the search toward good solutions. Many Estimation of Distribution Algorithms (EDAs) use truncation selection which discards all solutions below a certain fitness, thus losing this information. Our previous work on Distribution Estimation using Markov networks (DEUM) has described an EDA which constructs a model of the fitness function; a unique feature of this approach is that because selective pressure is built into the model itself selection becomes optional. This paper outlines a series of experiments which make use of this property to examine the effects of selection on the population. We look at the impact of selecting only highly fit solutions, only poor solutions, selecting a mixture of highly fit and poor solutions, and abandoning selection altogether. We show that in some circumstances, particularly where some information about the problem is already known, selection of the fittest only is suboptimal.

In this paper we present an application of an Estimation of Distribution Algorithm (EDA) that uses a Markov network probabilistic model. The application is to the problem of bio-control in mushroom farming, a domain which admits bang-bang-control solutions. The problem is multi-objective and uses a weighted fitness function. Previous work on this problem has applied genetic algorithms (GA) with directed intervention crossover schemes aimed at effective biocontrol at an efficient level of intervention. Here we compare these approaches with the EDA Distribution Estimation Using Markov networks (DEUMd). DEUMdconstructs a probabilistic model using Markov networks. Our experiments compare the quality of solutions produced by DEUMd with the GA approaches and also reveal interesting differences in the search dynamics that have implications for algorithm design.

Chemotherapy treatment for cancer is a complex optimisation problem with a large number of interacting variables and constraints. A number of different heuristics have been applied to it with varying success. In this paper we expand on this by applying two estimation of distribution algorithms to the problem. One is UMDA and the other is hBOA, the first EDA using a multivariate probabilistic model to be applied to the chemotherapy problem. While instinct would lead us to predict that the more sophisticated algorithm would yield better performance on a complex problem like this, we show that it is outperformed by the algorithms using the simpler univariate model. We hypothesise that this is caused by the more sophisticated algorithm being impeded by the large number of interactions in the problem which though present, do not complicate the search for optima.

We explore the application of an Estimation of Distribution Algorithm which uses a Markov Network to the problem of bio-control in mushroom farming. This falls into the category of .bang-bang control. problems and was previously used as an application for genetic algorithms with modified crossover operators. The EDA yields a small improvement in the solutions that are evolved. Moreover, the probabilistic models constructed closely match identifiable features in the underlying dynamics of the problem. We conclude that this is a useful by-product of the probabilistic modelling which can be further exploited.

This paper presents a practical methodology of improving the efficiency of genetic algorithms through tuning the factors significantly affecting GA performance. This methodology is based on the methods of statistical inference and has been successfully applied to both binary-and integer-encoded genetic algorithms that search for good chemotherapeutic schedules