ECTA 2020 Abstracts


Full Papers
Paper Nr: 10
Title:

Feature Selection using Binary Moth Flame Optimization with Time Varying Flames Strategies

Authors:

Ruba A. Khurma, Pedro A. Castillo, Ahmad Sharieh and Ibrahim Aljarah

Abstract: In this paper, a new feature selection (FS) approach is proposed based on the Moth Flame Optimization (MFO) algorithm with time-varying flames number strategies. FS is a data preprocessing technique that is applied to minimize the number of features in a data set to enhance the performance of the learning algorithm (e.g classifier) and reduce the learning time. Finding the best feature subset is a challenging search process that requires exponential running time if the complete search space is generated. Meta-heuristics algorithms are promising alternative solutions that have proven their performance in finding approximated optimal solutions within a reasonable time. The MFO algorithm is a recently developed Swarm Intelligence (SI) algorithm that has demonstrated effective performance in solving various optimization problems. This is due to its spiral update strategy that enhances the convergence trends of the algorithm. The number of flames is an important parameter in the MFO algorithm that controls the balance between the exploration and exploitation phases during the optimization process. In the standard MFO, the number of flames linearly decreases throughout the iterations. This paper proposes different time-varying strategies to update the number of flames and analyzes their impact on the performance of MFO when used to solve the FS problem. Seventeen medical benchmark data sets were used to evaluate the performance of the proposed approach. The proposed approach is compared with other well-regarded meta-heuristics and the results show promising performance in tackling the FS problem.

Paper Nr: 14
Title:

Behavioural Modelling of Digital Circuits in System Verilog using Grammatical Evolution

Authors:

Conor Ryan, Michael K. Tetteh and Douglas M. Dias

Abstract: Digital circuit design is an immensely complex and time consuming task that has been aided greatly by the use of Hardware Description Languages and powerful digital circuit simulators that permit a designer to program at a much higher level of abstraction, similar to how software programmers now rarely use Assembly Language, and also to test their circuits before committing them to hardware. We introduce Automatic Design of Digital Circuits (ADDC), a system comprised of Grammatical Evolution (GE), System Verilog, a high level Hardware Description Language (HDL) and Icarus, a powerful, but freely available, digital circuit simulator. ADDC operates at a much higher level than previous digital circuit evolution due to the fact that System Verilog supports behavioural modelling through the use of high level constructs such as If-Then-Else, Case and Always procedural blocks. Not only are HDLs very expressive, but they are also far more understandable than circuit diagrams, so solutions produced by ADDC are quite interpretable by humans. ADDC is applied to three benchmark problems from the Digital Circuit Literature. We show that ADDC is successful on all three benchmarks and further demonstrate how the integration of simple knowledge, e.g. the separation of input and output wires, is feasible through the grammars, and can have a major impact on overall performance.

Paper Nr: 15
Title:

Looking for the Hardest Hamiltonian Cycle Problem Instances

Authors:

Joeri Sleegers and Daan van den Berg

Abstract: We use two evolutionary algorithms to make hard instances of the Hamiltonian cycle problem. Hardness, or fitness, is defined as the number of recursions required by Vandegriend-Culberson, the best known exact backtracking algorithm for the problem. The hardest instances, all non-Hamiltonian, display a high degree of regularity and scalability across graph sizes. These graphs are found multiple times through independent runs and in both algorithms, suggestion the search space might contain monotonic paths to the global maximum. The one-bit neighbourhoods of these instances are also analyzed, and show that these hardest instances are separated from the easiest problem instances by just one bit of information. For Hamiltonian-bound graphs, the hardest instances are less uniform and substantially easier than their non-Hamiltonian counterparts. Reasons for these less-conclusive results are presented and discussed.

Paper Nr: 17
Title:

XCSF for Automatic Test Case Prioritization

Authors:

Lukas Rosenbauer, Anthony Stein, David Pätzel and Jörg Hähner

Abstract: Testing is a crucial part in the development of a new product. Due to the change from manual testing to automated testing, companies can rely on a higher number of tests. There are certain cases such as smoke tests where the execution of all tests is not feasible and a smaller test suite of critical test cases is necessary. This prioritization problem has just gotten into the focus of reinforcement learning. A neural network and an XCS classifier system have been applied to this task. Another evolutionary machine learning approach is the XCSF which produces, unlike XCS, continuous outputs. In this work we show that XCSF is superior to both the neural network and XCS for this problem.

Paper Nr: 20
Title:

A Comprehensive Study on Subgraph Crossover in Cartesian Genetic Programming

Authors:

Roman Kalkreuth

Abstract: While tree-based Genetic Programming is often used with crossover, Cartesian Genetic Programming (CGP) is mostly used only with mutation as the sole genetic operator. In contrast to comprehensive and fundamental knowledge about crossover in tree-based GP, the state of knowledge in CGP appears to be still ambiguous and ambivalent. Two decades after CGP was officially introduced, the role of recombination in CGP is still considered to be an open and remaining question. Although some promising steps have been taken in the last years, comprehensive studies are needed to evaluate the role of crossover in CGP on a large set of problems. In this paper, we take a step forward on the crossover issue by comparing algorithms that utilize the subgraph crossover technique which has been proposed for CGP to the traditional mutation-only CGP. Experiments on well-known symbolic regression and Boolean function problems demonstrate that the use of algorithms that utilize the subgraph crossover outperform the mutation-only CGP on well-known benchmark problems.

Paper Nr: 21
Title:

Grammar-based Fuzzy Pattern Trees for Classification Problems

Authors:

Aidan Murphy, Muhammad S. Ali, Douglas M. Dias, Jorge Amaral, Enrique Naredo and Conor Ryan

Abstract: This paper introduces a novel approach to induce Fuzzy Pattern Trees (FPT) using Grammatical Evolution (GE), FGE, and applies to a set of benchmark classification problems. While conventionally a set of FPTs are needed for classifiers, one for each class, FGE needs just a single tree. This is the case for both binary and multi-classification problems. Experimental results show that FGE achieves competitive and frequently better results against state of the art FPT related methods, such as FPTs evolved using Cartesian Genetic Programming (FCGP), on a set of benchmark problems. While FCGP produces smaller trees, FGE reaches a better classification performance. FGE also benefits from a reduction in the number of necessary user-selectable parameters. Furthermore, in order to tackle bloat or solutions growing too large, another version of FGE using parsimony pressure was tested. The experimental results show that FGE with this addition is able to produce smaller trees than those using FCGP, frequently without compromising the classification performance.

Paper Nr: 24
Title:

Behavioral Locality in Genetic Programming

Authors:

Adam K. Pindur and Hitoshi Iba

Abstract: Locality is a key concept affecting exploration and exploitation in evolutionary computation systems. Genotype to phenotype mapping has locality if the neighborhood is preserved under that mapping. Unfortunately, assessment of the locality in Genetic Programming is dependent on the distance metric used to compare program trees. Furthermore, there is no distinction between genotype and phenotype in GP. As such the definition of locality in GP was studied only in the context of genotype-fitness mapping. In this work we propose a different family of similarity measures, graph kernels, as alternatives to the traditional family of distance metrics in use, that is edit distance. Traditional tree edit distance is compared to the Weisfeiler-Lehman Subtree Kernel, which is considered to be the state-of-the-art method in graph classification. Additionally, we extend the definition of the locality of GP, by studying the relationship between genotypes and behaviors. In this paper, we consider a mutation-based GP system applied to two basic benchmark problems: artificial ant (multimodal deceptive landscape) and even parity (highly neutral landscape).

Paper Nr: 25
Title:

Parameter Sensitivity Patterns in the Plant Propagation Algorithm

Authors:

Marleen de Jonge and Daan van den Berg

Abstract: The parameter sensitivity of the plant propagation algorithm’s performance, defined as the maximum impact on attained objective values, is studied on function optimization. The number of offspring and population size are varied across a large range of values and tested on multidimensional benchmark test functions. As the dimensionality of a function increases, the parametric sensitivity shows one of three distinct different patterns: sublinear increase, superlinear increase or an up-down phase transition. We conjecture that the difference in algorithmic behaviour might be due to the intrinsic mathematical properties of the functions themselves.

Paper Nr: 28
Title:

Evolutionary Large-scale Sparse Multi-objective Optimization for Collaborative Edge-cloud Computation Offloading

Authors:

Guang Peng, Huaming Wu, Han Wu and Katinka Wolter

Abstract: This paper proposes evolutionary large-scale sparse multi-objective optimization (ELSMO) algorithms for collaboratively solving edge-cloud computation offloading problems. To begin with, a collaborative edge-cloud computation offloading multi-objective optimization model is established in a mobile environment, where the offloading decision is represented as a binary encoding. Considering the large-scale and sparsity property of the computation offloading model, the restricted Boltzmann machine (RBM) is applied to reduce the dimensionality and learn the Pareto-optimal subspace. In addition, the contribution score of each decision variable is assumed to generate new offsprings. Combining the RBM and the contribution score, two evolutionary algorithms using non-dominated sorting and crowding distance methods are designed, respectively. The proposed algorithms are compared with other state-of-the-art algorithms and offloading strategies on a number of test problems with different scales. The experiment results demonstrate the superiority of the proposed algorithms.

Short Papers
Paper Nr: 3
Title:

ACO Algorithms to Solve an Electromagnetic Discrete Optimization Problem

Authors:

Anton Duca and Ibrahim Hameed

Abstract: The paper proposes and studies the efficiency of the ant colony optimization (ACO) algorithms for solving an inverse problem in non-destructive electromagnetic testing (NDET). The inverse problem, which consists in finding the shape and parameters of cracks in conducting plates starting from the signal of an eddy current testing (ECT) probe, is formulated as a discrete optimization problem. Two of the most widely known ant algorithms are adapted and applied to solve the optimization problem. The influence over the optimization algorithms performances of some problem specific local search strategies is also analyzed.

Paper Nr: 8
Title:

A Dimensionality Reduction Method for Data Visualization using Particle Swarm Optimization

Authors:

Panagiotis C. Petrantonakis and Ioannis Kompatsiaris

Abstract: Dimensionality reduction involves mapping of a set of high dimensional input points on a low dimensional space. Mappings in low dimensional space are expected to preserve the pairwise distances of the high dimensional inputs. In this work we present a dimensionality reduction method, called Dimensionality Reduction based on Particle Swarm Optimization (PSO-DR), where the conversion of each input to the low dimensional output does not depend on the rest of the inputs but, instead, it is based on a set of reference points (beacons). The presented approach results in a simple, fast, versatile dimensionality reduction approach with good quality of visualization and straightforward out-of-sample extension.

Paper Nr: 9
Title:

New Fitness Functions in Binary Harris Hawks Optimization for Gene Selection in Microarray Datasets

Authors:

Ruba A. Khurma, Pedro A. Castillo, Ahmad Sharieh and Ibrahim Aljarah

Abstract: Gene selection (GS) is a challenging problem in medical applications. This is because of the availability of a large number of genes and a limited number of patient’s samples in microarray datasets. Selecting the most relevant genes is a necessary pre-processing step for building reliable cancer classification systems. This paper proposes two new fitness functions in Binary Harris Hawks Optimization (BHHO) for GS. The main objective is to select a small number of genes and achieve high classification accuracy. The first fitness function balances between the classification performance and the number of genes. This is done by using a weight that increases linearly throughout the optimization process. The second fitness function is applied across two-stages. The first stage optimizes the classification performance only while the second stage takes into consideration the number of genes. K-nearest neighbor (K-nn) is used to evaluate the proposed approaches on ten microarray data sets. The results show that the proposed fitness functions can achieve better classification results compared with the fitness function that takes into account only the classification performance. Besides, they outperform three other wrapper-based methods in most of the cases. The second fitness function outperforms the first fitness function across most of the datasets based on classification accuracy and the number of genes.

Paper Nr: 11
Title:

Identifying Botnets by Analysing Twitter Traffic during the Super Bowl

Authors:

Salah Safi, Huthaifa Jawazneh, Antonio Mora, Pablo García, Hossam Faris and Pedro A. Castillo

Abstract: Detecting accounts broadcasting illegal contents at sporting events in social networks is an important problem of difficult solution, since the traditional intrusion detection systems are not effective in online social networks due to the speed with which these kind of messages and contents spread. Thus, there is an increasing need for an adequate and efficient detection system of the so-called botnets used for the distribution of illegal contents on online social networks. In this paper we propose using well-known classification methods to analyse the activity of Twitter accounts in order to identify botnets. We have analysed the Twitter conversations that include hashtags related to the Super Bowl LIII (February 3, 2019). The objective is to identify the behaviour of various types of profiles with automatic and non-standard spamming activities. In order to do so, a dataset from public data available on Twitter that includes content published by human-managed accounts and also by bots that used hashtags related to the event has been collected. This dataset has been manually labelled to create a training set with tweets posted by humans and bots active in Twitter. As a result, several types of profiles with non standard activities have been identified. Also, some groups of accounts have been identified as botnets that were activated during the Super Bowl LIII (2019).

Paper Nr: 12
Title:

The addRole-EA: A New Evolutionary Algorithm for the Role Mining Problem

Authors:

Simon Anderer, Daniel Kreppein, Bernd Scheuermann and Sanaz Mostaghim

Abstract: Role Based Access Control is an important feature of cyber security and authorization management. The search of an optimum set of roles and their assignment to users can be modeled as an optimization problem, which is known as the Role Mining Problem (RMP) and has been shown to be NP-complete. Thus, fast heuristics are needed to search for solutions for the RMP in affordable time. This paper proposes a new evolutionary algorithm for the RMP, which is based on iteratively adding and deleting roles, while avoiding deviations from the original user-permission assignment. A range of experiments are presented which indicate that the proposed EA performs well on established benchmarking problems.

Paper Nr: 16
Title:

Improving the Transparency of Deep Neural Networks using Artificial Epigenetic Molecules

Authors:

George Lacey, Annika Schoene, Nina Dethlefs and Alexander Turner

Abstract: Artificial gene regulatory networks (AGRNs) are connectionist architectures inspired by biological gene regulation capable of solving tasks within complex dynamical systems. The implementation of an operational layer inspired by epigenetic mechanisms has been shown to improve the performance of AGRNs, and improve their transparency by providing a degree of explainability. In this paper, we apply artificial epigenetic layers (AELs) to two trained deep neural networks (DNNs) in order to gain an understanding of their internal workings, by determining which parts of the network are required at a particular point in time, and which nodes are not used at all. The AEL consists of artificial epigenetic molecules (AEMs) that dynamically interact with nodes within the DNNs to allow for the selective deactivation of parts of the network.

Paper Nr: 18
Title:

Discrete Pigeon Inspired Simulated Annealing Algorithm and Contract Net Algorithm based on Multi-objective Optimization for Task Allocation of UAV Formation

Authors:

Xuzan Liu, Yu Han, Jian Chen, Yi Cao and Shubo Wang

Abstract: In this paper, a mathematical model of multi-objective optimization under complex constraints is established to solve the task allocation problem. Among them, the constraint indexes include UAV quantity constraint and fuel consumption constraint; the optimization objectives include the gain, loss and fuel consumption. Discrete Pigeon Inspired Optimization-Simulated Annealing (DPIO-SA) algorithm is proposed to solve this problem. The experimental results show that while the total fitness reaches the optimum, the gain is the largest, the loss and fuel consumption are the smallest. After running the algorithm 30 times. The number of times that DPIO-SA reaches the global optimum is 15, while DPIO is 2. In addition, the average value of DPIO-SA after stabilization is 13.5% larger than that of DPIO. Both prove that after joining SA, the algorithm is easier to reach the global extremum. The Contract Net Algorithm (CNA) is adopted to solve the task scheduling problem. The UAVs are divided into tenderer UAV, potential bidder UAVs, bidder UAVs and winner UAV. After network communication, suitable bidder UAV is found to replace tenderer UAV to perform the task. Experimental results show that the algorithm has good applicability.

Paper Nr: 19
Title:

GEMO: Grammatical Evolution Memory Optimization System

Authors:

Meghana Kshirsagar, Rushikesh Jachak, Purva Chaudhari and Conor Ryan

Abstract: In Grammatical Evolution (GE) individuals occupy more space than required, that is, the Actual Length of the individuals is longer than their Effective Length. This has major implications for scaling GE to complex problems that demand larger populations and complex individuals. We show how these two lengths vary for different sizes of population, demonstrating that Effective Length is relatively independent of population size, but that the Actual Length is proportional to it. We introduce Grammatical Evolution Memory Optimization (GEMO), a two-stage evolutionary system that uses a multi-objective approach to identify the optimal, or at least, near-optimal, genome length for the problem being examined. It uses a single run with a multi-objective fitness function defined to minimize the error for the problem being tackled along with maximizing the ratio of Effective to Actual Genome Length leading to better utilization of memory and hence, computational speedup. Then, in Stage 2, standard GE runs are performed restricting the genome length to the length obtained in Stage 1. We demonstrate this technique on different problem domains and show that in all cases, GEMO produces individuals with the same fitness as standard GE but significantly improves memory usage and reduces computation time.

Paper Nr: 22
Title:

GA-based U-Net Architecture Optimization Applied to Retina Blood Vessel Segmentation

Authors:

Vipul Popat, Mahsa Mahdinejad, Oscar D. Cedeño, Enrique Naredo and Conor Ryan

Abstract: Blood vessel extraction in digital retinal images is an important step in medical image analysis for abnormality detection and also obtaining good retinopathy diabetic diagnosis; this is often referred to as the Retinal Blood Vessel Segmentation task and current state-of-the-art approaches all use some form of neural networks. Designing neural network architecture and selecting appropriate hyper-parameters for a specific task is challenging. In recent works, increasingly more complex models are starting to appear, but in this work, we present a simple and small model with a very low number of parameters with good performance compared with the state of the art algorithms. In particular, we choose a standard Genetic Algorithm (GA) for selecting the parameters of the model and we use an expert-designed U-net based model, which has become a very popular tool in image segmentation problems. Experimental results show that GA is able to find a much shorter architecture and acceptable accuracy compared to the U-net manually designed. This finding puts on the right track to be able in the future to implement these models in portable applications.

Paper Nr: 23
Title:

Hybrid Intellectual Scheme for Scheduling of Heterogeneous Workflows based on Evolutionary Approach and Reinforcement Learning

Authors:

Mikhail Melnik, Ivan Dolgov and Denis Nasonov

Abstract: Scheduling of workload in distributed computing systems is a well-known optimization proble. A workload may include single independent software packages. However, the computational process in scientific and industrial fields is often organized as composite applications or workflows which are represented by collection of interconnected computing packages that solve a common problem. We identified three common computing modes: batch, stream and iterative. The batch mode is a classic way for one-time execution of software packages with an initially specified set of input data. Stream mode corresponds to launch of a software package for further continuous processing of active data in real time. Iterative mode is a launching of a distributed application with global synchronization at each iteration. Each computing mode has its own specifics for organization of computation process. But at the moment, there are new problems that require organization of interaction between computing modes (batch, stream, iterative) and to develop optimization algorithms for this complex computations that leads to formation of heterogeneous workflows. In this work, we present a novel developed hybrid intellectual scheme for organizing and scheduling of heterogeneous workflows based on evolutionary computing and reinforcement learning methods.

Paper Nr: 26
Title:

Using Dominated Solutions to the Uniformity of Non-dominated Solution Distributions in NSGA-II

Authors:

Kina Yokoyama and Yuji Sato

Abstract: This paper proposes a method for improving the diversity of the Pareto front in a fast elitist non-dominated sorting genetic algorithm (NSGA-II), which is an evolutionary multi-objective optimization algorithm. Conventional NSGA-II has excellent convergence to the Pareto front, but it has been reported that for some test cases, it does not produce a more diverse solution distribution than the strength Pareto evolutionary algorithm 2 (SPEA2). To avoid this problem, we propose a method that stores an archive of dominated solutions that may be effective in improving diversity in the conventional search process when used for genetic operations. We experimentally compare this approach with the conventional method on the typical multi-objective test problems ZDT1, ZDT2, and ZDT3. By evaluating the performance based on Pareto front diagrams and hypervolume values, we show that the proposed method is effective at improving the diversity at both ends of Pareto optimal front and the uniformity of the solution distribution.

Paper Nr: 27
Title:

A Structured Approach to Modifying Successful Heuristics

Authors:

Simon P. Martin, Matthew J. Craven and John R. Woodward

Abstract: In some cases, heuristics may be transferred easily between different optimisation problems. This is the case if these problems are equivalent or dual (e.g., maximum clique and maximum independent set) or have similar objective functions. However, the link between problems can further be defined by the constraints that define them. This refining can be achieved by organising constraints into families and translating between them using gadgets. If two problems are in the same constraint family, the gadgets tell us how to map from one problem to another and which constraints are modified. This helps better understand a problem through its constraints and how best to use domain specific heuristics. In this position paper, we argue that this allows us to understand how to map between heuristics developed for one problem to heuristics for another problem, giving an example of how this might be achieved.

Paper Nr: 7
Title:

Metaheuristics for the Minimum Set Cover Problem: A Comparison

Authors:

Lukas Rosenbauer, Anthony Stein, Helena Stegherr and Jörg Hähner

Abstract: The minimum set cover problem (MSCP) is one of the first NP-hard optimization problems discovered. Theoretically it has a bad worst case approximation ratio. As the MSCP turns out to appear in several real world problems, various approaches exist where evolutionary algorithms and metaheuristics are utilized in order to achieve good average case results. This work is intended to revisit and compare current results regarding the application of metaheuristics for the MSCP. Therefore, a recapitulation of the MSCP and its classification into the class of NP-hard optimization problems are provided first. After an overview of notable approximation methods, the focus is shifted towards a brief review of existing metaheuristics which were adapted for the MSCP. In order to allow for a targeted comparison of the existing algorithms, the theoretical worst case complexities in terms of the big O-notation are derived first. This is followed by an empirical study where the identified metaheuristics are examined. Here we use Steiner triple systems, Beasley’s OR library, and introduce a new class of instances. Several of the considered approaches achieve close to optimal results. However, our analysis reveals significant differences in terms of runtime and shows that some approaches may even have exponential runtime.