ECTA 2022 Abstracts

Full Papers

Paper Nr:	3
Title:	Cluster-based Diversity Over-sampling: A Density and Diversity Oriented Synthetic Over-sampling for Imbalanced Data
Authors:	Yuxuan Yang, Hadi A. Khorshidi and Uwe Aickelin
Abstract:	In many real-life classification tasks, the issue of imbalanced data is commonly observed. The workings of mainstream machine learning algorithms typically assume the classes amongst underlying datasets are relatively well-balanced. The failure of this assumption can lead to a biased representation of the models’ performance. This has encouraged the incorporation of re-sampling techniques to generate more balanced datasets. However, mainstream re-sampling methods fail to account for the distribution of minority data and the diversity within generated instances. Therefore, in this paper, we propose a data-generation algorithm, Cluster-based Diversity Over-sampling (CDO), to consider minority instance distribution during the process of data generation. Diversity optimisation is utilised to promote diversity within the generated data. We have conducted extensive experiments on synthetic and real-world datasets to evaluate the performance of CDO in comparison with SMOTE-based and diversity-based methods (DADO, DIWO, BL-SMOTE, DB-SMOTE, and MAHAKIL). The experiments show the superiority of CDO.
Download

Paper Nr:	4
Title:	Making Hard(Er) Bechmark Test Functions
Authors:	Dante Niewenhuis and Daan van Den Berg
Abstract:	This paper is an exploration into the hardness and evolvability of default benchmark test functions. Some very well-known traditional two-dimensional continuous benchmark test functions are evolutionarily modified to challenge the performance of the plant propagation algorithm (PPA), a crossoverless evolutionary method. For each traditional benchmark function, only its scalar constant parameters are mutated, but the effect on PPA’s performance is nonetheless enormous, both measured in objective deficiency and in the success rate. Thereby, a traditional benchmark functions’ hardness can thereby indeed be evolutionarily increased, and an especially interesting observation is that the evolutionary processes seem to follow one of three specific patterns: global minimum narrowing, increase in ruggedness, or concave-to-convex inversion.
Download

Paper Nr:	12
Title:	Approaches for Rule Discovery in a Learning Classifier System
Authors:	Michael Heider, Helena Stegherr, David Pätzel, Roman Sraj, Jonathan Wurth, Benedikt Volger and Jörg Hähner
Abstract:	To fill the increasing demand for explanations of decisions made by automated prediction systems, machine learning (ML) techniques that produce inherently transparent models are directly suited. Learning Classifier Systems (LCSs), a family of rule-based learners, produce transparent models by design. However, the usefulness of such models, both for predictions and analyses, heavily depends on the placement and selection of rules (combined constituting the ML task of model selection). In this paper, we investigate a variety of techniques to efficiently place good rules within the search space based on their local prediction errors as well as their generality. This investigation is done within a specific LCS, named SupRB, where the placement of rules and the selection of good subsets of rules are strictly separated in contrast to other LCSs where these tasks sometimes blend. We compare a Random Search, (1,λ)-ES and three Novelty Search variants. We find that there is a definitive need to guide the search based on some sensible criteria, i.e. error and generality, rather than just placing rules randomly and selecting better performing ones but also find that Novelty Search variants do not beat the easier to understand (1,λ)-ES.
Download

Paper Nr:	15
Title:	Towards Phenotypic Duplication and Inversion in Cartesian Genetic Programming
Authors:	Roman Kalkreuth
Abstract:	The search performance of Cartesian Genetic Programming (CGP) relies to a large extent on the sole use of genotypic point mutation in combination with extremely large redundant genotypes. Over the last years, steps have been taken to extend CGP's variation mechanisms by the introduction of advanced methods for recombination and mutation. One branch of these contributions addresses phenotypic variation in CGP. Besides demonstrating the effectiveness of various phenotypic search operators, corresponding analytical experiments backed evidence that phenotypic variation is another approach for achieving effective evolutionary-driven search in CGP. However, recent comparative studies have demonstrated the limitations of phenotypic recombination in Boolean function learning and highlighted the effectiveness of the mutation-only approach. Especially the use of the 1+λ selection strategy with neutral genetic drift has been found superior to recombination-based approaches in this problem domain. Therefore, in this work, we further explore phenotypic mutation in CGP by the introduction and evaluation of two phenotypic mutation operators that are inspired by chromosomal rearrangement. Our initial findings show that our proposed methods can significantly improve the search performance of CGP on various single- and multiple-output Boolean function benchmarks by reducing the number of fitness evaluations needed to find the ideal solution.
Download

Short Papers

Paper Nr:	1
Title:	A Rolling Horizon Approach for the Dynamic Scheduling of Flying Taxis
Authors:	Sana Ikli
Abstract:	Flying taxis are a promising alternative to ground transportation to alleviate the congestion problem in metropolitan cities. The launching of the first air taxis is expected in the next few years. The companies operating air taxi services will deal with several real-time problems. Such problems include the scheduling of flying taxi operations, and the battery charging management as well as other maintenance issues. In this work, we are interested in the dynamic scheduling of flying taxis, so as to serve a set of clients. This problem is on the one hand under-explored in the literature, as we will show in the next sections, and on the other hand, it is more realistic than the static case. We present in this work a rolling-horizon approach, integrated with three heuristics, to solve the dynamic scheduling of flying taxis. We also construct new realistic and difficult instances to test and validate our algorithms. Our instances and implementations are publicly available for the scientific community online. Finally, we perform a computational study on our generated instances to show the benefits and the limits of each heuristic.
Download

Paper Nr:	5
Title:	New Evolutionary Selection Operators for Snake Optimizer
Authors:	Ruba A. Khurma, Moutaz Alazab, J. J. Merelo and Pedro A. Castillo
Abstract:	Evolutionary algorithms (EA) adopt a Darwinian theory which is known as ”survival of the fittest”. Snake Optimizer (SO) is a recently developed swarm algorithm that inherits the selection principle in its structure. This is applied by selecting the fittest solutions and using them in deriving new solutions for the next iterations of the algorithm. However, this makes the algorithm biased towards the highly fitted solutions in the search space, which affects the diversity of the SO algorithm. This paper proposes new selection operators to be integrated with the SO algorithm and replaces the global best operator. Four SO variations are investigated by individually integrating four different selection operators: SO-roulettewheel, SO-tournament, SO-linearrank, and SO-exponentialrank. The performance of the proposed SO variations is evaluated. The experiments show that the selection operators have a great influence on the performance of the SO algorithm. Finally, a parameter analysis of the SO variations is investigated.
Download

Paper Nr:	8
Title:	Universally Hard Hamiltonian Cycle Problem Instances
Authors:	Joeri Sleegers, Sarah L. Thomson and Daan van Den Berg
Abstract:	In 2021, evolutionary algorithms found the hardest-known yes and no instances for the Hamiltonian cycle problem. These instances, which show regularity patterns, require a very high number of recursions for the best exact backtracking algorithm (Vandegriend-Culberson), but don’t show up in large randomized instance ensembles. In this paper, we will demonstrate that these evolutionarily found instances of the Hamiltonian cycle problem are hard for all major backtracking algorithms, not just the Vandegriend-Culberson. We compare performance of these six algorithms on an ensemble of 91,000 randomized instances plus the evolutionarily found instances. These results present a first glance at universal hardness for this NP-complete problem. Algorithms, source code, and input data are all publicly supplied to the community.
Download

Paper Nr:	9
Title:	Improving Digital Circuit Synthesis of Complex Functions using Binary Weighted Fitness and Variable Mutation Rate in Cartesian Genetic Programming
Authors:	Prashanth H. C. and Madhav Rao
Abstract:	Cartesian Genetic Programming (CGP) is regularly applied to synthesize and realize digital circuits for small arithmetic and digital-logic functions. CGP benefits in obtaining hardware-efficient circuits through its heuristic search-space exploration, which is hard to reach in a rule-based synthesis process. However, the traditional CGP configuration has limitations in evolving large and complex circuits, requiring a large number of generations. High computation time and energy requirements hinder its usage from evolving complex digital circuits. This paper investigates and demonstrates the desired modifications to existing CGP in the form of Binary Weighted Fitness (BwF) and exponentially varying mutation rate (eVar) to evolve functionally correct solutions extremely fast. The benefits are demonstrated for the basic non-linear power functions and are validated for usage in activation functions which are otherwise difficult to realize. Additionally, 12 different CGP configurations with changes in mutation scheme and evolutionary strategy were also investigated for the power functions. A comparison with the benefits of BwF and eVar adopted CGP over the traditional CGP methods is presented and discussed.
Download

Paper Nr:	10
Title:	On using Authorization Traces to Support Role Mining with Evolutionary Algorithms
Authors:	Simon Anderer, Alpay Sahin, Bernd Scheuermann and Sanaz Mostaghim
Abstract:	To protect the security of IT systems of companies and organizations, Role Based Access Control is a widely used concept. The corresponding optimization problem, the Role Mining Problem, which consists of finding an optimum set of roles based on a given assignment of permissions to users was shown to be NP-complete and evolutionary algorithms have demonstrated to be a promising solution strategy. It is usually assumed that the assignment of permissions to users, used for role mining, reflects exactly the permissions needed by a user to perform the given tasks. However, considering enterprise resource planning systems (ERP) in real-world use cases, permission-to-user assignments are often outdated or, if at all, only partially available. In contrast, trace data, which records the behavior of users in ERP systems, is easily available. This paper describes and analyzes the different data types and sources provided by ERP systems. Furthermore, it is examined, if this data is suitable to create an initial permission-to-user assignment or to enhance the quality of a yet existing one. For this purpose, different trace-data-based methods are introduced. In the context of an industry-related research project, ERP data of two different companies is analyzed and used to evaluate the presented methods.
Download

Paper Nr:	14
Title:	Adaptive Combination of a Genetic Algorithm and Novelty Search for Deep Neuroevolution
Authors:	Eyal Segal and Moshe Sipper
Abstract:	Evolutionary Computation (EC) has been shown to be able to quickly train Deep Artificial Neural Networks (DNNs) to solve Reinforcement Learning (RL) problems. While a Genetic Algorithm (GA) is well-suited for exploiting reward functions that are neither deceptive nor sparse, it struggles when the reward function is either of those. To that end, Novelty Search (NS) has been shown to be able to outperform gradient-following optimizers in some cases, while under-performing in others. We propose a new algorithm: Explore-Exploit g-Adaptive Learner (E 2 gAL, or EyAL). By preserving a dynamically-sized niche of novelty-seeking agents, the algorithm manages to maintain population diversity, exploiting the reward signal when possible and exploring otherwise. The algorithm combines both the exploitation power of a GA and the exploration power of NS, while maintaining their simplicity and elegance. Our experiments show that EyAL outperforms NS in most scenarios, while being on par with a GA—and in some scenarios it can outperform both. EyAL also allows the substitution of the exploiting component (GA) and the exploring component (NS) with other algorithms, e.g., Evolution Strategy and Surprise Search, thus opening the door for future research.
Download

Paper Nr:	16
Title:	Towards Rigorous Foundations for Metaheuristic Research
Authors:	Thimershen Achary, Anban W. Pillay and Edgar Jembere
Abstract:	Several authors have recently pointed to a crisis within the metaheuristic research field, particularly the proliferation of metaphor-inspired metaheuristics. Common problems identified include using non-standard terminology, poor experimental practices, and, most importantly, the introduction of purportedly new algorithms that are only superficially different from existing ones. In this paper, we argue that although metaphors may be good sources of inspiration and creativity, being the only reason for publication is insufficient. Instead, adopting a formal, mathematically sound representation of metaheuristics is a valuable path to follow. We believe this will lead to more insightful research.
Download

Paper Nr:	2
Title:	Algorithms for Freight Train Scheduling
Authors:	Lucas Morais, Rodrigo Gonçalves, Alexandre Tazoniero and Fernando Gomide
Abstract:	This paper develops train scheduling algorithms for freight railroads using scheduling generation and genetic algorithms. First scheduling generation procedures developed in the realm of job shop manufacturing are tailored for freight railroad applications. The scheduling generation procedures are used to create feasible populations to start genetic algorithms. Next, it suggests a novel representation and encoding mechanism based on random keys and job permutation encoding inspired in flexible job shop scheduling. In freight railroads a common goal is to minimize overall maximum transit time, analogous to minimize the makespan in manufacturing systems. The genetic algorithms whose initial population are produced by the scheduling generation algorithms are compared with the random key-job permutation algorithm developed herein. An example rail line is used to evaluate the performance of the algorithms. The exact optimal solution for the example rail line, found using the OR Tools solver, is used as a baseline. The results suggest that all approaches may produce optimal solutions, but the random key-job permutation algorithm consistently performs best amongst the remaining ones.
Download

Paper Nr:	6
Title:	An Extremal Optimization Algorithm for Improving Gaussian Mixture Search
Authors:	Rodica I. Lung
Abstract:	Many standard clustering methods rely on optimizing a maximum likelihood function to reveal internal connections within data. While relying on the same model, alternative approaches may provide better insight into the division of data. This paper presents a new Gaussian mixture clustering approach that uses an extremal optimization algorithm to maximize the silhouette coefficient. The mean and covariance matrix of each component are evolved to maximize each cluster’s priors. Numerical experiments compare the performance of the expectation-maximization algorithm with the new approach on a set of synthetic and real-world data.
Download

Paper Nr:	7
Title:	Parameterising the SA-UNet using a Genetic Algorithm
Authors:	Mahsa Mahdinejad, Aidan Murphy, Patrick Healy and Conor Ryan
Abstract:	Deep learning is an excellent way for effectively addressing image processing, and several Neural Networks designs have been explored in this area. The Spatial Attention U-Net architecture, a version of the famous U-Net but which uses DropBlock and an attention block as well as the common U-Net convolutional blocks, is one notable example. Finding the best combination of hyper-parameters is expensive, time consuming and needs expert input. We show the genetic algorithm can be utilized to automatically determine the optimal combination of Spatial Attention U-Net hyper-parameters to train a model to solve a Retinal Blood Vessel Segmentation problem. Our new approach is able to find a model with an accuracy measure of 0.9855, an improvement from our previous experimentation which found a model with accuracy measure of 0.9751. Our new methods exhibit competitive performance with other state-of-the-art Retinal Blood Vessel Segmentation techniques.
Download

Paper Nr:	13
Title:	Strategic Solution Combination in Scatter Search for Quadratic Unconstrained Binary Optimization
Authors:	Justin Pauckert, Matthieu Parizy and Mayowa Ayodele
Abstract:	Quadratic Unconstrained Binary Optimization (QUBO) has become an important unifying model for formulating combinatorial optimization problems. Since QUBO is NP-hard, it is common to apply heuristics to them. Although a wider range of heuristics have been applied to QUBOs in the past, high performing QUBO solvers using specialized hardware have been of interest in more recent years. These solvers use local search algorithms such as Simulated Annealing, Quantum Annealing and Tabu Search to improve solution quality, but few also include global search methods to explore the solution space. Since research around global search for QUBO solvers is scarce, in this work we compare different variants implemented within a framework known as scatter search. We compare two global search methods, both used to generate new solutions from known solutions. The first method is path relinking which has been shown to deliver the best results in the literature for hard QUBO problems when used in scatter search. The second method is uniform crossover and is widely used in the field of Evolutionary Algorithms (EAs). We show that better performance can be achieved using path relinking compared to uniform crossover on knapsack problem instances.