GECCO '18- Proceedings of the Genetic and Evolutionary Computation ConferenceFull Citation in the ACM Digital Library
SESSION: Real world applications
Large-scale parallelization of partial evaluations in evolutionary algorithms for real-world problems
The importance and potential of Gray-Box Optimization (GBO) with evolutionary algorithms is becoming increasingly clear lately both for benchmark and real-world problems. We consider the GBO setting where partial evaluations are possible, meaning that sub-functions of the evaluation function are known and can be exploited to improve optimization efficiency. In this paper, we show that the efficiency of GBO can be greatly improved through large-scale parallelism, exploiting the fact that each evaluation function requires the calculation of a number of independent sub-functions. This is especially interesting for real-world problems where often the majority of the computational effort is spent on the evaluation function. Moreover, we show how the best parallelization technique largely depends on factors including the number of sub-functions and their required computation time, revealing that for different parts of the optimization the best parallelization technique should be selected based on these factors. As an illustration, we show how large-scale parallelization can be applied to optimization of high-dose-rate brachytherapy treatment plans for prostate cancer. We find that use of a modern Graphics Processing Unit (GPU) was the most efficient parallelization technique in all realistic scenarios, leading to substantial speed-ups up to a factor of 73.
With increasing demand for air travel and overloaded airport facilities, inefficient airport taxiing operations are a significant contributor to unnecessary fuel burn and a substantial source of pollution. Although taxiing is only a small part of a flight, aircraft engines are not optimised for taxiing speed and so contribute disproportionately to the overall fuel burn. Delays in taxiing also waste scarce airport resources and frustrate passengers. Consequently, reducing the time spent taxiing is an important investment. An exact algorithm for finding shortest paths based on A* allocates routes to aircraft that maintains aircraft at a safe distance apart, has been shown to yield efficient taxi routes. However, this approach depends on the order in which aircraft are chosen for allocating routes. Finding the right order in which to allocate routes to the aircraft is a combinatorial optimization problem in itself.
We apply a rolling window approach incorporating a genetic algorithm for permutations to this problem, for real-world scenarios at three busy airports. This is compared to an exhaustive approach over small rolling windows, and the conventional first-come-first-served ordering. We show that the GA is able to reduce overall taxi time with respect to the other approaches.
Genetic programming has been successfully applied to several real-world problem domains. One such application area is image classification, wherein genetic programming has been used for a variety of problems such as breast cancer detection, face detection, and pedestrian detection, to name a few. We present the use of genetic programming for detecting active tuberculosis in raw X-ray images. Our results demonstrate that genetic programming evolves classifiers that achieve promising accuracy results compared to that of traditional image classification techniques. Our classifiers do not require pre-processing, segmentation, or feature extraction beforehand. Furthermore, our evolved classifiers process a raw X-ray image and return a classification orders of magnitude faster than the reported times for traditional techniques.
There is increasing impetus towards 'Industry 4.0', a recently proposed roadmap for process automation across a broad spectrum of manufacturing industries. The proposed approach uses Evolutionary Computation to optimise real-world metrics. Features of the proposed approach are that it is generic (i.e. applicable across multiple problem domains) and decentralised, i.e. hosted remotely from the physical system upon which it operates. In particular, by virtue of being serverless, the project goal is that computation can be performed 'just in time' in a scalable fashion. We describe a case study for value-based optimisation, applicable to a wide range of manufacturing processes. In particular, value is expressed in terms of Overall Equipment Effectiveness (OEE), grounded in monetary units. We propose a novel online stopping condition that takes into account the predicted utility of further computational effort. We apply this method to scheduling problems in the (max, +) algebra, and compare against a baseline stopping criterion with no prediction mechanism. Near optimal profit is obtained by the proposed approach, across multiple problem instances.
RateSetter: roadmap for faster, safer, and better platform train interface design and operation using evolutionary optimisation
There is a challenge ahead in the rail industry to accommodate increased demand. Time spent at the platform train interface (PTI) as passengers board and alight, rather than on the move, represents a limitation on system capacity. To overcome this, we propose RateSetter: an evolutionary optimiser that for the first time provides more effective PTI design choices based on passenger flow time and safety. An agent based passenger simulation model validated with CCTV footage is employed for fitness evaluation. The initial results provide guidelines not only for future PTI designs but also for retrofit designs to existing infrastructure, evaluating the effectiveness and diminishing returns of PTI features for the considered scenarios. Furthermore, it is observed that the proposed optimal PTI designs could significantly reduce the flow time for the cases examined. Results show that retro-fit designs could reduce the flow time in the range of 10%-35%.
Surrogate Model Based Optimization (SMBO) is an established technique for handling computationally expensive optimization problems. One important application is the optimization of Particle Reinforced Metal Matrix Composites (PRMMCs). Multi-phase materials are gaining attention. Their performance is strongly affected by microscale properties. By optimizing the microscale structure, these materials can be tailored to satisfy specific requirements. Current manufacturing techniques have limited control over the distribution of reinforcing particles and are subject to considerable uncertainty. Moreover, the simulation and optimization of PRMMCs requires significant computational effort. We propose an approach that tackles the problem of optimizing the characteristics of PRMMCs subject to uniaxial load, by improving the particles' spatial distribution. The optimization problem is split into a bilevel problem: The upper-level optimization aims to find the particle distribution parameters which maximize the PRMMC limit load. Due to potentially infeasible distributions, the lower-level problem attempts to create a particle placement that reflects the specifications of an upper-level candidate solution.
We employ an SMBO approach that combines Kriging, Sequential Parameter Optimization, and a Genetic Algorithm. Experimental results indicate that our approach can find promising solutions within few evaluations, handles uncertainty, and allows insight into the most important effects on the limit load.
Optimizing residential energy resources with an improved multi-objective genetic algorithm based on greedy mutations
Energy management is increasingly becoming an important issue in face of the penetration of renewable generation and the evolution to smart grids. Home energy management systems are aimed to make the integrated optimization of residential energy resources, taking into account energy prices and end-user's requirements. This paper addresses a residential scenario where energy resources are automatically managed to reduce the overall energy cost while considering a set of user-defined comfort preferences. These energy resources include the grid, shiftable appliances, thermostatic loads, static batteries, electric vehicles, and local energy production. The comfort specifications consist of the time slots where the shiftable appliances are preferred to operate and the temperature ranges desired for the thermostatically controlled loads. The conflicting objectives are addressed by a multi-objective genetic algorithm that aims to minimize the overall energy cost and the user's dissatisfaction. This paper proposes a set of novel operators that result in statistically significant improvements in terms of hypervolume values when compared to a recently proposed genetic algorithm customized to address this same scenario. These novel operators include a different population initialization, a greedy mutation, and two geometric crossovers. The effect of the proposed operators on the resulting allocation of energy resources is analyzed.
We suggest a use of genetic programming for transformation from a vector space to an understandable graph representation, which is part of a project to inspect the latent space in matrix factorization. Given a relation matrix, we can apply standard techniques such as non-negative matrix factorization to extract low dimensional latent space in vector representation. While the vector representation of the latent space is useful, it is not intuitive and hard to interpret. The transformation with the help of genetic programming allows us to better understand the underlying latent structure. Applying the method in the context of a stock market, we show that it is possible to recover the tree representation of technical patterns from a relation matrix. Leveraging the properties of the vector representations, we are able to find patterns that correspond to cluster centers of technical patterns. We further investigate the geometry of the latent space.
Multi-modal journey planning, which allows multiple modes of transport to be used within a single trip, is becoming increasingly popular, due to a strong practical interest and an 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 major delays in the arrival or waiting for a long time at stations. In this paper, we tackle the multi-objective stochastic journey planning problem in multi-modal transportation networks. The problem is modeled as a Markov decision process with two objective functions: expected arrival time and journey convenience. We develop a GA-based MDP solver as a baseline search method for producing optimal policies for traveling 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 suggest that the proposed method is effective for practical purposes and provide strong evidence in favor of switching from deterministic to non-deterministic planning.
In this paper we show how genetic algorithms can be effectively applied to study the security of arbitrary quantum key distribution (QKD) protocols when faced with adversaries limited to current-day technology. We compare two approaches, both of which take into account practical limitations on the quantum power of an adversary (which can be specified by the user). Our system can be used to determine upper-bounds on noise tolerances of novel QKD protocols in this scenario, thus making it a useful tool for researchers. We compare our algorithm's results with current known numerical results, and also evaluate it on newer, more complex, protocols where no results are currently known.
Predicting friction system performance with symbolic regression and genetic programming with factor variables
Friction systems are mechanical systems wherein friction is used for force transmission (e.g. mechanical braking systems or automatic gearboxes). For finding optimal and safe design parameters, engineers have to predict friction system performance. This is especially difficult in real-worlds applications, because it is affected by many parameters.
We have used symbolic regression and genetic programming for finding accurate and trustworthy prediction models for this task. However, it is not straight-forward how nominal variables can be included. In particular, a one-hot-encoding is unsatisfactory because genetic programming tends to remove such indicator variables. We have therefore used so-called factor variables for representing nominal variables in symbolic regression models. Our results show that GP is able to produce symbolic regression models for predicting friction performance with predictive accuracy that is comparable to artificial neural networks. The symbolic regression models with factor variables are less complex than models using a one-hot encoding.
Insider threat detection represents a challenging problem to companies and organizations where malicious actions are performed by authorized users. This is a highly skewed data problem, where the huge class imbalance makes the adaptation of learning algorithms to the real world context very difficult. In this work, applications of genetic programming (GP) and stream active learning are evaluated for insider threat detection. Linear GP with lexicase/multi-objective selection is employed to address the problem under a stationary data assumption. Moreover, streaming GP is employed to address the problem under a non-stationary data assumption. Experiments conducted on a publicly available corporate data set show the capability of the approaches in dealing with extreme class imbalance, stream learning and adaptation to the real world context.
This paper concerns using evolutionary algorithms for optimization in epidemics prevention. Spreading of the epidemic is simulated on a graph and the goal of optimization is to determine which vertices in the graph to vaccinate in order to minimize the number of vertices affected by the epidemic. Decisions whether to vaccinate a vertex or not are represented using a binary genotype.
In this paper an informed mutation operator is introduced. The presented operator uses machine learning approach for determining which positions in the genotype to flip. The learning model used in the paper is a neural network trained using graph-based features of the vertices (such as a vertex degree) and the information how often on average a given vertex is infected. Once trained, the learning model helps determine which positions in the current solution to mutate. Results presented in the paper suggest that the proposed informed operator improves the ability of the evolutionary algorithm to produce good solutions to the tackled problem. Interestingly, a very good generalization was achieved. The model built using problem instances with 1000 vertices in the graph improved solutions for problem instances with up to 20000 vertices.
The security of cryptographic algorithms (such as block ciphers and hash functions) is often evaluated in terms of their output randomness. This paper presents a novel method for the statistical randomness testing of cryptographic primitives, which is based on the evolutionary construction of the so-called randomness distinguisher. Each distinguisher is represented as a Boolean polynomial in the Algebraic Normal Form. The previous approach, in which the distinguishers were developed in two phases by means of the brute-force method, is replaced with a more scalable evolutionary algorithm (EA). On seven complex datasets, this EA provided distinguishers of the same quality as the previous approach, but the execution time was in practice reduced 40 times. This approach allowed us to perform a more efficient search in the space of Boolean distinguishers and to obtain more complex high-quality distinguishers than the previous approach.
Agent-based crowd simulation is a widely used technique for designing and evaluating human-in-the-loop situations such as evacuation plans and building design. Valid evaluation requires a correct model of an individual agent's action rule, which causes human behavior in a crowd. However, in general, designing a specific action rule of each agent depends strongly on a trial-and-error approach because a real crowd shows diverse behaviors.
To avoid trial-and-error approaches, we specifically examine an automated method to estimate an agent's strategy to select a goal state from trajectories extracted from a human's action log. The previous method assumes a homogeneous strategy, meaning that all agents have a common strategy, but to reproduce the diversity of a real crowd it is more natural to assume a heterogeneous strategy: not all agents have the same strategy.
Our proposed method of estimating individual and different strategies of agents can estimate a heterogeneous strategy that incorporates readability by evolutionary computation, even for trajectories that are the result not only of homogeneous strategies but also of heterogeneous strategies. The experiment results demonstrate the validity of our method. Additionally, some cases exhibiting multiple strategies will be extracted for a single trajectory. They show applicability to actual action log data.
In order to address environmental concerns and meet growing energy demand the development of green energy technology has expanded tremendously. One of the most promising types of renewable energy is ocean wave energy. While there has been strong research in the development of this technology to date there remain a number of technical hurdles to overcome. This research explores a type of wave energy converter (WEC) called a buoy. This work models a power station as an array of fully submerged three-tether buoys. The target problem of this work is to place buoys in a size-constrained environment to maximise power output. This article improves prior work by using a more detailed model and exploring the search space using a wide variety of search heuristics. We show that a hybrid method of stochastic local search combined with Nelder-Mead Simplex direct search performs better than previous search techniques.
We consider the area of intelligent road vehicles, especially, the topic of automated vehicles. Focusing on the importance of the automated steering, we address the challenge of automated keeping of a car in the middle of the driving lane. Our objective is to investigate the feasibility of employing genetic programming (GP) to evolve the automated steering of a car. The latter is implemented in the Open Source Racing Car Simulator (TORCS) with a realistically modeled steering featuring both a delay of response and a rate limit. We propose two approaches aimed at improving the efficiency of evolution via GP. In the first approach we implement an incremental evolution of the steering function by commencing the evolution with an ideal car and gradually increasing the degree of its realism (i.e., the amount of steering delay) in due course of evolution. The second approach is based on incorporating expert knowledge about the (expected) structure of the steering function according to the servo control model of steering. The experimental results verify that the proposed approaches yield an improved efficiency of evolution in that the obtained solutions are both of a better quality and could be obtained faster than those of the canonical GP.
Multi-objective aerodynamic design with user preference using truncated expected hypervolume improvement
Multi-objective optimization in aerodynamic design plays an important role in capturing the trade-off and useful knowledge that would be useful for real-world design processes. In the preliminary design phase, aerodynamic designers usually have an interest in focusing the optimization process in a certain direction of interest. To this end, we propose the use of user preference multi-objective Bayesian global optimization (MOBGO) for aerodynamic design using truncated expected hypervolume improvement (TEHVI). Taking into account the apriori knowledge of objective functions, TEHVI acts as an infill criterion to search for the optimal solutions based on the Kriging models in MOBGO. In TEHVI-MOBGO, the first step is to obtain a coarse approximation of the Pareto front in order to capture the general trend and trade off using standard EHVI; following this step, TEHVI is then applied to focus the search on a defined region of interest. We demonstrate the capabilities and usefulness of TEHVI method on the design optimization of an inviscid transonic wing and a viscous transonic airfoil in order to minimize the drag coefficient and absolute value of pitching moment, which leads to a reduced fuel burn and easier control characteristic.
Impacts of constraints and constraint handling strategies for multi-objective mechanical design problems
Multi-objective optimization tools are becoming increasingly popular in mechanical engineering and allow decision-makers to better understand the inevitable trade-offs. Mechanical design problems can however combine properties that make the use of optimization more complex: (i) expensive cost functions; (ii) discrete or step-like behavior of the cost functions; and (iii) non-linear constraints. The latter in particular has a great impact on the convergence and the diversity of the obtained Pareto front.
In this paper, we present five bi-objective mechanical design optimization problems with various levels of constraint complexity. They are used to rigorously benchmark two common constraint handling strategies (constrained-dominance and penalty function). The results suggest that both strategies have similar performance, and that as constraints become more intricate, convergence to the best-known Pareto front is not guaranteed. Indeed, analyzing the evolution of the hypervolume along generations reveals that the optimizer can get trapped in local optima. A detailed analysis of the obtained Pareto fronts for the proposed problems allows us to qualify the effects of the different constraints.
The availability of several CPU cores on current computers enables parallelization and increases the computational power significantly. Optimization algorithms have to be adapted to exploit these highly parallelized systems and evaluate multiple candidate solutions in each iteration. This issue is especially challenging for expensive optimization problems, where surrogate models are employed to reduce the load of objective function evaluations.
This paper compares different approaches for surrogate model-based optimization in parallel environments. Additionally an easy to use method, which was developed for an industrial project, is proposed. All described algorithms are tested with a variety of standard benchmark functions. Furthermore, they are applied to a real-world engineering problem, the electrostatic precipitator problem. Expensive computational fluid dynamics simulations are required to estimate the performance of the precipitator. The task is to optimize a gas-distribution system so that a desired velocity distribution is achieved for the gas flow throughout the precipitator. The vast amount of possible configurations leads to a complex discrete valued optimization problem. The experiments indicate that a hybrid approach works best, which proposes candidate solutions based on different surrogate model-based infill criteria and evolutionary operators.
Real-world evolutionary design optimizations of complex shapes can efficiently be solved using linear deformation representations, but the optimization performance crucially depends on the initial deformation setup. For instance, when modeling the deformation by radial basis functions (RBF) the convergence speed depends on the condition number of the involved kernel matrix, which previous work therefore tried to optimize through careful placement of RBF kernels. We show that such representation-specific techniques are inherently limited and propose a generic, representation-agnostic optimization based on orthogonalization of the deformation matrix. This straightforward black-box optimization projects any given linear deformation setup to optimal condition number without changing its design space, which, as we show through extensive numerical experiments, can boost the convergence speed of evolutionary optimizations by up to an order of magnitude.
Project Scheduling Problem (PSP) plays a crucial role in large-scale software development, directly affecting the productivity of the team and on-time delivery of software projects. PSP concerns with the decision of who does what and when during the software project lifetime. PSP is a combinatorial optimisation problem and inherently NP-hard, indicating that approximation algorithms are highly advisable for real-world instances which are often large in size. In this work, we propose an iterated local search (ILS) algorithm for PSP. ILS is a simple, yet effective for combinatorial optimisation problems. However, its performance highly depends on its perturbation operator which is to guide the search to new starting points. Hereby, we propose a Genetic Programming (GP) approach to evolve perturbation operators based on a range of low-level operators and rules. The evolution process will go along with the iterated search process and supply better operators continuously. The GP based ILS algorithm is tested using a set of well known PSP benchmark instances and compared with state-of-the-art algorithms. The experimental results demonstrated the effectiveness of GP generated perturbation operators as they can outperform existing leading methods.
With an explosive increase in data traffic over recent years, it has become increasingly difficult to rely on outdoor base stations to support the traffic generated indoors mainly due to the penetration issue of wireless signals. Mobile operators have investigated different options to provide adequate capacity and good in-building coverage such as by deploying femtocells, Wi-Fi off-load or in-building distributed antenna systems (IB-DAS). A passive IB-DAS extends indoor coverage by connecting antennas to a base station through coaxial cables and passive components. This paper focuses on automated design of IB-DAS based on the real world requirements of a telecom service provider. A Genetic Algorithm (GA) is derived for this purpose, giving consideration to different factors, such as minimizing cabling and passive splitter costs, reducing power spillage and power deviation between the required and supplied power for antennas. The solution representation of the problem and the customized genetic operators to assist the evolution are described. The experimental results showing the effectiveness of the GA model on a number of different scenarios are also presented. The built model is incorporated into a software tool, which is being trialled by our industrial partner, delivering encouraging results, saving cost and design time.
Consumer-grade printers are widely available, but their ability to print complex objects is limited. Therefore, new designs need to be discovered that serve the same function, but are printable. A representative such problem is to produce a working, reliable mechanical spring. The proposed methodology for discovering solutions to this problem consists of three components: First, an effective search space is learned through a variational autoencoder (VAE); second, a surrogate model for functional designs is built; and third, a genetic algorithm is used to simultaneously update the hyperparameters of the surrogate and to optimize the designs using the updated surrogate. Using a car-launcher mechanism as a test domain, spring designs were 3D-printed and evaluated to update the surrogate model. Two experiments were then performed: First, the initial set of designs for the surrogate-based optimizer was selected randomly from the training set that was used for training the VAE model, which resulted in an exploitative search behavior. On the other hand, in the second experiment, the initial set was composed of more uniformly selected designs from the same training set and a more explorative search behavior was observed. Both of the experiments showed that the methodology generates interesting, successful, and reliable spring geometries robust to the noise inherent in the 3D printing process. The methodology can be generalized to other functional design problems, thus making consumer-grade 3D printing more versatile.
Better and faster catheter position optimization in HDR brachytherapy for prostate cancer using multi-objective real-valued GOMEA
The recently-introduced Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) family has been shown to be capable of excellent performance on academic benchmark problems, outperforming other state-of-the-art EAs, especially when efficient partial evaluations are possible. This holds true also for the latest extension, the Multi-Objective Real-Valued GOMEA (MO-RV-GOMEA). In this paper, we apply MO-RV-GOMEA to the real-world multi-objective optimization problem of catheter placement in High-Dose-Rate (HDR) brachytherapy for prostate cancer, a problem that is non-trivial to solve and has high real-world importance and relevance. Due to the underlying geometric structure of the real-valued variables, partial evaluations can be performed, allowing MO-RV-GOMEA to exploit this structure. The performance of MO-RV-GOMEA is tested on three real-world patient cases and compared to a recent state-of-the-art mixed-integer EA that is aimed at a restricted version of the problem. We find that with MO-RV-GOMEA better solutions can be found much faster, making our proposed approach much more realistic to be used in clinical practice, and enabling new insights into both catheter placement for prostate brachytherapy and on objectives used for automated treatment planning. First results indicate that richer problem models are needed to better match real-world clinical preferences.
Symbolic regression and feature construction with GP-GOMEA applied to radiotherapy dose reconstruction of childhood cancer survivors
The recently introduced Gene-pool Optimal Mixing Evolutionary Algorithm for Genetic Programming (GP-GOMEA) has been shown to find much smaller solutions of equally high quality compared to other state-of-the-art GP approaches. This is an interesting aspect as small solutions better enable human interpretation. In this paper, an adaptation of GP-GOMEA to tackle real-world symbolic regression is proposed, in order to find small yet accurate mathematical expressions, and with an application to a problem of clinical interest. For radiotherapy dose reconstruction, a model is sought that captures anatomical patient similarity. This problem is particularly interesting because while features are patient-specific, the variable to regress is a distance, and is defined over patient pairs. We show that on benchmark problems as well as on the application, GP-GOMEA outperforms variants of standard GP. To find even more accurate models, we further consider an evolutionary meta learning approach, where GP-GOMEA is used to construct small, yet effective features for a different machine learning algorithm. Experimental results show how this approach significantly improves the performance of linear regression, support vector machines, and random forest, while providing meaningful and interpretable features.
Estimating cement compressive strength from microstructural images using GEP with probabilistic polarized similarity weight tournament selection
The safety of building facilities is directly affected by the physical properties of cement, among which cement compressive strength plays the most important role in evaluating them. Therefore, the investigation of cement compressive strength is helpful in improving the cement properties. Traditionally, chemical composition, curing condition, and water-cement ratio are used to estimate the strength of cement paste. However, this approach is limited by the extreme complexity of physical changes and chemical reactions during cement hydration. Considering the cement microstructure contains information related to strength microscopically, microtomography, which can image three-dimensional microstructure, provides scientists with another way to study cement compressive strength nondestructively. This study estimates cement compressive strength using microstructure features extracted from microtomography images and gene expression programming. A probabilistic polarized similarity weight tournament selection operator is also proposed to balance the exploration and exploitation. Experimental results corroborate that the obtained relationship possesses higher estimation accuracy, good interpretability and the evolutionary capability performs well.