We propose a theory and its first experimental tests, relating difficulty of learning in deep architectures to culture and language. The theory is articulated around the following hypotheses: learning in an individual human brain is hampered by the presence of effective local minima, particularly when it comes to learning higher-level abstractions, which are represented by the composition of many levels of representation, i.e., by deep architectures; a human brain can learn such high-level abstractions if guided by the signals produced by other humans, which act as hints for intermediate and higher-level abstractions; language and the recombination and optimization of mental concepts provide an efficient evolutionary recombination operator for this purpose. The theory is grounded in experimental observations of the difficulties of training deep artificial neural networks and an empirical test of the hypothesis regarding the need for guidance of intermediate concepts is demonstrated. This is done through a learning task on which all the tested machine learning algorithms failed, unless provided with hints about intermediate-level abstractions.
In this talk I will show how artificial evolution can be used to address biological questions and explain phenomena for which there is no fossil record or no experimental evidence, such evolution of behavior, altruism, and communication. I will give examples related to insects and plants. Central to this endeavor is how selection mechanisms are applied and interpreted. I will also show how selection pressure can be lifted in artificial evolution and lead to open-ended evolution in dynamic and changing environments.
Computing devices have become widely available to billions of end users, yet a handful of experts have the needed expertise to program these devices. Automated program synthesis has the potential to revolutionize this landscape, when targeted for the right set of problems and when allowing the right interaction model. The first part of this talk discusses techniques for programming using examples and natural language. These techniques have been applied to various end-user programming domains including data manipulation and smartphone scripting. The second part of this talk presents surprising applications of program synthesis technology to automating various repetitive tasks in Education including problem, solution, and feedback generation for various subject domains such as math and programming. These results advance the state-of-the-art in intelligent tutoring, and can play a significant role in enabling personalized and interactive education in both standard classrooms and MOOCs.
Search-based software project management is a hot research point in software engineering. Based on the event-based scheduler (EBS) we have proposed in previous work , this paper intends to further propose a two-phase particle swarm optimization approach which uses a set-based representation for task scheduling and an integer representation for workload assignment scheduling to improve planning performance. Experimental results on 83 instances demonstrate the effectiveness of the proposed approach.
This paper presents Swarm-Assisted Behavior Graph Evolution (SABRE), a genetic algorithm which combines elements from genetic programming and neuroevolution to develop Behavior Graphs (BGs). SABRE evolves graph structure and parameters in parallel, with particle swarm optimization (PSO) being used for the latter. The algorithm's performance was evaluated on a set of black-box function approximation problems, one of which represents part of a robot controller. We found that SABRE performed significantly better in approximating the mathematically complex test functions than the reference algorithms genetic programming (GG) and NEAT.
Particle Swarm Optimization(PSO) has shown its advantages not only in dealing with continous optimization problems, but also in dealing with discrete optimization problems. Binary Particle Swarm Optimization(BPSO), the discrete version of PSO, has been widely applied to many areas. Although there are some variations aiming to improve BPSO's performance, none of them has been proven to be a promissing alternative. In this paper, we propose a novel binary particle swarm optimization called Fitness Proportionate Selection Based Binary Particle Swarm Optimization(FPSBPSO). We test FPSBPSO's performance in function optimization problems and multidimension knapsack problems. Experimental results show that FPSBPSO can find better optima than BPSO and a variation of BPSO.
Particle Swarm Optimization is fundamentally a stochastic algorithm, where each particle takes into account noisy information from its own history as well as that of its neighborhood. Though basic information-theoretic principles would suggest that less noise indicates greater certainty, the momentum term is simultaneously the least directly-informed and the most deterministically applied. This dichotomy suggests that the typically confident treatment of momentum is misplaced, and that swarm performance can benefit from better-motivated processes that obviate momentum entirely.
Inspired by the division of labor and migration behavior in nature, this paper proposes a novel particle swarm optimization algorithm with multiple learning strategies (PSO-MLS). In the algorithm, particles are divided into three sub-swarms randomly while three learning strategies with different motivations are applied to each sub-swarm respectively. The Traditional Learning Strategy (TLS) inherits the basic operations of PSO to guarantee the stability. Then a Periodically Stochastic Learning Strategy (PSLS) employs a random learning vector to increase the diversity so as to enhance the global search ability. A Random Mutation Learning Strategy (RMLS) adopts mutation to enable particles to jump out of local optima when trapped. Besides, information migration is applied within the intercommunication of sub-swarms. After a certain number of generations, sub-swarms would aggregate to continue search, aiming at global convergence. Through these learning strategies and swarm aggregation, PSO-MLS possesses both good exploration and exploitation abilities. PSO-MLS was tested on a set of benchmarks and the result shows its superiority to gain higher accuracy for unimodal functions and better solution quality for multimodal functions when compared to some PSO variants.
In this paper, we propose an ant colony optimization (ACO) to solve a realistic variant of flowshop problem. The considered scheduling problem is a hybrid flexible flowshop problem with sequence-dependent setup times under the objective of minimizing the makespan. The proposed approach uses concept from multi-objective evolutionary algorithms and look-ahead information to enhance solutions quality. We also introduce new constructive heuristic used in the ACO local improvement. Numerical experiments were performed to compare the performance of the ACO on different benchmarks from the literature. The results indicate that the ACO is very competitive and enhances solutions of the known reference sets.
Artificial Bee Colony (ABC) algorithm, which was initially proposed for numerical function optimization, has been increasingly used for clustering. However, when it is directly applied to clustering, the performance of ABC is lower than expected. This paper proposes an improved ABC algorithm for clustering, denoted as EABC. EABC uses a key initialization method to accommodate the special solution space of clustering. Experimental results show that the evaluation of clustering is significantly improved and the latency of clustering is sharply reduced. Furthermore, EABC outperforms two ABC variants in clustering benchmark data sets.
We describe a design paradigm for developing autonomic computing systems based on an analogy with the natural immune system, and show how current approaches to designing autonomic systems could be enriched by considering alternative design processes based on cognitive immune networks.
Real world machine learning, where data is sampled continuously, may in theory be classifiable into distinct and unchanging categories but in practice the classification becomes non-trivial because the nature of the background noise continuously changes. Applying distinct and unchanging categories for data ignores the fact that for some applications where the categories of data may remain constant, the background noise constantly changes, and thus the ability for a supervised learning method to work is limited. In this work, we propose a novel method based on an Artificial Immune System (AIS) and implemented on a systemic computer, which is designed to adapt itself over continuous arrival of data to cope with changing patterns of noise without requirement for feedback, as a result of its own experience.
We explore the evolution of programs for control tasks using the recently introduced Hierarchical Evolutionary Re-Combination Language (HERCL) which has been designed as an austere and general-purpose language, with a view toward modular evolutionary computation, combining elements from Linear GP with stack-based operations from FORTH. We show that HERCL programs can be evolved to robustly perform a benchmark double pole balancing task from a specified range of initial conditions, with the poles remaining balanced for up to an hour of simulated time.
We propose a new collaborative guidance platform for a team of robots that should protect a fixed ground target from one or several threats. The team of robots performs high-level behaviors. These are hand-coded since they consist in driving the robots to some given position. However, deciding when and how to use these behaviors is much more challenging. Scripting high-level interception strategies is a complex problem and applicable to few specific application contexts. We propose to use a gene regulatory network to regulate high-level behaviors and to enable the emergence of efficient and robust interception strategies.
In this report we describe our research involving the construction of quantum-based robotic controllers. By careful use of quantum interference as a computational resource and by utilizing only a linear number of elementary unitary transformations, we are able to construct systems which seem to provide a computational advantage even when simulated on a classical computer.
Different species of animals have vast differences in how general their learning abilities and behaviors are. This paper analyzes the effect of network connection density and prolonged evolution on general intelligence. Using the NEAT algorithm for neuroevolution, network structures with different connectivities were evaluated in recognizing digits and their mirror images. These experiments show that general intelligence, i.e. recognition of previously unseen examples, increases with increase in connectivity. General intelligence also increases with the number of generations in prolonged evolution, even when performance no longer improves in the known examples. This outcome suggests that general intelligence depends on specific anatomical and environmental factors.
The use of mass spectrometry to verify and quantify biomarkers requires the identification of the peptides that can be detectable. In this paper, we propose the use of genetic programming (GP) to measure the detection probability of the peptides. The new GP method is tested and verified on two different yeast data sets with increasing complexity and shows improved performance over other state-of-art classification and feature selection algorithms.
This work tries to cope with the standardization issue by the adoption of model exchange standards like CellML, BioBrick standard biological parts and standard signal carriers for modeling purpose. The BioBricks are easily assemblable  standard DNA sequences coding for well-defined structures and functions and represent an effort to introduce the engineering principles of abstraction and standardization in synthetic biology. Web applications as GenoCAD  are available and implements an algorithm of syntax check of the circuits designed , while some other tools for automatic design and optimization of genetic circuits have appeared  and are also specific for BioBrick systems . Our generated models are made of Standard Virtual Parts modular components. Model complexity includes more interaction dynamics than previous works. The inherent software complexity has been handled by a rational use of ontologies and rule engine. The database of parts and interactions is automatically created from publicly available whole system models. We implemented a genetic algorithm searching the space of possible genetic circuits for an optimal circuit meeting user defined input-output dynamics. The tools performing structural optimization usually use stochastic strategies, while those optimizing the parameters or matching the components for a given structure can take advantage of both stochastic and deterministic strategies. In most cases it is however necessary human intervention, for example to set the value of certain kinetic parameters. To our best knowledge no tool exists which does not show a couple of these limitations, then our tool is the only capable of using a library of parts, dynamically generated from other system models available from public databases . The tool automatically infers the chemical and genetic interactions occurring between entities of the repository models and applies them in the target model if opportune. The repository models have to be modeled by a specific CellML standard, the Standard Virtual Parts (SVP)  formalism and the components have to be annotated with OWL for unique identifiers. The output is a sequence of readily composable biological components, deposited in the registry of parts, and a complete CellML kinetic model of the system. Accordingly, a model can be generated and simulated from a sequence of BioBrick, without any human intervention. Actual tools present a moderated degree of accuracy in the prediction of the behavior, principally due to the lack of consideration of many cellular factors. Despite the advances in molecular construction, modeling and fine-tuning the behavior of synthetic circuits remains extremely challenging . We tried to cope with this issue of scalability by means of ontologies coupled with a rule engine . Model complexity includes more interaction dynamics than previous works, including gene regulation, interaction between small molecules and proteins but also protein-protein and post-transcriptional regulation. The domain was described by using Ontology Web Language (OWL) ontologies in conjunction with CellML , while complex logic was added by Jess rules . The system has been successfully tested on a single test case and looks towards the creation of a web platform .
Designing genetic regulatory networks (GRNs) to achieve a desired cellular function is one of the main goals of synthetic biology. However, determining minimal GRNs that produce desired time-series behaviors is non-trivial. In this paper, we propose a 'top-down' approach, wherein we start with relatively dense GRNs and then use differential evolution (DE) to evolve interaction coefficients. When the target dynamical behavior is found embedded in a dense GRN, we narrow the focus of the search and begin aggressively pruning out excess interactions at the end of each generation. We first show that the method can quickly rediscover known small GRNs for a toggle switch and an oscillatory circuit. Next we include these GRNs as non-evolvable subnetworks in the subsequent evolution of more complex, modular GRNs. By incorporating aggressive pruning and a penalty term, the DE was able to find minimal or nearly minimal GRNs in all test problems.
We present iSyn, an evolutionary algorithm that automatically designs de novo ligands with high predicted binding affinity and drug-like properties. It attempts to optimize candidate ligands in accordance with click chemistry and thus ensures chemical synthesizability. In addition to the existing genetic operators of mutation and crossover inherited from AutoGrow 3.0, our iSyn introduces four novel genetic operators to "cut" ligands in order to prevent them from becoming too large in molecular size, hence preserving drug-like properties. Moreover, iSyn interfaces with our fast docking engine idock, greatly reducing the execution time. We hope iSyn can supplement medicinal chemists' efforts.
iSyn was applied to optimizing candidate ligands against two important drug targets, TbREL1 and HIV-1 RT, and managed to produce chemically valid ligands with high predicted binding affinities and drug-like properties. In the example of TbREL1, the predicted free energy of the best generated ligand decreased from -9.878 kcal/mol to -13.985 kcal/mol after 3 generations. In the example of HIV-1 RT, the predicted free energy of the best generated ligand decreased from -5.427 kcal/mol to -12.488 kcal/mol after 2 generations, meanwhile the molecular mass dropped from 602.818 Da to 461.736 Da, so that the compound could be properly absorbed by human body.
iSyn is written in C++ and Python, and is free and open source, available at http://istar.cse.cuhk.edu.hk/iSyn.tgz. It has been tested successfully on Linux and Windows. In the near future we plan to implement a web-based user interface to facilitate its usage and to promote large-scale de novo drug design.
This paper presents a multi-population genetic algorithm for procedural generation of levels for platform games such as Super Mario Bros (SMB). The algorithm evolves four aspects of the game during its generations: terrain, enemies, coins and blocks. Each aspect has its own codification, population and fitness function. At the end of the evolution, the best four aspects are combined to construct the level. The method has as input a vector of parameters to configure the characteristics of each aspect. Experiments were made to evaluate the capability of the method in generating interesting levels. Results showed the method can be controlled to generate different types of levels.
This paper evaluates three different Evolutionary Algorithms (EAs) for generating non-player characters (NPCs) via Artificial Intelligence scripts for a Real Time Strategy (RTS) game. The first approach executes only a Genetic Algorithm (GA), while the second and third ones combine GA with a Dynamic Scripting approach. The Bos Wars game is used for testing these EAs, which are able to create and to evolve strategies of this RTS game coded as scripts in LUA language. In order to do this, the EA communicates with Bos Wars' engine by sending scripts, playing matches and capturing statistical data to evaluate its individuals.
The creation of fictional stories is a very complex task that usually implies a creative process where the author has to combine characters, conflicts and backstories to create an engaging narrative. This work presents a general methodology that uses individual based models to generate cohesive and coherent backstories where desired archetypes (universally accepted literary symbols) emerge and their life stories are a by-product of the simulation. This methodology includes the modeling and parameterization of the agents, the environment where they will live and the desired literary setting. The use of a genetic algorithm (GA) is proposed to establish the parameter configuration that will lead to backstories that best fit the setting. Information extracted from a simulation can then be used to create the backstories. To demonstrate the adequacy of the methodology, we perform an implementation using a specific multi-agent system and evaluate the results.
In this paper, we apply the Monte Carlo Tree Search (MCTS) method for controlling at once several virtual characters in a 3D multi-player learning game. The MCTS is used as a search algorithm to explore a search space where every potential solution reflects a specific state of the game environment. Functions representing the interaction abilities of each character are provided to the algorithm to leap from one state to another. We show that the MCTS algorithm successfully manages to plan the actions for several virtual characters in a synchronized fashion, from the initial state to one or more desirable end states. Besides, we demonstrate the ability of this algorithm to fulfill two specific requirements of a learning game AI : guiding the non player characters to follow a predefined plan while coping with the unpredictability of the human players actions.
This paper presents our work on Estimation of Distribution Algorithms (EDAs) that address sequencing problems, i.e., the task of finding the best ordering of a set of items or an optimal schedule to perform a given set of operations. Specifically, we focus on using probabilistic models based on $n$-gram statistics. These models have been used extensively in modeling the statistical properties of sequences. We start with an EDA that uses a bigram model, then extend this scheme to higher-order models. However, directly replacing the bigram model with a higher-order model results in premature convergence. We give an explanation on this situation, along with some empirical support. We then introduce a technique for combining multiple models of different orders, which allows for smooth transition from lower-order models to higher-order ones. Furthermore, this technique can also be used to incorporate other heuristics as well as prior knowledge about the problem into the search process. Promising preliminary results on solving Traveling Salesman Problems (TSPs) are presented.
Many of the real-world problems can be decomposed into a number of sub-problems for which the solutions can be found easier. However, proper decomposition of large problems remains a challenging issue, especially in optimization, where we need to find the optimal solutions more efficiently. Estimation of distribution algorithms (EDAs) are a class of evolutionary optimization algorithms that try to capture the interactions between problem variables when learning a probabilistic model from the population of candidate solutions. In this paper, we propose a type of synthesized problems, specially designed to challenge this specific ability of EDAs. They are based on the principal idea that each candidate solution to a problem may be simultaneously interpreted by two or more different structures where only one is true, resulting in the best solution to that problem. Of course, some of these structures may be more likely according to the statistics collected from the population of candidate solutions, but may not necessarily lead to the best solution. The experimental results show that the proposed benchmarks are indeed difficult for EDAs even when they use expressive models such as Bayesian networks to capture the interactions in the problem.
Estimation of distribution algorithms (EDAs) are stochastic optimization methods that guide the search by building and sampling probabilistic models. Inspired by Bayesian inference, we proposed a two-level hierarchical model based on beta distribution. Beta distribution is the conjugate priori for binomial distribution. Besides, we introduced a learning rate function into the framework to control the model update. To demonstrate the effectiveness and applicability of our proposed algorithm, experiments are carried out on the 01-knapsack problems. Experimental results show that the proposed algorithm outperforms cGA, PBIL and QEA.
We design and analyze a real-coded genetic algorithm for the use in evolving collections of quantum unitary operators (not circuits) which act on pure or mixed states over arbitrary quantum systems while interacting with fixed, problem specific operators (e.g., oracle calls) and intermediate partial measurements. Our algorithm is general enough so as to allow its application to multiple, very different, areas of quantum computation research.
This paper introduces the Spherical Evolutionary Algorithm (SEA) for global continuous optimization. Two new geometric search operators are included in the design of the SEA. The operators are named: Inversion Search Operator (ISO) and Reflection Search Operator (RSO). This paper describes the general implementation of SEA and its performance is analyzed through a benchmark of 10 functions.
When data is released or shared among different organizations, some sensitive or confidential information may be subject to be exposed by using data mining tools. Thus, a question arises: how can we protect sensitive knowledge while allowing other parties to extract the knowledge behind the shared data. In this paper, we address the problem of privacy preserving in association rule mining from the perspective of multi-objective optimization. A sensitive rule can be hidden by adding items into the dataset to make the support of the antecedent part of the sensitive rule increase and accordingly the confidence of the sensitive rule decrease. The evolutionary multi-objective optimization (EMO) algorithm is utilized to find suitable transactions (or tuples) to be modified so as the side effects to be minimized. Experiments on real datasets demonstrated the effectiveness of the proposed method.
In this paper we address the problem of constructing correct-by-design programs with the use of the automata-based programming paradigm. A recent algorithm for learning finite-state machines (FSMs) MuACOsm is applied to the problem of inferring extended finite-state machine (EFSM) models from behavior examples (test scenarios) and temporal properties, and is shown to outperform the genetic algorithm (GA) used earlier.
This work presents a differential evolution algorithm for combinatorial optimization, in which a set-based representation and operators define subproblems that are used to explore the search space. The proposed method is tested on the capacitated centered clustering problem.
A common problem when applying heuristics is that they often perform well on some problem instances, but poorly on others. We develop a hyper-heuristic approach, using Grammatical Evolution (GE), to generate heuristics for the Vehicle Routing Problem (VRP). Through a series of experiments we develop an approach that leads to solutions of acceptable quality to Vehicle Routing Problem instances with only limited prior knowledge of the problem to be solved.
In the Multidimensional Knapsack Problem (MKP) there are items easily identifiable as highly (lowly) profitable and likely to be chosen (not chosen) to compose high-quality solutions. For all the other items, the Knapsack Core~(KC), the decision is harder. By focusing the search on the KC effective algorithms have been developed. However, the true KC is not available and most algorithms can only rely on items' efficiencies. Chu & Beasley Genetic Algorithm (CBGA), for example, uses efficiencies in a repair-operator which bias the search towards the KC. This paper shows that, as the search progresses, efficiencies lose their descriptive power and, consequently, CBGA's effectiveness decreases. As a result, CBGA rapidly finds its best solutions and stagnates. In order to circumvent this stagnation, extra information about the KC should be used to implement specific operators. Since there is a correlation between marginal probabilities in a population and efficiencies, we show that KCs can be estimated from the population during the search. By solving the estimated KCs with CPLEX, improvements were possible in many instances, evidencing CBGA's weakness to solve KCs and indicating a promising way to improve GAs for the MKP through the use of KC estimates.
A framework for community discovery in multidimensional networks based on an evolutionary approach is proposed. Each network is clustered by running a multiobjective genetic algorithm that tries to maximize the modularity function of the current network and, at the same time, to minimize the difference between the current community structure and that obtained on the already considered dimensions. Experiments on synthetic datasets show the capability of the approach in discovering latent shared group organization of individuals.
Dimensionality reduction is an important problem class in machine learning and data mining, as the dimensionality of data sets is steadily increasing. This work is a contribution in the line of research on iterative unsupervised kernel regression (UKR), a class of methods for dimensionality reduction that employ regression methods to find low-dimensional representations of high-dimensional patterns. We introduce a hybrid optimization approach of iteratively constructing a solution and performing gradient descent in the data space reconstruction error (DSRE). Further, we introduce a variable kernel function that increases the flexibility of UKR learning. The variable kernel function increases the model capacity, but introduces new parameters that have to be tuned.
In nonlinear and chaotic time series prediction, constructing the mathematical model of the system dynamics is not an easy task. Partially connected Artificial Neural Network with Evolvable Topology (PANNET) is a new paradigm for prediction of chaotic time series without access to the dynamics and essential memory depth of the system. Evolvable topology of the PANNET provides flexibility in recognition of systems in contrast to fixed layered topology of the traditional ANNs. This evolvable topology guides the relationship between observation nodes and hidden nodes, where hidden nodes are extra nodes that play the role of memory or internal states of the system. In the proposed variable-length Genetic Algorithm (GA), internal neurons can be connected arbitrarily to any type of nodes. Besides, number of neurons, inputs and outputs for each neuron, origin and weight of each connection evolve in order to find the best configuration of the network.
It is widely known that reinforcement learning is a more general problem than supervised learning. In fact, supervised learning can be seen as a class of reinforcement learning problems. However, only a couple of papers tested reinforcement learning algorithms in supervised learning problems. Here we propose a new and simpler way to abstract supervised learning for any reinforcement learning algorithm. Moreover, a new algorithm called Novelty-Organizing Classifiers is developed based on a Novelty Map population that focuses more on the novelty of the inputs than their frequency. A comparison of the proposed method with Self-Organizing Classifiers and BioHel on some datasets is presented. Even though BioHel is specialized in solving supervised learning problems, the results showed only a trade-off between the algorithms. Lastly, results on a maze problem validate the flexibility of the proposed algorithm beyond supervised learning problems. Thus, Novelty-Organizing Classifiers is capable of solving many supervised learning problems as well as a maze problem without changing any parameter at all. Considering the fact that no adaptation of parameters was executed, the proposed algorithm's basis seems interestingly flexible.
Feature selection has two main conflicting objectives, which are to minimise the number of features and maximise the classification accuracy. Evolutionary computation techniques are particularly suitable for solving mult-objective tasks. Based on differential evolution (DE), this paper develops a multi-objective feature selection algorithm (DEMOFS). DEMOFS is examined and compared with two traditional feature selection algorithms and a DE based single objective feature selection algorithm. DEFS aims to minimise the classification error rate of the selected features. Experiments on nine benchmark datasets show that DEMOFS can successfully obtain a set of non-dominated feature subsets, which include a smaller number of features and maintain or improve the classification performance over using all features. In almost all cases, DEMOFS outperforms DEFS and the two traditional feature selection methods in terms of both the number of features and the classification performance.
In this paper, we propose an Indicator-based Chemical Reaction Optimization (ICRO) algorithm for multiobjective optimization. There are two main motivations behind this work. On the one hand, CRO is a new recently proposed metaheuristic which demonstrated very good performance in solving several mono-objective problems. On the other hand, the idea of performing selection in Multi-Objective Evolutionary Algorithms (MOEAs) based on the optimization of a quality metric has shown a big promise in tackling Multi-Objective Problems (MOPs). The statistical analysis of the obtained results shows that ICRO provides competitive and better results than several other MOEAs.
A non-dominated sorting differential evolution algorithm with improved directional convergence and spread (NSDE-IDCS) is developed. Taking advantage of differential evolution, searching direction for a dominated solution is determined by its nearest non-dominated neighbor, while searching direction for a non-dominated solution is determined by other two non-dominated solutions. A simplex local search operator with an adaptive search probability is embedded to further exploit the neighborhood of non-dominated solutions.
Hypervolume has been frequently used as an indicator to evaluate a solution set in indicator-based evolutionary algorithms (IBEAs). One important issue in such an IBEA is the choice of a reference point. A different solution set is often obtained from a different reference point since the hypervolume calculation depends on the location of the reference point. In this paper, we propose an idea of utilizing this dependency to formulate a meta-level multi-objective set optimization problem. Hypervolume maximization for a different reference point is used as a different objective.
This paper proposes to represent the preference of a decision maker by Gaussian functions on a hyperplane. The preference is used to evaluate non-dominated solutions as a second criterion instead of the crowding distance in NSGA-II. High performance of our proposal is demonstrated for many-objective DTLZ problems.
MOEA/D decomposes a multi-objective optimization problem (MOP) into a set of scalar sub-problems with evenly spread weight vectors. Recent studies have shown that the fixed weight vectors used in MOEA/D might not be able to cover the whole Pareto front (PF) very well. Due to this, we developed an adaptive weight adjustment method in our previous work by removing subproblems from the crowded parts of the PF and adding new ones into the sparse parts. Although it performs well, we found that the sparse measurement of a subproblem which is determined by the m-nearest (m is the dimensional of the object space) neighbors of its solution can be more appropriately defined. In this work, the neighborhood relationship between subproblems is defined by using Delaunay triangulation (DT) of the points in the population.
Optimizing several objectives that are often at odds with each other provides difficult challenges that are not encountered if having only one goal at hand. One intuitive way to solve a multi-objective problem is to aggregate the objectives and reformulate it as an optimization problem having just a single goal. This goal can be a designer specific aggregation of the objectives or a characterization of knees, trade-offs, utilities, stronger optimality concepts or preferences.
This paper examines the theoretical relationships between two knee concepts and aggregate objective functions methods. The changes in the fitness landscape by utilizing different aggregations is also discussed.
There exit high variations among nano-devices in nano-electronic systems, owing to the extremely small size and the bottom-up self-assembly nanofabrication process. Therefore, it is important to develop logical function mapping techniques with the consideration of variation tolerance. In this paper, the variation tolerant logical mapping (VTLM) problem is treated as a multi-objective optimization problem (MOP), a hybridization of Non-dominated Sorting Genetic Algorithm II (NSGA-II) with a problem-specific local search is presented to solve the problem. The experiment results show that with the assistance of the problem-specific local search, the presented algorithm is effective, and can find better solutions than that without the local search.
We present a novel 2D cellular automaton with rules that are a non-uniform generalization of a Moore-neighbourhood, outer-totalistic, two-state ("life-like") cellular automaton. The system is purely deterministic and exhibits interesting multi-scale emergent behaviour, including the spontaneous formation of mobile particles and other self-organizing structures. In particular, smaller-scale structures can be shown to combine with other structures to form inhomogeneous higher-order constructions, and to do so at multiple orders of magnitude. The system has features in common with reaction-diffusion models. We propose that this system has properties that make it useful as a model of an artificial chemistry with the potential for supporting open-ended evolutionary growth. We call it Nu-life.
This paper presents a new model for the development of artificial creatures from a single cell. The model aims at providing a more biologically plausible abstraction of the morphogenesis and the specialization process, which the organogenesis follows. It is built upon three main elements: a cellular physics simulation, a simplified cell cycle using an evolved artificial gene regulatory network and a cell specialization mechanism quantifying the ability to perform different functions. As a proof-of-concept, we present a first experiment where the morphology of a multicellular organism is guided by cell weaknesses and efficiency at performing different functions under environmental stress.
Deep learning through supervised and unsupervised learning has demonstrated human competitive performance on some visual tasks; however, evolution played an important role in the development of biological visual systems. Thus evolutionary approaches, specifically the Hypercube-based NeuroEvolution of Augmenting Topologies, are applied to deep learning tasks in this paper. Results indicate HyperNEAT alone struggles in image classification, but trains effective feature extractors for other machine learning approaches.
Traffic assignment is a complex optimization problem. In case the road network has many links (thus a high number of alternative routes) and multiple origin-destination pairs, most existing solutions approximate the so-called user equilibrium (a variant of Nash equilibrium). Furthermore, the quality of these solutions (mostly, iterative algorithms) come at the expense of computational performance. In this study, we introduce a methodology to evaluate an approximation of an optimal traffic assignment from the global network's perspective based on genetic algorithms. This approach has been investigated in terms of both network performance (travel time) and convergence speed.
Introducing the machine learning technique into evolutionary computation (EC) is one of the most important issues to expand EC design. In this paper, we proposed a novel method that combines the genetic algorithm and support vector machine to achieve the imaginary evolution without real fitness evaluations.
Aphasia is the degradation of one's ability to comprehend or convey language, usually due to brain damage caused by strokes or some external force. Sufferers can regain some or all of their prior abilities, but only with significant speech and language therapy (SLT) sessions. SLT sessions are resource-intensive, as they often require skilled therapists to adapt the therapy for the individual patients.
We present Ogma, a novel approach to the automatic creation of SLT sessions. Ogma is comprised of a proprietary mobile front-end application that the patients interact with, and an offline GA that designs patient-specific sessions based on a patient's progress. Key to this is the ability to accurately capture the difficulty of the generated sessions; this paper presents the results of experiments where SLT practitioners perform beta testing on Ogma, to ascertain its ability to consistently produce useful sessions of appropriate difficulty.
Network design is a broad class of essential engineering and science problems. The target of network design is to construct a graph that satisfies some restrictions. Many network design problems (NDPs) are known as NP-hard and become more challenging as networks grow fast in size. In this paper, we propose a novel genetic algorithm based on partitioning, termed PGA, which divides large-scale NDPs into low dimensional sub-problems and achieves global optimal solution by coordination of sub-problems. Experiments with PGA applied to the degree-constrained minimum spanning tree problem have shown the effectiveness of PGA for large-scale NDPs.
We have proposed the novel evolutionary computation called ``Dictyostelium based Genetic Algorithm" (DGA), which adopts the concept of life cycle of slime molds and can take a balance between exploitation and exploration.
In this research, we propose an extension of DGA with an index evaluating population diversity. To analyze the abilities of DGAs, the computational experiments are carried out taking several combinatorial optimization problems as examples. We show that the performance of DGAs is superior to that of Simple GA in all examples.
The behaviors of populations in evolutionary algorithms can be understood in terms of the dynamics of network models whose nodes represent individuals in the population. This paper explores "ancestral networks" in which connections indicate the proximity of the nearest common ancestor of two nodes. Preliminary experimental results show that the formation of large components in such an ancestral network model can be used to identify potential convergence, and to determine when randomly reseeding part of a population can prove beneficial.
Reliability is one of the important measures of how well a system meets its design objective, and mathematically is the probability that a system will perform satisfactorily for a given period of time. When the system is described by a network of N components (nodes) and L connections (links), the reliability of the system becomes a network design problem that is an NP-hard combinatorial optimization problem. In this paper, genetic algorithm is applied to find the most reliable connected network with the same connectivity, (i.e. with given N and L). The accuracy and efficiency of genetic algorithm in the search of the most reliable network(s) of same connectivity is verified by exhaustive search. Our results not only demonstrate the efficiency of our algorithm for optimization problem for graphs, but also suggest that the most reliable network will have high symmetry.
This paper considers advances in development of dedicated Evolutionary Algorithms (EA) for efficiently solving large, non-linear, constrained optimization problems. The EA are precisely understood here as decimal-coded Genetic Algorithms consisting of three operators: selection, crossover and mutation, followed by several newly developed calculation speed-up techniques based on simple concepts. These techniques include: solution smoothing and balancing, a--posteriori solution error analysis and related techniques, non-standard use of distributed and parallel calculations, and adaptive step-by-step mesh refinement. Efficiency of the techniques proposed here has been evaluated using several benchmark problems e.g. residual stresses analysis in chosen elastic-plastic bodies under cyclic loadings. These preliminary tests indicate significant acceleration of the large optimization processes involved. The final objective of our research is development of an algorithm efficient enough for solving real, large engineering problems.
In differential evolution (DE), the optimal value of the control parameters are problem-dependent. Many improved DE algorithms have been proposed with the aim of improving the exploration ability by adaptively adjusting the values of F. In those algorithms, although the value of F is adaptive at the individual level or at the population level, the value is the same for all dimensions of each individual. Individuals are close to the global optimum at some dimensions, but they may be far away from the global optimum at other dimensions. This indicated that different values of F may be needed for different dimensions. This paper proposed an adaptive scheme for the parameter F at the dimensional level. The scheme was incorporated into the jDE algorithm and tested on a set of 25 scalable benchmark functions. The results showed that the scheme improved the performance of the jDE algorithm, particularly in comparisons with several other peer algorithms on high-dimensional functions.
Scheduling the operating mode of nodes is an effective way to maximize the lifetime of wireless sensor networks (WSN). For a WSN with randomly and densely deployed sensors, we could maximize the lifetime of WSN through finding the maximum number of disjoint complete cover sets. Most of the related work focuses on 2D ideal plane. However, deploying sensors on the 3D surface is more practical in real world scenarios. We propose a novel genetic algorithm with redundant sensor auto-adjustment, termed RSAGA. In order to adapt the original GA into this application, we employ some effective mechanisms along with the basic crossover, mutation, and selection operation. The proposed operator of redundant sensor auto-adjustment schedules the redundant sensors in complete cover sets into incomplete cover sets so as to improve the coverage of the latters. A rearrangement operation specially designed for the critical sensors is embedded in the mutation operator to fine-tune the node arrangement of critical fields. Moreover, we modify the traditional cost function by increasing the penalty of incomplete cover sets for improving the convergence rate of finding feasible solutions. Simulation has been conducted to evaluate the performance of RSAGA. The experimental results show that the proposed RSAGA possesses very promising performance in terms of solution quality and robustness.
The ability to generalize beyond the training set is important for Genetic Programming (GP). Interleaved Sampling is a recently proposed approach to improve generalization in GP. In this technique, GP alternates between using the entire data set and only a single data point. Initial results showed that the technique not only produces solutions that generalize well, but that it so happens at a reduced computational expense as half the number of generations only evaluate a single data point.
This paper further investigates the merit of interleaving the use of training set with two alternatives approaches. These are: the use of random search instead of a single data point, and simply minimising the tree size. Both of these alternatives are computationally even cheaper than the original setup as they simply do not invoke the fitness function half the time. We test the utility of these new methods on four, well cited, and high dimensional problems from the symbolic regression domain.
The results show that the new approaches continue to produce general solutions despite taking only half the fitness evaluations. Size minimisation also prevents bloat while producing competitive results on both training and test data sets. The tree sizes with size minisation are substantially smaller than the rest of the setups, which further brings down the training costs.
Due to the increased quantity of digital data, especially in the form of digital images, the need for effective image compression techniques is greater than ever. The JPEG lossless mode relies on predictive coding, in which accurate predictive models are critical. This study presents an efficient method of generating predictor models for input images via genetic programming. It is shown to always produce error images with entropy equal to or lower than those produced by the JPEG lossless mode. This method is demonstrated to have practical use as a real-time asymetric image compression algorithm due to its ability to quickly and reliably derive prediction models.
The quality of candidate solutions in evolutionary computation (EC) depend on multiple independent runs and a large number of them fail to guarantee optimal result. These runs consume more or less equal or sometimes higher amount of computational resources on par the runs that produce desirable results.
This research work addresses these two issues (run quality, execution time), Run Prediction Model (RPM), in which undesirable quality evolutionary runs are identified to discontinue from their execution. An Ant Colony Optimization (ACO) based classifier that learns to discover a prediction model from the early generations of an EC run.
We consider Grammatical Evolution (GE) as our EC technique to apply RPM that is evaluated on four symbolic regression problems. We establish that the RPM applied GE produces a significant improvement in the success rate while reducing the execution time.
The process of creating city designs is a complex, time-consuming endeavor. This paper presents CityBreeder, a system which uses Evolutionary Computation to enable the rapid, user-guided development of city designs based on the blending of multiple existing designs.
In this paper, we compare a basic linear genetic programming (LGP) algorithm against several LGP variants, proposed by us, on two sets of symbolic regression benchmarks. We evaluated the influence of methods to control bloat, investigated these techniques focused in growth of effective code, and examined an operator to consider two successful individuals as modules to be integrated into a new individual. Results suggest that methods that deal with program size, percentage of effective code, and subfunctions, can improve the quality of the final solutions.
This paper presents a genotype-level distance metric for Genetic Programming (GP) based on the symmetric difference concept: first, the information contained in individuals is expressed as a set of symbols (the content of each node, its position inside the tree, and recurring parent-child structures); then, the difference between two individuals is computed considering the number of elements belonging to one, but not both, of their symbol sets.
This paper shows how attribute grammar (AG) can be used with Grammatical Evolution (GE) to avoid invalidators in the symbolic regression solutions generated by GE. In this paper, we also show how interval arithmetic can be implemented with AG to avoid selection of certain arithmetic operators or transcendental functions, whenever necessary to avoid infinite output bounds in the solutions. Results and analysis demonstrate that with the proposed extensions, GE shows significantly less overfitting than standard GE and Koza's GP, on the tested symbolic regression problems.
This paper describes a method of solving the symbolic regression problem using developmental linear genetic programming (DLGP) with an epigenetic hill climber (EHC). We propose the EHC for optimizing the epigenetic properties of the genotype. The epigenetic characteristics are then inherited through coevolution with the population. Results reveal that the EHC improves performance through maintenance of smaller expressed program sizes. For some problems it produces more successful runs while remaining essentially cost-neutral with respect to number of fitness evaluations.
Geometric Semantic Genetic Programming (GSGP) is a recently defined form of Genetic Programming (GP) that has shown promising results on single output Boolean problems when compared with standard tree-based GP. In this paper we compare GSGP with Cartesian GP (CGP) on comprehensive set of Boolean benchmarks, consisting of both single and multiple outputs Boolean problems. The results obtained show that GSGP outperforms also CGP, confirming the efficacy of GSGP in solving Boolean problems.
Genetic programming (GP) has proven to be successful at generating programs which solve a wide variety of problems. Object-oriented GP (OOGP) extends traditional GP by allowing the simultaneous evolution of multiple program trees, and thus multiple functions. OOGP has been shown to be capable of evolving more complex structures than traditional GP. However, OOGP does not facilitate the incorporation of expert knowledge within the resulting evolved type. This paper proposes an alternative OOGP methodology which does incorporate expert knowledge by the use of a user-supplied partially-implemented type definition, i.e. an abstract class.
Genetic programming systems often produce programs that include unnecessary code. This is undesirable for several reasons, including the burdens that overly-large programs put on end-users for program interpretation and maintenance. The problem is exacerbated by recently developed techniques, such as genetic programming with geometric semantic crossover, that tend to produce enormous programs. Methods for automatically simplifying evolved programs are therefore of interest, but automatic simplification is non-trivial in the context of traditional program representations with unconstrained function sets. Here we show how evolved programs expressed in the stack-based Push programming language can be automatically and reliably simplified using a simple, stochastic hill-climber. We demonstrate and quantitatively characterize this simplification process on programs evolved to solve four non-trivial genetic programming problems with qualitatively different function sets.
This paper presents a new model for regression problems based on Multi-Gene and Quantum Inspired Linear Genetic Programming. We discuss theoretical aspects, operators, representation, and experimental results.
State-of-the-art video coding technologies such as H.265/HEVC employ in-loop denoising filters such as deblocking filter and sample adaptive offset. This paper aims to develop a new type of in-loop denoising filter using an evolutionary method. To boost the evolution, GPGPU is utilized in filtering process. Generated filter is heavily nonlinear and content-specific. Simulation results demonstrate that proposed method generates better denoising filter in 100x shorter time. The bit rate reduction of 1.492 - 2.569% was obtained against HM7.2 anchor, the reference software of H.265/HEVC.
Scalability is the most important issue and not well-addressed in EHW field by far. To solve scalability, this paper proposes a novel EHW system called PD-ES, which integrates a Projection-based Decomposition (PD) and Evolutionary Strategy (ES). PD gradually decomposes a Boolean function by adaptively projecting it onto the property of variables, which makes the complexity and number of sub logic blocks minimized. The gate-level approach-CGP including ES searches complete solutions for these blocks. By employing PD into EHW system, the number of logic gates used for evolving and assembling the sub blocks decreases largely, and the scalability can be improved consequently. The MCNC circuits and n-parity circuits are used to prove the ability of PD-ES in solving scalability. The results illustrate that PD-ES is superior to 3SD-ES and fixed decomposition in evolving large circuits in terms of complexity reduction. Additionally, PD-ES makes success evolution in design of larger n-even-parity circuits as SDR has done.
An ecosystem inspired algorithm that aims to take advantage of highly distributed computer architectures is proposed. Our motivation is to grasp the phenomenal properties of ecosystems and use them for large-scale real-world problems. Just as an ecosystem comprises of many separate components that adapt together to form a single synergistic whole, the Artificial Ecosystem Algorithm (AEA) solves a problem by adapting subcomponents such that they fit together and form a single optimal solution. Typical biology inspired algorithms like GA, PSO, BCO, and ACO, represent candidate solutions as individuals in a population. However, AEA uses populations of solution components that are solved individually such that they combine to form the candidate solution. Like species in an ecosystem, AEA has different species that represent sub-parts of the solution, these species evolve and cooperate to form a complete solution.
In this paper, we study the evolutionary dynamics of the public goods game where the population of mobile individuals is divided into separate groups. We extend the usual discrete strategy game, by introducing "conditional investors" who have a real-value genetic trait that determines their level of risk aversion, or willingness to invest into the common pool. At the end of each round of the game, each individual has an opportunity to (a) update their risk aversion trait using a form of imitation from within their current group, and (b) to switch groups if they are not satisfied with their payoff in their current group. Detailed simulation experiments show that investment levels can be maintained within groups. The mean value of the risk aversion trait is significantly lower in smaller groups and is correlated with the underlying migration mode. In the conditional migration scenarios, levels of investment consistent with risk aversion emerge.
The fingerprint operator generates a representation-independent functional signature of a game-playing strategy, which enables the automated analysis of evolved agents. With this, we attempt to study the structure of a relatively small representation - the 8-state finite transducers for Prisoner's Dilemma. Even then, there are almost 3 x 1020 strategies representable, and hence we sample 32,768 strategies uniformly at random for investigation. Accounting for phenotypic duplicates, there are 31,531 distinct strategies in the dataset; we compute all pairwise distances and use a variety of dimensionality reduction techniques to embed it into a manageable space. Results indicate no obvious cutoff scales, and a strong structural similarity with parallel studies on the entirety of even smaller state spaces.
In this paper, we proposed a convergence speed controller (denoted as CSC) framework to improve the performance of differential evolution for continuous optimization problems.
The paper presents a parallel implementation of a variant of quantum inspired genetic algorithm (QIGA) for the problem of community structure detection in complex networks using NVIDIA® Compute Unified Device Architecture (CUDA®) technology. The paper explores feasibility of the approach in the domain of complex networks. The approach does not require any knowledge of the number of communities beforehand and works well for both directed and undirected networks. Experiments on benchmark networks show that the method is able to successfully reveal community structure with high modularity.
We designed and implemented Darwin, the first CAPTCHA generator using evolutionary algorithm. We evaluated the effectiveness of our proposed CAPTCHAs with MTurk users (non-attackers) and Antigate workers (attackers). Due to our ground-truth agnostic fitness function, we are able to discover a new category of CAPTCHAs in which attackers answer correctly but non-attackers answer incorrectly.
Data mining techniques enable efficient extraction of useful knowledge from a large data repository. However, it also can disclose sensitive information if used inappropriately. A feasible way to address this problem is to sanitize the database to conceal sensitive information. In this paper, we focus on privacy preserving in association rule mining. In light of the tradeoff between hiding sensitive rules and disclosing non-sensitive ones during the hiding process, a novel association rule hiding approach is proposed based on evolutionary multi-objective optimization (EMO). It modifies the original database by deleting identified transactions/tuples to hide sensitive rules. Experiment results are reported to show the effectiveness of the proposed approach.
A challenging issue in multi-robot system is to design effective algorithms which enable robots to collaborate with one another in order to search and find objects of interest. Unlike most of the research on PSO (particle swarm optimization) that adopts the method to a virtual multi-agent system, in this paper, we present a framework to use a modified PSO (MPSO) algorithm in a multi-robot system for search task in real-world environments. We modify the algorithm to optimize the total path traveled by robots. Experiments with multiple robots are provided.
In this paper, we describe a new real coded GA which may be used to analyze the security of quantum key distribution (QKD) protocols by estimating the maximally tolerated error rate - an important statistic and, for many newer more complicated protocols, still unknown. Our algorithm takes advantage of several nice features of QKD protocols to simplify the search process and was evaluated on several protocols and can even detect security flaws in a protocol thus showing our algorithm's usefulness in protocol design.
The extraction of weak signals from instrumental noise is a critical task in ongoing searches for gravitational waves. A detection and estimation method, made feasible by Particle Swarm Optimization, is presented for a particularly challenging class of signals expected from astrophysical sources.
This study proposes a semi-fragile watermark design method for detecting illegally copied 2D barcodes. The proposed method uses real mobile phones for fitness calculation rather than simulation. In addition, we formulate this task as a multi-objective optimization problem to design a commonly usable watermark on various mobile phones.
Biodiversity problems require strategies to accomplish specific conservation goals. An underlying principle of these strategies is known as Systematic Conservation Planning (SCP). SCP is an inherently multi-objective (MO) problem but, in the literature, it has been usually dealt with a monobjective approach. In addition, SCP analysis tend to assume that conserved biodiversity does not change throughout time. In this paper we propose a MO approach to the SCP problem which increases flexibility through the inclusion of more objectives, which whilst increasing the complexity, significantly augments the amount of information used to provide users with an improved decision support system. We employed ensemble forecasting approach, enriching our analysis by taking into account future climate simulations to estimate species occurrence projected to 2080. Our approach is able to identify sites of high priority for conservation, regions with high risk of investment and sites that may become attractive options in the future. As far as we know, this is the first attempt to apply MO algorithms to a SCP problem associated to climate forecasting, in a dynamic spatial prioritization analysis for biodiversity conservation.
We apply an evolutionary strategies (ES) algorithm to the problem of designing modulation schemes used in wireless communication systems. The ES is used to optimize the digital symbol to analog signal mapping, called a constellation. Typical human-designed constellations are compared to the constellations produced by our algorithms in a simulated radio environment with noise and multipath, in terms of bit error rate. We conclude that the algorithm, with diversity maintenance, find solutions that equal or outperform conventional ones in a given radio channel model, especially for those with higher number of symbols in the constellation (arity).
When designing a wind farm layout, we can reduce the number of variables by optimizing a pattern instead of considering the position of each turbine. In this paper we show that, by reducing the problem to only two variables defining a grid, we can gain up to $3\%$ of energy output on simple examples of wind farms dealing with many turbines (up to 1000) while dramatically reducing the computation time.
This paper proposes a novel normalization group strategy (NGS) to extend brain storm optimization (BSO) for power electronic circuit (PEC) design and optimization. As different variables in different dimensions of the PEC represent different circuit components such as resistor, capacitor, or inductor, they have different physical significances and various search space that are even not in comparable range. Therefore, the traditional group method used in BSO, which is based on the solution position information, is not suitable when solving PEC. In order to overcome this issue, the NGS proposed in this paper normalizes different dimensions of the solution to the same comparable range. This way, the grouping operator of BSO can work when using BSO to solve PEC. The NGS based BSO (NGBSO) approach has been implemented to optimize the design of a buck regulator in PEC. The results are compared with those obtained by using genetic algorithm (GA) and particle swarm optimization (PSO). Results show that the NGBSO algorithm outperforms GA and PSO in our PEC design and optimization study. Moreover, the NGS can be regarded as an efficient method to extend BSO to real-world application problems whose dimensions are with different physical significances and search ranges.
This paper proposes an adaptive multiobjective memetic algorithm to address the software next release problem. The proposed approach was tested and compared with single objective optimization approaches as well as multiobjective evolutionary approaches on real test instances mined from bug repository. Interestingly, results show multiobjective approach outperforms single objective approach in general and The proposed approach has the best performance.
Refactoring large systems involves several sources of uncertainty related to the severity levels of code smells to be corrected and the importance of the classes in which the smells are located. Due to the dynamic nature of software development, these values cannot be accurately determined in practice, leading to refactoring sequences that lack robustness. To address this problem, we introduced a multi-objective robust model, based on NSGA-II, for the software refactoring problem that tries to find the best trade-off between quality and robustness.
Taking the Next Release Problem (NRP) as a case study, we intend to analyze the relationship between heuristics and the software engineering problem instances. We adopt an evolutionary algorithm to evolve NRP instances that are either hard or easy for the target heuristic (GRASP in this study), to investigate where a heuristic works well and where it does not, when facing a software engineering problem. Thereafter, we use a feature-based approach to predict the hardness of the evolved instances, with respect to the target heuristic. Experimental results reveal that, the proposed algorithm is able to evolve NRP instances with different hardness. Furthermore, the problem-specific features enables the prediction of the target heuristic's performance.
Fate Agent EAs form a novel flavour or subclass in EC. The idea is to decompose the main loop of traditional evolutionary algorithms into three independently acting forces, implemented by the so-called Fate Agents, and create an evolutionary process by injecting these agents into a population of candidate solutions. This paper introduces an extension to the original concept, adding a mechanism to self-adapt the mutation of the Breeder Agents. The method improves the behaviour of the original Fate Agent EA on dynamically changing fitness landscapes.
Memetic search is well known as one of the state-of-the-art metaheuristics for finding high-quality solutions to NP-hard problems. Its performance is often attributable to appropriate design, including the choice of its operators. In this paper, we propose a Markov Decision Process model for the selection of crossover operators in the course of the evolutionary search. We solve the proposed model by a Q-learning method. We experimentally verify the efficacy of our proposed approach on the benchmark instances of Quadratic Assignment Problem.
Black-Box Search Algorithms (BBSAs) tailored to a specific problem class may be expected to significantly outperform more general purpose problem solvers, including canonical evolutionary algorithms. Recent work has introduced a novel approach to evolving tailored BBSAs through a genetic programming hyper-heuristic. However, that first generation of hyper-heuristics suffered from overspecialization. This poster paper presents a second generation hyper-heuristic employing a multi-sample training approach to alleviate the overspecialization problem. A variety of experiments demonstrated the significant increase in the robustness of the generated algorithms due to the multi-sample approach, clearly showing its ability to outperform established BBSAs. The trade-off between a priori computational time and the generated algorithm robustness is investigated, demonstrating the performance gain possible given additional run-time.
The present study introduces an automated mechanism to build algorithm portfolios for memetic algorithms. The objective is to determine an algorithm set involving combinations of crossover, mutation and local search operators based on their past performance. The past performance is used to cluster algorithm combinations. Top performing combinations are then considered as the members of the set. The set is expected to have algorithm combinations complementing each other with respect to their strengths in a portfolio setting. In other words, each algorithm combination should be good at solving a certain type of problem instances such that this set can be used to solve different problem instances. The set is used together with an online selection strategy. An empirical analysis is performed on the Quadratic Assignment problem to show the advantages of the proposed approach.
We consider the usage of artificial neural networks for representing genotype-phenotype maps, from and into continuous decision variable domains. Through such an approach, genetic representations become explicitly controllable entities, amenable to adaptation. With a view towards understanding the kinds of space transformations neural networks are able to express, we investigate here the typical representation locality given by arbitrary neuro-encoded genotype-phenotype maps.
There exist optimization problems with the target objective, which is to be optimized, and several extra objectives, which can be helpful in the optimization process. The previously proposed EA+RL method is designed to adaptively select objectives during the run of an optimization algorithm in order to reduce the number of evaluations needed to reach an optimum of the target objective.
The case when the extra objective is a fine-grained version of the target one is probably the simplest case when using an extra objective actually helps. We define a coarse-grained version of OneMax called XdivK as follows: XdivK(x)= [OneMax(x)/k] for a parameter k which is a divisor of n- the length of a bit vector. We also define XdivK+OneMax, which is a problem where the target objective is XdivK and a single extra objective is OneMax.
In this paper, the randomized local search (RLS) is used in the EA+RL method as an optimization algorithm. We construct exact expressions for the expected running time of RLS solving the XdivK problem and of the EA+RL method solving the XdivK+OneMax problem. It is shown that the EA+RL method makes optimization faster, and the speedup is exponential in k.
For the past 25 years, NK landscapes have been the classic benchmarks for modeling combinatorial fitness landscapes with epistatic interactions between up to K+1 of N binary features. However, the ruggedness of NK landscapes grows in large discrete jumps as K increases, and computing the global optimum of unrestricted NK landscapes is an NP-complete problem. Walsh polynomials are a superset of NK landscapes that solve some of the problems. In this paper, we propose a new class of benchmarks called NM landscapes, where M refers to the Maximum order of epistatic interactions between N features. NM landscapes are much more smoothly tunable in ruggedness than NK landscapes and the location and value of the global optima are trivially known. For a subset of NM landscapes the location and magnitude of global minima are also easily computed, enabling proper normalization of fitnesses. NM landscapes are simpler than Walsh polynomials and can be used with alphabets of any arity, from binary to real-valued. We discuss several advantages of NM landscapes over NK landscapes and Walsh polynomials as benchmark problems for evaluating search strategies.
The Introduction to Genetic Algorithms Tutorial is aimed at GECCO attendees with limited knowledge of genetic algorithms, and will start "at the beginning," describing first a "classical" genetic algorithm in terms of the biological principles on which it is loosely based, then present some of the fundamental results that describe its performance, using the schema concept. It will cover some variations on the classical model, some successful applications of genetic algorithms, and advances that are making genetic algorithms more useful.
Genetic programming emerged in the early 1990's as one of the most exciting new evolutionary algorithm paradigms. It has rapidly grown into a thriving area of research and application. While sharing the evolutionary inspired algorithm principles of a genetic algorithm, it differs by exploiting an executable genome. Genetic programming evolves a 'program' to solve a problem rather than a single solution. This tutorial introduces the basic genetic programming framework. It explains how the powerful capability of genetic programming is derived from modular algorithmic components: executable representations such as an abstract syntax tree, variation operators that preserve syntax and explore a variable length, hierarchical solution space, appropriately chosen programming functions and fitness function specification.
This tutorial gives a basic introduction to evolution strategies, a class of evolutionary algorithms. Key features such as mutation, recombination and selection operators are explained, and specifically the concept of self-adaptation of strategy parameters is introduced.
All algorithmic concepts are explained to a level of detail such that an implementation of basic evolution strategies is possible.
In addition, the tutorial also presents a brief taxonomy of contemporary evolution strategy variants, including e.g. the CMA-ES and variations thereof, and compares their performance for a small number of function evalutions - which represents many of today's practical application cases.
Some guidelines for utilization as well as some application examples are also given.
Many optimization problems are multiobjective in nature in the sense that multiple, conflicting criteria need to be optimized simultaneously. Due to the conflict between objectives, usually, no single optimal solution exists. Instead, the optimum corresponds to a set of so-called Pareto-optimal solutions for which no other solution has better function values in all objectives.
Evolutionary Multiobjective Optimization (EMO) algorithms are widely used in practice for solving multiobjective optimization problems due to several reasons. As stochastic blackbox algorithms, EMO approaches allow to tackle problems with nonlinear, nondifferentiable, or noisy objective functions. As set-based algorithms, they allow to compute or approximate the full set of Pareto-optimal solutions in one algorithm run---opposed to classical solution-based techniques from the multicriteria decision making (MCDM) field. Using EMO approaches in practice has two other advantages: they allow to learn about a problem formulation, for example, by automatically revealing common design principles among (Pareto-optimal) solutions (innovization) and it has been shown that certain single-objective problems become easier to solve with randomized search heuristics if the problem is reformulated as a multiobjective one (multiobjectivization).
This tutorial aims at giving a broad introduction to the EMO field and at presenting some of its recent research results in more detail. More specifically, we are going to (i) introduce the basic principles of EMO algorithms in comparison to classical solution-based approaches, (ii) show a few practical examples which motivate the use of EMO in terms of the mentioned innovization and multiobjectivization principles, and (iii) present a general overview of state-of-the-art algorithms and techniques. Moreover, we will present some of the most important research results in areas such as indicator-based EMO, preference articulation, and performance assessment.
Though classified as introductory, this tutorial is intended for both novices and regular users of EMO. Those without any knowledge will learn about the foundations of multiobjective optimization and the basic working principles of state-of-the-art EMO algorithms. Open questions, presented throughout the tutorial, can serve for all participants as a starting point for future research and/or discussions during the conference.
Successful and efficient use of evolutionary algorithms (EA) depends on the choice of the genotype, the problem representation (mapping from genotype to phenotype) and on the choice of search operators that are applied to the genotypes. These choices cannot be made independently of each other. The question whether a certain representation leads to better performing EAs than an alternative representation can only be answered when the operators applied are taken into consideration. The reverse is also true: deciding between alternative operators is only meaningful for a given representation.
In EA practice one can distinguish two complementary approaches. The first approach uses indirect representations where a solution is encoded in a standard data structure, such as strings, vectors, or discrete permutations, and standard off-the-shelf search operators are applied to these genotypes. This is for example the case in standard genetic algorithms, evolution strategies, and some genetic programming approaches like grammatical evolution or cartesian genetic programming. To evaluate the solution, the genotype needs to be mapped to the phenotype space. The proper choice of this genotype-phenotype mapping is important for the performance of the EA search process. The second approach, the direct representation, encodes solutions to the problem in its most 'natural' space and designs search operators to operate on this representation.
Research in the last few years has identified a number of key concepts to analyse the influence of representation-operator combinations on EA performance. Relevant properties of representations are locality and redundancy.
Locality is a result of the interplay between the search operator and the genotype-phenotype mapping. Representations are redundant if the number of phenotypes exceeds the number of possible genotypes. Redundant representations can lead to biased encodings if some phenotypes are on average represented by a larger number of genotypes or search operators favor some kind of phenotypes.
The tutorial gives a brief overview about existing guidelines for representation design, illustrates the different aspects of representations, gives a brief overview of models describing the different aspects, and illustrates the relevance of the aspects with practical examples.
It is expected that the participants have a basic understanding of EA principles.
Learning Classifier Systems were introduced in the 1970s by John H. Holland as highly adaptive, cognitive systems. More than 40 years later, the introduction of Stewart W. Wilson's XCS, a highly engineered classifier system model, has transformed them into a state-of-the-art machine learning system. Learning classifier systems can effectively solve data-mining problems, reinforcement learning problems, and also cognitive, robotics control problems. In comparison to other, non-evolutionary machine learning techniques, their performance is competitive or superior, dependent on the setup and problem. Learning classifier systems can work both online and offline, they are extremely flexible, applicable to a larger range of problems, and are highly adaptive. Moreover, system knowledge can be easily extracted, visualized, or even used to focus the progressive search on particular interesting subspaces.
This tutorial provides a gentle introduction to learning classifier systems and their general functionality. It then surveys the current theoretical understanding of the systems. Finally, we provide a suite of current successful LCS applications and discuss the most promising areas for future applications and research directions.
Neuroevolution, i.e. evolution of artificial neural networks, has recently emerged as a powerful technique for solving challenging reinforcement learning problems. Compared to traditional (e.g. value-function based) methods, neuroevolution is especially strong in domains where the state of the world is not fully known: The state can be disambiguated through recurrency, and novel situations handled through pattern matching. In this tutorial, I will review (1) neuroevolution methods that evolve fixed-topology networks, network topologies, and network construction processes, (2) ways of combining traditional neural network learning algorithms with evolutionary methods, and (3) applications of neuroevolution to control, robotics, artificial life, and games.
Evolutionary Algorithms (EAs), when used for global optimization, can be seen as unconstrained optimization techniques. Therefore, they require an additional mechanism to incorporate constraints of any kind (i.e., inequality, equality, linear, nonlinear) into their fitness function. Although the use of penalty functions (very popular with mathematical programming techniques) may seem an obvious choice, this sort of approach requires a careful fine tuning of the penalty factors to be used. Otherwise, an EA may be unable to reach the feasible region (if the penalty is too low) or may reach quickly the feasible region but being unable to locate solutions that lie in the boundary with the infeasible region (if the penalty is too severe). This has motivated the development of a number of approaches to incorporate constraints into the fitness function of an EA. This tutorial will cover the main proposals in current use, including novel approaches such as the use of tournament rules based on feasibility, multiobjective optimization concepts, hybrids with mathematical programming techniques (e.g., Lagrange multipliers), cultural algorithms, and artificial immune systems, among others. Other topics such as the importance of maintaining diversity, current benchmarks and the use of alternative search engines (e.g., particle swarm optimization, differential evolution, evolution strategies, etc.) will be also discussed (as time allows).
The language in which evolving programs are expressed can have significant impacts on the problem-solving capabilities of a genetic programming system. These impacts stem both from the absolute computational power of the languages that are used, as elucidated by formal language theory, and from the ease with which various computational structures can be produced by random code generation and by the action of genetic operators. Highly expressive languages can facilitate the evolution of programs for any computable function using, when appropriate, multiple data types, evolved subroutines, evolved control structures, evolved data structures, and evolved modular program and data architectures. In some cases expressive languages can even support the evolution of programs that express methods for their own reproduction and variation (and hence for the evolution of their offspring).
This tutorial will begin with a comparative survey of approaches to the evolution of programs in expressive programming languages ranging from machine code to graphical and grammatical representations. Within this context it will then provide a detailed introduction to the Push programming language, which was designed specifically for expressiveness and specifically for use in genetic programming systems. Push programs are syntactically unconstrained but can nonetheless make use of multiple data types and express arbitrary control structures, supporting the evolution of complex, modular programs in a particularly simple and flexible way. The Push language will be described and demonstrated, and ten years of Push-based research, including the production of human-competitive results, will be briefly surveyed. The tutorial will conclude with a discussion of recent enhancements to Push that are intended to support the evolution of complex and robust software systems.
Social animals as found in fish schools, bird flocks, bee hives, and ant colonies are able to solve highly complex problems in nature. This includes foraging for food, constructing astonishingly complex nests, and evading or defending against predators. Remarkably, these animals in many cases use very simple, decentralized communication mechanisms that do not require a single leader. This makes the animals perform surprisingly well, even in dynamically changing environments. The collective intelligence of such animals is known as swarm intelligence and it has inspired popular and very powerful optimization paradigms, including ant colony optimization (ACO) and particle swarm optimization (PSO). The reasons behind their success are often elusive. We are just beginning to understand when and why swarm intelligence algorithms perform well, and how to use swarm intelligence most effectively. Understanding the fundamental working principles that determine their efficiency is a major challenge.
This tutorial will give a comprehensive overview of recent theoretical results on swarm intelligence algorithms, with an emphasis on their efficiency (runtime/computational complexity). In particular, the tutorial will show how techniques for the analysis of evolutionary algorithms can be used to analyze swarm intelligence algorithms and how the performance of swarm intelligence algorithms compares to that of evolutionary algorithms. The results shed light on the working principles of swarm intelligence algorithms, identify the impact of parameters and other design choices on performance, and thus help to use swarm intelligence more effectively.
The tutorial will be divided into a first, larger part on ACO and a second, smaller part on PSO. For ACO we will consider simple variants of the MAX-MIN ant system. Investigations of example functions in pseudo-Boolean optimization demonstrate that the choices of the pheromone update strategy and the evaporation rate have a drastic impact on the running time. We further consider the performance of ACO on illustrative problems from combinatorial optimization: constructing minimum spanning trees, solving shortest path problems with and without noise, and finding short tours for the TSP.
For particle swarm optimization, the tutorial will cover results on PSO for pseudo-Boolean optimization as well as a discussion of theoretical results in continuous spaces.
In recent years there have been independent developments in multiple branches of Evolutionary Computation (EC) that interpret population-based and model-based search algorithms in terms of information geometric concepts. This trend has resulted in the development of novel algorithms and in improved understanding of existing ones. This tutorial aims at making this new line of research accessible to a broader range of researchers. A statistical model, identified by a parametric family of distributions, is equipped with an intrinsic (Riemannian) geometry, the so-called information geometry. From this perspective, a statistical model is a manifold of distributions where the inner product is given by the Fisher information metric. Any evolutionary algorithm that implicitly or explicitly evolves the parameters of a search distribution defines a dynamic over the manifold. Taking into account the Riemannian geometry of the new search space given by the search distributions allows for the description and analysis of evolutionary operators in a new light.
Notably, this framework can be used for the study of optimization algorithms. A core idea of several recent and novel heuristics, both in the continuous and the discrete domain, such as Estimation of Distribution Algorithms (EDAs) and Natural Evolution Strategies (NESs), is to perform stochastic gradient descent directly on the space of search distributions. However the definition of gradient depends on the metric, which is why it becomes fundamental to consider the information geometry of the space of search distributions.
Despite being equivalent to classical gradient-based methods for a stochastically relaxed problem the approach performs randomized direct search on the original search space: the generation of an offspring population as well as selection and strategy adaptation turn out to implicitly sample a search distribution in a statistical model and to perform a stochastic gradient step in the direction of the natural gradient.
Particular strengths of the information geometric framework are its ability to unify optimization in discrete and continuous domains as well as the traditionally separate processes of optimization and strategy parameter adaptation. Respecting the intrinsic information geometry automatically results in powerful invariance principles. The framework can be seen as an analysis toolbox for existing methods, as well as a generic design principle for novel algorithms. This tutorial will introduce from scratch the mathematical concept of information geometry to the EC community. It will transport not only rigorous definitions but also geometric intuition on Riemannian geometry, information geometry, natural gradient, and stochastic gradient descent. Stochastic relaxations of EC problems will act as a glue. The framework will be made accessible with applications to basic as well as state-of-the-art algorithms operating on discrete and continuous domains.
Many real-world optimization problems involve a large number of decision variables. For example, in shape optimization a large number of shape design variables are often used to represent complex shapes, such as turbine blades, aircraft wings, and heat exchangers. However, existing optimization methods are ill-equipped in dealing with this sort of large scale global optimization (LSGO) problems. A natural approach to tackle LSGO problems is to adopt a divide-and-conquer strategy. A good example is the early work on a cooperative coevolutionary (CC) algorithm by Potter and De Jong (1994), where a problem is decomposed into several subcomponents of smaller sizes, and then each subcomponent is "cooperatively coevolved" with other subcomponents.
In this tutorial we will provide an overview on the recent development of CC algorithms for LSGO problems, in particular those extended from the original Potter and De Jong's CC model. One key challenge in applying CC is how to best decompose a problem in a way such that the inter-dependency between subcomponents can be kept at minimum. Another challenge is how to best allocate a fixed computational budget among different subcomponents when there is an imbalance of contributions from these subcomponents. Equally dividing the budget among these subcomponents and optimizing each through a round-robin fashion (as in the classic CC method) may not be a wise strategy, since it can waste lots of computational resource. Many more research questions still remain to be answered. In recent years, several interesting decomposition methods (or variable grouping methods) have been proposed. This tutorial will survey these methods, and identify their strengths and weakness. The tutorial will also describe a contribution-based method for better allocating computation among the subcomponents. Finally we will present a newly designed variable grouping method, namely differential grouping, which outperforms those early surveyed decomposition methods. We will provide experimental results on CEC'2010 LSGO benchmark functions to demonstrate the effectiveness of this method.
In the last two decades, great progress has been made in molecular modelling through computational treatments of biological molecules grounded in evolutionary search techniques. Evolutionary search algorithms (EAs) are gaining popularity beyond exploring the relationship between sequence and function in biomolecules. In particular, recent work is showing the promise of EAs in exploring structure spaces of protein chains and protein assemblies to address open-standing problems in computational structural biology, such as de novo structure prediction and protein-protein docking. Exploring effective interleaving of global and local search has led to hybrid EAs that are now competitive with the Monte Carlo-based frameworks that have traditionally dominated de novo structure prediction. Similar advances have been made in protein-protein docking. Deeper understanding of the constraints posed by highly-coupled modular systems like proteins and integration of domain knowledge has resulted in effective reproductive operators. Multi-objective optimization has also shown promise in dealing with the conflicting terms that make up protein energy functions and effectively exploring protein energy surfaces. Combinations of these techniques have recently resulted in powerful stochastic search frameworks that go beyond de novo structure prediction and are capable of yielding comprehensive maps of possible diverse functionally-relevant structures of proteins. The objective of this tutorial is to introduce the EC community to the rapid developments on EA-based frameworks for protein structure modeling through a concise but comprehensive review of developments in this direction over the last decade. The review will be accompanied with specific detailed highlights and interactive software demonstrations of representative methods. The tutorial will expand the view of EA-based frameworks beyond sequence-focused application settings. The tutorial will introduce EC researchers to open problems in computational structural biology and in the process spur the design of novel and powerful evolutionary search techniques.
On behalf of the organizing committee, we cordially welcome you to the Seventeenth International Workshop on Learning Classifier Systems (IWLCS 2014). IWLCS has come a long way since its start in 1992, held at the NASA Johnson Space Center in Houston, Texas. Since 1999 the workshop has been held yearly in conjunction with PPSN in 2000 and 2002 and with GECCO in 1999, 2001 and from 2003 to 2013.
LCSs have been an integral part of the evolutionary computation field almost since its beginnings, so this workshop is very interesting for the Genetic and Evolutionary Computation (GEC) community for itself, but also because it shares many common research topics with the broader GEC field such as linkage learning, niching techniques, variable-length representations, facet-wise models, etc.
IWLCS is considered as one of the most important platform for the presentation of cutting edge research relating to LCS. Continuing the IWLCS tradition, this year's workshop includes the following:
This paper expands on work previously conducted on the XCS system using code fragments, which are GP-like trees that encapsulate building blocks of knowledge. The usage of code fragments in the XCS system enabled the solution of previously intractable, complex, boolean problems, e.g. the 135 bit multiplexer domain. However, it was not previously possible to replace functionality at nodes with learned relationships, which restricted scaling to larger problems and related domains. The aim of this paper is to reuse learned rule sets as functions. The functions are to be stored along with the code fragments produced as a solution for a problem. The results show for the first time that these learned functions can be reused in the inner nodes of the code fragment trees. The results are encouraging as there was no statistically significant difference in terms of classification. For the simpler problems the new system XCSCF2, required much less instances than the XCSCFC to solve the problems. However, for the more complex problems, the XCSCF2 required more instances than XCSCFC; but the additional time was not prohibitive for the continued development of this approach. The main contribution of this investigation is that functions can be learned and later reused in the inner nodes of a code fragment tree. This is anticipated to lead to a reduced search space and increased performance both in terms of instances needed to solve a problem and classification accuracy.
Interrelationships between rules can be used to develop network models that can usefully represent the dynamics of Learning Classifier Systems. We examine two different kinds of rule networks and study their significance by testing them on the 20-mux problem. Through this experimentation, we establish that there is latent information in the evolving rule networks alongside the usual information that we gain from the XCS. We analyze these interrelationships using metrics from Network Science. We also show that these network measures behave as reliable indicators of rule set convergence.
Welcome to the Eighth Annual Workshop on Evolutionary Computation and Multi-Agent Systems and Simulation (ECoMASS 2014)!
Evolutionary computation (EC) and multi-agent systems and simulation (MASS) both involve populations of agents. EC is a learning technique by which populations of individual agents adapt according to the selection pressures exerted by an environment; MASS seeks to understand how to coordinate the actions of a population of (possibly selfish) autonomous agents that share an environment so that some outcome is achieved. Both EC and MASS have top-down and bottom up features. For example, some aspects of multi-agent system engineering (e.g., mechanism design) are concerned with how top-down structure can constrain or influence individual decisions. Similarly, most work in EC is concerned with how to engineer selective pressures to drive the evolution of individual behavior towards some desired goal. Multi-agent simulation (also called agent-based modeling) addresses the bottom-up issue of how collective behavior emerges from individual action. Likewise, the study of evolutionary dynamics within EC (for example in coevolution) often considers how population-level phenomena emerge from individual-level interactions. Thus, at a high level, we may view EC and MASS as examining and utilizing analogous processes. It is therefore natural to consider how knowledge gained within EC may be relevant to MASS, and vice versa; indeed, applications and techniques from one field have often made use of technologies and algorithms from the other field. Studying EC and MASS in combination is warranted and has the potential to contribute to both fields.
The ECoMASS Workshop at GECCO has a successful history as a forum for exploring precisely this intersection, and we are looking forward to another year of stimulating discussion, bringing together experts as well as novices in both areas, to engage in dialogue about their work. This year's participants bring a variety of research topics for discussion, including migratory flows, the beating of the heart, embedded systems, pelotons and cyclists, and flocking behavior. This year, we will also be adding a "research slam". We will be inviting presenters who are presenting in the general conference to give us a quick presentation about their work. We hope that this will further encourage additional lively discussion about a wide range of topics. We also encourage presenters to demonstrate their software live during a breakout session, enabling additional opportunities for one-on-one dialogue and discussion of actual running systems. Through these additions to the workshop, we hope to continue to innovate, and develop the conversations around the interesting intersection of evolutionary computation and multi-agent systems and simulations!
Agent-Based Models are used to model dynamic systems such as stock markets, societies, and complex biological systems that are difficult to model analytically using partial differential equations. Many agent-based modeling software are designed for serial von-Neumann computer architectures. That limits the speed and scalability of these systems. Systemic computation (SC) is designed to be a model of natural behavior and, at the same time, a non Von-Neumann architecture with its characteristics similar to multi-agent system. Here we propose a novel method based on an Artificial Immune System (AIS) and implemented on a systemic computer, which is designed to adapt itself over continuous arrival of data to cope with changing patterns of noise without requirement for feedback, as a result of its own experience. Experiments with heartbeat data collected from a clinical trial in hospitals using a digital stethoscope shows the algorithm performs up to 3.60% better in the precision rate of murmur and 3.96% better in the recall rate of murmur than other standard anomaly detector approaches such as Multiple Kernel Anomaly Detection (MKAD).
This paper deals with the problem of scheduling the mixed workload of both homogeneous multiprocessor on-line and off-line periodic tasks in a critical reconfigurable real-time environment by a genetic algorithm. Two forms of automatic reconfigurations which are assumed to be applied at run-time: Addition-Removal of tasks or just modifications of their temporal parameters: worst case execution time (WCET) and/or deadlines. Nevertheless, when such a scenario is applied to save the system at the occurrence of hardware-software faults, or to improve its performance, some real-time properties can be violated at run-time. We define an Intelligent Agent that automatically checks the system's feasibility after any reconfiguration scenario to verify if all tasks meet the required deadlines after a reconfiguration scenario was applied on a multiprocessor embedded real-time system. Indeed, if the system is unfeasible, then the proposed genetic algorithm dynamically provides a solution that meets real-time constraints. This genetic algorithm based on a highly efficient decoding procedure, strongly improves the quality of real-time scheduling in a critical environment. The effectiveness and the performance of the designed approach is evaluated through simulation studies illustrated by testing Hopper's benchmark results.
A team of agents that cooperate to solve a problem together can handle many complex tasks that would not be possible without cooperation. While the benefit is clear, there are still many open questions in how best to achieve this cooperation. In this paper we focus on the role of communication in allowing agents to evolve effective cooperation for a prey capture task. Previous studies of this task have shown mixed results for the benefit of direct communication among predators, and we investigate potential explanations for these seemingly contradictory outcomes. We start by replicating the results of a study that found that agents with the ability to communicate actually performed worse than those without when each member of a team was evolved in a separate population . The simulated world used for these experiments is very simple, and we hypothesize that communication would become beneficial in a similar but more complex environment. We test several methods of increasing the problem complexity, but find that at best communicating predators perform equally as well as those that cannot communicate. We thus propose that the representation may hinder the success of communication in this environment. The behavior of each predator is encoded in a neural network, and the networks with communication have 6 inputs as opposed to just 2 for the standard network, giving communicating networks more than twice as many links for which to evolve weights. Another study using a relatively similar environment but genetic programming as a representation finds that communication is clearly beneficial for prey capture . We hypothesize that adding communication is less costly to these genetic programs as compared to the earlier neural networks and outline experiments to test this theory.
Development of Internet technology has made the use of email to be one of the predominant means of communication in the information society. Information exchange among people via email service has produced lots of communication data, which have been widely used in research about information propagation on virtual social networks. The focus of this paper is on the "Enron Email Dataset". The ideas discussed gave thorough consideration to the diversity of organizational positions' attributes, the dynamic behaviors of users to select information contents and communication partners via email service. We then established a quantitative analysis on the multiple interactive relationships of the email communication network. Further, an agent-based model for modeling the information diffusion in an organization via email communication network was proposed, by relating the microscopic individual behaviors and the macroscopic system evolution. Based on the simulation experiments, we analyzed and compared the topological characteristics and evaluative patterns of our model with the Enron Email Dataset. The experimental results proved that our model was beneficial to uncover the implicit communication mechanisms of a real organization.
The Island Model (IM) is a well known multi-population approach for Evolutionary Algorithms (EAs). One of the critical parameters for defining a suitable IM is the migration topology. Basically it determines the Migratory Flows (MF) between the islands of the model which are able to improve the rate and pace of convergence observed in the EAs coupled with IMs. Although, it is possible to find a wide number of approaches for the configuration of MFs, there still is a lack of knowledge about the real performance of these approaches in the IM. In order to fill this gap, this paper presents a thorough experimental analysis of the approaches coupled with the state-of-the-art EA Differential Evolution. The experiments on well known benchmark functions show that there is a trade-off between convergence speed and convergence rate among the different approaches. With respect to the computational times, the results indicate that the increase in implementation complexity does not necessarily represent an increase in the overall execution time.
It is our great pleasure to welcome you to the GECCO'14 Student Workshop!
The goal of the Student Workshop, organized as a joined event for graduate and undergraduate students, is to assist the students with their research in the field of Evolutionary Computation.
Exceeding our expectations in both the number and quality of submitted papers, 14 peer-reviewed papers have finally been accepted for presentation at the workshop. They cover a wide range of subjects in evolutionary computation, presenting advances in theory as well as applications, e.g. robotics and the travelling salesman problem. The topics include particle swarm algorithms as well as flood evolution, reinforcement learning, parallelism, niching, and parameter tuning, and many more, all yielding interesting contributions to the field.
During the workshop, the students will receive useful feedback on the quality of their work and presentation style. This will be assured by a question and answer period after each talk led by a mentor panel of established researchers. The students are encouraged to use this opportunity to get highly qualified feedback not only on the presented subject but also on future research directions. As it was good practice in the last years, the best contributions will receive a small award sponsored by GECCO.
In addition, the contributing students are invited to present their work as a poster at the GECCO'14 Poster Session -- an excellent opportunity to network with industrial and academic members of the community.
We hope that the variety of covered topics will catch the attention of a wide range of GECCO'14 attendees, who will learn about fresh research ideas and meet young researchers with related interests. Other students are encouraged to attend the workshop to learn from the work of their colleagues and broaden their (scientific) horizons.
In natural systems, many animals organize into groups without a designated leader and still perform complex collective behaviors. Although individuals in the group may be considered equal, all the individuals differ in the traits each of them possess. Of particular interest is the idea of an individual's personality as it often plays a role in determining which individuals lead collective behaviors. Personality is, in part, developed and maintained by an individual's experiences. However, neither an individual, nor its environment remains unchanged. Therefore, there is a need for an individual to continue to gain new experiences to ensure that its information about itself and its environment are current. Since observations have shown that the effects of experience on personality can decay over time, we investigate the effects of this decay on the emergence of leaders and followers and the resulting success of a group's collective movement attempts. Results show that personality decay has a negative effect on the overall success of the group in collective movements as it prevents the emergence of distinct personalities, a necessary requirement for individuals to assume distinct leader and follower roles.
Stagnation is a prevalent issue in many heuristic search algorithms, such as Particle Swarm Optimization (PSO). PSO stagnation occurs when the rate of position changes (or velocities) that attract particles to the global best position approaches zero, potentially leading the swarm to being trapped in a local optimum, especially for deceptive multimodal optimization problems. This paper proposes a novel fitness-based stagnation detection method that effectively and efficiently restarts the search process to escape potential local optima. The main idea of the proposed method is to make use of the already calculated fitness values of swarm particles, instead of their pairwise distance values, to predict an imminent stagnation situation. That is, the proposed fitness-based method does not require any computational overhead of repeatedly calculating pairwise distances between all particles at each iteration. The proposed fitness-based method substantially outperforms the commonly used distance-based method when tested on several classical and advanced (shifted/rotated) benchmark optimization functions in three ways: 1) The optimization performance is significantly better performing (using Wilcoxon rank-sum test). 2) The optimization performance is considerably faster (up to three times). 3) The proposed fitness-based method is less dependent on the problem search space, compared with the distance-based method.
In evolutionary optimization, it is important to use efficient evolutionary operators, such as mutation and crossover. But it is often difficult to decide, which operator should be used when solving a specific optimization problem. So an automatic approach is needed. We propose an adaptive method of selecting evolutionary operators, which takes a set of possible operators as input and learns what operators are efficient for the considered problem. One evolutionary algorithm run should be enough for both learning and obtaining suitable performance. The proposed EA+RL(O) method is based on reinforcement learning. We test it by solving H-IFF and Travelling Salesman optimization problems. The obtained results show that the proposed method significantly outperforms random selection, since it manages to select efficient evolutionary operators and ignore inefficient ones.
The use of finite-state machines (FSMs) is a reliable choice for control system design since they can be formally verified. In this paper a problem of constructing FSMs with real-valued input and control parameters is considered. It is supposed that a set of human-created behavior examples, or tests, is available. One of the earlier approaches for solving the problem suggested using genetic algorithms together with a transition labeling algorithm. This paper improves this approach via the use of real-valued variables which are calculated using the FSM's input data. FSMs with real-valued variables are represented as systems of linear controllers. The new approach allows to synthesize FSMs of better quality than it was possible earlier.
We describe the utilization of on-chip multiple CPU architectures to automatically evolve parallel computer programs. These programs have the capability of exploiting the computational efficiency of the modern multi-core machines.
This is significantly different from other parallel EC approaches because not only do we produce individuals that, in their final form, can exploit parallel architectures, we can also exploit the same parallel architecture during evolution to reduce evolution time.
We use Grammatical Evolution along with OpenMP specific grammars to produce natively parallel code, and demonstrate that not only do we enjoy the benefit of final individuals that can run in parallel, but that our system scales effectively with the number of cores.
We propose a numeric variant of quantum-inspired evolutionary algorithm (QIEA) where gene in the quantum chromosome is a superposition of k qubits, thus allowing the genes of the classical chromosome to take numeric values. We also present a modified form of real observation QIEA. Both these techniques are applied to the problem of partitioning a complex network. The algorithm parameters are tuned using an evolutionary bilevel search optimization technique.
Conventionally control can be achieved by attempting to simplify complex dynamics. The field of morphological computation explores how mechanical complexity can be advantageous. In this paper we demonstrate morphological computation in tensegrity robots. We present a novel approach to tensegrity actuation and explore the capabilities of our self-evolving system. Methods of finding desirable gaits through both hand selection and evolution are described and the effectiveness of the system is demonstrated by our robot's ability to pursue a moving target. We conclude with a discussion of a bootstrapped system with the potential of significantly reducing evolution time and need for user presence.
Many-objective optimization problems are common in real-world applications, few evolutionary optimization methods, however, are suitable for them up to date due to their difficulties. We proposed a reference points-based evolutionary algorithm (RPEA) to solve many-objective optimization problems in this study. In RPEA, a series of reference points with good performances in convergence and distribution are generated according to the current population to guide the evolution. Furthermore, superior individuals are selected based on the assessment of each individual by calculating the distances between the reference points and the individual in the objective space. The algorithm was applied to four benchmark optimization problems and compared with NSGA-II and HypE. The results experimentally demonstrate that the algorithm is strengthened in obtaining Pareto optimal set with high performances.
This research is devoted analysis of convergence in particle swarm where each of the particles can represent different dynamic behaviour in search space.
We present ongoing research that is an extension of novelty search, flood evolution. This technique aims to improve evolutionary algorithms by presenting them with large sets of problems, as opposed to individual ones. If the older approach of incremental evolution were analogous to moving over a path of stepping stones, then this approach is similar to navigating a rocky field. The method is discussed and preliminary results are presented.
It is commonly observed that aggregation in nature provides significant benefits to the group members. However, to reach a consensus individual preferences are frequently lost. Conflict is generally avoided because of the negative influence it could have on the success of collective movements. However, it could be used to balance consensus costs with individual preferences. Using a biologically-based collective movement model, this work investigates the possibility of conflict in a group movement allowing for differing individual goals to be accomplished, while still maintaining group cohesion much of the time. Individuals focus on their own needs, which may include the protection of being a part of a group or the desire to move away from the group and towards its preferred destination. Results show that by allowing conflict in group decision-making, consensus costs were balanced with individual preferences in such a way that group level success still occurred, while significantly improving the success of differing goals.
The paper introduces a Case Based Approximation method to solve large scale Traveling Salesman Problems in a short time with a low error rate. It is useful for domains with most solutions being similar to solutions that have been created. Thus, a solution can be derived by (1) selecting a most similar TSP from a library of former TSP solutions, (2) removing the locations that are not part of the current TSP and (3) adding the missing locations of the current TSP by mutation, namely Nearest Insertion (NI). This way of creating solutions by Case Based Reasoning (CBR) avoids the computational costs to create new solutions from scratch.
Multi-modal problems with multiple local/global optima are ubiquitous in real-world application. Many multi-modal optimization algorithms have been developed to search as many local/global optima as possible. However, to locate and maintain many optima simultaneously, both the search quality and efficiency of these algorithms may be influenced. Here, we propose a new niching genetic algorithm that attempts to improve both the search quality and efficiency. To the end, we incorporate two mechanisms into the algorithm: cumulative population technique and an evaluated probability of new individuals. The first mechanism is designed to keep the found solutions by storing all known information, whilst the second is responsible for exploiting unexplored space effectively by guiding the exploration process. The proposed approach is compared with five different niche genetic algorithms on six well known multimodal functions of different characteristics. Empirical results indicate that the proposed approach outperforms other algorithms. It not only increases the probability of finding both global and local optima, but also reduces the average number of function evaluations.
The simplification function was introduced to PushGP as a tool to reduce the sizes of evolved programs in final reports. While previous work suggests that simplification could reduce the sizes significantly, nothing has been done to study its impacts on the evolution of Push programs. In this paper, we show the impact of simplification as a genetic operator. By conducting test runs on the U.S. change problem, we show that using simplification operator with PushGP, lexicase selection and ULTRA could increase the possibility to find solutions in the short term while it might remove some useful genetic materials for the long term.
As work on visualisation in the evolutionary computation field continues to grow, we are pleased to be organising the fifth GECCO workshop on visualisation in genetic and evolutionary computation (VizGEC 2014).
Following a call for papers, three papers were accepted for presentation at the workshop. The papers cover a diverse range of topics, and we are particularly pleased to note that one of them builds on a discussion that took place at last year's workshop. Topics include visualising stability within an evolutionary algorithm, the visualisation of trade-offs in many-objective optimisation, and finally a method for visualising empirical attainment function differences. In addition to the presentation of papers, we are inviting demonstrations of tools that are used by people engaged in evolutionary computation research. We hope that by presenting a range of different tools and techniques we will encourage a discussion on visualisation methods that people find useful, as well as how the current state-of-the-art can be extended, with the development of new techniques and the application of existing methods to new problems, to fulfill researcher's visualisation needs.
We hope that the workshop will appeal to a wide range of GECCO attendees, from those with experience of developing novel visualisation methods, to those who simply use them as a tool to illustrate their work. We also intend that the workshop will provide an attractive opportunity for those with visualisation problems to find opportunities to engage with the visualisation community and identify potential collaborations.
It is well-known that Evolutionary Algorithms (EAs) are sensitive to changes in their control parameters, and it is generally agreed that too large a change may turn the EA from being successful to unsuccessful. This work reports on an experimental hybrid visualization scheme for the determination of EA stability according to perturbation of EA parameters. The scheme gives a visual representation of local neighborhoods of the parameter space according to a choice of two perturbation metrics, relating perturbations to EA performance as a variant of Kolmogorov distance. Through visualization and analysis of twelve thousand case study EA runs, we illustrate that we are able to distinguish between EA stability and instability depending upon perturbation and performance metrics. Finally we use what we have learned in the case study to provide a methodology for more general EAs.
This paper proposes a technique of Aggregation Trees to visualize the results of high-dimensional multiobjective optimization problems, or many-objective problems. The high-dimensionality makes it difficult to represent the relation between objectives and solutions. Most approaches in the literature are based on the representation of solutions in lower dimensions. The technique of Aggregation Trees proposed here is based on iterative aggregation of objectives which are represented in a tree. Besides, the location of conflict is also calculated and represented on the tree. Thus, the tree can represent which objectives and groups of objectives are harmonic the most, what sort of conflict is present between groups of objectives, and which aggregations would be more interesting in order to reduce the problem dimension.
In multiobjective optimization, the Empirical Attainment Function (EAF) can be used to determine which areas of the objective space are attained by an optimization algorithm. If two algorithms are to be compared, differences in EAF values show which areas of the objective space are more often attained by one of the algorithms. While the visualization of EAF values and differences is rather straightforward in 2D, the 3D case presents a great challenge as we need to visualize a large number of 3D cuboids. This paper presents a method for computing the cuboids with constant EAF values and reports on initial experiments using Maximum Intensity Projection, a very-well known volume rendering technique used in medicine.
It is our great pleasure to welcome you to the GECCO Workshop on Evolutionary Computation Software Systems (EvoSoft).
The evolution of so many different metaheuristic optimization algorithms results from the fact that no single method can outperform all others for all possible problems. As postulated in the No Free Lunch Theorem, a general-purpose and universal optimization strategy is impossible. The only way how one strategy can outperform another is to be more specialized to the structure of the tackled problem. Consequently it always takes qualified algorithm experts to select and tune a metaheuristic algorithm for a specific application.
Choosing an appropriate method for a certain problem is not trivial, as problem characteristics may change remarkably for different instances and the performance of a metaheuristic may vary considerably for different parameter settings. Therefore the choice of a well suited method and according parameter values is a crucial aspect when applying metaheuristics.
Because of these issues it is not advisable to implement only one specific metaheuristic algorithm for a specific problem, as it cannot be determined in advance whether the chosen method is suitable for the tackled problem or not. Thus soundly engineered, reusable, flexible, user-friendly and interoperable software systems are required which offer a broad spectrum of different metaheuristic algorithms and support researchers in adapting and comparing these methods for different problems in order to bridge the gap between theoretical research and practical applications.
However, the development of such systems is both, time consuming and complex. Surprisingly the chance to join forces in the development of evolutionary computation software systems is not yet seized sufficiently within the evolutionary computation research community. Instead of reusing existing software and continuing their work on the shoulders of others, many researchers implement individual and highly specialized applications. Often these systems are not even publically released which hinders comparability and replicability of research results.
The EvoSoft Workshop should highlight the importance of software engineering and software quality in the domain of evolutionary computation and should enable researchers to exchange their ideas on how to develop and apply generic and reusable software systems. It should provide a common platform to present open and freely available frameworks, to discuss novel approaches in their development, to identify cooperation potentials and synergies between research groups, and to define common standards.
Rapid prototyping and testing of new ideas has been a major argument for evolutionary computation frameworks. These frameworks facilitate the application of evolutionary computation and allow experimenting with new and modified algorithms and problems by building on existing, well tested code. However, one could argue, that despite the many frameworks of the metaheuristics community, software packages such as MATLAB, GNU Octave, Scilab, or RStudio are quite popular. These software packages however are associated more closely with numerical analysis rather than evolutionary computation. In contrast to typical evolutionary computation frameworks which provide standard implementations of algorithms and problems, these popular frameworks provide a direct programming environment for the user and several helpful functions and mathematical operations. The user does not need to use traditional development tools such as a compiler or linker, but can implement, execute, and visualize his ideas directly within the environment. HeuristicLab has become a popular environment for heuristic optimization over the years, but has not been recognized as a programming environment so far. In this article we will describe new scripting capabilities created in HeuristicLab and give information on technical details of the implementation. Additionally, we show how the programming interface can be used to integrate further metaheuristic optimization frameworks in HeuristicLab. Categories and Subject D.
The genetic programming tool EDDIE has been shown to be a successful financial forecasting tool, however it has suffered from an increase in execution time as new features have been added. Speed is an important aspect in financial problems, especially in the field of algorithmic trading, where a delay in taking a decision could cost millions. To offset this performance loss, EDDIE has been modified to take advantage of multi-core CPUs and dedicated GPUs. This has been achieved by modifying the candidate solution evaluation to use an OpenCL kernel, allowing the parallel evaluation of solutions. Our computational results have shown improvements in the running time of EDDIE when the evaluation was delegated to the OpenCL kernel running on a multi-core CPU, with speed ups up to 21 times faster than the original EDDIE algorithm. While most previous works in the literature reported significantly improvements in performance when running an OpenCL kernel on a GPU device, we did not observe this in our results. Further investigation revealed that memory copying overheads and branching code in the kernel are potentially causes of the (under-)performance of the OpenCL kernel when running on the GPU device.
Nowadays advanced software systems need to satisfy large number of quality attributes at the same time. It is a very complex optimization problem which software architects must address. Evolutionary algorithms can help architects to find optimal solutions which meet these conflicting quality attributes. However, these metaheuristic approaches in multiobjective problems especially for high dimensions mostly take so long time to be executed. One of the best solutions to speed up this process is distributing execution of evolutionary algorithm on multiple nodes of a super computer or on the cloud.
This paper presents the results of distributed execution of evolutionary algorithm for multiobjective optimization of software architecture. We report implementation of two different ways for distributed execution of evolutionary algorithm: (1) Actor-based approach, (2) MapReduce approach. The case study in this experiment is an industrial software system which is derived from a real world automotive embedded system.
The results of this computationally-intensive experiment on a super computer give us 81.27% parallelization efficiency for distribution among 5 nodes.
In order for appropriate meta-heuristics to be chosen and tuned for specific problems, it is critical that we better understand the problems themselves and how algorithms solve them. This is particularly important as we seek to automate the process of choosing and tuning algorithms and their operators via hyper-heuristics. If meta-heuristics are viewed as sampling algorithms, they can be classified by the trajectory taken through the search space. We term this trajectory a trace. In this paper, we present Hyperion2, a Java™ framework for meta- and hyper- heuristics which allows the analysis of the trace taken by an algorithm and its constituent components through the search space. Built with the principles of interoperability, generality and efficiency, we intend that this framework will be a useful aid to scientific research in this domain.
In this paper we describe a novel implementation of the Interpreter class for the metaheuristic optimization framework HeuristicLab, comparing it with the three existing interpreters provided with the framework. The Interpreter class is an internal software component utilized by HeuristicLab for the evaluation of the symbolic expression trees on which its Genetic Programming (GP) implementation relies. The proposed implementation is based on the creation and compilation of a .NET Expression Tree. We also analyze the Interpreters' performance, evaluating the algorithm execution times on GP Symbolic Regression problems for different run settings. Our implementation results to be the fastest on all evaluations, with comparatively better performance the larger the run population size, dataset length and tree size are, increasing HeuristicLab's computational efficiency for large problem setups.
There are many different genetic programming (GP) frameworks that can be used to implement algorithms to solve a particular optimization problem. In order to use a framework, users need to become familiar with a large numbers of source code before actually implementing the algorithm, adding a learning overhead. In some cases, this can prevent users from trying out different frameworks. This paper discusses the implementation of a code generator in the EpochX framework to facilitate the implementation of GP algorithms. The code generator is based on the GP definition language (GPDL), which is a framework-independent language that can be used to specify GP problems.
In this paper, we propose a multiobjective probabilistic Pareto local search to address combinatorial optimization problems (COPs). The probability is determined by the success counts of local search offspring entering an external domination archive and this probabilistic information is used to further guide the selection of promising solutions for Pareto local search. In addition, simulated annealing is integrated in this framework as the local refinement process. This multiobjective probabilistic Pareto local search algorithm (MOPPLS), is tested on two famous COPs and compared with some well-known multiobjective evolutionary algorithms. Experimental results suggest that MOPPLS outperforms other compared algorithms.
When Electronic Design Automation (EDA) has achieved great success both in academy and industry, design automation for mechanical systems seems to be lagged behind. One underlying reason for this is that the coupling of subsystems of mechanical systems is very strong, whereas this coupling for digital electronic system is usually much weaker. Or in other words, the modularity of electronic systems, especially digital electronic systems is much stronger. On the other hand, the mechatronic systems are becoming more and more modularized, which makes them more amenable to be designed automatically, just as digital electronic systems do. In this sense, Mechatronic Design Automation (MDA) is very likely to become the next wave after EDA both in academy and industry. In this paper, we give a survey of the topic of evolutionary synthesis of dynamical systems in general, and wish to shed some light on the future development of this subject.
MEMS layout optimization is a typical multi-objective constrained optimization problem. This paper proposes an improved MOEA called cMOEA/D to solve this problem. The cMOEA/D is based on MOEA/D but also uses the frequency of individual update of sub-problems to locate the promising sub-problems. By dynamically allocating computing resources to more promising sub-problems, we can effectively improve the performance of the algorithm to find more non-dominated solutions in MEMS layout optimization. In addition, we compared two mechanisms of constraint handling, Stochastic Ranking (SR) and Constraint-domination principle (CDP). The experimental results show that CDP works better than SR and the proposed algorithm outperforms the state-of-art algorithms such as NSGA-II and MOEA/D, in terms of convergence and diversity.
In this paper, the ε constrained method and Adaptive operator selection (AOS) are used in Multiobjective evolutionary algorithm based on decomposition (MOEA/D). The ε constrained method is an algorithm transformation method, which can convert algorithms for unconstrained problems to algorithms for constrained problems using the ε level comparison, which compares search points based on the pair of objective value and constraint violation of them. AOS is used to determine the application rates of different operators in an online manner based on their recent performances within an optimization process. The experimental results show our proposed approach for multiobjective constrained optimization is very competitive compared with other state-of-art algorithms.
We would like to express our great pleasure in welcoming you to the GECCO Workshop on Green and Efficient Energy Applications of Genetic and Evolutionary Computation (GreenGEC Workshop'14), held in conjunction with the GECCO 2014 International Conference.
A main characteristic of the studies in the area of green and energy-efficient applications is the strong connection with real-world environments and constraints. As such, there is only little place for errors and leading edge algorithms alone can be used. The potential impact and outcomes are also of foremost importance. Global increases in living standards, diminishing natural resources and environmental concerns place energy amongst the most important global issues today. On the consumer side, there is an increasing need for more efficient, smart, uses of energy, be it in large-scale computing systems and data warehouses, in homes or in office buildings. On the producer side, there is a push toward the use of sustainable, green, energy sources, which often come in the form of less reliable sources such as wind energy. In addition, future energy systems are often envisioned to be "smart", consisting of massive amounts of small generators, such as solar panels, located at consumers, effectively turning consumers into potential producers whenever they have a surplus of energy. The management, control and planning of, and efficient use of energy in (future) energy systems brings about many important challenges.
Energy systems are not only real-world systems, they are also one of the most important foundations of the modern world. Especially with the upcoming required changes to make more efficient use of energy and to shift towards a global use of sustainable, green energy sources, there are many challenges in mathematics and computer science. Real-world challenges, such as those arising in (future) energy systems, are typically highly complex because of the many aspects to be considered that are often disregarded in theoretical research such as dynamic changes, uncertainty and multiple objectives. In many situations therefore, problem-specific algorithms are infeasible or impractical. Instead, flexible and powerful approaches such as evolutionary algorithms (EAs) can often provide viable solutions. Typical real-world challenges that are addressed by EAs are of the optimization type. This covers the use of EAs to optimize issues ranging from energy consumption (e.g. scheduling, memory/storage management, communication protocols, smart sensors, etc.) to the planning and design of energy systems at many levels, ranging from small printed circuit boards to entire transmission networks.
In this paper, we tackle the distribution network expansion planning (DNEP) problem by employing two evolutionary algorithms (EAs): the classical Genetic Algorithm (GA) and a linkage-learning EA, specifically a Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA). We furthermore develop two efficiency-enhancement techniques for these two EAs for solving the DNEP problem: a restricted initialization mechanism to reduce the size of the explorable search space and a means to filter linkages (for GOMEA) to disregard linkage groups during genetic variation that are likely not useful. Experimental results on a benchmark network show that if we may assume that the optimal network will be very similar to the starting network, restricted initialization is generally useful for solving DNEP and moreover it becomes more beneficial to use the simple GA. However, in the more general setting where we cannot make the closeness assumption and the explorable search space becomes much larger, GOMEA outperforms the classical GA.
Reducing power consumption in LTE networks has become an important issue for mobile network operators. The 3GPP organization has included such operation as one of SON (Self-Organizing Networks) functions . Using the approach presented in this paper the decision about turning Radio Access Network (RAN) nodes off and on, according to the network load (which is typically low at night), is taken into account. The process is controlled using a combination of Fuzzy Logic and Q-Learning techniques (FQL). The effectiveness of the proposed approach has been evaluated using the LTE-Sim simulator with some extensions. The simulations are very close to real network implementation: we used the RAN node parameters that are defined by 3GPP and simulations take into account the network behaviour in the micro time scale.
This paper proposes and evaluates a multiobjective evolutionary game theoretic framework for adaptive and stable application deployment in clouds that support dynamic voltage and frequency scaling (DVFS) for CPUs. The proposed framework, called Cielo, aids cloud operators to adapt the resource allocation to applications and their locations according to the operational conditions in a cloud (e.g., workload and resource availability) with respect to multiple conflicting objectives such as response time performance, recourse utilization and power consumption. Moreover, Cielo theoretically guarantees that each application performs an evolutionarily stable deployment strategy, which is an equilibrium solution under given operational conditions. Simulation results verify this theoretical analysis; applications seek equilibria to perform adaptive and evolutionarily stable deployment strategies. Cielo allows applications to successfully leverage DVFS to balance their response time performance, resource utilization and power consumption.
The rise of the data centers industry, together with the emergence of large cloud computing that require large quantities of resources to be maintained, brought the need of providing a sustainable development process. Through this paper we aim to provide an introductory insight on the status and tools available to tackle this perspective within the evolutionary and genetic algorithms community. Existing advancements are also emphasized and perspectives outlined.
It is our great pleasure to welcome you to the 2014 GECCO Workshop on Problem Understanding and Real World Optimisation (PURO). This year's workshop builds upon the success of last year's even which was organized as part of GECCO 2013, held in the VU University in Amsterdam. Last year's event was a joint workshop combining workshops on problem understanding organised by Kent McClymont of the University of Exeter and on real world optimisation organized by Emma Hart from Edinburgh Napier University. Based on the success of last year's joint workshop this year's event merges the two workshops into a single event covering both ranges of topics.
This workshop aims to provide a single forum for the presentation and discussion of works focused on optimisation problems rather than the methods for solving them. The workshop brings together the study of real-world optimisation problems with the theoretical analysis and synthesis of problems.
The workshop will focus on, but not be limited to, topics such as:
The call for papers attracted submissions from Asia, Canada, Europe, and the United States. The topics covered address some of the real world issues and constraints imposed by industry and the complications associated with applying highly specialised techniques to real world problems. In addition, the program includes two keynote speeches, one from an industrial perspective and the other from academia. We are very grateful to both speakers, Anna I Esparcia-Alcázar from S2 GRUPO, Spain and Darrell Whitley from Colorado State University, USA who both have extensive knowledge of biologically inspired computing techniques within both industrial and academic environments.
Co-location of multiple antenna systems on a single fixed or mobile platform can be challenging due to a variety of factors, such as mutual coupling, individual antenna constraints, multipath, obstructions, and parasitic effects due to the platform. The situation frequently arises where a new communication capability, and hence antenna system, is needed on an existing platform. The problem of placing new antennas requires a long, manual effort in order to complete an antenna placement study. An automated procedure for determining such placements would not only save time, but would be able to optimize the performance of all co-located antenna systems. In this paper we examine a set of stochastic algorithms to determine their effectiveness at finding optimal placements for multiple antennas on a platform. To our knowledge, this is the first study to investigate optimizing multiple antenna placement on a single platform using multiple stochastic algorithms. Of the four algorithms studied, simulated annealing and evolutionary strategy were found to be most effective in finding optimal placements.
This paper studies the frequency assignment problem (FAP) in TD-SCDMA network of mobile communications industry in China. The problem considers finding the optimal frequency allocation scheme for carriers with a limited frequency resource, such that the entire network interference is minimized. Besides, the allocation of frequencies needs to satisfy some constraints to avoid the effect of call interference within the same cell or adjacent cell. Given the formula for calculation of the network interference, we take the FAP as a constrained optimization problem and use a hyper-heuristic genetic algorithm (HHGA) to optimize the assignment of frequencies. We first define six low-level heuristics (LLHs) search strategies based on the computation of interference, and then use genetic algorithm (GA) at a high-level to find the best combination sequence of LLH strategies to reduce interferences of the overall network. GA uses two-point crossover, uniform mutation, and Minimal Generation Gap (MGG) as the generation alternation model. In order to speed up the search, we define a Tabu table to avoid repeat search of LLHs. Compared with scatter search as one of the meta-heuristic algorithm with best performance, our experimental results on real data sets of TD-SCDMA network have shown better result.
We describe a hyper-heuristic application developed for a client to find quick, acceptable solutions to Workforce Scheduling and Routing problems. An interactive fitness function controlled by the user enables five different objectives to be weighted according to client preference. The application uses a real road network in order to calculate driving distances between locations, and is designed to integrate with a web-based application to access employee calendars.
It is our great pleasure to welcome you to the all-new 2014 Workshop on Genetic and Evolutionary Computation in Defense, Security, and Risk Management (SecDef'14). With the constant appearance of new threats, research in the areas of defense, security and risk management has acquired an increasing importance over the past few years. These new challenges often require innovative solutions and Computational Intelligence techniques can play a significant role in finding them. The workshop encouraged the submission of papers describing both theoretical developments and applications of Genetic and Evolutionary Computation and their hybrids to the following (and other related) topics:
The workshop invited completed or ongoing work, with the aim to encourage communication between active researchers and practitioners to better understand the current scope of efforts within this domain. The ultimate goal is to understand, discuss, and help set future directions for computational intelligence in security and defense problems.
As a first-year workshop, the organizers received and accepted four high-quality submissions from North America and Europe:
This paper presents an approach, based in a project in development, which combines Data Mining, Machine Learning and Computational Intelligence techniques, in order to create a user-centric and adaptable corporate security system. Thus, the system, named MUSES, will be able to analyse the user's behaviour (modelled as events) when interacting with the company's server, accessing to corporate assets, for instance. As a result of this analysis, and after the application of the aforementioned techniques, the Corporate Security Policies, and specifically, the Corporate Security Rules will be adapted to deal with new anomalous situations, or to better manage user's behaviour. The work reviews the current state of the art in security issues resolution by means of these kind of methods. Then it describes the MUSES features in this respect and compares them with the existing approaches.
Botnets represent a destructive cyber security threat that aim to hide their malicious activities within legitimate Internet traffic. Part of what makes botnets so affective is that they often upgrade themselves over time, hence reacting to improved detection mechanisms. In addition, Internet common communication protocols (i.e. HTTP) are used for the purposes of constructing subversive communication channels. This work employs machine learning algorithms (genetic programming and decision trees) to detect distinct behaviours in various botnets. That is to say, botnets mimic legitimate HTTP traffic while actually serving botnet purposes. To this end, two different feature sets are employed and analyzed to see how differences between three botnets - Zeus, Conficker and Torpig - can be distinguished. Specific recommendations are then made regarding the utility of different feature sets and machine learning algorithms for detecting each type of botnet.
A Moving Target (MT) defense constantly changes a system's attack surface, in an attempt to limit the usefulness of the reconnaissance the attacker has collected. One approach to this defense strategy is to intermittently change a system's configuration. These changes must maintain functionality and security, while also being diverse. Finding suitable configuration changes that form a MT defense is challenging. There are potentially a large number of individual configurations' settings to consider, without a full understanding of the settings' interdependencies.
Evolution-based algorithms, which formulate better solutions from good solutions, can be used to create a MT defense. New configurations are created based on the security of previous configurations and can be periodically implemented to change the system's attack surface. This approach not only has the ability to discover new, more secure configurations, but is also proactive and resilient since it can continually adapt to the current environment in a fashion similar to systems found in nature.
This article presents and compares two genetic algorithms to create a MT defense. The primary difference between the two is based on their approaches to mutation. One mutates values, and the other modifies the domains from which values are chosen.
The use of robotic sensor networks (RSNs) for Territorial Security (TerrSec) applications has earned an increasing popularity in recent years. In Critical Infrastructure Protection (CIP) applications, the RSN goal is to provide the information needed to maintain a secure perimeter around the desired infrastructure and efficiently coordinate a corporate response to any event that arises in the monitored region. Such a response will only involve the most suitable robotic nodes and must successfully counter any detected vulnerability in the system. This paper is a preliminary study of the role played by multi-objective optimization (MOO) in the elicitation of responses from a risk-aware RSN that is deployed around a critical infrastructure. Contrary to previous studies showcasing a pre-optimization auctioning scheme, where the RSN nodes bid on the basis of their knowledge of the event, we introduce a post-optimization auctioning scheme in which the nodes place their bids knowing what their final positions along the perimeter will be, hence calling for a more informed decision at the node level. The impact of the pre- vs. post-optimization stage in a first-price sealed bid auction system over the risk mitigation strategies elicited by the RSN is evaluated and discussed. Empirical results reveal that the pre-optimization auctioning is more suitable for dense RSNs whereas the post-optimization one is preferred in sparse RSNs. To the best of our knowledge, this is the first attempt to assess the role of MOO in risk mitigation for CIP with RSNs.
It is our great pleasure to welcome you to the first Workshop on Evolutionary Computation for Big Data and Big Learning ECBDL'14
We live in a time of unprecedented access to cheap and vast amounts of computational resources, which is producing a big leap forward in the fields of machine learning and data mining. We can tackle datasets of a scale (be it instances, attributes, classes, etc.) that was unimaginable some years ago, in what is well known as big data. On the other hand we can also use all these vast computational resources with the aim of understanding better our machine learning methods, by performing large scale evaluations, parameter sweeps, etc. We refer to the overall use massive on-demand computation (cloud or GPUs) for machine learning as Big Learning. Evolutionary Machine Learning techniques are perfect candidates for big learning tasks due to their flexibility in knowledge representations, learning paradigms and their innate parallelism.
In this workshop we have accepted two papers representing very different scenarios of big data and big learning. The first paper, "Evolving Relational Hierarchical Classification Rules for Predicting Gene Ontology-Based Protein Functions" by Ricardo Cerri, Rodrigo C. Barros, Alex A. Freitas and André C. P. L. F. Carvalho, focuses on an extremely complex and heterogeneous classification task, where instances have multiple classes organized hierarchically. The method is tested on real-world biological data, and explores the use of new rule representations to enhance knowledge discovery.
The second paper, "On the Application of GP to Streaming Data Classification Tasks with Label Budgets" by Ali Vahdat, Aaron Atwater, Andrew R. McIntyre, Malcolm I. Heywood, focuses on a very important topic within big data/learning, streaming data classification, in the particular scenario where access to the real annotation (classes) of data is costly, and budgets need to be specified.
Hierarchical Multi-Label Classification (HMC) is a complex classification problem where instances can be classified into many classes simultaneously, and these classes are organized in a hierarchical structure, having subclasses and superclasses. In this paper, we investigate the HMC problem of assign functions to proteins, being each function represented by a class (term) in the Gene Ontology (GO) taxonomy. It is a very difficult task, since the GO taxonomy has thousands of classes. We propose a Genetic Algorithm (GA) to generate HMC rules able to classify a given protein in a set of GO terms, respecting the hierarchical constraints imposed by the GO taxonomy. The proposed GA evolves rules with propositional and relational tests. Experiments using ten protein function datasets showed the potential of the method when compared to other literature methods.
A framework is introduced for applying GP to streaming data classification tasks under label budgets. This is a fundamental requirement if GP is going to adapt to the challenge of streaming data environments. The framework proposes three elements: a sampling policy, a data subset and a data archiving policy. The sampling policy establishes on what basis data is sampled from the stream, and therefore when label information is requested. The data subset is used to define what GP individuals evolve against. The composition of such a subset is a mixture of data forwarded under the sampling policy and historical data identified through the data archiving policy. The combination of sampling policy and the data subset achieve a decoupling between the rate at which the stream passes and the rate at which evolution commences. Benchmarking is performed on two artificial data sets with specific forms of sudden shift and gradual drift as well as a well known real-world data set.
Welcome to MedGEC 2014 MedGEC is the GECCO Workshop on the application of genetic and evolutionary computation (GEC) to problems in medicine and healthcare.
A dedicated workshop at GECCO continues to provide a much needed focus for medical related applications of evolutionary computation, not only providing a clear definition of the state of the art, but also support to practitioners for whom genetic and evolutionary computation might not be their main area of expertise or experience.
The Workshop has two main aims:
This is the tenth year that this Workshop has been presented at GECCO, a reflection of the continued importance of genetic and evolutionary programming to medical applications. Presentations reflect awide range of healthcare areas including: Medical Imaging and Signal Processing; Data Mining Medical Data and Patient Records; Clinical Expert Systems and Knowledge-based Systems; Modeling and Simulation of Medical Processes; and Clinical Diagnosis and Therapy. Despite this broad range of applications, there are common themes of interest that are important in achieving a successful solution to the problems addressed. One recurring theme is accessibility to reliable medical datasets to train, test and evaluate genetic and evolutionary algorithms. It is acknowledged that achieving a "Gold Standard" dataset is problematic, due to the difficulties in gaining access to patients and the reliance on conventional clinical evaluation, which is often subjective, and therefore, potentially unreliable. A second important theme is the choice of genetic and evolutionary algorithm employed, its suitability for the problem at hand and the benefits of alternate representations. The Workshop provides a knowledgeable and supportive forum in which these and other issues can be discussed. Although traditionally a venue for practitioners in genetic and evolutionary computation development, it is hoped that the Workshop will also attract a wider audience, such as medical practitioners and other healthcare professionals who have an interest in the use of evolutionary algorithms in medicine. The Workshop organizers are always receptive to suggestions for new themes, areas for discussion and new activities and can be contacted directly via email.
In this paper, we present a new method for classification of electroencephalogram (EEG) signals using Genetic Programming (GP). The Empirical Mode Decomposition (EMD) is used to extract the features of EEG signals which served as an input for the GP. In this paper, new constructive crossover and mutation operations are also produced to improve GP. In these constructive crossover and mutation operators hill climbing search is integrated to remove the destructive nature of these operators. To improve GP, we apply constructive crossover on all the individuals which remain after reproduction. A new concept of selecting the global prime off-springs of the generation is also proposed. The constructive mutation approach is applied to poor individuals who are left after selecting globally prime off-springs. Improvement of the method is measured against classification accuracy, training time and the number of generations for EEG signal classification. As we show in the results section, the classification accuracy can be estimated to be 98.69% on the test cases, which is better than classification accuracy of Liang and coworkers method which was published in 2010.
Diabetes mellitus is a disease that affects to hundreds of millions of people worldwide. Maintaining a good control of the disease is critical to avoid severe long-term complications. In recent years, a lot of research has been made to improve the quality of life of the diabetic patient, especially in the automation of glucose level control. One of the main problems that arises in the (semi) automatic control of diabetes, is to obtain a model that explains the behavior of blood glucose levels with insulin, food intakes and other external factors, fitting the characteristics of each individual or patient. Recently, Grammatical Evolution (GE), has been proposed to solve this lack of models. A proposal based on GE was able to obtain customized models of five in-silico patient data with a mean percentage average error of 13.69%, modeling well also both hyper and hypoglycemic situations. In this paper we have extended the study of Error Grid Analysis (EGA) to prediction models in up to 8 in-silico patients. EGA is commonly used in Endocrinology to test the clinical significance of differences between measurements and real value of blood glucose, but has not been used before as a metric in obtention of glycemia models.
Image segmentation is a common image processing step to many computer vision applications with the purpose to segment pixels into different classes. As improved variants of particle swarm optimization (PSO) algorithms, the fractional-order Darwinian particle swarm optimization (FODPSO) and Darwinian particle swarm optimization (DPSO) have been proposed for image segmentation. The purpose of this paper is to compare the segmentation performance of PSO, DPSO, and FODPSO as parametric approaches to existing methods; namely the parametric fuzzy c-means (FCM) algorithm, and the non-parametric Otsu segmentation technique with application to five biomedical images. All PSO-based experiments are conducted with twenty runs to assess the effectiveness of PSO models. The universal quality index is used to evaluate the segmentation results. The obtained experimental results showed that particle swarm based algorithms outperformed both FCM and Otsu segmentation technique.
Parkinson's disease is a chronic neurodegenerative condition that manifests clinically with various movement disorders. These are often treated with the dopamine-replacement drug levodopa. However, the dosage of levodopa must be kept as low as possible in order to avoid the drug's side effects, such as the involuntary, and often violent, muscle spasms called dyskinesia, or levodopa-induced dyskinesia. In this paper, we investigate the use of genetic programming for training classifiers that can monitor the effectiveness of levodopa therapy. In particular, we evolve classifiers that can recognise tremor and dyskinesia, movement states that are indicative of insufficient or excessive doses of levodopa, respectively. The evolved classifiers achieve clinically useful rates of discrimination, with AUC>0.9. We also find that temporal classifiers generally out-perform spectral classifiers. By using classifiers that respond to low-level features of the data, we identify the conserved patterns of movement that are used as a basis for classification, showing how this approach can be used to characterise as well as classify abnormal movement.
Neuronal signaling is one of several approaches to network nanomachines in the human body. This paper formulates a noisy optimization problem for a neuronal signaling protocol based on Time Division Multiple Access (TDMA) and solves the problem with a noise-aware optimizer that leverages an evolutionary algorithm. The proposed optimizer is intended to minimize signaling latency by multiplexing and parallelizing signal transmissions in a given neuronal network, while maximizing signaling robustness (i.e., unlikeliness of signal interference). Since latency and robustness objectives conflict with each other, the proposed optimizer seeks the optimal trade-offs between them. It exploits a nonparametric (i.e. distribution-free) statistical operator because it is not fully known what distribution(s) noise follows in each step/component in neuronal signaling. Simulation results show that the proposed optimizer efficiently obtains quality TDMA signaling schedules and operates a TDMA protocol by balancing conflicting objectives in noisy environments.
In this paper we discuss heterogeneous estimation model ensembles for cancer diagnoses produced using various machine learning algorithms. Based on patients' data records including standard blood parameters, tumor markers, and information about the diagnosis of tumors, the goal is to identify mathematical models for estimating cancer diagnoses. Several machine learning approaches implemented in HeuristicLab and WEKA have been applied for identifying estimators for selected cancer diagnoses: k-nearest neighbor learning, decision trees, artificial neural networks, support vector machines, random forests, and genetic programming. The models produced using these methods have been combined to heterogeneous model ensembles. All models trained during the learning phase are applied during the test phase; the final classification is annotated with a confidence value that specifies how reliable the models are regarding the presented decision: We calculate the final estimation for each sample via majority voting, and the relative ratio of a sample's majority vote is used for calculating the confidence in the final estimation. We use a confidence threshold that specifies the minimum confidence level that has to be reached; if this threshold is not reached for a sample, then there is no prediction for that specific sample.
As we show in the results section, the accuracies of diagnoses of breast cancer, melanoma, and respiratory system cancer can so be increased significantly. We see that increasing the confidence threshold leads to higher classification accuracies, bearing in mind that the ratio of samples, for which there is a classification statement, is significantly decreased.
It is our great pleasure to welcome you to the 6th 2014 GECCO Workshop on Symbolic Regression and Modeling. Over the past five workshops, we have had interesting presentations and fantastic discussions around symbolic regression, genetic programming, and the increasing demands and opportunities to impact science and industry. The workshop has spawned new research and lead to many new collaborations. We are looking forward to another great workshop with four accepted papers and one invited talk.
Symbolic Regression and Modeling is used to designate the search for symbolic descriptions, usually in the language of mathematics, to describe and predict numerical data in diverse fields such as industry, economics, finance and science.
Symbolic modeling captures the field of symbolic regression: a genetic programming based search technique for finding symbolic formulae on numerical data in order to obtain an accurate and concise description of that data in symbolic, mathematical form. In the evolutionary computation field it also captures learning classifier systems, if and when they are applied to obtain specific interpretable results in the field of interest.
The key discriminator of producing symbolic results over numerical results is the ability to interpret and analyze the results, leading either to acceptance by field experts, or to heightened understanding of the theory in the field of application. Interpretation is key, and the workshop will focus heavily on this. The workshop will focus on advances in using symbolic modeling for real world problems in industry, economics, finance and science.
The invited talk to be presented at the workshop is by David Medernach from the University on the topic of training data sampling approaches in symbolic regression modeling.
Improvement of processes in metallurgical industry is a constant of competitive enterprises, however, changes made in a process are risky and involves high cost and time, considering this, a model can be made even using inputs usually not presented in real process and its analysis could be useful for the improvement of the process. In this work, a mathematical model is built using only experimental data of a four high tandem cold rolling mill, a set of input variables involving characteristics of the process. The performance of the model is determined by residual analysis considering new data. Results are a non black box model with a good performance; by this way, the model is a good representation of the process under study.
The quality of the evolved solutions of an evolutionary algorithm (EA) varies across different runs and a significant percentage of runs can produce solutions of undesirable quality. These runs are a waste of computational resources, particularly in difficult problems where practitioners have time bound limitations in repeating runs. This paper proposes a completely novel approach, that of a Run Prediction Model (RPM) in which we identify and terminate evolutionary runs that are likely to produce low-quality solutions. This is justified with an Ant Colony Optimization (ACO) based classifier that learns from the early generations of a run and decides whether to continue or not.
We apply RPM to Grammatical Evolution (GE) applied to four benchmark symbolic regression problems and consider several contemporary machine learning algorithms to train the predictive models and find that ACO produces the best results and acceptable predictive accuracy for this first investigation. The ACO discovered prediction models are in the form of a list of simple rules. We further analyse that list manually to tune them in order to predict poor GE runs.
We then apply the analysed model to GE runs on the regression problems and terminate the runs identified by the model likely to be poor, thus increasing the rate of production of successful runs while reducing the computational effort required. We demonstrate that, although there is a high bootstrapping cost for RPM, further investigation is warranted as the mean success rate and the total execution time enjoys a statistically significant boost on all the four benchmark problems.
In this publication genetic programming (GP) with data migration for symbolic regression is presented. The motivation for the development of the algorithm is to evolve models which generalize well on previously unseen data. GP with data migration uses multiple subpopulations to maintain the genetic diversity during the algorithm run and a sophisticated training subset selection strategy. Each subpopulation is evaluated on a different fixed training subset (FTS) and additionally a variable training subset (VTS) is exchanged between the subpopulations at specific data migration intervals. Thus, the individuals are evaluated on the unification of FTS and VTS and should have better generalization properties due to the regular changes of the VTS.
The implemented algorithm is compared to several GP variants on a number of symbolic regression benchmark problems to test the effectiveness of the multiple populations and data migration strategy. Additionally, different algorithm configurations and migration strategies are evaluated to show their impact with respect to the achieved quality.
A novel approach is proposed for generating equations from measured data of dynamic processes. A composition of unary (alpha) and binary (beta) functions is represented by a real vector and adapted by an evolutionary algorithm to build mathematical equations. The equations can be used for identification and prediction considering a mathematical model with specific number of inputs and outputs. Three cases are used for illustration of the approach where mathematical models and plots of theirs performance are presented with promising results.
Automated Design of Algorithms (ADA) and Genetic Improvement (GI) are two relatively young fields of research that have been receiving more attention in recent years. Both methodologies can improve programs using evolutionary search methods and successfully produce human competitive programs. ADA and GI are used for improving functional properties such as quality of solution and non-functional properties, e.g. speed, memory and, energy consumption. Only GI of the two has been used to fix bugs, probably because it is applied globally on the whole source code while ADA typically replaces a function or a method locally. While GI is applied directly to the source code ADA works ex-situ, i.e. as a separate process from the program it is improving.
Although the methodologies overlap in many ways they differ on some fundamentals and for further progress to be made researchers from both disciplines should be aware of each other's work.
The mutation operator is the only genetic operator in Evolutionary Programming (EP). In the past researchers have nominated Gaussian, Cauchy, and Lévy distributions as mutation operators. According to the No Free Lunch theorem , no single mutation operator is able to outperform all others over the set of all possible functions. Potentially there is a lot of useful information generated when EP is ongoing. In this paper, we collect such information and propose a step size based self-adaptive mutation operator for Evolutionary Programming (SSEP). In SSEP, the mutation operator might be changed during the evolutionary process, based on the step size, from generation to generation. Principles for selecting an appropriate mutation operator for EP is proposed, with SSEP grounded on the principles. SSEP is shown to outperform static mutation operators in Evolutionary Programming on most of the functions tested. We also compare the experimental results of SSEP with other recent Evolutionary Programming methods, which uses multiple mutation operators.
Black-Box Search Algorithms (BBSAs) tailored to a specific problem class may be expected to significantly outperform more general purpose problem solvers, including canonical evolutionary algorithms. Recent work has introduced a novel approach to evolving tailored BBSAs through a genetic programming hyper-heuristic. However, that first generation of hyper-heuristics suffered from over-specialization. This paper presents a study on the second generation hyper-heuristic which employs a multi-sample training approach to alleviate the over-specialization problem. In particular, the study is focused on the affect that the multi-sample approach has on the problem configuration landscape. A variety of experiments are reported on which demonstrate the significant increase in the robustness of the generated algorithms to changes in problem configuration due to the multi-sample approach. The results clearly show the resulting BBSAs' ability to outperform established BBSAs, including canonical evolutionary algorithms. The trade-off between a priori computational time and the generated algorithm robustness is investigated, demonstrating the performance gain possible given additional run-time.
There have been several papers published relating to the practice of benchmarking in machine learning and Genetic Programming (GP) in particular. In addition, GP has been accused of targeting over-simplified 'toy' problems that do not reflect the complexity of real-world applications that GP is ultimately intended. There are also theoretical results that relate the performance of an algorithm with a probability distribution over problem instances, and so the current debate concerning benchmarks spans from the theoretical to the empirical.
The aim of this article is to consolidate an emerging theme arising from these papers and suggest that benchmarks should not be arbitrarily selected but should instead be drawn from an underlying probability distribution that reflects the problem instances which the algorithm is likely to be applied to in the real-world. These probability distributions are effectively dictated by the application domains themselves (essentially data-driven) and should thus re-engage the owners of the originating data.
A consequence of properly-founded benchmarking leads to the suggestion of meta-learning as a methodology for automatically designing algorithms rather than manually designing algorithms. A secondary motive is to reduce the number of research papers that propose new algorithms but do not state in advance what their purpose is (i.e. in what context should they be applied). To put the current practice of GP benchmarking in a particular harsh light, one might ask what the performance of an algorithm on Koza's lawnmower problem (a favourite toy-problem of the GP community) has to say about its performance on a very real-world cancer data set: the two are completely unrelated.
The widespread adoption of 'Design Patterns' heralded a revolution in the software industry, offering a catalog of designs that cut across lower-level concerns such as choice of programming language, platform etc.
In a similar manner, we anticipate that the identification of "crosscutting abstractions" within metaheuristic theory and practice will afford new and unifying perspectives on a field that has become dominated by metaphor and is in danger of increasingly fragmentation.
Despite this being the first MetaDeeP workshop, we are happy to say that there were a total of 15 submissions, of which 10 have been accepted. Each submission was reviewed by at least two program committee members. One of the main goals for this initial Workshop is to attempt consensus on what the metaheuristics community might usefully obtain from a pattern-based approach. To this end, the range of presentation topics is intentionally diverse, and includes:
The longer-term motivation behind the Workshop is twofold:
Above all, we envision this initiative as primarily bottom-up, driven by ideas and needs of the community rather than by any arbitrary assumptions. A panel discussion will following the paper presentations and we will attempt to provide a platform for the range of opinions expressed by those present.
To construct graphs whose quality results from complicated relationships that pervade the entire graph, especially relationships at multiple scales, follow a strategy of repeatedly making local patches to a single graph. Look for small, easily recognized flaws in local areas of the graph and fix them. Add tags to the graph to represent non-local relationships and higher-level structures as individual nodes. The tags then have easily recognized flaws that relate to non-local and higher-level concerns, enabling local patching to set off cascades of local fixes that address those concerns.
Could decisions made during some search iterations use information discovered by other search iterations? Then store that information in tags: data that persist between search iterations.
In metaheuristic algorithms applied to certain problems, it may be difficult to design search operators that guarantee producing feasible search points. In such cases, it may be more efficient to allow a search operator to yield an infeasible solution, and then turn it into a feasible one using a repair process. This paper is an attempt to provide a broad perspective on the candidate solution repair and frame it as a metaheuristic design pattern.
To many people, the terms nature-inspired algorithm and metaheuristic are interchangeable. However, this contemporary usage is not consistent with the original meaning of the term metaheuristic, which referred to something closer to a design pattern than to an algorithm. In this paper, it is argued that the loss of focus on true metaheuristics is a primary reason behind the explosion of "novel" nature-inspired algorithms and the issues this has raised. To address this, this paper attempts to explicitly identify the metaheuristics that are used in conventional optimisation algorithms, discuss whether more recent nature-inspired algorithms have delivered any fundamental new knowledge to the field of metaheuristics, and suggest some guidelines for future research in this field.
Single-solution metaheuristics are among the earliest and most successful metaheuristics, with many variants appearing in the literature. Even among the most popular variants, there is a large degree of overlap in terms of actual behavior. Moreover, in the case of hybrids of different metaheuristics, traditional names do not actually reflect how the hybrids are composed. In this paper, we discuss a template for single-solution hybrid metaheuristics. Our template builds upon the Paradiseo-MO framework, but restricts itself to a pre-defined structure based on iterated local search (ILS). The flexibility is given by generalizing the components of ILS (perturbation, local search and acceptance criterion) in order to incorporate components from other metaheuristics. We give precise definitions of these components within the context of our proposed template. The template proposed is flexible enough to reproduce many classical single-solution metaheuristics and hybrids thereof, while at the same time being sufficiently concrete to generate code from a grammar description in order to support automatic design of algorithms. We give examples of three IG-VNS hybrids that can be instantiated from the proposed template.
The optimization literature is awash with metaphorically-inspired metaheuristics and their subsequent variants and hybridizations. This results in a plethora of methods, with descriptions that are often polluted with the language of the metaphor which inspired them . Within such a fragmented field, the traditional approach of manual 'operator tweaking' makes it difficult to establish the contribution of individual metaheuristic components to the overall success of a methodology.
Irrespective of whether it happens to best the state-of-the-art, such 'tweaking' is so labour-intensive that does relatively little to advance scientific understanding. In order to introduce further structure and rigour, it is therefore desirable to not only to be able to specify entire families of metaheuristics (rather than individual metaheuristics), but also be able to generate and test them. In particular, the adoption of a model agnostic approach towards the generation of metaheuristics would help to establish which metaheuristic components are useful contributors to a solution.
The helper-objective approach for solving the job-shop scheduling problem using multi-objective evolutionary algorithms is considered.
We implemented the approach from the Lochtefeld and Ciarallo paper using NSGA-II with the correct implementation of the non-dominated sorting procedure which is able to work with equal values of objectives. The experimental evaluation showed the significant improvement of solution quality.
We also report new best results for 16 out of 24 problem instances used in the considered paper.
The existence of the curse of dimensionality is well known, and its general effects are well acknowledged. However, perhaps due to this colloquial understanding, specific measurements on the curse of dimensionality and its effects are not as extensive. In continuous domains, the volume of the search space grows exponentially with dimensionality. Conversely, the number of function evaluations budgeted to explore this search space usually grows only linearly. New experiments show that particle swarm optimization and differential evolution have super-linear growth in convergence time as dimensionality grows. When restricted by a linear growth in allotted function evaluations, this super-linear growth in convergence time leads to a decrease in the allowed population size.
This paper presents a fast genetic algorithm (GA) for solving the flexible job shob scheduling problem (FJSP). The FJSP is an extension of a classical NP-hard job shop scheduling problem. Here, we combine the active schedule constructive crossover (ASCX) with the generalized order crossover (GOX). Also, we show how to divide a population of solutions in the high-low fit selection scheme in order to guide the search efficiently. An initial experimental study indicates high convergence capabilities of the proposed GA.
In recent years, deep learning methods applying unsupervised learning to train deep layers of neural networks have achieved remarkable results in numerous fields. In the past, many genetic algorithms based methods have been successfully applied to training neural networks. In this paper, we extend previous work and propose a GA-assisted method for deep learning. Our experimental results indicate that this GA-assisted approach improves the performance of a deep autoencoder, producing a sparser neural network.
The gravitational search algorithm (GSA) is a stochastic population-based metaheuristic inspired by the interaction of masses via Newtonian gravity law. In this paper, we propose a modified GSA (MGSA) based on logarithm and Gaussian signals for enhancing the performance of standard GSA. To evaluate the performance of the proposed MGSA, well-known benchmark functions in the literature are optimized using the proposed MGSA, and provides comparisons with the standard GSA.
Recently, it was proposed a new metaheuristic optimization approach namely bat algorithm (BA), which is based on the fascinating capability of microbats in to find their prey and discriminate different types of insects even in complete darkness. In this paper, we introduce a novel enhanced hybrid approach combining BA with a mutation style operator from differential evolution and beta probability distribution (BADEBD) and report its performance on to identification of the 10 hysteresis parameters for the 2-dimensional Jiles-Atherton hysteresis modeling to a material under rotational excitation. Compared with the classical BA, the proposed BADEBD performs better in terms of the solution accuracy and the convergence rate.
The portfolio selection is an essential component of fund administration because it contributes to economic growth of the investor. Many of the related works use the Markowitz's mean-variance portfolio selection model approach to solve this optimization problem. However, the use of continuous variables in this approach does not allow us to implement directly the obtained solutions because assets cannot be divided. This paper presents a portfolio selection model that involves integer variables, allowing a more realistic treatment. Due to the complexity of this mixed-integer nonlinear programming problem, a corresponding genetic algorithm is used to solve it.
This paper describes ongoing research on the use of genetic programming to learn term-weighting schemes to be used for text classification. A term-weighting scheme (TWS) determines the way in which documents are represented before applying a text classification model. We propose a genetic program that aims at learning an effective TWS that can improve the performance in text classification. We report preliminary experimental results that give evidence of the validity of the proposal.
Genetic algorithms are widely used to solve combinatorial optimization problems, but they often take a long time. Usually, generating and evaluating a large number of different solutions spend most of the running time. We propose a genetic algorithm for the linear ordering problem which uses an approximate fitness evaluation. We use a part of the edges to compute the fitness function value, and the number of the edges for this is gradually increased during the evolutionary process. We present experimental results on the benchmark library LOLIB. The approximation scheme reduced the running time without loss of solution quality in general.
This paper has the purpose of presenting a new hybridization of the Artificial Bee Colony Algorithm (ABC) based on the evolutionary strategies (ES) found on the Evolutionary Particle Swarm Optimization (EPSO). The main motivation of this approach is to augment the original ABC in a way that combines the effectiveness and simplicity of the ABC with the robustness and increased exploitation of the Evolution Strategies.
The algorithm is intended to be tested on two large-scale engineering design problem and its results compared to other optimization techniques.
This paper describes a methodology for evolving image reconstruction transforms consisting of an arbitrarily large, user-selected number of wavelet and scaling numbers. Given images previously subjected to lossy compression using NASA's wavelet-based ICER compressor, these novel transforms are capable of reconstructing those images with less error than ICER's own reconstruction scheme. This advance has the potential to enhance the science value of all images subjected to lossy compression.
This paper presents an adaptive memetic algorithm (AMA) to minimize the total travel distance in the NP-hard vehicle routing problem with time windows (VRPTW). Although memetic algorithms (MAs) have been proven to be very efficient in solving the VRPTW, their main drawback is an unclear tuning of their numerous parameters. Here, we introduce the AMA in which the selection scheme and the population size are adjusted during the search. We propose a new adaptive selection scheme to balance the exploration and exploitation of the search space. An extensive experimental study confirms that the AMA outperforms a standard MA in terms of the convergence capabilities.
This paper examines the influence of neutral crossover operators in a genetic algorithm (GA) applied to the one-dimensional bin packing problem. In the experimentation 16 benchmark instances have been used and the results obtained by three different GAs are compared with the ones obtained by an evolutionary algorithm (EA). The aim of this work is to determine whether an EA (with no crossover functions) can perform similarly to a GA.
In this paper the influence of using heuristic functions to initialize the population of a classic genetic algorithm (GA) applied to the N-Queens Problem (NQP) is analyzed. The aim of this work is to evaluate the impact of the heuristic initialization phase on the results of the classic GA. In order to probe this, several experiments using two different initialization functions have been carried out. In this paper, the well-known NQP has been used as benchmark problem, but the objective of the authors is to contrast the findings of this study with other combinatorial optimization problems.
Image reconstruction from projections in tomography is an ill-posed, inverse problem. This problem is always a challenge because there are no standard methods which give satisfactory results. In this paper we propose hybridization between Local Search (LS) and Harmony Search (HS) metaheuristics to improve quality of reconstructed images. The proposed method is implemented, tested on some images and compared to LS and Filtered backprojection (FBP) methods. The preliminary results are promising and prove the efficiency of our method.
This paper compares the performance of parallel computation on two types of many-core processors, Tesla K20c GPU and Xeon Phi 5110P, in solving the quadratic assignment problem (QAP) with ant colony optimization (ACO). The results show that the performance on Xeon Phi 5110P is not so promising compared to the Tesla K20c GPU on these problems. Further efficient implementation methods must be investigated for Xeon Phi.
Genetic Algorithm (GA) classifier can automatically search a proper clustering number according to fitness evaluation instead of assignment by users. In this study, a GA classifier with various fitness functions is adopted to search the cluster centers and a suitable cluster number for digital images to overcome the disadvantages of the conventional unsupervised classifier. By employing a proper clustering index as fitness, a GA with length-variable chromosome can determine the most suitable number of clusters and the most proper cluster centers.
This paper evaluates three popular classification indexes, including DBI, FCMI, and PASI, as fitness functions in GA operation. The GA classifier is applied to SPOT-5 satellite image to verify its accuracy and robustness. The results show the GA classifier adopting FCMI having the best performance, followed by DBI and PASI, sequentially. Regarding to computation efficiency, the GA classification with DBI took much less computation time of the GA classifications with FCMI and PASI.
In this paper, inspired by speed-up and speed-down (SUSD) mechanism observed by the fish swarm avoiding light, an SUSD strategy is proposed to develop new swarm intelligence based optimization algorithms to enhance the accuracy and efficiency of swarm optimization algorithms. By comparing with the global best solution, each particle adaptively speeds up and speeds down towards the best solution. Specifically, a new directed speed term is added to the original particle swarm optimization (PSO) algorithm or other PSO variations. Due to the SUSD mechanism, the algorithm shows a great improvement of the accuracy and convergence rate compared with the original PSO and other PSO variations. The numerical evaluation is provided by solving recent benchmark functions in IEEE CEC 2013.
The paper proposed a new genetic clustering algorithm with variable-length chromosome representation (GCVCR), which can automatically evolve and find the optimal number of clusters as well as proper cluster centers of the data set. A new clustering criterion based on message passing between data points and the candidate centers described by the chromosome are presented to make the clustering problem more effective. The simulation results show the effectiveness of the proposed algorithm.
Based on the concept and principles of quantum computing, a novel genetic clustering algorithm is proposed, which can automatically clustering a data set into clusters, and evolve the optimal number of clusters as well as the cluster centers of a data set. A Q-gate with adaptive selection of the angle for every niche is introduced as a variation operator to drive individuals toward better solutions. Experiments show that the algorithm proposed is better than simple clustering algorithms.