ECTA 2024 Abstracts

Full Papers Short Papers
Full Papers
Paper Nr: 16
Title:

Randomized Local Search for Two-Dimensional Bin Packing and a Negative Result for Frequency Fitness Assignment
Authors:

Rui Zhao, Zhize Wu, Daan van den Berg, Matthias Thürer, Tianyu Liang, Ming Tan and Thomas Weise
Abstract: We consider a two-dimensional orthogonal bin packing problem (2BP) where rectangular items are to be placed into rectangular bins such that their edges are parallel to those of the bins with the aim to require as few bins as possible. Two variants of the problem are analyzed. In the 2BP|O|F, the items have a fixed orientation while in the 2BP|R|F, they can be rotated by 90 degrees. We show that on both variants, a simple randomized local search (RLS) has surprisingly good performance – if the objective function guiding the search is defined suitably. In particular, on the 2BP|O|F, the RLS performs on par with more complicated state-of-the-art metaheuristics. We furthermore investigate plugging Frequency Fitness Assignment (FFA) into the RLS, obtaining the FRLS. FFA has improved the RLS performance on several classical N P-hard optimization problems from operations research, including Max-SAT, the Job Shop Scheduling Problem, and the Traveling Salesperson Problem. This paper is the first negative result for FFA: it cannot improve algorithm performance on the 2BP variants studied. This can be explained by the fact that RLS already performs very well on the instances of the 2DPackLib benchmark set used as the basis of our experiments.
Download
Paper Nr: 17
Title:

Frequency Fitness Assignment: Optimization Without Bias for Good Solution Outperforms Randomized Local Search on the Quadratic Assignment Problem
Authors:

Jiayang Chen, Zhize Wu, Sarah L. Thomson and Thomas Weise
Abstract: The Quadratic Assignment Problem (QAP) is one of the classical NP-hard tasks from operations research with a history of more than 65 years. It is often approached with heuristic algorithms and over the years, a multitude of such methods has been applied. All of them have in common that they tend to prefer better solutions over worse ones. We approach the QAP with Frequency Fitness Assignment (FFA), an algorithm module that can be plugged into arbitrary iterative heuristics and that removes this bias. One would expect that a heuristic that does not care whether a new solution is better or worse compared to the current one should not perform very well. We plug FFA into a simple randomized local search (RLS) and yield the FRLS, which surprisingly outperforms RLS on the vast majority of the instances of the well-known QAPLIB benchmark set.
Download
Paper Nr: 19
Title:

Randomized Local Search vs. NSGA-II vs. Frequency Fitness Assignment on The Traveling Tournament Problem
Authors:

Cao Xiang, Zhize Wu, Daan van den Berg and Thomas Weise
Abstract: The classical compact double-round robin traveling tournament problem (TTP) asks us to schedule the games of n teams in a tournament such that each team plays against every other team twice, once at home and once away (doubleRoundRobin constraint). The maxStreak constraint prevents teams from having more than three consecutive home or away games. The noRepeat constraint demands that, before two teams can play against each other the second time, they must at least play one other game in between. The goal is to find a game plan observing all of these constraints and having the overall shortest travel length. We define a game-permutation based encoding that allows for representing game plans with arbitrary numbers of constraint violations and tackle the TTP as a bi-objective problem minimizing both the number of constraint violations and the travel length by applying the well-known NSGA-II. We combine both objectives in a lexicographic prioritization scheme and also apply the randomized local search RLS to this single-objective variant of the problem. We realize that Frequency Fitness Assignment (FFA), which makes algorithms invariant under all injective transformations of the objective function value, would also make optimization algorithms invariant under all lexicographic prioritization schemes for multi-objective problems. The FRLS, i.e., the RLS with FFA plugged in, would therefore solve both possible prioritizations of our TTP variants at once. We thus also explore its performance on the TTP. We find that RLS performs surprisingly well and can find game plans without constraint violations reliably until a scale of 36 teams, whereas FRLS and NSGA-II have an advantage on small- and mid-scale problems.
Download
Paper Nr: 22
Title:

A Simple yet Effective Algorithm for the Asteroid Routing Problem
Authors:

Valentino Santucci
Abstract: In this paper we investigate the application of meta-heuristic algorithms in the context of expensive black-box permutation optimization. These problems are characterized by solution spaces composed of permutations of items, where the objective function is not explicitly defined in a closed mathematical form and is costly to evaluate. The benchmark problem under investigation is the Asteroid Routing Problem (ARP), which aims to determine the optimal order for a spacecraft to visit asteroids, starting from Earth’s orbit, while minimizing both energy consumption and visit time. In particular, we examine the effectiveness of a simple algorithm, namely FAT-RLS, which is mainly based on the randomized local search scheme, equipped with a tabu structure and a mechanism to regulate the perturbation strength. A series of experiments were performed on accepted instances of the ARP in order to compare the effectiveness of FAT-RLS with respect to two established meta-heuristics for the ARP. The results clearly show that FAT-RLS achieves more effective results both considering a black-box setting and an informed setting, where the meta-heuristics are seeded with a purposely designed constructive algorithm for the ARP.
Download
Paper Nr: 27
Title:

Impact of Spatial Transformations on Exploratory and Deep-Learning Based Landscape Features of CEC2022 Benchmark Suite
Authors:

Haoran Yin, Diederick Vermetten, Furong Ye, Thomas H.W. Bäck and Anna V. Kononova
Abstract: When benchmarking optimization heuristics, we need to take care to avoid an algorithm exploiting biases in the construction of the used problems. One way in which this might be done is by providing different versions of each problem but with transformations applied to ensure the algorithms are equipped with mechanisms for successfully tackling a range of problems. In this paper, we investigate several of these problem transformations and show how they influence the low-level landscape features of problems from the Congress on Evolutionary Computation 2022 benchmark suite. Our results highlight that even relatively small transformations can significantly alter the measured landscape features. This poses a wider question of what properties we want to preserve when creating problem transformations, and how to measure them fairly.
Download
Paper Nr: 30
Title:

Real-Time IoMT-driven Optimisation for Large-Scale Home Health Care Planning
Authors:

Seyedamirhossein Salehiamiri, Richard Allmendinger and Arijit De
Abstract: The number of home caretakers is rising rapidly due to an increasing number of elderly people, recent pandemics, and the advancement of home health care facilities. Wearable medical devices and the Internet of Medical Things (IoMT) help health care managers monitor patients in real-time and provide remote medical care. This reduces home visits and helps Home Health Care (HHC) companies plan their resources. The paper addresses the HHC planning problem of allocating the optimal number of experts to patients while minimising the delay in visiting the patient, matching medical expertise with patient needs, and identifying the patient’s visit sequence. To tackle this, a new mixed-integer mathematical problem is proposed to reduce the total visit time for patients. This paper makes three key contributions towards tackling this plan, including (i) providing a formal definition of the problem and putting it in context with related work, (ii) proposing multiple problem instances varying in complexity, and (iii) an initial analysis of several heuristics and an exact solver (CPLEX) on these problem instances. The results indicated that the application of computational intelligence combined with IoMT can reduce patient visitation time significantly in a daily plan and therefore lead to 3.7 percent improved care for HHC patients.
Download
Paper Nr: 31
Title:

Studying the Relationship Between Crossover Features and Performance on MNK-Landscapes Using Regression Models
Authors:

Teruhisa Nakashima, Hernán Aguirre and Kiyoshi Tanaka
Abstract: Crossover is a key component of evolutionary algorithms and has been the focus of numerous studies. Its effectiveness depends on the operator’s properties to mix information, the specific characteristics of the problem, and the diversity of the population, influenced by the dynamics of the algorithm. This study focuses on binary representations and introduces a method to examine the relationship between crossover features and the performance of a multi-objective evolutionary algorithm on problem subclasses with random and neighbor patterns of variable interactions. The aim is to identify the crossover features relevant to performance in each problem subclass through regression models.
Download
Paper Nr: 35
Title:

Testing Emergent Bilateral Symmetry in Evolvable Robots with Vision
Authors:

Michele Vannucci, Satchit Chatterji and Babak H. Kargar
Abstract: Bilateral symmetry is a prominent characteristic in the animal kingdom and is linked to evolutionary advantages such as cephalization. This study investigates whether integrating vision into modular evolvable robots influences bilateral symmetry development for a targeted locomotion task. Through simulation, we found that vision did not significantly increase our measure of symmetry in the robots, which predominantly evolved into ‘snake-like’ morphologies (with only one limb extending from the head). However, vision capability was observed to accelerate the convergence of the evolutionary process in some conditions. Our findings suggest that, while vision enhances evolutionary efficiency, it does not necessarily promote symmetrical morphology in modular robots. Further research directions are proposed to explore more complex environments and alternative symmetry measures.
Download
Paper Nr: 43
Title:

Cartesian Genetic Programming Is Robust Against Redundant Attributes in Datasets
Authors:

Henning Cui and Jörg Hähner
Abstract: Real world datasets might contain duplicate or redundant attributes—or even pure noise—which may not be filtered out by data preprocessing algorithms. This might be problematic, as it decreases the performance of learning algorithms. Cartesian Genetic Programming (CGP) is able to choose its own input attributes by design. Thus, we hypothesize that CGP should be able to ignore redundant or noise attributes. In this work, we empirically show that CGP is indeed able to handle such problematic datasets. For this task, six different datasets are extended with different kinds of redundancies: Duplicated-, duplicated and noised-, and pure noise attributes. Different numbers of unwanted attributes are examined, and we present our results which indicate that CGP is robust against additional redundant or noisy attributes in a dataset. We show that there is no decrease in performance as well as no change in CGP’s convergence behaviour.
Download
Paper Nr: 54
Title:

Sampling in CMA-ES: Low Numbers of Low Discrepancy Points
Authors:

Jacob de Nobel, Diederick Vermetten, Thomas H. W. Bäck and Anna V. Kononova
Abstract: The Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is one of the most successful examples of a derandomized evolution strategy. However, it still relies on randomly sampling offspring, which can be done via a uniform distribution and subsequently transforming into the required Gaussian. Previous work has shown that replacing this uniform sampling with a low-discrepancy sampler, such as Halton or Sobol sequences, can improve performance over a wide set of problems. We show that iterating through small, fixed sets of low-discrepancy points can still perform better than the default uniform distribution. Moreover, using only 128 points throughout the search is sufficient to closely approximate the empirical performance of using the complete pseudorandom sequence up to dimensionality 40 on the BBOB benchmark. For lower dimensionalities (below 10), we find that using as little as 32 unique low discrepancy points performs similar or better than uniform sampling. In 2D, for which we have highly optimized low discrepancy samples available, we demonstrate that using these points yields the highest empirical performance and requires only 16 samples to improve over uniform sampling. Overall, we establish a clear relation between the L2 discrepancy of the used point set and the empirical performance of the CMA-ES.
Download
Paper Nr: 57
Title:

REACT: Revealing Evolutionary Action Consequence Trajectories for Interpretable Reinforcement Learning
Authors:

Philipp Altmann, Céline Davignon, Maximilian Zorn, Fabian Ritz, Claudia Linnhoff-Popien and Thomas Gabor
Abstract: To enhance the interpretability of Reinforcement Learning (RL), we propose Revealing Evolutionary Action Consequence Trajectories (REACT). In contrast to the prevalent practice of validating RL models based on their optimal behavior learned during training, we posit that considering a range of edge-case trajectories provides a more comprehensive understanding of their inherent behavior. To induce such scenarios, we introduce a disturbance to the initial state, optimizing it through an evolutionary algorithm to generate a diverse population of demonstrations. To evaluate the fitness of trajectories, REACT incorporates a joint fitness function that encourages local and global diversity in the encountered states and chosen actions. Through assessments with policies trained for varying durations in discrete and continuous environments, we demonstrate the descriptive power of REACT. Our results highlight its effectiveness in revealing nuanced aspects of RL models’ behavior beyond optimal performance, with up to 400% increased fidelities, contributing to improved interpretability. Code and videos are available at https://github.com/philippaltmann/REACT.
Download
Paper Nr: 62
Title:

Hybrid Genetic Programming and Deep Reinforcement Learning for Low-Complexity Robot Arm Trajectory Planning
Authors:

Quentin Vacher, Nicolas Beuve, Paul Allaire, Thibaut Marty, Mickaël Dardaillon and Karol Desnos
Abstract: Robot arm control is a technological challenge where an algorithm needs to learn a deep understanding of spatial navigation. In particular, spatial navigation requires learning the relationship between the motor joint angular positions and the Cartesian coordinates of the robot. Trajectory planning is an even more complex challenge, where the algorithm must create a trajectory between two coordinates that does not cause a collision. State-of-the-art algorithms capable of solving trajectory planning are based on deep Reinforcement Learning (RL). These algorithms achieve high accuracy but suffer from high computational complexity. This paper proposes to use a genetic RL algorithm, the Tangled Program Graphs (TPGs), to solve trajectory planning. Using a genetic process, the TPGs generate a graph of programs with low inference complexity. On a first trajectory planning problem, the algorithm used achieves performance close to the state-of-the-art, but with a 100 less execution time and a 20× smaller model size. On a second and more difficult problem, the TPGs are not able to learn with efficiency. We propose a hybrid solution that mixes the TPGs and a state-of-the-art deep RL algorithm, the Soft Actor-Critic (SAC). This solution achieves better performance than the state-of-the-art for both problems, with 6 to 20 times faster execution times.
Download
Paper Nr: 63
Title:

Alternative Step-Size Adaptation Rule for the Matrix Adaptation Evolution Strategy
Authors:

Eryk Warchulski and Jarosław Arabas
Abstract: In this paper, we present a comparison of various step-size adaptation rules for the Matrix Adaptation Evolution Strategy (MA-ES) algorithm, which is a lightweight version of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). In contrast to CMA-ES, MA-ES does not require to invoke numerically complex covariance matrix factorization. We take a step further in this direction and provide a quantitative assessment of alternative step-size rules to Cumulative Step Adaptation (CSA), which is considered to be a state-of-the-art method. Our study shows that generalized 1/5-th success rules like the Previous Population Midpoint Fitness rule (PPMF) or Population Success Rule (PSR) exhibit comparable or superior performance to the CSA rule on standard benchmark problems, including the CEC benchmark suites.
Download
Paper Nr: 75
Title:

Optimizing Genetic Algorithms Using the Binomial Distribution
Authors:

Vincent A. Cicirello
Abstract: Evolutionary algorithms rely very heavily on randomized behavior. Execution speed, therefore, depends strongly on how we implement randomness, such as our choice of pseudorandom number generator, or the algorithms used to map pseudorandom values to specific intervals or distributions. In this paper, we observe that the standard bit-flip mutation of a genetic algorithm (GA), uniform crossover, and the GA control loop that determines which pairs of parents to cross are all in essence binomial experiments. We then show how to optimize each of these by utilizing a binomial distribution and sampling algorithms to dramatically speed the runtime of a GA relative to the common implementation. We implement our approach in the open-source Java library Chips-n-Salsa. Our experiments validate that the approach is orders of magnitude faster than the common GA implementation, yet produces solutions that are statistically equivalent in solution quality.
Download
Short Papers
Paper Nr: 18
Title:

Generating Small Instances with Interesting Features for the Traveling Salesperson Problem
Authors:

Tianyu Liang, Zhize Wu, Matthias Thürer, Markus Wagner and Thomas Weise
Abstract: The Traveling Salesperson Problem (TSP) is one of the most well-known NP-hard optimization tasks. A randomized local search (RLS) is not a good approach for solving TSPs, as it quickly gets stuck at local optima. FRLS, the same algorithm with Frequency Fitness Assignment plugged in, has been shown to be able to solve many more TSP instances to optimality. However, it was also assumed that its performance will decline if an instance has a large number M of different possible objective values. How can we explore these more or less obvious algorithm properties in a controlled fashion, if determining the number #L of local optima or the size BL of their joint basins of attraction as well as the feature M are NP-hard problems themselves? By creating TSP instances with a small number of cities for which we can actually know these features! We develop a deterministic construction method for creating TSP instances with rising numbers M and a sampling based approach for the other features. We determine all the instance features exactly and can clearly confirm the obvious (in the case of RLS) or previously suspected (in the case of FRLS) properties of the algorithms. Furthermore, we show that even with small-scale instances, we can make interesting new findings, such as that local optima seemingly have little impact on the performance of FRLS.
Download
Paper Nr: 20
Title:

Separating the Yes- from the No-Instances in the Number Partitioning Problem
Authors:

Ruben Horn, Reitze Jansen, Okke van Eck and Daan van den Berg
Abstract: The (two-way) number partitioning problem (NPP) is a well known NP-complete decision problem in which a set of (positive) integers must be split in such a way that the sum of both resulting subsets is equal. However, its optimization problem variant is even harder, since the verification of partitions is only possible in polynomial time for instances which have a perfect partition. We investigate the distribution of instances that have and that do not have a perfect partition, and find that they are not randomly distributed in the instance space. Thus, the hardness of any given instance might be predictable to some extent. We demonstrate that it is possible to separate these two instance types visually using a linear time embedding into R2 for instances of the same template. Furthermore, we compare three greedy heuristic algorithms (greedy captains, greedy coach, and greedy tyrant) and their difference to the solution from an exact branch-and-bound (BB) algorithm.
Download
Paper Nr: 25
Title:

Control of Biohybrid Actuators Using Neuroevolution
Authors:

Hugo Alcaraz-Herrera, Michail-Antisthenis Tsompanas, Igor Balaz and Andrew Adamatzky
Abstract: In medical-related tasks, soft robots can perform better than conventional robots because of their compliant building materials and the movements they are able perform. However, designing soft robot controllers is not an easy task, due to the non-linear properties of their materials. A formal design process is needed since human expertise to design such controllers is not sufficiently effective. The present research proposes neuroevolution-based algorithms as the core mechanism to automatically generate controllers for biohybrid actuators that can be used on future medical devices, such as a catheter that will deliver drugs. The controllers generated by methodologies based on Neuroevolution of Augmenting Topologies (NEAT) and Hypercube-based NEAT (HyperNEAT) are compared against the ones generated by a standard genetic algorithm (SGA). In specific, the metrics considered are the maximum displacement in upward bending movement and the robustness to control different biohybrid actuator morphologies without redesigning the control strategy. Results indicate that the neuroevolution-based algorithms produce better-suited controllers than the SGA. In particular, NEAT designed the best controllers, achieving up to 25% higher displacement when compared with SGA-produced specialised controllers trained over a single morphology and 23% when compared with general-purpose controllers trained over a set of morphologies.
Download
Paper Nr: 26
Title:

Fitness Histograms of Expert-Defined Problem Classes in Fitness Landscape Classification
Authors:

Vojtěch Uher and Pavel Krömer
Abstract: Various metaheuristic algorithms can be employed to find optimal or sub-optimal solutions for different problems. A fitness landscape (FL) is an abstraction representing a specific optimization task. Exploratory landscape analysis (ELA) approximates the FL by estimating its features from a limited number of random solution samples. Such ELA features help in estimating the properties of the FL and ultimately aid the selection of suitable optimization algorithms for problems with certain FL characteristics. This paper proposes using a normalized histogram of fitness values as a simple statistical feature vector for representing FLs. These histograms are classified using various classifiers to evaluate their effectiveness in representing different problems. The study focuses on 24 single-objective benchmark problems, grouped into five expert-defined classes. The performance of several classifiers is compared across different problem dimensions and sample sizes, emphasizing the impact of different sampling strategies and the number of histogram bins. The findings highlight the robustness of histogram representation and reveal promising experimental setups and relationships.
Download
Paper Nr: 29
Title:

A Modified Preference-Based Hypervolume Indicator for Interactive Evolutionary Multiobjective Optimization Methods
Authors:

MaoMao Liang, Babooshka Shavazipour, Bhupinder Saini, Michael Emmerich and Kaisa Miettinen
Abstract: Various interactive evolutionary multiobjective optimization methods have been proposed in the literature for problems with multiple, conflicting objective functions. In these methods, a decision maker, who is a domain expert, iteratively provides preference information to guide the solution process while gaining insight into the problem. To compare interactive evolutionary multiobjective optimization methods, a preference-based hypervolume indicator (PHI) has been proposed to quantify the performance of the methods. PHI was the first indicator designed based on some desirable properties of indicators for interactive evolutionary multiobjective optimization methods. However, it has some shortcomings, such as excluding some potentially interesting solutions and being limited to consider a reference point as a type of preference information. In this paper, a modified indicator called PHI+ is proposed to address the mentioned drawbacks. PHI+ modifies the region of interest in PHI. While PHI is directed at methods where a decision maker provides preference information in the form of a reference point, PHI+ is applicable for methods that utilize desirable ranges of objective function values as preference information. Therefore, PHI+ is the first indicator that can handle preference information provided as desirable ranges when evaluating interactive methods. Experimental results show that PHI+ can also better distinguish differences in the performance of interactive evolutionary multiobjective optimization methods.
Download
Paper Nr: 36
Title:

Grammatical Evolution of Synthesizable Finite State Machine-Based Behavioural Level Hardware Description Language Codes
Authors:

Bilal Majeed, Jack McEllin, Rajkumar Sarma, Ayman Youssef, Douglas Mota Dias and Conor Ryan
Abstract: The importance of designing efficient and accurate digital circuits has grown due to the widespread use of wearable, ready-made, and custom electronic products. These digital circuits are typically sequential and designed using synthesizable Hardware Description Languages (HDLs) that can be translated into hardware. A large part of this exercise comprises designing synthesizable HDLs for sequential circuits, which are challenging to design and test, thus requiring much time for the engineers to construct them. This paper proposes using Grammatical Evolution (GE) to evolve the synthesizable HDL codes for sequential circuits on the behavioural or algorithmic level in SystemVerilog. The codes evolved in this work are of JK-Flip Flop (JK-FF), 3-bit Up-Down Counter (UDC), and 8-Floor Elevator (8FE), all from the perspective of Finite State Machines (FSMs). Circuits such as 3-bit UDC and JK-FF are the basic blocks in many circuits in the industry, while 8FE is a real-life example mimicking 3-bit UDC but with a few practical exceptions. All circuits are evolved using two types of grammars. The G1 Type Grammar evolves parts of the code, while the more powerful and generic G2 Type Grammar evolves the full HDL codes for these sequential circuits. The GE-based evolution of these synthesizable design codes using both types of grammar achieves a success rate of over 86% for all circuits. Moreover, all the solution circuits evolved with the best achieved success score under the respective hyper-parameter settings for G1 and G2 Type Grammar are synthesised, and their synthesis reports are compared against the synthesis reports of Gold (human-designed) circuits. The synthesis is performed using Cadence Genus at Generic Process Design Kit (GPDK) 45, 90, and 180 nm technology libraries. The synthesis results show that machine-generated designs often perform as well as or better than human-designed circuits.
Download
Paper Nr: 41
Title:

The Performance of Frequency Fitness Assignment on JSSP for Different Problem Instance Sizes
Authors:

Iris Pijning, Levi Koppenhol, Danny Dijkzeul, Nielis Brouwer, Sarah L. Thomson and Daan van den Berg
Abstract: The Frequency Fitness Assignment (FFA) method steers evolutionary algorithms by objective rareness instead of objective goodness. Does this mean the size of the combinatorial search space influences its performance when compared to more traditional evolutionary algorithms? Our results suggest it does. To address to which extent the search space size matters for the effectiveness of the FFA-principle, we compare the algorithms on 420 Job Shop Scheduling Problem (JSSP) instances systematically generated in gridwise sizes. The comparison of the FFA-hillclimber and the standard hillclimber is done in both EQ setting, accepting equally good (or fitness-frequent) solutions, and NOEQ setting, only accepting improvement. FFA-hillclimbers are more successful than standard hillclimbers on smaller problem instances, but not on larger ones. It seems that the ratio between jobs and machines, influences the success of the respective algorithms for fixed computational budgets.
Download
Paper Nr: 49
Title:

Fractal Analysis of the Subset-Sum Problem
Authors:

Ruben Horn, Daan van den Berg and Pieter Adriaans
Abstract: It is known that the hardness of the (two-way) number partitioning problem (NPP) variant of the subset-sum problem (SSP) depends on the number and distribution of bits in the set of numbers, but beyond this, it is relatively unexplained for the SSP itself. Thus, we look at the solution space of various problem instances of the SSP using fractal analysis. Two methods to determine the dimension are used. Plotting the fractal dimension over the range and distributions of informational bits, we find that it is correlated with this linear model and also moderately correlated to the hardness of the NPP. This suggests that fractal analysis might be a useful tool in understanding the complexity of combinatorial problems and, we believe, may help further understand the hardness in NP. Finally, we introduce a thought experiment derived from the famous Hilbert’s hotel, which we call Hilbert’s hotel with elevators, to intuitively illustrate how the complexity of the solutions space and the computational hardness may relate across combinatorial problems.
Download
Paper Nr: 50
Title:

Genetic Programming for 5×5 Matrix Multiplication
Authors:

Rik Timmer, Jesse Kommandeur, Jonathan Koutstaal, Eric S. Fraga and Daan van den Berg
Abstract: Using genetic programming, we fail in evolving an algorithm that correctly multiplies two 5×5 matrices. We do make progress on the issue however, identifying an experimental setting that could potentially lead to such algorithm which until now, has not been successfully done. We discuss earlier work, experimental results and possible ways forward.
Download
Paper Nr: 60
Title:

A Vector Autoregression-Based Algorithm for Dynamic Many-Objective Optimization Problems
Authors:

Kalthoum Karkazan, Haluk Rahmi Topcuoglu and Shaaban Sahmoud
Abstract: Dynamic Many-Objective Optimization Problems (DMaOPs) represent a significant challenge due to their inherent dynamism and the presence of a large number of objectives. In addressing this complexity, this paper proposes a new prediction-based strategy tailored to managing detected changes in such problems, which is one of the first attempts to address the DMaOPs. Our proposed algorithm constructs a Vector Autoregressive (VAR) model within a dimensionality-reduced space. This model effectively captures the mutual relationships among decision variables and enables an accurate prediction of the initial positions for the evolving solutions in dynamic environments. To accelerate the convergence process, the algorithm demonstrates adaptability by responding multiple times to the same detected change. In our empirical study, the performance of the proposed algorithm is evaluated using four selected test problems from various benchmarks. Our proposed approach shows competitive results compared to the other algorithms in most test instances.
Download
Paper Nr: 66
Title:

Tangled Program Graphs with Indexed Memory in Control Tasks with Short Time Dependencies
Authors:

Tanya Djavaherpour, Ali Naqvi and Stephen Kelly
Abstract: This paper addresses the challenges of shared temporal memory for evolutionary reinforcement learning agents in partially observable control tasks with short time dependencies. Tangled Program Graphs (TPG) is a genetic programming framework which has been widely studied in memory intensive tasks from video games, time series forecasting, and predictive control domains. In this study, we aim to improve external indexed memory usage in TPG by minimizing the impact of destructive agents during cultural transmission. We test various memory resetting strategies—per agent, per episode, and a no-memory control group—and evaluate their effectiveness in mitigating destructive effects while maintaining performance. Results from Acrobot, Pendulum, and CartPole tasks show that resetting memory more often can significantly boost TPG performance while preserving computational efficiency. These findings highlight the importance of memory management in Reinforcement Learning (RL) and suggest opportunities for further optimization for more complex visual RL environments, including adaptive memory resetting and evolved probabilistic memory operations.
Download
Paper Nr: 68
Title:

Using Secondary Inherited Characteristics During Reproductive Choice to Replicate Allopatric Speciation
Authors:

Gary B. Parker and Jay B. Nash
Abstract: The goal of this research is to create an environment where we can use evolutionary computation (EC) with separate chromosomes in independent agents to replicate allopatric speciation, the process in which a species diverges into two distinct, reproductively separate species based on geographic isolation. In previous work done by Parker and Edwards, an environment and genetic algorithm were developed to simulate this type of speciation. However, some aspects of the developed environment could be considered a priori knowledge. This paper details a new system where agents do not have access to what we will refer to as “primary characteristics” or characteristics that directly affect agent fitness and success. Characteristics that have no bearing on agent fitness, referred to as "secondary characteristics", are solely used by the agents to determine reproductive choice. This has a variety of benefits, most clearly that no a priori knowledge is used in the system. This can result in two species that have identical primary, fitness affecting characteristics, but are reproductively separated due to secondary, arbitrary characteristics. The reduction of knowledge available to the agents during reproduction makes the system a better match for biological systems, but was expected to cause an increase in cross species hybrids. However, it led to a higher degree of speciation than previous work on the topic. As a result, this system improves upon the previous method used to simulate the natural process of allopatric speciation via a genetic algorithm by reducing a priori knowledge and increasing efficacy.
Download
Paper Nr: 78
Title:

Trade Data Harmonization: A Multi-Objective Optimization Approach for Subcategory Alignment and Volume Optimization
Authors:

Himadri Sikhar Khargharia, Sid Shakya and Dymitr Ruta
Abstract: Aligning trade data from disparate sources poses challenges due to volume disparities and category naming variations. This study aims to harmonize subcategories from a secondary dataset with those of a primary dataset, focusing on aligning the number and combined volumes of subcategories. We employ a multi-objective optimization approach using Non-dominated Sorting Genetic Algorithm II (NSGA-II) to facilitate trade-off assessments and decision-making via Pareto fronts. NSGA-II’s performance is compared with single-objective optimization techniques, including Genetic Algorithm (GA), Population-based Incremental Learning (PBIL), Distribution Estimation using Markov Random Field (DEUM), and Simulated Annealing (SA). The comparative analysis highlights NSGA-II’s efficacy in managing trade data complexities and achieving optimal solutions, demonstrating the effectiveness of meta-heuristic approaches in this context.
Download
Paper Nr: 79
Title:

Automated Design of Routing Policies for the Dynamic Electric Vehicle Routing Problem with Genetic Programming
Authors:

Marko Durasevic and Francisco Javier Gil Gala
Abstract: The dynamic electric vehicle routing problem (EVRP) with time windows (DEVRPTW) is an important combinatorial optimisation problem gaining on importance in today’s world due to environmental concern and the requirement of dealing with dynamic and uncertain environments. This represents a problem when solving such problems, as standard improvement based heuristics cannot be used to solve them, since not all information about the problem is known beforehand. This provides a motivation for applying improvement based heuristics, most notably routing policies (RPs), which determine only the next decision that needs to be performed an execute it. Since these RPs do not construct the schedule in advance, they can easily react to any changes in the problem. However, RPs are difficult to design, which motivated the use of genetic programming (GP) in automatically designing such heuristics for various problems. Unfortunately, in the context of EVRP only static problems were considered. This study investigates the application of GP to automatically design new RPs for DEVRPTW under different levels of dynamism. The results demonstrate that GP performs well for certain levels of dynamism, although as it increases it is more difficult to perform good decisions.
Download
Paper Nr: 89
Title:

ETA-Based Secondary Conflict-Free Local Path Replanning for Air Logistics Transportation
Authors:

Yuan Zheng, Jie Cheng and Chenglong Li
Abstract: Air logistics transportation has become one of the most promising markets for the civil drone industry. However, the large flow, high density, and complex environmental characteristics of urban scenes make in-flight path replanning very challenging, especially when considering the temporal constraints of predetermined 4D waypoints. Existing in-flight replanning methods fail to consider the implications of conflict resolution on subsequent flight paths, potentially leading to secondary conflicts. In this paper, we aim to overcome this limitation by proposing an ETA-based, secondary conflict-free 4D local path replanning method. Specifically, we first integrate the Estimated Time of Arrival (ETA) into the Particle Swarm Optimization (PSO) evaluation function to avoid secondary conflicts. Additionally, by integrating the Artificial Potential Field (APF) with PSO and defining a new update formula, our method not only avoids local optima but also accelerates the algorithm's convergence. As demonstrated by the numerical simulation results, our method effectively resolves conflicts with twice the safety margin, while maintaining adherence to the original flight plan, thus mitigating the risk of secondary conflicts in urban very-low-level (VLL) airspace.
Paper Nr: 21
Title:

Automated Design of a Genetic Algorithm for Image Segmentation Using the Iterated Local Search
Authors:

Thambo Nyathi
Abstract: Image thresholding is a fundamental technique used in image processing for segmentation. This is the process of determining optimal thresholds for an image. When the number of thresholds exceeds two, that is, multilevel thresholding, the computational complexity of the process increases exponentially. This has resulted in the popularity of addressing this problem by using metaheuristic methods. However, metaheuristics are pa-rameterised and their effectiveness depends on their configuration, which is often performed manually using an iterative trial-and-error approach. This leads to less effective designs that yield less accurate thresholds and longer design times. This study proposes using an Iterated Local Search to configure a low-level metaheuristic, namely, a Genetic Algorithm(GA), to solve the multilevel threshold problem. The performance of the proposed approach was compared with that of a manually designed standard GA approach, and evaluated using T2 weighted Magnetic Resonance images of the brain. Furthermore, the proposed approach is compared with two other metaheuristic algorithms for the same problem. The results showed that the automatically designed genetic algorithm significantly outperformed the standard genetic algorithm approach and the other two algorithms on the set objective function. Although the runtimes were higher than those of the manual design approach, better thresholds were obtained.
Download
Paper Nr: 37
Title:

Educational Evolutionary Neural Architecture Search for Time Series Prediction
Authors:

Martha Isabel Escalona-Llaguno and Sergio M. Sarmiento-Rosales
Abstract: This paper presents a sophisticated tool designed to teach Evolutionary Neural Architecture Search (ENAS) in time series analysis. The goal is to create a flexible and modular algorithm that helps to understand evolutionary algorithms in the context of neural architecture optimization. The tool allows parameter tuning and search space exploration. Its initial setup can include a population size of 20 individuals, spanning 5 generations, with an elitism rate of 20% and crossover and mutation probabilities set to 90% and 10%, respectively. However, these hyperparameters are completely modular, so that the effect on the algorithm can be studied. The parameter ranges from 1 to 20 for neurons and delays. The neural networks are extensively trained using the MATLAB narnet function and the PJM hourly energy consumption dataset, which is split into 70% for training, 15% for validation, and 15% for testing. The goal is to maximize the correlation coefficient r obtained from the test dataset. This approach offers an interactive platform for experimentation and learning about the evolutionary process of neural architectures, thus improving the understanding of evolutionary algorithms applied to Neural Architecture Search (NAS). Our experiments show efficiency due to the limited search space and the absence of specialized hardware requirements such as GPU, making it accessible and practical for educational and research environments. Using only an AMD Ryzen 7 7800X3D CPU, all architectures within the search space were trained in less than 3 hours, demonstrating the agility of ENAS in various configurations and its effectiveness in facilitating practical understanding of the evolutionary process in NAS. All datasets, tutorials and essential codes to apply this work are publicly accessible at the following link: https://github.com/SergioSarmientoRosales/ENAS-Time-Series.
Download
Paper Nr: 38
Title:

Surrogate Modeling for Efficient Evolutionary Multi-Objective Neural Architecture Search in Super Resolution Image Restoration
Authors:

Sergio Sarmiento-Rosales, Jesús Leopoldo Llano García, Jesús Guillermo Falcón-Cardona, Raúl Monroy, Manuel Iván Casillas del Llano and Víctor Adrián Sosa-Hernández
Abstract: Fully training each candidate architecture generated during the Neural Architecture Search (NAS) process is computationally expensive. To overcome this issue, surrogate models approximate the performance of a Deep Neural Network (DNN), considerably reducing the computational cost and, thus, democratizing the utilization of NAS techniques. This paper proposes an XGBoost-based surrogate model to predict the Peak-Signal-to-Noise Ratio (PSNR) of DNNs for Super-Resolution Image Restoration (SRIR) tasks. In addition to maximizing PSNR, we also focus on minimizing the number of learnable parameters and the total number of floating-point operations. We use the Non-dominated Sorting Genetic Algorithm III (NSGA-III) to tackle this three-objective optimization NAS problem. Our experimental results indicate that NSGA-III using our XGBoost-based surrogate model is significantly faster than using full or partial training of the candidate architectures. Moreover, some selected architectures are comparable in quality to those found using partial training. Consequently, our XGBoost-based surrogate model offers a promising approach to accelerate the automatic design of architectures for SRIR, particularly in resource-constrained environments, decreasing computing time.
Download
Paper Nr: 64
Title:

Step Size Control in Evolutionary Algorithms for Neural Architecture Search
Authors:

Christian Nieber, Douglas Mota Dias, Enrique Naredo Garcia and Conor Ryan
Abstract: This work examines how evolutionary Neural Architecture Search (NAS) algorithms can be improved by controlling the step size of the mutation of numerical parameters. The proposed NAS algorithms are based on F-DENSER, a variation of Dynamic Structured Grammatical Evolution (DSGE). Overall, a (1+5) Evolutionary Strategy is used. Two methods of controlling the step size of mutations of numeric values are compared to Random Search and F-DENSER: Decay of the step size over time and adaptive step size for mutations. The search for lightweight, LeNet-like CNN architectures for MNIST classification is used as a benchmark, optimizing for both accuracy and small architectures. An architecture is described by about 30 evolvable parameters. Experiments show that with step size control, convergence is faster, better performing neural architectures are found on average, and with lower variance. The smallest architecture found during the experiments reached an accuracy of 98.8% on MNIST with only 5,450 free parameters, compared to the 62,158 parameters of LeNet-5.
Download
Paper Nr: 71
Title:

Modelling and Simulation of Adaptive Multi-Agent Systems with Stochastic Nets-within-Nets
Authors:

Michael Köhler-Bußmeier and Lorenzo Capra
Abstract: This study centers on self-adapting multi-agent systems modeled utilizing the SONAR framework. Our key focus is on forecasting the costs and benefits of adaptation during execution within the MAPE loop (monitor, analyse, plan, and execute). Analyzing these adaptation processes is intricate due to SONAR enabling second-order activities, such as structural adaptation involving agent interaction protocols or the organizational network itself. We forecast these dynamic processes using a stochastic run-time model (e.g., the environment has a stochastic representation). Since SONAR is conceptualized with HORNETS (a nets-within-nets formalism), we necessitate “probabilistic” HORNETS. To illustrate our approach’s effectiveness, we showcase a small case study of a self-modifying MAS organization and provide an analysis of adaptation dynamics.
Download
Paper Nr: 72
Title:

L-SAGA: A Learning Hyper-Heuristic Architecture for the Permutation Flow-Shop Problem
Authors:

Younes Boukacem, Hatem M. Abdelmoumen, Hodhaifa Benouaklil, Samy Ghebache, Boualem Hamroune, Mohammed Tirichine, Nassim Ameur and Malika Bessedik
Abstract: The permutation flow-shop problem or PFSP consists in finding the optimal launching sequence of jobs to be sequentially executed along a chain of machines, each job having different execution times for each machine, in order to minimize the total completion time. As an NP-hard problem, PFSP has significant applications in large-scale industries. In this paper we present L-SAGA, a generative hyper-heuristic designed for finding optimal to sub-optimal solutions for the PFSP. L-SAGA combines a high level simulated annealing with a learning component and a low level PFSP adapted genetic algorithm. The performed tests on various benchmarks indicate that, while our method had competitive results on some small and medium size benchmarks thus showing interesting potential, it still requires further improvement to be fully competitive on larger and more complex benchmarks.
Download
Paper Nr: 76
Title:

Open Source Evolutionary Computation with Chips-n-Salsa
Authors:

Vincent A. Cicirello
Abstract: When it was first introduced, the Chips-n-Salsa Java library provided stochastic local search and related algorithms, with a focus on self-adaptation and parallel execution. For the past four years, we expanded its scope to include evolutionary computation. This paper concerns the evolutionary algorithms that Chips-n-Salsa now provides, which includes multiple evolutionary models, common problem representations, a wide range of mutation and crossover operators, and a variety of benchmark problems. Well-defined Java interfaces enable easily integrating custom representations and evolutionary operators, as well as defining optimization problems. Chips-n-Salsa’s evolutionary algorithms include implementations with adaptive mutation and crossover rates, as well as both sequential and parallel execution. Source code is maintained on GitHub, and immutable artifacts are regularly published to the Maven Central Repository to enable easily importing into projects for reproducible builds. Effective development processes such as test-driven development, as well as a variety of static analysis tools help ensure code quality.
Download
Paper Nr: 90
Title:

Improving the Performance of Genetic Algorithms for Combinatorial Optimization Using Machine Learning for Knowledge Transfer
Authors:

George Mweshi and Nelishia Pillay
Abstract: This study investigates improving the performance of genetic algorithms applied to the solution space using machine learning and knowledge transfer. Genetic algorithms are powerful techniques that have been successfully used to explore various problem spaces, such as solution space, program space, and heuristic space. Recently, researchers have found that transferring knowledge between these spaces can significantly enhance the quality of solutions and reduce computational costs. While this transfer of knowledge works well in program and heuristic spaces due to their indirect nature, it is more challenging in the solution space. This is because each problem in the solution space has its own unique representation, making it difficult to transfer knowledge effectively. This study explores how machine learning, specifically using classifiers, can help bridge this gap and facilitate knowledge transfer between different solution spaces. We train two classifiers, namely, Support Vector Machines and Random Forests, using data consisting of fitness landscape measures from a source genetic algorithm to determine if a chromosome is a local optimum or not. This information is then used during the execution of a target genetic algorithm to identify and remove potential local optima from the population. We tested this approach on two challenging optimization problems: the examination timetabling problem (ETP) and the capacitated vehicle routing problem (CVRP). Our results show that this method provides statistically significant improvements over genetic algorithms that do not use knowledge transfer, both in terms of solution quality and computational efficiency. Moreover, we found that random forests were more effective than support vector machines for transferring knowledge between the source and target genetic algorithms.
Download
Paper Nr: 91
Title:

Working on the Structural Components of Evolutionary Approaches
Authors:

Alexandros Tzanetos and Jakub Kůdela
Abstract: Several researchers have turned their attention to the structural components of Evolutionary Computation-and Swarm Intelligence-oriented approaches. This direction offers various opportunities, such as developing automatic design and configuration frameworks and integrating operators and mechanisms addressing known limitations. This work lists recent operators and discusses promising mechanisms found in existing nature-inspired approaches. It also discusses how these algorithmic components can be integrated into modular frameworks and how they can be assessed and benchmarked. The work aims to emphasize the importance of the research direction about nature-inspired mechanisms and operators in the Evolutionary Computation field.
Download