GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation ConferenceFull Citation in the ACM Digital Library
SESSION: Real world applications
Sustainable forest management is a crucial element in combating climate change, plastic pollution, and other unsolved challenges of the 21st century. Forests not only produce wood - a renewable resource that is increasingly replacing fossil-based materials - but also preserve biodiversity and store massive amounts of carbon. Thus, a truly optimal forest policy has to balance profit-oriented logging with ecological and societal interests, and should thus be solved as a multi-objective optimization problem. Economic forest research, however, has largely focused on profit maximization. Recent publications still scalarize the problem a priori by assigning weights to objectives. In this paper, we formulate a multi-objective forest management problem where profit, carbon storage, and biodiversity are maximized. We obtain Pareto-efficient forest management strategies by utilizing three state-of-the-art Multi-Objective Evolutionary Algorithms (MOEAs), and by incorporating domain-specific knowledge through customized evolutionary operators. An analysis of Pareto-efficient strategies and their harvesting schedules in the design space clearly shows the benefits of the proposed approach. Unlike many EMO application studies, we demonstrate how a systematic post-optimality trade-off analysis can be applied to choose a single preferred solution. Our pioneering work on sustainable forest management explores an entirely new application area for MOEAs with great societal impact.
Simultaneously searching and solving multiple avoidable collisions for testing autonomous driving systems
The oracle problem is a key issue in testing Autonomous Driving Systems (ADS): when a collision is found, it is not always clear whether the ADS is responsible for it. Our recent search-based testing approach offers a solution to this problem by defining a collision as avoidable if a differently configured ADS would have avoided it. This approach searches for both collision scenarios and the ADS configurations capable of avoiding them. However, its main problem is that the ADS configurations generated for avoiding some collisions are not suitable for preventing other ones. Therefore, it does not provide any guidance to automotive engineers for improving the safety of the ADS. To this end, we propose a new search-based approach to generate configurations of the ADS that can avoid as many different types of collisions as possible. We present two versions of the approach, which differ in the way of searching for collisions and alternative configurations. The approaches have been experimented on the path planner component of an ADS provided by our industry partner.
Substitution boxes (S-boxes) are nonlinear mappings that represent one of the core parts of many cryptographic algorithms (ciphers). If S-box does not possess good properties, a cipher would be susceptible to attacks. To design suitable S-boxes, we can use heuristics as it allows significant freedom in the selection of required cryptographic properties. Unfortunately, with heuristics, one is seldom sure how good a trade-off between cryptographic properties is reached or if optimizing for one property optimizes implicitly for another property. In this paper, we consider what is to the best of our knowledge, the most detailed analysis of trade-offs among S-box cryptographic properties. More precisely, we ask questions if one property is optimized, what is the worst possible value for some other property, and what happens if all properties are optimized. Our results show that while it is possible to reach a large variety of possible solutions, optimizing for a certain property would commonly result in good values for other properties. In turn, this suggests that a single-objective approach should be a method of choice unless some precise values for multiple properties are needed.
In the context of the introduction of renewable energies in France, Nuclear Power Plant Operations (NPPO) are a key component for the compensation of the intermittent production of solar and wind power. In this work, we focus on the optimization of the operation cost and stability of power of a real-life power transient, while maintaining safety standards. From an optimization point of view, the NPPO problem is a typical example of a discrete constrained bi-objective problem based on time expensive computation simulation. We propose a massive asynchronous parallel master/workers MOEA/D assisted by a surrogate models. The algorithm design components are discussed and argued in this work. We show that our proposed surrogate assistance is able to improve algorithm performance and reliability, allowing us to extend our approach to a large range of strategic future real-life operations.
Genetic algorithms are 0th-order methods and therefore praised in many non-differentiable optimization problems, which encompass the majority of real world applications. In this work, a multiobjective optimization of hybrid, i.e. multi-material, components under technological constraints is performed to guide engineers towards the optimal design of manufactured parts in competition-driven industries, like in the automotive or the aerospace sector. Specifically, three of the main challenges Original Equipment Manufacturers (OEMs) face nowadays are met : simultaneously minimizing compliance, weight and cost. This is achieved by replacing pure metallic components with lightweight materials such as thermoplastics and composites. However, a mere substitution would not be appropriate because it would usually result in insufficient performances or expensive designs. The task of the genetic algorithm is hence to find the optimal material distribution using Voronoï tessellations on a fixed Finite Element (FE) mesh while complying with the manufacturing methods of thermoplastics and composites. The Voronoï encoding has a great advantage over traditional Bit-Array genotypes : its size is independent of the FE mesh granularity, therefore refining the mesh has no impact on the computational cost of the genetic algorithm's operators. Experimental results on the cantilever beam test case show Pareto optimal material distributions.
With the increased size and frequency of wildfire events worldwide, accurate real-time prediction of evolving wildfire fronts is a crucial component of firefighting efforts and forest management practices. We propose a cellular automaton (CA) that simulates the spread of wildfire. We embed the CA inside of a genetic program (GP) that learns the state transition rules from spatially registered synthetic wildfire data. We demonstrate this model's predictive abilities by testing it on unseen synthetically generated landscapes. We compare the performance of a genetic program (GP) based on a set of primitive operators and restricted expression length to null and logistic models. We find that the GP is able to closely replicate the spreading behavior driven by a balanced logistic model. Our method is a potential alternative to current benchmark physics-based models.
Non-deterministic journey planning in multi-modal transportation networks: a meta-heuristic approach
Multi-modal journey planning, which allows multiple modes of transport to be used within a single trip, is becoming increasingly popular, due to a vast practical interest and the increasing availability of data. In real-life situations, transport networks often involve uncertainty, and yet, most approaches assume a deterministic environment, making plans more prone to failures such as significant delays in the arrival or waiting for a long time at stations. In this paper, we tackle the multi-criteria stochastic journey planning problem in multi-modal transportation networks. We consider the problem as a probabilistic conditional planning problem, and we use Markov Decision Processes to model the problem. Journey plans are optimised simultaneously against five criteria, namely: travel time, journey convenience, monetary cost, CO2, and personal energy expenditure (PEE). We develop an NSGA-III-based solver as a baseline search method for producing optimal policies for travelling from a given origin to a given destination. Our empirical evaluation uses Melbourne transportation network using probabilistic density functions for estimated departure/arrival time of the trips. Numerical results demonstrate the effectiveness of the proposed method for practical purposes and provide strong evidence in favour of contingency planning for journey planning problem.
A memetic level-based learning swarm optimizer for large-scale water distribution network optimization
Potable water distribution networks are requisites of modern cities. Because of the city expansion, nowadays, the scale of the network grows rapidly, which brings great difficulty to its optimization. Evolutionary computation methods have been widely investigated on small-scale networks, but their performance is far from satisfactory on large-scale networks. Aimed at addressing this difficulty, a new memetic algorithm called level-based learning swarm optimizer with restart and local search is proposed in this paper to solve the large-scale water distribution network optimization problem. Instead of using traditional evolutionary computation algorithms, the level-based learning swarm optimizer that is especially proposed for large-scale optimization problems is applied as the population-based optimizer. Two restart strategies are incorporated to make the algorithm more effective. They can help the algorithm jump out from local optima thus to increase its exploration ability. Moreover, a simple yet effective local search algorithm is proposed based on the domain knowledge to further refine the solutions after the algorithm converges. Experimental results on both single-source and multi-source large-scale water distribution networks show that the proposed algorithm is more effective than the state-of-the-art evolutionary computation algorithms.
The application of Evolutionary Algorithms (EAs) to real-world problems comes with inherent challenges, primarily the difficulty in defining the large number of considerations needed when designing complex systems such as Water Distribution Networks (WDN). One solution is to use an Interactive Evolutionary Algorithm (IEA), which integrates a human expert into the optimisation process and helps guide it to solutions more suited to real-world application. The involvement of an expert provides the algorithm with valuable domain knowledge; however, it is an intensive task requiring extensive interaction, leading to user fatigue and reduced effectiveness. To address this, the authors have developed methods for capturing human expertise from user interactions utilising machine learning to produce Human-Derived Heuristics (HDH) which are integrated into an EA's mutation operator. This work focuses on the development of an adaptive method for applying multiple HDHs throughout an EA's search. The new adaptive approach is shown to outperform both singular HDH approaches and traditional EAs on a range of large scale WDN design problems. This work paves the way for the development of a new type of IEA that has the capability of learning from human experts whilst minimising user fatigue.
Convolutional Neural Network (CNN) dataflow inference accelerators implemented in Field-Programmable Gate Arrays (FPGAs) have demonstrated increased energy efficiency and lower latency compared to CNN execution on CPUs or GPUs. However, the complex shapes of CNN parameter memories do not typically map well to FPGA On-Chip Memories (OCM), which results in poor OCM utilization and ultimately limits the size and types of CNNs which can be effectively accelerated on FPGAs. In this work, we present a design methodology that improves the mapping efficiency of CNN parameters to FPGA OCM. We frame the mapping as a bin packing problem and determine that traditional bin packing algorithms are not well suited to solve the problem within FPGA- and CNN-specific constraints. We hybridize genetic algorithms and simulated annealing with traditional bin packing heuristics to create flexible mappers capable of grouping parameter memories such that each group optimally fits FPGA on-chip memories. We evaluate these algorithms on a variety of FPGA inference accelerators. Our hybrid mappers converge to optimal solutions in a matter of seconds for all CNN use-cases, achieve an increase of up to 65% in OCM utilization efficiency for deep CNNs, and are up to 200× faster than current state-of-the-art simulated annealing approaches.
The selection of ElectroEncephaloGram (EEG) features with functional relevance to Motor Imagery (MI) is a crucial task for successful outcome in Brain-Computer Interface (BCI)-based motor rehabilitation. Individual EEG patterns during MI requires subject-dependent feature selection, which is an arduous task due to the complexity and large number of features. One solution is to use metaheuristics, e.g. Genetic Algorithm (GA), to avoid an exhaustive search which is impractical. In this work, one of the most widely used GA, NSGA-II, is used with an hierarchical individual representation to facilitate the exclusion of EEG channels irrelevant for MI. In essence, the performance of different objectives in NSGA-II was evaluated on a previously recorded MI EEG data set. Empirical results show that k-Nearest Neighbors (k-NN) combined with Pearson's Correlation (PCFS) as objective functions yielded higher classification accuracy as compared to the other objective-combinations (73% vs. 69%). Linear Discriminant Analysis (LDA) combined with Feature Reduction (FR) as objective functions maximized the reduction of features (99.6%) but reduced classification performance (65.6%). All classifier objectives combined with PCFS selected similar features in accordance with expected activity patterns during MI. In conclusion, PCFS and a classifier as objective functions constitutes a good trade-off solution for MI data.
Energy is essential for all countries, since it is in the core of social and economic development. Since the industrial revolution, the demand for energy has increased exponentially. It is expected that the energy consumption in the world increases by 50% by 2030 . As such, managing the demand of energy is of the uttermost importance. The development of tools to model and accurately predict the demand of energy is very important to policy makers. In this paper we propose the use of the Structured Grammatical Evolution (SGE) algorithm to evolve models of energy demand, over macro-economic indicators. The proposed SGE is hybridised with a Differential Evolution approach in order to obtain the parameters of the models evolved which better fit the real energy demand. We have tested the performance of the proposed approach in a problem of total energy demand estimation in Spain, where we show that the SGE is able to generate extremely accurate and robust models for the energy prediction within one year time-horizon.
Wave energy is a fast-developing and promising renewable energy resource. The primary goal of this research is to maximise the total harnessed power of a large wave farm consisting of fully-submerged three-tether wave energy converters (WECs). Energy maximisation for large farms is a challenging search problem due to the costly calculations of the hydrodynamic interactions between WECs in a large wave farm and the high dimensionality of the search space. To address this problem, we propose a new hybrid multi-strategy evolutionary framework combining smart initialisation, binary population-based evolutionary algorithm, discrete local search and continuous global optimisation. For assessing the performance of the proposed hybrid method, we compare it with a wide variety of state-of-the-art optimisation approaches, including six continuous evolutionary algorithms, four discrete search techniques and three hybrid optimisation methods. The results show that the proposed method performs considerably better in terms of convergence speed and farm output.
Hybrid genetic algorithm for ridesharing with timing constraints: efficiency analysis with real-world data
Ridesharing is an effective, affordable and environment-friendly way of transportation. This paper proposes a Hybrid Genetic Algorithm(HGA) using elements from Simulated Annealing(SA) and Local search(LS) which is very suitable for Ridesharing related applications. The designed algorithm efficiently handles advanced constraints like timing windows for pick-up, detour time(or distance), and waiting-time minimization.
To quantify the effectiveness of HGA for the Ridesharing problem, we study Ridesharing as a close variant of the Orienteering Problem(OP) and Orienteering Problem with Time Windows(OPTW). Both these problems have been extensively studied and have many benchmark data sets. The experiments performed on popular benchmark instances of orienteering problems show that HGA for orienteering problems outperforms all the available algorithms in the literature. Further, for many of the instances, our HGA has discovered solutions that are better than the current Best Known solutions. Using our HGA for orienteering problems, we have developed a prototype system for Ridesharing. The experiments using real-world New York taxi trip data  shows that the system ensures that about 40%-50% of the rides could have been shared, and 60%-70% of customers could have shared rides. The detailed data analysis shows how to tune the parameters for the system to achieve the best possible performance.
Automated design of multi-level network partitioning heuristics employing self-adaptive primitive granularity control
Network segmentation has a variety of applications, including computer network security. A well segmented computer network is less likely to result in information leaks and more resilient to adversarial traversal. Conventionally network segmentation approaches rely on graph partitioning algorithms. However, general-purpose graph partitioning solutions are just that, general purpose. These approaches do not exploit specific topological characteristics present in certain classes of networks. Tailored partition methods can be developed to target specific domains, but this process can be time consuming and difficult. This work builds on previous research employing generative hyper-heuristics in the form of genetic programming for automating the development of customized graph partitioning heuristics by incorporating a dynamic approach to controlling the granularity of the heuristic search. The potential of this approach is demonstrated using two real-world complex network applications. Results show that the automated design process is capable of fine tuning graph partitioning heuristics that sacrifice generality for improved performance on targeted networks.
Real-world problems such as computational fluid dynamics simulations and finite element analyses are computationally expensive. A standard approach to mitigating the high computational expense is Surrogate-Based Optimization (SBO). Yet, due to the high-dimensionality of many simulation problems, SBO is not directly applicable or not efficient. Reducing the dimensionality of the search space is one method to overcome this limitation. In addition to the applicability of SBO, dimensionality reduction enables easier data handling and improved data and model interpretability. Regularization is considered as one state-of-the-art technique for dimensionality reduction. We propose a hybridization approach called Regularized-Surrogate-Optimization (RSO) aimed at overcoming difficulties related to high-dimensionality. It couples standard Kriging-based SBO with regularization techniques. The employed regularization methods are based on three adaptations of the least absolute shrinkage and selection operator (LASSO). In addition, tree-based methods are analyzed as an alternative variable selection method. An extensive study is performed on a set of artificial test functions and two real-world applications: the electrostatic precipitator problem and a multilayered composite design problem. Experiments reveal that RSO requires significantly less time than standard SBO to obtain comparable results. The pros and cons of the RSO approach are discussed, and recommendations for practitioners are presented.
A genetic programming approach to feature construction for ensemble learning in skin cancer detection
Ensembles of classifiers have proved to be more effective than a single classification algorithm in skin image classification problems. Generally, the ensembles are created using the whole set of original features. However, some original features can be redundant and may not provide useful information in building good ensemble classifiers. To deal with this, existing feature construction methods that usually generate new features for only a single classifier have been developed but they fit the training data too well, resulting in poor test performance. This study develops a new classification method that combines feature construction and ensemble learning using genetic programming (GP) to address the above limitations. The proposed method is evaluated on two benchmark real-world skin image datasets. The experimental results reveal that the proposed algorithm has significantly outperformed two existing GP approaches, two state-of-the-art convolutional neural network methods, and ten commonly used machine learning algorithms. The evolved individual that is considered as a set of constructed features helps identify prominent original features which can assist dermatologists in making a diagnosis.
Through malware, cyber criminals can leverage our computing resources to disrupt our work, steal our information, and even hold it hostage. Security professionals seek to classify these malicious software so as to prevent their distribution and execution, but the sheer volume of malware complicates these efforts. In response, machine learning algorithms are actively employed to alleviate the workload. One such approach is evolutionary computation, where solutions are bred, rather than built. In this paper, we design, develop and evaluate a system, COUGAR, to reduce high-dimensional malware behavioural data, and optimize clustering behaviour using a multi-objective genetic algorithm. Evaluations demonstrate that each of our chosen clustering algorithms can successfully highlight groups of malware. We also present an example real-world scenario, based on the testing data, to demonstrate practical applications.