EvoApplications, the International Conference on the Applications of Evolutionary Computation -formerly known as EvoWorkshops- brings together researchers in a variety of areas of application of Evolutionary Computation and other Nature-inspired techniques.
invites high quality contributions for its 22nd edition, which will be held
as part of the EvoStar
2019 event in Leipzig, Germany, April 2019 and co-located within EvoStar
with three related conferences: EuroGP, EvoCOP
EvoApplications will focus on the following Thematic Areas:
Accepted papers will appear in the proceedings of EvoApplications, published in a volume of the Springer Lecture Notes in Computer Science, which will be available at the Conference. Submissions must be original and not published elsewhere. The submissions will be peer reviewed by at least three members of the program committee. The authors of accepted papers will have to improve their paper on the basis of the reviewers comments and will be asked to send a camera ready version of their manuscripts. At least one author of each accepted work has to register for the conference and attend the conference and present the work.
This year EvoApplications is accepting two kinds of submission: full papers and short papers. Full papers require novel and complete research work and have a limit of 16 pages. Short papers should present complete research or interesting preliminary results and have a limit of 8 pages. Both types of submission will undergo the same double blind review process and all accepted papers will be included in the LNCS proceedings. All authors of accepted papers will be given the opportunity to further disseminate their work in poster sessions.
Mainz University, Germany
paul.kaufmann (at) uni-mainz.de
University of Granada, Spain
Compact Optimization Algorithms with Re-sampled Inheritance
Giovanni Iacca, Fabio Caraffini
Compact optimization algorithms are a class of Estimation of Distribution Algorithms (EDAs) characterized by extremely limited memory requirements (hence they are called "compact"). As all EDAs, compact algorithms build and update a probabilistic model of the distribution of solutions within the search space, as opposed to population-based algorithms that instead make use of an explicit population of solutions. In addition to that, to keep their memory consumption low, compact algorithms purposely employ simple probabilistic models that can be described with a small number of parameters. Despite their simplicity, compact algorithms have shown good performances on a broad range of benchmark functions and real-world problems. However, compact algorithms also come with some drawbacks, i.e. they tend to premature convergence and show poorer performance on non-separable problems. To overcome these limitations, here we investigate a possible memetic computing approach obtained by combining compact algorithms with a non-disruptive restart mechanism taken from the literature, named Re-Sampled Inheritance (RI). The resulting compact algorithms with RI are then tested on the CEC 2014 benchmark functions. The numerical results show on the one hand that the use of RI consistently enhances the performances of compact algorithms, still keeping a limited usage of memory. On the other hand, our experiments show that among the tested algorithms, the best performance is obtained by compact Differential Evolution with RI.
Optimizing the C Index Using a Canonical Genetic Algorithm
Thomas Runkler, James Bezdek
Clustering is an important family of unsupervised machine learning methods. Cluster validity indices are widely used to assess the quality of obtained clustering results. The C index is one of the most popular cluster validity indices. This paper shows that the C index can be used not only to validate but also to actually find clusters. This leads to difficult discrete optimization problems which can be approximately solved by a canonical genetic algorithm. Numerical experiments compare this novel approach to the well-known c-means and single linkage clustering algorithms. For all five considered popular real-world benchmark data sets the proposed method yields a better C index than any of the other (pure) clustering methods.
Coordination Index for Directional Overcurrent Relays Using Multiobjective C-DEEPSO Approach
Directional Overcurrent Relays (DORs) can be dynamically and quickly configured using optimization techniques making the electrical network more dynamic and resilient. In this work, the DOR coordination is modeled as mixed integer non-linear problem that minimizes the sum of relays operating times and maximizes their coordination. To solve this, the use of Multiobjective Canonical Differential Evolutionary Particle Swarm Optimization (C-DEEPSO) is proposed in this work. The effects of different probabilistic distributions (normal, uniform, triangular and qui-squared ones) to initialize the decision variables (time dials, pickup currents, curves and indexes) are also discussed in this work. With the proposed method a reduction in total actuation time of more than 50% can be obtained when the adequate probabilistic distribution is used. The decrease in time can also be enhanced if a different acceptable reduction of the Coordination Time Interval (CTI) is considered resulting in different robust and solutions.
A Comparison of Different Many-Objective Optimization Algorithms for Energy System Optimization
The usage of renewable energy sources, storage devices, and flexible loads has the potential to greatly improve the overall efficiency of a building complex or factory. However, one needs to considera multitude of upgrade options and several performance criteria. We therefore formulated this taskas a many-objective optimization problem with 10 design parameters and 5 objectives (investment cost, yearly energy costs, CO2 emissions, system resilience, and battery lifetime). We investigated if different optimization algorithms might produce different results, we therefore tested several different many-objective optimization algorithms in terms of their hypervolume performance and the practical relevance of their results. We found substantial performance differences between thealgorithms, both regarding hypervolume and in the basic distribution of solutions in objective space. We have also used the concept of desirabilities to better visualize and assess the quality of solutions found.
Free Form Evolution for Angry Birds Level Generation
Laura Calle, JJ Merelo, Mario García-Valdez, Antonio Mora-García
This paper presents an original approach for building structures that are stable under gravity for the physics-based puzzle game Angry Birds, with the ultimate objective of creating fun and aesthetically pleasing Angry Birds levels with the minimum number of constraints. This approach consists of a search-based procedural level generation method that uses evolutionary algorithms. In order to evaluate the stability of the levels, they are executed in an adaptation of an open source version of the game called Science Birds. In the same way, an open source evolutionary computation framework has been implemented to fit the requirements of the problem. The main challenge has been to design a fitness function that, first, avoids if possible the actual execution of the simulator, which is time consuming, and, then, to take
Efficient Online Hyperparameter Adaptation for Deep Reinforcement Learning
Yinda Zhou, Weiming Liu, Bin Li
Deep Reinforcement Learning (DRL) has shown its extraordinary performance on a variety of challenging learning tasks, especially those in games. It's has been recognized that DRL process is a high-dynamic and non-stationary optimization process even in the static environments, their performance is notoriously sensitive to the hyperparameter configuration which includes learning rate, discount coefficient and step size, etc. The situation will be more serious when DRL is conducting in a changing environment. The most ideal state of hyperparameter configuration in DRL is that the hyperparameter can self-adapt to the best values promptly for their current learning state, rather than using a fixed set of hyperparameters for the whole course of training like most previous works did. In this paper, an efficient online hyperparameter adaptation method is presented, which is an improved version of Population-based Training(PBT) method on the promptness of adaptation. A recombination operation inspired by GA is introduced into the population adaptation to accelerate the convergence of population towards the better hyperparameter configurations. Experiment results have shown that in four test environments, the presented method has achieved 92\\%, 70\\%, 2\\% and 15\\% performance improvement over PBT.
Genetic Programming for Rare Diseases
Illya Bakurov, Leonardo Vanneschi, Mauro Castelli, Maria João Freitas
Casa dos Marcos is the largest specialized medical and residential center for rare diseases in the Iberian Peninsula. The large number of patients and the uniqueness of their diseases demand a considerable amount of diverse and highly personalized therapies, that are nowadays largely managed manually. This paper aims at catering for the emergent need of efficient and effective artificial intelligence systems for the support of the everyday activities of centers like Casa dos Marcos. We present six predictive data models developed with a genetic programming based system which, integrated into a web-application, enabled data-driven support for the therapists in Casa dos Marcos. The presented results clearly indicate the usefulness of the system in assisting complex therapeutic procedures for children suffering from rare diseases.
A Knowledge Based Differential Evolution Algorithm for Protein Structure Prediction
Pedro Henrique Narloch, Marcio Dorn
Three-dimensional protein structure prediction is an open-challenging problem in Structural Bioinformatics and classified as an NP-hard problem in computational complexity theory. As exact algorithms cannot solve this type of problem, metaheuristics became useful strategies to find solutions in viable computational time. In this way, we analyze four standard mutation mechanisms present in Differential Evolution algorithms using the Angle Probability List as a source of information to predict tertiary protein structures, something not explored yet with Differential Evolution. As the balance between diversification and intensification is an essential fact during the optimization process, we also analyzed how the Angle Probability List might influence the algorithm behavior, something not investigated in other algorithms. Our tests reinforce that the use of structural data is a crucial factor to reach better results. Furthermore, combining experimental data in the optimization process can help the algorithm to avoid premature convergence, maintaining population diversity during the whole process and, consequently, reaching better conformational results.
Influence of Local Selection and Robot Swarm Density on the Distributed Evolution of GRNs
Iñaki Fernández Pérez, Stéphane Sanchez
Distributed Embodied Evolution (dEE) is a powerful approach to learn behaviors in robot swarms by exploiting their intrinsic parallelism: each robot runs an evolutionary algorithm, and locally shares its learning experience with other nearby robots. Given the distributed nature of this approach, dEE entails different evolutionary dynamics when compared to standard centralized Evolutionary Robotics. In this paper, we investigate the distributed evolution of Gene Regulatory Networks (GRNs) as controller representation to learn swarm robot behavior, which have been extensively used for the evolution of single- robot behavior with remarkable success. Concretely, we use dEE to evolve fixed-topology GRN swarm robot controllers for an item collection task; this constitutes the first work to evolve GRNs in distributed swarm robot settings. To improve our understanding of such distributed GRN evolution, we analyze the fitness and the behavioral diversity of the swarm over generations when using 5 levels of increasing local selection pressure and 4 different swarm sizes, from 25 to 200 robots. Our experiments reveal that there exist different regimes, depending on the swarm size, in the relationship between local selection pressure, and both behavioral diversity and overall swarm performance, providing several insights on distributed evolution. We further use a metric to quantify selection pressure in evolutionary systems, which is based on the correlation between number of offspring and fitness of the behaviors. This reveals a complex relationship on the overall selection pressure between the ability or ease to spread genomes (or environmental pressure), and the fitness of the behavior (or task-oriented (local) pressure), opening new research questions. We conclude the paper by discussing the need for developing specialized statistical tools to facilitate the analysis of the large and diverse amount of data relevant to distributed Embodied Evolution.
Particle Swarm Optimization: Understanding Order-2 Stability Guarantees
This paper's primary aim is to provide clarity on which guarantees about particle stability can actually be made. The particle swarm optimization algorithm has undergone a considerable amount of theoretical analysis. However, with this abundance of theory has come some terminological inconstancies, and as a result it is easy for a practitioner to be misguided by overloaded terminology. Specifically, the criteria for both order-1 and order-2 stability are well studied, but the exact definition of order-2 stability is not consistent amongst researchers. A consequence of this inconsistency in terminology is that the existing theory may in fact misguide practitioners instead of assisting them. In this paper it is theoretically and empirically demonstrated which practical guarantees can in fact be made about particle stability. Specifically, it is shown that the definition of order-2 stability which accurately reflects PSO behavior is that of convergence in second order moment to a constant, and not to zero.
A Biased Random Key Genetic Algorithm with Local Search Chains for Molecular Docking
Pablo Felipe Leonhart, Marcio Dorn
Molecular Docking is an essential tool in the drug discovery process. The procedure for finding the best energy affinity between ligand-receptor molecules is a very computationally expensive optimization process because of the roughness of the search space and the thousands of possible conformations of ligand. In this way, besides a realistic energy function to evaluate possible solutions, a robust search method must be applied to avoid local minimums. Recently, many algorithms have been proposed to solve the docking problem, mainly based on Evolutionary Strategies. However, the problem remained unsolved and its needed the development of new and efficient techniques. In this paper, we developed a Biased Random Key Genetic Algorithm, as global search, hybridized with three variations of Hill-climbing and a Simulated Annealing version, as local search strategies. To evaluate the receptor-ligand binding affinity we used the Rosetta scoring function. The proposed approaches have been tested on an adequate benchmark of protein-ligand complexes and compared to existing tools AUTODOCK VINA, DOCKTHOR, and jMETAL. A statistical test was performed on the results, and shown that the application of local search methods provides better solutions for the molecular docking problem.
Design of Powered Floor Systems for Mobile Robots with Differential Evolution
Eric Medvet, Stefano Seriani, Alberto Bartoli, Paolo Gallina
Mobile robots depend on power for performing their task. Powered floor systems, i.e., surfaces with conductive strips alternatively connected to the two poles of a power source, are a practical and effective way for supplying power to robots without interruptions, by means of sliding contacts. Deciding where to place the sliding contacts so as to guarantee that a robot is actually powered irrespective of its position and orientation is a difficult task. We here propose a solution based on Differential Evolution: we formally define problem-specific constraints and objectives and we use them for driving the evolutionary search. We validate experimentally our proposed solution by applying it to three real robots and by studying the impact of the main problem parameters on the effectiveness of the evolved designs for the sliding contacts. The experimental results suggest that our solution may be useful in practice for assisting the design of powered floor systems.
Solving the Multi-Objective Flexible Job-Shop Scheduling Problem with Alternative Recipes for a Chemical Production Process
Piotr Dziurzanski, Shuai Zhao, Jerry Swan, Leandro Indrusiak, Sebastian Scholze, Karl Krone
This paper considers a new variant of a multi-objective flexible job-shop scheduling problem, featuring multisubset selection of manufactured recipes. We propose a novel associated chromosome encoding and customise the classic MOEA/D multi-objective genetic algorithm with new genetic operators. The applicability of the proposed approach is evaluated experimentally and showed to outperform typical multi-objective genetic algorithms. The problem variant is motivated by real-world manufacturing in a chemical plant and is applicable to other plants that manufacture goods using alternative recipes.
Body Symmetry in Morphologically Evolving Modular Robots
T. van de Velde, C. Rossi, A.E. Eiben
Almost all animals natural evolution has produced on Earth have a symmetrical body. In this paper we investigate the evolution of body symmetry in an artificial system where robots evolve. To this end, we define several measures to quantify symmetry in modular robots and see how these relate to fitness that corresponds to a locomotion task. We find that, although there is only a weak correlation between symmetry and fitness over the course of a single evolutionary run, there is a positive correlation between the level of symmetry and maximum fitness when a set of runs is taken into account.
Evolutionary successful strategies in a transparent iterated Prisoner's Dilemma
Anton M. Unakafov, Thomas Schultze, Igor Kagan, Sebastian Moeller, Alexander Gail, Stefan Treue, Stephan Eule, Fred Wolf
A Transparent game is a game-theoretic setting that takes action visibility into account. In each round, depending on the relative timing of their actions, players have a certain probability to see their partner's choice before making their own decision. This probability is determined by the level of transparency. At the two extremes a game with zero transparency is equivalent to the classical simultaneous game, and a game with maximal transparency corresponds to a sequential game. Despite the prevalence of intermediate transparency in many everyday interactions such scenarios have not been sufficiently studied. Here we consider a transparent iterated Prisoner's dilemma (iPD) and use evolutionary simulations to investigate how and why the success of various strategies changes with the level of transparency. We demonstrate that non-zero transparency greatly reduces the set of successful memory-one strategies compared to the simultaneous iPD. For low and moderate transparency the classical "Win - Stay, Lose - Shift" (WSLS) strategy is the only evolutionary successful strategy. For high transparency all strategies are evolutionary unstable in the sense that they can be easily counteracted, and, finally, for maximal transparency a novel "Leader-Follower" strategy outperforms WSLS. Our results provide a partial explanation for the fact that the strategies proposed for the simultaneous iPD are rarely observed in nature, where high levels of transparency are common.
Evolutionary Algorithms for the Design of Quantum Protocols
Walter Krawec, Stjepan Picek, Domagoj Jakobovic
In this paper, we use evolutionary algorithm to evolve customized quantum key distribution (QKD) protocols designed to counter attacks against the system in order to optimize the speed of the secure communication. This is in contrast to most work in QKD protocols, where a fixed protocol is designed and then its security is analyzed to determine how strong an attack it can withstand. We show that our system is able to find protocols that can operate securely against attacks where ordinary QKD protocols would fail. Our algorithm evolves protocols as quantum circuits, thus making the end result potentially easier to implement in practice.
Memetic Evolution of Classification Ensembles
Szymon Piechaczek, Michal Kawulok, Jakub Nalepa
Creating classification ensembles may be perceived as a regularization technique which aims at improving the generalization capabilities of a classifier. In this paper, we introduce a multi-level memetic algorithm for evolving classification ensembles (they can be either homo- or heterogeneous). First, we evolve the content of such ensembles, and then we optimize the weights (both for the classifiers and for different classes) exploited while voting. The experimental study showed that our memetic algorithm retrieves high-quality heterogeneous ensembles, and can effectively deal with small training sets in multi-class classification.
Self-sustainability Challenges of Plants Colonization Strategies in Virtual 3D Environments
Kevin Godin-Dubois, Sylvain Cussat-Blanc, Yves Duthen
The Biosphere is a bountiful source of inspiration for the biologically inclined scientist, though one may be seized by the twists and turns of its complexity. Artificial Life emerged from the conundrum of condensing this overwhelming intricacy into a tractable volume of data. To tackle the challenge of studying the long-term dynamics of artificial ecosystems, we focused our efforts on plant-plant interactions in a 3D setting. Through an extension of K. Sims' directed graphs, we devised a polyvalent genotype for artificial plants development. These individuals compete and collaborate with one another in a shared plot of earth with the environment playing a crucial part in the phenotype's expression. We illustrate and analyze how the use of multi-objective fitnesses generated a panel of diverse morphologies and strategies. Furthermore we identify two driving forces of the emerge of self-reproduction and investigate their effect on self-sustainability.
Quantifying the effects of increasing user choice in MAP-Elites applied to a Workforce Scheduling and Routing Problem
Neil Urquhart, Emma Hart, William Hutcheson
Quality-diversity algorithms such as MAP-Elites provide a means of supporting the users when finding and choosing solutions to a problem by returning a set of solutions which are diverse according to set of user-defined features. The number of solutions that can potentially be returned by MAP-Elites is controlled by a parameter that discretises the user-defined features into `bins'. For a fixed evaluation budget, increasing the number of bins increases user-choice, but at the same time, can lead to a reduction in overall quality of solutions while vice-versa, decreasing the number of bins can lead to higher-quality solutions at the expense of reducing choice. The goal of this paper is to explicitly quantify this trade-off, through a study of the application of Map-Elites to a Workforce Scheduling and Routing problem, using large realistic instances based in London and Edinburgh. We note that for the problems under consideration 30 bins or above maximises coverage (and therefore the choice to the end user), whilst fewer bins maximise performance.
Evolutionary Computation Techniques for Constructing SAT-based Attacks in Algebraic Cryptanalysis
Artyom Pavlenko, Alexander Semenov, Vladimir Ulyantsev
In this paper we present the results on applying evolutionary computation techniques to construction of several cryptographic attacks. In particular, SAT-based guess-and-determine attacks studied in the context of algebraic cryptanalysis. Each of these attacks is built upon some set of Boolean variables, thus it can be specified by a Boolean vector. We use two general evolutionary strategies to find an optimal vector: (1+1)-EA and GA. Based on these strategies the parallel algorithms (based on modern SAT-solvers) for solving the problem of minimization of a special pseudo-Boolean function are implemented. This function is a fitness-function used to evaluate the runtime of a guess-and-determine attack. We compare the effectiveness of (1+1)-EA and GA with the algorithm from the Tabu search class, that was earlier used to solve related problems. Our implementation of GA algorithm showed the best results on a number of test instances, in the role of which we used the cryptanalysis problems of several stream ciphers (cryptographic keystream generators).
Ensemble-based Evolutionary Algorithms for Detecting Known and Unknown Attacks
Hasanen Alyasiri, Daniel Kudenko, John Clark
The internet and computer networks have become an important asset in distributed computing organisations especially through enabling the collaboration between components of heterogeneous systems. As they have grown in popularity, so have the numbers of attacks on them. Threats are becoming more sophisticated, with attackers using new attacks or modifying existing ones. Thus, security teams must deal with numerous threats and the threat landscape is continuously evolving. We investigate the use of Evolutionary Computation (EC) algorithms for synthesising intrusion detection programs for such environments. EC algorithms extended with the ensemble-learning paradigm, indicating how EC can be used as a stacking technique to evolve detectors. The experiments were conducted on up-to-date datasets and compared with state-of-the-art algorithms. The potential application of these algorithms to detect unknown attacks is also examined and discussed.
Trophallaxis, Low-power Vision Sensors andMulti-objective Heuristics for 3D Scene Reconstruction using Swarm Robotics
Maria Carrillo, Javier Sanchez-Cubillo, Eneko Osaba, Miren Nekane Bilbao, Javier Del Ser
A profitable strand of literature has lately capitalized on the exploitation of the collaborative capabilities of robotic swarms for efficiently undertaking diverse tasks without any human intervention, ranging from the blind exploration of devastated areas after massive disasters to mechanical repairs of industrial machinery in hostile environments, among others. However, most contributions reported to date deal only with robotic missions driven by a single task-related metric to be optimized by the robotic swarm (e.g. tardiness to complete the commanded mission), even though other objectives such as energy consumption may conflict with the imposed goal. In this paper multi-objective heuristic solvers are used to command and route a set of robots towards efficiently reconstructing a scene using simple camera sensors and stereo vision processing techniques. The need for resorting to multi-objective heuristics stems, among other modeling and computational aspects, from the consideration of energy efficiency as a second target of the mission plan. In this regard, the modeled scenario also incorporates energy trophallaxis within the swarm, i.e. specific robots capable of recharging other members of the swarm in favor of an increased overall autonomy. A robotic simulation environment is arranged to shed light on the performance of different heuristic algorithms over a realistically emulated physical environment. The obtained results stimulate further research lines aimed at considering decentralized heuristics for the considered problem.
The Evolution of Self-taught Neural Networks in a Multi-agent Environment
Nam Le, Michael O'Neill, Anthony Brabazon
Evolution and learning are two different forms of adaptation by which the organism can change their behaviour to cope with problems posed by the environment. The second form of adaptation occurs when individuals exhibit plasticity in response to environmental conditions that may strengthen their survival. Learning has been shown to be beneficial to the evolutionary process through the Baldwin Effect. This line of thought has also been employed in evolving adaptive neural networks, in which learning algorithms, such as Backpropagation, can be used to enhance the adaptivity of the population. Most work focuses on evolving learning agents in separate environments, this means each agent experiences its own environment (mostly similar), and has no interactive effect on others (e.g., the more one gains, the more another loses). The competition for survival in such settings is not that strong, if being compared to that of a multi-agent (or shared) environment . This paper investigates an evolving population of self-taught neural networks -- networks that can teach themselves -- in a shared environment. Experimental results show that learning has an impact more on increasing the performance of the whole multi-agent system, rather than on individual agents. Indications for future work on evolving neural networks are also presented.
Early Detection of Botnet Activities using Grammatical Evolution
Selim Yilmaz, Sevil Sen
There have been numerous studies proposed for detecting botnets in the literature. However, it is still a challenging issue as most of the proposed systems are unable to detect botnets in their early stage and they cannot perform satisfying performance on new forms of botnets. In this study, we propose an evolutionary computation-based approach that relies on grammatical evolution to generate a botnet detection algorithm automatically. The performance of the proposed method reveals that it detects botnets accurately in their very early stage and outperforms most of the existing methods.
Coevolution of Generative Adversarial Networks
Victor Costa, Nuno Lourenço, Penousal Machado
Generative adversarial networks (GAN) became a hot topic, presenting impressive results in the field of computer vision. However, there are still open problems with the GAN model, such as the training stability and the hand-design of architectures. Neuroevolution is a technique that can be used to provide the automatic design of network architectures even in large search spaces as in deep neural networks. Therefore, this project proposes COEGAN, a model that combines neuroevolution and coevolution in the coordination of the GAN training algorithm. The proposal uses the adversarial characteristic between the generator and discriminator components to design an algorithm using coevolution techniques. Our proposal was evaluated in the MNIST dataset. The results suggest the improvement of the training stability and the automatic discovery of efficient network architectures for GANs. Our model also partially solves the mode collapse problem.
On the Use of Evolutionary Computation for In-Silico Medicine: Modelling Sepsis via Evolving Continuous Petri Nets
Ahmed Hallawa, Elisabeth Zechendorf, Yi Song, Anke Schmeink, Lukas Martin, Gedo Dartmann, Gerd Ascheid
Sepsis is the leading cause of death in non-surgical intensive care units. Continuous Petri Nets (CPNs) offer a promising solution in modelling its pathophysiological process. In this work, we propose a framework to evolve CPNs, i.e. evolve places, transitions, arc weights, topology, and kinetics. This facilitates modeling complex biological systems, including sepsis signalling pathway using limited experimental data. Inspired by Neuroevolution of Augmenting Toplogies (NEAT), which is adopted in Artificial Neural Networks (ANNs), our framework includes a genotype to phenotype mapping based on the CPN incidence matrix, and a fitness function, which consider both the behaviour of the evolving CPN and its emerging structural complexity. We tested our framework on ten different cases with different complexity structures. In the worst case, results show the NMSE less than 2% in the learning phase, and MSE of 13% in the validation phase. Furthermore, we conducting cell culture experiments by exposing cardiomyocytes to Heparan Sulfate (HS), which activated the intrinsic apoptosis signal pathway. Using the output of these experiments, the proposed framework was able to evolve a CPN to model this pathway with an MSE value of 10% in the verification phase.
Evolving Robots on Easy Mode: Towards a Variable Complexity Controller for Quadrupeds
Tønnes F. Nygaard, Charles P. Martin, Jim Torresen, Kyrre Glette
There are many challenges when it comes to evolving control and morphology for physical robot systems. When relying on physics simulations for evolving robots for complicated environments or tasks, a flexible gait controller is needed. This allows for specialization to the particular demands of a given setting through many evaluations. Other times, evolution might be done exclusively in hardware, or for simpler environments, and a less flexible controller could work just as well, and be optimized with far fewer evaluations. Traditionally, only gait controllers with a static balance between these two goals have been available. In this paper, we introduce a new controller where the complexity of the controller can be set by a single parameter, using a dynamic genotype-phenotype mapping. Low controller complexity results in simple and conservative gaits, while higher complexity allows the more extreme controllers needed to achieve high performance in demanding environments or tasks, at the cost of a longer period of optimization. We investigate the new controller on a virtual robot in simulations, and do preliminary testing on a physical robot in the real world. We show that having variable complexity allows us to adapt to different optimization budgets, which is especially important when doing evolution in the real world.
A Hybrid Multiobjective Differential Evolution Approach to Stator Winding Optimization
André Silva, Fernando Ferreira, Carlos Antunes
This paper describes a multiobjective differential evolution approach to the optimization of the design of alternating current distributed stator windings of electric motors. The objective functions are minimizing both the machine airgap magnetomotive force distortion and the winding wire length. Constraints are related to the physical feasibility of solutions. Four distinct winding types are considered. Three mutation variations of the multiobjective differential evolution algorithm are developed and assessed using different performance metrics. These algorithmic approaches are able to generate well-distributed, uniformly spread solutions on the nondominated front. The characterization of the nondominated fronts conveys helpful information for aiding design engineers to choose the most suitable compromise solution for a specific machine, embodying a balanced trade-off between machine efficiency and manufacturing cost.
Evolving Recurrent Neural Networks for Time Series Data Prediction of Coal Plant Parameters
AbdElRahman ElSaid, Steven Benson, Shuchita Patwardhan, David Stadem, Travis Desell
This paper presents the Evolutionary eXploration of Augmenting LSTM Topologies (EXALT) algorithm and its use in evolving recurrent neural networks (RNNs) for time series data prediction. It introduces a new open data set from a coal-fired power plant, consisting of 10 days of per minute sensor recordings from 12 different burners at the plant. This large scale real world data set involves complex depedencies between sensor parameters and makes for challening data to predict. EXALT provides interesting new techniques for evolving neural networks, including epigenetic weight initialization, where child neural networks re-use parental weights as a starting point to backpropagation, as well as node-level mutation operations which can improve evolutionary progress. EXALT has been designed with parallel computation in mind to further improve performance. Preliminary results were gathered predicting the Main Flame Intensity data parameter, with EXALT strongly outperforming five traditional neural network architectures on the best, average and worse cases across 10 repeated training runs per test case; and was only slightly behind the best trained Elman recurrent neural networks while being significantly more reliable (i.e., much better average and worst case results). Further, EXALT achived these results 2 to 10 times faster than the traditional methods, in part due to its scalability, showing strong potential to beat traditional architectures given additional runtime.
Fundamental Flowers: Evolutionary Discovery of Coresets for Classification
Pietro Barbiero, Alberto Tonda
In an optimization problem, a coreset can be defined as a subset of the input points, such that a good approximation to the optimization problem can be obtained by solving it directly on the coreset, instead of using the whole original input. In machine learning, coresets are exploited for applications ranging from speeding up training time, to helping humans understand the fundamental properties of a class, by considering only a few meaningful samples. The problem of discovering coresets, starting from a dataset and an application, can be defined as identifying the minimal amount of samples that do not significangly lower performance with respect to the performance on the whole dataset. Specialized literature offers several approaches to finding coresets, but such algorithms often disregard the application, or explicitly ask the user for the desired number of points. Starting from the consideration that finding coresets is an intuitively multi-objective problem, as minimizing the number of points goes against maintaining the original performance, in this paper we propose a multi-objective evolutionary approach to identifying coresets for classification. The proposed approach is tested on classical machine learning classification benchmarks, using 6 state-of-the-art classifiers, comparing against 7 algorithms for coreset discovery. Results show that not only the proposed approach is able to find coresets representing different compromises between compactness and performance, but that different coresets are identified for different classifiers, reinforcing the assumption that coresets might be closely linked to the specific application.
Exploring concurrent and stateless evolutionary algorithms
JJ Merelo, JLJ lAREDO, Pedro Castillo, Mario Garcia Valdez, Sergio Rojas
Creating a concurrent and stateless version of an evolutionary algorithm implies changes in its behavior. From the performance point of view, the main challenge is to balance computation with communication, but from the algorithmic point of view we have to keep diversity high so that the algorithm is not stuck in local minima. In a concurrent setting, we will have to find the right balance so that improvements in both fields do not cancel out. This is what we will be doing in this paper, where we explore the space of parameters of a population based concurrent evolutionary algorithm to find out the best combination for a particular problem.
Evolving Trust Formula to Evaluate Data Trustworthiness in VANETs Using Genetic Programming
Mehmet Aslan, Sevil Sen
Vehicular Ad Hoc Networks (VANETs) provide traffic safety, improve traffic efficiency and present infotainment by sending messages about events on the road. Trust is widely used to distinguish genuine messages from fake ones. However, trust management in VANETs is a challenging area due to their dynamically changing and decentralised topology. In this study, a genetic programming based trust management model for VANETs is proposed to properly evaluate trustworthiness of data about events. A large number of features is introduced in order to take into account VANETs' complex characteristics. Simulations with bogus information attack scenarios show that the proposed trust model considerably increase the security of the network.
GA-Novo: De Novo Peptide Sequencing via Tandem Mass Spectrometry using Genetic Algorithm
Samaneh Azari, Bing Xue, Mengjie Zhang, Lifeng Peng
Proteomics is the large-scale analysis of the proteins. The common method for identifying proteins and characterising their amino acid sequences is to digest the proteins into peptides, analysing the peptides using mass spectrometry and assign the resulting tandem mass spectra (MS/MS) to peptides using database search tools. However, database search algorithms are highly dependent on a reference protein database and they cannot identify peptides and proteins not included in the database. Therefore, de novo sequencing algorithms are developed to overcome the problem by directly reconstructing the peptide sequence of an MS/MS spectrum without using any protein database. Current de novo sequencing algorithms often fail to construct the completely matched sequences, and produce partial matches. In this study, we pro- pose a genetic algorithm based method, GA-Novo, to solve the complex optimisation task of de novo peptide sequencing, aiming at constructing full length sequences. Given an MS/MS spectrum, GA-Novo optimises the amino acid sequences to best fit the input spectrum. On the test- ing dataset, GA-Novo outperforms PEAKS, the the most commonly used software for this task, by constructing 4% higher number of fully matched peptide sequences, and 8% higher recall at partially matched sequences.
Genetic Programming for Feature Selection and Feature Combination in Salient Object Detection
Shima Afzali, Harith Al-Sahaf, Bing Xue, Christopher Hollitt, Mengjie Zhang
Salient Object Detection (SOD) aims to model human visual attention system to cope with the complex natural scene which contains various objects at different scales. Over the past two decades, a wide range of saliency features have been introduced in the SOD field, however feature selection has not been widely investigated regarding selecting informative, non-redundant, and complementary features from the exciting features. In SOD, multi-level feature extraction and feature combination are two fundamental stages to compute the final saliency map. However, designing a good feature combination framework is a challenging task and requires domain-expert intervention. In this paper, we propose a genetic programming (GP) based method that is able to automatically select the complementary saliency features and generate mathematical function to combine those features. The performance of the proposed method is evaluated using four benchmark datasets and compared to nine state-of-the-art methods. The qualitative and quantitative results show that the proposed method significantly outperformed, or achieved comparable performance to, the competitor methods.
A Matheuristic for Green and Robust 5G Virtual Network Function
Fabio D'Andreagiovanni, Andreas Kassler, Chenghao Wang
We investigate the problem of optimally placing virtual network functions in 5G virtualized infrastructures according to a green paradigm that pursues energy efficiency. This optimization problem can be modelled as an articulated 0-1 Linear Program based on a flow model. Since the problem can prove hard to solve, even for instances of moderate size, for a state-of-the-art optimization solver, we propose a new fast matheuristic for its solution. Preliminary computational results on a set of realistic instances show that our algorithm can find solutions of higher quality in sensibly less time than a state-of-the-art solver.
Ant Colony Optimization for Optimized Operation Scheduling of Combined Heat and Power Plants
Johannes Mast, Stefan Rädle, Joachim Gerlach, Oliver Bringmann
In the worldwide expansion of renewable energies, there is not only a need for weather-dependent plants, but also for plants with flexible power generation that have the potential to reduce storage requirements by working against fluctuations. A highly promising technology is provided by Combined heat and power (CHP) plants, which achieve high efficiencies through the simultaneous generation of electricity and heat. This is why they are also being promoted by the European Union. Also, the construction of biogas plants is usually linked to the construction of CHP plants in order to generate energy from the emission-free produced biogas. However, until now CHP plants have mostly been operated by heat demand (just like boilers), causing the generated electricity often to put additional stress on the power grid. The planning of a CHP plant, whose generated heat always finds a consumer and the generated electricity is simultaneously optimized with regard to an optimization objective, requires nonlinear optimization approaches due to the physical effects in the heat storage. This paper presents a methodology for optimized planning of CHP plants using Ant Colony Optimization. The selected optimization objectives are the power exchange, the tenant electricity and CO2. It could be shown that all optimizations are at least 10% better than the heat-led operation. The best results were achieved with the electricity exchange optimization that can be up to 24% more profitable than a CHP in a heat-led mode.
Variable length representation for EC-based feature selection in high-dimensional data
Nicole Dalia Cilia, Claudio De Stefano, Francesco Fontanella, Alessandra Scotto di Freca
Feature selection is a challenging problem, especially when hundreds or thousands of features are involved. Evolutionary Computation based techniques and in particular genetic algorithms, because of their ability to explore large and complex search spaces, have proven to be effective in solving such kind of problems. Though genetic algorithms binary strings provide a natural way to represent feature subsets, several different representation schemes have been proposed to improve the performance, with most of them needing to a priori set the number of features. In this paper, we propose a novel variable length representation, in which feature subsets are represented by lists of integers. We also devised a crossover operator to cope with the variable length representation. The proposed approach has been tested on several datasets and the results compared with those achieved by a standard genetic algorithm. Results of comparisons demonstrated the effectiveness of the proposed approach in improving the performance obtainable with a standard genetic algorithm when thousand of features are involved.
Improving NeuroEvolution Efficiency by Surrogate Model-based Optimization with Phenotypic Distance Kernels
Jörg Stork, Martin Zaefferer, Thomas Bartz-Beielstein
In NeuroEvolution, the topologies of artificial neural networks are optimized with evolutionary algorithms to solve tasks in data regression, data classification, or reinforcement learning. One downside of NeuroEvolution is the large amount of necessary fitness evaluations, which might render it inefficient for tasks with expensive evaluations, such as real-time learning. For these expensive optimization tasks, surrogate model-based optimization is frequently applied as it features a good evaluation efficiency. While a combination of both procedures appears as a valuable solution, the definition of adequate distance measures for the surrogate modeling process is difficult. In this study, we will extend cartesian genetic programming of artificial neural networks by the use of surrogate model-based optimization. We propose different distance measures and test our algorithm on a replicable benchmark task. The results indicate that we can significantly increase the evaluation efficiency and that a phenotypic distance, which is based on the behavior of the associated neural networks, is most promising.
GAMER: A Genetic Algorithm with Motion Encoding Reuse for action-adventure video games
Tasos Papagiannis, Georgios Alexandridis, Andreas Stafylopatis
Genetic Algorithms (GAs) have been predominantly used in video games for finding the best possible sequence of actions that leads to a win condition. This work sets out to investigate an alternative application of GAs on action-adventure type video games. The main intuition is to encode actions depending on the state of the world of the game instead of the sequence of actions, like most of the other GA approaches do. Additionally, a methodology is being introduced which modifies a part of the agent's logic and reuses it in another game. The proposed algorithm has been implemented in the GVG-AI competition's framework and more specifically for the Zelda and Portals games. The obtained results, in terms of average score and win percentage, seem quite satisfactory and highlight the advantages of the suggested technique, especially when compared to a rolling horizon GA implementation of the aforementioned framework; firstly, the agent is efficient at various levels (different world topologies) after being trained in only one of them and secondly, the agent may be generalized to play more games of the same category.
Introducing Weighted Intermediate Recombination in On-line Collective Robotics
Weighted intermediate recombination has been proven very useful in evolution strategies. We propose here to use it in the case of on-line embodied evolutionary algorithms. With this recombination scheme, solutions at the local populations are recombined using a weighted aver- age that favors fitter solutions to produce a new solution. We describe the newly proposed algorithm which we dubbed (mu/muW,1)-On-line EEA, and assess it performance on two swarm robotics benchmarks while com- paring the results to other existing algorithms. The experiments show that the recombination scheme is very beneficial on these problems.
A Cultural Algorithm for Determining Similarity Values Between Users in Recommender Systems
Kalyani Selvarajah, Ziad Kobti, Mehdi Kargar
Recommendation systems for online marketing often rely on users' ratings to evaluate the similarity between users in Collaborative Filtering (CF) recommender systems. This paper applies knowledge- based evolutionary optimization algorithms called Cultural Algorithms (CA) to evaluate the similarity between users. To deal with the sparsity of data, we combine CF with a trust network between users. The trust network is then clustered using Singular Value Decomposition (SVD) which helps to discover the top neighbors' trust value. By incorporat- ing trust relationships with CF, we predict the rating by each user on a given item. This study uses the Epinions dataset in order to train and test the accuracy of the results of the approach. The results are then compared against those produced by Genetic Algorithms (GA), Cosine, and Pearson Correlation Coeficient (PCC) methods. The comparison of the results suggests that the proposed algorithm outperforms the other similarity functions.
A flexible similarity measure for active and passive 3D structures and its application in the fitness-distance analysis
Maciej Komosinski, Agnieszka Mensfelt
Evolutionary design of 3D structures - either static structures, or equipped with some sort of a control system - is one of the hardest optimization tasks. One of the reasons are rugged fitness landscapes resulting from complex and non-obvious genetic representations of such structures. This paper investigates global convexity of fitness landscapes in optimization tasks of maximizing velocity and height of both active and passive structures. For this purpose, a new similarity measure for 3D active and passive structures represented as undirected graphs is introduced. The proposed measure is general and flexible -- any vertex properties can be easily incorporated as similarity components. The new measure was compared against the previously introduced measure in terms of triangle inequality satisfiability, changes in raw measure values and the computational cost. The comparison revealed improvements for triangle inequality and raw values at the expense of increased computational complexity. The investigation of global convexity of the fitness landscape, involving the fitness--distance correlation analysis, revealed positive correlation between the similarity of structures and their fitness for most of the investigated cases.
Prolong the network lifetime of Wireless Underground Sensor Networks by optimal relay node placement
Binh Huynh Thi Thanh, Hung Tran Huy, Tam Nguyen Thi, Dung Dinh Anh, Vinh Le Trong
Wireless Underground Sensor Networks (WUSNs) have received attention in the past years because of their popularity and cost effectiveness when they are used in many real fields such as military applications, environmental applications, and home applications. In WUSNs, sensors are deployed with limited power, once their power is out of, the sensors are ineffectual. The extension of the network's lifetime is a critical issue in WUSNs, making it a topic of much interest in research. Several approaches have been proposed to keep the sensor nodes active, one of which is deploying relay nodes above ground to transfer data from sensor nodes to the base station. However, this method has faced issues, such as balancing the load of relay nodes and the increased transmission loss between relay nodes and sensor nodes. This paper addresses this concern and proposes heuristics for relay nodes placement problem to guarantee load balance among relay nodes and maximize network lifetime.The experimental results show that the proposed methods result in quality solutions for the problem, when compared to existing methods
Metamorph Reinforcement Learning in Adaptive Games
Iago Bonnici, Abdelkader Gouaïch, Fabien Michel
Adaptive Games (AG) involve a controller agent that continuously feeds from player actions and game state to tweak a set of game parameters and maintain or achieve an objective function. This can be considered a Rein- forcement Learning (RL) situation, so that classical Machine Learning (ML) ap- proaches can be used. For instance, the objective function can represent player’s experience such as the flow measure defined by Csíkszentmihályi. In such games, the adaptation scheme is designed to reach and maintain this objective. On the other hand, many games naturally exhibit an incremental gameplay where new actions and elements are introduced or removed progressively to enhance player’s learning curve or to introduce variety within the game. This makes the RL situa- tion unusual because the controller agent input/output signature can change over the course of learning. In this paper, we get interested in this unusual “meta- morph” RL situation (mRL), In particular, we assess how the learner can rely on its past shapes and experience to keep improving among signature changes with- out needing to start the learning from scratch on each change. We have first devel- oped a rigorous formalization of the mRL problem. Then, we have started explor- ing the incremental addition of inputs with Recurrent Neural Networks (RNNs) in an artificial metamorph Supervised Learning (mSL) situation. As an first re- sult, we find that it is possible to benefit from prior learning in RNNs even if the past controller agent signature differs in its number of inputs. The using of mRL in AG thus remains encouraged. Investigating output addition, input/output removal and translating these results from mSL to actua
An Unorthodox Evolutionary Algorithm for Antivirus Signature Optimization
This work presents a methodology able to significantly improve ma- chine-generated signatures for detecting Android Malware. The technique re- lies on an population-less estimation of probability evolutionary algorithm, using an unorthodox fitness function able to incorporate unsystematic human experts’ knowledge, in the form of a set of rules of thumb. Experimental results show that the optimized signatures are more accurate, lowering both false positives and negatives.