Academic research in dynamic optimisation uses benchmark generators to artificially simulate controlled and reproducible changing-environments to systematically compare algorithmic performance under uncertainty. However, due to the scarcity or difficulty in acquiring real-world data, benchmarks often fail to incorporate real-world features, such as problem constraints or the time-linkage property, where previously made decisions influence future events. This study introduces a Gaussian Copula-based real-world data-driven synthetic data generation model for Dynamic Truck and Trailer Scheduling Problem (DTTSP). The model offers a realistic, privacy-preserving DTTSP benchmark instance generator, which can be used to recreate the dynamism, constraints, heterogeneity, and time-linkage of logistics and supply chain operations. This work examines the utility, fidelity, and privacy of the suggested model in four workday case studies from a local transportation company. The conducted experiments demonstrate the systematical application of Gaussian Copulas to produce accurate, useful, and secure DTTSP benchmark instances that capture the statistical properties and correlation of variables, as well as the temporal patterns, in the original annual data. Nevertheless, the utility analysis of the conditional sampling indicates that there is still room for improvement in the modelling process.

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 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.

While population-based metaheuristics have proven useful for refining and improving explainable AI systems, they are seldom the focus of explanatory approaches themselves. This stems from their inherently stochastic, population-driven searches, which complicate the use of standard explainability techniques. In this article, we present a method to identify which decision variables have the greatest impact during an algorithm’s trajectory from random initialsation to convergence. We apply Principal Component Analysis to project each population onto a lower-dimensional space, then introduce two metrics—Mean Variable Contribution and Proportion of Aligned Variables—to identify the variables most responsible for guiding the search. Using four different population-based methods (Particle Swarm Optimisation, Genetic Algorithm, Differential Evolution, and Covariance Matrix Adaptation Evolution Strategy) on 24 BBOB benchmark functions in 10 dimensions, we find that these metrics highlight meaningful variable relationships and provide a window into each method’s search dynamics. By comparing the features extracted across algorithms and problems, we illustrate how certain variable subsets consistently drive major improvements in solution quality. In doing so, new evolutionary algorithm variants can be designed to take advantage of these influential variables, while also identifying underutilised variables that may benefit alternative search strategies.

Deep neural networks (DNN) has achieved great successes across multiple domains. In recent years, a number of approaches have emerged on automatically finding the optimal DNN configurations. A technique among these approaches which show great promise is Evolutionary Algorithms (EA), which are based on observations from natural, biological processes. However, since the EA needs to evaluate multiple DNN candidates, and if the training time for a DNN is large, then the required time would be very large. A potential solution is to use Surrogate Assisted Evolutionary Algorithm (SAEA), in which a surrogate model is used to predict performance of DNNs without training. It is noted that all popular surrogate models in the literature require a fixed-length input, while encodings of a DNN are usually variable-length, since a DNN structure is very complex and its depths, sizes, etc. cannot be known beforehand. In this paper, we propose a novel surrogate model for variable-length encoding to optimise deep learning architecture. An encoder-decoder model is used to convert the variable-length encoding into a fixed-length representation, which is used as inputs to the surrogate model to predict the DNN performance without training. The weights of the encoder-decoder model are found via training on the variable-length data, with the targets being the same as the inputs, while the surrogate model is trained on the encoder output in the encoder-decoder model. In this study, a Long Short-Term Memory (LSTM) model is used as the encoder and decoder. Our proposed variable-length encoding based surrogate model is tested on a well-known method which evolves optimal Convolutional Neural Networks (CNNs). The experimental results show that our proposed method has competitive performance while significantly reducing the time of optimisation process.

Modern supply chains are complex structures of interacting units exchanging goods and services. Business decisions made by individual units in the supply chain have knock-on effects on decisions made by successor units in the chain. Linked Optimisation Problems are an abstraction of real-world supply chains and are defined as a directed network where each node is a formally defined optimisation problem, and each link indicates dependencies. The development of approaches to holistically solve linked optimisation problems is of high significance to decarbonisation as well as building robust industrial supply chains resilient to economic shock and climate change. This paper develops a novel linked problem benchmark (IWSP-VAP-MTSP) integrating Inventory Warehouse Selection Problem, Vehicle Assignment Problem and Multiple Traveling Salesmen Problem. The linked problem represents tactical and operational supply chain decision problems that arise in inventory location and routing. We consider three algorithmic approaches, Sequential, Nondominated Sorting Genetic Algorithm for Linked Problem (NSGALP) and Multi-Criteria Ranking Genetic Algorithm for Linked Problem (MCRGALP). We generated 960 randomised instances of IWSP-VAP-MTSP and statistically compared the performance of the proposed holistic approaches. Results show that MCRGALP outperforms the other two approaches based on the performance metrics used, however, at the expense of greater computational time.

• A multi-layer ensemble connects each classifier to multiple ones in prior layer. • Connections signify the use of previous-layer-classifiers’ outputs as new inputs. • A binary encoding scheme is proposed to encode the topology of proposed ensemble. • The optimal topology of proposed ensemble is found by using Differential Evolution. • Our ensemble performs better than benchmark algorithms on experimental datasets. Ensemble learning is a powerful machine learning strategy that combines multiple models e.g. classifiers to improve predictions beyond what any single model can achieve. Until recently, traditional ensemble methods typically use only one layer of models which limits the exploration of different aspects in the classifiers’ predictions. On the other hand, the rise of deep learning has introduced multi-layer architectures that can learn complex functions by transforming data into multiple levels of representation. This characteristic of deep learning suggests that multi-layer ensembles may potentially provide better performance compared to single-layer ensembles. However, a problem which might arise is that in the subsequent layers, not all the inputs to a classifier are desirable, leading to lower performance. In this paper, we introduce a novel multi-layer ensemble of classifiers named COME in which each classifier at a specific layer is connected to multiple classifiers in the previous layer. These connections signify the use of the previous-layer-classifiers’ outputs as inputs for training the current layer's classifier. Each classifier can be connected to different classifiers in the previous layer, which allows inputs in each layer to be optimally selected. We propose a binary encoding scheme to encode the topology of the proposed multi-layer ensemble with defined connections between layers. Differential Evolution, a popular evolutionary computation method, is used as the optimisation algorithm to search for the optimal set of connections. Experimental results on 30 datasets from the UCI Machine Learning Repository and OpenML demonstrate that our proposed ensemble outperforms many state-of-the-art ensemble learning algorithms.

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.

The past five years have seen rapid development of plans and test pilots aimed at introducing connected and autonomous vehicles (CAVs) in public transport systems around the world. While self-driving technology is still being perfected, public transport authorities are increasingly interested in the ability to model and optimize the benefits of adding CAVs to existing multi-modal transport systems. Using a real-world scenario from the Leeds Metropolitan Area as a case study, we demonstrate an effective way of combining macro-level mobility simulations based on open data with global optimisation techniques to discover realistic optimal deployment strategies for CAVs. The macro-level mobility simulations are used to assess the quality of a potential multi-route CAV service by quantifying geographic accessibility improvements using an extended version of Dijkstra’s algorithm on an abstract multi-modal transport network. The optimisations were carried out using several popular population-based optimisation algorithms that were combined with several routing strategies aimed at constructing the best routes by ordering stops in a realistic sequence.

With the significant breakthrough of Deep Neural Networks in recent years, multi-layer architecture has influenced other sub-fields of machine learning including ensemble learning. In 2017, Zhou and Feng introduced a deep random forest called gcForest that involves several layers of Random Forest-based classifiers. Although gcForest has outperformed several benchmark algorithms on specific datasets in terms of classification accuracy and model complexity, its input features do not ensure better performance when going deeply through layer-by-layer architecture. We address this limitation by introducing a deep ensemble model with a novel feature generation module. Unlike gcForest where the original features are concatenated to the outputs of classifiers to generate the input features for the subsequent layer, we integrate weights on the classifiers’ outputs as augmented features to grow the deep model. The usage of weights in the feature generation process can adjust the input data of each layer, leading the better results for the deep model. We encode the weights using variable-length encoding and develop a variable-length Particle Swarm Optimization method to search for the optimal values of the weights by maximizing the classification accuracy on the validation data. Experiments on a number of UCI datasets confirm the benefit of the proposed method compared to some well-known benchmark algorithms.

Deep Neural Networks (DNNs) have created a breakthrough in medical image analysis in recent years. Because clinical applications of automated medical analysis are required to be reliable, robust and accurate, it is necessary to devise effective DNNs based models for medical applications. In this paper, we propose an ensemble framework of DNNs for the problem of medical image segmentation with a note that combining multiple models can obtain better results compared to each constituent one. We introduce an effective combining strategy for individual segmentation models based on swarm intelligence, which is a family of optimization algorithms inspired by biological processes. The problem of expensive computational time of the optimizer during the objective function evaluation is relieved by using a surrogate-based method. We train a surrogate on the objective function information of some populations and then use it to predict the objective values of each candidate in the subsequent populations. Experiments run on a number of public datasets indicate that our framework achieves competitive results within reasonable computation time.

In recent years, deep learning has rapidly become a method of choice for segmentation of medical images. Deep neural architectures such as UNet and FPN have achieved high performances on many medical datasets. However, medical image analysis algorithms are required to be reliable, robust, and accurate for clinical applications which can be difficult to achieve for some single deep learning methods. In this study, we introduce an ensemble of classifiers for semantic segmentation of medical images. The ensemble of classifiers here is a set of various deep learning-based classifiers, aiming to achieve better performance than using a single classifier. We propose a weighted ensemble method in which the weighted sum of segmentation outputs by classifiers is used to choose the final segmentation decision. We use a swarm intelligence algorithm namely Comprehensive Learning Particle Swarm Optimization to optimize the combining weights. Dice coefficient, a popular performance metric for image segmentation, is used as the fitness criteria. Experiments conducted on some medical datasets of the CAMUS competition on cardiographic image segmentation show that our method achieves better results than both the constituent segmentation models and the reported model of the CAMUS competition.

In this paper, we demonstrate the application of features from landscape analysis, initially proposed for multi-objective combinatorial optimisation, to a benchmark set of 1 200 randomly-generated multiobjective interpolated continuous optimisation problems (MO-ICOPs). We also explore the benefits of evaluating the considered landscape features on the basis of a fixed-size sampling of the search space. This allows fine control over cost when aiming for an efficient application of feature-based automated performance prediction and algorithm selection. While previous work shows that the parameters used to generate MO-ICOPs are able to discriminate the convergence behaviour of four state-of-the-art multi-objective evolutionary algorithms, our experiments reveal that the proposed (black-box) landscape features used as predictors deliver a similar accuracy when combined with a classification model. In addition, we analyse the relative importance of each feature for performance prediction and algorithm selection.

In previous work, we proposed and studied a new dynamic formulation of the Location-allocation (LA) problem called the Dynamic-Customer Location-allocation (DC-LA) problem. DC-LA is based on the idea of changes in customer distribution over a defined period, and these changes have to be taken into account when establishing facilities to service changing customers distributions. This necessitated a dynamic stochastic evaluation function Which came with a high computational cost due to a large number of simulations required in the evaluation process.In this paper, we investigate the use of racing, an approach used in model selection, to reduce the high computational cost by employing the minimum number of simulations for solution selection. Our adaptation of racing uses the Friedman test to compare solutions statistically. Racing allows simulations to be performed iteratively, ensuring that the minimum number of simulations is performed to detect a statistical difference.We present experiments using Population-Based Incremental Learning (PBIL) to explore the savings achievable from using racing in this way. Our results show that racing achieves improved cost savings over the dynamic stochastic evaluation function. We also observed that on average, the computational cost of racing was about 4.5 times loWer than the computational cost of the full dynamic stochastic evaluation.

Text classification is one of the most important tasks in the field of Natural Language Processing. There are many approaches that focus on two main aspects: generating an effective representation; and selecting and refining algorithms to build the classification model. Traditional machine learning methods represent documents in vector space using features such as term frequencies, which have limitations in handling the order and semantics of words. Meanwhile, although achieving many successes, deep learning classifiers require substantial resources in terms of labelled data and computational complexity. In this work, a weighted ensemble of classifiers (WEC) is introduced to address the text classification problem. Instead of using majority vote as the combining method, we propose to associate each classifier's prediction with a different weight when combining classifiers. The optimal weights are obtained by minimising a loss function on the training data with the Particle Swarm Optimisation algorithm. We conducted experiments on 5 popular datasets and report classification performance of algorithms with classification accuracy and macro F1 score. WEC was run with several different combinations of traditional machine learning and deep learning classifiers to show its flexibility and robustness. Experimental results confirm the advantage of WEC, especially on smaller datasets.

Deep Neural Networks have achieved many successes when applying to visual, text, and speech information in various domains. The crucial reasons behind these successes are the multi-layer architecture and the in-model feature transformation of deep learning models. These design principles have inspired other sub-fields of machine learning including ensemble learning. In recent years, there are some deep homogenous ensemble models introduced with a large number of classifiers in each layer. These models, thus, require a costly computational classification. Moreover, the existing deep ensemble models use all classifiers including unnecessary ones which can reduce the predictive accuracy of the ensemble. In this study, we propose a multi-layer ensemble learning framework called MUlti-Layer heterogeneous Ensemble System (MULES) to solve the classification problem. The proposed system works with a small number of heterogeneous classifiers to obtain ensemble diversity, therefore being efficiency in resource usage. We also propose an Evolutionary Algorithm-based selection method to select the subset of suitable classifiers and features at each layer to enhance the predictive performance of MULES. The selection method uses NSGA-II algorithm to optimize two objectives concerning classification accuracy and ensemble diversity. Experiments on 33 datasets confirm that MULES is better than a number of well-known benchmark algorithms.

In this paper, we introduce a new stochastic Location-Allocation Problem which assumes the movement of customers over time. We call this new problem Dynamic Customer Location-Allocation Problem (DC-LAP). The problem is based on the idea that customers will change locations over a defined horizon and these changes have to be taken into account when establishing facilities to service customers demands. We generate 1440 problem instances by varying the problem parameters of movement rate which determines the possible number of times a customer will change locations over the defined period, the number of facilities and the number of customers. We propose to analyse the characteristics of the instances generated by testing a search algorithm using the stochastic dynamic evaluation (based on the replication of customer movement scenarios) and a deterministic static evaluation (based on the assumption that customer will not move over time). We show that the dynamic approach obtains globally better results, but the performances are highly related to the parameters of the problem. Moreover, the dynamic approach involves a significantly high computational overhead.

In ensemble systems, the predictions of base classifiers are aggregated by a combining algorithm (meta-classifier) to achieve better classification accuracy than using a single classifier. Experiments show that the performance of ensembles significantly depends on the choice of meta-classifier. Normally, the classifier selection method applied to an ensemble usually removes all the predictions of a classifier if this classifier is not selected in the final ensemble. Here we present an idea to only remove a subset of each classifier's prediction thereby introducing a simultaneous meta-data and meta-classifier selection method for ensemble systems. Our approach uses Cross Validation on the training set to generate meta-data as the predictions of base classifiers. We then use Ant Colony Optimization to search for the optimal subset of meta-data and meta-classifier for the data. By considering each column of meta-data, we construct the configuration including a subset of these columns and a meta-classifier. Specifically, the columns are selected according to their corresponding pheromones, and the meta-classifier is chosen at random. The classification accuracy of each configuration is computed based on Cross Validation on meta-data. Experiments on UCI datasets show the advantage of proposed method compared to several classifier and feature selection methods for ensemble systems.

With the advancement of storage and processing technology, an enormous amount of data is collected on a daily basis in many applications. Nowadays, advanced data analytics have been used to mine the collected data for useful information and make predictions, contributing to the competitive advantages of companies. The increasing data volume, however, has posed many problems to classical batch learning systems, such as the need to retrain the model completely with the newly arrived samples or the impracticality of storing and accessing a large volume of data. This has prompted interest on incremental learning that operates on data streams. In this study, we develop an incremental online multi-label classification (OMLC) method based on a weighted clustering model. The model is made to adapt to the change of data via the decay mechanism in which each sample's weight dwindles away over time. The clustering model therefore always focuses more on newly arrived samples. In the classification process, only clusters whose weights are greater than a threshold (called mature clusters) are employed to assign labels for the samples. In our method, not only is the clustering model incrementally maintained with the revealed ground truth labels of the arrived samples, the number of predicted labels in a sample are also adjusted based on the Hoeffding inequality and the label cardinality. The experimental results show that our method is competitive compared to several well-known benchmark algorithms on six performance measures in both the stationary and the concept drift settings.

The service chain planning process is a critical component in the operations of companies in the service industry, such as logistics, telecoms or utilities. This process involves looking ahead over various timescales to ensure that available capacity matches the required demand whilst maximizing revenues and minimizing costs. This problem is particularly complex for companies with large, multi-skilled workforces as matching these resources to the required demand can be done in a vast number of combinations. The vastness of the problem space combined with the criticality to the business is leading to an increasing move towards automation of the process in recent years. In this paper we focus on the tactical plan where planning is occurring daily for the coming weeks, matching the available capacity to demand, using capacity levers to flex capacity to keep backlogs within target levels whilst maintaining target levels for provision of new revenues. First we describe the tactical planning problem before defining a bi-level model to search for optimal solutions to it. We show, by comparing the model results to actual planners on real world examples, that the bi-level model produces good results that replicate the planners' process whilst keeping the backlogs closer to target levels, thus providing a strong case for its use in the automation of the tactical planning process.

The Uncapacitated Location-Allocation problem (ULAP) is a major optimisation problem concerning the determination of the optimal location of facilities and the allocation of demand to them. In this paper, we present two novel problem variants of Non-Linear ULAP motivated by a real-world problem from the telecommunication industry: Uncapacitated Location-Allocation Resilience problem (ULARP) and Uncapacitated Location-Allocation Resilience problem with Restrictions (ULARPR). Problem sizes ranging from 16 to 100 facilities by 50 to 10000 demand points are considered. To solve the problems, we explore the components and configurations of four Genetic Algorithms [1]-[3] and [4] selected from the ULAP literature. We aim to understand the contribution each choice makes to the GA performance and so hope to design an Optimal GA configuration for the novel problems. We also conduct comparative experiments with Population-Based Incremental Learning (PBIL) Algorithm on ULAP. We show the effectiveness of PBIL and GA with parameter set: random and heuristic initialisation, tournament and fined_grained tournament selection, uniform crossover and bitflip mutation in solving the proposed problems.

The purpose of this paper is two fold. First, we present a set of benchmark problems for maintenance optimisation called VMELight. This model allows the user to define the number of components in the system to maintain and a number of customisable parameters such as the failure distribution of the components, the spare part stock level and every costs associated with the preventive and corrective maintenances, unavailability and spare parts. From this model, we create a benchmark of 175 optimisation problems across different dimensions. This benchmark allows us to test the idea of using an iterated racing algorithm called IRACE based on the Friedman statistical test, to reduce the number of simulations needed to compare solutions in the population. We assess different population size and truncation rate to show that those parameters can have a strong influence on the performance of the algorithm.

By incorporating domain knowledge, simple greedy procedures can be defined to generate reasonably good solutions to many optimisation problems. However, such solutions are unlikely to be optimal and their quality often depends on the way the decision variables are input to the greedy method. Indirect optimisation uses meta-heuristics to optimise the input of the greedy decoders. As the performance and the runtime differ across greedy methods and meta-heuristics, deciding how to split the computational effort between the two sides of the optimisation is not trivial and can significantly impact the search. In this paper, an artificial scheduling problem is presented along with five greedy procedures, using varying levels of domain information. A methodology to compare different indirect optimisation strategies is presented using a simple Hill Climber, a Genetic Algorithm and a population-based Local Search. By assessing all combinations of meta-heuristics and greedy procedures on a range of problem instances with different properties, experiments show that encapsulating problem knowledge within greedy decoders may not always prove successful and that simpler methods can lead to comparable results as advanced ones when combined with meta-heuristics that are adapted to the problem. However, the use of efficient greedy procedures reduces the relative difference between meta-heuristics.

Multi-Mode Resource Constrained Project Problem (MRCPSP) is a multi-component problem which combines two interacting sub-problems; activity scheduling and mode assignment. Multi-component problems have been of research interest to the evolutionary computation community as they are more complex to solve. Estimation of Distribution Algorithms (EDAs) generate solutions by sampling a probabilistic model that captures key features of good solutions. Often they can significantly improve search efficiency and solution quality. Previous research has shown that the mode assignment subproblem can be more effectively solved with an EDA. Also, a competitive Random Key based EDA (RK-EDA) for permutation problems has recently been proposed. In this paper, activity and mode solutions are respectively generated using the RK-EDA and an integer based EDA. This approach is competitive with leading approaches of solving the MRCPSP.

Random Key (RK) is an alternative representation for permutation problems that enables application of techniques generally used for continuous optimisation. Although the benefit of RKs to permutation optimisation has been shown, its use within Estimation of Distribution Algorithms (EDAs) has been a challenge. Recent research proposing a RK-based EDA (RK-EDA) has shown that RKs can produce competitive results with state of the art algorithms. Following promising results on the Permutation Flowshop Scheduling Problem, this paper presents an analysis of RK-EDA for optimising the total flow time. Experiments show that RK-EDA outperforms other permutation-based EDAs on instances of large dimensions. The difference in performance between RK-EDA and the state of the art algorithms also decreases when the problem difficulty increases.

The Multi-mode Resource Constrained Project Scheduling Problem (MRCPSP) has been of research interest for over two decades. The problem is composed of two interacting sub problems: mode assignment and activity scheduling. These problems cannot be solved in isolation because of the interaction that exists between them. Many evolutionary algorithms have been applied to this problem most commonly the Genetic Algorithm (GA). It has been common practice to improve the performance of the GA with some local search techniques. The Bi-population Genetic Algorithm (BPGA) is one of the most competitive GAs for solving the MRCPSP. In this paper, we improve the BPGA by hybridising it with an Estimation of Distribution Algorithm that focuses on improving how modes are generated. We also suggest improvement to the existing experimental methodology.

Critical for successful operations of service industries, such as telecoms, utility companies and logistic companies, is the service chain planning process. This involves optimizing resources against expected demand to maximize the utilization and minimize the wastage, which in turn maximizes revenue whilst minimizing the cost. This is increasingly involving the automation of the planning process. However, due to unforeseen factors, the calculated optimal allocation of resources to complete tasks often does not match up with what is actually occurring on the day. This factor highlights a requirement for a method of predicting accurately the number of tasks that will be completed given a known amount of resources and demand in order to produce a more accurate plan.

The need to assess internet performance from the user's perspective grows, as does the interest in deployment of Large-Scale Measurement Platforms (LMAPs). The potential of these platforms as a real-time network diagnostic tool is limited by the volume, velocity and variety of the data they generated. Fusing this data from multiple sources and generating a single piece of coherent information about the state of the network would increase the efficiency of network monitoring. The current practice of visually analysing LMAPs' data stream would certainly benefit from having automatically generated notifications in a timely manner alerting human controllers to the network's conditions of interest. This paper proposed a data fusion framework for LMAPs that makes use of mathematical distribution based sensors to generate probabilistic sensor outputs which are fused using a Dempster-Shafer Theory.

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.

Structural learning of Bayesian networks is a very expensive task even when sacrifying the optimality of the result. Because of that, there are some proposals aimed at obtaining relative-quality solutions in short times. One of them, namely Chain-ACO, searches an ordering among all variables with Ant Colony Optimization and a chain-structured surrogate model, and then uses this ordering to build a Bayesian network by means of the well-known K2 algorithm.

Problem structure, or linkage, refers to the interaction between variables in a black-box fitness function. Discovering structure is a feature of a range of algorithms, including estimation of distribution algorithms (EDAs) and perturbation methods (PMs). The complexity of structure has traditionally been used as a broad measure of problem difficulty, as the computational complexity relates directly to the complexity of structure. The EDA literature describes necessary and unnecessary interactions in terms of the relationship between problem structure and the structure of probabilistic graphical models discovered by the EDA. In this paper we introduce a classification of problems based on monotonicity invariance. We observe that the minimal problem structures for these classes often reveal that significant proportions of detected structures are unnecessary. We perform a complete classification of all functions on 3 bits. We consider nonmonotonicity linkage discovery using perturbation methods and derive a concept of directed ordinal linkage associated to optimization schedules. The resulting refined classification factored out by relabeling, shows a hierarchy of nine directed ordinal linkage classes for all 3-bit functions. We show that this classification allows precise analysis of computational complexity and parallelizability and conclude with a number of suggestions for future work.

This paper improves a recently developed multi-objective particle swarm optimizer (D2MOPSO) that incorporates dominance with decomposition used in the context of multi-objective optimization. Decomposition simplifies a multi-objective problem (MOP) by transforming it to a set of aggregation problems, whereas dominance plays a major role in building the leaders' archive. D2MOPSO introduces a new archiving technique that facilitates attaining better diversity and coverage in both objective and solution spaces. The improved method is evaluated on standard benchmarks including both constrained and unconstrained test problems, by comparing it with three state of the art multi-objective evolutionary algorithms: MOEA/D, OMOPSO, and dMOPSO. The comparison and analysis of the experimental results, supported by statistical tests, indicate that the proposed algorithm is highly competitive, efficient, and applicable to a wide range of multi-objective optimization problems.

The Artificial Reaction Network (ARN) is a cell signaling network inspired representation belonging to the branch of A-Life known as Artificial Chemistry. It has properties in common with both AI and Systems Biology techniques including Artificial Neural Networks, Petri Nets, Random Boolean Networks and S-Systems. The ARN has been previously applied to control of limbed robots and simulation of biological signaling pathways. In this paper, multiple instances of independent distributed ARN controlled agents function to find the global minima within a set of simulated environments characterized by benchmark problems. The search behavior results from the internal ARN network, but is enhanced by collective activities and stigmergic interaction of the agents. The results show that the agents are able to find best fitness solutions in all problems, and compare well with results of cell inspired optimization algorithms. Such a system may have practical application in distributed or swarm robotics.

The single core processor, which has dominated for over 30 years, is now obsolete with recent trends increasing towards parallel systems, demanding a huge shift in programming techniques and practices. Moreover, we are rapidly moving towards an age where almost all programming will be targeting parallel systems. Parallel hardware is rapidly evolving, with large heterogeneous systems, typically comprising a mixture of CPUs and GPUs, becoming the mainstream. Additionally, with this increasing heterogeneity comes increasing complexity: not only does the programmer have to worry about where and how to express the parallelism, they must also express an efficient mapping of resources to the available system. This generally requires in-depth expert knowledge that most application programmers do not have. In this paper we describe a new technique that derives, automatically, optimal mappings for an application onto a heterogeneous architecture, using a Monte Carlo Tree Search algorithm. Our technique exploits high-level design patterns, targeting a set of well-specified parallel skeletons. We demonstrate that our MCTS on a convolution example obtained speedups that are within 5% of the speedups achieved by a hand-tuned version of the same application.

There exist several operators to search through permutation spaces that can benefit search and score algorithms when combined. This paper presents COMpetitive Mutating Agents (COMMA), an algorithm which uses geometric mutation operators to create a geometrically defined distribution of solutions. Sampling from the distribution generates solutions in a similar fashion as with Estimation of Distribution Algorithms (EDAs). COMMA is applied on classical permutation optimization benchmarks, namely the Quadratic Assignement and the Permutation Flowshop Scheduling Problems and its performance is compared with those of reference EDAs. Although COMMA does not require a model building step, results suggest that it is competitive with state-of-the-art EDAs. In addition, COMMA's underlying geometric-based sampling could be transposed to representations other than permutations.

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.

A novel presentation for channel selection problem in Brain-Computer Interfaces (BCI) is introduced here. Continuous presentation in a projected two-dimensional space of the Electroencephalograph (EEG) cap is proposed. A multi-objective particle swarm optimization method (D2MOPSO) is employed where particles move in the EEG cap space to locate the optimum set of solutions that minimize the number of selected channels and the classification error rate. This representation focuses on the local relationships among EEG channels as the physical location of the channels is explicitly represented in the search space avoiding picking up channels that are known to be uncorrelated with the mental task. In addition continuous presentation is a more natural way for problem solving in PSO framework. The method is validated on 10 subjects performing right-vs-left motor imagery BCI. The results are compared to these obtained using Sequential Floating Forward Search (SFFS) and shows significant enhancement in classification accuracy but most importantly in the distribution of the selected channels.

Bayesian Networks (BNs) are graphical probabilistic models that represent relationships that may exist between variables of a dataset. BN can be applied to data in a variety of different ways. Yet, using a BN requires knowing its structure. BN structure learning represents a challenge as the number of possible structures is very large. Search and score approaches have been used to address the problem. One of them, a Genetic Algorithm based on the K2 search (K2GA) has shown that BNs can be learned from many datasets. However, the computational cost which is involved is high while structures obtained from benchmark data often exhibit significant differences from known correct structures. In this paper, we investigate the use of K2GA within an Island Model (IM) implementation and compare the quality of the BN structures obtained with those of the traditional K2GA. Experiments are run on five datasets created from BNs with known structures. Results show that the use of IM improves the quality of the structures obtained. BNs present better fitnesses, but also sets of edges more consistent with the known true structures. We conclude that migration between islands helps maintaining diversity within each population.

Bayesian network (BN) structure learning is an NP hard problem. Search and score algorithms are one of the main approaches proposed for learning BN structure from data. Previous research has shown that the relative performances of such algorithms are problem dependent and that fitness landscape analysis can be used to characterize the difficulty of the search for different scoring functions. In this paper, we construct a classifier based on fitness landscape analysis and receiver operating characteristic curves. The classifier labels search landscapes with the most suitable scoring function. We train the classifier on a number of standard benchmark functions. The classifier forms the basis for a selective hyperheuristic algorithm. This uses an initial landscape analysis stage to select a scoring function using the classifier. The hyperheuristic algorithm is tested on a distribution of unseen problems based on mutations of the standard benchmarks. Our results establish that the hyperheuristic performs better than a uniformly random scoring function selection approach that omit the landscape analysis stage. Therefore the effects on performance of problem-dependency can be significantly reduced.

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.

Algorithms for learning the structure of Bayesian Networks (BN) from data are the focus of intense research interest. Search-and-score algorithms using nature-inspired metaheuristics are an important strand of this research; however performance is variable and strongly problem-dependent. In this paper we use fitness landscape analysis to explain empirically observed performance differences between particular search and-score algorithms on two well-studied benchmark problems. We investigate the average landscape discovered by random walks around optimal points in the space of BN node orderings. Differences in algorithm performance are explained in terms of these landscapes, which in turn are related to properties of the BN structures. These initial findings suggest that fitness landscape analysis is a promising approach for explaining existing empirical performance comparisons with further potential for understanding the relative difficulty of benchmark problems and the robustness of particular algorithms.

Cancer treatment by chemotherapy involves multiple applications of toxic drugs over a period of time. Optimising the schedule of these treatments can improve the outcome for the patient. A schedule of treatment and its effect on the tumour can be simulated by a mathematical growth model. However, when used in conjunction with a black-box optimisation algorithm such as an Evolutionary Algorithm (EA) to search for effective treatment schedules, the frequent use of the model can become computationally onerous. One approach to improve the efficiency of EAs is to use `fitness inheritance', in which, for a proportion of candidate solutions, simple means are used to estimate the fitness, rather than use the computationally intensive model. We investigate two versions of fitness inheritance for the chemotherapy schedule optimisation problem, and demonstrate the significant improvement in efficiency that can be achieved. In particular, concerning the two main types of fitness inheritance (Averaged and Proportional), we find that the Averaged Inheritance strategy is highly effective in this case, and is strongly recommended for use in further investigations of chemotherapy optimisation using population-based search.

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.

The operation of drilling rigs is highly expensive. It is therefore important to be able to identify and analyse factors affecting rig operations. We investigate the use of two Genetic Algorithms, K2GA and ChainGA, to induce a Bayesian Network model for the real world problem of Rig Operations Management. We sample from a unique dataset derived from the commercial market intelligence databases assembled by ODS-Petrodata Ltd. We observe a trade-off between K2GA, which finds significantly better scoring networks on our dataset, and ChainGA, which uses only one quarter of the computation time. We analyse the best structures produced from an industry standpoint and conclude by outlining a few potential applications of the models to support rig operations.

We present a novel approach to User Interface optimization. A Genetic Algorithm is used to evolve an interface layout to minimize user task times. Solutions are evaluated using the cognitive architecture - Active Control of Thought - Rational (ACT-R) to simulate the human cognition and motor action required to complete the task. A development environment, TOISE, has been created to integrate the GALib toolkit with user task definition and ACT-R. Our approach is tested on a classic design problem - the telephone keypad - in comparison with a Local Search. Solutions produced are also compared to the classic Bell telephone keypad. Our results show that both GA and LS evolve competitive solutions to the problem, with GA significantly outperforming LS. One of the solutions produced by GA approximates the classic Bell keypad. We conclude that the combination of EC and cognitive modeling may offer a competitive and cost effective alternative to interface design approaches driven by human evaluation.

Learning Bayesian networks from data is an NP-hard problem with important practical applications. Several researchers have designed algorithms to overcome the computational complexity of this task. Difficult challenges remain however in reducing computation time for structure learning in networks of medium to large size and in understanding problem-dependent aspects of performance. In this paper, we present two novel algorithms (ChainACO and K2ACO) that use Ant Colony Optimization (ACO). Both algorithms search through the space of orderings of data variables. The ChainACO approach uses chain structures to reduce computational complexity of evaluation but at the expense of ignoring the richer structure that is explored in the K2ACO approach. The novel algorithms presented here are ACO versions of previously published GA approaches. We are therefore able to compare ACO vs GA algorithms and Chain vs K2 evaluations. We present a series of experiments on three well-known benchmark problems. Our results show problem-specific trade-offs between solution quality and computational effort. However it seems that the ACO-based approaches might be favored for larger problems, achieving better fitnesses and success rate than their GA counterparts on the largest network studied in our experiments.

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.

This paper describes two directed intervention crossover approaches that are applied to the problem of deriving optimal cancer chemotherapy treatment schedules. Unlike traditional uniform crossover (UC), both the calculated expanding bin (CalEB) method and targeted intervention with stochastic selection (TInSSel) approaches actively choose an intervention level and spread based on the fitness of the parents selected for crossover. Our results indicate that these approaches lead to significant improvements over UC when applied to cancer chemotherapy scheduling.

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.

This paper discusses the effects of using directed intervention crossover approaches with Genetic Algorithms (GA) and demonstrates their application to scheduling of bio-control agents and cancer chemotherapy treatments. Unlike traditional approaches such as Single Point Crossover (SPC) or Uniform Crossover (UC), the directed intervention techniques actively choose the intervention level based on the fitness of the parents selected for crossover. This work shows that a fitness directed intervention crossover approach leads to significant improvements over SPC and UC when applied to the two different scheduling problems.

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 discusses the effects of mutation and directed intervention crossover approaches when applied to the derivation of cancer chemotherapy treatment schedules. Unlike traditional Uniform Crossover (UC), the directed intervention techniques actively choose the intervention level based on the fitness of the parents selected for crossover. This work describes how directed intervention crossover principles are more robust to mutation and lead to significant improvement over UC when applied to cancer chemotherapy treatment scheduling.

In this paper, we report on work done evolving Bayesian Networks with Genetic Algorithms. We use a Chain Model GA [19] to induce a Bayesian network model for the real world problem of Prostate Cancer management. Bayesian networks can and have been used in a wide range of complex domains, notably in medicine. In fact, they have shown powerful capabilities in representing and dealing with the uncertainties generally inherent in the clinical practice. In this study, we investigate those capabilities by testing the evolved model's predictive power and exploring its potential use as a more versatile alternative to the widely used Partin tables for prostate cancer pathology staging.

Bayesian Networks are today used in various fields and domains due to their inherent ability to deal with uncertainty. Learning Bayesian Networks, however is an NP-Hard task [7]. The super exponential growth of the number of possible networks given the number of factors in the studied problem domain has meant that more often, approximate and heuristic rather than exact methods are used. In this paper, a novel genetic algorithm approach for reducing the complexity of Bayesian network structure discovery is presented. We propose a method that uses chain structures as a model for Bayesian networks that can be constructed from given node orderings. The chain model is used to evolve a small number of orderings which are then injected into a greedy search phase which searches for an optimal structure. We present a series of experiments that show a significant reduction can be made in computational cost although with some penalty in success rate.

Markov random field (MRF) modelling techniques have been recently proposed as a novel approach to probabilistic modelling for estimation of distribution algorithms (EDAs). An EDA using this technique was called distribution estimation using Markov random fields (DEUM). DEUM was later extended to DEUMd. DEUM and DEUMd use a univariate model of probability distribution, and have been shown to perform better than other univariate EDAs for a range of optimization problems. This paper extends DEUM to use a bivariate model and applies it to the Ising spin glass problems. We propose two variants of DEUM that use different sampling techniques. Our experimental result show a noticeable gain in performance.

This paper presents a methodology for using heuristic search methods to optimise cancer chemotherapy. Specifically, two evolutionary algorithms- Population Based Incremental Learning (PBIL), which is an Estimation of Distribution Algorithm (EDA), and Genetic Algorithms (GAs) have been applied to the problem of finding effective chemotherapeutic treatments. To our knowledge, EDAs have been applied to fewer real world problems compared to GAs, and the aim of the present paper is to expand the application domain of this technique. We compare and analyse the performance of both algorithms and draw a conclusion as to which approach to cancer chemotherapy optimisation is more efficient and helpful in the decision-making activity led by the oncologists. Categories and Subject Descriptors

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

Markov random field (MRF) modelling techniques have been recently proposed as a novel approach to probabilistic modelling for estimation of distribution algorithms (EDAs) (S. K. Shakya et al., 2004). An EDA using this technique was called distribution estimation using Markov random fields (DEUM). DEUM was later extended to DEUM/sub d/ (S. Shakya et al., 2005). DEUM and DEUM/sub d/ use a univariate model of probability distribution, and have been shown to perform better than other univariate EDAs for a range of optimization problems. This paper extends DEUM/sub d/ to incorporate a simple Metropolis method and empirically shows that for linear univariate problems the proposed univariate MRF models are very effective. In particular, the proposed DEUM/sub d/ algorithm can find the solution in O(n) fitness evaluations. Furthermore, we suggest that the Metropolis method can also be used to extend the DEUM approach to multivariate problems.

This paper presents an empirical cost-benefit analysis of an algorithm called Distribution Estimation Using MRF with direct sampling (DEUMd). DEUMd belongs to the family of Estimation of Distribution Algorithm (EDA). Particularly it is a univariate EDA. DEUMd uses a computationally more expensive model to estimate the probability distribution than other univariate EDAs. We investigate the performance of DEUMd in a range of optimization problem. Our experiments shows a better performance (in terms of the number of fitness evaluation needed by the algorithm to find a solution and the quality of the solution) of DEUMd on most of the problems analysed in this paper in comparison to that of other univariate EDAs. We conclude that use of a Markov Network in a univariate EDA can be of net benefit in defined set of circumstances.