Sub-Tree Swapping Crossover and Arity Histogram Distributions
Stephen Dignum, Riccardo Poli
Recent theoretical work has characterised the search bias of GP sub-tree swapping crossover in terms of program length distributions, providing an exact fixed point for trees with internal nodes of identical arity. However, only an approximate model (based on the notion of average arity) for the mixed-arity case has been proposed. This leaves a particularly important gap in our knowledge because multi-arity function sets are commonplace in GP and deep lessons could be learnt from the fixed point. In this paper, we present an accurate theoretical model of program length distributions when mixed-arity function sets are employed. The new model is based on the notion of an arity histogram, a count of the number of primitives of each arity in a program. Empirical support is provided and a discussion of the model is used to place earlier findings into a more general context.
Phenotypic Diversity in Initial Genetic Programming Populations
A key factor in the success or otherwise of a genetic programming population in evolving towards a solution is the extent of diversity amongst its members. Diversity may be viewed in genotypic (structural) or in phenotypic (behavioural) terms, but the latter has received less attention. We propose a method for measuring phenotypic diversity in terms of the run-time behaviour of programs. We describe how this is applicable to a range of problem domains and show how the promotion of such diversity in initial genetic programming populations can have a substantial impact on solution-finding performance.
Controlling Complex Dynamics with Artificial Biochemical Networks
Michael Lones, Andy Tyrrell, Susan Stepney, Leo Caves
Artificial biochemical networks (ABNs) are computational models inspired by the biochemical networks which underlie the cellular activities of biological organisms. This paper shows how evolved ABNs may be used to control chaotic dynamics in both discrete and continuous dynamical systems, illustrating that ABNs can be used to represent complex computational behaviours within evolutionary algorithms. Our results also show that performance is sensitive to model choice, and suggest that conservation laws play an important role in guiding search.
Enabling Object Reuse on Genetic Programming-based Approaches to Object-Oriented Evolutionary Testing
José Ribeiro, Mário Zenha-Rela, Francisco Vega
Recent research on search-based test data generation for Object-Oriented software has relied heavily on typed Genetic Programming for representing and evolving test data. However, standard typed Genetic Programming approaches do not allow Object Reuse; this paper proposes a novel methodology to overcome this limitation. Object Reuse means that one instance can be passed to multiple methods as an argument, or multiple times to the same method as arguments. In the context of Object-Oriented Evolutionary Testing, it enables the generation of test programs that exercise structures of the software under test that would not be reachable otherwise. Additionally, the experimental studies performed show that the proposed methodology is able to effectively increase the performance of the test data generation process.
Analytic Solutions to Differential Equations under Graph-based Genetic Programming
Tom Seaton, Gavin Brown, Julian Miller
Cartesian Genetic Programming (CGP) is applied to solving differential equations (DE). We illustrate that repeated elements in analytic solutions to DE can be exploited under GP. An analysis is carried out of the search space in tree and CGP frameworks, examining the complexity of different DE problems. Experimental results are provided against benchmark ordinary and partial differential equations. A system of ordinary differential equations (SODE) is solved using multiple outputs from a genome. We discuss best heuristics when generating DE solutions through evolutionary search.
A Relaxed Approach to Simplification in Genetic Programming
Mark Johnston, Thomas Liddle, Mengjie Zhang
We propose a novel approach to program simplification in tree-based Genetic Programming, based upon numerical relaxations of algebraic rules. We also separate proposal of simplifications from an acceptance criterion that checks the effect of proposed simplifications on the evaluation of training examples, looking several levels up the tree. We test our simplification method on three classification datasets and conclude that the success of linear regression is dataset dependent, that looking further up the tree can catch ineffective simplifications, and that CPU time can be significantly reduced while maintaining classification accuracy on unseen examples.
An Indirect Approach to the Three-dimensional Multi-pipe Routing Problem
Marcus Furuholmen, Kyrre Glette, Mats Hovin, Jim Torressen
This paper explores an indirect approach to the Three-dimensional Multi-pipe Routing problem. Variable length pipelines are built by letting a virtual robot called a turtle navigate through space, leaving pipe segments along its route. The turtle senses its environment and acts in accordance with commands received from heuristics currently under evaluation. The heuristics are evolved by a Gene Expression Programming based Learning Classifier System. The suggested approach is compared to earlier studies using a direct encoding, where command lines were evolved directly by genetic algorithms. Heuristics generating higher quality pipelines are evolved by fewer generations compared to the direct approach, however the evaluation time is longer and the search space is more complex. The best evolved heuristic is short and simple, builds modular solutions, exhibits some degree of generalization and demonstrates good scalability on test cases similar to the training case.
A Many Threaded CUDA Interpreter for Genetic Programming
W. B. Langdon
A Single Instruction Multiple Thread CUDA interpreter provides SIMD like parallel evaluation of the whole GP population of a quarter of a million reverse polish notation (RPN) expressions on graphics cards and nVidia Tesla. Using sub-machine code tree GP a sustain peak performance of 665 billion GP operations per second (10,000 speed up) and an average of 22 peta GP ops per day is reported for a single GPU card on a Boolean induction benchmark never attempted before, let alone solved.
Positional Effect of Crossover and Mutation in Grammatical Evolution
Tom Castle, Colin G. Johnson
An often-mentioned issue with Grammatical Evolution is that a small change in the genotype, through mutation or crossover, may completely change the meaning of all of the following genes. This paper analyses the crossover and mutation operations in GE, in particular examining the constructive or destructive nature of these operations when occurring at points throughout a genotype. The results we present show some strong support for the idea that events occurring at the first positions of a genotype are indeed more destructive, but also indicate that they may be the most constructive crossover and mutation points too. We also demonstrate the sensitivity of this work to the precise definition of what is constructive/destructive.
Novelty-based Fitness: An Evaluation under the Santa Fe Trail
John Doucette, Malcolm Heywood
We present an empirical analysis of the effects of incorporating novelty-based fitness (phenotypic behavioral diversity) into Genetic Programming with respect to training, test and generalization performance. Three novelty-based approaches are considered: novelty comparison against a finite archive of behavioral archetypes, novelty comparison against all previously seen behaviors, and a simple linear combination of the first method with a standard fitness measure. Performance is evaluated on the Santa Fe Trail, a well known GP benchmark selected for its deceptiveness and established generalization test procedures. Results are compared to a standard quality-based fitness function (count of food eaten). Ultimately, the quality style objective provided better overall performance, however, solutions identified under novelty based fitness functions generally provided much better test performance than their corresponding training performance. This is interpreted as representing a requirement for layered learning/ symbiosis when assuming novelty based fitness functions in order to more quickly achieve the integration of diverse behaviors into a single cohesive strategy.
GP-fileprints: File Types Detection using GP
Ahmed Kattan, Edgar Galván-López, Riccardo Poli, Michael O'Neill
We propose a novel application of Genetic Programming (GP): the identification of file types via the analysis of raw binary streams (i.e., without the use of meta data). GP evolves programs with multiple components. One component analyses statistical features extracted from the raw byte-series to divide the data into blocks. These blocks are then analysed via another component to obtain a signature for each file in a training set. These signatures are then projected onto a two-dimensional Euclidean space via two further (evolved) program components. K-means clustering is applied to group similar signatures. Each cluster is then labelled according to the dominant label for its members. Once a program that achieves good classification is evolved it can be used on unseen data without requiring any further evolution. Experimental results show that GP compares very well with established file classification algorithms (i.e., Neural Networks, Bayes Networks and J48 Decision Trees).
Evolving Genes to Balance a Pole
Miguel Nicolau, Marc Schoenauer, Wolfgang Banzhaf
We discuss how to use a Genetic Regulatory Network as an evolutionary representation to solve a typical GP reinforcement problem, the pole balancing. The network is a modified version of an Artificial Regulatory Network proposed a few years ago, and the task could be solved only by finding a proper way of connecting inputs and outputs to the network. We show that the representation is able to generalize well over the problem domain, and discuss the performance of different models of this kind.
An Analysis of the Behaviour of Mutation in Grammatical Evolution
Jonathan Byrne, James McDermott, Michael O'Neill, Anthony Brabazon
This study attempts to decompose the behaviour of mutation in Grammatical Evolution (GE). Standard GE mutation can be divided into two types of events, those that are structural in nature and those that are nodal. A structural event can alter the length of the phenotype whereas a nodal event simply alters the value at any terminal (leaf or internal node) of a derivation tree. We analyse the behaviour of standard mutation and compare it to the behaviour of its nodal and structural components. These results are then compared with standard GP operators to see how they differ. This study increases our understanding of how the search operators of an evolutionary algorithm behave.
Learning a Lot from Only a Little: Genetic Programming for Panel Segmentation on Sparse Sensory Evaluation Data
Katya Vladislavleva, Kalyan Veeramachaneni, Una-May O'Reilly
We describe a data mining framework that derives panelist information from sparse flavour survey data. One component of the framework executes genetic programming ensemble based symbolic regression. Its evolved models for each panelist provide a second component with all plausible and uncorrelated explanations of how a panelist rates flavours. The second component bootstraps the data using an ensemble selected from the evolved models, forms a probability density function for each panelist and clusters the panelists into segments that are easy to please, neutral, and hard to please.
Genetic Programming for Classification with Unbalanced Data
Urvesh Bhowan, Mengjie Zhang, Mark Johnston
Learning algorithms can suffer a performance bias when data sets only have a small number of training examples for one or more classes. In this scenario learning methods can produce the deceptive appearance of "good looking" results even when classification performance on the important minority class can be poor. This paper compares two Genetic Programming (GP) approaches for classification with unbalanced data. The first focuses on adapting the fitness function to evolve classifiers with good classification ability across both minority and majority classes. The second uses a multi-objective approach to simultaneously evolve a Pareto front (or set) of classifiers along the minority and majority class trade-off surface. Our results show that solutions with good classification ability were evolved across a range of binary classification tasks with unbalanced data.
An Analysis of Genotype-Phenotype Maps in Grammatical Evolution
David Fagan, Michael O'Neill, Edgar Galván-López, Anthony Brabazon, Sean McGarraghy
We present an analysis of the genotype-phenotype map in Grammatical Evolution (GE). The standard map adopted in GE is a depth-first expansion of the non-terminal symbols during the derivation sequence. Earlier studies have indicated that allowing the path of the expansion to be under the guidance of evolution as opposed to a deterministic process produced significant performance gains on all of the benchmark problems analysed. In this study we extend this analysis to include a breadth-first and random map, investigate additional benchmark problems, and take into consideration the implications of recent results on alternative grammar representations with this new evidence. We conclude that it is possible to improve the performance of grammar-based Genetic Programming by the manner in which a genotype-phenotype map is performed.
Improving the Generalisation Ability of Genetic Programming with Semantic Similarity based Crossover
Quang Uy Nguyen, Thi Hien Nguyen, Xuan Hoai Nguyen, Michael O'Neill
This paper examines the impact of semantic control on the ability of Genetic Programming (GP) to generalise via a semantic based crossover operator (Semantic Similarity based Crossover - SSC). The use of validation sets is also investigated for both standard crossover and SSC. All GP systems are tested on a number of real-valued symbolic regression problems. The experimental results show that while using validation sets barely improve generalisation ability of GP,by using semantics, the performance of Genetic Programming is enhanced both on training and testing data. Further recorded statistics shows that the size of the evolved solutions by using SSC are often smaller than ones obtained from GP systems that do not use semantics. This can be seen as one of the reasons for the success of SSC in improving the generalisation ability of GP.
Unsupervised Problem Decomposition using Genetic Programming
Ahmed Kattan, Alexandros Agapitos, Riccardo Poli
We propose a new framework based on Genetic Programming (GP) to automatically decompose problems into smaller and simpler tasks. The frame- work uses GP at two levels. At the top level GP evolves ways of splitting the fitness cases into subsets. At the lower level GP evolves programs that solve the fitness cases in each subset. The top level GP programs include two components. Each component receives a training case as the input. The components outputs act as coordinates to project training examples onto a 2-D Euclidean space. When an individual is evaluated, K-means clustering is applied to group the fitness cases of the problem. The number of clusters is decided based on the density of the projected samples. Each cluster then invokes an independent GP run to solve its member fitness cases. The fitness of the lower level GP individuals is evaluated as usual. The fitness of the high-level GP individuals is a combination of the fitness of the best evolved programs in each of the lower level GP runs. The proposed framework has been tested on several symbolic regression problems and has been seen to significantly outperforming standard GP systems.
Handling Different Categories of Concept Drifts in Data Streams using Distributed GP
Gianluigi Folino, Giuseppe Papuzzo
Using Genetic Programming (GP) for classifying data streams is problematic as GP is slow compared with traditional single solution techniques. However, the availability of cheaper and better-performing distributed and parallel architectures make it possible to deal with complex problems previously hardly solved owing to the large amount of time necessary. This work presents a general framework based on a distributed GP ensemble algorithm for coping with different types of concept drift for the task of classification of large data streams. The framework is able to detect changes in a very efficient way using only a detection function based on the incoming unclassified data. Thus, only if a change is detected a distributed GP algorithm is performed in order to improve classification accuracy and this limits the overhead associated with the use of a population-based method. Real world data streams may present drifts of different types. The introduced detection function, based on the self-similarity fractal dimension, permits to cope in a very short time with the main types of different drifts, as demonstrated by the first experiments performed on some artificial datasets. Furthermore, having an adequate number of resources, distributed GP can handle very frequent concept drifts.
Geometric Differential Evolution on the Space of Genetic Programs
Alberto Moraglio, Sara Silva
Geometric Differential Evolution (GDE) is a very recently introduced formal generalization of traditional Differential Evolution (DE) that can be used to derive specific GDE for both continuous and combinatorial spaces retaining the same geometric interpretation of the dynamics of the DE search across representations. In this paper, we derive formally a specific GDE for the space of genetic programs. The result is a Differential Evolution algorithm searching the space of genetic programs by acting directly on their tree representation. We present experimental results for the new algorithm.
Solution-locked Averages and Solution-time Binning in GP
Averaging data collected in multiple independent runs across generations is the standard method to study the behaviour of GP. We show that while averaging may represent with good resolution GP's behaviour in the early stages of a run, it blurs later components of the dynamics. We propose two techniques to improve the situation: solution-locked averaging and solution-time binning. Results indicate that there are significant benefits in adopting these techniques.
Using Imaginary Ensembles to Select GP Classifiers
Ulf Johansson, Rikard König, Tuve Löfström, Lars Niklasson
When predictive modeling requires comprehensible models, most data miners will use specialized techniques producing rule sets or decision trees. This study, however, shows that genetically evolved decision trees may very well outperform the more specialized techniques. The proposed approach evolves a number of decision trees and then uses one of several suggested selection strategies to pick one specific tree from that pool. The inherent inconsistency of evolution makes it possible to evolve each tree using all data, and still obtain somewhat different models. The main idea is to use these quite accurate and slightly diverse trees to form an imaginary ensemble, which is then used as a guide when selecting one specific tree. Simply put, the tree classifying the largest number of instances identically to the ensemble is chosen. In the experimentation, using 25 UCI data sets, two selection strategies obtained significantly higher accuracy than the standard rule inducer J48.
Analysis of Building Blocks with Numerical Simplification in Genetic Programming
David Kinzett, Mengjie Zhang, Mark Johnston
This paper investigates the effect of numerical simplification on building blocks during evolution in genetic programming. The building blocks considered are three level subtrees. We develop a method for encoding building blocks for the analysis. Compared with the canonical genetic programming method, numerical simplification can generate much smaller programs, use much shorter evolutionary training time and achieve comparable effectiveness performance.
Ensemble Image Classification Method Based on Genetic Image Network
Shiro Nakayama, Shinichi Shirakawa, Noriko Yata, Tomoharu Nagao
Automatic image classification methods have been required. Genetic Image Network for Image Classification (GIN-IC) is one of the methods that construct image classification algorithms automatically, and its effectiveness has already been proven. In our study, we try to improve the performance of GIN-IC with AdaBoost algorithm using GIN-IC as weak classifiers to complement with each other. We apply our proposed method to three types of image classification problems, and show the results in this paper. In our method, discrimination rates for training images and test images improved in the experiments compared with the previous method GIN-IC.
Fast Evaluation of GP Trees on GPGPU by Optimizing Hardware Scheduling
Ogier Maitre, Pierre Collet, Nicolas Lachiche
This paper shows that it is possible to use General Purpose Graphic Processing Unit cards for a fast evaluation of different Genetic Programming trees on as few as 32 fitness cases by using the hardware scheduling of NVIDIA cards. Depending on the function set, observed speedup ranges between x50 and x250 on one half of an NVidia GTX295 GPGPU card, vs a single core of an Intel Quad core Q8200.
Fine-Grained Timing using Genetic Programming
David White, John Clark, Juan Tapiador, Julio Hernandez-Castro
In previous work, we have demonstrated that it is possible to use Genetic Programming to minimise the resource consumption of software, such as its power consumption or execution time. In this paper, we investigate the extent to which Genetic Programming can be used to gain fine-grained control over software timing. We introduce the ideas behind our work, and carry out experimentation to find that Genetic Programming is indeed able to produce software with unusual and desirable timing properties, where it is not obvious how a manual approach could replicate such results. In general, we discover that Genetic Programming is most effective in controlling statistical properties of software rather than precise control over its timing for individual inputs. This control may find useful application in cryptography and embedded systems.
Bandit-Based Genetic Programming
Jean-Baptiste Hoock, Olivier Teytaud
We consider the validation of randomly generated patterns in a Monte-Carlo Tree Search program. Our bandit-based genetic programming (BGP) algorithm, with proved mathematical properties, outperformed a highly optimized handcrafted module of a well-known computer-Go program with several world records in the game of Go.
GP for Discovering Bidding Strategies for Auction Based Multi-agent Scheduling
Mohamed Bader-El-Den, Shaheen Fatima
In this paper, we present a genetic programming (GP) framework for evolving agent's binding function (GPAuc) in a resource allocation problem. The framework is tested on the exam timetabling problem (ETP). There is a set of exams, which have to be assigned to a predefined set of slots and rooms. Here, the exam time tabling system is the seller that auctions a set of slots. The exams are viewed as the bidding agents in need of slots. The problem is then to find a schedule (i.e., a slot for each exam) such that the total cost of conducting the exams as per the schedule is minimised. In order to arrive at such a schedule, we need to find the bidders' optimal bids. This is done using genetic programming. The effectiveness of GPAuc is demonstrated experimentally by comparing it with some existing benchmarks for exam timetabling.
Local Search Algorithms on Graphics Processing Units. A Case Study: the Permutation Perceptron Problem
Thé Van Luong, Nouredine Melab, El-Ghazali Talbi
Optimization problems are more and more complex and their resource requirements are ever increasing. Although metaheuristics allow to significantly reduce the computational complexity of the search process, the latter remains time-consuming for many problems in diverse domains of application. As a result, the use of GPU has been recently revealed as an efficient way to speed up the search. In this paper, we provide a new methodology to design and implement efficiently local search methods on GPU. The work has been experimented on the permuted perceptron problem and the experimental results show that the approach is very efficient especially for large problem instances.
A Real-Integer-Discrete-coded Differential Evolution Algorithm Dilip
Dillip Datta, Jose Rui Figueira
The successful application of differential evolution (DE) algorithms to various real-valued problems encourages to develop some integer-coded versions of DE for working directly with integer and discrete variables of a problem. However, in most of those works, actually a real-valued solution is just converted into a desired integer-valued solution by applying some decoding mechanisms. Only a limited number of works are found, in which attempts are made for developing an actual integer-coded DE. In this article, a novel version of DE is proposed which can work directly with real, integer and discrete variables of a problem without any conversion. Applying to two non-linear real-integer-discrete-valued engineering design problems, the proposed DE is found successful in obtaining the known best solutions of the problems.
A Study of Memetic Search with Multi-Parent Crossover for UBQP
Zhipeng Lu, Jin-Kao Hao, Fred Glover
We present a multi-parent hybrid genetic--tabu algorithm (denoted by GTA) for the Unconstrained Binary Quadratic Programming (UBQP) problem, by incorporating tabu search into the framework of genetic algorithm. In this paper, we propose a new multi-parent combination operator for generating offspring solutions. A pool updating strategy based on a quality-nd-distance criterion is used to manage the population. Experimental comparisons with leading methods for the UBQP problem on 25 large public instances demonstrate the efficacy of our proposed algorithm in terms of both solution quality and computational efficiency.
Heuristic and exact methods for the discrete (r|p)-centroid problem
Ekaterina Alekseeva, Yury Kochetov, Nina Kochetova, Alexander Plyasunov
In the discrete (r|p)-centroid problem two decision makers, a leader and a follower, compete to attract clients from a given market. The leader opens p facilities, anticipating that the follower will react to the decision by opening his own r facilities. The decision makers try to maximize their own profits. This Stackelberg game is Σ2P-hard. So, we develop a hybrid memetic algorithm for it. A probabilistic tabu search heuristic is applied for improving the offsprings. To obtain an upper bound, we reformulate the problem as a mixed integer program with an exponential number of constraints and variables. Selecting some of them, we get the desired upper bound. To find optimal solutions, we iteratively modify the subset of the constraints and variables. This approach is tested on the benchmarks from the library Discrete Location Problems. The optimal solutions are found for r=p=5, 100 clients, and 100 facilities.
On the Benefit of Sub-Optimality within the Divide-and-Evolve Scheme
Jacques Bibai, Pierre Savéant, Marc Schoenauer, Vincent Vidal
Divide-and-Evolve (DaE) is an original "memeticization" of Evolutionary Computation and Artificial Intelligence Planning. DaE optimizes either the number of actions, or the total cost of actions, or the total makespan, by generating ordered sequences of intermediate goals via artificial evolution. The evolutionary part of DaE is based on the Evolving Objects (EO) library, and can theorically use any embedded planner. However, since the introduction of this approach only one embedded planner has been used: the temporal optimal planner CPT. In this paper, we built a new version of DaE based on time-based Atom Choice and we embarked another planner (the sub-optimal planner YAHSP in order to test the technical robustness of the approach and to compare the impact of using an optimal planner versus using a sub-optimal planner for all kinds of planning problems.
Characterizing Fault-tolerance of Genetic Algorithms in Desktop Grid Systems
Daniel Lombraña González, Juan Luís Jiménez, Francisco Fernández de Vega, Juan Julián Merelo Guervós
This paper presents a study of the fault-tolerant nature of Genetic Algorithms (GAs) on a real-world Desktop Grid System, without implementing any kind of fault-tolerance mechanism. The aim is to extend to parallel GAs previous works tackling fault-tolerance characterization in Genetic Programming. The results show that GAs are able to achieve a similar quality in results in comparison with a failure-free system in three of the six scenarios under study despite the system degradation. Additionally, we show that a small increase on the initial population size is a successful method to provide resilience to system failures in five of the scenarios. Such results suggest that Parallel GAs are inherently and naturally fault-tolerant.
Geometric Generalization of the Nelder-Mead Algorithm
Alberto Moraglio, Colin Johnson
The Nelder-Mead Algorithm (NMA) is an almost half-century old method for numerical optimization, which is used in many applications. This algorithm fits well the evolutionary framework and it is a close relative of Particle Swarm Optimization (PSO) and Differential Evolution (DE). Geometric Particle Swarm Optimization (GPSO) and Geometric Differential Evolution (GDE) are recently introduced formal generalization of traditional PSO and DE that apply naturally to both continuous and combinatorial spaces. In this paper, we generalize NMA to combinatorial search spaces by naturally extending its geometric interpretation to these spaces, analogously as what was done for the traditional PSO and DE algorithms, obtaining the Geometric Nelder-Mead Algorithm (GNMA). Then we formally derive the specific GNMA for the Hamming space associated with binary strings and present experimental results on a standard benchmark of problems.
The Office-Space-Allocation Problem in Strongly Hierarchized Organizations
Rui Lopes, Daniela Girimonte
The Office-space-allocation (OSA) problem will be introduced for strongly hierarchized organizations. In several organizations the relation between the entities is strongly hierarchized, affecting the design and handling of constraints and algorithms used to solve the problem. Moreover there is also an increase in the constraint number when compared to the common test instances. Several well known meta-heuristics were used, new constraints developed, and some variations to the local search algorithms were studied. This article describes the work done and its application to a particular case study, the European Space Research and Technology Center (ESTEC).
Evolutionary Approaches to the Three-dimensional Multi-pipe Routing Problem: A Comparative Study using Direct Encodings
Marcus Furuholmen, Kyrre Glette, Mats Hovin, Jim Torressen
In this study, three Genetic Algorithms (GAs) are applied to the Three-dimensional Multi-pipe Routing problem. A Standard GA, an Incremental GA, and a Coevolutionary GA are compared. Variable length pipelines are built by letting a virtual robot move in space according to evolved, fixed length command lines and allocate pipe segments along its route. A relative and an absolute encoding of the command lines are compared. Experiments on three proposed benchmark problems show that the GAs taking advantage of the natural problem decomposition; Coevolutionary GA, and Incremental GA outperform Standard GA, and that the relative encoding works better than the absolute encoding. The methods, the results, and the relevant parameter settings are discussed.
A Memetic Algorithm for Workforce Distribution in Dynamic Multi-Skill Call Centres
David Millan-Ruiz, J. Ignacio Hidalgo
In this paper, we describe a novel approach for workforce distribution in dynamic multi-skill call centres. Dynamic multi-skill call centres require quick adaptations to a changing environment that only fast greedy heuristics can handle. The use of memetic algorithms, which are more complex than ad-hoc heuristics, can guide us to more accurate solutions. In order to apply memetic algorithms to such a dynamic environment, we propose a reformulation of the traditional problem, which combines predictions of future situations with a precise search mechanism, by enlarging the time-frame considered. Concretely, we propose a neural network for predicting call arrivals and the number of available agents, and a memetic algorithm to carry out the assignment of incoming calls to agents, which outperforms classical approaches to this dynamic environment. We also test our method on a real-world environment within a large multinational telephone operator.
A Genetic Algorithm to Minimize Chromatic Entropy
Greg Durrett, Muriel Medard, Una-May O'Reilly
We present an algorithmic approach to solving the problem of chromatic entropy, a combinatorial optimization problem related to graph coloring. This problem is a component in algorithms for optimizing data compression when computing a function of two correlated sources at a receiver. Our genetic algorithm for minimizing chromatic entropy uses an order-based genome inspired by graph coloring genetic algorithms, as well as some problem-specific heuristics. It performs consistently well on synthetic instances, and for an expositional set of functional compression problems, the GA routinely finds a compression scheme that is 20-30% more efficient than that given by a reference compression algorithm.
Efficient Cycle Search for the Minimum Routing Cost Spanning Tree Problem
Steffen Wolf, Peter Merz
The Minimum Routing Cost Spanning Tree problem is an optimization problem that strongly benefits from local search. Well-established approaches are the Ahuja-Murty local search and a weaker subtree search used in an evolutionary framework. We present a new and efficient cycle search that has a lower time complexity but achieves the same results as the strong but slow Ahuja-Murty local search. Moreover, we show that an evolutionary framework using this cycle search outperforms previous approaches regarding both quality and time. Our approach is able to find (near-)optimal solutions in all runs for all tested instances.
A Tabu Search Heuristic for Point Coverage, Sink Location and Data Routing in Wireless Sensor Networks
Evren Guney, I.Kuban Altinel, Necati Aras, Cem Ersoy
The point coverage, sink location, and data routing problems are considered in an integrated way and two new mixed-integer programming formulations are proposed. As these models are difficult to solve, a nested solution procedure is proposed. The best sensor locations are sought by tabu search in the upper level. For the fixed sensor locations, the remaining problem of determining sink locations and data routes are solved efficiently in the lower level. According to the experimental results performed on a number of test instances, the performance of the nested solution approach is quite satisfactory, and the proposed heuristic method brings considerable improvements over a two-stage solution approach.
Fitness Distance Correlation and Search Space Analysis for Permutation Based Problems
The fitness distance correlation (FDC) as a measure for problem difficulty was first introduced by Forrest and Jones. It was applied to many binary coded problems. This method is now applied to permutation based problems. As demanded by Schiavinotto and Stützle, the distance in a search space is calculated by regarding the steps of the (neighborhood) operator. In this paper the five most common operators for permutations are analyzed on symmetric and asymmetric TSP instances. In addition a local quality measure, the point quality (PQ) is proposed as a supplement to the global FDC. With this local measure more characteristics and differences can be investigated. Some experimental results are illustrating these concepts.
DSA Approach for University Course Timetabling
Salwani Abdullah, Khalid Shaker, Barry McCollum, Paul McMullan
Course timetabling (CTTP) within Universities is a complex problem wherein the problem size can become huge due to limited resources (e.g. amount of rooms, their capacities and number availability of lecturers) and the requirements for these resources. The university course timetabling problem involves assigning a given number of events into a limited number of timeslots and rooms under a given set of constraints; the objective is to satisfy the hard constraints (essential requirements) and minimize the violation of soft constraints (desirable requirements). In this study we apply a novel Dual-sequence Simulated Annealing (DSA) algorithm, an extension to the standard SA algorithm, to the problem. We use a Round Robin Scheduling Algorithm (RR) as a new strategy to control the application of neighbourhood structures. The performance of our approach is tested over eleven benchmark datasets (representing one large, five medium and five small problems). Competitive results have been obtained when compared with other state-of-the-art techniques.
Evolutionary Algorithm Guided by Preferences Elicited According to the ELECTRE TRI Method Principles
Eunice Oliveira, Carlos Henggeller Antunes
The resolution of a multi-objective optimization problem involves not just a search and computation phase, capable of providing a representative sample of the Pareto-optimal front, but also a decision support process to aid the Decision Maker (DM) to progress in the learning of the trade-offs at stake in different regions of the search space. This is accomplished by integrating in the search process the DM’s preferences to guide the search and limit both the cognitive effort, in assessing Pareto-optimal solutions with distinct characteristics, and the computational effort, by reducing the scope of the search according to the preferences expressed by the DM. The introduction of meaningful preference expression parameters used in the ELECTRE TRI method for sorting problems in the framework of an evolutionary algorithm is proposed. Illustrative results in an operational planning problem in electricity networks are reported.
Multilevel Variable Neighborhood Search for Periodic Routing Problems
Sandro Pirkwieser, Günther R. Raidl
In this work we present the extension of a variable neighborhood search (VNS) with the multilevel refinement strategy for periodic routing problems. The underlying VNS was recently proposed and performs already well on these problems. We apply a path based coarsening scheme by building fixed (route) segments of customers accounting for the periodicity. Starting at the coarsest level the problem is iteratively refined until the original problem is reached again. This refinement is smoothly integrated into the VNS. Further a suitable solution-based recoarsening is proposed. Results on available benchmark test data as well as on newly generated larger instances show the advantage of the multilevel VNS compared to the standard VNS, yielding better results in usually less CPU time. This new approach is especially appealing for large instances.
Iterated Local Search with Path Relinking for Solving Parallel Machines Scheduling Problem with Resource-assignable Sequence Dependent Setup Times
Edmar Hell Kampke, José Elias Claudio Arroyo, André Gustavo Santos
This paper addresses the unrelated parallel machine problem with machine and job sequence dependent setup. In this problem, the amount of the setup time does not only depend on the machine and job sequence, but also on a number of resources assigned, which can vary between a minimum and a maximum. The goal is to find a schedule that minimizes the linear combination of the total resources assigned and the total completion time. The problem is NP-hard in the strong sense. The NP-hardness of the problem motivates us to develop a new Iterated Local Search (ILS) heuristic to obtain near-optimal solutions. The heuristic uses an intensification strategy based on the Path Relinking technique which generates new solutions by exploring trajectories that connect high-quality solutions. Computational tests are carried out on a set of benchmark instances and the results obtained by the proposed ILS improve the best known results from the literature by a significant margin.
A New Primal-dual Genetic Algorithm. Case Study for the Winner Determination Problem
Madalina Raschip, Cornelius Croitoru
This paper presents a new evolutionary computing strategy which uses the linear programming duality information to help the search for optimum solutions of hard optimization problems. The algorithm is restarted several times when it is stuck into a local optima. At each restart, the appropriate dual space is constructed. A new population of primal individuals is generated using the information from dual solutions and is considered for next iterations. The pursued goal was not to find the best algorithm for solving winner determination problem, but to prove the method's viability using the problem as a case study. Experiments on realistic instances were performed.
Enhancing Genetic Algorithms by a Trie-Based Complete Solution Archive
Günther Raidl, Bin Hu
Genetic algorithms (GAs) share a common weakness with most other metaheuristics: Candidate solutions are in general revisited multiple times, lowering diversity and wasting precious CPU time. We propose a complete solution archive based on a special binary trie structure for GAs with binary representations that efficiently stores all evaluated solutions during the heuristic search. Solutions that would later be revisited are detected and effectively transformed into similar yet unconsidered candidate solutions. The archive’s relevant insert, find, and transform operations all run in time O(l) where l is the length of the binary solution representation. From a theoretical point of view, the archive turns the GA into a complete algorithm with a clear termination condition and bounded run time. Computational results are presented for Royal Road functions and NK landscapes, indicating the practical advantages.
Guided Ejection Search for the Pickup and Delivery Problem with Time Windows
Yuichi Nagata, Shigenobu Kobayashi
This paper presents an efficient route minimization heuristic for the pickup and delivery problem with time windows (PDPTW) based on guided ejection search (GES). GES is a recently proposed metaheuristc framework and was first applied to the vehicle routing problem with time windows. The existence of the pickup and delivery constraint makes the feasible solution space tightly constrained and then makes the design of effective metaheuristics more difficult. We demonstrate that GES can be successfully applied to such an complicated problem. Experimental results on the Li and Lim's benchmarks demonstrate that the proposed GES algorithm outperforms existing algorithms and is able to improve 105 best-known solutions out of 298 instances.
Bicriteria Scheduling Problem in Two-Machine Flowshop Using Simulated Annealing
Mohammad Mesgarpour, Nureddin Kirkavak, Hakan Ozaktas
Real life scheduling problems require the decision maker to consider a number of criteria before arriving at any decision. The trade-offs involved in considering several different criteria provide useful insights for the decision maker. Surprisingly, research in the field of multi-objective scheduling has been quite limited when compared to research in single criterion scheduling. The subject of this paper is the bicriteria scheduling problem in a two-machine flowshop. The objective is to find a job sequence that minimizes sum of weighted total flowtime and total tardiness. Based on the problem characteristics, a Simulated Annealing algorithm is developed. The proposed meta-heuristic is compared with the branch and bound enumeration algorithm of the integer programming model as well as a modified version of the well-known NEH algorithm. During these evaluations, the experimental design approach and careful statistical analysis have been used to validate the effectiveness of the simulated annealing approach.
Enhancing a Tabu Algorithm for Approximate Graph Matching by using Similarity Measures
Segla Kpodjedo, Philippe Galinier, Giulio Antoniol
In this paper, we investigate heuristics in order to solve the Approximated Matching Problem (AGM). We propose a tabu search algorithm which exploits a simple neighborhood. The algorithm is initialized by a greedy procedure which uses a measure of similarity between the vertices of the two graphs. The algorithm is tested on a large collection of graphs of various sizes (from 300 vertices and up to 3000 vertices) and densities. Computing times range from less than 1 second up to a few minutes. The algorithm obtains consistently very good results on labeled graphs, while the results are not as good with unlabeled graphs. The results obtained by the tabu algorithm alone (without the greedy procedure) were very poor, illustrating the importance of using vertex similarity during the early steps of the search process.
Ant Colony Optimization for Tree Decompositions
Thomas Hammerl, Nysret Musliu
Instances of constraint satisfaction problems can be solved efficiently if they are representable as a tree decomposition of small width. Unfortunately, the task of finding a decomposition of minimum width is NP-complete itself. Therefore, several heuristic and metaheuristic methods have been developed for this problem. In this paper we investigate application of different variants of Ant Colony Optimization algorithms for the generation of tree decompositions. Furthermore, we extend these implementations with two local search methods and we compare two heuristics that guide the ACO algorithms. Our computational results for selected instances of the DIMACS graph coloring library show that the ACO metaheuristic gives results comparable to those of other decomposition methods such as branch and bound and tabu search for many problem instances. One of the proposed algorithms was even able to improve the best known upper bound for one problem instance. Nonetheless, for some larger problems the best existing methods outperform our algorithms.
Identification of Individualized Feature Combinations for Survival Prediction in Breast Cancer: A Comparison of Machine Learning Techniques
Leonardo Vanneschi, Antonella Farinaccio, Mario Giacobini, Marco Antoniotti, Giancarlo Mauri, Paolo Provero
The ability to accurately classify cancer patients into risk classes, i.e. to predict the outcome of the pathology on an individual basis, is a key ingredient in making therapeutic decisions. In recent years gene expression data have been successfully used to complement the clinical and histological criteria traditionally used in such prediction. Many "gene expression signatures" have been developed, i.e. sets of genes whose expression values in a tumor can be used to predict the outcome of the pathology. Here we investigate the use of several machine learning techniques to classify breast cancer patients using one of such signatures, the well established 70-gene signature. We show that Genetic Programming performs significantly better than Support Vector Machines, Multilayered Perceptron and Random Forest in classifying patients from the NKI breast cancer dataset, and slightly better than the scoring-based method originally proposed by the authors of the seventy-gene signature. Furthermore, Genetic Programming is able to perform an automatic feature selection. Since the performance of Genetic Programming is likely to be improvable compared to the out-of-the-box approach used here, and given the biological insight potentially provided by the Genetic Programming solutions, we conclude that Genetic Programming methods are worth further investigation as a tool for cancer patient classification based on gene expression data.
A Model Free Method to Generate Human Genetics Datasets with Complex Gene-Disease Relationships
Casey Greene, Daniel Himmelstein, Jason Moore
A goal of human genetics is to discover genetic factors that influence individuals' susceptibility to common diseases. Most common diseases are thought to result from the joint failure of two or more interacting components instead of single component failures. This greatly complicates both the task of selecting informative genetic variations and the task of modeling interactions between them. We and others have previously developed algorithms to detect and model the relationships between these genetic factors and disease. Previously these methods have been evaluated with datasets simulated according to pre-defined genetic models. Here we develop and evaluate a model free evolution strategy to generate datasets which display a complex relationship between individual genotype and disease susceptibility. We show that this model free approach is capable of generating a diverse array of datasets with distinct gene-disease relationships for an arbitrary interaction order and sample size. We specifically generate six-hundred pareto fronts; one for each independent run of our algorithm. In each run the predictiveness of single genetic variation and pairs of genetic variations have been minimized, while the predictiveness of third, fourth, or fifth order combinations is maximized. This method and the resulting datasets will allow the capabilities of novel methods to be tested without pre-specified genetic models. This could improve our ability to evaluate which methods will succeed on human genetics problems where the model is not known in advance. We further make freely available to the community the entire pareto-optimal front of datasets from each run so that novel methods may be rigorously evaluated. These 56,600 datasets are available from http://discovery.dartmouth.edu/model_free_data/.
Correlation-Based Scatter Search for Discovering Biclusters from Gene Expression Data
Juan A. Nepomuceno, Alicia Troncoso-Lora, Jesús S. Aguilar-Ruiz
Scatter Search is an evolutionary method that combines existing solutions to create new offspring as the well--known genetic algorithms. This paper presents a Scatter Search with the aim of finding biclusters from gene expression data. However, biclusters with certain patterns are more interesting from a biological point of view. Therefore, the proposed Scatter Search uses a measure based on linear correlations among genes to evaluate the quality of biclusters. As it is usual in Scatter Search methodology an improvement method is included which avoids to find biclusters with negatively correlated genes. Experimental results from yeast cell cycle and human B-cell lymphoma datasets are reported showing a remarkable performance of the proposed method and measure.ted showing a remarkable performance of the proposed method and measure.
Variable Genetic Operator Search for the Molecular Docking Problem
Salma Mesmoudi, Jorge Tavares, Laetitia Jourdan, El-Ghazali Talbi
The aim of this work is to present a new hybrid algorithm for the Molecular Docking problem: Variable Genetic Operator Search (VGOS). The proposed method combines an Evolutionary Algorithm with Variable Neighborhood Search. Experimental results show that the algorithm is able to achieve good results, in terms of energy optimization and RMSD values for several molecules when compared with previous approaches. In addition, when hybridized with the L-BFGS local search method it attains very competitive results.
Role of Centrality in Network-Based Prioritization of Disease Genes
Sinan Erten, Mehmet Koyuturk
High-throughput molecular interaction data have been used effectively to prioritize candidate genes that are linked to a disease, based on the notion that the products of genes associated with similar diseases are likely to interact with each other heavily in a network of protein-protein interactions (PPIs). An important challenge for these applications, however, is the incomplete and noisy nature of PPI data. Random walk and network propagation based methods alleviate these problems to a certain extent, by considering indirect interactions and multiplicity of paths. However, as we demonstrate in this paper, such methods are likely to favor highly connected genes, making prioritization sensitive to the skewed degree distribution of PPI networks, as well as ascertainment bias in available interaction and disease association data. Here, we propose several statistical correction schemes that aim to account for the degree distribution of known disease and candidate genes. We show that, while the proposed schemes are very effective in detecting loosely connected disease genes that are missed by existing approaches, this improvement might come at the price of more false negatives for highly connected genes. Motivated by these results, we develop uniform prioritization methods that effectively integrate existing methods with the proposed statistical correction schemes. Comprehensive experimental results on the Online Mendelian Inheritance in Man (OMIM) database show that the resulting hybrid schemes outperform existing methods in prioritizing candidate disease genes.
Grammatical Evolution of Neural Networks for Discovering Epistasis among Quantitative Trait Loci
Stephen D. Turner, Scott M. Dudek, Marylyn D. Ritchie
Growing interest and burgeoning technology for discovering genetic mechanisms that influence disease processes have ushered in a flood of genetic association studies over the last decade, yet little heritability in highly studied complex traits has been explained by genetic variation. Non-additive gene-gene interactions, which are not often explored, are thought to be one source of this missing heritability. Here we present our assessment of the performance of grammatical evolution to evolve neural networks (GENN) for discovering gene-gene interactions which contribute to a quantitative heritable trait. We present several modifications to the GENN procedure which result in modest improvements in performance.
Improving Multi-Relief for Detecting Specificity Residues from Multiple Sequence Alignments
A challenging problem in bioinformatics is the detection of residues that account for protein function specificity, not only in order to gain deeper insight in the nature of functional specificity but also to guide protein engineering experiments aimed at switching the specificity of an enzyme, regulator or transporter. The majority of the state-of-the art algorithms for this task use multiple sequence alignments (MSA's) to identify residue positions conserved within- and divergent between- protein subfamilies. In this study, we focus on a recent method based on this approach called multi-RELIEF. We analyze and modify the two core parts of the method in order to improve its predictive performance. A parametric generalization of the popular RELIEF machine learning algorithm for weighting residues is introduced and incorporated in multi-RELIEF. The ensemble criterion of multi-RELIEF for merging the weights of multiple runs is simplified. Finally, the method used by multi-RELIEF for exploiting tertiary structure information is modified by incorporating prior information describing the confidence of the original scores assigned to residues. Extensive computational experiments on six real-life datasets show improvement of both robustness and detection capability of the new multi-RELIEF over the original method.
Parallel Multi-objective Approaches for Inferring Phylogenies
Waldo Cancino, Laetitia Jourdan, El-Ghazali Talbi, Alexandre Delbemv
The inference of the phylogenetic tree that best express the evolutionary relationships concerning data is one of the central problem of bioinformatics. Several single optimality criterion have been proposed for the phylogenetic reconstruction problem. However, different criteria may lead to conflicting phylogenies. In this scenario, a multi-objective approach can be useful since it could produce a set of optimal trees according to multiple criteria. PhyloMOEA is a multi objective evolutionary approach applied to phylogenetic inference using maximum parsimony and maximum likelihood criteria. On the other hand, the computational power required for phylogenetic inference of large alignments easily surpasses the capabilities of single machines. In this context, the parallelization of the heuristic reconstruction methods can not only help to reduce the inference execution time but also improve the results quality and search robustness. On the other hand, The PhyloMOEA parallelization represents the next development step in order to reduce the execution time. In this paper, we present the PhyloMOEA parallel version developed using the ParadisEO framework. The experiments conducted show significant speedup in the execution time for the employed datasets.
Top-Down Induction of Phylogenetic Trees
Celine Vens, Eduardo Costa, Hendrik Blockeel
We propose a novel distance based method for phylogenetic tree reconstruction. Our method is based on a conceptual clustering method that extends the well-known decision tree learning approach. It starts from a single cluster and repeatedly splits it into subclusters until all sequences form a different cluster. We assume that a split can be described by referring to particular polymorphic locations, which makes such a divisive method computationally feasible. To define the best split, we use a criterion that is close to Neighbor Joining's optimization criterion, namely, minimizing total branch length. A thorough experimental evaluation shows that our method yields phylogenetic trees with an accuracy comparable to that of existing methods. Moreover, it has a number of important advantages. First, by listing the polymorphic locations at the internal nodes, it provides an explanation for the resulting tree topology. Second, the top-down tree growing process can be stopped before a complete tree is generated, yielding an efficient gene or protein subfamily identification approach. Third, the resulting trees can be used as classification trees to classify new sequences into subfamilies.
A Local Search Approach for Transmembrane Segment and Signal Peptide Discrimination
Sami Laroum, Dominique Tessier, Béatrice Duval, Jin-Kao Hao
Discriminating between secreted and membrane proteins is a challenging task. This is particularly true for discriminating between transmembrane segments and signal peptides because they have common biochemical properties. In this paper, we introduce a new predictive method called LSTranslocon (Local Search Translocon) based on a Local Search methodology. The method takes advantage of the latest knowledge in the field to model the biological behaviors of proteins with the aim of ensuring good prediction. The LS Prediction approach is assessed on a constructed data set from Swiss-Prot database and compared with one of the best methods from the literature.
An Evolutionary Model based on Hill-Climbing Search Operators for Protein Structure Prediction
Camelia Chira, Dragos Horvath, D Dumitrescu
The prediction of a minimum-energy protein structure from its amino-acid sequence represents one of the most important and challenging problems in computational biology. A new evolutionary model based on hill-climbing genetic operators is proposed to address the hydrophobic - polar model of the protein folding problem. The introduced model ensures an efficient exploration of the search space by implementing a problem-specific crossover operator and enforcing an explicit diversification stage during the evolution. The mutation operator engaged in the proposed model refers to the pull-move operation by which a single residue is moved diagonally causing the potential transition of connecting residues in the same direction in order to maintain a valid protein configuration. Both crossover and mutation are applied using a steepest-ascent hill-climbing approach. The resulting evolutionary algorithm with hill-climbing operators is successfully applied to the protein structure prediction problem for a set of difficult bidimensional instances from lattice models.
A Replica Exchange Monte Carlo Algorithm for the Optimization of Secondary Structure Packing in Proteins
Leonidas Kapsokalivas, Kathleen Steinhofel
We approach the problem of packing secondary structure fragments into low energy conformations with a local search optimization algorithm. Protein conformations are represented in a simplified off-lattice model. In that model we propose a move set that transforms a protein conformation into another in order to enable the use of local search algorithms for protein folding simulations and conformational search. The energy minimization problem behind protein folding is adapted to our model. Special care has been taken so that amino acids in a conformation do not overlap. The constraint of producing an overlap-free conformation can be seen as a objective that conflicts with the energy minimization. Thus, we approach protein folding as a two-objective problem. We employ a replica exchange Monte Carlo algorithm in combination to the proposed move set. The algorithm deals with the energy minimization problem while maintaining overlap-free conformations. Initial conformations incorporate experimentally determined secondary structure, which is preserved throughout the execution of local search. Our method produced conformations with a minimum RMSD of alpha-carbon atoms in the range of 4.71∞A(Angstroms) to 6.82∞A(Angstroms) for all benchmarks apart from one for which the value was 9.68∞A(Angstroms).
Using Probabilistic Dependencies Improves the Search of Conductance-based Compartmental Neuron Models
Roberto Santana, Concha Bielza, Pedro Larrañaga
Conductance-based compartmental neuron models are traditionally used to investigate the electrophysiological properties of neurons. These models require a number of parameters to be adjusted to biological experimental data and this question can be posed as an optimization problem. In this paper we investigate the behavior of different estimation of distribution algorithms (EDAs) for this problem. We focus on studying the influence that the interactions between the neuron model conductances have in the complexity of the optimization problem. We support evidence that the use of these interactions during the optimization process can improve the EDA behavior.
Grammatical Evolution Decision Trees for Detecting Gene-Gene Interactions
Sushamna Deodhar, Alison Motsinger-Reif
A fundamental goal of human genetics is the discovery of polymorphisms that predict common, complex diseases. It is hypothesized that complex diseases are due to a myriad of factors including environmental exposures and complex genetic risk models, including gene-gene interactions. Such interactive models present an important analytical challenge, requiring that methods perform both variable selection and statistical modeling to generate testable genetic model hypotheses. Decision trees are a highly successful, easily interpretable data-mining method that are typically optimized with a hierarchical model building approach, which limits their potential to identify interactive effects. To overcome this limitation, we utilize evolutionary computation, specifically grammatical evolution, to build decision trees to detect and model gene-gene interactions. Currently, we introduce the Grammatical Evolution Decision Trees (GEDT) method, and demonstrate that GEDT has power to detect interactive models in a range of simulated data, revealing GEDT to be a promising new approach for human genetics.
Finding Gapped Motifs by A Novel Evolutionary Algorithm
Chengwei Lei, Jianhua Ruan
Identifying approximately repeated patterns, or motifs, in biological sequences from a set of co-regulated genes is an important step towards deciphering the complex gene regulatory networks and understanding gene functions. In this work, we develop a novel motif finding algorithm based on a population-based stochastic optimization technique called Particle Swarm Optimization (PSO), which has been shown to be effective in optimizing difficult multidimensional problems in continuous domains. We propose a modification of the standard PSO algorithm to handle discrete values, such as characters in DNA sequences. Our algorithm also provides several unique features. First, we use both consensus and position-specific weight matrix representations in our algorithm, taking advantage of the efficiency of the former and the accuracy of the later. Furthermore, many real motifs contain gaps, but the existing methods usually ignore them or assume a user know their exact locations and lengths, which is usually impractical for real applications. In comparison, our method models gaps explicitly, and provides an easy solution to find gapped motifs without any detailed knowledge of gaps. Our method also allows some input sequences to contain zero or multiple binding sites. Experimental results on synthetic challenge problems as well as real biological sequences show that our method is both more efficient and more accurate than several existing algorithms, especially when gaps are present in the motifs.
The Informative Extremes: Using Both Nearest and Farthest Individuals Can Improve Relief Algorithms in the Domain of Human Genetics
Casey Greene, Daniel Himmelstein, Jeff Kiralis, Jason Moore
A primary goal of human genetics is the discovery of genetic factors that influence individual susceptibility to common human diseases. This problem is difficult because common diseases are likely the result of joint failure of two or more interacting components instead of single component failures. Efficient algorithms that can detect interacting attributes are needed. The Relief family of machine learning algorithms, which use nearest neighbors to weight attributes, are a promising approach. Recently an improved Relief algorithm called Spatially Uniform ReliefF (SURF) has been developed that significantly increases the ability of these algorithms to detect interacting attributes. Here we introduce an algorithm called SURF* which uses distant instances along with the usual nearby ones to weight attributes. The weighting depends on whether the instances are are nearby or distant. We show this new algorithm significantly outperforms both ReliefF and SURF for genetic analysis in the presence of attribute interactions. We make SURF* freely available in the open source MDR software package. MDR is a cross-platform Java application which features a user friendly graphical interface.
Artificial Immune Systems for Epistasis Analysis in Human Genetics
Nadia Penrod, Casey Greene, Delaney Granizo-MacKenzie, Jason Moore
Modern genotyping techniques have allowed the field of human genetics to generate vast amounts of data, but analysis methodologies have not been able to keep pace with this increase. In order to allow personal genomics to play a vital role in modern health care, analysis methods capable of discovering high order interactions that contribute to an individual's risk of disease must be developed. An artificial immune system (AIS) is a method which maps well to this problem and has a number of appealing properties. By considering many attributes simultaneously, it may be able to effectively and efficiently detect epistasis, that is non-additive gene-gene interactions. This situation of interacting genes is currently very difficult to detect without biological insight or statistical heuristics. Even with these approaches, at low heritability (i.e.\ where there is only a small genetic signal), these approaches have trouble distinguishing genetic signal from noise. The AIS also has a compact solution representation which can be rapidly evaluated. Finally the AIS approach, by iteratively developing an antibody which ignores irrelevant genotypes, may be better able to differentiate signal from noise than machine learning approaches like ReliefF which struggle at small heritabilities. Here we develop a basic AIS and evaluate it on very low heritability datasets. We find that the basic AIS is not robust to parameter settings but that, at some parameter settings, it performs very effectively. We use the settings where the strategy succeeds to suggest a path towards a robust AIS for human genetics. Developing an AIS which succeeds across many parameter settings will be critical to prepare this method for widespread use.
Metaheuristics for Strain Optimization using Transcriptional Information Enriched Metabolic Models
Paulo Vilaça, Paulo Maia, Isabel Rocha, Miguel Rocha
The identification of a set of genetic manipulations that result in a microbial strain with improved production capabilities of a metabolite with industrial interest is a big challenge in Metabolic Engineering. Evolutionary Algorithms and Simulated Annealing have been used in this task to identify sets of reaction deletions, towards the maximization of a desired objective function. To simulate the cell phenotype for each mutant strain, the Flux Balance Analysis approach is used, assuming organisms have maximized their growth along evolution. In this work, transcriptional information is added to the models using gene-reaction rules. The aim is to find the (near-)optimal set of gene knockouts necessary to reach a given productivity goal. The results obtained are compared with the ones reached using the deletion of reactions, showing that we obtain solutions with similar quality levels and number of knockouts, but biologically more feasible. Indeed, we show that several of the previous solutions are not viable using the provided rules.
Using Rotation Forest for Protein Fold Prediction Problem: An Empirical Study
Abdollah Dehzangi, Somnuk Phon-Amnuaisuk, Mahmoud Manafi, Soodabeh Safa
Recent advancement in the pattern recognition field has driven many classification algorithms being implemented to tackle protein fold prediction problem. In this paper, a newly introduced method called Rotation Forest for building ensemble of classifiers based on bootstrap sampling and feature extraction is implemented and applied to challenge this problem. The Rotation Forest is a straight forward extension of bagging algorithms which aims to promote diversity within the ensemble through feature extraction by using Principle Component Analysis (PCA). We compare the performance of the employed method with other Meta classifiers that are based on boosting and bagging algorithms, such as: AdaBoost.M1, LogitBoost, Bagging and Random Forest. Experimental results show that the Rotation Forest enhanced the protein folding prediction accuracy better than the other applied Meta classifiers, as well as the previous works found in the literature.
Towards Automatic Detecting of Overlapping Genes - Clustered BLAST Analysis of Viral Genomes
Klaus Neuhaus, Daniela Oelke, David Fürst, Siegfried Scherer, Daniel A. Keim
Overlapping genes (encoded on the same DNA strand but in different frames) are thought to be rare and, therefore, were largely neglected in the past. In a test set of 800 viruses we found more than 350 potential overlapping open reading frames of >500 bp which generate BLAST hits, indicating a possible biological function. Interestingly, five overlaps with more than 2000 bp were found, the largest may even contain triple overlaps. In order to perform the vast amount of BLAST searches required to test all detected open reading frames, we compared two clustering strategies (BLASTCLUST and k-means) and queried the database with one representative only. Our results show that this approach achieves a significant speed-up while retaining a high quality of the results (>99% precision compared to single queries) for both clustering methods. Future wet lab experiments are needed to show whether the detected overlapping reading frames are biologically functional.
Investigating Populational Evolutionary Algorithms to Add Vertical Meaning in Phylogenetic Trees
Francesco Cerutti, Luigi Bertolotti, Tony Goldberg, Mario Giacobini
In a typical "left-to-right" phylogenetic tree, the vertical order of taxa is meaningless, and the degree of similarity between taxa is only reflected by the branch path between them. We applied a Evolutionary Algorithm (EA) to improve the graphical representation of phylogenies, adding interpretability to the vertical order of taxa. We investigated the influence of different populations in the heuristic method to evaluate their influence on a (lambda + mu) -EA. In our example, the order of taxa linked to polytomic nodes is optimized using data from genetic distance matrices. However the vertical order of taxa on a phylogenetic tree can also be used to represent non-genetic features of interest.
ABC Supported Handoff Decision Scheme Based on Population Migration
Xingwei Wang, Hui Cheng, Peiyu Qin, Min Huang, Lei Guo
Abstract. In this paper, a handoff decision scheme is proposed with always best connected (ABC) supported. It comprehensively considers the status of the access network, the application QoS requirement, the preference of the user over the coding system of the access network, the preference of the user over the access network provider, the current speed of the terminal, and the residual electric quantity of the terminal. Based on the population migration algorithm (PMA) and gaming, it aims to find the Pareto-optimal solution under Nash equilibrium between the user utility and the network service provider utility. The simulation experiments demonstrate that the proposed scheme is effective.
TCP Modification Robust to Packet Reordering in Ant Routing Networks
Malgorzata Gadomska-Kudelska, Andrzej Pacut
In this paper a modification of the TCP protocol is proposed that improves its robustness to packet reordering in networks controlled by ant routing algorithms. In our approach the TCP sender builds models of packet end-to-end delay and every time a DUPACK is received it utilizes these models to calculate the probability that the packet will still arrive at the receiver. Based on this probability the decision is made whether or not to retransmit the packet. The advantages of our approach are proved in a set of simulations.
Using Code Bloat to Obfuscate Evolved Network Traffic
Patrick LaRoche, Nur Zincir-Heywood, Malcolm Heywood
In this work, we investigate the ability of genetic programming techniques to evolve valid network patterns, while avoiding detectability by obfuscating the intent of the traffic. In order to validate our system's capabilities, we choose to evolve a port scan attack while running the packets through an Intrusion Detection System (IDS). In turn, the evolutionary process uses feedback such that it minimizes the alarms raised while port scanning across a network range. Results build off of previous work allow us to further analyze and understand what the role of introns, code bloat, play in the systems ability to reduce the detectability of it malicious behaviour.
Particle Swarm Optimization for Coverage Maximization and Energy Conservation in Wireless Sensor Networks
Nor Azlina Ab. Aziz, Ammar Mohemmed, Mengjie Zhang
Two key issues in mobile Wireless Sensors Network (WSN) are coverage and energy conservation. A high coverage rate ensures a high quality of service of the WSN. Energy conservation prolongs the network lifetime. These two issues are correlated, as coverage improvement in mobile WSN requires the sensors to move, which is one of the main factors of energy consumption. Therefore coverage optimization should take into consideration the available energy. Considering the sensors limited energy, this paper proposes a PSO based algorithm for maximizing the coverage subject to a constraint on the maximum distance any sensor can move. The simulation results show that the proposed algorithm achieves good coverage and significantly reduces the energy consumption for sensors repositioning.
Efficient Load Balancing for a Resilient Packet Ring using Artificial Bee Colony
Anabela M. Bernardino, Eugénia M. Bernardino, Juan M. Sánchez-Pérez, Juan A. Gómez-Pulido, Miguel A. Vega-Rodríguez
Resilient Packet Ring (RPR), also known as IEEE 802.17, is a standard designed for optimising the transport of data traffic over optical fiber ring networks. The Weighted Ring Arc-Loading Problem (WRALP) is a NP-complete problem that arises in engineering and planning of the RPR systems. Specifically, for a given set of non-split and uni-directional point-to-point demands (weights), the objective is to find the routing for each demand (i.e., assignment of the demand to either clockwise or counter-clockwise ring) so that the maximum arc load will be minimised. This paper suggests an efficient traffic loading algorithm- Artificial Bee Colony (ABC). We compare our results with the ones obtained by the standard Genetic Algorithm, Tabu Search Algorithm and Particle Swarm Optimisation, used in literature. Simulation results verify the effectiveness of the ABC algorithm.
Solving the Physical Impairment Aware Routing and Wavelength Assignment Problem in Optical WDM Networks Using a Tabu Search Based Hyper-Heuristic Approach
Ali Keles, A. Şima Uyar, Aysegul Yayimli
In this paper, a tabu search based hyper heuristic is applied to the routing and wavelength assignment problem, considering physical impairments caused by Amplified Spontaneous Emission noise in erbium-doped fiber amplifiers and crosstalk noise at optical cross-connects. The objective is to minimize the total bit error rate of the routed lightpaths over optical wavelength division multiplexing networks. The results of the tabu search based hyper-heuristics are compared with single heuristic approaches. The results show that different heuristics provide the best result for different instances. The tabu search based hyper heuristic, which combines all the heuristics, gives comparable results to the single heuristics while using a modest amount of time. Furthermore, it has the best results for some problem instances.
Automatic Parameter Tuning with Metaheuristics of the AODV Routing Protocol for Vehicular Ad-Hoc Networks
Jose Garcia-Nieto, Enrique Alba
Communication protocol tuning can yield significant gains in energy efficiency, resource requirements, and the overall network performance, all of which is of particular importance in vehicular ad-hoc networks (VANETs). In this kind of networks, the lack of a predefined infrastructure as well as the high level of dynamism usually provoke problems such as the congestion of intermediate nodes, the appearance of jitters, and the disconnection of links. Therefore, it is crucial to make an optimal configuration of the routing protocols previously to the network deployment. In this work, we address the optimal automatic parameter tuning of a well-known routing protocol: Ad Hoc On Demand Distance Vector (AODV). For this task, we have used and compared five optimization techniques: PSO, DE, GA, ES, and SA. For our tests, a urban VANET scenario has been defined by following realistic mobility and data flow models. The experiments reveal that the produced configurations of AODV significantly improve their performance over using default parameters, as well as compared against other well-known routing protocols. Additionally, we found that PSO outperforms all the compared algorithms in efficiency and accuracy.
WiMAX Network Planning Using Adaptive-Population-Size Genetic Algorithm
Ting Hu, Yuanzhu Peter Chen, Wolfgang Banzhaf
IEEE 802.16, also known as WiMAX, is a new wireless access technology for currently increasing demand of wireless high-speed broadband service. Efficient and effective deployment of such a network to service an area of users with certain traffic demands is an important network planning problem. In this article, we resort to a Genetic Algorithm in order to yield good approximation solutions. In our method, individual representation and genetic variation operations are specifically designed to incorporate the feature of this application problem. Moreover, an adaptive population size approach inspired by neutral theory in molecular biology is applied in our algorithm to enhance its search ability. Simulation results show that our algorithm is fairly effective and robust to different scenarios of the network planning problem. By comparing to a conventional fixed population size scheme, our method is further verified to be able to accelerate the search process.
Markov Chain Models for Genetic Algorithm Based Topology Control in MANETs
Cem Safak Sahin, Stephen Gundry, Elkin Urrea, M. Umit Uyar, Michael Conner, Giorgio Bertoli, Christian Pizzo
We analyze the convergence properties of our force based genetic algorithm (FGA) as a decentralized topology control mechanism distributed among software agents. FGA guides autonomous mobile agents over an unknown geographical area to obtain a uniform node distribution. The stochastic behavior of FGA makes it difficult to analyze the effects of various MANET characteristics over its convergence rate. We present ergodic homogeneous Markov chains to analyze the convergence of our FGA with respect to changing communication range of mobile nodes. Simulation experiments indicate that the increased communication range for the mobile nodes does not result in a faster convergence.
Detection of DDoS Attacks via an Artificial Immune System-Inspired Multiobjective Evolutionary Algorithm
Ugur Akyazi, A. Şima Uyar
A Distributed Denial of Service Attack is a coordinated attack on the availability of services of a victim system, launched indirectly through many compromised computers. Intrusion detection systems (IDS) are network security tools that process local audit data or monitor network traffic to search for specific patterns or certain deviations from expected behavior. We use an Artificial Immune System (AIS) as a method of anomaly-based IDS because of the similarity between the IDS architecture and the Biological Immune Systems. We improved the jREMISA study; a Multiobjective Evolutionary Algorithm inspired AIS, in order to get better true and false positive rates while detecting DDoS attacks on the MIT DARPA LLDOS 1.0 dataset. We added the method of r-continuous evaluations, changed the Negative Selection and Clonal Selection structure, and redefined the objectives while keeping the general concepts the same. The 100% true positive rate and 0% false positive rate of our approach, under the given parameter settings and experimental conditions, shows that it is very successful as an anomaly-based IDS for DDoS attacks.
Performance Evaluation of an Artificial Neural Network-Based Adaptive Antenna Array System
Muamar Al-Bajari, Jamal Ahmed, Mustafa Ayoob
Efficient tracking systems are needed to constantly track multiple desired signals simultaneously in different modern wireless applications such as mobile communication, radar, and localization. The adaptive antenna tracking system presented in this paper mainly consists of three units: data processing, Artificial Neural Network Processor (ANNP) and the optimum weights processing. The data processing unit is used to calculate the correlation matrix of the received signals, which is eventually handled by the ANNP unit. The ANNP unit is based on the architecture of a family of Radial Basis Function Neural Network (RBFNN) to perform both detection and Direction of Arrival (DOA) estimation. The optimum weights processing unit utilizes the Linear Constraint Minimum Variance (LCMV) approach, using the estimated angles of the desired signals generated by the ANNP unit, to calculate the steering matrix of the AAA system. The performance evaluation of the system is conducted experimentally using simulation techniques in a variety of angular separations, number of sources and various Signal to Noise Ratios (SNRs).
A Generalized, Location-based Model of Connections in Ad-hoc Networks Improving the Performance of Ant Routing
Michal Kudelski, Andrzej Pacut
We formalize and analyze a generalized model of connections in ad-hoc networks. The proposed model defines connections on the locations level rather than on the nodes level. We show how the generalized model improves the stability of connections if the ant learning mechanism is applied to solve the routing problem. Stable connections reduce the overhead generated by ant routing mechanism and improve its performance in terms of end-to-end delay and delivery ratio. Moreover, connections on the locations level reflect physical connections in ad-hoc networks very well and agree with biological inspirations of ant algorithms.
On Modeling and Evolutionary Optimization of Nonlinearly Coupled Pedestrian Interactions
Pradyumn Kumar Shukla
Social force based modeling of pedestrians is an advanced microscopic approach for simulating the dynamics of pedestrian motion. The developments presented in this paper extend the widespread social force model to include improved velocity-dependent interaction forces. This modeling considers interactions of pedestrians with both static and dynamic obstacles, which can be also be effectively used to model pedestrian-vehicle interactions. The superiority of the proposed model is shown by comparing it with existing ones considering several thought experiments. Moreover, we apply an evolutionary algorithm to solve the model calibration problem, considering two real-world instances. The objective function for this problem comes from a set of highly nonlinear coupled differential equations. An interesting feature that came out is that the solutions are multi-modal. This makes this problem an excellent example for evolutionary algorithms and other such population based heuristics algorithms.
Evolving Individual Behavior in a Multi-Agent Traffic Simulator
Ernesto Sanchez, Giovanni Squillero, Alberto Tonda
In this paper, we illustrate the use of evolutionary agents in a Multi-Agent System designed to describe the behavior of car drivers. Each agent has the selfish objective to reach its destination in the shortest time possible, and a preference in terms of paths to take, based on the presence of other agents and on the width of the roads. Those parameters are changed with an evolutionary strategy, to mimic the adaptation of a human driver to different traffic conditions. The system proposed is then tested by giving the agents the ability to perceive the presence of other agents in a given radius. Experimental results show that knowing the position of all the car drivers in the map leads the agents to obtain a better performance, thanks to the evolution of their behavior. Even the system as a whole gains some benefits from the evolution of the agents' individual choices.
Symbiogenesis as a Mechanism for Building Complex Adaptive Systems: A Review
Peter Lichodzijewski, Malcolm Heywood
In 1996 Daida et al. reviewed the case for using symbiosis as the basis for evolving complex adaptive systems Specific observations included the impact of different philosophical views taken by biologists as to what constituted a symbiotic relationship and whether symbiosis represented an operator or a state. The case was made for symbiosis as an operator. Thus, although specific cost benefit characterizations may vary, the underlying process of symbiosis is the same, supporting the operator based perspective. Symbiosis provides an additional mechanism for adaption/ complexification than available under Mendelian genetics with which Evolutionary Computation (EC) is most widely associated. In the following we review the case for symbiosis in EC. In particular, symbiosis appears to represent a much more effective mechanism for automatic hierarchical model building and therefore scaling EC methods to more difficult problem domains than through Mendelian genetics alone.
Sexual Recombination in Self-Organizing Interaction Networks
Joshua Payne, Jason Moore
We build on recent advances in the design of self-organizing interaction networks by introducing a sexual variant of an existing asexual, mutation-limited algorithm. Both the asexual and sexual variants are tested on benchmark optimization problems with varying levels of problem difficulty, deception, and epistasis. Specifically, we investigate algorithm performance on Massively Multimodal Deceptive Problems and NK Landscapes. In the former case, we find that sexual recombination improves solution quality for all problem instances considered; in the latter case, sexual recombination is not found to offer any significant improvement. We conclude that sexual recombination in self-organizing interaction networks may improve solution quality in problem domains with deception, and discuss directions for future research.
Coevolutionary Dynamics of Interacting Species
Marc Ebner, Richard Watson, Jason Alexander
One of the open questions in evolutionary computation is how an arms race may be initiated between coevolving entities such that the entities acquire new behaviors and increase in complexity over time. It would be highly desirable to establish the necessary and sufficient conditions which lead to such an arms race. We investigate what these conditions may be using a model of competitive coevolution. Coevolving species are modeled as points which are placed randomly on a two-dimensional fitness landscape. The position of the species has an impact on the fitness landscape surrounding the phenotype of the species. Each species deforms the fitness landscape locally. This deformation, however, is not immediate. It follows the species after some latency period. We model evolution as a simple hill climbing process. Selection causes the species to climb towards the nearest optimum. We investigate the impact different conditions have on the evolutionary dynamics of this process. We will see that some conditions lead to cyclic or stationary behavior while others lead to an arms race. We will also see spontaneous occurrence of speciation on the two-dimensional landscape.
Revising the Trade-off Between the Number of Agents and Agent Intelligence
Marcus Komann, Dietmar Fey
Emergent agents are a promising approach to handle complex systems. Agent intelligence is thereby either defined by the number of states and the state transition function or the length of their steering programs. Evolution has shown to be successful in creating desired behaviors for such agents. Genetic algorithms have been used to find agents with fixed numbers of states and genetic programming is able to balance between the steering program length and the costs for longer programs. This paper extends previous work by further discussing the relationship between either using more agents with less intelligence or using fewer agents with higher intelligence. Therefore, the Creatures' Exploration Problem with a complex input set is solved by evolving emergent agents. It shows that neither a sole increase in intelligence nor amount is the best solution. Instead, a cautious balance creates best results.
Influence of Topology and Payload on CO2 Optimised Vehicle Routing
Cathy Scott, Neil Urquhart, Emma Hart
This paper investigates the influence of gradient and payload correction factors used within a CO2 emission model on the solutions to shortest path and travelling salesman problems when applied to freight delivery. Problem instances based on real life examples using the road network of Scotland are studied. Solutions are obtained using a range of metrics and vehicles. The results are compared to determine if the inclusion of gradient and payload as inputs to the emission model have any influence on the final routes taken by vehicles or the order of visiting customers. For the problem instances studied no significant influence was found. However for vehicle routing problems with large differences in payload and hilly road networks further investigation is needed.
Start-up Optimisation of a Combined Cycle Power Plant with Multiobjective Evolutionary Algorithms
Matteo De Felice, Ilaria Bertini, Fabio Moretti, Stefano Pizzuti
In this paper we present a study of the application of Evolutionary Computation methods to the optimisation of the start-up of a combined cycle power plant. We propose a multiobjective approach considering different objectives for the optimisation in order to reduce the pollution emissions and to maximise the efficiency of the plant. We compare a multiobjective evolutionary algorithm (NSGA-II) with 2 and 5 objectives on a software simulator and then we use different metrics to measure the performances. We show that NSGA-II algorithm is able to provide a set of solutions, defined as Pareto Front, that represent the best trade-off on the different objectives among those the decision maker can choose.
A Hyper-Heuristic Approach for the Unit Commitment Problem
Argun Berberoglu, A. Şima Uyar
This paper introduces a hyper-heuristic approach for the Unit Commitment Problem (UCP). Tests are performed using benchmark data from literature and real-world data from the Turkish interconnected power network. The proposed hyper-heuristic and several methods applied previously to the UCP, are compared. Results show that the hyper-heuristic method achieves good results in all test sets. Furthermore, it is also a robust method for increased problem sizes without the need for parameter tuning. Based on the promising results, research will continue for further improvements.
Application of Genetic Programming Classification in an Industrial Process Resulting in Greenhouse Gas Emission Reductions
Marco Lotz, Sara Silva
This paper compares Genetic Programming and the Classification and Regression Trees algorithm as data driven modelling techniques on a case study in the ferrous metals and steel industry in South Africa. These industries are responsible for vast amounts of greenhouse gas production, and greenhouse gas emission reduction incentives exist that can fund these abatement technologies. Genetic Programming is used to derive pure classification rule sets, and to derive a regression model used for classification, and both these results are compared to the results obtained by decision trees, regarding accuracy and human interpretability. Considering the overall simplicity of the rule set obtained by Genetic Programming, and the fact that its accuracy was not surpassed by any of the other methods, we consider it to be the best approach, and highlight the advantages of using a rule based classification system. We conclude that Genetic Programming can potentially be used as a process model that reduces greenhouse gas production.
Evolutionary Monte Carlo Based Techniques for First Passage Time Problems in Credit Risk and Other Applications in Finance
Olena Tsviliuk, Roderick Melnik, Di Zhang
Evolutionary computation techniques are closely connected with Monte Carlo simulations via statistical mechanics. Most practical realizations of such a connection are based on Markov chain Monte Carlo procedures and Markov chain approximation methodologies. However, such realizations face challenges when we have to deal with multivariate situations. In this contribution, we consider the development of evolutionary type Monte Carlo based algorithms for dealing with jump-diffusion stochastic processes. In particular, we focus on the first passage time problems for multivariate correlated jump-diffusion processes in the context of credit risk and the analysis of default correlations. The developed technique can be useful in option pricing as well as in other areas of complex systems analysis.
Active Portfolio Management from a Fuzzy Multi-objective Programming Perspective
We consider the problem of structuring a portfolio that outperforms a benchmark index, assuming restrictions on the total number of tradable assets. We experiment with non-standard formulations of active portfolio management, outside the mean-variance framework, incorporating approximate (fuzzy) investment targets and portfolio constraints. To deal with the inherent computational difficulties of cardinality-constrained active allocation problems, we apply three nature-inspired optimisation procedures: simulated annealing, genetic algorithms and particle swarm optimisation. Optimal portfolios derived from these methods are benchmarked against the Dow Jones Industrial Average stock market index and two simpler heuristics for detecting good asset combinations, based on Monte-Carlo simulation and fundamental analysis.
Calibrating the Heston Model with Differential Evolution
Manfred Gilli, Enrico Schumann
Calibrating option pricing models to market prices often leads to optimisation problems to which standard methods (like such based on gradients) cannot be applied. We investigate one particular example, Heston's stochastic volatility model. We discuss how to price options under this model, and how to calibrate the parameters of the model with a heuristic technique, Differential Evolution.
Evolving Dynamic Trade Execution Strategies using Grammatical Evolution
Wei Cui, Anthony Brabazon, Michael O'Neill
Although there is a plentiful literature on the use of evolutionary methodologies for the trading of financial assets, little attention has been paid to potential use of these methods for efficient trade execution. Trade execution is concerned with the actual mechanics of buying or selling the desired amount of a financial instrument of interest. Grammatical Evolution (GE) is an evolutionary automatic programming methodology which can be used to evolve rule sets. In this paper we use a GE algorithm to discover dynamic, efficient, trade execution strategies which adapt to changing market conditions. The strategies are tested in an artificial limit order market. GE was found to be able to evolve quality trade execution strategies which are highly competitive with two benchmark trade execution strategies.
Modesty is the Best Policy: Automatic Discovery of Viable Forecasting Goals in Financial Data
Fiacc Larkin, Conor Ryan
This paper presents a new approach to financial forecasting, inspired by strategies used by market traders. We demonstrate that a trading system with the relatively modest task of spotting trends in progress rather than the usual goal of spotting peaks and troughs can produce highly accurate forecasts. This is achieved by using a Genetic Algorithm to select appropriate training cases which are then fed to a trading system composed of multiple GP derived trees.
Threshold Recurrent Reinforcement Learning Model for Automated Trading
Dietmar Maringer, Tikesh Ramtohul
This paper presents the threshold recurrent reinforcement learning (TRRL) model and describes its application in a simple automated trading system. The TRRL is a regime-switching extension of the recurrent reinforcement learning (RRL) algorithm. The basic RRL model was proposed by Moody and Wu (1997) and used for uncovering trading strategies. We argue that the RRL is not sufficiently equipped to capture the non-linearities and structural breaks present in financial data, and propose the TRRL model as a more suitable algorithm for such environments. This paper gives a detailed description of the TRRL and compares its performance with that of the basic RRL model in a simple automated trading framework using daily data from four well-known European indices. We assume a frictionless setting and use volatility as an indicator variable for switching between regimes. We find that the TRRL produces better trading strategies in all the cases studied, and demonstrate that it is more apt at finding structure in non-linear financial time series than the standard RRL.
A Study of Nature-Inspired Methodologies for Financial Turning Point Detection
Antonia Azzini, Matteo De Felice, Andrea G.B. Tettamanzi
This paper presents an application of two nature-inspired algorithms to the financial problem concerning the detection of turning points. Nature-Inspired methods are receiving a growing interest due to their ability to cope with complex tasks like classification, forecasting and anomaly detection problems. A swarm intelligence algorithm, Particle Swarm Optimization (PSO), and an artificial immune system one, the Negative Selection (NS), are applied to the problem of detection of turning points, modeled as an Anomaly Detection (AD) problem, and their performances are compared. Both methods are found to give interesting results with respect to an unpredictable behavior.
Evolving Trading Rule-Based Policies
Robert Bradley, Anthony Brabazon, Michael O'Neill
Trading-rule representation is an important factor to consider when designing a quantitative trading system. This study implements a trading strategy as a rule-based policy. The result is an intuitive human-readable format which allows for seamless integration of domain knowledge. The components of a policy are specified and represented as a set of rewrite rules in a context-free grammar. These rewrite rules define how the components can be legally assembled. Thus, strategies derived from the grammar are well formed, domain specific, solutions. A grammar-based Evolutionary Algorithm, Grammatical Evolution (GE), is then employed to automatically evolve intra-day trading strategies for the U.S. Stock Market. The GE methodology managed to discover profitable rules with realistic transaction costs included. The paper concludes with a number of suggestions for future work.
Outperforming Buy-and-Hold with Evolved Technical Trading Rules: Daily, Weekly and Monthly Trading
Dome Lohpetch, David Corne
Genetic programming (GP) is increasingly popular as a research tool for applications in finance and economics. One thread in this area is the use of GP to discover effective technical trading rules. In a seminal article, Allen & Karjalainen (1999) used GP to find rules that were profitable, but were nevertheless outperformed by the simple "buy and hold" trading strategy. Many succeeding attempts have reported similar findings. There are a small handful of cases in which such work has managed to find rules that outperform buy-and-hold, but these have tended to be difficult to replicate. Recently, however, Lohpetch & Corne (2009) investigated work by Becker & Seshadri (2003), which showed outperformance of buy-and-hold. In turn, Becker & Seshadri's work had made several modifications to Allen & Karjalainen's work, including the adoption of monthly rather than daily trading. Lohpetch et al (2009) provided a replicable account of this, and also showed how further modifications enabled fairly reliable outperformance of buy-and-hold. It remained unclear, however, whether adoption of monthly trading is necessary to achieve robust outperformance of buy-and-hold. Here we investigate and compare each of daily, weekly and monthly trading; we find that outperformance of buy-and-hold can be achieved even for daily trading, but as we move from monthly to daily trading the performance of evolved rules becomes increasingly dependent on prevailing market conditions.
Evolutionary Multi-stage Financial Scenario Tree Generation
Multi-stage financial decision optimization under uncertainty depends on a careful numerical approximation of the underlying stochastic process, which describes the future returns of the selected assets or asset categories. Various approaches towards an optimal generation of discrete-time, discrete-state approximations (represented as scenario trees) have been suggested in the literature. In this paper, a new evolutionary algorithm to create scenario trees for multi-stage financial optimization models will be presented. Numerical results and implementation details conclude the paper.
Evolving a Ms.Pac-man Controller using Grammatical Evolution
Edgar Galván-López, John Swafford, Michael O'Neill
In this paper we propose an evolutionary approach capable of successfully combining rules to play the popular video game, Ms. Pac-Man. In particular we focus our attention on the benefits of using Grammatical Evolution to combine rules in the form of "if
Evolutionary Algorithm for Generation of Entertaining Shinro Logic Puzzles
A Shinro puzzle is a type of deductive reasoning puzzle that originated in Japanese periodicals. To solve the puzzle, one must locate twelve hidden stones on an 8x8 grid using only clues in the form of stone counts per row and column, and arrows placed in the grid that point to some of the hidden stones. Construction of these puzzles by hand is tedious. We explore the use of a simple genetic algorithm that automates construction of Shinro puzzles with desirable qualities which improve their entertainment value.
Social Learning algorithms reaching Nash Equilibrium in Symmetric Cournot Games
Mattheos Protopapas, Francesco Battaglia, Elias Kosmatopoulos
The series of studies about the convergence or not of the evolutionary strategies of players that use co-evolutionary genetic algorithms in Cournot games has not adressed the issue of individual players' strategies convergence, but only of the convergence of the aggregate indices (total quantity and price) to the levels that correspond either to the Nash or Walrash Equilibrium. Here we discover that while some algorithms lead to convergence of the aggregates to Nash Equilibrium values, this is not the case for the individual players' strategies (i.e. no NE is reached). Co-evolutionary programming social learning, as well as a social learning algorithm we introduce here, achieve this goal (in a stochastic sense); this is displayed by statistical tests, as well as "NE stages" evaluation, based on ergodic Markov chains.
Multiple Overlapping Tiles for Contextual Monte Carlo Tree Search
Arpad Rimmel, Fabien Teytaud
Monte Carlo Tree Search is a recent algorithm that achieves more and more successes in various domains. We propose an improvement of the Monte Carlo part of the algorithm by modifying the simulations depending on the context. The modification is based on a reward function learned on a tiling of the space of Monte Carlo simulations. The tiling is done by regrouping the Monte Carlo simulations where two moves have been selected by one player. We show that it is very efficient by experimenting on the game of Havannah.
Evolving Bot's AI in Unreal
Antonio Mora, Juan Julián Merelo, Ramón Montoya, Pablo García, Pedro Castilllo, Juan Luís Jiménez, Anna Esparcia, Ana Martínez
This paper describes the design, implementation and results of an evolutionary bot inside the PC game Unreal (TM), that is, an autonomous enemy which tries to beat the human player and/or some other bots. The default artificial intelligence (AI) of this bot has been improved using two different evolutionary methods: genetic algorithms (GAs) and genetic programming (GP). The first one has been applied for tuning the parameters of the hard-coded values inside the bot AI code. The second method has been used to change the default set of rules (or states) that defines its behaviour. Both techniques yield very good results, evolving bots which are capable to beat the default ones. The best results are yielded for the GA approach, since it just does a refinement following the default behaviour rules, while the GP method has to redefine the whole set of rules, so it is harder to get good results.
Evolution of Grim Trigger in Prisoner Dilemma Game with Partial Imitation
Degang Wu, Mathis Antony, Kwok Yip Szeto
The emergence of Grim Trigger as the dominant strategy in the Iterated Prisoner Dilemma (IPD) on a square lattice is investigated for players with finite memory, using three different kinds of imitation rule: the traditional imitation rule where the entire data base of the opponent's moves is copied, and the two more realistic partial imitation rules that copy only a subset of opponent's moves based on information of games played. We find that the dominance of Grim Trigger is enhanced at the expense of some well known strategies such as tit-for-tat (TFT) when a player has access only to those moves observed in past games played with his opponents. The evolution of the clusters of Grim Trigger in the early stage of the games obeys a common pattern for all imitation rules, before these clusters of Grim Triggers coalesce into larger patches in the square lattice. A physical explanation for this pattern evolution is given. Implication of the partial imitation rule for IPD on complex networks is discussed.
Towards a Generic Framework for Automated Video Game Level Creation
Nathan Sorenson, Philippe Pasquier
This paper presents a generative system for the automatic creation of video game levels. Our approach is novel in that it allows high-level design goals to be expressed in a top-down manner, while existing bottom-up techniques do not. We use the FI-2Pop genetic algorithm as a natural way to express both constraints and optimization goals for potential level designs. We develop a genetic encoding technique specific to level design, which proves to be extremely flexible. Example levels are generated for two different genres of game, demonstrating the system's broad applicability.
Fuzzy Nash-Pareto Equilibrium: Concepts and Evolutionary Detection
Dumitru Dumitrescu, Rodica Ioana Lung, Tudor Dan Mihoc, Reka Nagy
Standard game theory relies on the assumption that players are rational agents that try to maximize their payoff. Experiments with human players indicate that Nash equilibrium is seldom played. The goal of proposed approach is to explore more nuance equilibria by allowing a player to be biased towards different equilibria in a fuzzy manner. Several classes of equilibria (Nash, Pareto, Nash-Pareto) are defined by using appropriate generative relations. An evolutionary technique for detecting fuzzy equilibria is considered. Experimental results on Cournot' duopoly game illustrate evolutionary detection of proposed fuzzy equilibria.
An Evolutionary Approach for Solving the Rubik's Cube Incorporating Exact Methods
Nail El-Sourani, Sascha Hauke, Markus Borschbach
Solutions calculated by Evolutionary Algorithms have come to surpass exact methods for solving various problems. The Rubik's Cube multiobjective optimization problem is one such area. In this work we present an evolutionary approach to solve the Rubik's Cube with a low number of moves by building upon the classic Thistlethwaite's approach. We provide a group theoretic analysis of the subproblem complexity induced by Thistlethwaite's group transitions and design an Evolutionary Algorithm from the ground up including detailed derivation of our custom fitness functions. The implementation resulting from these observations is thoroughly tested for integrity and random scrambles, revealing performance that is competitive with exact methods without the need for pre-calculated lookup tables.
Evolution of Artificial Terrains for Video Games Based on Accessibility
Miguel Frade, Francisco Fernandez de Vega, Carlos Cotta
Diverse methods have been developed to generate terrains under constraints to control terrain features, but most of them use strict restrictions. However, there are situations were more flexible restrictions are sufficient, such as ensuring that terrains have enough accessible area, which is an important trait for video games. The Genetic Terrain Program technique, based on genetic programming, was used to automatically evolve Terrain Programs (TPs - which are able to generate terrains procedurally) for the desired accessibility parameters. Results showed that the accessibility parameters have negligible influence on the evolutionary system and that the terminal set has a major role on the terrain look. TPs produced this way are already being used on Chapas video game.
Finding Better Solutions to the Mastermind Puzzle Using Evolutionary Algorithms
Juan J. Merelo Guervós, Tómas Philip Runarsson
The art of solving the Mastermind puzzle was initiated by Donald Knuth and is already more than thirty years old; despite that, it still receives much attention in operational research and computer games journals, not to mention the nature-inspired stochastic algorithm literature. In this paper we revisit the application of evolutionary algorithms to solving it and trying some recently-found results to an evolutionary algorithm. The most parts heuristic is used to select guesses found by the evolutionary algorithms in an attempt to find solutions that are closer to those found by exhaustive search algorithms, but at the same time, possibly have better scaling properties when the size of the puzzle increases.
Evolving Behaviour Trees for the Commercial Game DEFCON
Chong-U Lim, Robin Baumgarten, Simon Colton
Behaviour trees provide the possibility of improving on existing Artificial Intelligence techniques in games by being simple to implement, scalable, able to handle the complexity of games, and modular to improve reusability. This ultimately improves the development process for designing automated game players. We cover here the use of behaviour trees to design and develop an AI-controlled player for the commercial real-time strategy game DEFCON. In particular, we evolved behaviour trees to develop a competitive player which was able to outperform the game's original AI-bot more than 50% of the time. We aim to highlight the potential for evolving behaviour trees as a practical approach to developing AI-bots in games.
Co-evolution of Optimal Agents for the Alternating Offers Bargaining Game
Arjun Chandra, Pietro S Oliveto, Xin Yao
Bargaining, as an instance of sequential games, is a widely studied problem in game theory, experimental and computational economics. We consider the problem of evolving computational agents with optimal (Subgame Perfect Equilibrium) strategies for the Alternating Offers Bargaining Game. Previous work co-evolving agents for this problem has argued that it is not possible to achieve optimal agents at the end of the co-evolutionary process due to the myopic properties of the evolutionary agents. Emphasising the notion of a co-evolutionary solution concept, we show that this conclusion is mis-leading and present a co-evolutionary algorithm that evolves optimal strategies for the bargaining game with one round. We conclude by explaining why, using previous evaluation procedures and strategy representations, the algorithm is not able to converge to optimal strategies for games with more rounds.
Search-based Procedural Content Generation
Julian Togelius, Georgios N. Yannakakis, Kenneth O. Stanley, Cameron Browne
Recently, a small number of papers have appeared in which the authors implement stochastic search algorithms, such as evolutionary computation, to generate game content, such as levels, rules and weapons. We propose a taxonomy of such approaches, centring on what sort of content is generated, how the content is represented, and how the quality of the content is evaluated. The relation between search-based and other types of procedural content generation is described, as are some of the main research challenges in this new field. The paper ends with some successful examples of this approach.
Evolving 3D Buildings for the Prototype Video Game Subversion
Andy Martin, Andrew Lim, Simon Colton, Cameron Browne
We investigate user-guided evolution for the development of virtual 3D building structures for the prototype (commercial) game Subversion, which is being developed by Introversion Software Ltd. Buildings are described in a custom plain-text markup language that can be parsed by Subversion's procedural generation engine, which renders the 3D models on-screen. The building descriptions are amenable to random generation, crossover and mutation, which enabled us to implement and test a user-driven evolutionary approach to building generation. We performed some fundamental experimentation with ten participants to determine how visually similar child buildings are to their parents, when generated in differing ways. We hope to demonstrate the potential of user-guided evolution for content generation in games in general, as such tools require very little training, time or effort to be employed effectively.
An Evolutionary Method for Model-Based Automatic Segmentation of Lower Abdomen CT Images for Radiotherapy Planning
Vitoantonio Bevilacqua, Giuseppe Mastronardi, Alessandro Piazzolla
Segmentation of target organs and organs at risk is a fundamental task in radiotherapy treatment planning. Since its completion carried out by a radiation oncologist is really time-consuming, there is the need to perform it automatically. Unfortunately there is not a universal method capable to segment accurately every anatomical structure in every medical image, so each problem requires a study and an own solution. In this paper we analyze the problem of segmentation of bladder, prostate and rectum in lower abdomen CT images and propose a novel algorithm to solve it. It builds a statistical model of the organs analyzing a training set, generates potential solutions and chooses the segmentation result evaluating them on the basis of an aprioristic knowledge and the characteristics of patient image, using Genetic Algorithms. Out method has been tested qualitatively and quantitatively and offered good performance.
Dynamic Data Clustering Using Stochastic Approximation Driven Multi-Dimensional Particle Swarm Optimization
Serkan Kiranyaz, Turker Ince, Moncef Gabbouj
With an ever-growing attention Particle Swarm Optimization (PSO) has found many application areas for many challenging optimization problems. It is, however, a known fact that PSO has a severe drawback in the update of its global best (gbest) particle, which has a crucial role of guiding the rest of the swarm. In this paper, we propose two efficient solutions to remedy this problem using a stochastic approximation (SA) technique. For this purpose we use simultaneous perturbation stochastic approximation (SPSA), which is applied only to the gbest (not to the entire swarm) for a low-cost solution. Since the problem of poor gbest update persists in the recently proposed extension of PSO, called multi-dimensional PSO (MD-PSO), two distinct SA approaches are then integrated into MD-PSO and tested over a set of unsupervised data clustering applications. Experimental results show that the proposed approaches significantly improved the quality of the MD-PSO clustering as measured by a validity index function. Furthermore, the proposed approaches are generic as they can be used with other PSO variants and applicable to a wide range of problems.
Automatic Synthesis of Associative Memories through Genetic Programming: a Co-evolutionary Approach
Juan Villegas-Cortez, Gustavo Olague, J. Humberto Sossa A., Carlos Aviles-Cruz, A. Ferreyra
Associative Memories (AMs) are mathematical structures specially designed to associate input patterns with output patterns within a single stage. Since the last fifty years all reported AMs have been manually designed. The paper describes a Genetic Programming based methodology able to create a process for the automatic synthesis of AMs. It paves a new area of research that permits for the first time to propose new AMs for solving specific problems. In order to test our methodology we study the application of AMs for real value patterns. The results illustrate that it is possible to automatically generate AMs that achieve good recall performance for problems commonly used in pattern recognition research.
Evolution of Communicating Individuals
Leonardo Bocchi, Sara Lapi, Lucia Ballerini
Verbal communication between individuals requires the parallel evolution of a vocal system capable of emitting different sounds and of an auditory system able to recognize each vocal pattern. In this work we present the evolution of a population of twins where the selection pressure is based on the ability of learning a communication pattern which allows verbal transmission of information. The fitness of each pair of twins (i.e. individuals having the same genotype) is based on the percentage of correct recognition of the perceived sounds. Results indicate the evolved communication system, in absence of noise, rapidly evolves and reaches almost 100% correct classifications, while, even in presence of a strong noise either in the channel, or in the sound generation parameters, the system can obtain a very good performance (approximately 80% correct classifications in the worst case).
Content-Based Image Retrieval of Skin Lesions by Evolutionary Feature Synthesis
Lucia Ballerini, Xiang Li, Robert Fisher, Ben Aldridge, Jonathan Rees
This paper gives an example of evolved features that improve image retrieval performance. A content-based image retrieval system for skin lesion images is presented. The aim is to support decision making by retrieving and displaying relevant past cases visually similar to the one under examination. Skin lesions of five common classes, including two non-melanoma cancer types, are used. Colour and texture features are extracted from lesions. Evolutionary algorithms are used to create composite features that optimise a similarity matching function. Experiments on our database of 533 images are performed and results are compared to those obtained using simple features. The use of the evolved composite features improves the precision by about 7%.
Genetic Algorithms for Training Data and Polynomial Optimization in Colorimetric Characterization of Scanners
Leonardo Vanneschi, Mauro Castelli, Simone Bianco, Raimondo Schettini
Generalization is an important issue in colorimetric characterization of devices. We propose a framework based on Genetic Algorithms to select training samples from large datasets. Even though the framework is general, and can be used in principle for any dataset, we use two well known datasets as case studies: training samples are selected from the Macbeth ColorCheckerDC dataset and the trained models are tested on the Kodak Q60 photographic standard dataset. The presented experimental results show that the proposed framework has better, or at least comparable, performances than a set of other computational methods defined so far for the same goal (Hardeberg, Cheung, CIC and Schettini). Even more importantly, the proposed framework has the ability to optimize the training samples and the characterizing polynomial's coefficients at the same time.
Chaotic Hybrid Algorithm and its Application in Circle Detection
Wu Chun-ho, Dong Na, IP Wai-hung, Chan Ching-yuen, Yung Kei-leung, Chen Zeng-qiang
An evolutionary circle detection method based on a novel Chaotic Hybrid Algorithm (CHA) is proposed. The method combines the strengths of particle swarm optimization, genetic algorithms and chaotic dynamics, and involves the standard velocity and position updating rules of PSO with the ideas of GA selection, crossover and mutation. In addition, the notion of species is introduced into the proposed CHA to enhance its performance in solving multimodal problems. The effectiveness of the Species based Chaotic Hybrid Algorithm (SCHA) is proven through simulations and benchmarking, and finally, it is successfully applied to solve circle detection problems.
Bloat Free Genetic Programming versus Classification Trees for Identification of Burned Areas in Satellite Imagery
Sara Silva, Maria Vasconcelos, Joana Melo
This paper compares Genetic Programming and Classification Trees on a problem of identification of burned areas in satellite imagery. Additionally, it studies how the most recently recognized bloat control technique, Operator Equalisation, affects the quality of the solutions provided by Genetic Programming. The merit of each approach is assessed not only by its classification accuracy, but also by the ability to predict the correctness of its own classifications, and the ability to provide solutions that are human readable and robust to data inaccuracies. The results reveal that both approaches achieve high accuracy with no overfitting, and that Genetic Programming can reveal some surprises and offer interesting advantages even on a simple problem so easily tackled by the popular Classification Trees. Operator Equalisation proved to be crucial.
Towards Automated Learning of Object Detectors
Recognizing arbitrary objects in images or video sequences is a difficult task for a computer vision system. We work towards automated learning of object detectors from video sequences (without user interaction). Our system uses object motion as an important cue to detect independently moving objects in the input sequence. The largest object is always taken as the teaching input, i.e. the object to be extracted. We use Cartesian Genetic Programming to evolve image processing routines which deliver the maximum output at the same position where the detected object is located. The graphics processor (GPU) is used to speed up the image processing. Our system is a step towards automated learning of object detectors.
A CNN Based Algorithm for the Automated Segmentation of Multiple Sclerosis Lesions
Eleonora Bilotta, Antonio Cerasa, Pietro Pantano, Aldo Quattrone, Andrea Staino, Francesca Stramandinoli
We describe a new application based on genetic algorithms (GAs) that evolves a Cellular Neural Network (CNN) capable to automatically determine the lesion load in multiple sclerosis (MS) patients from Magnetic Resonance Images (MRI). In particular, it seeks to identify in MRI brain areas affected by lesions, whose presence is revealed by areas of lighter color than the healthy brain tissue. In the first step of the experiment, the CNN has been evolved to achieve better performances for the analysis of MRI. Then, the algorithm was run on a data set of 11 patients; for each one 24 slices, each with a resolution of 256 x 256 pixels, were acquired. The results show that the application is efficient in detecting MS lesions. Furthermore, the increased accuracy of the system, in comparison with other approaches, already implemented in the literature, greatly improves the diagnosis for this disease.
Hand Posture Recognition using a Real-time EA
Benoit Kaufmann, Jean Louchet, Evelyne Lutton
In this paper, we present a hand posture recognition system (configuration and position) we designed as part of a gestural man-machine interface. After a simple image preprocessing, the parameter space (corresponding to the configuration and spatial position of the user's hand) is directly explored using a population of points evolved via an Evolution Strategy. Giving the priority to exploring the parameter space rather than the image, is an alternative to the classical generalisation of the Hough Transform and allows to meet the real-time constraints of the project. The application is an Augmented Reality prototype for a long term exhibition at the Cité des Sciences, Paris. As it will be open to the general public, rather than using conventional peripherals like a mouse or a joystick, a more natural interface has been chosen, using a microcamera embedded into virtual reality goggles in order to exploit the images of the user's hand as input data and enable the user to manipulate virtual objects without any specific training.
Comparing Cellular and Panmictic Genetic Algorithms for Real-Time Object Detection
Jesús Martínez-Gómez, José A. Gámez, Ismael García-Varea
Object detection is a key point in robotics, both in localization and robot decision making. Genetic Algorithms (GAs) have proven to work well in this type of tasks, but they usually give rise to heavy computational processes. The scope of this study is the Standard Platform category of the RoboCup soccer competition, and so real-time object detection is needed. Because of this, we constraint ourselves to the use of tiny GAs. The main problem with this type of GAs is their premature convergence to local optima. In this paper we study two different approaches to overcoming this problem: the use of population re-starts, and the use of a cellular GA instead of the standard generational one. The combination of these approaches with a clever initialisation of the population has been analyzed experimentally, and from the results we can conclude that for our problem the best choice is the use of cellular GAs.
Markerless Multi-View Articulated Pose Estimation Using Adaptive Hierarchical Particle Swarm Optimisation
Spela Ivekovic, Vijay John, Emanuele Trucco
In this paper, we present a new adaptive approach to multi-view markerless articulated human body pose estimation from multi-view video sequences, using Particle Swarm Optimisation (PSO). We address the computational complexity of the recently developed hierarchical PSO (HPSO) approach, which successfully estimated a wide range of different motion with a fixed set of parameters, but incurred an unnecessary overhead in computational complexity. Our adaptive approach, called APSO, preserves the black-box property of the HPSO in that it requires no parameter value input from the user. Instead, it adaptively changes the value of the search parameters online, depending on the quality of the pose estimate in the preceding frame of the sequence. We experimentally compare our adaptive approach with HPSO on four different video sequences and show that the computational complexity can be reduced without sacrificing accuracy and without requiring any user input or prior knowledge about the estimated motion type.
New Genetic Operators in the Fly Algorithm: Application to Medical PET Image Reconstruction
Franck P. Vidal, Jean Louchet, Jean-Marie Rocchisani, Evelyne Lutton
This paper presents an evolutionary approach for image reconstruction in positron emission tomography (PET). Our reconstruction method is based on a cooperative coevolution strategy (also called Parisian evolution): the "fly algorithm". Each fly is a 3D point that mimics a positron emitter. The flies' position is progressively optimised using evolutionary computing to closely match the data measured by the imaging system. The performance of each fly is assessed using a "marginal evaluation" based on the positive or negative contribution of this fly to the performance of the population. Using this property, we propose a "thresholded-selection" method to replace the classical tournament method. A mitosis operator is also proposed. It is triggered to automatically increase the population size when the number of flies with negative fitness becomes too low.
A Hybrid Evolutionary Algorithm for Bayesian Networks Learning: an Application to Classifier Combination
Claudio De Stefano, Francesco Fontanella, Cristina Marrocco, Alessandra Scotto di Freca
Classifier combination methods have shown their effectiveness in a number of applications. Nonetheless, using simultaneously multiple classifiers may result in some cases in a reduction of the overall performance, since the responses provided by some of the experts may generate consensus on a wrong decision even if other experts provided the correct one. To reduce these undesired effects, in a previous paper, we proposed a combining method based on the use of a Bayesian Network. The structure of the Bayesian Network was learned by using an Evolutionary Algorithm which uses a specifically devised data structure to encode Direct Acyclic Graphs. In this paper we presents an further improvement along this direction, in that we have developed a new hybrid evolutionary algorithm in which the exploration of the search space has been improved by using a measure of the statistical dependencies among the experts. Moreover, new genetic operators have been defined that allow a more effective exploitation of the solutions in the evolving population. The experimental results, obtained by using two standard databases, confirmed the effectiveness of the method.
Makerless Localization for Blind Users using Computer Vision and Particle Swarm Optimization
Hashem Tamimi, Anas Sharabati
In this paper, we propose a novel approach, which aims to solve the localization and target-finding problem for blind and partially sighted people. A guidance system, solely implemented on a mobile phone with a camera, is employed. A computer vision approach integrated with Particle Swarm Optimization (PSO) is proposed for tracking the location. Using PSO leads to many advantages: first, it is possible to obtain robust localization results by combining the current and historical information about the location of the blind person. Second, it helps the system to resolve from ambiguous situations caused by facing similar images at different locations. Third, it can detect and recover from cases where the calculated location is wrong. Experimental results show that the proposed method works efficiently because of the simplicity of the approach, which makes it suitable for mobile applications.
Self-organized and Evolvable Cognitive Architecture for Intelligent Agents and Multi-Agent Systems
Oscar Javier Romero López, Angélica De Antonio Jiménez
Integrating different kinds of micro-theories of cognition in intelligent systems when a huge amount of variables are changing continuously, with increasing complexity, is a very exhaustive and complicated task. Our approach proposes a hybrid cognitive architecture that relies on the integration of emergent and cognitivist approaches using evolutionary strategies, in order to combine implicit and explicit knowledge representations necessary to develop cognitive skills. The proposed architecture includes a cognitive level controlled by autopoietic machines and artificial immune systems based on genetic algorithms, giving it a significant degree of plasticity. Furthermore, we propose an attention module which includes an evolutionary programming mechanism in charge of orchestrating the hierarchical relations among specialized behaviors, taking into consideration the global workspace theory for consciousness. Additionally, a co-evolutionary mechanism is proposed to propagate knowledge among cognitive agents on the basis of memetic engineering. As a result, several properties of self-organization and adaptability emerged when the proposed architecture was tested in an animat environment, using a multi-agent platform.
A Comparative Study between Genetic Algorithm and Genetic Programming Based Gait Generation Methods for Quadruped Robots
Kisung Seo, Soohwan Hyun
Planning gaits for legged robots is a challenging task that requires optimizing parameters in a highly irregular and multidimensional space. Two gait generation methods using GA (Genetic Algorithm), GP (genetic programming) are compared to develop fast locomotion for a quadruped robot. GA-based approaches seek to optimize a pre-selected set of parameters which include locus of paw and stance parameters of initial position. A GP-based technique is an effective way to generate a few joint trajectories instead of the locus of paw positions and many stance parameters. Optimizations for two proposed methods are executed and analyzed using a Webots simulation of the quadruped robot built by Bioloid. Furthermore, simulation results for the two proposed methods are tested in a real quadruped robot, and the performance and motion features of GA-, GP-based methods are compared.
Particle Swarm Optimization for Feature Selection in Speaker Verification
Mohammad Ehsan Basiri, Shahla Nemati
The problem addressed in this paper concerns the feature subset selection for an automatic speaker verification system. An effective algorithm based on particle swarm optimization is proposed here for discovering the best feature combinations. After feature reduction phase, feature vectors are applied to a Gaussian mixture model which is a text-independent speaker verification model. The performance of proposed system is compared to the performance of a genetic algorithm based system and the baseline algorithm. Experimentation is carried out, using TIMIT corpora. The results of experiments indicate that with the optimized feature subset, the performance of the system is improved. Moreover, the speed of verification is significantly increased since by use of PSO, number of features is reduced over 85% which consequently decrease the complexity of our ASV system.
Scale and Rotation-Robust Genetic Programming-Based Corner Detectors
Kisung Seo, Youngkyun Kim
This paper introduces GP- (Genetic Programming-) based robust corner detectors for scaled and rotated images. Previous Harris, SUSAN and FAST corner detectors are highly efficient for well-defined corners, but frequently mis-detect as corners the corner-like edges which are often generated in rotated images. It is very difficult to avoid incorrectly detecting as corners many edges which have characteristics similar to corners. In this paper, we have focused on this challenging problem and proposed using Genetic Programming to do automated generation of corner detectors that work robustly on scaled and rotated images. Various terminal sets are presented and tested to capture the key properties of corners. Combining intensity-related information, several mask sizes, and amount of contiguity of neighboring pixels of similar intensity, allows a well-devised terminal set to be proposed. This method is then compared to three existing corner detectors on test images and shows superior results.
Evolutionary Sound Synthesis: Rendering Spectrograms from Cellular Automata Histograms
Jaime Serquera, Eduardo Miranda
In this paper we report on the synthesis of sounds using cellular automata, specifically the multitype voter model. The mapping process adopted is based on digital signal processing analysis of automata evolutions and consists in mapping histograms onto spectrograms. The main problem of cellular automata is the difficulty of control and, consequently, sound synthesis methods based on these computational models normally present a high factor of randomness in the output. We have achieved a significant degree of control as to predict the type of sounds that we can obtain. We are able to develop a flexible sound design process with emphasis on the possibility of controlling over time the spectrum complexity.
Dynamic Musical Orchestration using Genetic Algorithms and a Spectro-Temporal Description of Musical Instruments
Esling Philippe, Carpentier Grégoire, Agon Carlos
In this paper a computational approach of musical orchestration is presented. We consider orchestration as the search of relevant sound combinations within large instruments sample databases. The working environment is Orchid\'ee, an evolutionary orchestration algorithm that allows a constrained multiobjective search towards a target timbre, in which several perceptual dimensions are jointly optimized. Up until now, Orchidee was bounded to "time-blind" features, by the use of averaged descriptors over the whole spectrum. We introduce a new instrumental model based on Gaussian Mixture Models (GMM) which allows to represent the complete spectro-temporal structure. We then present the results of the integration of our model and improvement that it brings to the existing system.
Comparing Aesthetic Measures for Evolutionary Art
E. den Heijer, A. E. Eiben
In this paper we investigate and compare four aesthetic measures within the context of evolutionary art. We evolve visual art with an unsupervised evolutionary art system using genetic programming and an aesthetic measure as the fitness function. We perform multiple experiments with different aesthetic measures and examine their influence on the evolved images. To this end we store the 5 fittest individuals of each run and hand-pick the best 9 images after finishing the whole series. This way we create a portfolio of evolved art for each aesthetic measure for visual inspection. Additionally, we perform a cross-evaluation by calculating the aesthetic value of images evolved by measure i according to measure j. This way we investigate the flexiblity of each aesthetic measure (i.e., whether the aesthetic measure appreciates different types of images). The results show that aesthetic measures have a rather clear "style" and that these styles can be very different. Furthermore we find that some aesthetic measures show very little flexibility and appreciate only a limited set of images.
Refinement Techniques for Animated Evolutionary Photomosaics using Limited Tile Collections
Shahrul Badariah Mat Sah, Vic Ciesielski, Daryl D'Souza
An animated evolutionary photomosaic is produced from a sequence of still or static photomosaics to evolve a near match to a given target image. A static photomosaic is composed of small digital images or tiles, each having their own aesthetic value. If the tiles are prepared manually, the tile collections are typically small. This potentially limits the visual quality of a photomosaic as there may not be sufficient options for matching tiles. We investigate the use of colour adjustment and tile size variation techniques via genetic programming to improve the animated photomosaics. The results show that colour adjustment improved both visual quality and fitness. However, it can produce strange looking tiles. Tile size variation was able to focus on details in the target image but produced slightly worse fitness values than an equal-sized tiles approach. Combining these techniques revealed that, regardless of the size of tiles, colour adjustment was the dominant refinement. In conclusion, each of these techniques is able to produce an aesthetically different animation effect and presents a better mechanism for generating photomosaics when only a limited number of tiles is available.
Aesthetic Learning in an Interactive Evolutionary Art System
Yang Li, Changjun Hu
Learning aesthetic judgements is essential for reducing the users' fatigue in evolutionary art system. Although judging beauty is a highly subjective task, we consider that certain features are important to please users. In this paper, the aesthetic preferences are explored by learning the features, which we extracted from the images in the interactive generations. In addition to color ingredients, image complexity and image order are considered highly relevant to aesthetic measurement. We interpret these two features from the information theory and fractal compression perspective. Our experimental results suggest that these features play important roles in aesthetic judgements. Our findings also show that our evolutionary art system is efficient at predicting user's preference.
Jive: A Generative, Interactive, Virtual, Evolutionary Music System
Jianhua Shao, James McDermott, Michael O'Neill, Anthony Brabazon
A novel paradigm and system for interactive generative music are described. Families of musical pieces are represented as functions of a time variable and several variables under user control. Composition/performance proceeds in the following two stages. Interactive grammatical evolution is used to represent, explore, and optimise the possible functions. The computer mouse or a Wii-controller can be used for real-time interaction with the generative process. We present rationale for design decisions and several pieces of example music.
Generative Art and Evolutionary Refinement
In considering a case study, we examine the process of promoting emergence and creativity within an evolutionary art system using the technique of evolutionary refinement. That is, for the complex, difficult to predict generative scheme based on a model for simulating cellular morphogenesis that forms the generative component of an evolutionary art system, we discuss how we proceed in stages to develop, analyze, focus, and re-target evolved genetic material for aesthetic purposes --- in this instance aesthetic pattern formation.
Learning to Dance through Interactive Evolution
Gregory Dubbin, Kenneth Stanley
A relatively rare application of artificial intelligence at the nexus of art and music is dance. The impulse shared by all humans to express ourselves through dance represents a unique opportunity to artificially capture human creative expression. In particular, the spontaneity and relative ease of moving to the music without any overall plan suggests a natural connection between temporal patterns and motor control. To explore this potential, this paper presents a model called Dance Evolution, which allows the user to train virtual humans to dance to MIDI songs or raw audio, that is, the dancers can dance to any song heard on the radio, including the latest pop music. The dancers are controlled by artificial neural networks (ANNs) that "hear" MIDI sequences or raw audio processed through a discrete Fourier transform-based technique. ANNs learn to dance in new ways through an interactive evolutionary process driven by the user. The main result is that when motion is expressed as a function of sound the effect is a plausible approximation of the natural human tendency to move to music.
Philippe Codognet, Olivier Pasquet
Sound Agents is a media intallation relating real space and virtual sound space. Each agent is a virtual entity producing sound, which has its own autonomous behavior. This sound is spatialized in the real installation space through many loudspeakers (24 loudspeakers + 1 subwoofer), creating thus an ever-changing ambient music which is dynamically spatialized and modified by the movement of the virtual agents. We implemented a first propotype of this general scheme by using swarm intelligence and the classical ant foraging simulation to generate ambient soundscape, associating sounds to ants movements and pheromone levels. We further designed a declarative high-level language for describing autonomous behaviors of the virtual sound agents.This language is based on the notion of goal constraints and simple constraint-based local search techniques are defined as a behavior engine.
From Evolutionary Composition to Robotic Sonification
Artemis Moroni, Jônatas Manzolli
A new approach is presented which integrates evolutionary computation and real world devices such as mobile robots and an omnidirectional vision system. Starting with an evolutionary composition system named JaVOX, a hybrid environment named AURAL evolved. In the AURAL, the behavior of mobile robots in an arena is applied as a compositional strategy. It uses trajectories produced by mobile robots to modify the fitness function of a real time sonic composition. The model is described, its evolutionary design and how the interaction between the real world devices was implemented. This research is oriented towards the study of automatic and semi-automatic processes of artistic production in the sound domain.
The problem with evolutionary art is ...
Computational evolutionary art has been an active practice for at least 20 years. Given the remarkable advances in that time in other realms of computing, including other forms of evolutionary computing, for many a vague feeling of disappointment surrounds evolutionary art. Aesthetic improvement in evolutionary art has been slow, and typically achieved in ways that are not widely generalizable or extensible. So what is the problem with evolutionary art? And, frankly, why isn't it better? In this paper I respond to these questions from my point of view as a practicing artist applying both a technical and art theoretical understanding of evolutionary art. First the lack of robust fitness functions is considered with particular attention to the problem of computational aesthetic evaluation. Next the issue of genetic representation is discussed in the context of complexity and emergence. And finally, and perhaps most importantly, the need for art theory around evolutionary and generative art is discussed, and a theory that stands typical evolutionary art on its head is proposed.
A Neural Network for Bass Functional Harmonization
Roberto De Prisco, Antonio Eletto, Antonio Torre, Rocco Zaccagnino
This paper presents the design, implementation and testing of a neural network for the functional harmonization of a bass line. The overall network consists of three base networks that are used in parallel under the control of an additional network that, at each step, chooses the best output from the three base networks. All the neural networks have been trained using J.S. Bach's chorales. In order to evaluate the networks, a metric measuring the distance of the output from the original J.S. Bach's harmonization is defined.
Graph-based Evolution of Visual Languages
Penousal Machado, Henrique Nunes, Juan Romero, Jorge Tavares
We present a novel evolutionary engine for the evolution of context free grammars. The system relies on specially designed graph-based crossover and mutation operators. While in most evolutionary art systems each individual corresponds to a single artwork, in our approach each individual is a context free grammar that specifies a family of shapes following the same production rules. To assess the adequacy and completeness of the system we perform experiments using automated fitness assignment and user-guided evolution. The experimental results show that the system is able to create diverse and interesting families of shapes even when the initial population is composed of minimal grammars.
Combining Musical Constraints with Markov Transition Probabilities to Improve the Generation of Creative Musical Structures
Stephen Davismoon, John Eccles
This paper explores a fundamental dilemma regularly faced by any composer engaged in computer-aided composition: the generation of musically 'meaningful' or 'sensible' musical structures beyond those of a very localized nature. Initially an outline of the uses of Markov processes in music is given, highlighting their strengths and weaknesses. There then follows a brief discussion describing some of the many constraints (cultural and otherwise) that have been and continue to be placed upon us all as we engage with music that emanates from relatively localized regions of the sonic continuum. Finally, through the combination of additional musical constraints with Markov transition probabilities within a stochastic optimization process, specific improvements in creating sensible musical structures are described.
Evolving Artistic Styles through Visual Dialogues
Jae Oh, Edward Zajec
We describe an interactive art that can facilitate visual dialogues with a user and reveal the user's compositional proclivity. The system invites the user for a visual dialogue, initially presenting two compositions in distinct styles. Then, the user "converses" with the system by responding. As the interactions continue, the user starts to experience a tendency evolving in the compositions--much the same way as in a dialogue between two people. Throughout the interactions, the evolutionary process brings out a certain sense of self-reflection to the user. The product of the dialogue is an experience in self-reflection in visual proclivity. I3 was exhibited to the public in two international art forums.
Musical Composer Identification through Probabilistic and Feed Forward Neural Networks
Kaliakatsos-Papakostas Maximos, Epitropakis Michael, Vrahatis Michael
During the last decade many efforts for music information retrieval have been made utilizing Computational Intelligence methods. Here, we examine the information capacity of the Dodecaphonic Trace Vector for composer classification and identification. To this end, we utilize Probabilistic Neural Networks for the construction of a "similarity matrix" of different composers and analyze the Dodecaphonic Trace Vector's ability to identify a composer through trained Feedforward Neural Networks. The training procedure is based on classical gradient-based methods as well as on the Differential Evolution algorithm. An experimental analysis on the pieces of seven classical composers is presented to gain insight about the most important strengths and weaknesses of the aforementioned approach.
Estimation Distribution Differential Evolution
Ernesto Mininno, Ferrante Neri
This paper proposes a novel adaptation scheme for Differential Evolution (DE) frameworks. The proposed algorithm, namely Estimation Distribution Differential Evolution (EDDE), is based on a DE structure and employs randomized scale factor ad crossover rate values. These values are sampled from truncated Gaussian probability distribution functions. These probability functions adaptively vary during the optimization process. At the beginning of the optimization the truncated Gaussian functions are characterized by a large standard deviation values and thus are similar to uniform distributions. During the later stages of the evolution, the probability functions progressively adapt to the most promising values attempting to detect the optimal working conditions of the algorithm. The performance offered by the proposed algorithm has been compared with those given by three modern DE based algorithms which represent the state-of-the-art in DE. Numerical results show that the proposed EDDE, despite its simplicity, is competitive with the other algorithms and in many cases displays a very good performance in terms of both final solution detected and convergence speed.
A Directed Mutation Operator for Real Coded Genetic Algorithms
Imtiaz Korejo, Shengxiang Yang, Changhe Li
Developing directed mutation methods has been an interesting research topic to improve the performance of genetic algorithms (GAs) for function optimization. This paper introduces a directed mutation (DM) operator for GAs to explore promising areas in the search space. In this DM method, the statistics information regarding the fitness and distribution of individuals over intervals of each dimension is calculated according to the current population and is used to guide the mutation of an individual toward the neighboring interval that has the best statistics result in each dimension. Experiments are carried out to compare the proposed DM technique with an existing directed variation on a set of benchmark test problems. The experimental results show that the proposed DM operator achieves a better performance than the directed variation on most test problems.
Parameter Tuning of Evolutionary Algorithms: Generalist vs. Specialist
S. K. Smit, A. E. Eiben
Finding appropriate parameter values for Evolutionary Algorithms (EAs) is one of the persistent challenges of Evolutionary Computing. In recent publications we showed how the REVAC (Relevance Estimation and VAlue Calibration) method is capable to find good EA parameter values for single problems. Here we demonstrate that REVAC can also tune an EA to a set of problems (a whole test suite). Hereby we obtain robust, rather than problem-tailored, parameter values and an EA that is a 'generalist', rather than a 'specialist'. The optimized parameter values prove to be different from problem to problem and also different from the values of the generalist. Furthermore, we compare the robust parameter values optimized by REVAC with the supposedly robust conventional values and see great differences. This suggests that traditional settings might be far from optimal, even if they are meant to be robust.
Design of Continuous Controllers using a Multiobjective Differential Evolution Algorithm with Spherical Pruning
Gilberto Reynoso-Meza, Javier Sanchis, Xavier Blasco, Miguel Martínez
Controller design has evolved to a multiobjective task, i.e., today is necessary to take into account, besides any performance requirement, robustness requisites, frequency domain specifications and uncertain model parameters in the design process. The designer (control engineer), as Decision Maker, has to select the best choice according to his preferences and the trade-off he wants to achieve between conflicting objectives. In this work, a new multiobjective optimization approach using Differential Evolution (DE) algorithm is presented for the design of (but not limited to) Laplace domain controllers. The methodology is used to propose a set of solutions for an engineering control benchmark, all of them non-dominated and pareto-optimal. The obtained results shows the viability of this approach to give a higher degree of flexibility to the control engineer at the decision making stage.
Speedups between x70 and x120 for a Generic Local Search (Memetic) Algorithm on a Single GPGPU chip
Frédéric Krüger, Ogier Maitre, Pierre Collet
This paper presents the first implementation of a generic memetic algorithm on one of the two GPU (Graphic Processing Unit) chips of a GTX295 gaming card. Observed speedups range between x70 and x120, mainly depending on the population size. An automatic parallelization of a memetic algorithm is provided through an upgrade of the EASEA language, so that the EC community can benefit from the extraordinary power of these cards without needing to program them.
Advancing Model-Building for Many-Objective Optimization Estimation of Distribution Algorithms
Luis Martí, Jesús García, Antonio Berlanga, José M. Molinavv
In order to achieve a substantial improvement of MOEDAs regarding MOEAs it is necessary to adapt their model-building algorithms. Most current model--building schemes used so far off-the-shelf machine learning methods. These methods are mostly error-based learning algorithms. However, the model-building problem has specific requirements that those methods do not meet and even avoid. In this work we dissect this issue and propose a set of algorithms that can be used to bridge the gap of MOEDA application. A set of experiments are carried out in order to sustain our assertions.
Parallel Random Injection Differential Evolution
Matthieu Weber, Ferrante Neri, Ville Tirronen
This paper proposes the introduction of a generator of random individuals within the ring topology of a Parallel Differential Evolution algorithm. The generated random individuals are then injected within a sub-population. A crucial point in the proposed study is that a proper balance between migration and random injection can determine the success of a distributed Differential Evolution scheme. An experimental study of this balance is carried out in this paper. Numerical results show that the proposed Parallel Random Injection Differential Evolution seems to be a simple, robust, and efficient algorithm which can be used for various applications. An important finding of this paper is that premature convergence problems due to an excessively frequent migration can be overcome by the injection of random individuals. In this way, the resulting algorithm maintains the high convergence speed properties of a parallel algorithm with high migration but differs in that it is able to continue improving upon the available genotypes and detect high quality solutions.
Effect of Spatial Locality on An Evolutionary Algorithm for Multimodal Optimization
Ka-Chun Wong, Kwong-Sak Leung, Man-Hon Wong
To explore the effect of spatial locality, crowding differential evolution is incorporated with spatial locality for multimodal optimization. Instead of random trial vector generations, it takes advantages of spatial locality to generate fitter trial vectors. Experiments were conducted to compare the proposed algorithm (CrowdingDE-L) with the state-of-the-art algorithms. Further experiments were also conducted on a real world problem. The experimental results indicate that CrowdingDE-L has a competitive edge over the other algorithms tested.
Gaussian Adaptation Revisited - an Entropic View on Covariance Matrix Adaptation
Christian L. Müller, Ivo F. Sbalzarini
We revisit Gaussian Adaptation (GaA), a black-box optimizer for discrete and continuous problems that has been developed in the late 1960's. This largely neglected search heuristic shares several interesting features with the well-known Covariance Matrix Adaptation Evolution Strategy (CMA-ES) and with Simulated Annealing (SA). GaA samples single candidate solutions from a multivariate normal distribution and continuously adapts its first and second moments (mean and covariance) such as to maximize the entropy of the search distribution. Sample-point selection is controlled by a monotonically decreasing acceptance threshold, reminiscent of the cooling schedule in SA. We describe the theoretical foundations of GaA and analyze some key features of this algorithm. We empirically show that GaA converges log-linearly on the sphere function and analyze its behavior on selected non-convex test functions.
Automatically Modeling Hybrid Evolutionary Algorithms from Past Executions
Santiago Muelas, José-María Peña, Antonio LaTorre
The selection of the most appropriate Evolutionary Algorithm for a given optimization problem is a difficult task. Hybrid Evolutionary Algorithms are a promising alternative to deal with this problem. By means of the combination of different heuristic optimization approaches, it is possible to profit from the benefits of the best approach, avoiding the limitations of the others. Nowadays, there is an active research in the design of dynamic or adaptive hybrid algorithms. However, little research has been done in the automatic learning of the best hybridization strategy. This paper proposes a mechanism to learn a strategy based on the analysis of the results from past executions. The proposed algorithm has been evaluated on a well-known benchmark on continuous optimization. The obtained results suggest that the proposed approach is able to learn very promising hybridization strategies.
Exploiting Evolution for an Adaptive Drift-Robust Classifier in Chemical Sensing
Stefano Di Carlo, Matteo Falasconi, Ernesto Sanchez, Alberto Scionti, Giovanni Squillero, Alberto Tonda
Gas chemical sensors are strongly affected by drift, i.e., changes in sensors’ response with time, that may turn statistical models commonly used for classification completely useless after a period of time. This paper presents a new classifier that embeds an adaptive stage able to reduce drift effects. The proposed system exploits a state-of-the-art evolutionary strategy to iteratively tweak the coefficients of a linear transformation able to transparently transform raw measures in order to mitigate the negative effects of the drift. The system operates continuously. The optimal correction strategy is learnt without a-priori models or other hypothesis on the behavior of physical-chemical sensors. Experimental results demonstrate the efficacy of the approach on a real problem.
Multi-Objective Probability Collectives
Antony Waldock, David Corne
We describe and evaluate a multi-objective optimisation (MOO) algorithm that works within the Probability Collectives (PC) optimisation framework. PC is an alternative approach to optimization where the optimization process focusses on finding an ideal distribution over the solution space rather than an ideal solution. We describe one way in which MOO can be done in the PC framework, via using a Pareto-based ranking strategy as a single objective. We partially evaluate this via test-ing on a number of problems, and compare the results with state of the art alternatives. We find that this first multi-objective probability collectives (MOPC) approach performs competitively, indicating both clear promise, and clear room for improvement.
A New Selection Ratio for Large Population Sizes
Motivated by parallel optimization, we study the Self-Adaptation algorithm for large population sizes. We first show that the current version of this algorithm does not reach the theoretical bounds, then we propose a very simple modification, in the selection part of the evolution process. We show that this simple modification leads to big improvement of the speed-up when the population size is large.
Investigating the Local-Meta-Model CMA-ES for Large Population Sizes
Zyed Bouzarkouna, Anne Auger, Didier Yu Ding
For many real-life engineering optimization problems, the cost of one objective function evaluation can take several minutes or hours. In this context, a popular approach to reduce the number of function evaluations consists in building a (meta-)model of the function to be optimized using the points explored during the optimization process and replacing some (true) function evaluations by the function values given by the meta-model. In this paper, the local-meta-model CMA-ES (lmm-CMA) proposed by Kern et al. in 2006 coupling local quadratic meta-models with the Covariance Matrix Adaptation Evolution Strategy is investigated. The scaling of the algorithm with respect to the population size is analyzed and limitations of the approach for population sizes larger than the default one are shown. A new variant for deciding when the meta-model is accepted is proposed. The choice of the recombination type is also investigated to conclude that the weighted recombination is the most appropriate. Finally, this paper illustrates the influence of the different initial parameters on the convergence of the algorithm for multimodal functions.
Parallel Genetic Algorithm on the CUDA Architecture
Petr Pospíchal, Jiří Jaroš, Josef Schwarz
This paper deals with the mapping of the parallel island-based genetic algorithm with unidirectional ring migrations to nVidia CUDA software model. The proposed mapping is tested using Rosenbrock's, Griewank's and Michalewicz's benchmark functions. The obtained results indicate that our approach leads to speedups up to seven thousand times higher compared to one CPU thread while maintaining a reasonable results quality. This clearly shows that GPUs have a potential for acceleration of GAs and allow to solve much complex tasks.
Memory Design for Constrained Dynamic Optimization Problems
A proposal for a memory design is given that is suitable for solving constrained dynamic optimization problems by an evolutionary algorithm. Based on ideas from abstract memory, two schemes, blending and censoring, are introduced and tested. Using a new benchmark we show in numerical experiments that such a memory can improve solving certain types of constrained dynamic problems.
Multi-population Genetic Algorithms with Immigrants Scheme for Dynamic Shortest Path Routing Problems in Mobile Ad Hoc Networks
Hui Cheng, Shengxiang Yangv
The static shortest path (SP) problem has been well addressed using intelligent optimization techniques, e.g., artificial neural networks, genetic algorithms (GAs), particle swarm optimization, etc. However, with the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile ad hoc network (MANET), wireless mesh network, etc. One of the most important characteristics in mobile wireless networks is the topology dynamics, that is, the network topology changes over time due to energy conservation or node mobility. Therefore, the SP problem turns out to be a dynamic optimization problem in mobile wireless networks. In this paper, we propose to use multi-population GAs with immigrants scheme to solve the dynamic SP problem in MANETs which is the representative of new generation wireless networks. The experimental results show that the proposed GAs can quickly adapt to the environmental changes (i.e., the network topology change) and produce good solutions after each change.
Measuring Fitness Degradation in Dynamic Optimization Problems
Enrique Alba, Briseida Sarasola
Measuring the performance of algorithms over dynamic optimization problems (DOPs) presents some important differences when compared to static ones. One of the main problems is the loss of solution quality as the optimization process advances in time. The objective in DOPs is tracking the optima as the landscape changes; however it is possible that the algorithm fails to follow the optima after some changes happened. The main goal in this article is to introduce a new way of measuring how algorithms are able to maintain their performance during the dynamic optimization process. We propose a measure based on linear regression and study its behaviour. In order to do so, we study a scenario based on the moving peaks benchmark and analyze our results using several metrics existing in the literature. We test our measure for degradation on the same scenario and obtain results which help us to explain changes in algorithm performances.
Handling Undefined Vectors in Expensive Optimization Problems
When using computer simulations in engineering design optimization one often encounters vectors which 'crash' the simulation and so no fitness is associated with them. In this paper we refer to these as undefined vectors since the objective function is undefined there. Since each simulation run (a function evaluation) is expensive (anywhere from minutes to weeks of CPU time) only a small number of evaluations are allowed during the entire search and so such undefined vectors pose a risk of consuming a large portion of the optimization 'budget' thus stalling the search. To manage this open issue we propose a classification-assisted framework for expensive optimization problems, that is, where candidate vectors are classified in a pre-evaluation stage whether they are defined or not. We describe: a) a baseline single-classifier framework (no undefined vectors in the model) b) a non-classification assisted framework (undefined vectors in the model) and c) an extension of the classifier-assisted framework to a multi-classifier setup. Performance analysis using a test problem of airfoil shape optimization shows: a) the classifier-assisted framework obtains a better solution compared to the non-classification assisted one and b) the classifier can data-mine the accumulated information to provide new insights into the problem being solved.
Adaptive Noisy Optimization
Philippe Rolet, Olivier Teytaud
In this paper, adaptive noisy optimization on variants of the noisy sphere model is considered, i.e. optimization in which the same algorithm is able to adapt to several frameworks, including some for which no bound has never been derived. Incidentally, bounds derived by  for noise quickly decreasing to zero around the optimum are extended to the more general case of a positively lower-bounded noise thanks to a careful use of Bernstein bounds (using empirical estimates of the variance) instead of Chernoff-like variants.
Noise Analysis Compact Genetic Algorithm
Ferrante Neri, Ernesto Mininno, Tommi Kärkkäinenv
This paper proposes the Noise Analysis compact Genetic Algorithm (NAcGA). This algorithm integrates a noise analysis component within a compact structure. This fact makes the proposed algorithm appealing for those real-world applications characterized by the necessity of a high performance optimizer despite severe hardware limitations. The noise analysis component adaptively assigns the amount of fitness evaluations to be performed in order to distinguish two candidate solutions. In this way, it is assured that computational resources are not wasted and the selection of the most promising solution is correctly performed. The noise analysis employed in this algorithm spouses very well the pair-wise comparison logic typical of compact evolutionary algorithms. Numerical results show that the proposed algorithm significantly improves upon the performance, in noisy environments, of the standard compact genetic algorithm. Two implementation variants based on the elitist strategy have been tested in this studies. It is shown that the nonpersistent strategy is more robust to the noise than the persistent one and therefore its implementation seems to be advisable in noisy environments.
Particle Swarm Optimization and an Agent-Based Algorithm for a Problem of Staff Scheduling
Maik Guenther, Volker Nissen
Eight problems of a practical staff scheduling application from logistics are used to compare the effectiveness and efficiency of two fundamentally different solution approaches. One can be called centralized and is based on search in the solution space with an adapted metaheuristic, namely particle swarm optimization (PSO). The second approach is decentralized. Artificial agents negotiate to construct a staff schedule. Both approaches significantly outperform todays manual planning. PSO delivers the best overall results in terms of solution quality and is the method of choice, when CPU-time is not limited. The agent approach is vastly quicker in finding solutions of almost the same quality as PSO. The results suggest that agents could be an interesting method for real-time scheduling or re-scheduling tasks.
Using an Evolutionary Algorithm to Discover Low CO2 tours within a Travelling Salesman Problem
Neil Urquhart, Cathy Scott, Emma Hart
This paper examines the issues surrounding the effects of using vehicle emissions as the fitness criteria when solving routing problems using evolutionary techniques. The case-study examined is that of the Travelling Salesman Problem (TSP) based upon the road network within the City of Edinburgh, Scotland. A low cost path finding algorithm (A*) is used to build paths through the street network between delivery points. The EA is used to discover tours that utilise paths with low emissions characteristics. Two methods of estimating CO2 emissions are examined; one that utilises a fuel consumption model and applies it to an estimated drive cycle and one that applies a simplistic CO2 calculation model that focuses on average speeds over street sections. The results of these two metrics are compared with each other and with results obtained using a traditional distance metric.
An Evolutionary Approach to the Traveling Salesman Problem with Pickup and Delivery using Depot Removal and Insertion Moves
Volkan Cinar, Temel Oncan, Haldun Sural
In this work, we consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD), which is an extension of the well-known NP-hard Traveling Salesman Problem. We propose a Genetic Algorithm (GA) based on a specially tailored tour improvement procedure for the TSPPD. Computational experiments are reported on the test instances taken from the literature. The experimental results suggest that the proposed GA yields a promising performance in terms of both accuracy and efficiency compared to existing algorithms in the literature.
A Math-heuristic for the Multi-level Capacitated Lot Sizing Problem with Carryover
Marco Caserta, Adriana Ramirez, Stefan Voss
We present a math-heuristic algorithm for the lot sizing problem with carryover. The proposed algorithm uses mathematical programming techniques in a metaheuristic fashion to iteratively solve smaller portions of the original problem. More specifically, we draw ideas from the corridor method to design and impose exogenous constraints on the original problem and, subsequently, we solve to optimality the constrained problem using a MIP solver. The algorithm iteratively builds new corridors around the best solution found within each corridor and, therefore, explores adjacent portions of the search space. In the attempt of fostering diversification while exploring the original search space, we generate a pool of incumbent solutions for the corridor method and, therefore, we reapply the corridor method using different starting points. The algorithm has been tested on instances of a standard benchmark library and the reported results show the robustness and effectiveness of the proposed scheme.
Fast Approximation Heuristics for Multi-Objective Vehicle Routing Problems
Martin Josef Geiger
The article describes an investigation of the use of fast approximation heuristics for multi-objective vehicle routing problems (MO-VRP). We first present a constructive heuristic based on the savings approach, which we generalize to fit the particular multi-objective nature of the problem. Then, an iterative phase based on local search improves the solutions towards the Pareto-front. Experimental investigations on benchmark instances taken from the literature show that the required computational effort for approximating such problems heavily depends on the underlying structures of the data sets. The insights gained in our study are particularly valuable when giving recommendations on how to solve a particular MO-VRP or even a particular MO-VRP instance, e.g. by means of a posteriori or interactive optimization approaches.