ECTA 2021 Abstracts

Full Papers Short Papers
Full Papers
Paper Nr: 5
Title:

Improving Image Filters with Cartesian Genetic Programming
Authors:

Julien Biau, Dennis Wilson, Sylvain Cussat-Blanc and Hervé Luga
Abstract: The automatic construction of an image filter is a difficult task for which many recent machine learning methods have been proposed. However, these approaches, such as deep learning, do not allow for the filter to be understood, and they often replace existing filters designed by human engineers without building on this expertise. Genetic improvement offers an alternative approach to construct understandable image filter programs and to build them by improving existing systems. In this paper, we propose a method for genetic improvement of image filters using Cartesian Genetic Programming. We introduce two operators for genetic improvement which allow insertion and deletion of a node in the graph in order to quickly improve a given filter. These new operators are tested in three different datasets starting from published or engineered filters. We show that insertion and deletion operators improve the performance of CGP to produce newly adapted filters.
Download
Paper Nr: 9
Title:

An Effective Resistance based Genetic Algorithm for Community Detection
Authors:

Clara Pizzuti and Annalisa Socievole
Abstract: This work presents a new approach based on genetic algorithms (GAs) and the concept of effective resistance for detecting communities within an undirected graph. The method considers the equivalent electric network of the input graph, where edges are weighted with their effective resistance, a measure of electrical resistance between nodes, whose square root has been shown to be a Euclidean metric. The algorithm computes the similarity between nodes by using the effective resistance values and generates a weighted and sparse graph by adopting a thresholding sparsification strategy based on the nearest neighbors of each node. Experiments over synthetic and real-world networks demonstrate the effectiveness of our approach when compared to other benchmark methods.
Download
Paper Nr: 12
Title:

The Dynamic Role Mining Problem: Role Mining in Dynamically Changing Business Environments
Authors:

Simon Anderer, Tobias Kempter, Bernd Scheuermann and Sanaz Mostaghim
Abstract: Role Based Access Control is one of the most frequently used concepts for authorization management in today’s business landscapes. The corresponding optimization problem, the so-called Role Mining Problem (RMP), which was shown to be NP-complete, relies in finding a minimal set of roles and a corresponding assignment of those roles to users based on a static user permission assignment. However, as job duties, positions and responsibilities of users in companies constantly change, the corresponding user permission assignment is also subject to changes. Thus, the RMP in its present form has to be extended by dynamically occurring events, representing the changes in business environments. This paper defines the Dynamic Role Mining Problem (DynRMP) and presents the most relevant events from business perspective as well as their algorithmic implications for the RMP. Furthermore, several methods to include those events into the framework of an evolutionary algorithm, which is a suitable solution strategy for the RMP, are presented and evaluated in a range of experiments.
Download
Paper Nr: 15
Title:

Pyramid-Z: Evolving Hierarchical Specialists in Genetic Algorithms
Authors:

Atif Rafiq, Enrique Naredo, Meghana Kshirsagar and Conor Ryan
Abstract: Pyramid is a hierarchical approach to Evolutionary Computation that decomposes problems by first tackling simpler versions of them before scaling up to increasingly more difficult versions with smaller populations. Previous work showed that Pyramid was mostly as good or better than a standard GA approach, but that it did so with a fraction of individuals processed. Pyramid requires two key parameters to manage the problem complexity; (i) a threshold α as the performance bar, and (ii) β as the container with the maximum number of individuals to survive to the next level down. Pyramid-Z addressed the shortcomings of Pyramid by automating the choice of α (to assure that the top individuals are highly significantly better from the original population at the current level) and makes β less aggressive (to maintain a moderately sized population at the final level). In cases where evolution starts to stagnate at the final level, the population enters into a different form of evolution, driven by a form of hyper-mutation that runs until either a satisfactory fitness has been found or the total evaluation budget has been exhausted. The experimental results show that Pyramid-Z consistently outperforms the previous version and the baseline too.
Download
Paper Nr: 16
Title:

Substitution of the Fittest: A Novel Approach for Mitigating Disengagement in Coevolutionary Genetic Algorithms
Authors:

Hugo Alcaraz-Herrera and John Cartlidge
Abstract: We propose substitution of the fittest (SF), a novel technique designed to counteract the problem of disengagement in two-population competitive coevolutionary genetic algorithms. The approach presented is domain-independent and requires no calibration. In a minimal domain, we perform a controlled evaluation of the ability to maintain engagement and the capacity to discover optimal solutions. Results demonstrate that the solution discovery performance of SF is comparable with other techniques in the literature, while SF also offers benefits including a greater ability to maintain engagement and a much simpler mechanism.
Download
Paper Nr: 21
Title:

Towards Automatic Grammatical Evolution for Real-world Symbolic Regression
Authors:

Muhammad S. Ali, Meghana Kshirsagar, Enrique Naredo and Conor Ryan
Abstract: AutoGE (Automatic Grammatical Evolution) is a tool designed to aid users of GE for the automatic estimation of Grammatical Evolution (GE) parameters, a key one being the grammar. The tool comprises of a rich suite of algorithms to assist in fine tuning a BNF (Backus-Naur Form) grammar to make it adaptable across a wide range of problems. It primarily facilitates the identification of better grammar structures and the choice of function sets to enhance existing fitness scores at a lower computational overhead. This research work discusses and reports experimental results for our Production Rule Pruning algorithm from AutoGE which employs a simple frequency-based approach for eliminating less useful productions. It captures the relationship between production rules and function sets involved in the problem domain to identify better grammar. The experimental study incorporates an extended function set and common grammar structures for grammar definition. Preliminary results based on ten popular real-world regression datasets demonstrate that the proposed algorithm not only identifies suitable grammar structures, but also prunes the grammar which results in shorter genome length for every problem, thus optimizing memory usage. Despite utilizing a fraction of budget in pruning, AutoGE was able to significantly enhance test scores for 3 problems.
Download
Short Papers
Paper Nr: 6
Title:

A Strength Pareto Evolutionary Algorithm for Solving the Capacitated Vehicle Routing Problem with Time Windows
Authors:

Wissam Marrouche and Haidar M. Harmanani
Abstract: The capacitated vehicle routing problem with time windows (CVRPTW) belongs to a set of complex combinatorial optimization problems that find major application in logistic systems and telecommunications. It is a complex variant of the well studied capacitated vehicle routing problem (CVRP). Few meta-heuristic approaches have been proposed to solve the CVRPTW problem in literature. In this paper, we examine a population based meta-heuristic algorithm, more precisely the strength Pareto evolutionary algorithm SPEA2 with hill climbing as a local search. The novelty of the approach lies in the choice of multi objective evolutionary algorithm namely SPEA2, its suggested evolutionary operators, and the optimization for three objectives: the number of routes, the total distance travelled, and the average time per route. The proposed algorithm is implemented using Python, and tested on the Solomon’s instances benchmark. Favorable results are reported and suggestions for further improvements are discussed.
Download
Paper Nr: 7
Title:

Solving a Problem of the Lateral Dynamics Identification of a UAV using a Hyper-heuristic for Non-stationary Optimization
Authors:

Evgenii Sopov
Abstract: A control system of an Unmanned Aerial Vehicle (UAV) requires identification of the lateral and longitudinal dynamics. While data on the longitudinal dynamics can be accessed via precise navigation devices, the lateral dynamics is predicted using such control parameters as aileron, elevator, rudder, and throttle positions. Autoregressive neural networks (ARNN) usually demonstrate high performance when modeling dynamic systems. At the same time, the lateral dynamics identification problem is known as non-stationary because of constantly changing operating conditions and errors in control equipment buses. Thus, an optimizer for ARNN must be accurate enough and must adapt to the changes in the environment. In the study, we have proposed an evolutionary hyper-heuristic for training ARNN in the non-stationary environment. The approach is based on the combination of the algorithm portfolio and the population-level dynamic probabilities approach. The hyper-heuristic selects and controls online the interaction of five evolutionary metaheuristics for dealing with dynamic optimization problems. The experimental results have shown that the proposed approach outperforms the standard back-propagation algorithm and all single metaheuristics.
Download
Paper Nr: 8
Title:

Continuous Parameter Control in Genetic Algorithms using Policy Gradient Reinforcement Learning
Authors:

Alejandro de Miguel Gomez and Farshad G. Toosi
Abstract: Genetic Algorithms are biological-inspired optimization techniques that are able to solve complex problems by evolving candidate solutions in the search space. Their evolutionary features rely on parameterized stochastic operators that are sensitive to changes and, ultimately, determine the performance of the algorithms. In recent years, Reinforcement Learning has been proposed for online parameter control in contrast to traditional fine-tuning, which inevitably leads to suboptimal configurations found through extensive trial-and-error. In this regard, the current literature has focused on value-based Reinforcement Learning controllers for Genetic Algorithms without exploring the advantages of policy gradient methods in such environments. In this study, we propose a novel approach to leverage the continuous nature of the latter with agents that learn a behavior policy and enhance the performance of Genetic Algorithms by tuning their operators dynamically at runtime. In particular, we look at Deep Deterministic Policy Gradient (DDPG) and Proximal Policy Optimization (PPO). The resulting hybrid algorithms are tested on benchmark combinatorial problems and performance metrics are discussed in great detail considering the existing work based on Q-Learning and SARSA.
Download
Paper Nr: 11
Title:

A Hybrid Evolutionary Algorithm, Utilizing Novelty Search and Local Optimization, Used to Design Convolutional Neural Networks for Handwritten Digit Recognition
Authors:

Tabish Ashfaq, Nivedha Ramesh and Nawwaf Kharma
Abstract: Convolutional neural networks (CNNs) are deep learning models that have been successfully applied to various computer vision tasks. The design of CNN topologies often requires extensive domain knowledge and a high degree of trial and error. In recent years, numerous Evolutionary Algorithms (EAs) have been proposed to automate the design of CNNs. The search space of these EAs is very large and often deceptive, which entails great computational cost. In this work, we investigate the design of CNNs using Cartesian Genetic Programming (CGP), an EA variant. We then augment the basic CGP with methods for identifying potential/actual local optima within the solution space (via Novelty Search), followed by further local optimization of each of the optima (via Simulated Annealing). This hybrid EA methodology is evaluated using the MNIST data-set for handwritten digit recognition. We demonstrate that the use of the proposed method results in considerable reduction of computational effort, when compared to the basic CGP approach, while still returning competitive results. Also, the CNNs designed by our method achieve competitive recognition results compared to other neuroevolutionary methods.
Download
Paper Nr: 17
Title:

Subset Sum and the Distribution of Information
Authors:

Daan Van Den Berg and Pieter Adriaans
Abstract: The complexity of the subset sum problem does not only depend on the lack of an exact algorithm that runs in subexponential time with the number of input values. It also critically depends on the number of bits m of the typical integer in the input: a subset sum instance of n with large m has fewer solutions than a subset sum instance with relatively small m. Empirical evidence from this study suggests that this image of complexity has a more fine-grained structure. A depth-first branch and bound algorithm deployed to the integer partition problem (a special case of subset sum) shows that for this experiment, its hardest instances reside in a region where informational bits are equally dispersed among the integers. Its easiest instances reside there too, but in regions of more eccentric informational dispersion, hardness is much less volatile among instances. The boundary between these hardness regions is given by instances in which the ith element is an integer of exactly i bits. These findings show that, for this experiment, a very clear hardness classification can be made even on the basis of information dispersal, even for subset sum instances with identical values of n and m. The role of the ‘scale free’ region are discussed from an information theoretical perspective.
Download
Paper Nr: 18
Title:

Optimal Scheduling for Flying Taxi Operation
Authors:

Panwadee Tangpattanakul and Ilhem Quenel
Abstract: According to the traffic congestion problem in big cities around the world, some sustainable transportation technologies are researched and developed in these recent years. Flying taxi is a transportation mode, which is being developed from several major brands. It can become an alternative transportation mode in the future. In this work, a simplified optimization model of the flying taxi scheduling is proposed. Two algorithms, which consists of genetic algorithm and simulated annealing, are used to solve the problem. The experiments are conducted on 15 instances with different number of customer demands (between 10 and 200 demands) and different number of available flying taxis in the system (from 2 to 10 taxis). The experimental results show that both algorithms are efficient to solve the problem. The genetic algorithm obtains better quality solutions for the small and medium size instances but it spends more computation time than the simulated annealing. However, the simulated annealing can solve the large instances and obtain good solutions in reasonable time.
Download
Paper Nr: 2
Title:

A Simulated Annealing based Energy Efficient Task Scheduling Algorithm for Multi-core Processors
Authors:

Pratik S. and Abhishek Mishra
Abstract: In this paper we propose a Simulated Annealing (SA) based energy-efficient task scheduling algorithm for multi-core processors, the Simulated Annealing Energy Efficient Task Scheduling Algorithm (SAEETSA), and compare it with another algorithm, the Energy Efficient Task Scheduling Algorithm (EETSA). Our results show that for dual-core processors the SAEETSA algorithm is taking up to 16.78% less energy as compared to the EETSA algorithm, and for tri-core processors, the SAEETSA algorithm is taking up to 26.97% less energy as compared to the EETSA algorithm.
Download
Paper Nr: 4
Title:

Harris Hawks Optimization: A Formal Analysis of Its Variants and Applications
Authors:

Ruba A. Khurma, Ibrahim Aljarah and Pedro A. Castillo
Abstract: The Harris Hawks Optimization (HHO) is a recent meta-heuristic algorithm developed by Hideri in 2019. HHO algorithm has been widely utilized to solve many optimization problems in different fields. The primary objective of HHO is to define a fitness function that can successfully optimize a specific problem by finding the minimum or maximum value. This survey presents a thorough study of the algorithm, including its variants such as binary, hybridization, multi-objective and modifications. It highlights the main applications such as medical, engineering, machine learning, and network applications. Finally, the conclusion summarizes the current works on HHO and suggests possible future directions.
Download
Paper Nr: 20
Title:

Multiobjective Evolutionary Computation for Market Segmentation
Authors:

Ying Liu
Abstract: The market segmentation, by its computational essence, is a NP-hard multicriteria problem. Multiobjective evolutionary algorithms are developed to optimize multiple objectives simultaneously and can generate a set of Pareto optimal solutions. As a proven meta-heuristic technique, multiobjective evolutionary computation is robust in handling different data types, various business constraints and different objective function forms. The generated Pareto optimal solution set gives a holistic view of possible solutions that bring business insights and allow big flexibility in solution selection. These features make the multiobjective evolution computation a good fit for market segmentation problems. There are challenges in every phase in implementation of multiobjective evolutionary computation for market segmentation.
Download