Applications of Evolutionary Computation

The majority of standard approaches to financial portfolio optimization (PO) are based on the mean-variance (MV) framework. Given a risk aversion coefficient, the MV procedure yields a single portfolio that represents the optimal trade-off between risk and return. However, the resulting optimal portfolio is known to be highly sensitive to the input parameters, i.e., the estimates of the return covariance matrix and the mean return vector. It has been shown that a more robust and flexible alternative lies in determining the entire region of near-optimal portfolios. In this paper, we present a novel approach for finding a diverse set of such portfolios based on quality-diversity (QD) optimization. More specifically, we employ the CVT-MAP-Elites algorithm, which is scalable to high-dimensional settings with potentially hundreds of behavioral descriptors and/or assets. The results highlight the promising features of QD as a novel tool in PO.

For real-time applications in embedded systems, an efficient image filter is not defined solely by its accuracy but by the delicate balance it strikes between precision and computational cost. While one approach to manage an algorithm’s computing demands involves evaluating its complexity, an alternative strategy employs a multi-objective algorithm to optimize both precision and computational cost.

In this paper, we introduce a multi-objective adaptation of Cartesian Genetic Programming aimed at enhancing image filter performance. We refine the existing Cartesian Genetic Programming framework for image processing by integrating the elite Non-dominated Sorting Genetic Algorithm into the evolutionary process, thus enabling the generation of a set of Pareto front solutions that cater to multiple objectives.

To assess the effectiveness of our framework, we conduct a study using a Urban Traffic dataset and compare our results with those obtained using the standard framework employing a mono-objective evolutionary strategy. Our findings reveal two key advantages of this adaptation. Firstly, it generates individuals with nearly identical precision in one objective while achieving a substantial enhancement in the other objective. Secondly, the use of the Pareto front during the evolution process expands the research space, yielding individuals with improved fitness.

The Low-Memory Matrix Adaptation Evolution Strategy is a recent variant of CMA-ES that is specifically meant for large-scale numerical optimization. In this paper, we investigate if and how gradient information can be included in this algorithm, in order to enhance its performance. Furthermore, we consider the incorporation of Lévy flight to alleviate stability issues due to possibly unreliably gradient estimation as well as promote better exploration. In total, we propose four new variants of LMMA-ES, making use of real and estimated gradient, with and without Lévy flight. We test the proposed variants on two neural network training tasks, one for image classification through the newly introduced Forward-Forward paradigm, and one for a Reinforcement Learning problem, as well as five benchmark functions for numerical optimization.

In this article, we focus on a dynamic aircraft conflict resolution problem. The objective of an algorithm dedicated to dynamic problems shifts from finding the global optimum to detecting changes and monitoring the evolution of the optima over time. In the air traffic control domain, there is added value in dealing quickly with the dynamic nature of the environment and providing the controller with solutions that are stable over time. In this article, we compare two approaches of an evolutionary algorithm for the management of aircraft in a control sector at a given flight level: one is naive, i.e. the resolution of the current situation is reset to zero at each time step, and the other is memory-based, where the last population of the optimisation is stored to initiate the resolution at the next time step. Both approaches are evaluated with basic and optimised operators and settings. The results are in favour of the optimised version with explicit memory, where conflict-free solutions are found quicker and the solutions are more stable over time. Furthermore in the case of an external action, although the diversity of the population could be lower with the memory-based approach, the presence of memory does not appear to be a hindrance and, on average, improves the solver’s responsiveness.

Imbalanced datasets pose a significant and longstanding challenge to machine learning algorithms, particularly in binary classification tasks. Over the past few years, various solutions have emerged, with a substantial focus on the automated generation of synthetic observations for the minority class, a technique known as oversampling. Among the various oversampling approaches, the Synthetic Minority Oversampling Technique (SMOTE) has recently garnered considerable attention as a highly promising method. SMOTE achieves this by generating new observations through the creation of points along the line segment connecting two existing minority class observations. Nevertheless, the performance of SMOTE frequently hinges upon the specific selection of these observation pairs for resampling. This research introduces the Genetic Methods for OverSampling (GM4OS), a novel oversampling technique that addresses this challenge. In GM4OS, individuals are represented as pairs of objects. The first object assumes the form of a GP-like function, operating on vectors, while the second object adopts a GA-like genome structure containing pairs of minority class observations. By co-evolving these two elements, GM4OS conducts a simultaneous search for the most suitable resampling pair and the most effective oversampling function. Experimental results, obtained on ten imbalanced binary classification problems, demonstrate that GM4OS consistently outperforms or yields results that are at least comparable to those achieved through linear regression and linear regression when combined with SMOTE.

When using a meta-heuristic based optimiser in some industrial scenarios, there may be a need to amend the objective function as time progresses to encompass constraints that did not exist during the development phase of the software. We propose a means by which a Domain Specific Language (DSL) can be used to allow constraints to be expressed in language familiar to a domain expert, allowing additional constraints to be added to the objective function without the need to recompile the solver. To illustrate the approach, we consider the construction of staff training schedules within an organisation where staff are already managed within highly constrained schedules. A set of constraints are hard-coded into the objective function in a conventional manner as part of a Java application. A custom built domain specific language (named Basil) was developed by the authors which is used to specify additional constraints affecting individual members of staff or groups. We demonstrate the use of Basil and show how it allows the specification of additional constraints that enable the software to meet the requirements of the user without any technical knowledge.

Portfolio diversification is a crucial strategy for mitigating risk and enhancing long-term returns. This paper introduces a unique approach to large-scale diversification using Ant Brood Sorting clustering, a nature-inspired algorithm, in conjunction with co-integration measure of time series. Traditional diversification strategies often struggle during uncertain market times. In contrast, the proposed method leverages Ant Brood Sorting to group similar stocks based on the co-integration of their closing prices. This approach allows for the creation of diversified portfolios from a wide range of stocks. The study presents promising results, with clusters of stocks showing both high correlation and cosine similarity, validating the effectiveness of the approach. Silhouette score, a measure of cluster quality, and inter-cluster analysis demonstrate support in validating the results of the study by displaying similarities between the stocks being clustered and distinctiveness with stocks in other clusters. The research contributes to the application of nature-inspired algorithms in large-scale portfolio diversification, offering potential benefits for investors seeking resilient and balanced portfolios.

The hybrid modelling framework of gene regulatory networks (hGRNs) is a functional framework for studying biological systems, taking into account both the structural relationship between genes and the continuous time evolution of gene concentrations. The goal is to identify the variables of such a model, controlling the aggregated experimental observations. A recent study considered this task as a free optimisation problem and concluded that metaheuristics are well suited. The main drawback of this previous approach is that panmictic heuristics converge towards one basin of attraction in the search space, while biologists are interested in finding multiple satisfactory solutions. This paper investigates the problem of multimodality and assesses the effectiveness of cellular genetic algorithms (cGAs) in dealing with the increasing dimensionality and complexity of hGRN models. A comparison with the second variant of covariance matrix self-adaptation strategy with repelling subpopulations (RS-CMSA-ESII), the winner of the CEC’2020 competition for multimodal optimisation (MMO), is made. Results show evidence that cGAs better maintain a diverse set of solutions while giving better quality solutions, making them better suited for this MMO task.

Can we use computational modeling to infer whether fish can remember or anticipate each other’s movements? What minimum of temporal input and internal complexity is sufficient to model a specific fish, or to produce generally “fish-like” behavior? Agent-based modeling to emulate biological behavior has been used to great effect, both in real-world and simulated experiments. We present feedforward neural network architectures for simulating fish social interactions, evolved using evolution strategies in two different experiments. Evolution of the temporal input of the partner fish’s position when testing models on labeled data uncovers anticipation or memory capacities used by a focal fish. When testing via a general discriminator for fish-like trajectories, the right neural network architecture and temporal input are shown to be a necessary, but insufficient condition for highly lifelike simulations. Lifelike simulations for some datasets are possible as simple functions of the input, showing variability in the complexity of individual fish’s social behaviors.

The Bin Packing Problem (BPP) is an optimization problem where a number of objects are placed within a finite space. This problem has a wide range of applications, from improving the efficiency of transportation to reducing waste in manufacturing. In this paper, we are considering a variant of the BPP where irregular shaped polygons are required to be placed as close to the center as possible. This variant is motivated by its application in 3D printing, where central placement of the objects improves the printing reliability. To find (near) optimum solutions to this problem, we employ Evolutionary Algorithms, and propose several heuristics. We show how these heuristics interact with each other, and their most effective configurations in providing the best solutions.

Behaviour trees (BTs) are commonly used as controllers in robotic swarms due their modular composition and to the fact that they can be easily interpreted by humans. From an algorithmic perspective, an additional advantage is that extra modules can easily be introduced and incorporated into new trees. Genetic Programming (GP) has already been shown to be capable of evolving BTs to achieve a variety of sub-tasks (primitives) of a higher-level goal. In this work we show that a hierarchical controller can be evolved that first uses GP to evolve a repertoire of primitives expressed as BTs, and then to evolve a high-level BT controller that leverages the evolved repertoire for a foraging task. We show that the hierarchical approach that uses BTs at two levels outperforms a baseline in which the BTs are evolved using only low-level nodes. In addition, we propose a method to improve the quality of the primitive repertoire, which in turn results in improved high-level BTs.

The problem of finding the optimal placement of emergency exits in an indoor environment to facilitate the rapid and orderly evacuation of crowds is addressed in this work. A cellular-automaton model is used to simulate the behavior of pedestrians in such scenarios, taking into account factors such as the environment, the pedestrians themselves, and the interactions among them. A metric is proposed to determine how successful or satisfactory an evacuation was. Subsequently, two metaheuristic algorithms, namely an iterated greedy heuristic and an evolutionary algorithm (EA) are proposed to solve the optimization problem. A comparative analysis shows that the proposed EA is able to find effective solutions for different scenarios, and that an island-based version of it outperforms the other two algorithms in terms of solution quality.

The multi-objective pathfinding problem is a complex and NP-hard problem with numerous industrial applications. However, the number of non-dominated solutions can often exceed human comprehension capacity. This paper introduces a novel methodology that leverages the concept of a Pareto graph to address this challenge. Unlike previous approaches, our method constructs a graph that relates paths where there is potential for change between them and applies a graph community algorithm to identify solution subsets based on specific aspects defined by a decision-maker. We describe the construction of a Route Change Graph (RCG) to represent possible route changes. A matrix is constructed to save the number of possible change opportunities between two routes, which is then used to construct the RCG. We propose using a threshold value for edge weights in the graph construction, balancing between minimising the number of edges and maintaining connectivity. Following the construction of the RCG, we apply a community detection algorithm to identify closely related solutions, using Leiden algorithm due to its efficiency and refinement phase. We propose calculating various metrics on these communities, including Density, Average Cluster Coefficient, Group Betweenness Centrality, and Graph Degree Centrality, to provide insights into the network structure and interconnectivity. This methodology offers a more manageable set of solutions for decision-makers, enhancing their ability to make informed decisions in complex multi-objective pathfinding problems.

Software modularisation is a pivotal facet within software engineering, seeking to optimise the arrangement of software components based on their interrelationships. Despite extensive investigations in this domain, particularly concerning evolutionary computation, the research emphasis has transitioned towards solution design and convergence analysis rather than pioneering methodologies. The primary objective is to attain efficient solutions within a pragmatic timeframe. Recent research posits that initial positions in the search space wield minimal influence, given the prevalent trend of methods converging upon akin local optima. This paper delves into this phenomenon comprehensively, employing graph partitioning techniques on dependency graphs to generate initial clustering arrangement seeds. Our empirical discoveries challenge conventional insight, underscoring the pivotal role of seed selection in software modularisation to enhance overall outcomes.

Determining appropriate weights and biases for feed-forward neural networks is a critical task. Despite the prevalence of gradient-based methods for training, these approaches suffer from sensitivity to initial values and susceptibility to local optima. To address these challenges, we introduce a novel two-level clustering-based differential evolution approach, C2L-DE, to identify the initial seed for a gradient-based algorithm. In the initial phase, clustering is employed to detect some regions in the search space. Population updates are then executed based on the information available within each region. A new central point is proposed in the subsequent phase, leveraging cluster centres for incorporation into the population. Our C2L-DE algorithm is compared against several recent DE-based neural network training algorithms, and is shown to yield favourable performance.

Wildfires cause significant damage costs globally, and it is likely that they are becoming more damaging due to climate change. Here we study methods for fire suppression, after a breakout of fire. In our model, we have a grid graph \(G=(V,A)\) that represents the discretization of a terrain into cells and an ignition node \(s \in V\) from which the fire spreads to other nodes. The spread of the fire is defined by the arc weights, which can be used to model important factors such as wind direction and vegetation type. At various points in time, one or more fire suppression resources become available to be applied to nodes in the graph that are not yet burned. Applying a resource to a node \(v \in V\) adds a delay to the outgoing edges of v, which causes a local slowdown in fire propagation. The goal is to find an allocation of resources to the nodes of the graph such that the total burned area at a target time is minimized. In this work, we propose a heuristic algorithm based on beam search to tackle this problem. Our computational experiments show that our approach is able to consistently find the optimal solution to almost all instances used in literature, but in considerably less time than previous approaches.

Rotation symmetric Boolean functions represent an interesting class of Boolean functions as they are relatively rare compared to general Boolean functions. At the same time, the functions in this class can have excellent cryptographic properties, making them interesting for various practical applications. The usage of metaheuristics to construct rotation symmetric Boolean functions is a direction that has been explored for almost twenty years. Despite that, there are very few results considering evolutionary computation methods. This paper uses several evolutionary algorithms to evolve rotation symmetric Boolean functions with different properties. Despite using generic metaheuristics, we obtain results that are competitive with prior work relying on customized heuristics. Surprisingly, we find that bitstring and floating point encodings work better than the tree encoding. Moreover, evolving highly nonlinear general Boolean functions is easier than rotation symmetric ones.

The complexity of Multi-Objective (MO) continuous optimisation problems arises from a combination of different characteristics, such as the level of multi-modality. Earlier studies revealed that there is a conflict between solver convergence in objective space and solution set diversity in the decision space, which is especially important in the multi-modal setting. We build on top of this observation and investigate this trade-off in a multi-objective manner by using multi-objective automated algorithm configuration (MO-AAC) on evolutionary multi-objective algorithms (EMOA). Our results show that MO-AAC is able to find configurations that outperform the default configuration as well as configurations found by single-objective AAC in regards to objective space convergence and diversity in decision space, leading to new recommendations for high-performing default settings.

One of the strong points of evolutionary algorithms and other similar metaheuristics is their robustness, which means that their performance is consistent across large varieties of problem settings. In particular, such algorithms avoid preferring one solution to another unless the optimized function gives enough reasons for doing that. This property is formally captured as invariance with regards to certain transformations of the search space and the problem definition, such as translation or rotation.

The lack of some basic invariance properties in some recently proposed “nature-inspired” algorithms, together with the deliberate misuse of commonly used benchmark functions, can present them as excellent optimizers, which they are not. One particular class of such algorithms, origin-biased metaheuristics, are good at finding an optimum at the origin and are much worse for any other purpose.

This paper presents a statistical testing procedure which can help to reveal such algorithms and to illustrate the negative aspects of their behavior. A case study involving 15 different algorithms shows that this test successfully detects most origin-biased algorithms.

This paper addresses the optimization of urban infrastructure for e-scooter mobility through a multi-criteria approach. The proposed problem considers redesigning road infrastructure to integrate e-scooters into a city’s multimodal transportation system. The objectives involve improving cycle lane coverage for e-scooters while minimizing installation costs. A parallel multi-objective evolutionary algorithm is introduced to solve this problem, applied to a real-world instance based on Málaga city data. The results showcase the algorithm’s effectiveness in exploring the Pareto front, offering diverse trade-off solutions. Key solutions are analyzed, highlighting different zones with varying trade-offs between travel time improvement and installation costs. Visualization of proposed infrastructure changes illustrates significant reductions in travel time and enhanced multimodality. Computational efficiency analysis indicates successful parallelization, achieving substantial speedup and high efficiency with up to 32 processing elements.

Training and deploying genetic programming (GP) classifiers for intrusion detection tasks on the one hand remains a challenge (high cardinality and high class imbalance). On the other hand, GP solutions can also be particularly ‘lightweight’ from a deployment perspective, enabling detectors to be deployed ‘at the edge’ without specialized hardware support. We compare state-of-the-art ensemble learning solutions from GP and XGBoost on three examples of intrusion detection tasks with 250,000 to 700,000 training records, 8 to 115 features and 2 to 23 classes. XGBoost provides the most accurate solutions, but at two orders of magnitude higher complexity. Training time for the preferred GP ensemble is in the order of minutes, but the combination of simplicity and specificity is such that the resulting solutions are more informative and discriminatory. Thus, as the number of features increases and/or classes increase, the resulting ensembles are composed from particularly simple trees that associate specific features with specific behaviours.

Evolutionary computation (EC) has a great potential of exploiting parallelization, a feature often underemphasized when describing evolutionary algorithms (EAs). In this paper, we show that the paradigm of stream processing (SP) can be used to express EAs in a way that allows the immediate exploitation of parallel and distributed computing, not at the expense of the agnosticity of the EAs with respect to the application domain. We introduce the first formal framework for EC based on SP and describe several building blocks tailored to EC. Then, we experimentally validate our framework and show that (a) it can be used to express common EAs, (b) it scales when deployed on real-world stream processing engines (SPEs), and (c) it facilitates the design of EA modifications which would require a larger effort with traditional implementation.

In many machine learning applications, there are hundreds or even thousands of features available, and selecting the smallest subset of relevant features is a challenging task. More recently, researchers have investigated how data augmentation affects feature selection performance. Although evolutionary algorithms have been widely used for feature selection, no studies have investigated how data augmentation affects their performance on this challenging task. The study presented in this paper investigates how data augmentation affects the performance of evolutionary algorithms on feature selection problems. To this aim, we have tested Genetic Algorithms and Particle Swarm Optimization and compared their performance with two widely used feature selection algorithms. The experimental results confirmed that data augmentation is a promising tool for improving the performance of evolutionary algorithms for feature selection.

As global mortality rates rise alongside an increasing incidence of skin cancer, it becomes increasingly clear that the pursuit of an effective strategy to combat this challenge is gaining urgency. In traditional practices, the diagnosis of skin cancer predominantly depends on manual inspection of skin lesions. Despite its prevalent use, this approach is beset with several limitations, such as subjectivity, time constraints, and the invasive nature of biopsy procedures. Addressing these obstacles, the burgeoning field of Artificial Intelligence has been instrumental in advancing Computer Automated Diagnostic Systems (CADS) for skin cancer. A critical aspect of these systems is feature extraction, a process crucial for discerning and utilising key characteristics from raw image data, thereby bolstering the efficacy of CADS. This study introduces a feature extraction model that evolves automatically, leveraging the principles of genetic programming and cooperative coevolution. This method generates a ensemble of models that collaboratively work to extract discerning features from images of skin lesions. The model’s effectiveness is evaluated using a publicly accessible dataset, whilst further analysis pertaining to interactions between the decomposition of image colour channels are explored. The findings indicate that the proposed method either matches or significantly surpasses the performance of established benchmarks and recent methodologies in this field, underscoring its potential in enhancing skin cancer diagnostic processes.