Artificial Evolution

Table of Contents

1. Frontmatter

2. GRASP-Based Memetic Algorithm for Multi-period Technician Routing Problem with Mandatory Assigned Tasks and Selective Tasks

   Loïc Cardinaël, W. Ramdane Cherif-Khettaf, Ammar Oulamara

   Abstract

   This paper addresses an industrial application encountered by water distribution companies managing extensive networks, focusing specifically on routing and scheduling of tasks over a multi-day planning horizon. Tasks are categorized into customer request tasks, which must adhere to predefined reservation dates and time windows, and internal tasks related to the company network, characterized by priority and due dates, allowing for flexible daily scheduling. The aim is to simultaneously minimize the total travel distance over the planning horizon and maximize the number of network tasks inserted, ensuring that all customer tasks are scheduled. The solution must consider constraints such as limited technician availability, multiple availability intervals, and maximum daily working hours. Additionally, penalties are incurred for unassigned network tasks.

   The problem is formulated as a novel variant of the Multi-period Technician Routing and Scheduling Problem with Profits (MPTRSPP). To tackle this problem, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) based on a memetic algorithm in the local search phase. The memetic algorithm uses a giant tour encoding of chromosomes and integrates an extended optimal split method. Computational experiments conducted on real-world instances illustrate the effectiveness of the proposed GRASP approach.

3. Investigation of Structures for Routing Rules Designed by Genetic Programming for the Electric Vehicle Routing Problem

   Marko Đurasević, Nikolina Frid, Francisco Javier Gil-Gala

   Abstract

   The electric vehicle routing problem (EVRP) is becoming an increasingly important in today’s world. Its relevance stems from the fact that logistic processes play a pivotal role in many industries, but also since they have a negative influence on the environment. This motivates research on new methods that can solve such problems more efficiently. Routing rules (RRs) represent simple heuristics that can efficiently construct solutions for large or dynamic EVRPs. However, manual design of such heuristics is a tedious and time consuming process, because of which it is being automatised with the use of genetic programming (GP). Although GP can generate efficient RRs, their performance can be significantly influenced by the design choices performed when defining their structure. Therefore, in this study, we investigate how different design choices in the design of RRs influence their performance. We examine 4 design decisions, which concern the selection of customers, charging stations and vehicles during the process of solution construction. Through an extensive experimental analysis we investigate the influence of these design decisions on the performance of RRs for problems with different properties and structures. The obtained results demonstrate that the performance of RRs is heavily influenced by the different design choices, however, there is no single combination of those design choices that works best for all problem variants, and thus it is imperative to select them according to the problem variant that is being optimised.

4. Optimizing Scheduling for Energy Sales in Public Stations: A Revenue Management Perspective

   Abdennour Azerine, Mahmoud Golabi, Ammar Oulamara, Lhassane Idoumghar

   Abstract

   Electric vehicles (EVs) play a crucial role in reducing greenhouse gas emissions and meeting climate targets. However, the increasing adoption of EVs presents significant challenges to the existing electrical grid, underscoring the necessity for efficient charging strategies. This paper explores the intricate task of scheduling EV charging at public stations, considering the vehicles’ arrival and departure times. EV drivers specify their charging needs before reaching the station. To maximize the station’s revenue, the scheduler strategically allocates chargers and manages power distribution, ensuring that power capacity and charger availability constraints are met. As customers may withdraw their demand if the station cannot meet their minimum required charging level, a revenue management strategy is used to prioritize loyal customers with consistent, long-term demands over random customers with uncertain future needs. The problem is initially formulated as a mixed-integer linear programming (MILP) model, which is solved using an exact solver. Additionally, a heuristic algorithm and a variable neighborhood search (VNS) metaheuristic are developed as alternative solution approaches. Simulation results demonstrate the effectiveness of the proposed methods, highlighting their capability to address the complexities of EV charging scheduling problems efficiently.

5. A Study of an Ant-Based Algorithm to Model Cyclist Behavior in Bicycle-Friendly Cities

   Felix Repusseau, Emmanuel Néron, Tifenn Rault, Nicolas Monmarché

   Abstract

   In this article we study how ant algorithms can be adapted to simulate the decision of cyclists in a city with bicycle lanes. The difference between ants and cyclists is that ants don’t have GPS and a shortest-path algorithm: they use a kind of compass and influence each other through pheromones. By comparing ant trajectories with artificial human trajectories, we show that compass and pheromones are relevant in a typical urban graph.

6. Paving the Way Towards Evolutionary Machine Teaching: An Application to 4-Part Harmony

   Elia Pacioni, Francisco Fernández De Vega

   Abstract

   Human experts have traditionally been involved in the development of Artificial Intelligence approaches to real-life problem solving. The inclusion of expert knowledge can clearly show the difficulties in adequately finding solutions in huge search spaces, while the opposite usually leads to over-simplification and poor solutions. This paper shows how a proper combination of human learning, as developed by inexperienced students in a given domain, and teaching, as applied by the experts, may allow to find new ways for finding solutions of quality. A real-life problem is used to conduct the research: the 4-part harmonization problem that music students face. Results show how we may profit from the way humans teach and learn, thus allowing to consider teaching within the evolutionary problem-solving approaches, thus paving the way towards evolutionary machine teaching.

7. Scalable Local Optima Networks for Continuous Search Spaces

   Jonathan E. Fieldsend

   Abstract

   Local optima networks (LONs) are a compact graph-based visualisation and characterisation approach to represent the fitness landscape of an optimisation problem. LONs are most frequently generated for combinatorial problems, where neighbourhoods can be crisply defined. A handful of approaches exist for continuous spaces, e.g. using derivatives-based local search approaches and basin-hopping, or by discretising the continuous space via gridding. Here we propose a new approach. Neighbourhoods are defined as balls around quasi-random samples from the search space. Basins and local optima are identified by greedily traversing these sampled neighbourhoods. One interpretation of such a formulation is that it approximates the LON induced by a \((1+\lambda )\)–Evolution Strategy (ES) with a ball mutation. The proposal allows the generation of LONs for problems with non-linear constraints, and discontinuous functions. We detail construction methods and illustrate the effective landscapes for some different objective functions using both the proposed methodology and derivatives-based alternatives.

8. Comparing Quantum Annealer and Metaheuristic Methods to Solve the Steiner Tree Problem

   Darren M. Chitty, James Charles, Alberto Moraglio, Ed Keedwell

   Abstract

   Quantum computers are early-stage technology, but are progressing rapidly. Here, we compare metaheuristics with a quantum annealer (QA), a quantum computer tailored to solve combinatorial optimisation problems formulated as a Quadratic Unconstrained Binary Optimisation (QUBO) problem. Formulating non-trivial optimisation problems as QUBOs is a challenge, so it is to ensure that the direct comparison of classical and quantum search algorithms is conducted fairly. This paper illustrates the use of a streamlined methodology to derive a QUBO for a classical optimisation problem – the Steiner tree problem – and provides comprehensive experiments comparing D-WAVE pure QA and hybrid QA with classical methods including Simulated Annealing and Genetic Algorithms. We find that the pure QA suffers from considerable qubit noise but the hybrid QA is on a par with traditional methods.

9. Classification vs Regression Models in a Decision Tree-Based Interactive Evolutionary Multi-objective Optimization Algorithm

   Mahmoud Golabi, Seyed Mahdi Shavarani, Lhassane Idoumghar

   Abstract

   Multi-objective optimization problems involve conflicting objectives, making it particularly challenging to find a single optimal solution. Instead, their solution methods aim to yield numerous high-quality, non-dominated solutions, each representing different trade-offs among the objectives. Evolutionary multi-objective algorithms (EMOAs) are widely used to generate these diverse sets of non-dominated solutions. However, the sheer number of solutions complicates decision-making by making it difficult to identify the most desirable ones. Additionally, generating a diverse representation of non-dominated solutions becomes increasingly difficult as the number of objectives increases. Interactive EMOAs leverage the decision-maker’s (DM) preferences to guide the search towards a smaller subset of preferred non-dominated solutions or even the most preferred one. However, existing methods often lack robustness in learning the DM’s preferences under realistic conditions. Recently, the use of decision trees (DTs) for learning DM’s preferences has been proposed to enhance the robustness of interactive algorithms. Since the performance of different DT models in preference learning has not been thoroughly analyzed, this study aims to evaluate and compare the effectiveness of DT classification and regression models in learning to rank, which is a crucial element in ranking-based interactive algorithms. The analysis considers different problems with different dimensions and various preference models. The results demonstrate that DT-classification-based preference learning is superior to the DT-regression-based method. Nevertheless, this study discusses an improvement to the regression models that could enhance their performance, paving the way towards the realization of the potential of these models.

10. Tackling Long-Range Dependencies in Dynamic Range Compression Modeling via Deep Learning

    Yann Bourdin, Pierrick Legrand, Fanny Roche

    Abstract

    Deep learning has increasingly been studied as a black-box method for audio effects modeling. While successful for some effects like equalizers or guitar amplifiers, learning long-range dependencies remains challenging. We discuss the disparity between streamed target and windowed target, and introduce the state prediction network, a general method addressing long-range dependencies in stateful models. We propose a novel model architecture, conduct hyperparameter search, and compare it with stateless and recurrent state-of-the-art models. Our architecture achieves better spectral accuracy with reduced training costs.

11. Optimizing Reservoir Computing with Genetic Algorithm for High-Dimensional SARS-CoV-2 Hospitalization Forecasting: Impacts of Genetic Algorithm Hyperparameters on Feature Selection and Reservoir Computing Hyperparameter Tuning

    Thomas Ferté, Dan Dutartre, Boris Hejblum, Romain Griffier, Vianney Jouhet, Rodolphe Thiébaut, Xavier Hinaut, Pierrick Legrand

    Abstract

    This study focuses on forecasting SARS-CoV-2 hospitalizations 14 days ahead at Bordeaux University Hospital using a high-dimensional dataset with 409 predictors and 586 observations, combining public data and electronic health records. Previous research showed that integrating reservoir computing (RC) with genetic algorithm (GA) for hyperparameter optimization and feature selection outperformed state-of-the-art methods. However, the behavior of RC-GA under high-dimensional conditions is not well understood. This work examines the impact of GA hyperparameters (GA-HP), specifically the mutation probability of feature selection and the extent of mutation on a critical RC hyperparameter (RC-HP), the leaking rate.

    GA-HP significantly influence feature selection and RC-HP optimization. Higher mutation rates led to a more diverse set of selected features and fewer total features, resulting in increased mean absolute error (MAE) on the training set but comparable MAE on the test set, suggesting reduced overfitting. Conversely, lower mutation rates of categorical genes and leaking rates correlated with slightly poorer performance, indicating potential lack of exploration during RC-HP selection. Notably, a bimodal convergence of the leaking rate was observed, with lower leaking rates enhancing training performance but slightly diminishing test performance. The RC-GA approach demonstrated robust behavior with higher leaking rates, possibly due to increased regularization effects from higher ridge values.

    Optimizing RC-GA in a high-dimensional setting remains challenging. Current practices using the median forecast of the top 40 RC-HP sets might not be optimal. Enhancing GA for high-dimensional contexts and exploring complementary RC-HP sets instead of selecting the top 40 might further improve forecasting accuracy.

12. Can Mutations Replace Local Search? Studying the Effect of Repeated Genetic Programming Operators in the Unrelated Machines Environment

    Josip Hrvatić, Marko Đurasević, Francisco Javier Gil-Gala, Domagoj Jakobović

    Abstract

    Dispatching rules are simple heuristics primarily used for solving dynamic scheduling problems. Since designing such rules manually is time-consuming and requires expert knowledge, genetic programming is employed to develop them automatically. However, the quality of those automatically developed rules is limited and must therefore be further improved by integrating genetic programming with more sophisticated methods, most notably local search. This paper explores the potential of substituting local search algorithms with repeated applications of genetic operators, specifically mutation and crossover, within genetic programming to obtain better performing dispatching rules for the unrelated machines scheduling environment. Experimental results indicate that certain configurations of repeated genetic operators significantly outperform the baseline genetic programming approach and can be comparable or, at times, superior to the variants enhanced by local search. This finding indicates a significant advancement in evolutionary algorithm design for scheduling problems, proposing the strategic repetition of genetic operators as a potentially simpler yet effective alternative to more complex local search strategies.

13. Optimizing the Viability of Interacting Systems with Evolutionary Algorithms

    Alice de Lapparent, Alberto Tonda, Rodolphe Sabatier, Evelyne Lutton, Isabelle Alvarez, Sophie Martin

    Abstract

    Viability theory studies the behavior of dynamical systems, with the aim of keeping them viable, or in other terms, keep their trajectories within desired constraints in the state space. Finding strategies to keep a dynamical system viable is already a challenge for optimization algorithms, but this task becomes even harder for multi-agent systems, where agents’ individual decision can influence the dynamics of the whole system. In this paper, we consider a multi-agent dynamic system and introduce an evolutionary approach for optimizing agents’ interaction behaviour, delimited by some a priori agreements, in the form of a set of commitments, with the objective of keeping the system viable. This approach is tested on the case-study of a collective project grouping several agritouristic activities on a shared place. Experimental results show that it is possible to find a set of agents’ commitments that can maintain system viability, supporting the proposed framework’s effectiveness.

14. Single-Objective Constrained Optimization for Gene Regulatory Networks Modeling

    Guillaume Grataloup, Denis Pallez, Gilles Bernot, Jean-Paul Comet

    Abstract

    In the course of apprehending of biological system, the modeling process of gene interactions plays a crucial rocketing role. Unfortunately, the main bottleneck of the modeling process is always the determination of the model parameters. This study focuses on the problem of identifying Gene Regulatory Network (GRN) variables in a discrete framework, represented by gene product concentration thresholds, that separate discrete states of genes contained in the GRN. We propose to compute thresholds from graphs representing interactions between biological genes, gene product concentrations experimentally measured by biologists, and observable behaviors. In this setting, we have developed some adaptations of bio-inspired methods to assist modelers and to propose compatible models to biologists. Since the parameter identification problem is constrained, in this article we focus on adapting and comparing three different heuristics of the CEC’2020 competition for solving single-objective constrained problems using the aforementioned bio-inspired methods by defining a dedicated fitness. To validate our approach, we used an abstract model of the cell cycle and found the performances of the three heuristics consistent with the results of the CEC’2020 competition. This serves as a proof of concept for the development of methods to identify parameters of GRN models using available data and relying less on biological expertise.

15. Symbolic Regression of Confidence Intervals for Conformal Prediction

    Alberto Tonda, Alejandro Lopez-Rincon, David Rojas-Velazquez, Evelyne Lutton

    Abstract

    Conformal prediction is a class of algorithms designed to deliver confidence intervals around point predictions of models, with robust theoretical guarantees. Nevertheless, when dealing with regression problems, the original methodology always computes confidence intervals of the same size, independently of the magnitude of the predicted value \(\hat{y}\), impairing the potential usefulness of the information. Several alternatives to properly scale the confidence intervals have been proposed in specialized literature, using assessments of the difficulty of predictions to produce wider intervals for more difficult points and tighter ones for easier predictions. However, each conformal prediction algorithm only exploits one specific type of information to evaluate the difficulty of a point prediction, such as Euclidean distance from points observed during training, or variance in the values of predictions for neighboring points. In this work, we introduce a novel symbolic regression approach to computation of confidence intervals. The algorithm can take into account all types of information considered by other conformal predictors at the same time, delivering human-interpretable equations that describe the amplitude of the intervals, tailored to the specific regression problem under evaluation. Experimental results show that the proposed approach outperforms other conformal predictors on an established benchmark suite of regression problems.

16. A New Step Size Update Strategy for CMA-ES in Multi-objective Optimisation

    Zheng Tan, Bo Yuan, Hao Wang, Miqing Li

    Abstract

    The covariance matrix adaptation evolution strategy (CMA-ES) is one of the most widely used evolutionary algorithms in single-objective black-box optimisation. Unlike the popularity of the single-objective CMA-ES, its multi-objective variant - MO-CMA-ES - has not been extensively studied. In MO-CMA-ES, like CMA-ES the step size, which determines how far the mutation can go, depends on whether a newly generated solution is better than its parent in the population. However, unlike single-objective optimisation where all solutions are distinguishable about their objective values, in multi-objective optimisation there may exist many solutions incomparable (i.e., non-dominated to each other). Updating the step size based on the qualitative comparison between solutions may not work best for the multi-objective case.

    In this paper, we propose a simple step-size update strategy for MO-CMA-ES. The proposed strategy considers how much change the newly generated solution has compared with its parent. Specifically, we factor in the difference in the non-domination levels that the offspring and parent solutions are located in, attempting to make use of quantitative information that may better reflect the current search progress. Experimental results show the effectiveness of the proposed strategy - it can accelerate the convergence speed on almost all the test problems considered.

17. UMDA with Random Affine Maps

    Arnaud Berny

    Abstract

    We propose to extend the probability model of UMDA by means of random affine maps on bit vectors. To limit the complexity, the bit matrix of affine maps is represented as short sequences of simple and reversible bit operations called transvections. We consider two versions of UMDA with random affine maps (RAMU) updating one or two probability vectors. We provide fixed-budget experiments to explore the behavior of RAMU and compare it with UMDA.

18. Backmatter