GECCO '18- Proceedings of the Genetic and Evolutionary Computation Conference CompanionFull Citation in the ACM Digital Library
SESSION: Hot off the press
Employing multi-objective search to enhance reactive test generation and prioritization for testing industrial cyber-physical systems
Cyber-Physical Systems (CPSs) integrate digital cyber computations with physical processes. Testing these systems in a time consuming task. Furthermore, the input space for test cases is huge, and several issues need to be considered when generating them. In  we tackle the test case generation and prioritization problem for CPSs. The approach is empirically evaluated with four different case studies from different domains and complexities. Five pareto-based algorithms were evaluated and overall, the NSGA-II algorithm outperformed the remaining algorithms. The NSGA-II algorithm improved RS by 43.8% on average for each objective and 49.25% for the Hypervolume quality indicator.
Energy awareness has gained momentum over the last decade in the software industry, as well as in environmentally concious society. Thus, algorithm designers and programmers are paying increasing attention this issue, particularly when handheld devices are considered, given their battery-consuming characteristics. When we focus on Evolutionary Algorithms, few works have attempted to study the relationship between the main features of the algorithm, the problem to be solved and the underlying hardware where it runs. This work presents a preliminary analysis and modeling of energy consumption of EAs. We try to predict it by means of a fuzzy rule-based system, so that different devices are considered as well as a number of problems and Genetic Programming parameters. Experimental results performed show that the proposed model can predict energy consumption with very low error values.
Standard steady state genetic algorithms can hillclimb faster than evolutionary algorithms using standard bit mutation
Genetic Algorithms (GAs) use principles of natural selection to evolve a population of candidate solutions obtained by the recombination of individuals of the current generation. Albeit their huge popularity, providing natural examples where standard GAs provably outperform more traditional mutation-based heuristics has turned out to be a tedious task. In this paper we rigorously prove that a standard steady state (μ+1) GA outperforms any evolutionary algorithm, that relies only on standard bit mutation (SBM) as variation operator, for hillclimbing the classical OneMax benchmark function. In particular, we show that the GA is 25% faster by providing an upper bound of (3/4)en ln n on its expected runtime versus the en ln n expected function evaluations required by any algorithm using only SBM. To achieve the result, we devise a mathematical framework which extends the classical artificial fitness levels method by coupling each level with a Markov chain. This Markov chain allows to bound the improvement probabilities of the current population based on its diversity. In turn it can be appreciated how larger populations sustain diversity for a longer time, effectively giving crossover more chances of finding improved solutions. Since diversity is created via mutation, higher rates than the standard 1/n mutation rate, lead to better upper bounds on the expected runtime. This paper summarises the work that appeared in 1.
Apart from few exceptions, the mathematical runtime analysis of evolutionary algorithms is mostly concerned with expected runtimes. In this work, we argue that stochastic domination is a notion that should be used more frequently in this area. Stochastic domination allows to formulate much more informative performance guarantees than the expectation alone, it allows to decouple the algorithm analysis into the true algorithmic part of detecting a domination statement and probability theoretic part of deriving the desired probabilistic guarantees from this statement, and it allows simpler and more natural proofs.
As particular results, we prove a fitness level theorem which shows that the runtime is dominated by a sum of independent geometric random variables, we prove tail bounds for several classic problems, and we give a short and natural proof for Witt's result that the runtime of any (μ, p) mutation-based algorithm on any function with unique optimum is subdominated by the runtime of a variant of the (1 + 1) EA on the O
This abstract for the Hot-off-the-Press track of GECCO 2018 summarizes work that has appeared in Benjamin Doerr. Better runtime guarantees via stochastic domination. In Evolutionary Computation in Combinatorial Optimization (EvoCOP 2018), pages 1--17. Springer, 2018.
In this paper a recently proposed approach for making a statistical comparison of meta-heuristic stochastic optimization algorithms is presented. The main contribution of this approach is that the ranking scheme is based on the whole distribution, instead of using only one statistic to describe the distribution, such as average or median. Experimental results showed that our approach gives more robust results compared to state-of-the-art approaches in case when the results are affected by outliers or by statistical insignificant differences that could exist between data values.
Evolutionary Computation is used to automatically evolve small cell schedulers on a realistic simulation of a 4G-LTE heterogeneous cellular network. Evolved schedulers are then further augmented by human design to improve robustness. Extensive analysis of evolved solutions and their performance across a wide range of metrics reveals evolution has uncovered a new human-competitive scheduling technique which generalises well across cells of varying sizes. Furthermore, evolved methods are shown to conform to accepted scheduling frameworks without the evolutionary process being explicitly told the form of the desired solution. Evolved solutions are shown to out-perform a human-engineered state-of-the-art benchmark by up to 50%. Finally, the approach is shown to be flexible in that tailored algorithms can be evolved for specific scenarios and corner cases, allowing network operators to create unique algorithms for different deployments, and to postpone the need for costly hardware upgrades. This work appears in full in Fenton et al., "Towards Automation & Augmentation of the Design of Schedulers for Cellular Communications Networks", Evolutionary Computation, 2018. DOI 10.1162/evco_a_00221.
Detection of minimum biomarker features via bi-level optimization framework by nested hybrid differential evolution
Support vector machine (SVM) using full features is a common approach for classifying diseases in healthcare systems. However, little literature reported to use it towards determining minimum features of biomarkers. This study introduced a bilevel mixed-integer optimization framework to detect minimum biomarker features for SVM. We proposed the two-population nested hybrid differential evolution (NHDE) to solve the problem. In case studies, two dominant biomarkers were found. The two-population NHDE algorithm was more efficient to achieve minimum biomarkers compared with one-population NHDE and traditional genetic algorithm.
On botnet detection with genetic programming under streaming data, label budgets and class imbalance
Botnets represent a widely deployed framework for remotely infecting and controlling hundreds of networked computing devices for malicious ends. Traditionally detection of Botnets from network data using machine learning approaches is framed as an offline, supervised learning activity. However, in practice both normal behaviours and Botnet behaviours represent non-stationary processes in which there are continuous developments to both as new services/applications and malicious behaviours appear. This work formulates the task of Botnet detection as a streaming data task in which finite label budgets, class imbalance and incremental/online learning predominate. We demonstrate that effective Botnet detection is possible for label budgets as low as 0.5% when an active learning approach is adopted for genetic programming (GP) streaming data analysis. The full article appears as S. Khanchi et al., (2018) "On Botnet Detection with Genetic Programming under Streaming Data, Label Budgets and Class Imbalance" in Swarm and Evolutionary Computation, 39:139--140. https://doi.org/10.1016/j.swevo.2017.09.008
We propose a novel methodology for binary and multiclass classification that uses genetic programming to construct features for a nearest centroid classifier. The method, coined M4GP, improves upon earlier approaches in this vein (M2GP and M3GP) by simplifying the program encoding, using advanced selection methods, and archiving solutions during the run. In our recent paper, we test this stategy against traditional GP formulations of the classification problem, showing that this framework outperforms boolean and floating point encodings. In comparison to several machine learning techniques, M4GP achieves the best overall ranking on benchmark problems. We then compare our algorithm against state-ofthe-art machine learning approaches to the task of disease classification using simulated genetics datasets with up to 5000 features. The results suggest that our proposed approach performs on par with the best results in literature with less computation time, while producing simpler models.
This abstract summarizes the results reported in the paper . In this paper a new method of performing the local search for the multiobjective Firefighter Problem (FFP) is proposed. The proposed method reduces the size of the neighbourhood in which the local search looks for improved solutions by using heuristics to decide which solutions in the neighbourhood should be visited.
In the paper the proposed local search method is used for improving solutions produced by two commonly used evolutionary algorithms: the MOEA/D and the NSGA-II. In the experiments the proposed method outperformed both the evolutionary algorithms without any local search (the 'None' method) as well as the algorithms combined with the local search visiting all solutions in the neighbourhood (the 'Full' method). Comparison to the local search selecting the same number of solutions as the ED-LS, but at random (the 'Random' method) shows that the proposed heuristics are indeed selecting good solutions to visit.
Presented research can be extended in further studies. One possibility is to study in-depth how to balance computational resources between the evolutionary and local search algorithms. Second possibility is to employ more advanced models instead of the heuristics used in the paper.
Solving rich vehicle routing problems (VRPs) is a vital research topic due to their wide applicability. Although there exist various (meta)heuristics to tackle VRPs, most of them require a practitioner to tune their parameters before the execution. It is challenging in practice, since different algorithm variants often perform well for different scenarios. In this work, we present our adaptive heuristics for this task, in which we benefit from the adaptation schemes executed before the optimization. Extensive experiments backed up with statistical tests revealed that our heuristics is automatically adapted to effectively solve a given transportation problem, and retrieve routing schedules of the state-of-the-art quality.
Through an extensive series of experiments over multiple evolutionary algorithm implementations and 25 problems we showed that parameter space tends to be rife with viable parameters, somewhat in contrast with common lore .
This paper presents the results of the second edition of the Wind Farm Layout Optimization Competition, which was held at the 22nd Genetic and Evolutionary Computation COnference (GECCO) in 2015. During this competition, competitors were tasked with optimizing the layouts of five generated wind farms based on a simplified cost of energy evaluation function of the wind farm layouts. Online and offline APIs were implemented in C++, Java, Matlab and Python for this competition to offer a common framework for the competitors. The top four approaches out of eight participating teams are presented in this paper and their results are compared. All of the competitors' algorithms use evolutionary computation.
SESSION: Late-breaking abstract
The Tagged Visual Cryptography Scheme (TVCS)1 adds tag images to the noise-like shares generated by the traditional VCS to improve the shares management of the traditional VCS. However, the existing TVCSs suffers visual quality of the recovered secret image may be degraded and there may be pixel expansion. This study proposes a Threshold Adaptive Tagged Visual Cryptography Scheme ((k, n)-ATVCS) to solve the above-mentioned problems. The ATVCS encryption problem is formulated in a mathematical optimization model, and an evolutionary algorithm is developed to find the optimal solution to the problem. The proposed (k, n)-ATVCS enables the encryptor to adjust the visual quality between the tag image and the secret image by tuning parameters. Experimental results show the correctness and effectiveness of this study.
Tuning various parameters coexisting in genetic algorithms (GAs) has a direct impact on the performance of GA. Because of this, finding a proper parameter value is challenging. In this study, we use support vector regression to show the appropriate parameter space of GA. Moreover, this was applied and analyzed to solving NK-landscape problems. As a result, we show the complexities and difficulties of GA parameter space through this paper.
Automated architecture search has demonstrated significant success for image data, where reinforcement learning and evolution approaches now outperform the best human designed networks (, ). These successes have not transferred over to models dealing with sequential data, such as in language modeling and translation tasks. While there have been several attempts to evolve improved recurrent cells for sequence data , none have achieved significant gains over the standard LSTM. Recent work has introduced high performing recurrent neural network alternatives, such as Transformer  and Wavenet , but these models are the result of manual human tuning.
Human-based evolutionary computation (HBEC) is evolutionary computation in which agents of implementing evolutionary operators are multiple humans and can solve problems in our human society, where only humans can judge the qualities of their solutions. In this study we add a new function that enables us to follow the solution evolution to our previously developed HBEC system, in which a tag cloud is used as a place for the solution evolution. Also, we show the usability and the traceability of the HBEC system through an experiment.
In this paper, we propose a simple yet effective approach in surrogate-assisted genetic algorithms employing a neural network to estimate survival probabilities of individuals in selections to reduce computational cost of their fitness evaluations. A surrogate-assisted selection scheme we propose employs multi-layer perceptron to learn whether an individual is selected or not without fitness evaluations based on the observations of selections by fitness evaluations in the previous generations.
We have proposed EDA-GK, Estimation of Distribution Algorithms with Graph Kernels. The EDA-GK is designed for solving graph-related problems, where individuals can be represented by graphs. By using graph kernels, the EDA-GK can be solved for graph-related problems well. The EDA-GK uses the graph kernels as probabilistic models in EDA. In this study, we examine the Weisfeiler-Lehman Kernel, and the mixture of two kernels. Experimental results on Graph Isomorphism problems showed the effectiveness of the pro- posed method:
In this work, we describe a self-replication-based mechanism for designing agents of increasing complexity. We demonstrate the validity of this approach by solving simple, standard evolutionary computation problems in simulation. In the context of these simulation results, we describe the fundamental differences of this approach when compared to traditional approaches. Further, we highlight the possible advantages of applying this approach to the problem of designing complex artificial agents, along with the potential drawbacks and issues to be addressed in the future.
Syllables play an important role in speech synthesis, speech recognition, and spoken document retrieval. A novel, low cost, and language agnostic approach to dividing words into their corresponding syllables is presented. A hybrid genetic algorithm constructs a categorization of phones optimized for syllabification. This categorization is used on top of a hidden Markov model sequence classifier to find syllable boundaries. The technique shows promising preliminary results when trained and tested on English words.
In genetic algorithms, the importance of the basis for representation has been well known. In this paper, we studied the effect of a good basis in binary representation, and resultantly we could show that a good basis improves the performance of search algorithms. A complicated problem space may be transformed into a linearly-separable one via a change of basis. We had experiments on search performance. Finding a good basis from all the bases may not be practical, because it takes O(2n2) time, where n is the length of a chromosome. However, we used a genetic algorithm to find a good basis, to correctly investigate how a basis affects the problem space. We also conducted experiments on the NK-landscape model as a representative computationally hard problem. Experimental results showed that changing basis by the presented genetic algorithm always leads better search performance on the NK-landscape model.
On the hardness of parameter optimization of convolution neural networks using genetic algorithm and machine learning
We introduce a method for optimizing parameters in convolution neural network (CNN) using a genetic algorithm (GA). In the experiment, 11 CNN parameters were chosen and considered as one chromosome. We generated 150 datasets were created by arbitrarily changing the parameters. Among approximately 30 types of models with the highest cross validation, the dataset trained with a random forest model was used as the fitness function in our GA, and the optimized parameter was obtained. To improve the GA, we attempted to filter data and amplify training steps. The randomly revised parameters showed insignificant results, but the final 10 parameter sets showed 67.4% accuracy, which was 13.7% higher than that of the dataset obtained randomly. Among these, it showed a parameter that improved by 1.7% compared to that of the existing dataset.
In this paper, we present a genetic algorithm using geometric crossover to preserve musically important properties. The length of the chromosome is variable when we use a musical note as a gene. A geometric crossover based on the edit distance was used to combine chromosomes of variable length and succeeded in creating a better child by using a model in which melody pattern is learned. The model can evaluate the score of melody in a specified chord. As a result, we could successfully create a melody preserving parent's good patterns.
Evolutionary algorithm using surrogate assisted model for simultaneous design optimization benchmark problem of multiple car structures
This paper proposes a surrogate-assisted evolutionary algorithm for solving optimization problems with high calculation cost for constraint determination. The proposed method consists of CMOEA/D that extends the ability of MOEA/D to deal with constrained optimization problems and a surrogate evaluation model constructed by a machine learning, extreme learning machine (ELM). To investigate the effectiveness of the proposed method, we conduct an experiment on simultaneous design optimization benchmark problem of multiple car structures developed by Mazda Motor Corporation et al.. The experimental result revealed that the proposed method can obtain optimal solutions faster than CMOEA/D without a surrogate model.
Nvidia's CUDA parallel computation is a good way to reduce computational cost when applying a filter expressed by an equation to an image. In fact, programs need to be compiled to build GPU kernels. Over the past decade, various implementation methods for the image filter using Genetic Programming (GP) have been developed to enhance its performance. By using GP, an appropriate image filter structure can be obtained through learning algorithms based on test data. In this case, each solution must be compiled; therefore, the required computational effort grows significantly. In this paper, we propose a PyCuda-based GP framework to reduce the computational efforts for evaluations. We verify that the proposed method can implement GPU kernels easily based on a sequential GP algorithm, thereby reducing the computational cost significantly.
In this paper we present the recent accomplishments in developing a biclustering method based on evolutionary computation. In one of the recent papers we demonstrated the supremacy of our method over several state-of-the-art algorithms. We highlight the evolutionary fundamentals of the method and discuss potential future directions.
Configuring the parameters of artificial neural networks using neuroevoiution and automatic algorithm configuration
NeuroEvolution (NE) is a powerful method that uses Evolutionary Algorithms (EAs) for learning Artificial Neural Networks (ANNs). However, NE's performance is determined by the definition of dozens of parameters that guide the search of the EAs. In this study we apply automatic algorithm configuration for tuning the parameters of a NE method in an offline matter. The tuned NE method is then used to evolve the weights, topology and activation functions of ANNs while performing feature selection and its performance is compared to the case of using default parameters. We show that tuning the parameters results in NE methods able to solve the problems with 100% accuracy in significantly less generations.
Deep learning is a widely explored research area, as it established the state of the art in many fields. However, the effectiveness of deep neural networks (DNNs) is affected by several factors related with their training. The commonly used gradient-based back-propagation algorithm suffers from a number of shortcomings, such as slow convergence, difficulties with escaping local minima of the search space, and vanishing/exploding gradients. In this work, we propose a genetic algorithm assisted by gradient learning to improve the DNN training process. Our method is applicable to any DNN architecture or dataset, and the reported experiments confirm that the evolved DNN models consistently outperform those trained using a classical method within the same time budget.
Digital investigations on the evolution of prokaryote photosynthesis regulation: late-breaking abstract
The questions about nature that we can address using digital evolution are constrained by the speed of our software and the level of abstraction used in our genetic representations. One subject that has been particularly challenging is the evolution of gene regulatory networks. We introduce a new digital evolution platform, built upon a mechanistic model of gene regulation and chemical signaling, that permits studying the evolution of an organism's adaptive decision-making and its underlying gene regulatory and signaling networks. We will discuss how this platform is being used to investigate the evolution of homeostasis and circadian rhythms in photosynthetic prokaryotes.
In this paper, a genetic algorithm for solving Sudoku puzzles is presented. Objective function has been defined as maximization of an entropy function in order to get a solution of Sudoku by generating rows, columns and 3x3 sub-matrices containing each integer [1, 2, 3, 4, 5, 6, 7, 8, 9] without duplication, for the case of 9x9 grid puzzle. A permutation and row-crossover operators are designed to this problem. The proposed algorithm is tested on different instances of Sudoku: easy and multimodal Sudoku. Simulation results show a competitive performance for these two instances of Sudoku.
A recent trend in multiobjective evolutionary algorithms is to increase the population size to approximate the Pareto front with high accuracy. On the other hand, the NSGA-II algorithm widely used in multiobjective optimization performs non-dominated sorting in solution ranking, which means an increase in computational complexity proportional to the square of the population. This execution time becomes a problem in engineering applications. It is also difficult to achieve high speeds while maintaining the accuracy of solution searching by simply applying fast, parallel processing to standard genetic operations. In this paper, we propose NSGA-II distributed processing in a many-core environment and a migration method that shares extreme Pareto solutions of the current generation among all cores after performing compensation of the non-dominated solution set obtained by distributed processing. Using a two-objective and three-objective constrained knapsack problem for evaluation, we show that the proposed method is effective in improving diversity in solution searching while shortening execution time and increasing the accuracy of solution searching.
Infeasible solution repair and MOEA/D sharing weight vectors for solving multi-objective set packing problems
For solving multi-objective set packing problems involving constraints, this work proposes an algorithm combining an infeasible solution repair method and MOEA/D sharing the same weight vector set determining search directions in the objective space. To share the same weight vectors between repair method and evolutionary algorithm enhances the affinity of them, and the experimental results on problems with two and four objectives show that the proposed algorithm improves the search performance especially in the viewpoint of the spread of solutions in the objective space.
Swarm intelligence is rather a simple implementation but has a good performance in function optimization. There are a variety of instances of swarm model and has its inherent dynamic property. In this study we consider a hybrid swarm model where agents complement each other using its native property. Employing popular swarm intelligence model Particle swarm and Firefly we consider hybridization methods in this study. This paper presents a hybridization that agents in Particle swarm selected by a simple rule or a random choice are changing its property to Firefly. Numerical studies are carried out by using complex function optimization benchmarks, the proposed method gives better performance compared with standard PSO.
We develop a model to forecast Chinese soybean futures price with eighteen predictors by integrating the recently proposed dynamic model averaging (DMA) and particle swarm optimization (PSO). Specifically, three important parameters, i.e., two forgetting factors and a decay factor, of DMA are tuned by PSO. The proposed prediction model, named DMA-PSO, not only allow for coefficients to change over time, but also allow for forecasting model to evolve over time. Experimental results show that the proposed DMA-PSO outperforms four counterparts and the best predictors in DMA-PSO for forecasting soybean futures price vary a lot over time1.
Is it worth to approximate fitness by machine learning?: investigation on the extensibility according to problem size
It is usual to need an approximate model in evolutionary computation when fitness function is deemed to be abstract or expected to have a long computation time. In these cases, research on possibility of fitness approximation should proceed before applying an evolutionary algorithm in real-world problems. In this paper, it was found that we could train machine learning algorithms with the sampled solutions when problem size is large, if there is a possibility of fitness approximation at small problem sizes.
Symbolic regression is used to estimate daily time series of local station precipitation amounts from global climate model output with a coarse spatial resolution. Local precipitation is of high importance in climate impact studies. Standard regression, minimizing the RMSE or a similar point-wise error, by design underestimates temporal variability. For impact studies realistic variability is crucial. We use multi-objective Genetic Programming to evolve both deterministic and stochastic regression models that simultaneously optimize RMSE and temporal variability. Results are compared with standard methods based on generalized linear models.