This document proposes the use of multi-objective machine learning in order to solve the problem of online anomaly detection for drinking water quality. Such problem consists of an imbalanced data set where events, the minority class, must be correctly detected based on a time series denoting water quality data and operative data. In order to develop two different robust systems, signal processing and feature engineering are used to prepare the data, while evolutionary multi-objective optimization is used for feature selection and ensemble generation. The proposed systems are tested with hold-out validation during optimization, and are expected to generalize well the predictions for future testing data.
In this paper, a deep BiLSTM ensemble method was proposed to detect anomaly of drinking water quality. First, a convolutional neural network (CNN) is utilized as a feature extractor in order to process the raw data of water quality. Second, bidirectional Long Short Term Memory (BiLSTM) is employed to handle the time series prediction problem. Then, a linear combination of t-time-step predictions weighted by a discount factor was utilized to ensemble the final output of event. Finally, cost-sensitive learning combined with Adam optimization was applied to learn the model according to the imbalance property of the event label.
This paper evaluates anomaly detection approaches for drinking-water quality. Two major machine learning techniques are compared. One is manual feature engineering with feature subset selection for dimensionality reduction. The other is automatic feature learning through a recurrent neural network. Both methods incorporate the time domain for change detection. Preliminary results show a superior performance of automatic feature learning with an F1 score of 80%. While the feature set proposed in this work out-performs naive classification with original features, it needs further analysis to reach comparable performance to the automatic approach.
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 [2] 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.
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]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.
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.
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 [4]. 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 [6].
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.
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 ([12], [8]). 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 [7], none have achieved significant gains over the standard LSTM. Recent work has introduced high performing recurrent neural network alternatives, such as Transformer [11] and Wavenet [4], 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.
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.
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.
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.
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.
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.
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.
One of the most relevant problems in social networks is influence maximization, that is the problem of finding the set of the most influential nodes in a network, for a given influence propagation model. As the problem is NP-hard, recent works have attempted to solve it by means of computational intelligence approaches, for instance Evolutionary Algorithms. However, most of these methods are of limited applicability for real-world large-scale networks, for two reasons: on the one hand, they require a large number of candidate solution evaluations to converge; on the other hand, each evaluation is computationally expensive in that it needs a considerable number of Monte Carlo simulations to obtain reliable values. In this work, we consider a possible solution to such limitations, by evaluating a surrogate-assisted Multi-Objective Evolutionary Algorithm that uses an approximate model of influence propagation (instead of Monte Carlo simulations) to find the minimum-sized set of most influential nodes. Experiments carried out on two social networks datasets suggest that approximate models should be carefully considered before using them in influence maximization approaches, as the errors induced by these models are in some cases too big to benefit the algorithmic performance.
This paper introduces a new, highly asynchronous method for surrogate-assisted optimization where it is possible to concurrently create surrogate models, evaluate fitness functions and do parameter optimization for the underlying problem, effectively eliminating sequential workflows of other surrogate-assisted algorithms. Using optimization networks, each part of the optimization process is exchangeable. First experiments are done for single objective benchmark functions, namely Ackley, Griewank, Schwefel and Rastrigin, using problem sizes starting from 2D up to 10D, and other EGO implementations are used as baseline for comparison. First results show that the implemented network approach is competitive to other EGO implementations in terms of achieved solution qualities and more efficient in terms of execution times.
Autonomously training interpretable control strategies, called policies, using pre-existing plant trajectory data is of great interest in industrial applications. Fuzzy controllers have been used in industry for decades as interpretable and efficient system controllers. In this study, we introduce a fuzzy genetic programming (GP) approach called fuzzy GP reinforcement learning (FGPRL) that can select the relevant state features, determine the size of the required fuzzy rule set, and automatically adjust all the controller parameters simultaneously. Each GP individual's fitness is computed using model-based batch reinforcement learning (RL), which first trains a model using available system samples and subsequently performs Monte Carlo rollouts to predict each policy candidate's performance. We compare FGPRL to an extended version of a related method called fuzzy particle swarm reinforcement learning (FPSRL), which uses swarm intelligence to tune the fuzzy policy parameters. Experiments using an industrial benchmark show that FGPRL is able to autonomously learn interpretable fuzzy policies with high control performance.
With the rise of networked multi-core machines, we have seen an increased emphasis on parallel and distributed programming. In this paper we describe an implementation of Factored Evolutionary Algorithms (FEA) and Distributed Factored Evolutionary Algorithms (DFEA) using the Actor model. FEA and DFEA are multi-population algorithms, which make them good candidates for distributed implementation. The Actor model is a robust architecture for implementing distributed, reactive programs. After walking through the translation of the serial pseudocode into an Actor implementation, we run validation experiments against an FEA baseline. The evidence supports the claim that the Actor versions preserve the semantics and operational performance of the FEA baseline. We also discuss some of the nuances of translating serial pseudocode into an actual distributed implementation.
In this paper, we present a distributed island model implementation of biogeography-based optimization for classification rule mining (island BBO-RM). Island BBO-RM is an evolutionary algorithm for rule mining that uses Pittsburgh style classification rule encoding, which represents an entire ruleset (classifier) as a single chromosome. Our algorithm relies on biogeography-based optimization (BBO), an optimization technique that is inspired by species migration pattern between habitats. Biogeography-based optimization has been reported to perform well in various applications ranging from function optimization to image classification. A major limitation of evolutionary rule mining algorithms is their high computational cost and running time. To address this challenge, we have applied a distributed island model to parallelize the rule extraction phase via BBO. We have explored several different migration topologies and data windowing techniques. Our algorithm is implemented in Julia, a dynamic programming language designed for high-performance and parallel computation. Our results show that our distributed implementation is able to achieve considerable speedups when compared to a serial implementation. Without data windowing, we obtain speedups up to a factor of nine without a loss of classification accuracy. With data windowing, we obtain speedups up to a factor of 30 with a small loss of accuracy in some cases.
The paper presents how Extremal Optimization can be used in a parallel multi-objective load balancing algorithm applied in execution of distributed programs. Extremal Optimization is used to find task migration which dynamically improves processor load balance in a distributed system. In the proposed multi-objective approach we use three objectives relevant to distributed processor load balancing in execution of program tasks. They are: computational load balance of processors, the volume of inter-processor communication and task migration metrics. In the algorithms additional criteria are used which are based on some knowledge on the influence of the computational and communication loads on task execution. The proposed algorithms are assessed by simulation experiments with distributed execution of program macro data flow graphs. Two methods of finding compromise solutions based on the Pareto front were used: one based on a geometric (Euclidean) distance of solutions and the second one based on the Manhattan (taxicab geometry) distance. The influence of the distance geometry on the final solutions is discussed.
Ant Colony Optimization (ACO) is a well-established nature-inspired heuristic, and parallel versions of the algorithm now exist to take advantage of emerging high-performance computing processors. However, careful attention must be paid to parallel components of such implementations if the full benefit of these platforms is to be obtained. One such component of the ACO algorithm is next node selection, which presents unique challenges in a parallel setting. In this paper, we present a new node selection method for ACO, Vectorized Candidate Set Selection (VCSS), which achieves significant speedup over existing selection methods on a test set of Traveling Salesman Problem instances.
Naming Games are AI platforms that can account for how conventions in language and culture are achieved. This approach, however, does not account for other cultural features such as contentions. By contentions it is meant that agents learn other agents' traits but decide not to transmit these. This work introduces a version termed Flouted Naming Game which allows convergence to stable states of cultural contentions as an alternative outcome of the Naming Game. Which regime is achieved depends on a basic asymmetry on the cognitive reward of two opposing cultural forms. Moreover, it is found that there is a sharp phase transition between the two behavioural strategies. The transition point is sensitive to population size: larger populations can maintain contentions on a wider range of parameters than smaller populations.
The scope of the Baldwin effect was recently called into question by two papers that closely examined the seminal work of Hinton and Nowlan. To this date there has been no demonstration of its necessity in empirically challenging tasks. Here we show that the Baldwin effect is capable of evolving few-shot supervised and reinforcement learning mechanisms, by shaping the hyperparameters and the initial parameters of deep learning algorithms. Furthermore it can genetically accommodate strong learning biases on the same set of problems as a recent machine learning algorithm called MAML "Model Agnostic Meta-Learning" which uses second-order gradients instead of evolution to learn a set of reference parameters (initial weights) that can allow rapid adaptation to tasks sampled from a distribution. Whilst in simple cases MAML is more data efficient than the Baldwin effect, the Baldwin effect is more general in that it does not require gradients to be backpropagated to the reference parameters or hyperparameters, and permits effectively any number of gradient updates in the inner loop. The Baldwin effect learns strong learning dependent biases, rather than purely genetically accommodating fixed behaviours in a learning independent manner.
In this paper, a new benchmark, for testing the capability of Evolutionary Algorithms to generate maze solving Exploration Strategies is introduced. This benchmark solves three problems commonly found in other benchmarks: small maze set, all mazes belonging to the same kind of maze, and biased methods for choosing starting locations. In this benchmark, the Connectivity Based Maze Generation Algorithm is proposed for building maze sets. Mazes generated using this algorithm exhibit a property called connectivity that indicates how much the walls are connected among them. Connectivity can be used to control the diversity of the sets. Additionally, a new method for choosing starting locations, that takes into account the maze goal positions, is presented. Using the Connectivity Based Maze Generation Algorithm and the new method for choosing starting locations, two problems that test the capability of an Evolutionary Algorithm for solving mazes with similar and different connectivity are built. Example datasets are generated and experiments are performed to validate the proposed benchmark.
Benchmarking theory in evolutionary computation research is a crucial task that should be properly applied in order to evaluate the performance of a newly introduced evolutionary algorithm with performance of state-of-the-art algorithms. Benchmarking theory is related to three main questions: which problems to choose, how to setup experiments, and how to evaluate performance. In this paper, we evaluate the impact of different already established statistical ranking schemes that can be used for evaluation of performance in benchmarking practice for evolutionary computation. Experimental results obtained on Black-Box Benchmarking 2015 showed that different statistical ranking schemes, used on the same benchmarking data, can lead to different benchmarking results. For this reason, we examined the merits and issues of each of them regarding benchmarking practices.
Evolutionary algorithms are cost-effective for solving real-world optimization problems, such as NP-hard and black-box problems. Before an evolutionary algorithm can be put into real-world applications, it is desirable that the algorithm was tested on a number of benchmark problems. On the other hand, performance measure on benchmarks can reflect if the benchmark suite is representative. In this paper, benchmarks are generated based on the performance comparison among a set of established algorithms. For each algorithm, its uniquely easy (or uniquely difficult) problem instances can be generated by an evolutionary algorithm. The unique difficulty nature of a problem instance to an algorithm is ensured by the Kruskal-Wallis H-test, assisted by a hierarchical fitness assignment method. Experimental results show that an algorithm performs the best (worst) consistently on its uniquely easy (difficult) problem. The testing results are repeatable. Some possible applications of this work include: 1) to compose an alternative benchmark suite; 2) to give a novel method for accessing novel algorithms; and 3) to generate a set of meaningful training and testing problems for evolutionary algorithm selectors and portfolios.
The definition of a concise and effective testbed for Genetic Programming (GP) is a recurrent matter in the research community. This paper takes a new step in this direction, proposing a different approach to measure the quality of the symbolic regression benchmarks quantitatively. The proposed approach is based on meta-learning and uses a set of dataset meta-features---such as the number of examples or output skewness---to describe the datasets. Our idea is to correlate these meta-features with the errors obtained by a GP method. These meta-features define a space of benchmarks that should, ideally have datasets (points) covering different regions of the space. An initial analysis of 63 datasets showed that current benchmarks are concentrated in a small region of this benchmark space. We also found out that number of instances and output skewness are the most relevant meta-features to GP output error. Both conclusions can help define which datasets should compose an effective testbed for symbolic regression methods.
Assessing the performance of stochastic optimization algorithms in the field of multi-objective optimization is of utmost importance. Besides the visual comparison of the obtained approximation sets, more sophisticated methods have been proposed in the last decade, e. g., a variety of quantitative performance indicators or statistical tests. In this paper, we present tools implemented in the R package ecr, which assist in performing comprehensive and sound comparison and evaluation of multi-objective evolutionary algorithms following recommendations from the literature.
Evolutionary robotics researchers often need to share results that may be too difficult to describe in text and too complex to show using images. Many researchers include links to videos as supplementary materials, but videos have a predefined view of the scene and do not allow watchers to adjust the viewing angle to their preference. In this paper we present a web-based application (based on three.js) for sharing interactive animations. Specifically, our tool (called Review) enables researchers to generate simple animation log data that can be loaded in any modern web browser on a computer or mobile device. The camera in these animations is controlled by the user such that they can pan, tilt, rotate, and zoom in and out of the scene. Review is meant to improve the ability of researchers to share their evolved results with one another.
In recent years, metaheuristics have been a convincing solution for solving many types of complex optimization problems. Efficient execution for the most variants of metaheuristics e.g. Evolutionary Algorithms (EAs) or Swarm Optimization can require lots of computational power depending on the complexity of the application. For maximizing performance, parallelization of metaheuristic algorithms represents a meaningful approach, especially for EAs featuring an inherent parallelism. However, the majority of existing distributed optimization frameworks are implemented as monolithic and non-distributed applications running on one computer instead of using the computing power of computer clusters. Additionally, the application typically cannot easily work dynamically together with other tools and services like single simulators or combinations of simulators for multi-domain simulations. In the present paper, a new distributed framework for population-based metaheuristics, which can run highly parallelized optimizations on large scale computing clusters is introduced. The framework exploits and combines two lightweight technologies namely container virtualization and microservices for a fully automated and highly scalable solution. Another main advantage of the framework is that it allows plugging in and out different metaheuristic optimization algorithms and services via its modular distributed architecture. In order to validate the new design and implementation, the EA GLEAM (General Learning Evolutionary Algorithm and Method) [2, 3] is integrated into the framework and deployed on a cluster with 4 nodes and 128 cores for benchmarking. The tested master-slave parallelization of this EA shows considerable low overhead times and hence paves the way for future applications in, e.g., smart energy systems.
Perl 6 is a recently released language that belongs to the Perl family but was actually designed from scratch, not as a refactoring of the Perl 5 codebase. Through its two-year-old (released) history, it has increased performance by several orders of magnitude, arriving recently to the point where it can be safely used in production. In this paper, we are going to compare the historical and current performance of Perl 6 in a single problem, OneMax, to those of other interpreted languages; besides, we will also use implicit concurrency and see what kind of performance and scaling can we expect from it.
In the Push programming language, all sequences of valid symbols with balanced parentheses are syntactically valid and execute without error. Push nonetheless supports arbitrary data types and is Turing complete. This combination of features makes it useful as the target language for program induction in genetic programming systems, for which it was developed, and potentially also in other program induction systems. Prior Push implementations have generally been designed for use only within the host language in which they were implemented, often in conjunction with a specific program induction system that is written in the same host language. In this paper we present Plushi, a modular, embeddable Push interpreter that is designed to interoperate with program induction systems written in any language.
In this paper, we describe the Evo-ROS framework, which is intended to help bridge the gap between the evolutionary and traditional robotics communities. Evo-ROS combines an evolutionary algorithm with individual physics-based evaluations conducted using the Robot Operating System (ROS) and the Gazebo simulation environment. Our goals in developing Evo-ROS are to (1) provide researchers in evolutionary robotics with access to the extensive support for real-world components and capabilities developed by the ROS community and (2) enable ROS developers, and more broadly robotics researchers, to take advantage of evolutionary search during design and testing. We describe the details of the Evo-ROS structure and operation, followed by presentation of a case study using Evo-ROS to optimize placement of sonar sensors on unmanned ground vehicles that can experience reduced sensing capability due to component failures and physical damage. The case study provides insights into the current capabilities and identifies areas for future enhancements.
Feature selection is an essential problem in pattern classification systems. The entire performance of the classifier is highly affected by the quality of the selected features. In this paper, we address this problem by integrating feature selection with the clustering process. A novel feature-modulated classification algorithm is proposed to improve the classification accuracy. We use a rough sets approach for feature selection based on a scatter search meta-heuristic scheme. The proposed approach sifts a compact subset of characterizing features in multi-class systems according to the clustering performance. To verify the effectiveness of our method, experimental comparisons are carried out on eleven benchmark datasets using two typical classifiers. The results indicate that the proposed method has a remarkable ability to generate effective reduced-size subsets of salient features while yielding significant classification accuracy.
In this paper, we propose a method to generate an optimized ensemble classifier. In the proposed method, a diverse input space is created by clustering training data incrementally within a cycle. A cycle is one complete round that includes clustering, training, and error calculation. In each cycle, a random upper bound of clustering is chosen and data clusters are generated. A set of heterogeneous classifiers are trained on all generated clusters to promote structural diversity. An ensemble classifier is formed in each cycle and generalization error of that ensemble is calculated. This process is optimized to find the set of classifiers which can have the lowest generalization error. The process of optimization terminates when generalization error can no longer be minimized. The cycle with the lowest error is then selected and all trained classifiers of that particular cycle are passed to the next stage. Any classifier having lower accuracy than the average accuracy of the pool is discarded, and the remaining classifiers form the proposed ensemble classifier. The proposed ensemble classifier is tested on classification benchmark datasets from UCI repository. The results are compared with existing state-of-the-art ensemble classifier methods including Bagging and Boosting. It is demonstrated that the proposed ensemble classifier performs better than the existing ensemble methods.
This paper explains the process of integrating ACS2 algorithm with the standardised framework for comparing reinforcement learning tasks - OpenAI Gym. The new Python library is introduced alongside with standard environments derived from LCS literature. Typical use cases enabling quick evaluation of different research problems are described.
This paper proposes the novel Learning Classifier System (LCS) which can solve high-dimensional problems, and obtain human-readable knowledge by integrating deep neural networks as a compressor. In the proposed system named DCAXCSR, deep neural network called Deep Classification Autoencoder (DCA) compresses (encodes) input to lower dimension information which LCS can deal with, and decompresses (decodes) output of LCS to the original dimension information. DCA is hybrid network of classification network and autoencoder towards increasing compression rate. If the learning is insufficient due to lost information by compression, by using decoded information as an initial value for narrowing down state space, LCS can solve high dimensional problems directly. As LCS of the proposed system, we employs XCSR which is LCS for real value in this paper since DCA compresses input to real values. In order to investigate the effectiveness of the proposed system, this paper conducts experiments on the benchmark classification problem of MNIST database and Multiplexer problems. The result of the experiments shows that the proposed system can solve high-dimensional problems which conventional XCSR cannot solve, and can obtain human-readable knowledge.
Evolutionary Computation (EC) attracts more and more attention in Reinforcement Learning (RL) with successful applications such as robot control. Instance-Based Policy (IBP) is a promising alternative to policy representations based on Artificial Neural Networks (ANNs). The IBP has been reported superior to continuous policy representations such as ANNs in the stabilization control of non-holonomic systems due to its nature of bang-bang type control, and its understandability. A difficulty in applying an EC based policy optimization to an RL task is to choose appropriate hyper-parameters such as the network structure in ANNs and the parameters of EC. The same applies to the IBP, where the critical parameter is the number of instances that determines mode flexibility. In this paper, we propose a novel RL method combining the IBP representation and optimization by the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), which is a state-of-the-art general-purpose search algorithm for black-box continuous optimization. The proposed method, called IBP-CMA, is a direct policy search that adapts the number of instances during the learning process and activates instances that do not contribute to the output. In the simulation, the IBP-CMA is compared with an ANN-based RL, CMA-TWEANN.
XCS and its derivatives are some of the most prominent Learning Classifier Systems (LCSs). Since XCS's design was done "algorithm first", there existed no formal basis at its inception. Over the past 20 years, several publications analysed parts of the system theoretically but the only approach to a more holistic theory of LCSs in general was never fully adapted. We present an algebraic formalisation of XCS that facilitates formal reasoning about the system and serves as a complement to earlier algorithmic descriptions. Our work is meant to give a fresh impetus to XCS and LCS theory. Since we use the programming language Haskell for our formal expressions we also describe a new abstract XCS framework in the process.
Database intrusion detection (DB-IDS) is the problem of detecting anomalous queries in transaction systems like e-commerce platform. The adaptive detection algorithm is necessary to find anomaly accesses when the environment changes continuously. To solve this problem, we used accuracy-based LCS (XCS), one of the primary model of adaptive machine learning method, for detecting malicious accesses in databases. In the problem of database intrusion detection which changes the detecting targets, we found and analyzed the patterns of rule generation to show systemically how the adaptive learning of XCS algorithm is working in practical usage.
While some attention has been given to the process of using Evolutionary Computation (EC) to optimize the activation functions within hidden layers, available activation function sets have always been hard coded by the developers, and were immutable by users.
In this paper, we present EvoNN. While many other Neuro-evolution based tools or algorithms focus primarily on the evolution of either Neural Network (NN) architecture, or its weights, EvoNN focuses on simultaneous evolution of weights and the activation functions within hidden layers. The main novely offered by EvoNN lies in that users can provide additional activation functions to the EvoNN system to be employed as part of the "alphabet" of available functions. This feature gives users a greater degree of flexibility over which functions the evolutionary optimizer can utilize.
We employ a set of three test cases where we compare EvoNN to a standard NN, and observe encouraging results showing a superior performance of the EvoNN system. We also observe this increase in performance comes at the cost of additional run time, but note that for some applications, this can be a worthwhile trade-off.
Accuracy based Learning Classifier System (XCS) prefers to generalize the classifiers that always acquire the same reward, because they make accurate reward predictions. However, real-world problems have noise, which means that classifiers may not receive the same reward even if they always take the correct action. For this case, since all classifiers acquire multiple values as the reward, XCS cannot identify accurate classifiers. In this paper, we study a single step environment with action noise, where XCS's action is sometimes changed at random. To overcome this problem, this paper proposes XCS based on Collective weighted Reward (XCS-CR) to identify the accurate classifiers. In XCS each rule predicts its next reward by averaging its past rewards. Instead, XCS-CR predicts its next reward by selecting a reward from the set of past rewards, by comparing the past rewards to the collective weighted average reward of the rules matching the current input for each action. This comparison helps XCS-CR identify rewards that result from action noise. In experiments, XCS-CR acquired the optimal generalized classifier subset in 6-Multiplexer problems with action noise, similar to the environment without noise, and judged those optimal generalized classifiers correctly accurate.
This paper proposes high-dimensional data mining technique by integrating two data mining methods: Accuracy-based Learning Classifier Systems (XCS) and Random Forests (RF). Concretely the proposed system integrates RF and XCS: RF generates several numbers of decision trees, and XCS generalizes the rules converted from the decision trees. The convert manner is as follows: (1) the branch node of the decision tree becomes the attribute; (2) if the branch node does not exist, the attribute of that becomes # for XCS; and (3) One decision tree becomes one rule at least. Note that # can become any value in the attribute. From the experiments of Multiplexer problems, we derive that: (i) the good performance of the proposed system; and (ii) RF helps XCS to acquire optimal solutions as knowledge by generating appropriately generalized rules.
Understanding the properties of neural network error landscapes is an important problem faced by the neural network research community. A few attempts have been made in the past to gather insight about neural network error landscapes using fitness landscape analysis techniques. However, most fitness landscape metrics rely on the analysis of random samples, which may not represent the high-dimensional neural network search spaces well. If the random samples do not include areas of good fitness, then the presence of local optima and/or saddle points cannot be quantified. This paper proposes a progressive gradient walk as an alternative sampling algorithm for neural network error landscape analysis. Experiments show that the proposed walk captures areas of good fitness significantly better than the random walks.
There has been an increasing amount of research on the visualisation of search landscapes through the use of exact and approximate local optima networks (LONs). Although there are many papers available describing the construction of a LON, there is a dearth of code released to support the general practitioner constructing a LON for their problem. Furthermore, a naive implementation of the algorithms described in work on LONs will lead to inefficient and costly code, due to the possibility of repeatedly reevaluating neighbourhood members, and partially overlapping greedy paths. Here we discuss algorithms for the efficient computation of both exact and approximate LONs, and provide open source code online. We also provide some empirical illustrations of the reduction in the number of recursive greedy calls, and quality function calls that can be obtained on NK model landscapes, and discretised versions of the IEEE CEC 2013 niching competition tests functions, using the developed framework compared to naive implementations. In many instances multiple order of magnitude improvements are observed.
Feature selection is a complex problem used across many fields, such as computer vision and data mining. Feature selection algorithms extract a subset of features from a greater feature set which can improve algorithm accuracy by discarding features that are less significant in achieving the goal function. Current approaches are often computationally expensive, provide insignificant increases in predictor performance, and can lead to overfitting. This paper investigates the binary feature selection problem and the applicability of using filter and wrapper techniques guided by fitness landscape characteristics. It is shown that using filter methods are more appropriate for problems where the fitness does not provide sufficient information to guide search as needed by wrapper techniques.
This work introduces a novel adaptation framework to energy-efficiently adapt small-sized circuits operating under scarce resources in dynamic environments, as autonomous swarm of sensory agents. This framework makes it possible to optimally configure the circuit based on three key mechanisms: (a) an off-line optimization phase relying on R2 indicator based Evolutionary Multi-objective Optimization Algorithm (EMOA), (b) an on-line phase based on hardware instincts and (c) the possibility to include the environment in the optimization loop. Specifically, the evolutionary algorithm is able to simultaneously determine an optimal combination of static settings and dynamic instinct for the hardware, considering highly dynamic environments. The instinct is then run on-line with minimal on-chip resources so that the circuit efficiently react to environmental changes. This framework is demonstrated on an ultrasonic communication system between energy-scarce wireless nodes. The proposed approach is environment-adaptive and enables power savings up to 45% for the same performance on the considered case studies.
Living cells exhibit both growth and regeneration of body tissues. Epigenetic Tracking (ET), models this growth and regenerative qualities of living cells and has been used to generate complex 2D and 3D shapes. In this paper, we present an ET based algorithm that aids a swarm of identically-programmed robots to form arbitrary shapes and regenerate them when cut. The algorithm works in a distributed manner using only local interactions and computations without any central control and aids the robots to form the shape in a triangular lattice structure. In case of damage or splitting of the shape, it helps each set of the remaining robots to regenerate and position themselves to build scaled down versions of the original shape. The paper presents the shapes formed and regenerated by the algorithm using the Kilombo simulator.
Benchmarking algorithms is a crucial task to understand them and to make recommendations for which algorithms to use in practice. However, one has to keep in mind that we typically compare only algorithm implementations and that care must be taken when making general statements about an algorithm while implementation details and parameter settings might have a strong impact on the performance. In this paper, we investigate those impacts of initialization, internal parameter setting, and algorithm implementation over different languages for the well-known BFGS algorithm. We must conclude that even in the default setting, the BFGS algorithms in Python's scipy library and in Matlab's fminunc differ widely---with the latter even changing significantly over time.
The CMAES-APOP algorithm tracks the median of the elite objective values in each S successive iterations to decide whether we should increase or decrease or keep the population size in the next slot of S iterations. This quantity could be seen as the 25th percentile of objective function values evaluated in each iteration on λ candidate points. In this paper we propose a variant of the CMAES-APOP algorithm, in which we will track some percentiles of the objective values simultaneously. Some numerical results will show the improvement of this approach on some ill-conditioned functions, and on some multi-modal functions with weak global structure in small dimensions.
We evaluate the CMA-ES with population size adaptation mechanism (PSA-CMA-ES) on the BBOB noiseless testbed. On one hand, the PSA-CMA-ES with a simple restart strategy shows performance competitive with the best 2009 portfolio on most well-structured multimodal functions. On the other hand, it is not effective on weakly-structured multimodal functions. Moreover, on most uni-modal functions, the scale-up of performance measure w.r.t. the dimension tends to be worse than the default CMA-ES, implying that the population size is adapted greater than needed on the unimodal functions. To improve performance on unimodal functions and weakly-structured multimodal functions, we additionally propose a restart strategy for the PSA-CMA-ES. The proposed strategy consists of three search regimes. The resulted restart strategy shows improved performance on unimodal functions and weakly-structured multimodal functions with a little compromise in the performance on well-structured multimodal functions. The overall performance is competitive to the BIPOP-CMA-ES.
Recently, black-box differential evolution (BBDE) has been proposed to overcome the search biases and sensitivity to rotation of the classic differential evolution (DE). To date, BBDE has been studied only for the 'rand' strategy and even for this strategy, no systematic experimental study has been published yet. In this paper we provide such a study and further examine whether the idea from BBDE can be extended to two other DE strategies, 'best' and 'target-to-best'. We compare in detail these DE and BBDE variants using the COCO (Comparing Continuous Optimizers) platform to assess their overall performance and invariance to rotation. The results show that BBDE with the 'rand' strategy performs better than the original algorithm, but this is not true for the other two strategies. We also demonstrate that while the BBDE variants are less sensitive to rotation than the DE variants, some sensitivity to this transformation still persists and remains currently unexplained.
Selection functions enable Evolutionary Algorithms (EAs) to apply selection pressure to a population of individuals, by regulating the probability that an individual's genes survive, typically based on fitness. Various conventional fitness based selection methods exist, each providing a unique relationship between the fitnesses of individuals in a population and their chances of selection. However, the full space of selection algorithms is only limited by max algorithm size, and each possible selection algorithm is optimal for some EA configuration applied to a particular problem class. Therefore, improved performance may be expected by tuning an EA's selection algorithm to the problem at hand, rather than employing a conventional selection method. The objective of this paper is to investigate the extent to which performance can be improved by tuning selection algorithms, employing a Hyper-heuristic to explore the space of search algorithms which encode the relationships between the fitnesses of individuals and their probability of selection. We show the improved performance obtained versus conventional selection functions on fixed instances from a benchmark problem class, including separate testing instances to show generalization of the improved performance.
Understanding the evolutionary dynamics created by a given evolutionary algorithm is a critical step in determining which ones are most likely to produce desirable outcomes for a given problem. While it is relatively easy to come up with hypotheses that could plausibly explain observed evolutionary outcomes, we often fail to take the next step of confirming that our proposed mechanism accurately describes the underlying evolutionary dynamics. Visualization is a powerful tool for exploring evolutionary history as it actually played out. We can create visualizations that summarize the evolutionary history of a population or group of populations by drawing representative lineages on top of the fitness landscape being traversed. This approach integrates information about the adaptations that took place with information about the evolutionary pressures they were being subjected to as they evolved. However, these visualizations can be challenging to depict on a two-dimensional surface, as they integrate multiple forms of three-dimensional (or more) data. Here, we propose an alternative: taking advantage of recent advances in virtual reality to view evolutionary history in three dimensions. This technique produces an intuitive and detailed illustration of evolutionary processes. A demo of our visualization is available here: https://emilydolson.github.io/fitness_landscape_visualizations.
This paper proposes different visualisation techniques to understand the behaviour of an algorithm's entities during the search process when solving multi-objective optimisation problems. A scatter plot is used to highlight the Pareto-ranking of the entities during the search. Different fronts of the entities are indicated through the ball sizes of the scatter plot. Using a parallel coordinate plot for visualising the effect of control parameter values on the performance of an algorithm is also proposed. Possible extensions for dynamic multi-objective optimisation are also discussed.
Recent advances in deep neuroevolution have demonstrated that evolutionary algorithms, such as evolution strategies (ES) and genetic algorithms (GA), can scale to train deep neural networks to solve difficult reinforcement learning (RL) problems. However, it remains a challenge to analyze and interpret the underlying process of neuroevolution in such high dimensions. To begin to address this challenge, this paper presents an interactive data visualization tool called VINE (Visual Inspector for NeuroEvolution) aimed at helping neuroevolution researchers and end-users better understand and explore this family of algorithms. VINE works seamlessly with a breadth of neuroevolution algorithms, including ES and GA, and addresses the difficulty of observing the underlying dynamics of the learning process through an interactive visualization of the evolving agent's behavior characterizations over generations. As neuroevolution scales to neural networks with millions or more connections, visualization tools like VINE that offer fresh insight into the underlying dynamics of evolution become increasingly valuable and important for inspiring new innovations and applications.
High Intensity Focused Ultrasound (HIFU) is an emerging technique for non-invasive cancer treatment where malignant tissue is destroyed by thermal ablation. Since one ablation only allows a small region of tissue to be destroyed, a series of ablations has to be conducted to treat larger volumes. To maximize the treatment outcome and prevent injuries such as skin burns, complex preoperative treatment planning is carried out to determine the focal position and sonication time for each ablation. Here, we present an evolutionary strategy to design HIFU treatment plans using a map of patient specific material properties and a realistic thermal model. The proposed strategy allows high-quality treatment plans to be designed, with the average volume of mistreated and under-treated tissue not exceeding 0.1 %.
Humanity have long strived to create microscopic machines for various purposes. Most prominent of them employ nano-robots for medical purposes and procedures, otherwise deemed hard or impossible to perform. However, the main advantage of this kind, of machines is also their main drawback - their small size. The miniature scale they work in, brings a lot of problems, such as not having enough space for the computational power needed for their operation, or the specifics of the laws of physic that govern their behavior. In our study we focus on the former challenge, by introducing a new standpoint to the well-studied predator-prey pursuit problem (PPPP) using an implementation of very simple predator agents, using nano-robots designed to be morphologically simple. They feature direct mapping of the (few) perceived environmental variables into corresponding pairs of rotational velocities of the wheels' motors. Our previous, unpublished work showed that the classic problem with agents that use straightforward sensor, do not yield favorable results as they solve only a few of the initial test situations. We implemented genetic algorithm to evolve such a mapping that results in an optimal successful behavioral of the team of predator agents. In addition, to cope with the previously described issue, we introduced a simple change to the agents in order to improve the generality of the evolved behavior for additional test situations. Our approach is to implement an angular offset to the visibility sensor beam relative to the longitudinal axis of the agents. We added the offset to the genetic algorithm in order to define the best possible value, that introduces most efficient and consistent solution results. The successfully evolved behavior can be used in nano-robots to deliver medicine, locate and destroy cancer cells, pinpoint microscopic imaging, etc.1
Solving problems involves the following two phases. In the first phase, detail of the problem are determined and the solution is found according to these condition. In the second phase, the results are used to narrow down any remaining ambiguities in the problem. In terms of the flow of a river, the former lies upstream of solving the problem while the latter lies downstream. Multiobjective genetic algorithms (GAs) is are able to find possible solution sets involving trade-offs among several different objective functions. In this study, we use a multiobjective GA to grasp variety types of solutions, not solve the problem directly. In other words, we use it for the upstream problem-solving step. As a case study of using multiobjective GAs to explore solutions, we identify cancer cells where the Nrf3 transcription factor is active and consider the problem of determining which genes to focus on in experiments based on that information. In this case, we selected gene candidates that are likely to be associated with Nrf3 activity and experiments (which previously had to be carried out exhaustively) are currently being carried out to confirm these results.
When attempting to improve the non-functional requirements of software, specifically run-time performance of code, an important requirement is to preserve the correctness of the optimized code. Additionally when attempting to integrate Genetic Improvement into a compiler or interpreter, the large search spaces resulting from the amount of operators and operands a language provides needs to be dealt with. This publication explores dynamic fitness functions as a foundation for a use in Genetic Improvement to optimize programs. An approach of using a test suite to verify code correctness in the Truffle Framework [19, 20] and Graal Compiler [11] is presented. Two types of fitness functions are explored, which split the test suite according to their complexity and attempt to generate correct solutions with a growing set of increasingly complex tests. One of them increases the amount of tests sequentially over several iterations. The parallel fitness function attempts to split a test suite and to re-combine the results with increasingly large suites. The results show that these functions only marginally improve the fitness landscape on their own, but show that more partially correct solutions can be found with dynamic fitness functions. In the future, our approach may be improved by implementing specific crossover and mutator operations to accompany the dynamic fitness functions.
Genetic Improvement (GI) performs a search at the level of source code to find the best variant of a baseline system that improves non-functional properties while maintaining functionality with noticeable results in several domains. There a many aspects of this general approach that are currently being explored. In particular, this work deals to the way in which the search is guided to efficiently explore the search space of possible software versions in which GI operates. The proposal is to integrate Novelty Search (NS) within the GISMOE GI framework to improve KinectFusion, which is a vision-based Simultaneous Localization and Mapping (SLAM) system that is used for augmented reality, autonomous vehicle navigation, and many other real-world applications. This is one of a small set of works that have successfully combined NS with a GP system, and the first time that it has been used for software improvement. To achieve this, we propose a new behaviour descriptor for SLAM algorithms, based on state-of-the-art benchmarking and present results that show that NS can produce significant improvement gains in a GI setting, when considering execution time and trajectory estimation as the main performance criteria.
The automatic detection of refactoring recommendations has been tackled in prior optimization studies involving bad code smells, semantic coherence and importance of classes; however, such studies informally addressed formalisms to standardize and replicate refactoring models. We propose to assess the refactoring detection by means of performance convergence and time complexity. Since the reported approaches are difficult to reproduce, we employ an Artificial Refactoring Generation (ARGen) as a formal and naive computational solution for the Refactoring Detection Problem. ARGen is able to detect massive refactoring's sets in feasible areas of the search space. We used a refactoring formalization to adapt search techniques (Hill Climbing, Simulated Annealing and Hybrid Adaptive Evolutionary Algorithm) that assess the performance and complexity on three open software systems. Combinatorial techniques are limited in solving the Refactoring Detection Problem due to the relevance of developers' criteria (human factor) when designing reconstructions. Without performance convergence and time complexity analysis, a software empirical analysis that utilizes search techniques is incomplete.
This paper proposes to explore a software engineer-assisted method for evolutionarily improving large-scale software systems. A framework is outlined for selecting and evolving specific components of such systems, while avoiding treating the complete software as a single independent individual in the population, thereby forgoing the high costs of that approach.
Given the advances in areas such as home automation, agricultural networks, smart cities, designers often need to design protocols that utilize the features of that network while dealing with its limitations. Utilizing standardized protocols for such networks may not be appropriate as they may not address limitations of the network such as heterogeneous nodes or limited capability of some nodes. While designing a customized protocol for that network would be desirable, it is extremely time-consuming unless we can automate the development of the required protocol. In this paper, we present NetSynth, a GP based mechanism to develop customized routing protocol for the given network. NetSynth lets us conveniently describe a network using an XML file, and it synthesizes a routing protocol that suits the input network by considering the characteristics specific to the given network. We show how NetSynth creates protocols that perform comparably to best-known protocols for the case where we want to broadcast a set of messages to all nodes in a grid. We also show how NetSynth helps us design protocols that provide a tradeoff between throughput and energy.
A highly-configurable system provides many configuration options to diversify application scenarios. The combination of these configuration options results in a large search space of configurations. This makes the detection of configuration-related faults extremely hard. Since it is infeasible to exhaust every configuration, several methods are proposed to sample a subset of all configurations to detect hidden faults. Configuration sampling can be viewed as a process of repeating a pre-defined sampling action to the whole search space, such as the one-enabled or pair-wise strategy.
In this paper, we propose genetic configuration sampling, a new method of learning a sampling strategy for configuration-related faults. Genetic configuration sampling encodes a sequence of sampling actions as a chromosome in the genetic algorithm. Given a set of known configuration-related faults, genetic configuration sampling evolves the sequence of sampling actions and applies the learnt sequence to new configuration data. A pilot study on three highly-configurable systems shows that genetic configuration sampling performs well among nine sampling strategies in comparison.
The Software Defined Networking paradigm has enabled dynamic configuration and control of large networks. Although the division of the control and data planes on networks has lead to dynamic reconfigurability of large networks, finding the minimal and optimal set of controllers that can adapt to the changes in the network has proven to be a challenging problem. Recent research tends to favor small solution sets with a focus on either propagation latency or controller load distribution, and struggles to find large balanced solution sets. In this paper, we propose a multi-objective genetic algorithm based approach to the controller placement problem that minimizes inter-controller latency, load distribution and the number of controllers with fitness sharing. We demonstrate that the proposed approach provides diverse and adaptive solutions to real network architectures such as the United States backbone and Japanese backbone networks. We further discuss the relevance and application of a diversity focused genetic algorithm for a moving target defense security model.
Successful attacks on computer networks today do not often owe their victory to directly overcoming strong security measures set up by the defender. Rather, most attacks succeed because the number of possible vulnerabilities are too large for humans to fully protect without making a mistake. Regardless of the security elsewhere, a skilled attacker can exploit a single vulnerability in a defensive system and negate the benefits of those security measures. This paper presents an evolutionary framework for evolving attacker agents in a real, emulated network environment using genetic programming, as a foundation for coevolutionary systems which can automatically discover and mitigate network security flaws. We examine network enumeration, an initial network reconnaissance step, through our framework and present results demonstrating its success, indicating a broader applicability to further cyber-security tasks.
In computer security, guidance is slim on how to prioritize or configure the many available defensive measures, when guidance is available at all. We show how a competitive co-evolutionary algorithm framework can identify defensive configurations that are effective against a range of attackers. We consider network segmentation, a widely recommended defensive strategy, deployed against the threat of serial network security attacks that delay the mission of the network's operator. We employ a simulation model to investigate the effectiveness over time of different defensive strategies against different attack strategies. For a set of four network topologies, we generate strong availability attack patterns that were not identified a priori. Then, by combining the simulation with a co-evolutionary algorithm to explore the adversaries' action spaces, we identify effective configurations that minimize mission delay when facing the attacks. The novel application of co-evolutionary computation to enterprise network security represents a step toward course-of-action determination that is robust to responses by intelligent adversaries.1
Complex, realistic scenarios in training simulations can benefit from good control of large numbers of simulation entities. However, training simulations typically focus on simulation physics and graphics over the intelligence required to control large numbers of entities. Real-Time Strategy games, on the other hand, have evolved to make tradeoffs between the AI needed and human interaction required to control hundreds of entities in complex tactical skirmishes. Borrowing from work in real-time strategy games, this paper attacks the problem of controlling groups of heterogenous entities in training simulations by using a genetic algorithm to evolve control algorithm parameters that maximize damage done and minimize damage received during skirmishes in a real-time strategy game-like simulation. Results show the emergence of complex, coordinated behavior among groups of simulated entities. Evolved behavior quality seems to be relatively independent of the underlying physics model but depends on the initial dispositions of entities in the simulation. We can get over this dependence and evolve more robust high performance behaviors by evaluating fitness in several different scenarios with different initial dispositions. We believe these preliminary results indicate the viability of our approach for generating robust, high performance behaviors for controlling swarms of entities in training simulations to enable more complex, realistic training scenarios.
Accurate detection of natural or intentional contamination events in water distribution pipes is critical to drinking water safety. Efficient early warning systems that can detect contamination events require detection algorithms that can accurately predict the occurrence of such events. This paper presents the development of adaptive neuro-fuzzy inference system (ANFIS) models for detecting the safety condition of water in pipe networks when concentrations of water quality variables in the pipes exceed their maximum thresholds. The event detection is based on time series data composed of pH, turbidity, color and bacteria count measured at the effluent of a drinking water utility and nine different locations of sensors in the distribution network in the city of Ålesund, Norway. The proposed ANFIS models correctly detected between 92% and 96% of the safety condition of the water in the pipe network, with approximately 1% false alarm rate during the testing stage. The models also achieved high rates of specificity and precision, with very high correlations between the predictions and actual conditions of the water in the pipes. The accuracy of the models achieved in this study suggests that the models can be useful in real time contamination event detection in the pipe networks.
In this paper, we address the problem of applying evolutionary dynamic optimization of network monitoring to highly dynamic communication network infrastructures.
One major challenge of modern communication networks is the increasing volatility due to, e.g., changing availability of nodes and links, load of paths, or attacks. While optimization of those dynamic networks has been an important application area since decades, new developments in the area of network function virtualization and software defined network facilitate a completely new level of automated dynamic network optimization. Especially in mobile networks, changes can be observed to appear swiftly. Thus, using population-based heuristics becomes challenging as reevaluation of all candidate solutions may become time-wise impossible and operations need to rely on possibly obsolete fitness values.
Here, an established method has been applied to solve the dynamic monitor selection problem on multiple real-world problem instances using a different simulated level of change. Statistically significant results of the proposed method have been compared to the performance of a best-of-multiple selection local search (EMS LS) heuristic. As the results show, optimization reaches results of high quality even under difficult circumstances.
Many abstract security measurements are based on characteristics of a graph that represents the network. These are typically simple and quick to compute but are often of little practical use in making real-world predictions. Practical network security is often measured using simulation or real-world exercises. These approaches better represent realistic outcomes but can be costly and time-consuming. This work aims to combine the strengths of these two approaches, developing efficient heuristics that accurately predict attack success. Hyper-heuristic machine learning techniques, trained on network attack simulation training data, are used to produce novel graph-based security metrics. These low-cost metrics serve as an approximation for simulation when measuring network security in real time. The approach is tested and verified using a simulation based on activity from an actual large enterprise network. The results demonstrate the potential of using hyper-heuristic techniques to rapidly evolve and react to emerging cybersecurity threats.
In the paper, a Role Mining problem, which is the cornerstone for creating Role-Based Access Control (RBAC) systems, is transferred to the domain of data spaces. RBAC is the most widespread model of access control in different multi-user information systems, including critical infrastructures. The data spaces is the perspective concept of creating information storage systems, which transforms the concept of databases, integrating in one system the information resources from other systems, and allows us to control their security on a centralized basis. The paper considers a mathematical statement of the RBAC design problem for data spaces and offers the approaches to its solving based on genetic algorithms. The proposed approaches consider requirements of compliance with role-based security policies in case of combining all users' sets and all permissions' sets in the data space. The paper considers main decisions on creation and enhancement of genetic algorithms which implementation increases their operational speed. The experimental assessment of the offered genetic algorithms shows their high performance.
Carbon dioxide Capture and Storage (CCS) is a viable technique for reducing CO2 emitted to the atmosphere. A simulation based optimization of well placement is a promising solution to geologic CO2 storage (GCS), which is a part of CCS. Covariance matrix adaptation evolution strategy (CMA-ES) is considered to apply for well placement problem because it is a state-of-the-art black-box continuous optimization algorithm. However, insufficient search by the algorithm is anticipated since well placement problem often forms a mixed integer programming problem. In this paper, we investigate the use of variants of CMA-ES to the optimization of well placement and injection schedule as a mixed integer programming problem. First we investigate the effect of each algorithmic component to treat integer variables on mixed integer programming test functions. Then, some promising variants are applied to the well placement and injection scheduling problem for a CCS project. We observed that the CMA-ES with step-size lower bound behaved robust and found better solutions than the variants without the bound, independently of initial search points. We bring up some issues of current optimization framework including the mixed integer support in the CMA-ES and the formulation of the GCS optimization problem.
Learning surrogates for product design and optimization is potential to capitalize on competitive market segments. In this paper we propose an approach to learn surrogates of product performance from historical clusters by using ensembles of Genetic Programming. By using computational experiments involving more than 500 surrogate learning instances and 27,858 observations of vehicle models collected over the last thirty years shows (1) the feasibility to learn function surrogates as symbolic ensembles at different levels of granularity of the hierarchical vehicle clustering, (2) the direct relationship of the predictive ability of the learned surrogates in both seen (training) and unseen (testing) scenarios as a function of the number of cluster instances, and (3) the attractive predictive ability of relatively smaller ensemble of trees in unseen scenarios. We believe our approach introduces the building blocks to further advance on studies regarding data-driven product design and market segmentation.
Cooperative co-evolution (CC) is a powerful evolutionary computation framework for solving large scale global optimization (LSGO) problems via the strategy of "divide-and-conquer", but its efficiency highly relies on the decomposition result. Existing decomposition algorithms either cannot obtain correct decomposition results or require a large number of fitness evaluations (FEs). To alleviate these limitations, this paper proposes a new decomposition algorithm named historical interdependency based differential grouping (HIDG). HIDG detects interdependency from the perspective of vectors. By utilizing historical interdependency information, it develops a novel criterion which can directly deduce the interdependencies among some vectors without consuming extra FEs. Coupled with an existing vector-based decomposition framework, HIDG further significantly reduces the total number of FEs for decomposition. Experiments on two sets of LSGO benchmark functions verified the effectiveness and efficiency of HIDG.
A wide range of real-world problems are multi-objective optimization problems (MOPs). Multi-objective evolutionary algorithms (MOEAs) have been proposed to solve MOPs, but the search process deteriorates with the increase of MOPs' dimension of decision variables. In order to solve the problem, firstly, the decision variables are divided into different groups by adopting a fast interdependency identification algorithm; secondly, a novel cooperative co-evolutionary algorithm is used to solve MOPs. Experiment results on large-scale problems show that the proposed algorithm is effective.
We consider collective tasks to be solved by simple agents synthesized automatically by means of neuroevolution. We investigate whether driving neuroevolution by promoting a form of selfish behavior, i.e., by optimizing a fitness index that synthesizes the behavior of each agent independent of any other agent, may also result in optimizing global, system-wide properties. We focus on a specific and challenging task, i.e., evolutionary synthesis of agent as car controller for a road traffic scenario. Based on an extensive simulation-based analysis, our results indicate that even by optimizing the behavior of each single agent, the resulting system-wide performance is comparable to the performance resulting from optimizing the behavior of the system as a whole. Furthermore, agents evolved with a fitness promoting selfish behavior appear to lead to a system that is globally more robust with respect to the presence of unskilled agents.
Owing to the immunity to illumination and atmospheric conditions, synthetic aperture radar (SAR) images have been the main source of data for environmental monitoring. However, it is a challenging task for change detection because of the influence of speckle noise. In this paper, we propose an unsupervised multiobjective particle swarm optimization approach based on decomposition for change detection in SAR images. For the change detection task, it can be modeled as a multiobjective optimization problem (MOP), which consists of two contradictory objectives, namely, retaining image change details and removing the speckle noise. We optimize this MOP by using particle swarm optimization, which decomposes it into a set of subproblems by assigning different weights to these two objectives, thus obtaining the optimal trade-off between them. To accurately identify changed regions, the strategy of majority voting is employed to assemble partial good solutions to generate the final change detection result. The impressive experimental results on both real data sets have demonstrated the effectiveness and superiority of the proposed method.
Performance comparisons of optimization algorithms are heavily influenced by the underlying indicator(s). In this paper we investigate commonly used performance indicators for single-objective stochastic solvers, such as the Penalized Average Runtime (e.g., PAR10) or the Expected Running Time (ERT), based on exemplary benchmark performances of state-of-the-art inexact TSP solvers. Thereby, we introduce a methodology for analyzing the effects of (usually heuristically set) indicator parametrizations - such as the penalty factor and the method used for aggregating across multiple runs - w.r.t. the robustness of the considered optimization algorithms.
Combinatorial optimization problems come in a wide variety of types but five common problem components can be identified. This categorization can aid the selection of interesting and diverse set of problems for inclusion in the combinatorial black-box problem benchmark. We suggest two real-world problems for inclusion into the benchmark. One is a transport-lot building problem and the other one is the clustered generalized quadratic assignment problem. We look into designing an interface for discrete black-box problems that can accommodate problems belonging to all of the described categories as well real-world problems that often feature multiple problem components. We describe three different interfaces for black-box problems, the first using a general encoding for all types of problems the second one using specialized encodings per problem type and the last one describes problems in terms of the available operators. We compare the strengths and weaknesses of the three designs.
This contribution focuses on the challenge of formulating a set of benchmark problems and/or a test-suite for Combinatorial Optimization problems when treated as black-box global optimization problems. We discuss the involved dilemmas and possible obstacles of such a compilation. To this end, we formulate a list of design questions that need to be answered as a first step in this compilation process. We articulate our perspective on these questions by proposing a rough classification of relevant problem classes, answering the posed questions, and suggesting a preliminary set of problems. While this position paper addresses the Evolutionary Computation community, it intends to offer an open-minded Computer Science perspective - by considering the broad definition of Combinatorial Optimization and by accounting for equivalent threads within Operations Research and Mathematical Programming communities. At the same time, this work capitalizes on prior art in algorithms' benchmarking, including the authors' own experience with the continuous BBOB benchmark problem set, as well as a number of discrete black-box optimization challenges frequently encountered in practice.
Measuring the performance of an optimization algorithm involves benchmark instances of related problems. In the area of discrete optimization, most well-known problems are covered by a large variety of problem instances already. However, while exploring the area of lesser-known optimization problems there is usually not a sufficient amount or variety of such benchmark instances available. The reasons for this lack of data vary from privacy or confidentiality issues to technical difficulties that prevent the collection of such data. This results in the inability to evaluate new optimization algorithms on these problems. Ideally, the necessary data for a variety of problem instances can be created randomly in advance to measure the performance of a set of algorithms. Random problem instance generators exist for specific problems already, however, generic tools that are applicable to multiple optimization problems are rare and usually restricted to a smaller subset of problems. We propose a generic problem instance generator for discrete optimization problems, which is easy to configure, and simple to expand to cover a broad variety of optimization problems. We show the capabilities of our tool by creating exemplary configurations for the TSP, Max-SAT and a real-world load allocation problem to generate random problem instances.
The first event of the Black-Box Discrete Optimization Benchmarking (BB-DOB) workshop series aims to establish a set of example problems for benchmarking black-box optimization algorithms for discrete or combinatorial domains. In this paper, we 1) discuss important features that should be embodied by these benchmark functions and 2) present the W-Model problem which exhibits them. The W-Model follows a layered approach, where each layer can either be omitted or introduce a different characteristic feature such as neutrality via redundancy, ruggedness and deceptiveness, epistasis, and multi-objectivity, in a tunable way. The model problem is defined over bit string representations, which allows for extracting some of its layers and stacking them on top of existing problems that use this representation, such as OneMax, the Maximum Satisfiability or the Set Covering tasks, and the NK landscape. The ruggedness and deceptiveness layer can be stacked on top of any problem with integer-valued objectives. We put the W-Model into the context of related model problems targeting ruggedness, neutrality, and epistasis. We then present the results of a series of experiments to further substantiate the utility of the W-Model and to give an idea about suitable configurations of it that could be included in the BB-DOB benchmark suite.
This paper provides a taxonomical identification survey of classes in discrete optimization challenges that can be found in the literature including a proposed pipeline for benchmarking, inspired by previous computational optimization competitions. Thereby, a Black-Box Discrete Optimization Benchmarking (BB-DOB) perspective is presented for the [email protected] Workshop. It is motivated why certain classes together with their properties (like deception and separability or toy problem label) should be included in the perspective. Moreover, guidelines on how to select significant instances within these classes, the design of experiments setup, performance measures, and presentation methods and formats are discussed.
Robust and multi-modal optimisation are two important topics that have received significant attention from the evolutionary computation community over the past few years. However, the two topics have usually been investigated independently and there is a lack of work that explores the important intersection between them. This is because there are real-world problems where both formulations are appropriate in combination. For instance, multiple 'good' solutions may be sought which are distinct in design space for an engineering problem - where error between the computational model queried during optimisation and the real engineering environment is believed to exist (a common justification for multi-modal optimisation) - but also engineering tolerances may mean a realised design might not exactly match the inputted specification (a robust optimisation problem). This paper conducts a preliminary examination of such intersections and identifies issues that need to be addressed for further advancement in this new area. The paper presents initial benchmark problems and examines the performance of combined state-of-the-art methods from both fields on these problems.
This paper proposes a framework for solving high-dimensional robust multi-objective optimization problems. A decision variable classification-based framework is developed to search for robust Pareto-optimal solutions. The decision variables are classified as highly and weakly robustness-related variables based on their contributions to the robustness of candidate solutions. In the case study, an order scheduling problem in the apparel industry is investigated via the proposed framework. The experimental results reveal that the performance of robust evolutionary optimization can be greatly improved via analyzing the properties of decision variables and then decomposing the high-dimensional robust multi-objective optimization problem.
In electrical engineering, the deviation from average values of a signal is viewed as noise to the useful measurement. In human societies, however, the diversity of the exhibited characteristics are a sign of individuality and personal worth. We investigate the effect of uncertainty variables in the environment on multi-agent societies (MAS) and the consequences of the deviation, from the average features of the modeled agents. We show the performance of heterogeneous MAS of agents in comparison to morphologically identical homogeneous systems, preserving the same average physical and sensory abilities for the system as a whole, in a dynamic environment. We are employing a form of the predator-prey pursuit problem in attempt to measure the different performance of homogeneous MAS with average parameters and its heterogeneous counterpart. The effects of uncertainty in our work is investigated from the viewpoint of (i) employing a limited number of initial situations to evolve the team of predator agents, (ii) generality to unforeseen initial situations, and (iii) robustness to perception noise. Key statistics are the efficiency of evolution of the successful behavior of predator agents, effectiveness of their behavior and its degradation because of newly introduced situation or noise. Preliminary results indicate that a heterogeneous system can be at least as good as its homogeneous average equivalent, in solution quality at the expense of the runtime of evolution.
This work formalizes a multi-objective evolutionary approach for the segmentation issue according to Piecewise Linear Representation. It consists in the approximation of a given digital curve by a set of linear models minimizing the representation error and the number of such models. This solution allows the final user to decide from the best array of best found solutions considering the different objectives jointly. The proposed approach eliminates the difficult a-priori parameter choices in order to satisfy the user restrictions (the solution choice is performed a-posteriori, from the obtained array of solutions) and allows the algorithm to be run a single time (since the whole Pareto front is obtained with a single run and different solutions may be chosen at different times from that Pareto front in order to satisfy different requirements). This solution will be applied to Petroleum Industry in particular to the problem of identifying resources from extraction areas in order to optimize their operational costs and production capacity.
Minimal trees in polygonal maps aim at minimizing the connectivity in a network while avoiding obstacle collision. Being closely related to the Steiner Tree Problem, yet with a different scope, minimal trees aim at connecting origin-destination pairs, given in a bipartite network, to allow the joint transport of information, goods, resources and people. In this paper, we propose a method to tackle the bundling problem of minimal trees in modular bipartite networks by using a two-layer optimization based on Differential Evolution with a convex representation of coordinates. Our computational experiments in polygonal domains considering both convex and non-convex geometry show the feasibility and the efficiency of the proposed approach.
This study presents the crude oil scheduling problem with four objectives divided in two different levels of importance. It comes from a real refinery where the scheduling starts on the offloading of ships, encompasses terminal and refinery tanks, a crude pipeline, and finishes on the output streams of the crude distillation units. We propose a new approach for the Quantum-Inspired Grammar-based Linear Genetic Programming (QIGLGP) evolutionary algorithm to handle the multiple objectives of the problem using the non-dominance concept. The modifications are concentrated on the population updating and sorting steps of QIGLGP. We tackle difference of importance among the objectives using the principle of violation of constraints. The problem constraints define if an instruction will or not be executed but do not affect the violation equation of the objectives. The individuals which have objective values under a pre-defined upper limit are better ranked. Results from five scenarios showed that the proposed model was able to significantly increase the percentage of runs with acceptable solutions, achieving success ratio of 100% in 3 cases and over 70% in 2 other ones. They also show that the Pareto front of these accepted runs contains a set of non-dominated solutions that could be analyzed by the decision maker for his a posteriori decision.
In recent years, planning sport training sessions with computational intelligence have been studied by many authors. Most of the algorithms were used for proposing basic and advanced training plans for athletes. In a nutshell, most of the solutions focused on the individual sports disciplines, such as, for example, cycling and running. To the knowledge of the authors, few efforts were invested into planning sports training sessions in triathlon. Triathlon is considered as a popular multi-disciplinary sport consisting of three different sport disciplines. Therefore, planning the triathlon training sessions is much harder than the planning in individual sport disciplines. In this paper, we propose an initial framework for planning triathlon training sessions using Particle Swarm Optimization. Preliminary results are also shown.
This paper develops a prototype system for evaluating upper limb function that combines Internet of Things (IoT) and Augmented Reality (AR) technology. IoT builds the network of patients, test environment and doctor's surgery from which the system gathers and exchanges data such as the speeds and locations of hand movement. With the help of AR technology, the real-world test environment is overlaid with the information (e.g. the instructions from doctors, the progress of evaluation) gathered from the IoT. Compared to the conventional system, the detailed information of hand movement supports further assessments and the instructions generated in the AR scene for patients relieve the burden of doctors. The control experiments were conducted to explore the effects of the object size, the existence of obstacles and the hand dominance on the upper limb function using the developed system. The results verified the validity of the developed system.
Currently, a system is being developed that gathers information about a dementia patient's condition and sends it to a smartphone. Through this system, caregivers in a nursing facility could always check on their patients' current condition and act accordingly. However, they are generally too busy to constantly check their smartphones for "non-critical" information about patients. This research proposes putting a small robot in front of a patient to speak to the patient in a professional manner in reaction to his/her current condition. Caregivers nearby could hear the robot and then determine the patient's condition. When the caregiver is free, he/she could approach the patient and start talking to him/her in the same manner as the robot just did1.
In this paper, focusing on a sensor network for monitoring human activities, the suitable architecture is discussed to obtain sustain-ability. After briefly showing a general architecture in present, the problems happening with long time usage are described. Then, our ideas are suggested to solve these problems.
In dementia care, caregivers need to respond adequately and in a timely manner to their recipients' needs, which is a challenging problem. As it is difficult to measure the effect of responses with strongly evidenced methods, computational simulation may be a useful means of evaluating the results. This article introduces conceivable cases that may be candidates for simulation.
Hedonic games are coalition formation games where agents have hedonic preferences for coalition structures. The main focus of hedonic games has been on notion of stability. In this paper, however, we consider envy based fairness in hedonic games. We investigate emptiness of envy-free coalition structures and summarize the relationship with core stability.
We proposed XCS-VRc3 that can extract useful rules (classifiers) from data and verify its effectiveness. The difficulty of mining real world data is that not only the type of the input state but also the number of instances varies. Although conventional method XCS-VRc is able to extract classifiers, the generalization of classifiers was insufficient and lack of human readability. The proposed XCS-VRc3 incorporating "generalization mechanism by comprehensive classifier subsumption" to solves this problem. Specifically, (1) All classifiers of the matching set subsume other classifiers, (2) Abolition of the inappropriate classifier deletion introduced by XCS-VRc (3) Preferentially select classifier with small variance of output in genetic algorithm. To verify the effectiveness of XCS-VRc3, we applied on care plan planning problem in a nursing home (in this case, identifying daytime behavior contributing to increase the ratio of deep sleep time). Comparing the association rules obtained by Apriori, and classifiers obtained by XCS-VRc3, the followings was found. First, abolishing the inappropriate classifier deletion and comprehensively subsuming promotes various degrees of generalization. Second, parent selection mechanism can obtain classifiers with small output variance. Finally, XCS-VRc3 is able to extract a small number classifiers equivalent to large number of rules found in Apriori.
The present trend in the development of computer architectures that offer improvements in both performance and energy efficiency has provided clusters with interconnected nodes including multiple multi-core microprocessors and accelerators. In these so-called heterogeneous computers, the applications can take advantage of different parallelism levels according to the characteristics of the architectures in the platform. Thus, the applications should be properly programmed to reach good efficiencies, not only with respect to the achieved speedups but also taking into account the issues related to energy consumption. In this paper we provide a multi-objective evolutionary algorithm for feature selection in electroencephalogram (EEG) classification, which can take advantage of parallelism at multiple levels: among the CPU-GPU nodes interconnected in the cluster (through message-passing), and inside these nodes (through shared-memory thread-level parallelism in the CPU cores, and data-level parallelism and thread-level parallelism in the GPU). The procedure has been experimentally evaluated in performance and energy consumption and shows statistically significant benefits for feature selection: speedups of up to 73 requiring only a 6% of the energy consumed by the sequential code.
Genetic algorithms (GA) [8] are currently one of the most widely used meta-heuristics to solve engineering problems. Furthermore, parallel genetic algorithms (pGAs) are useful to find solutions of complex optimizations problems in adequate times [16]; in particular, problems with complex fitness. Some authors [1] state that using pGAs improves the quality of solutions in terms of the number of evaluations needed to find one. This reason, together with the improvement in evaluation time brought by the simultaneous running in several nodes, have made parallel and distributed evolutionary algorithms a popular methodology.
During the initialization step, a genetic programming (GP) system traditionally creates a population of completely random programs to populate the initial population. These programs almost always perform poorly in terms of their total error---some might not even output the correct data type. In this paper, we present new methods for initialization that attempt to generate programs that are somewhat relevant to the problem being solved and/or increase the initial diversity (both error and behavioral diversity) of the population prior to the GP run. By seeding the population---and thereby eliminating worthless programs and increasing the initial diversity of the population---we hope to improve the performance of the GP system. Here, we present two novel techniques for initialization (Lexicase Seeding and Pareto Seeding) and compare them to a previous method (Enforced Diverse Populations) and traditional, non-seeded initialization. Surprisingly, we found that none of the initialization methods result in significant differences in problem-solving performance or population diversity across five program synthesis benchmark problems. We attribute this lack of difference to our use of lexicase selection, which seems to rapidly converge on similar populations regardless of initialization method.
Machine learning algorithms have found to be useful for the solution of complex engineering problems. However, due to problem's characteristics, such as class imbalance, classical methods may not be formidable. The authors believe that the application of multi-objective optimization design can improve the results of machine learning algorithms on such scenarios. Thus, this paper proposes a novel methodology for the creation of ensembles of classifiers. To do so, a multi-objective optimization design approach composed of two steps is used. The first step focus on generating a set of diverse classifiers, while the second step focus on the selection of such classifiers as ensemble members. The proposed method is tested on a real-world competition data set, using both decision trees and logistic regression classifiers. Results show that the ensembles created with such technique outperform the best ensemble members.
We propose the method of selection of auxiliary objectives (2 + 2λ)-EA+RL which is the population-based modification of the EA+RL method. We analyse the efficiency of this method on the problem X
Recently, it was shown that Many-Objective Evolutionary Algorithms (MaOEAs) that employ a set of convex weight vectors are overspecialized in solving certain benchmark problems. This over-specialization is due to a high correlation between the Pareto fronts of the test problems and the simplex formed by the weight vectors. In furtherance of avoiding this issue, we propose a novel steady-state MaOEA that does not require weight vectors and adaptively chooses between two density estimators: one based on the IGD+ indicador that strengthens convergence to the Pareto front and another one, based on the s-energy indicator, which improves the diversity of the solutions. This approach, called sIGD+-MOEA, is compared with respect to NSGA-III, MOEA/D, IGD+-EMOA and MOMBI2 (which are MaOEAs that employ convex weight vectors) on the test suites WFG and WFG-1, using the hypervolume indicator. Experimental results show that sIGD+-MOEA is a promising alternative that can solve many-objective optimization problems whose Pareto fronts present different geometries.
Recently, an idea of evolutionary multi-tasking has been proposed and applied to various types of optimization problems. The basic idea of evolutionary multi-tasking is to simultaneously solve multiple optimization problems (i.e., tasks) in a cooperative manner by a single run of an evolutionary algorithm. For this purpose, each individual in a population has its own task. This means that a population of individuals can be viewed as being divided into multiple sub-populations. The number of sub-populations is the same as the number of tasks to be solved. In this paper, first we explain that a multi-factorial evolutionary algorithm (MFEA), which is a representative algorithm of evolutionary multi-tasking, can be viewed as a special island model. MFEA has the following two features: (i) Crossover is performed not only within an island but also between islands, and (ii) no migration is performed between islands. Information of individuals in one island is transferred to another island through inter-island crossover. Next, we propose a simple implementation of evolutionary multi-tasking in the framework of the standard island model. Then, we compare our island model with MFEA through computational experiments. Promising results are obtained by our implementation of evolutionary multi-tasking.
A Multi-objective optimization problem with several different Pareto optimal solution sets is defined as a multi-modal multi-objective optimization problem. Finding all the Pareto optimal solution sets for this type of problem can provide more options for the decision maker, which is important in some real-world situations. The Multi-objective evolutionary algorithm based on decomposition (MOEA/D) has been proved to perform well in various multi-objective problems but it does not perform well in finding all the Pareto optimal solution sets for multi-modal multi-objective optimization problems. In this paper, a MOEA/D variant is proposed to solve these problems. K solutions are assigned to each weight vector in the MOEA/D variant and the solutions are evaluated by not only the scalarizing function values but also the minimum distance from other solutions with the same weight vector and the average distance from the neighboring solutions in the same weight vector grid. Experimental results show that the MOEA/D variant performs much better than the original MOEA/D on the multi-modal distance minimization problems.
Search-based software engineering, a discipline that often requires finding optimal solutions, can be a viable source for problems that bridge theory and practice of evolutionary computation. In this research we consider one such problem: generation of data connections in a distributed control application designed according to the IEC 61499 industry standard.
We perform the analysis of the fitness landscape of this problem and find why exactly the simplistic (1 + 1) evolutionary algorithm is slower than expected when finding an optimal solution to this problem. To counteract, we develop a population-based algorithm that explicitly maximises diversity among the individuals in the population. We show that this measure indeed helps to improve the running times.
Currently, most of the decomposition-based multi-objective evolutionary algorithms (MOEA) are based on a number of prespecified weight vectors. However, when the shape of the Pareto front is inconsistent with the distribution of weight vectors, only a small number of non-dominated solutions can be obtained inside the Pareto front. Moreover, if an external archive with a dominance-based update mechanism is used to overcome this difficulty, a large computational time is needed which is often unpractical. In this paper, we propose a new archive update mechanism with a new archive structure. A large weight vector grid is used to update the archive by using a scalarizing function. The proposed archive update mechanism can be applied to any MOEA with an external archive. We examine the effectiveness of the proposed mechanism on MOEA/D. Our experimental results show that MOEA/D with the proposed new archive update mechanism is able to find more solutions inside the Pareto front compared to MOEA/D without the archive. In addition, it needs less computational time compared to MOEA/D with the dominance-based archive update mechanism.
In this paper, a new Multi-Objective Particle Swarm optimization algorithm (MOPSO) with adaptive inertia weight and dynamic search space is introduced for multi-objective optimization. The objective of the study is to investigate an efficient MOPSO to deal with large-scale optimization and multi-modal problems. The new adaptive inertia weight strategy allows the inertia weight to keep varying throughout the algorithm process, which helps the algorithm to escape from local optima. The dynamic search space design can avoid decision variables from continuously taking their extreme values, and therefore enhances the searching efficiency. The performance of the proposed algorithm was compared with three popular multi-objective algorithms in solving seven benchmark test functions. Results show that the new algorithm can produce reasonably good approximations of the Pareto front, while performing with a budget of 10,000 fitness function evaluations.
Prior work has demonstrated that genetic programming systems often maintain higher levels of population diversity when using lexicase selection than when using other parent selection methods, and that the use of lexicase selection improves problem-solving performance in many circumstances. It has been suggested that it is not only the maintenance of diversity that is responsible for the performance of lexicase selection, but more specifically the production and maintenance of "specialists" that matters, where specialists are defined to be individuals with the lowest error, relative to the rest of the population, on a small number of training cases regardless of total error. Here we provide results of experiments that uphold this suggestion by tracking the numbers of specialists selected by lexicase selection and by tournament selection in a genetic programming system solving software synthesis problems. Our results also show that lexicase selection selects parents with poor total error far more frequently than tournament selection, even near the ends of successful runs, suggesting that such selections are integral to the improved problem-solving performance of lexicase selection.
Genetic algorithms and artificial neural networks are two widely-used techniques that can be combined with each other to produce evolved neural networks. Some research has also looked at the use of diploidy in genetic algorithms for possible advantages over the haploid genetic representation usually used, most notably in the form of better adaptation to changing environments. This paper proposes a diploid representation for evolving neural networks, used in an agent-based simulation. Two versions of the diploid representation were tested with a haploid version in one static and two changing environments. All three genetic types performed differently in different environments.
In machine learning, feature selection is a commonly used technique for improving the predictive performance and interpretability of a trained model. Feature selection techniques are classified into three approaches: the filter, wrapper, and embedded approaches. The embedded approach performs the feature selection process during the model training and achieves a good balance between performance and computational cost in general. In the paper, we propose a novel embedded feature selection method using probabilistic model-based evolutionary optimization. We introduce the multivariate Bernoulli distribution, which determines the selection of features, and we optimize its parameters during the training. The distribution parameter update rule is the same as that of the population-based incremental learning (PBIL), but we simultaneously update the parameters of the machine learning model using an ordinary gradient descent method. This method can be easily implemented into non-linear models, such as neural networks. Moreover, we incorporate the penalty term into the objective function to control the number of selected feature. We apply the proposed method with the neural network model to the feature selection of three classification problems. The proposed method achieves competitive performance and reasonable computational cost compared with conventional feature selection methods.
The Controller Area Network (CAN) in vehicles provides serial communication between electronic control units that manage engine, transmission, steering and braking. Researchers have recently demonstrated the vulnerability of the network to cyber-attacks which can manipulate the operation of the vehicle and compromise its safety. Some proposals for CAN intrusion detection systems, that identify attacks by detecting packet anomalies, have drawn on one-class classification, whereby the system builds a decision surface based on a large number of normal instances. The one-class approach is discussed in this paper, together with initial results and observations from implementing a classifier new to this field. The Compound Classier has been used in image processing and medical analysis, and holds advantages that could be relevant to CAN intrusion detection.
The Graph Coloring Problem is an important benchmark problem for decision and discrete optimization problems. In this work, we perform a comparative experimental study of four algorithms based on Swarm Intelligence for the 3-Graph Coloring Problem: Particle Swarm Optimization (PSO), Artificial Bee Colonies (ABC), Cuckoo Search (CS) and FireFly Algorithm (FFA). For each algorithm, we test parameter settings published in the literature, as well as parameters found by an automated tuning methodology (irace). This comparison may shed some light at the strengths and weaknesses of each algorithm, as well as their dependence on parameter values.
The Pareto Improving Particle Swarm Optimization algorithm (PI-PSO) has been shown to perform better than Global Best PSO on a variety of benchmark problems. However, these experiments used benchmark problems with a single dimension, namely 32d. Here we compare global best PSO and PI-PSO on benchmark problems of varying dimensions and with varying numbers of particles. The experiments show that PI-PSO generally achieves better performance than PSO as the number of dimensions increases. PI-PSO also outperforms PSO on problems with the same dimension but with the same or fewer particles.
We investigate the convergence speed, accuracy, robustness and scalability of PSOs structured by regular and random graphs with 3 ≤ k ≤ n. The main conclusion is that regular and random graphs with the same averaged connectivity k may result in significantly different performance, namely when k is low.
Multimodal optimization (MMO) aims at finding multiple optimal (or close to optimal) solutions, which plays a crucial role in various fields. However, most of the efforts have been devoted to the continuous MMO domain, while little attention has been paid to discrete problems like the traveling salesman problem (TSP). This paper makes a proof of principle study on multimodal TSP. Particularly, we design a test suite for multimodal TSP and then develop an ant colony algorithm to accomplish the optimization task. The traditional ant algorithms such as the ant colony system are unable to maintain multiple solutions because of the global convergence. To deal with this problem, we propose a novel niching ant colony system (NACS). The algorithm employs a niching strategy and multiple pheromone matrices to preserve population diversity and keep the trace of multiple paths. The experimental results are presented to validate the good performance of the proposed algorithm.
We demonstrate the applicability of inverted Ant Colony Optimization (iACO) for target search in a complex unknown indoor environment simulated by a maze. The colony of autonomous ants lay repellent pheromones to speed up exploration of the unknown maze instead of reinforcing presence in already visited areas. The role of a target-collocated beacon signal within the maze is evaluated in terms of its utility to guide the search. Variants of iACO were developed, with beacon initialization (iACO-B), and with increased sensing ranges (iACO-R with a 2-step far-sightedness) to quantify the most effective one. The presented models can be implemented with self-organizing wireless sensor networks carried by autonomous drones or vehicles and can offer life-saving services of localizing victims of natural disasters or during major infrastructure failures.
Test case prioritization which aims to improve the efficiency of regression testing by ordering test cases is an active research topic that has attracted increasing attention recently. This paper proposes an efficient Ant Colony System(ACS) framework to solve the coverage based test case prioritization problem. A tour based heuristic function and a tree shape pheromone updating rule are designed. The underlying rationale is to make full use of the ants' partially built solutions in their later traveling and to vary their search at the same time. The proposed method is tested on six benchmark problems with different scales, and the experimental results have demonstrated that the proposed method can outperform several state-of-the-art methods in terms of the Average Percentage of Statement Coverage(APSC).
Cuckoo search (CS), as a relatively recent emerged swarm intelligence algorithm, is powerful and popular for the complex real parameter global optimization. However, the premature convergence has greatly affected the performance of original CS. Inspired from the individuals in the population will converge to the weighted average of global best and personal best in particle swarm optimization (PSO), we proposed a novel Gaussian bare-bones CS algorithm, named GBCS, in which the new solution for a cuckoo is generated by the Lévy flight or the Gaussian bare-bones method in a random manner. Experimental results have proved that the proposed algorithm is promising.
This paper focuses on Artificial Bee Colony (ABC) algorithm in dynamic optimization problems (DOPs), and proposes the improvements for ABC algorithm in DOPs as ABC algorithm based on adaptive local information sharing (ABC-alis). To investigate the tracking ability to dynamic change of ABC-alis, it is compared the improved algorithm to two cases of dynamic change. These two cases are "Case 1: Periodic Change" and "Case 2: Continuing Change". The experimental results revealed that the following implications: (1) ABC-alis can adapt with various dynamic changes; (2) ABC-alis has high tracking performance against continuous change.
This paper proposes the multiple swarm optimization method composed of some numbers of populations, each of which is optimized by the different swarm optimization algorithm to adapt to dynamically change environment. To investigates the effectiveness of the proposed method, we apply it into the complex environment, where the objective function changes in a certain interval. The intensive experiments have revealed that the performance of the proposed method is better than the other conventional algorithms (i.e., particle swarm optimization (PSO), cuckoo search (CS), differential evolution (DE)) in terms of convergence and fitness.
We propose a scouting strategy to find better searching directions in fireworks algorithm (FWA) to enhance its exploitation capability. It generates spark individuals from a firework individual one by one by checking if the generated spark climbs up to a better direction, and this process continues until spark individual climbing down is generated, while canonical FWA generates spark individuals around a firework individual at once. We can know potential search directions from the number of consciously climbing up sparks. Besides this strategy, we use a filtering strategy for a random selection of FWA, where worse sparks are eliminated when their fitness is worse than their parents, i.e. fireworks, and become unable to survive in the next generation. We combined these strategies with the enhanced FWA (EFWA) and evaluated using 28 CEC2013 benchmark functions. Experimental results confirm that the proposed strategies are effective and show better performance in terms of convergence speed and accuracy. Finally, we analyze their applicability and provide some open topics.
Population-based optimization algorithms have proved themselves very effective and efficient way for solving some complex problems, particularly for problems of non-linear and non-convex nature. 2D-3D registration is one such problem where inherent non-linearity and high-dimensionality along with non-convex optimization nature makes it very difficult to achieve satisfying accuracy especially when starting point for optimization is not ideal. Because of the underlying structure of population-based optimization algorithms, especially particle swarm optimization (PSO), 2D-3D registration with PSO is expected to yield better accuracy compared to conventional gradient-based optimization algorithms. Another considerable factor is that gradient approximation error makes non-gradient methods more favorable for the case of 2D-3D registration over gradient-based methods. Our experiment on 2D-3D registration using virtual X-ray shows that PSO has better accuracy and convergence rate than gradient based approaches like Stochastic Gradient Descent (SGD), Momentum Stochastic Gradient Descent (MSGD) and Nesterov Accelerated Gradient (NAG).
In this work, we focus on the Dendritic Cell Algorithm (DCA), a bio-inspired classifier, and its limitation when coping with very large datasets. To overcome this limitation, we propose a novel distributed DCA version for data classification based on the MapReduce framework to distribute the functioning of this algorithm through a cluster of computing elements. Our experimental results show that our proposed distributed solution is suitable to enhance the performance of the DCA enabling the algorithm to be applied over big data classification problems.
Promoting diversity in an evolving population is important for Evolutionary Computation (EC) because it reduces premature convergence on suboptimal fitness peaks while still encouraging both exploration and exploitation [3]. However, some types of diversity facilitate finding global optima better than other types. For example, a high mutation rate may maintain high population-level diversity, but all of those genotypes are clustered in a local region of a fitness landscape. Fitness sharing [3], on the other hand, promotes diversity via negative density dependence forcing solutions apart. Lexicase selection [5] goes one step further, dynamically selecting for diverse phenotypic traits, encouraging solutions to actively represent many portions of the landscape.
Evolution in nature has allowed biological systems to develop and survive in many different environments. It can be attributed to one of the major features of natural evolution: its open-endedness, that can be considered as the ability to continuously produce novelty and/or complexity [1]. This feature is critical to allow an agent to continuously adapt to its environment. We propose here an extension of Quality Diversity algorithms to make it more open-ended. Quality Diversity algorithms aim at generating a large set of diverse solutions [3, 10]. They can be used in a two-steps process in which (1) a diverse set of solutions is generated offline before (2) the agent can exploit it online to find the behavior that fits to the situation [2, 4--6]. QD algorithms main goal is to fill a behavior space whose dimensions are defined by behavior descriptors. Current QD algorithms can generate novelty and complexity, but within the frame of these behavior descriptors. To make the evolutionary process more open-ended, we extend Cully and Demiris framework [3] and introduce Multi-Container Quality Diversity algorithms (MCQD). MCQD are QD algorithms relying on multiple behavior spaces that can be added on the fly. MCQD thus aims at implementing an open-ended evolutionary process that would explore any new behavior space that could be found of interest during the search process.
We show that the Baldwin effect is capable of evolving few-shot supervised and reinforcement learning mechanisms, by shaping the hyperparameters and the initial parameters of deep learning algorithms. This method rivals a recent meta-learning algorithm called MAML "Model Agnostic Meta-Learning," which uses second-order gradients instead of evolution to learn a set of reference parameters that can allow rapid adaptation to tasks sampled from a distribution. The Baldwin effect does not require gradients to be backpropagated to the reference parameters or hyperparameters, and permits effectively any number of gradient updates in the inner loop, learning strong learning dependent biases.
This paper proposes a new recurrent neural network (RNN) structure evolved to control the gait of a hexapod robot for fast forward walking. In this evolutionary robot, the gait control problem is formulated as an optimization problem with the objective of a fast forward walking speed and a small deviation in the forward walking direction. Evolutionary optimization of the RNNs through a group-based hybrid metaheuristic algorithm is proposed to find the optimal RNN controller. Preliminary simulation results with comparisons show the advantage of the proposed approach1.
Muscle and tendon elasticity enables animals to interact with their environment softly, reducing ground impact force and increasing efficiency of locomotion. Traditional rigid body robots remain the commercially viable option, but incorporating flexibility can harness the benefits exhibited by natural organisms. In this paper, we examine how the addition of passive flexibility impacts performance and locomotive efficiency in a quadruped animat. Results show that the addition of flexibility in the spine and lower limbs of a quadruped animat significantly increases the distance traveled compared to a fully rigid-body animat. However, replacing these passively flexibile joints with actively controlled joints results in the farthest traveling individuals while maintaining similar efficiency. It appears that increases in DOF and joint configuration are the drivers of performance increases rather than passive flexibility.
The emergence and inter-play of cooperation versus competition in groups of individuals has been widely studied, for example using game-theoretic models of eusocial insects [11], [1] experimental evolution in bacterium [5], and agent-based models of societal institutions [8]. Game theory models have been demonstrated as indispensable analytical tools to complement our understanding of the emergence and social mechanics of natural phenomena such as cooperation and competition. For example, game theory models have supported the supposition that cooperation between individuals and competition between groups are critical factors in cultural evolution in human societies [2]. However, such game theory models are ultimately limited by their own abstractions and lack consideration for the role of complex phenomena such as evolutionary and environmental change in shaping emergent social phenomena.
Policy (behavior) transfer is a method to speed-up and improve learning by leveraging knowledge from learning in related but simpler tasks. That is, learned information is reused and shared between a source and target tasks, where target tasks were used as a starting point for continuing learning [16]. Policy transfer has been widely studied in the context of Reinforcement Learning (RL) methods [21], where various studies have consistently demonstrated that transferring knowledge learned on a source task accelerates learning and increases solution quality in target tasks by exploiting relevant prior knowledge [22].
We use an evolutionary robotics approach to demonstrate how the choice of robot morphology can affect one specific aspect of neural networks: their ability to resist catastrophic forgetting.
Wagner's modularity inducing problem domain is a key contribution to the study of the evolution of modularity, including both evolutionary theory and evolutionary computation. We study its behavior under classical genetic algorithms. Unlike what we seem to observe in nature, the emergence of modularity is highly conditional and dependent, for example, on the eagerness of search. In nature, modular solutions generally dominate populations, whereas in this domain, modularity, when it emerges, is a relatively rare variant. Emergence of modularity depends heavily on random fluctuations in the fitness function; with a randomly varied but unchanging fitness function, modularity evolved far more rarely. Interestingly, high-fitness non-modular solutions could frequently be converted into even-higher-fitness modular solutions by manually removing all inter-module edges. Despite careful exploration, we do not yet have a full explanation of why the genetic algorithm was unable to find these better solutions.
To date, efforts to automatically configure problem representations for classes of optimization problems have yielded few practical results. We show that a recently proposed approach for training neural G-P maps for optimization problems yields maps that generalize poorly to translated problem instances. We propose that alternative neural architectures---especially ones that allow the number of control genes to be greater than the number of phenotypic traits---may provide a means of learning maps that are better able to generalize to new problem instances.
Interactive Evolutionary Computation (IEC) is used for creating media contents suited to each user's feelings. To obtain media contents commonly suited to multiple users, distributed approach was employed in previous IECs based on Genetic Algorithm. This study proposes Distributed Interactive Differential Evolution (DIDE) by employing Differential Evolution (DE). Based on each user's subjective selection and scoring with Interactive DE, DIDE exchanges good solutions between users. Through the exchange, it is expected that the good solution for all users is obtained. A fundamental experiment was conducted with a simple DIDE system creating sign sounds for two users. Distance between DE vectors obtained by two users and fitness values were investigated.
Interactive Evolution (
Real-time video game problems are very challenging because of short response times and numerous state space issues. As global companies and research institutes such as Google, Facebook, Intel and Carnegie Mellon university continue to develop Artificial Intelligence(AI) and participated in various Game AI competitions, many AI developers are implementing algorithms, such as Monte Carlo Tree Search (MCTS) and Deep Reinforcement Learning (DRL), to solve problems. However, these algorithms also have a number of limitations, including the inability to effectively calculate the number of possible cases present in the games and the large amount of time required for computation. We combine the genetic algorithm, which is very effective in finding general solutions to solve the constraints of AI, and the MCTS, which dominates the recent Fighting Game AI Competition, into a hierarchical structure. We propose to call it Hybrid Fighting Game AI.
M
This paper proposes a three-dimensional (3D) entire shape reconstruction method that performs simultaneous 3D registration of multiple depth images obtained from multiple viewpoints. With the combination of a silhouette-based objective function and evolutionary computation algorithms, the proposed method realizes the entire shape reconstruction from small number (two or three) of depth images, which do not involve enough overlapping regions for other 3D registration methods. In particular, this paper proposes a CMA-ES algorithm with regional intensification techniques (CMA-ESPR+VF) to speed up the registration process. Experimental results show that the proposed CMA-ESPR+VF achieved a speedup that is at most 18 times faster than self-adaptive differential evolution.
Automatic Design of Algorithms (ADA) treats algorithm choice and design as a machine learning problem, with problem instances as training data. However, this paper reveals that, as with classification and regression, for ADA not all training sets are equally valuable.
We apply genetic programming ADA for bin packing to several new and existing benchmark sets. Using sets with narrowly-distributed features for training results in highly specialised algorithms, whereas those with well-spread features result in very general algorithms. Variance in certain features has a strong correlation with the generality of the trained policies.
Estimation of distribution algorithms have already demonstrated their utility when solving a broad range of combinatorial problems. However, there is still room for methodological improvements when approaching constrained type problems. The great majority of works in the literature implement external repairing or penalty schemes, or use ad-hoc sampling methods in order to avoid unfeasible solutions. In this work, we present a new way to develop ED As for this type of problems by implementing distance-based exponential probability models defined exclusively on the set of feasible solutions. In order to illustrate this procedure, we take the 2-partition balanced Graph Partitioning Problem as a case of study, and design efficient learning and sampling methods in order to use these distance-based probability models in EDAs.
We consider the design of a supply chain network for a blood bank system to satisfy the needs of hospitals in a certain region, by integrating strategic, tactical and operational decisions. In the current blood distribution network, hospitals keep their own inventory and procure bloods from a main blood bank. We propose an alternative model, in which, some of the hospitals are selected as local blood banks (LBBs) and serve the hospitals that are assigned to them. Thus, we try to solve a complex problem which aims to find optimal number and locations of LBBs, assignment of hospitals to opened LBBs and the weekly and daily routes between the facilities. We formulate a mixed integer nonlinear programming model to combine these decisions to minimize total system cost and propose a simulated annealing heuristic approach to find near optimal solutions. We analyze the performance of the heuristic via detailed numerical studies.
This paper investigates evolving routing policy for general Uncertain Capacitated Arc Routing Problems (UCARP) with any number of vehicles, and for the first time, designs a novel model for online decision making (i.e. meta-algorithm) for multiple vehicles in service simultaneously. Then, we develop a GPHH based on the meta-algorithm. The experimental studies show the GPHH can evolve much better policies than the state-of-the-art manually designed policy. In addition, the reusability of the evolved policies dramatically decreases when the number of vehicles changes, which suggests a retraining process when a new vehicle is brought or an existing vehicle breaks down.
Resource scheduling is always a highly concerned NP-hard problem in operations research. Taking advantage of estimation of distribution (EDA) algorithms, this paper develops a histogram EDA (HEDA) for resource scheduling. First, a histogram-based distribution model is adopted. The height of each bin in the histogram is updated using the accumulation strategy according to the ranking of individuals. Second, a repair strategy is applied to fix all the newly sampled solutions into feasible ones that satisfy the deadline constraint. Experimental results show that the proposed HEDA is promising, particularly in large-scale instances.
This study considers single machine scheduling with the machine operating at varying speed levels for different jobs with release dates and sequence-dependent setup times, in order to examine the trade-off between makespan and total energy consumption. A bi-objective mixed integer linear programming model is developed employing this speed scaling scheme. The augmented ε-constraint method with a time limit is used to obtain a set of non-dominated solutions for each instance of the problem. An energy-efficient multi-objective variable block insertion heuristic is also proposed. The computational results on a benchmark suite consisting of 260 instances with 25 jobs from the literature reveal that the proposed algorithm is very competitive in terms of providing tight Pareto front approximations for the problem.
In the domain of Service-Oriented Architecture, web services are selected and composed to meet users' functional and non-functional requirements. A few researchers have proposed Evolutionary Computation (EC) techniques for service composition problems, where semantic matchmaking quality and Quality of Service (QoS) are individually or jointly optimised. However, these EC-based approaches allow best individuals (i.e., composition solutions) to be carried across generations, but does not consider the knowledge of the promising individuals for breeding better solutions. Due to its capability of learning the knowledge of good solutions, Estimation of Distribution Algorithm (EDA) has been successfully applied to tackle semi-automated QoS-aware service composition, where an abstract composition workflow is assumed known. However, this assumption is not always satisfied, so learning the knowledge of solutions without pre-given workflows is very challenge. We propose an EDA-based service composition approach to jointly optimize QoS and semantic matchmaking quality in a fully automated way and our experiment evaluation demonstrates the efficiency and the effectiveness of our proposed approach.
Genetic Programming Hyper-Heuristic (GPHH) has shown success in evolving dispatching rules for dynamic Flexible Job Shop Scheduling (FJSS). In this paper, we focus on feature construction to improve the effectiveness and efficiency of GPHH, and propose a GPHH with Cooperative Co-evolution with Feature Construction (CCGP-FC). The experimental results showed that the proposed CCGP-FC could improve the smoothness of the convergence curve, and thus improve the stability of the evolutionary process. There is a great potential to improve the FC methods, such as filtering the meaningless building blocks, and incorporating with feature selection to improve the terminal set.
A barrier tree is a model for representing the hierarchical distribution of local optima and valleys. While it is useful, constructing a barrier tree is challenging for a large problem instance. In this paper, we propose an efficient method to approximate the barrier tree. One important subgoal is to estimate a saddle point between two solutions, and it is achieved by exploiting the bias of the Great Deluge Algorithm. We also present a case study of a pseudo-boolean problem of size 296, which is roughly 6 times larger than the scale that the existing methods can handle.
he research in capacitated arc routing problems (CARPs) is getting more and more attention for its wide applications in reality. Memetic algorithms (MAs) are promising in solving CARPs, but the intensity of local search (LS) in MAs should adapt to the evolution of the population for achieving the maximal effectiveness. In this paper, a novel MA based on adaptive adjustment of LS intensity (LIMA) is proposed. LIMA dynamically adjusts the probability of LS according to the distance between the individual of the population and the solution lower bound for further deepening the LS depth of potential solutions. It makes the algorithm spend as much time as possible on more potential solutions, so as to shorten the computation time and speed up the convergence. Experimental results show that LIMA has faster convergence speed and better global search ability than traditional MAs. Adaptively tuning the LS intensity of a MA has high potential for solving complex problems.1
This paper introduces a hybrid system called R-EDML, combining the sequential decision making of Reinforcement Learning (RL) with the evolutionary feature prioritizing process of Evolutionary Distance Metric Learning (EDML) in clustering aiming to optimize the input space by reducing the number of selected features while maintaining the clustering performance. In the proposed method, features represented by the elements of EDML distance transformation matrices are prioritized. Then a selection control strategy using Reinforcement Learning is learned. R-EDML was compared to normal EDML and conventional feature selection. Results show a decrease in the number of features, while maintaining a similar accuracy level.
This paper examines three generic strategies for improving the performance of neuro-evolving convolutional neural networks (CNNs): node-level mutation operations, epigenetic weight initialization and pooling connections. These were implemented using the Evolutionary eXploration of Augmenting Convolutional Topologies (EXACT) algorithm. Results were gathered over the period of a month using a volunteer computing project, where over 225,000 CNNs were trained and evaluated across 16 different EXACT searches. The node mutation operations where shown to dramatically improve evolution rates over traditional edge mutation operations (as used by the NEAT algorithm), and epigenetic weight initialization was shown to further increase the accuracy and generalizability of the trained CNNs. As a negative but interesting result, allowing for pooling connections was shown to degrade the evolution progress. The best trained CNNs reached 99.46% accuracy on the MNIST test data in under 13,500 CNN evaluations - accuracy comparable with some of the best human designed CNNs.
Neuroevolution is a field in which evolutionary algorithms are applied with the goal of evolving Neural Networks (NNs). This paper studies different variants of the Semantic Learning Machine (SLM) algorithm, a recently proposed supervised learning neuroevolution method. Perhaps the most interesting characteristic of SLM is that it searches over unimodal error landscapes in any supervised learning problem where the error is measured as a distance to the known targets. SLM is compared with the NeuroEvolution of Augmenting Topologies (NEAT) algorithm and with a fixed-topology neuroevolution approach. Experiments are performed on a total of 9 real-world regression and classification datasets. The results show that the best SLM variants generally outperform the other neuroevolution approaches in terms of generalization achieved, while also being more efficient in learning the training data. The best SLM variants also outperform the common NN backpropagation-based approach under different topologies. The most efficient SLM variant used in combination with a recently proposed semantic stopping criterion is capable of evolving competitive neural networks in a few seconds on the vast majority of the datasets considered. A final comparison shows that a NN ensemble built with SLM is able to outperform the Random Forest algorithm in two classification datasets.
Sorting data into groups and clusters is one of the fundamental tasks of artificially intelligent systems. Classical clustering algorithms rely on heuristic (k-nearest neighbours) or statistical methods (k-means, fuzzy c-means) to derive clusters and these have performed well. Neural networks have also been used in clustering data, but researchers have only recently begun to adopt the strategy of having neural networks directly determine the cluster membership of an input datum. This paper presents a novel strategy, employing NeuroEvolution of Augmenting Topologies to produce an evoltionary neural network capable of directly clustering unlabelled inputs. It establishes the use of cluster validity metrics in a fitness function to train the neural network.
A recent approach for improving the accuracy of ensemble models is confidence-based modeling. Thereby, confidence measures, which indicate an ensemble prediction's reliability, are used for identifying unreliable predictions in order to improve a model's accuracy among reliable predictions. However, despite promising results in previous work, no comparable results for public benchmark data sets have been published yet.
This paper applies confidence-based modeling with GP-based symbolic binary classification ensembles on a set of medical benchmark problems to make statements about the concept's general applicability. Moreover, extensions for multiclass classification problems are proposed.
Adaptive boosting (AdaBoost) is a method for building classification ensemble, which combines multiple classifiers built in an iterative process of reweighting instances. This method proves to be a very effective classification method, therefore it was the major part of our evolutionary inspired classification algorithm.
In this paper, we introduce the Genetic Programming with AdaBoost (GPAB) which combines the induction of classification trees with genetic programming (GP) and AdaBoost for multiple class problems. Our method GPAB builds the ensemble of classification trees and uses AdaBoost through the evolution to weight instances and individual trees.
To evaluate the potential of the proposed evolutionary method, we made an experiment where we compared the GPAB with Random Forest and AdaBoost on several standard UCI classification benchmarks. The results show that GPAB improves classification accuracy in comparison to other two classifiers.
Subspace clustering techniques become popular in identifying local patterns from high dimensional data. In this paper, we present a multiobjective optimization based evolutionary algorithm in order to tackle the subspace clustering problem. Previous state-of-the-art algorithms on subspace clustering optimize implicitly or explicitly a single cluster quality measure. The proposed approach optimizes two cluster quality measures namely PBM-index and XB-index simultaneously. The developed algorithm is applied to seven standard real-life datasets for identifying different subspace clusters. Experimentation reveals that the proposed algorithm is able to take advantages of its evolvable genomic structure and multiobjective based framework and it can be applied to any data set.
This work proposes a method for predicting the internal mechanisms of individual agents using observed collective behaviours by multi-agent reinforcement learning (MARL). Since the emergence of group behaviour among many agents can undergo phase transitions, and the action space will not in general be smooth, natural evolution strategies were adopted for updating a policy function. We tested the approach using a well-known flocking algorithm as a target model for our system to learn. With the data obtained from this rule-based model, the MARL model was trained, and its acquired behaviour was compared to the original. In the process, we discovered that agents trained by MARL can self-organize flow patterns using only local information. The expressed pattern is robust to changes in the initial positions of agents, whilst being sensitive to the training conditions used.
In this study, a neuroevolution strategy using Multi-Agent Incorporated Hierarchical Ensemble Model (MAIHEM) inspired by human incorporated company structure is proposed. It utilizes the hierarchical structure to ensemble modules of entities into firms to preserve complex structure at lower level, and at higher level incorporates firms into departments to facilitate multiple objectives. The corporate level structure from the top guides and reviews their overall performance. The ensemble structure not only compete within their own ranks, but also cooperate and swap/merger underlying units for fast adaptation without compromising their existing structures. The preliminary result with multi-constrained music melody generation shows this strategy can not only solve complex multi-objective tasks steadily but also preserve diversity in the population.
Automatic clustering problems, which need to detect the appropriate clustering solution without a pre-defined number of clusters, still remain challenging in unsupervised learning. In many related works, cluster validity indices (CVIs) play an important role to evaluate the goodness of partitioning of data sets. However, there is no CVI that is likely to ensure reliable results for different structures of data. In this paper, we present a study of evolutionary many-objective optimization (EMaO) based automatic clustering, in contrast to the weighted sum validity function defined in literature, several validity functions (more than 3) are considered to be optimized simultaneously here. Since the research of EMaO is still in its fancy, we take four state-of-the-art EMaO algorithms into consideration as the underlying optimization tool. To be more applicable and efficient for clustering problems, the encoding scheme and genetic operators are redesigned. Experiments show that, for the purpose of this study, it is promising to address automatic clustering problems based on a suitable EMaO approach.
Probabilistic modeling in multi-objective optimization problems (MOPs) has mainly focused on capturing and representing the dependencies between decision variables in a set of selected solutions. Recently, some works have proposed to model also the dependencies between the objective variables, which are represented as random variables, and the decision variables. In this paper, we investigate the suitability of copula models to capture and exploit these dependencies in MOPs with a continuous representation. Copulas are very flexible probabilistic models able to represent a large variety of probability distributions.
While many of real-world industrial design problems involve several constraints, researches on multiobjective evolutionary algorithms (MOEAs) for problems with many constraints or the benchmark problems themselves are limited. The novel constrained multiobjective optimization benchmark problem based on a real-world car structure design optimization problem, termed Mazda CdMOBP, has more desirable characteristics as a constrained benchmark problem than the existing ones. The experimental results with 12 constrained MOEAs on this problem suggest the importance of balancing all of three factors of convergence, diversity, and feasibility and knowledge of proper settings of not only MOEA and CHT but also these parameters are imperative for application of MOEAs to industrial design problems.
In this paper, we propose MOEA/D-LIEM2 to optimize multiple real-valued objective functions which have complex interaction among variables by employing linkage identification. We compared the proposed algorithm with MOEA/D without linkage identification. As a result, we found that the proposed algorithm out-performs the original MOEA/D for problems consisting of two deceptive functions with linkage.
The (α, β)-k Feature Set Problem is a mathematical model proposed for multivariate feature selection. Unfortunately, addressing this problem requires a combinatorial search in a space that grows exponentially with the number of features. In this paper, we propose a novel index-based Memetic Algorithm for the Multi-objective (α, β)-k Feature Set Problem. The method is able to speed-up the search during the exploration of the neighborhood on the local search procedure. We evaluate our algorithm using six well-known microarray datasets. Our results show that exploiting the natural feature hierarchies of the data can have, in practice, a significant positive impact on both the solutions' quality and the algorithm's execution time.
A benchmark problem based on a real-world car structure design optimization1 is proposed. The benchmark problem is constructed by using a response surface method from the design optimization result of a car structure design optimization problem. Because this benchmark problem bases on actual car structure design optimization result conducted by Mazda, it contains features of real-world design optimization problems. Objectives are the minimization of the total weight of the different type of cars and maximization of the number of common gauge (standard plate thickness) parts among the different type of cars. This benchmark problem has 148 discrete design parameters and 36 design constraints for simultaneous design optimization of two types of cars and 222 discrete design parameters and 54 design constraints for simultaneous design optimization of three types of cars. Thus, it is a scalable and multiobjective design optimization problem with many and discrete design parameters and many and severe constraints. The benchmark problem is available on our website (http://ladse.eng.isas.jaxa.jp/benchmark/).
In this paper we adapt ϵ-lexicase selection, a parent selection strategy designed for genetic programming, to solve many-objective optimization problems, ϵ-lexicase selection has been shown to perform well in regression due to its use of full program semantics for conducting selection. A recent theoretical analysis showed that this selection strategy preserves individuals located near the boundaries of the Pareto front in semantic space. We hypothesize that this strategy of biasing search to extreme positions in objective space may be beneficial for many-objective optimization as the number of objectives increases. Here, we replace program semantics with objective fitness to define ϵ-lexicase selection for many-objective optimization. We then compare this method to multi-objective optimization methods from literature on problems ranging from 3 to 100 objectives. We find that ϵ-lexicase selection outperforms state-of-the-art optimization algorithms in terms of convergence to the Pareto front, spread of solutions, and CPU time for problems with more than 3 objectives.
The mission planning of agile earth observation satellite (AEOS) involves multiple objectives to be optimized simultaneously. Total profit, observed target number, averaged image quality, satellite usage balance and averaged timeliness are the five objectives considered in this paper. The problem is a mixed-integer problem with constraints and belongs to the class of NP-hard problems. Two preference-based evolutionary algorithms, i.e., T-NSGA-III and T-MOEA/D, are proposed with problem-specific coding and decoding strategies to solve the problem. Target region, which is defined by preferred range of each objective, is used for preference articulation. Experiments show that the proposed algorithms can obtain Pareto optimal solutions within the target region efficiently. They outperform Pareto-based T-NSGA-II with regard to Hypervolume indicator and CPU runtime.
Despite the extensive application of multi-objective evolutionary algorithms (MOEAs) to solve multi-objective optimization problems (MOPs), understanding their working principles is still open to research. One of the most popular and successful MOEA approaches is based on Pareto dominance and its relaxed version, Pareto ϵ-dominance. However, such approaches have not been sufficiently studied in problems of increased complexity. In this work, we study the effects of the working mechanisms of the various components of these algorithms on test problems with difficult Pareto set topologies. We focus on separable unimodal and multimodal functions with 2, 3, and 4 objectives, all having difficult Pareto set topologies. Our experimental study provides some interesting and useful insights to understand better Pareto dominance-based MOEAs.
The road to a better design of multi- and many-objective evolutionary algorithms requires a deeper understanding of their behavior. A step on this road has recently been taken with the proposal of compartmental models to study population dynamics. In this work, we push this step further by introducing a new set of features that we link with algorithm performance. By tracking the number of newly discovered Pareto Optimal (PO) solutions, the previously-found PO solutions and the remaining non-PO solutions, we can track the algorithm progression. By relating these features with a performance measure, such as the hypervolume, we can analyze their relevance for algorithm comparison. This study considers out-of-the-box implementations of recognized multi- and many-objective optimizers belonging to popular classes such as conventional Pareto dominance, extensions of dominance, indicator, and decomposition based approaches. In order to generate training data for the compartmental models, we consider multiple instances of MNK-landscapes with different numbers of objectives.
A large number of Multi-Objective Evolutionary Algorithms employ reference directions in order to establish relative preferences for each objective function. Uniform Design (UD), Simplex Lattice Design (SLD) and their variants are techniques commonly used to generate a set of uniformly distributed reference directions with the aim of capturing the whole Pareto optimal front. In this paper, we present a comparative study of UD and SLD methods when solving Many-objective Optimization problems and we design a new strategy that combines SLD with multiple layers and UD techniques. Our preliminary results indicate that our proposed approach is able to outperform state-of-the-art methods in many-objective optimization problems.
In many practical multi-objective optimization problems, evaluations of objectives and constraints are computationally time-consuming because they require expensive simulations of complicated models. In this paper, we propose a metamodel-based multi-objective evolutionary algorithm to make a balance between error uncertainty and progress. In contrast to other trust region methods, our method deals with multiple trust regions. These regions can grow or shrink in size according to the deviation between metamodel prediction and high-fidelity evaluation. We introduce a performance indicator based on hypervolume to control the size of the trust regions. We compare our results with a standard metamodel-based approach without trust region and a multi-objective evolutionary algorithm. The results suggest that our trust region based methods can effectively solve test and real-world problems using limited solution evaluations with increased accuracy.
Determining a scheduling system's framework conditions (e.g. number of vehicles or employees) results in a hierarchical optimization problem, which can be solved through evolutionary bilevel optimization. In this paper, we propose an approach to gain better understanding of a scheduling system's behavior by applying visual analytics on the whole set of evaluated solutions during the bilevel optimization procedure. The results show that bilevel innovization can be used to support the decision making process in a strategic planning context by providing useful information regarding the scheduling system's behavior.
Balancing exploration and exploitation is fundamental to the performance of an evolutionary algorithm. In this paper, we propose a survival analysis method to address this issue. Results of the analysis is used to adaptively choose appropriate new solution creation operators which prefer either exploration or exploitation. In the developed algorithm, a differential evolution recombination operator is used for the exploration purpose, while a new clustering-based operator is proposed for exploitation. Empirical comparison with four well-known multi-objective evolutionary algorithms on test instances with complex Pareto sets and Pareto fronts indicates the effectiveness and outperformance of the developed algorithms on these test instances in terms of commonly-used metrics.
For the last couple of years, the development of many-objective optimization problems opened new avenues of research in the evolutionary multi-objective optimization domain. There are already a number of algorithms to solve such problems, now the next challenge is to interpret the results produced by those algorithms. In this paper, we propose an alternative way to visualize high-dimensional Pareto fronts where the goal is to present the Pareto front in terms of a decision maker's perspective. A decision maker is more interested in the different aspects of the end results instead of the convergence and spread of a Pareto front solutions. They are interested in Pareto-optimal solutions that offer the most trade-off. They are also interested to know the boundary solutions of a Pareto front. In this paper, we present a way to visualize the Pareto front in high dimension by keeping those criteria in mind.
Nondominated sorting (NS) is commonly needed in multi-objective optimization to distinguish the fitness of solutions. Since it was suggested, several NS algorithms have been proposed to reduce its time complexity. In our study, we found that their performances are closely related to properties of the distribution of a data set, especially the number of fronts. To address this issue, we propose a novel NS algorithm Filter Sort. We also propose a new benchmark data generator for evaluating the performance of a NS algorithm. Experimental results show that our algorithm is superior to several state-of-the-art NS algorithms in most cases.
In parallel and distributed environments, generational evolutionary algorithms often do not exploit the full potential of the computation system since they have to wait until the entire population is evaluated before starting selection procedures. Steady-state algorithms can perform fitness evaluations asynchronously however, if the algorithm updates its state in a complicated way - which is common in multiobjective evolutionary algorithms - the threads will eventually have to wait until this update finishes.
The most expensive part of the update procedure in NSGA-II is non-dominated sorting. We turned the existing incremental non-dominated sorting algorithm into an asynchronous one using several concurrency techniques: a single entry-level lock, finer-grained locks on non-domination levels, and a non-blocking approach using compare-and-set operations. Our experimental results reveal the trade-off between the work-efficiency of the algorithm and the achieved amount of parallelism.
Differential Evolution (DE) is a robust optimization algorithm, but it suffers from the stagnation problem in which individuals may not escape from a local optimum. In this article, we proposed a new Cauchy mutation using multiple exponential recombination, self-adaptive parameter control, and linear failure threshold reduction. The proposed method is a simple yet efficient to mitigate the stagnation problem, and it can improve the convergence speed of DE. Our experimental results show that the proposed method can find more accurate solutions to complicated problems.
Benchmarks are important for comparing performance of optimisation algorithms, but we can select instances that present our algorithm favourably, and dismiss those on which our algorithm under-performs. Also related are automated design of algorithms, which use problem instances (benchmarks) to train an algorithm: careful choice of instances is needed for the algorithm to generalise.
We sweep parameter settings of differential evolution to applied to the BBOB benchmarks. Several benchmark functions are highly correlated. This may lead to the false conclusion that an algorithm performs well in general, when it performs poorly on a few key instances. These correlations vary with the number of evaluations.
Exploratory landscape analysis techniques are widely used methods for the algorithm selection problem. The existing sampling methods for exploratory landscape analysis are usually designed to sample unbiased candidates for measuring the characteristics of the entire search space. In this paper, we discuss the limitation of the unbiased sampling and propose a novel sampling method, which is algorithm based and thus biased. Based on the sampling method, we propose several novel landscape features which are called algorithm based landscape features. The proposed features are compared with the conventional landscape features using supervised and unsupervised learning. The experimental results show that the algorithm based landscape features outperform the conventional landscape features.
The recently proposed dynamic constrained multi-objective evolutionary algorithm (DCMOEA) is effective to handle constrained optimization problems (COPs). However, one drawback of DCMOEA is it mainly searches the global optimum from infeasible regions, which may result in the bias against feasible solutions. Then the useful information about the optimal direction of feasible regions is not fully used. To overcome this defect, this paper proposes a novel selection strategy based on DCMOEA framework, called NSDCMOEA to solve COPs. The performance of NSDCMOEA is evaluated using a set of benchmark suites. Experimental results validate that the proposed method is better than or very competitive to five state-of-the-art algorithms.
Multifactorial 1 Optimization (MFO) has been attracting considerable attention in the evolutionary computation community. In this paper, we propose a general multi-population evolution framework (MPEF) for MFO, wherein each population has its own random mating probability (rmp) and is used for its own task. The benefits of using MPEF are twofold: 1) Various well-developed evolutionary algorithms (EAs) can be easily embedded into MPEF for solving the task(s) of MFO problems; 2) Different populations can implement different genetic material transfers. Moreover, for instantiation, we embed a powerful differential evolution algorithm, namely SHADE, into MPEF to form a multipopulation DE algorithm (MPEF-SHADE) for solving MFO problems. The experimental results on nine MFO benchmark problems show that MPEF-SHADE is significantly better than or at least competitive with other multifactorial evolution algorithms, such as MFEA, MFDE, MFPSO and AMA.
Traditional Gaussian estimation of distribution algorithm (EDA) may suffer from premature convergence and has a high risk of falling into local optimum when dealing with multimodal problem. In this paper, we first attempt to improve the performance of EDA by utilizing historical solutions and develop a novel archive-based EDA variant. The use of historical solutions not only enhances the search efficiency of EDA to a large extent, but also significantly reduces the population size so that a faster convergence could be achieved. Then, the archive-based EDA is further integrated with an novel adaptive clustering strategy for solving multimodal optimization problems. Taking the advantage of the clustering strategy in locating different promising areas and the powerful exploitation ability of the archive-based EDA, the resultant algorithm is endowed with strong capability in finding multiple optima. To verify the efficiency of the proposed algorithm, we tested it on a set of niching benchmark problems, the experimental results indicate that the proposed algorithm is competitive.
In this work, we give some numerical investigations of the CMAES-APOP on some multi-modal functions and introduce a relaxed version of this algorithm to cope with the hard Schwefel function. The numerical simulations will show the efficiency of our approach.
It has been shown that cooperative coevolution (CC) can effectively deal with large scale optimization problems (LSOPs) through a divide-and-conquer strategy. However, its performance is severely restricted by the current context-vector-based sub-solution evaluation method because this method requires too many computation resources. To alleviate this issue, this study proposes an adaptive surrogate model assisted CC framework which adaptively constructs surrogate models for different sub-problems by fully considering their characteristics. By this means, the computation cost could be greatly reduced without significantly sacrificing evaluation quality. Empirical studies on IEEE CEC 2010 large scale benchmark suit show that the concrete algorithm based on this framework performs well.
There are two types of Chance Constrained Problems (CCPs), namely Separate CCP (SCCP) and Joint CCP (JCCP). This paper extends the optimization method for solving SCCP and applies it to JCCP. By using Bonferroni inequality, JCCP is stated with the Cumulative Distribution Function (CDF) of uncertain function value. Then Weighted Empirical CDF (W_ECDF) is used to approximate the CDF in JCCP. A new Adaptive Differential Evolution (ADE) combined with W_ECDF is also contrived for solving both CCPs.
Recently the use of Radial Basis Functions (RBF) has been introduced as an optional alternative to co-Kriging in the context of multi-fidelity surrogate modeling. In this paper, we compare the performance of Random Forest-based co-surrogates to the previously introduced co-Kriging and co-RBF using a set of bi-fidelity benchmark problems in 2, 4 and 8 dimensions. Our results show that there is a minimal overall difference between the different co-surrogate models with regards to final performace, although the training of Random Forests takes much less time compared to the Kriging and RBF methods.
In this short paper, we reveal the issue of the covariance matrix adaptation evolution strategy when solving a function with periodic variables. We investigate the effect of a simple modification that the coordinate-wise standard deviation of the sampling distribution is restricts to the one-fourth of the period length. This is achieved by pre- and post-multiplying a diagonal matrix to the covariance matrix.
In contrast to the traditional single-task evolutionary algorithms, multi-factorial evolutionary algorithm (MFEA) has been proposed recently to conduct evolutionary search on multiple tasks simultaneously. It aims to improve convergence characteristics of the tasks to be tackled by seamlessly transferring knowledge among them. Towards superior multitasking performance, the evaluation of task relationship plays an important role for grouping the related tasks, and solve them at the same time. However, in the literature, only a little work has been conducted to provide deeper insights in the measure of task relationship in MFEA. In this paper, we thus present a study of similarity measure between tasks for MFEA from three different perspectives. 21 multitasking problem sets are developed to investigate and analyze the effectiveness of the three similarity measures with MFEA for evolutionary multitasking.
How to disseminate information or ideas through social network connection has received much attention in recent years. The core issue is to find a seed set of initially active individuals that can maximize the influence spread. In this paper, we present a comparative study on three basic algorithms for such issue. Experimental results show that although genetic algorithm can find slightly better solution than other algorithms, it is too time-consuming to be cost-effective. Hence, our on-going work is aimed at improving the search efficiency of different bio-inspired meta-heuristic methods.
In this paper we introduce KafkEO, a cloud native evolutionary algorithms framework that is prepared to work with population-based metaheuristics by using micro-populations and stateless services as the main building blocks; KafkEO is an attempt to map the traditional evolutionary algorithm to this new cloud-native format.
In IEEE 802.11 Wireless Local Area Network (WLAN), the mobile stations (STAs) have to perform handover to keep network connections when they move out of the range of an access point (AP). However, the STAs collect the information of surrounding APs by channel scanning, which will cause high handover latency and degrade the quality of mobility. Therefore, minimizing the scanning delay is key to enabling seamless communications over WLAN. In this paper, we propose a genetic algorithm (GA) algorithm combined with neighbor list mechanism to reduce handover latency. Using this proposed approach, the handover latency is minimized by reducing both the number of scanned channels and the waiting time for each channel. Simulation results demonstrate that our approach improves throughput up to 9.5% and reduces handover delay up to 74% compared to standard IEEE 802.11.
This paper aims to show a glimpse of the potential benefits of using genetic algorithms (GA's) in EEG data analysis. The system attempts machine-learning based classification of a mental state reached during competitive gameplay and an idle state. EEG activity from a large number of experienced players of League of Legends has been recorded during both idle periods and during a competitive, ranked game. A proven, industry-tested GA is used in order to optimize aspects of the brain-computer interface (BCI) system, by evolving both electrode and feature sets. Alongside a rather high cross validation base classification accuracy, statistically significant improvements have been obtained by applying the GA in selecting both electrode subset and features. The run time improvements are evident as well, although even further improvements are possible. This not only allows major improvements in both processing power and data acquisition requirements, but it is a step further in the attempt of bringing both BCI technology closer to consumer products, and cognitive state identification as a means of improving gaming experience, as well as other aspects of everyday life.
A deeper understanding in how the power consumption of evolutionary algorithms behaves is necessary to keep meeting high quality results without wasting energy resources. This paper presents a black-box model for predicting the energy consumption of the NSGA-II-based Parallel Islands approach to Multiobjective Feature Selection (pi-MOFS). We analyzed the power usage of each stage in pi-MOFS when applied to a brain-computer interface classification task. Fitness evaluation showed as the most relevant stage for the case study presented in time and power consumption. The results showed a 98.81% prediction accuracy for the eight experiments designed. We believe that our findings and methodology can be used to apply pi-MOFS, NSGA-II and other EAs to current optimization problems from an energy-aware perspective.
Any evolutionary method may store the fitness values for the genotypes it has already rated. Any time the fitness is to be computed, the check may be made if the fitness for the same genotype was not computed earlier. If so, then instead of re-evaluating the same genotype, the stored value from the repository may be returned. Such technique will be denoted as fitness caching. It is easy to implement in any evolutionary method, and it minimizes the number of fitness function evaluations (FFE), which is desirable. Despite its simplicity fitness caching may significantly affect the computation load spent on fitness computation. Moreover, it may cause that the FFE will not be a reliable computation load measure.
Given the advances in areas such as home automation, agricultural networks, smart cities, designers often need to design protocols that utilize the features of that network while dealing with its limitations. Utilizing standardized protocols for such networks may not be appropriate as they may not address limitations of the network such as heterogeneous nodes or limited capability of some nodes. While designing a customized protocol for that network would be desirable, it is extremely time-consuming unless we can automate the development of the required protocol. In this paper, we present NetSynth, a GP based mechanism to develop customized protocols for the given network. NetSynth lets us conveniently describe a network using an XML file, and it synthesizes protocols that suit the input network by considering the characteristics specific to the given network.
We propose a heterogeneous island model where each of the islands can run a different optimization algorithm. The distributed computation is managed by a central planner, that re-plans the methods during the run of the algorithm - less successful methods are removed while new instances of more successful methods are added. We show that this re-planning improves the performance of the optimization algorithm.
A portfolio optimization problem involves optimal allocation of finite capital to a series of assets to achieve an acceptable trade-off between profit and risk in a given investment period. In the paper, the extended Markowitz's mean-variance portfolio optimization model is studied with some practical constraints. We introduce a new operator and an adaptive strategy for improving the performance of the multi-dimensional mapping algorithm (MDM) proposed specially for the portfolio optimization. Experimental results show that the modification is efficient on tackling large-scale portfolio problems.
We propose a framework for estimating the quality of solutions in a robust optimisation setting by utilising samples from the search history and using MC sampling to approximate a Voronoi tessellation. This is used to determine a new point in the disturbance neighbourhood of a given solution such that - along with the relevant archived points - they form a well-spread distribution, and is also used to weight the archive points to mitigate any selection bias in the neighbourhood history. Our method performs comparably well with existing frameworks when implemented inside a CMA-ES on 9 test problems collected from the literature in 2 and 10 dimensions.
The multi-point dynamic aggregation (MPDA) is a typical task planning problem. In order to solve the MPDA problem efficiently a hybrid differential evolution (DE) and estimation of distribution algorithm (EDA) called DE-EDA is proposed in this paper, which combines the merits of DE and EDA. The DE-EDA has been applied to multiple MPDA instances of different scales, and compared with EDA and two versions of DE in convergence speed and solution quality separately. The results demonstrate the DE-EDA can solve the MPDA problem effectively.
This paper proposes an efficient solution selection method in a surrogate-assisted asynchronous multi-objective evolutionary algorithm. Our previous research proposed a novel multi-objective evolutionary algorithm that integrates a surrogate evaluation model with asynchronous approach, named as AELMOEA/D. AELMOEA/D constructs a surrogate model with extreme learning machine (ELM) and generates a promising solution by MOEA/D with a constructed ELM model. A generated promising solution is selected in the order of the indexes of the weighted vector of MOEA/D, and is evaluated asynchronously. In contrast to the previous method, the proposed method considers degree of search progress of each weight vector and selects a promising solution in a region where the search progress is insufficient. To evaluate the degree of the search progress, this study employs crowding distance, which is basically used in NSGA-II. To investigate the effectiveness of the proposed method, we conduct the experiment on a multi-objective optimization benchmark problem. The experimental result revealed that the proposed method can accelerate the convergence speed of the optimization without deteriorating the performance compared with the previous method.
Complex systems' modeling and simulation are powerful ways to investigate a multitude of natural phenomena providing extended knowledge on their structure and behavior. However, enhanced modeling and simulation require integration of various data and knowledge sources, models of various kinds, intelligent components in one composite solution. Growing complexity of such composite model leads to the need of specific approaches for management of such model. To support automatic building and management of complex models we propose a general evolutionary computation approach based on an evolutionary investigation of model phase space to identify the best model's structure and parameters.
In this paper, we propose two new approaches to rank the frequently used empirical cumulative distribution functions (ECDFs) for performance assessment of stochastic optimization algorithms. In the first approach, the different orders of stochastic dominance among running lengths are adopted in a hierarchical manner: the first order stochastic dominance is tested and the second order is used when the first order leads to incomparable results. In the second approach, ECDFs are considered as local Pareto front of the bi-criteria decision-making problem, in which one objective is to achieve a high success rate and the other is to use as few function evaluations as possible. In this case, it is proposed to adopt the multi-objective performance indicator to handle incomparable ECDFs.
In evolutionary algorithms, a preselection operator aims to choose some promising offspring solutions for a further environmental selection. Most existing preselection operators are based on fitness values, surrogate models, or classification models. Since a preselection operation can be regarded as a classification procedure, the classification based preselection is a natural choice for evolutionary algorithms. However, it is not trivial to prepare 'positive' and 'negative' training samples by using binary and/or multi-class classification models in preselection. To deal with this problem, this paper proposes a one-class classification based preselection (OCPS) scheme, which only needs one class of 'positive' training samples. The proposed OCPS scheme is applied to two state-of-the-art evolutionary algorithms on a test suite. The experimental results show the potential of OCPS on improving the performance of some existing evolutionary algorithms.
In this paper, we proposed a novel differential evolution (DE) variant with multi-information guidance. First, based on a rank-based method, the DE population is divided into three groups by using both of the fitness information and position information. Then three distinct combinations of mutation strategy and parameter settings are assigned to these three groups respectively. Last, a neighborhood search operator is conducted with the aim of using the neighborhood information. Experimental results on 22 well-known benchmark functions have shown the effectiveness of our approach.
This paper investigates the possibility of evolving new particle swarm equations representing a collective search mechanism, acting in environments with unknown external dynamics, using Geometric Semantic Genetic Programming (GSGP). The proposed method uses a novel initialization technique - the Evolutionary Demes Despeciation Algorithm (EDDA)- which allows to generate solutions of smaller size than using the traditional ramped half-and-half algorithm. We show that EDDA, using a mixture of both GP and GSGP mutation operators, allows us to evolve new search mechanisms with good generalization ability.
Accurate early diagnosis and monitoring of neurodegenerative conditions is essential for effective disease management and treatment. This research develops automatic methods for detecting brain imaging preclinical biomarkers for olfactory dysfunction in early stage Parkinson's disease (PD) by considering the novel application of evolutionary algorithms. Classification will be applied to PD patients with severe hyposmia, patients with no/mild hyposmia, and healthy controls. An additional novel element is the use of evolutionary algorithms to map and predict the functional connectivity using rs-fMRI. Cartesian Genetic Programming (CGP) will be used to classify dynamic causal modelling (DCM) data as well as timeseries data. The findings will be validated using two other commonly used classification methods (ANN and SVM) and by employing k-fold cross-validation. Developing methods for identifying early stage PD patients with hyposmia is relevant since current methods of diagnosing early stage PD have low reliability and accuracy. Furthermore, exploring the performance of CGP relative to other methods is crucial given the additional benefits it provides regarding easy classifier decoding. Hence, this research underscores the potential relevance of DCM analyses for classification and CGP as a novel classification tool for brain imaging data with medical implications for disease diagnosis, particularly in early stages.
Genetic programming(GP) is a powerful tool to solve Symbolic Regression that requires finding mathematic formula to fit the given observed data. However, existing GPs construct solutions based on building blocks (i.e., the terminal and function set) defined by users in an ad-hoc manner. The search efficacy of GP could be degraded significantly when the size of the building blocks increases. To solve the above problem, this paper proposes a multi-population GP framework with adaptively weighted building blocks. The key idea is to divide the whole population into multiple sub-populations with building blocks with different weights. During the evolution, the weights of building blocks in the sub-populations are adaptively adjusted so that important building blocks can have larger weights and higher selection probabilities to construct solutions. The proposed framework is tested on a set of benchmark problems, and the experimental results have demonstrated the efficacy of the proposed method.
Term-Weighting Scheme (TWS) is an important step in text classification. It determines how documents are represented in Vector Space Model (VSM). Even though state-of-the-art TWSs exhibit good behaviors, a large number of new works propose new approaches and new TWSs that improve performances. Furthermore, it is still difficult to tell which TWS is well suited for a specific problem. In this paper, we are interested in automatically generating new TWSs with the help of evolutionary algorithms and especially genetic programming (GP). GP evolves and combines different statistical information and generates a new TWS based on the performance of the learning method. We experience the generated TWSs on three well-known benchmarks. Our study shows that even early generated formulas are quite competitive with the state-of-the-art TWSs and even in some cases outperform them.
We explore the application of GOMEA, a recent method for discovering and exploiting the model for a problem in the form of linkage, to Grammatical Evolution (GE). GE employs an indirect representation based on familiar bit-string genotypes and is applicable to any problem where the solutions may be described using a context-free grammar, which hence greatly favors its wide adoption. Being general purpose, the representation of GE raises the opportunity for benefiting from the potential of GOMEA to automatically discover and exploit the linkage. We analyze experimentally the application of GOMEA to two bit-string-based variants of GE representation (the original representation and the recent WHGE) and show that GOMEA is clearly beneficial when coupled to WHGE, whereas it delivers no significant advantages when coupled with GE.
Supervised learning by means of Genetic Programming aims at the evolutionary synthesis of a model that achieves a balance between approximating the target function on the training data and generalising on new data. In this study we benchmark the approximation / generalisation of models evolved using different function set setups, across a range of symbolic regression problems. Results show that Koza's protected division and power should be avoided, and operators such as analytic quotient and sine should be used instead.
To improve product recall systems, we studied social simulation using a multi-agent system with a co-evolution model. This research is important because empirical approaches are no longer adequate for complex and diverse modern societies. Results of a simulation experiment have revealed the possibility that improving consumer trust in product recall actions is useful for producers and makes it possible to sell expensive products. We believe this work can contribute to support of government staff for improving product recall systems and to support of executive officers of product companies deliberating about recall decision strategies.
The implementation of the microgrid concept is expected to bring multiple advantages on the sustainability and reliability of electric power systems. In this paper, the performance of a modified Cuckoo's Search (CS) algorithm with parameter control is evaluated for solving a planning optimization problem which considers uncertainties of non dispatchable energy resources and both operations modes of a microgrid. The results show that the Cuckoo's Search algorithm offers advantages in terms of exploration of the search space.
Stock market prediction plays an important role in financial decision-making for investors. Many of them rely on news disclosures to make their decisions in buying or selling stocks. However, accurate modelling of stock market trends via news disclosures is a challenging task, considering the complexity and ambiguity of natural languages used. Unlike previous work along this line of research, which typically applies bag-of-words to extract tens of thousands of features to build a prediction model, we propose a sentiment analysis-based approach for financial market prediction using news disclosures. Specifically, sentiment analysis is carried out in the pre-processing phase to extract sentiment-related features from financial news. Historical stock market data from the perspective of time series analysis is also included as an input feature. With the extracted features, we use a support vector machine (SVM) to build the prediction model, with its parameters optimised through particle swarm optimisation (PSO). Experimental results show that our proposed SVM and PSO-based model is able to obtain better results than a deep learning model in terms of time and accuracy. The results presented here are to date the best in the literature based on the financial news dataset tested. This excellent performance is attributed to the sentiment analysis done during the pre-processing stage, as it reduces the feature dimensions significantly.
We developed a Voronoi-based algorithm, called Bio-Inspired Self Organizing Network (BISON), designed to provide a successful deployment of wireless sensor network (WSN) following fast, cost-efficient and self-organizing process, autonomously adapting to the unknown topology of the target environment, and avoiding obstacles discovered in real-time. To limit the power consumed during the deployment, BISON restricts each node to use only locally sensed information to adapt to live-discovered topology while avoiding obstacles and connecting with neighboring nodes. The algorithm is evaluated with respect to several metrics, and simulation results showed faster convergence to a fully connected network with lower deployment costs compared to similar algorithms reported in the literature.
A distal locking compression plate (DLCP) has been used to treat distal femoral fracture. An DLCP with a large number of screws can improve fixation stability, but the use of a small number of screws can reduce the damage on soft tissue and bone. The purpose of this study was to determine the best screw position and number of DLCP screws for distal femoral fracture fixation. Three-dimensional finite element models of the spine-pelvis-femur complex were developed to evaluate the fixation stability. The best screw position and number of DLCP screws were determined using a simulation-based genetic algorithm. The results showed that the DLCP with eight screws had acceptable fixation stability. The best screw position of the DLCP was four DLCP screws on either side of the bone fragment with three DLCP screws as close as practicable to the fracture site.
Super-resolution reconstruction (SRR) allows for enhancing image spatial resolution from low-resolution (LR) observations, which are assumed to have been derived from a hypothetical high-resolution image by applying a certain imaging model (IM). However, if the actual degradation is different from the assumed IM, which is often the case in real-world scenarios, then the reconstruction quality is affected. We introduce a genetic algorithm to optimize the SRR hyper-parameters and to discover the actual IM by evolving the kernels exploited in the IM. The reported experimental results indicate that our approach outperforms the state of the art for a variety of images, including difficult real-life satellite data.
Process mining aims at discovering the workflow of a process from the event logs that provide insights into organizational processes for improving these processes and their support systems. Ideally a process mining algorithm should produce a model that is simple, precise, general and fits the available logs. A conventional process mining algorithm typically generates a single process model that may not describe the recorded behavior effectively. Recently, Pareto multi-objective evolutionary algorithms have been used to generate several competing process models from the event logs. Subsequently, a user can choose a model based on his/her preference. In this paper, we have used three second-generation MOEA techniques, namely, PAES, SPEA-II, and NSGA-II, for generating a set of non-dominated process models. Using the BPI datasets, we demonstrate the efficacy of NSGA-II with respect to solution quality over its competitor algorithms.
Optimizing traffic lights in road intersections is a mandatory step to achieve sustainable mobility and efficient public transportation in modern cities. Several mono or multi-objective optimization methods exist to find the best traffic signals settings, such as evolutionary algorithms, fuzzy logic algorithms, or even particle swarm optimizations. However, they are generally dedicated to very specific traffic configurations. In this paper, we introduce the SIALAC benchmark bringing together about 24 real-world based study cases, and investigate fitness landscapes structure of these problem instances.
In most of applications of Wireless Sensor Networks(WSNs), it is expected that a solution finding a number of non-disjoint cover sets will save more energy. Base on sleep scheduling method, this paper proposed a modified genetic algorithm to maximize the lifetime of networks and schedule the sensors in the sets successively. Results show that under the same conditions, the proposed algorithm can always find the sets with maximum lifetime and consume less computation time while comparing with the recently published algorithms.
Optimal control of greenhouse environments can be improved by using a combined microclimate-crop-yield model to allow selection of greenhouse designs and control algorithms to maximize the profit margin. However, classical methods for optimal greenhouse control are not adequate to establish the tradeoffs between multiple objectives. We use NSGA-II to evolve the setpoints for microclimate control in a greenhouse simulation and define two objectives: minimizing variable costs and maximizing the value of the tomato crop yield. Results show that the evolved setpoints can provide the grower a variety of better solutions, resulting in greater profitability compared to prior simulated results. The Pareto front also provides additional information to the grower, showing the economic tradeoffs between variable costs and tomato crop yield, which can aid in decision making.
As a promising approach to the design of energy efficient circuits, approximate circuits and approximate circuit design methodologies have attracted a significant attention of researchers as well as industry. Compared to the traditional design methods, it has been demonstrated that evolutionary approaches are able to discover approximate circuits exhibiting a good trade-off between the energy consumption and circuit quality. In this work, evolutionary design of large approximate adders is addressed. In order to improve scalability, the quality of the candidate solutions is analyzed using a formal approach based on Binary Decision Diagrams. Compared to the common approach based on a parallel circuit simulator, the proposed method is able to evaluate 2-3 orders of magnitude more generations.
For air-conditioning systems in office buildings, it is crucial to reduce the power consumption while maintaining office workers' thermal comfort. To generate practically feasible temperature setting schedules of air-conditioning systems, we propose an evolutionary multi-objective air-conditioning schedule optimization system for office buildings. In the proposed system, the target building is modeled and simulated by EnergyPlus building simulator which used in the building construction field, and the OMOPSO optimizer is employed to optimize temperature setting schedules. Experimental results show that the proposed system can obtain temperature schedules showing an optimal trade-off between the thermal comfort and the power consumption.
Multiobjective evolutionary algorithms (MOEAs) try to produce enough and sufficiently diverse Pareto-optimal tradeoff solutions to cover the entire Pareto surface. However, in practical scenarios, presenting numerous solutions to stakeholders may result in confusion and indecision. This paper proposes a method for generating a small (user-specified) number of well-distributed Pareto-optimal feasible solutions for multiobjective problems. The proposed method can be applied to a set of aggregate solutions produced by (1) one MOEA over multiple runs, (2) several different MOEAs, or (3) a universal set of feasible solutions produced by one or more constraint solvers.
Using coevolutionary algorithms to find solutions to problems is a powerful technique but once solutions are identified it can be difficult for a decision maker to select a solution to deploy. ESTABLO runs competitive coevolutionary algorithm variants independently, in parallel, and then combines their test and solution results at the final generation into a compendium. From there, it re-evaluates each solution, according to three different measurements, on every test as well as on a set of unseen tests. For a decision maker, it finally identifies top solutions using various metrics and visualizes them in the context of other solutions. We demonstrate ESTABLO on a cyber security related resource allocation problem.
Multifactorial disorders are diseases whose underlying causes may be due to a combination of factors, including genetics, environmental influences, and lifestyle. Deconvoluting the factors responsible for such issues can be tremendously challenging. However, evolutionary algorithms (EAs) are particularly well suited to address this class of problem. EAs may be used to generate populations of solutions to carry out ensemble-based analyses of mathematical models that can determine which factors may have the largest impact on a particular disease state. In this work, a commonly utilized mathematical model for bone physiology was used to explore the underlying mechanism responsible for secondary hyperparathyroidism due to renal failure. Using a genetic algorithm (GA), a population of parameter sets for the bone model were generated based on a clinical data set. The average result of the best five GA-based models was compared to the standard bone model prediction as reported in the literature. The GA-based models manipulated several parameters simultaneously while the standard literature model manipulated only the glomerular filtration rate (GFR) parameter. The GA model resulted in a superior fit of the clinical data. It further indicated that six of the 108 parameters were significantly changed from what would be expected of a healthy individual. The GFR parameter was among the six significantly changed parameters. The remaining significantly changed parameters involved phosphate imbalances. Interestingly, hyperphosphatemia has been recognized as one of the primary causes of secondary hyperparathyroidism. These results would appear to corroborate the effectiveness of the GA in better understanding multifactorial disorders.
This paper proposes a total optimization method of a smart city (SC) by Global-best brain storm optimization (GBSO). The SC model includes natural gas utilities, electric power utilities, drinking and waste water treatment plants, industries, buildings, residences, and railroads. The proposed method minimizes energy cost, shifts actual electric power loads, and minimizes C02 emission using the model. Particle Swarm Optimization (PSO), Differential Evolution (DE), and Differential evolutionary particle swarm optimization (DEEPSO) have been applied to the optimization problem. However, there is room for improving solution quality. The proposed GBSO based method is applied to a model which considers a moderately-sized city in Japan, such as Toyama city. The proposed method is compared with the conventional DEEPSO and BSO based methods with promising results.
This contribution presents numerical results for optimizing a many-objective space mission trajectory benchmark under consideration of massively parallelized co-evaluation of solution candidates. The considered benchmark is the well-known Cassini1 instance published by the European Space Agency (ESA) extended to four objectives. The MIDACO optimization software represents an evolutionary algorithm based on Ant Colony Optimization (ACO) and is applied to solve this benchmark with a varying fine-grained parallelization factor (P) ranging from one to 1024. It can be shown that the required number of sequential steps to solve this benchmark can be significantly reduced by applying massive parallelization, while still maintaining a sufficient high number of well distributed non-dominated solutions in the objective space.
Nowadays, city streets are populated not only by private vehicles but also by public transport, distribution of goods, and deliveries. Since each vehicle class has a maximum cargo capacity, we study in this article how authorities could improve the road traffic by changing the different vehicle proportions: sedans, minivans, full-size vans, trucks, and motorbikes, without losing the ability of moving cargo throughout the city. We have performed our study in a realistic scenario and defined a multi-objective optimization problem to be solved, so as to minimize these city metrics. Our results provide a scientific evidence that we can improve the delivery of goods in the city by reducing the number of heavy duty vehicles and fostering the use of full-size vans instead.
Dynamical models are a mathematical framework for understanding the spread of a disease using various epidemiological parameters. However, in data-scarce regions like the Philippines, local estimates of epidemiological parameters are difficult to obtain because methods to obtain these values are costly or inaccessible. In this paper, we employ genetic algorithms trained with novel fitness functions as a low-cost, data-driven method to estimate parameters for dengue incidence in the Western Visayas Region of the Philippines (2011-2016). Initial results show good ht between monthly historical values and model outputs using parameter estimates, with a best Pearson correlation of 0.86 and normalized error of 0.65 over the selected 72-month period. Furthermore, we demonstrate a quality assessment procedure for selecting biologically feasible and numerically stable parameter estimates. Implications of our findings are discussed in both epidemiological and computational contexts, highlighting their application in FASSSTER, an integrated syndromic surveillance system for infectious diseases in the Philippines.
Most existing algorithms for optimizing the lifetime of wireless sensor networks (WSNs) are developed assuming that the sensing ranges of sensors are fixed. This paper1 focuses on adjustable WSNs and proposes a lifetime maximization approach, in which the active periods and sensing ranges of sensors are scheduled simultaneously subject to the constraints of target coverage and power limit. First, the lifetime maximization problem is converted to a problem of finding a set of coverage patterns that can lead to the best schedule when fed into a linear programming model. A genetic algorithm is then developed for coverage pattern finding. With each individual representing a coverage pattern, evolutionary operators and repair strategy are tailored to evolve the pattern set efficiently. Experimental results in a variety conditions show that the proposed approach is advantageous in both terms of computational time and solution quality.
We present a novel approach for discovering and suggesting classes/objects in legacy/procedural code, based on a genetic algorithm. Initially, a (procedures-accessing-variables) matrix is extracted from the code and converted into a square matrix. This matrix highlights the variable-relationships between procedures and is used as input to a genetic algorithm. The output of the genetic algorithm is then visually encoded using a heat-map. The developers can then (1) either manually identify objects in the presented heat-map or (2) use an automated detection algorithm that suggests objects. We compare our results with previous work.
Performance bugs are common and can cause a significant deterioration in the behaviour of a program, leading to costly issues. To detect them and reduce their impact, performance tests are typically applied. However, there is a lack of mechanisms to evaluate the quality of performance tests, causing many of these bugs remain unrevealed. Mutation testing, a fault-based technique to assess and improve test suites, has been successfully studied with functional tests. In this paper, we propose the use of mutation testing together with a search-based strategy (evolutionary algorithm) to find mutants that simulate performance issues. This novel approach contributes to enhance the confidence on performance tests while reducing the cost of mutation testing.
For a typical crowdsourcing process, a task publisher first publishes a task with an acceptable budget. Then hundreds of crowdsourced workers apply for the task with their desired bids. To recruit an adequate Crowdsourced Virtual Team (CVT) while balancing the profits of the task publisher and crowdsourced workers, previous studies proposed various algorithms, including Genetic Algorithm (GA), Alternating Variable Method (AVM), etc. However, the performance is still limited. In this study, we propose a novel hybrid metaheuristic algorithm CVTMaker to help publishers identify ideal CVTs. CVTMaker is effective which combines (1+1) Evolutionary Strategy ((1+1)-ES) and AVM to search solutions. Experimental results show that CVTMaker significantly outperforms GA and AVM over 3,117 and 5,642 of the 6,000 instances respectively.
Search Based Software Testing (SBST) formulates testing as an optimization problem, hence some search algorithms can be used to tackle it. The goal of SBST is to improve various test adequacy criteria. There are different types of coverage criteria, and in this paper, we deal with branch coverage, as it is the mostly used criterion. However, the state of the art fitness function definitions used for branch coverage testing have changed little. To fill this gap, this paper proposes a novel fitness function for branch coverage. Concretely, we first use a negative exponential model to evaluate the hardness of covering essential branches of the program, based on which we approximately evaluate the distance of a test candidate to the target branch. Finally, the experiment reveals the promising results of our proposal.
In their GECCO'12 paper, Doerr and Doerr proved that the k-ary unbiased black-box complexity of O
For each block of size 2k-1 - 1 we set up, in O(k) queries, a virtual coordinate system, which enables us to use an arbitrary unrestricted algorithm to optimize this block. This is possible because this coordinate system introduces a bijection between unrestricted queries and a subset of k-ary unbiased operators. We note that this technique does not depend on O
This together constitutes an algorithm which is conceptually simpler than the one by Doerr and Doerr, and in the same time achieves better constant multiples in the asymptotic notation. Our algorithm works in (2 + o(1)) · n/(k - 1), where o(1) relates to k. Our experimental evaluation of this algorithm shows its efficiency already for 3 ≤ k ≤ 6.
The statistical assessment of the empirical comparison of algorithms is an essential step in heuristic optimization. Classically, researchers have relied on the use of statistical tests. However, recently, concerns about their use have arisen and, in many fields, other (Bayesian) alternatives are being considered. For a proper analysis, different aspects should be considered. In this work we focus on the question: what is the probability of a given algorithm being the best? To tackle this question, we propose a Bayesian analysis based on the Plackett-Luce model over rankings that allows several algorithms to be considered at the same time.
In the last few years, parameterized complexity has emerged as a new tool to analyze the running time of randomized local search algorithm. However, such analysis are few and far between. In this paper, we do a parameterized running time analysis of a randomized local search algorithm and a (1 + 1) EA for a classical graph partitioning problem, namely, M