Applications of Evolutionary Computation

Peer-to-peer (P2P) systems have attracted significant interest in recent years. In P2P networks, each peer act as both a server or a client. This characteristic makes peers vulnerable to a wide variety of attacks. Having robust trust management is very critical for such open environments to exclude unreliable peers from the system. This paper investigates the use of genetic programming to asses the trustworthiness of peers without a central authority. A trust management model is proposed in which each peer ranks other peers according to local trust values calculated automatically based on the past interactions and recommendations. The experimental results have shown that the model could successfully identify malicious peers without using a central authority or global trust values and, improve the system performance.

We investigate the Robust Multiperiod Network Design Problem, a generalization of the classical Capacitated Network Design Problem that additionally considers multiple design periods and provides solutions protected against traffic uncertainty. Given the intrinsic difficulty of the problem, which proves challenging even for state-of-the art commercial solvers, we propose a hybrid primal heuristic based on the combination of ant colony optimization and an exact large neighborhood search. Computational experiments on a set of realistic instances from the SNDlib show that our heuristic can find solutions of extremely good quality with low optimality gap.

Nowadays, wireless sensor networks (WSNs) are widely used in more and more fields of application. However, there are some important shortcomings which have not been solved yet in the current literature. This paper focuses on how to add relay nodes to previously established static WSNs with the purpose of optimizing three important factors: energy consumption, average coverage and network reliability. As this is an NP-hard multiobjective optimization problem, we consider two well-known genetic algorithms (NSGA-II and SPEA2) and a multiobjective approach of the variable neighborhood search algorithm (MO-VNS). These metaheuristics are used to solve the problem from a freely available data set, analyzing all the results obtained by considering two multiobjective quality indicators (hypervolume and set coverage). We conclude that MO-VNS provides better performance on average than the standard algorithms NSGA-II and SPEA2.

Due to the highly unpredictable topology of ad hoc networks, most of the existing communication protocols rely on different thresholds for adapting their behavior to the environment. Good performance is required under any circumstances. Therefore, finding the optimal configuration for those protocols and algorithms implemented in these networks is a complex task. We propose in this work to automatically fine tune the AEDB broadcasting protocol for MANETs thanks to the use of cooperative coevolutionary multi-objective evolutionary algorithms. AEDB is an advanced adaptive protocol based on the Distance Based broadcasting algorithm that acts differently according to local information to minimize the energy and network use, while maximizing the coverage of the broadcasting process. In this work, it will be fine tuned using multi-objective techniques in terms of the conflicting objectives: coverage, energy and network resources, subject to a broadcast time constraint. Because of the few parameters of AEDB, we defined new versions of the problem in which variables are discretized into bit-strings, making it more suitable for cooperative coevolutionary algorithms. Two versions of the proposed method are evaluated and compared versus the original NSGA-II, providing highly accurate tradeoff configurations in shorter execution times.

The paper concerns the use of Extremal Optimization (EO) technique in dynamic load balancing for optimized execution of distributed programs. EO approach is used to periodically detect the best candidates for task migration leading to balanced execution. To improve the quality of load balancing and decrease time complexity of the algorithms, we have improved EO by a local search of the best computing node to receive migrating tasks. The improved guided EO algorithm assumes a two-step stochastic selection based on two separate fitness functions. The functions are based on specific program models which estimate relations between the programs and the executive hardware. The proposed load balancing algorithm is compared against a standard EO-based algorithm with random placement of migrated tasks and a classic genetic algorithm. The algorithm is assessed by experiments with simulated load balancing of distributed program graphs and analysis of the outcome of the discussed approaches.

This manuscript addresses a vital task in any Public Land Mobile Network, the mobile location management. This management task is tackled following the Reporting Cells strategy. Basically, the Reporting Cells planning consists in selecting a subset of network cells as Reporting Cells with the aim of controlling the subscribers’ movement and minimizing the signaling traffic. In previous works, the Reporting Cells Planning Problem was optimized by using single-objective metaheuristics, in which the two objective functions were linearly combined. This technique simplifies the optimization problem but has got several drawbacks. In this work, with the aim of avoiding such drawbacks, we have adapted a well-known multiobjective metaheuristic: the Non-dominated Sorting Genetic Algorithm II (NSGAII). Furthermore, a multiobjective approach obtains a wide range of solutions (each one related to a specific trade-off between objectives), and hence, it gives the possibility of selecting the solution that best adjusts to the real state of the signaling network. The quality of our proposal is checked by means of an experimental study, where we demonstrate that our version of NSGAII outperforms other algorithms published in the literature.

Migration topology plays a key role in designing effective distributed evolutionary algorithms. In this work we investigate the impact of several network topologies on the performance of a stepping–stone structured Differential Evolution model. Although some issues on the control parameters of the migration process and the way they affect the efficiency of the algorithm and the solution quality deserve further evaluative study, the influence of the topology on the performance both in terms of solution quality and convergence rate emerges from the empirical findings carried out on a set of test problems.

Modern smartphones permit to run a large variety of applications, i.e. multimedia, games, social network applications, etc. However, this aspect considerably reduces the battery life of these devices. A possible solution to alleviate this problem is to offload part of the application or the whole computation to remote servers, i.e. Cloud Computing. The offloading cannot be performed without considering the issues derived from the nature of the application (i.e. multimedia, games, etc.), which can considerably change the resources necessary to the computation and the type, the frequency and the amount of data to be exchanged with the network. This work shows a framework for automatically building models for the offloading of mobile applications based on evolutionary algorithms and how it can be used to simulate different kinds of mobile applications and to analyze the rules generated. To this aim, a tool for generating mobile datasets, presenting different features, is designed and experiments are performed in different usage conditions in order to demonstrate the utility of the overall framework.

Artificial development has been widely used for designing complex structures and as a means to increase the complexity of an artifact. One central challenge in artificial development is to understand how a mapping process could work on a class of architectures in a more general way by exploiting the most favorable properties from each computational architecture or by combining efficiently more than one computational architectures (i.e., a true multicellular approach). Computational architectures in this context comprise structures with connected computational elements, namely, cellular automata and boolean networks. The ability to develop and co-evolve different computational architectures has previously been investigated using common developmental genomes. In this paper, we extend a previous work that studied their evolvability. Here, we focus on their ability to evolve when the goal changes over evolutionary time (i.e., adaptation), utilizing a more fair fitness assignment scheme. In addition, we try to investigate how common developmental genomes exploit the underlying architecture in order to build the phenotypes. The results show that they are able to find very good solutions with rather simplified solutions than anticipated.

Artificial multi-cellular organisms develop from a single zygote to complex morphologies, following the instructions encoded in their genomes. Small genome mutations can result in very different developed phenotypes. In this paper we investigate how to exploit genotype information in order to guide evolution towards favorable areas of the phenotype solution space, where the sought emergent behavior is more likely to be found. Lambda genome parameter, with its ability to discriminate different developmental behaviors, is incorporated into the fitness function and used as a discriminating factor for genetic distance, to keep resulting phenotype’s developmental behavior close by and encourage beneficial mutations that yield adaptive evolution. Genome activation patterns are detected and grouped into genome parameter sub-transitions. Different sub-transitions are investigated as simple genome parameters, or composed to integrate several genome properties into a more exhaustive composite parameter. The experimental model used herein is based on 2-dimensional cellular automata.

This paper aims at improving the training process of complex decision support systems, where evolutionary algorithms are used to integrate a large number of decision rules in a form of a weighted average. It proposes an enhancement of Differential Evolution by Locally Linear Embedding to process objective functions with correlated variables, which focuses on detecting local dependencies among variables of the objective function by analyzing the manifold in the search space that contains the current population and transforming it to a reduced search space. Experiments performed on some popular benchmark functions as well as on a financial decision support system confirm that the method may significantly improve the search process in the case of objective functions with a large number of variables, which usually occur in many practical applications.

The paper introduces a multi-deme, memetic global optimization strategy

Hierarchic memetic Strategy

(HMS) especially well-suited to the solution of a class of parametric inverse problems. This strategy develops dynamically a tree of dependent populations (demes) searching with the various accuracy growing from the root to the leaves. The search accuracy is associated with the accuracy of solving direct problems by

$$hp$$

–adaptive Finite Element Method. Throughout the paper we describe details of exploited accuracy adaptation and computational cost reduction mechanisms, an agent-based architecture of the proposed system, a sample implementation and preliminary benchmark results.

Various changes in energy production and consumption lead to new challenges for design and control mechanisms of the energy system. In particular, the intermittent nature of power generation from renewables asks for significantly increased load flexibility to support local balancing of energy demand and supply. This paper focuses on a flexible, generic energy management system for Smart Buildings in real-world applications, which is already in use in households and office buildings. The major contribution is the design of a “plug-and-play”-type Evolutionary Algorithm for optimizing distributed generation, storage and consumption using a sub-problem based approach. Relevant power consuming or producing components identify themselves as sub-problems by providing an abstract specification of their genotype, an evaluation function and a back transformation from an optimized genotype to specific control commands. The generic optimization respects technical constraints as well as external signals like variable energy tariffs. The relevance of this approach to energy optimization is evaluated in different scenarios. Results show significant improvements of self-consumption rates and reductions of energy costs.

In this article, we propose DYNAMOP (DYNAmic programming using Metaheuristic for Optimization Problems) a new dynamic programming based on genetic algorithm to solve a hydro-scheduling problem. The representation which is based on a path in the graph of states of dynamic programming is adapted to dynamic structure of the problem and it allows to hybridize easily evolutionary algorithms with dynamic programming. DYNAMOP is tested on two case studies of hydro-scheduling problem with different price scenarios. Experiments indicate that the proposed approach performs considerably better than classical genetic algorithms and dynamic programming.

We investigate different

evolutionary algorithm

(EA) variants for structural optimization of energy supply systems and compare them with a deterministic optimization approach. The evolutionary algorithms enable structural optimization avoiding to use an underlying superstructure model. As result of the optimization, we are interested in multiple good alternative designs, instead of the one single best solution only. This problem has three levels: On the top level, we need to fix a structure; based on that structure, we then have to select facility sizes; finally, given the structure and equipment sizing, on the bottom level, the equipment operation has to be specified to satisfy given energy demands. In the presented optimization approach, these three levels are addressed simultaneously. We compare EAs acting on the top level (the lower levels are treated by a

mixed-integer linear programming

(MILP) solver) against an MILP-only-approach and are highly interested in the ability of both methods to deliver multiple different solutions and the time required for performing this task.

Neither state-of-the-art EA for numerical optimization nor standard measures or visualizations are applicable to the problem. This lack of experience makes it difficult to understand why different EA variants perform as they do (e.g., for stating

how

different two structures are), we introduce a distance concept for structures. We therefore introduce a short code, and, based on this short code, a distance measure that is employed for a

multidimensional scaling

(MDS) based visualization. This is meant as first step towards a better understanding of the problem landscape. The algorithm comparison shows that deterministic optimization has advantages if we need to find the global optimum. In contrast, the presented EA variants reliably find multiple solutions very quickly if the required solution accuracy is relaxed. Furthermore, the proposed distance measure enables visualization revealing interesting problem properties.

CPPN-NEAT (Compositional Pattern Producing Networks and NeuroEvolution for Augmented Topologies) is a representation and optimisation approach that can generate and optimise complex forms without any pre-defined structure by using indirect, implicit representations. CPPN is based on an analogy to embryonic development; NEAT is based on an analogy to neural evolution. We present new developments that extend the approach to include multi-material objects, where the material distribution must be optimised in parallel with the form.

Results are given for a simple problem concerning PV panels to validate the method. This approach is applicable to a large number of problems concerning the design of complex forms. There are many such problems in the field of energy saving and generation, particularly those areas concerned with solar gain. This work forms a first step in exploring the potential of this approach.

Current frameworks for identifying trading agents using machine learning are able to simultaneously address the characterization of both technical indicator and decision tree. Moreover, multi-agent frameworks have also been proposed with the goal of improving the reliability and trust in the agent policy identified. Such advances need weighing against the computational overhead of assuming such flexibility. In this work a framework for evolutionary multi-agent trading is introduced and systematically benchmarked for FX currency trading; including the impact of FX trading spread. It is demonstrated that simplifications can be made to the ‘base’ trading agent that do not impact on the quality of solutions, but provide considerable computational speedups. The resulting evolutionary multi-agent architecture is demonstrated to provide significant benefits to the profitability and improve the reliability with which profitable policies are returned.

We cast financial trading as a symbolic regression problem on the lagged time series, and test a state of the art symbolic regression method on it. The system is geometric semantic genetic programming, which achieves good performance by converting the fitness landscape to a cone landscape which can be searched by hill-climbing. Two novel variants are introduced and tested also, as well as a standard hill-climbing genetic programming method. Baselines are provided by buy-and-hold and ARIMA. Results are promising for the novel methods, which produce smaller trees than the existing geometric semantic method. Results are also surprisingly good for standard genetic programming. New insights into the behaviour of geometric semantic genetic programming are also generated.

In this paper, we study from the perspective of an insurance company the

Reinsurance Contract Placement problem

. Given a reinsurance contract consisting of a fixed number of layers and a set of expected loss distributions (one per layer) as produced by a Catastrophe Model, plus a model of current costs in the global reinsurance market, identifying optimal combinations of placements (percent shares of sub-contracts) such that for a given expected return the associated risk value is minimized. Our approach explores the use bio-inpired metaheuristics with the goal of determining which evolutionary optimization approach leads to the best results for this problem, while being executable in a reasonable amount of time on realistic industrial sized problems.

Adaptive algebraic level-set segmentation algorithm of financial time series is presented in this paper. The proposed algorithm is based on the algebraic one step-forward predictor with internal smoothing, which is used to identify a near optimal algebraic model. Particle swarm optimization algorithm is exploited for the detection of a base algebraic fragment of the time series. A combinatorial algorithm is used to detect intervals where predictions are lower than a predefined level. Moreover, the combinatorial algorithm does assess the simplicity of the identified near optimal algebraic model. Automatic adaptive identification of quasi-stationary segments can be employed for complex financial time series.

This paper presents a realistic study of applying a gene regulatory model to financial prediction. The combined adaptation of evolutionary and developmental processes used in the model highlight its suitability to dynamic domains, and the results obtained show the potential of this approach for real-world trading.

This paper concerns optimization of trading experts that are used for generating investment decisions. A population of trading experts is optimized using a dynamic evolutionary algorithm. In the paper a new method is proposed which allows analyzing and visualizing the behaviour of optimized trading experts over a period of time. The application of this method resulted in an observation that during certain intervals of time the behaviour of the optimized trading experts becomes more stable.

Financial forecasting is a vital area in computational finance, where several studies have taken place over the years. One way of viewing financial forecasting is as a classification problem, where the goal is to find a model that represents the predictive relationships between predictor attribute values and class attribute values. In this paper we present a comparative study between two bio-inspired classification algorithms, a genetic programming algorithm especially designed for financial forecasting, and an ant colony optimization one, which is designed for classification problems. In addition, we compare the above algorithms with two other state-of-the-art classification algorithms, namely C4.5 and RIPPER. Results show that the ant colony optimization classification algorithm is very successful, significantly outperforming all other algorithms in the given classification problems, which provides insights for improving the design of specific financial forecasting algorithms.

This paper addresses the issue of discovering frequent patterns in order book shapes, in the context of the stock market depth, for ultra-high frequency data. It proposes a computational intelligence approach to building frequent patterns by clustering order book shapes with Self-Organizing Maps. An experimental evaluation of the approach proposed on the London Stock Exchange Rebuild Order Book database succeeded with providing a number of characteristic shape patterns and also with estimating probabilities of some typical transitions between shape patterns in the order book.

We compare Temporal Difference Learning (TDL) with Coevolutionary Learning (CEL) on Othello. Apart from using three popular single-criteria performance measures: (i) generalization performance or expected utility, (ii) average results against a hand-crafted heuristic and (iii) result in a head to head match, we compare the algorithms using performance profiles. This multi-criteria performance measure characterizes player’s performance in the context of opponents of various strength. The multi-criteria analysis reveals that although the generalization performance of players produced by the two algorithms is similar, TDL is much better at playing against strong opponents, while CEL copes better against weak ones. We also find out that the TDL produces less diverse strategies than CEL. Our results confirms the usefulness of performance profiles as a tool for comparison of learning algorithms for games.

Flocking strategies are sets of behavior rules for the interaction of agents that allow to devise controllers with reduced complexity that generate emerging behavior. In this paper, we present an application of genetic algorithms and flocking strategies to control the Ghost Team in the game Ms. Pac-Man. In particular, we define flocking strategies for the Ghost Team and optimize them for robustness with respect to the stochastic elements of the game and effectivity against different possible opponents by means of genetic algorithm. The performance of the methodology proposed is tested and compared with that of other standard controllers. The results show that flocking strategies are capable of modeling complex behaviors and produce effective and challenging agents.

In this paper we present a search-based approach for procedural generation of game levels that represents levels as sequences of

micro-patterns

and searched for

meso-patterns

. The micro-patterns are “slices” of original human-designed levels from an existing game, whereas the meso-patters are abstractions of common design patterns seen in the same levels. This method generates levels that are similar in style to the levels from which the original patterns were extracted, while still allowing for considerable variation in the geometry of the generated levels. The evolutionary method for generating the levels was tested extensively to investigate the distribution of micro-patterns used and meso-patterns found.

Ant Colony Optimization (ACO) has been successfully applied to a wide number of complex and real domains. From classical optimization problems to video games, these kind of swarm-based approaches have been adapted, to be later used, to search for new meta-heuristic based solutions. This paper presents a simple ACO algorithm that uses a specifically designed heuristic, called common-sense, which has been applied in the classical video game

Lemmings

. In this game a set of

lemmings

must reach the exit point of each level, using a subset of finite number of skills, taking into account the contextual information given from the level. The paper describes both the graph model and the context-based heuristic, designed to implement our ACO approach. Afterwards, two different kind of simulations have been carried out to analyse the behaviour of the ACO algorithm. On the one hand, a micro simulation, where each ant is used to model a lemming, and a macro simulation where a swarm of lemmings is represented using only one ant. Using both kind of simulations, a complete experimental comparison based on the number and quality of solutions found and the levels solved, is carried out to study the behaviour of the algorithm under different game configurations.

This paper describes a new adaptive Monte Carlo Tree Search (MCTS) algorithm that uses evolution to rapidly optimise its performance. An evolutionary algorithm is used as a source of control parameters to modify the behaviour of each iteration (i.e. each simulation or roll-out) of the MCTS algorithm; in this paper we largely restrict this to modifying the behaviour of the random default policy, though it can also be applied to modify the tree policy.

This method of tightly integrating evolution into the MCTS algorithm means that evolutionary adaptation occurs on a much faster time-scale than has previously been achieved, and addresses a particular problem with MCTS which frequently occurs in real-time video and control problems: that uniform random roll-outs may be uninformative.

Results are presented on the classic Mountain Car reinforcement learning benchmark and also on a simplified version of Space Invaders. The results clearly demonstrate the value of the approach, significantly outperforming “standard” MCTS in each case. Furthermore, the adaptation is almost immediate, with no perceptual delay as the system learns: the agent frequently performs well from its very first game.

Automatically generating computer animations is a challenging and complex problem with applications in games and film production. In this paper, we investigate how to translate a shot list for a virtual scene into a series of virtual camera configurations — i.e automatically controlling the virtual camera. We approach this problem by modelling it as a dynamic multi-objective optimisation problem and show how this metaphor allows a much richer expressiveness than a classical single objective approach. Finally, we showcase the application of a multi-objective evolutionary algorithm to generate a shot for a sample game replay and we analyse the results.

This paper presents an approach based in an evolutionary algorithm, aimed to improve the behavioral parameters which guide the actions of an autonomous agent (bot) inside the real-time strategy game, Planet Wars. The work describes a co-evolutionary implementation of a previously presented method GeneBot, which yielded successful results, but focused in 4vs matches this time. Thus, there have been analyzed the effects of considering several individuals to be evolved (improved) at the same time in the algorithm, along with the use of three different fitness functions measuring the goodness of each bot in the evaluation. They are based in turns and position, and also in mathematical computations of linear regression and area regarding the number of ships belonging to the bot/individual to be evaluated. In addition, the variance of using an evolutionary algorithm with and without previous knowledge in the co-evolution phase is also studied, i.e., respectively using specific rivals to perform the evaluation, or just considering to this end individuals in the population being evolved. The aim of these co-evolutionary approaches are mainly two: first, reduce the computational time; and second find a robust fitness function to be used in the generation of evolutionary bots optimized for 4vs battles.

2-Player games in general provide a popular platform for research in Artificial Intelligence (AI). One of the main challenges coming from this platform is approximating a Nash Equilibrium (NE) over zero-sum matrix games. While the problem of computing such a Nash Equilibrium is solvable in polynomial time using Linear Programming (LP), it rapidly becomes infeasible to solve as the size of the matrix grows; a situation commonly encountered in games. This paper focuses on improving the approximation of a NE for matrix games such that it outperforms the state-of-the-art algorithms given a finite (and rather small) number

$$T$$

of oracle requests to rewards. To reach this objective, we propose to share information between the different relevant pure strategies. We show both theoretically by improving the bound and empirically by experiments on artificial matrices and on a real-world game that information sharing leads to an improvement of the approximation of the NE.

In the study of evolutionary game theory, a tool called the fingerprint was developed. This mathematical technique generates a functional summary of an arbitrary game-playing strategy independent of representational details. Using this tool, this study expands the boundaries of investigating an entire small state space of strategies, to wit the probabilistic 1-state tranducers, as a representation for playing iterated Prisoner’s Dilemma. A sampled grid of 35,937 strategies out of the continuous cube was used: they are fingerprinted and pairwise distances computed. A subsampled grid of 4,913 strategies was analyzed using metric multidimensional scaling. The results show that the known 3-dimensional manifold can be embedded into around 4–5 Euclidean dimensions without self-intersection, and the curvature of the fingerprint metric with respect to standard distance is not too extreme; there is also similarity with analogous results on other state spaces.

This work presents the results obtained from comparing different tree depths in a Genetic Programming Algorithm to create agents that play the Planet Wars game. Three different maximum levels of the tree have been used (3, 7 and Unlimited) and two bots available in the literature, based on human expertise, and optimized by a Genetic Algorithm have been used for training and comparison. Results show that in average, the bots obtained using our method equal or outperform the previous ones, being the maximum depth of the tree a relevant parameter for the algorithm.

Verification is increasingly becoming a bottleneck in the process of designing electronic circuits. While there exists several verification tools that assist in detecting occurrences of design errors, or bugs, there is a lack of solutions for accurately pin-pointing the root causes of these errors. Statistical bug localization has proven to be an approach that scales up to large designs and is widely utilized both in debugging hardware and software. However, the accuracy of localization is highly dependent on the quality of the stimuli. In this paper we formulate diagnostic test set generation as a task for an evolutionary algorithm, and propose dedicated fitness functions that closely correlate with the bug localization capabilities. We perform experiments on the register-transfer level design of the Plasma microprocessor coupling an evolutionary test-pattern generator and a simulator for fitness evaluation. As a result, the diagnostic resolution of the tests is significantly improved.

Dense pixel matching is an essential step required by many computer vision applications. While a large body of work has addressed quite successfully the rectified scenario, accurate pixel correspondence between an image and a distorted version remains very challenging. Exploiting an analogy between sequences of genetic material and images, we propose a novel genetics inspired algorithm where image variability is treated as the product of a set of image mutations. As a consequence, correspondence for each scanline of the initial image is formulated as the optimisation of a path in the second image minimising a fitness function penalising mutations. This optimisation is performed by a evolutionary algorithm which, in addition to provide fast convergence, implicitly ensures consistency between successive scanlines. Performance evaluation on locally and globally distorted images validates our bio-inspired approach.

Typically, a single natural image is not sufficient to train a program to extract edge features in edge detection when only training images and their ground truth are provided. However, a single training image might be considered as proper training data when domain knowledge, such as used in Gaussian-based edge detection, is provided. In this paper, we employ Genetic Programming (GP) to automatically evolve Gaussian-based edge detectors to extract edge features based on training data consisting of a single image only. The results show that a single image with a high proportion of true edge points can be used to train edge detectors which are not significantly different from rotation invariant surround suppression. When the programs separately evolved from eight single images are considered as weak classifiers, the combinations of these programs perform better than rotation invariant surround suppression.

This paper investigates how Felzenszwalb’s and Huttenlocher’s graph-based segmentation algorithm can be improved by automatic programming. We show that computers running Automatic Design of Algorithms Through Evolution (ADATE), our system for automatic programming, have induced a new graph-based algorithm that is 12 percent more accurate than the original without affecting the runtime efficiency. The result shows that ADATE is capable of improving an effective image segmentation algorithm and suggests that the system can be used to improve image analysis algorithms in general.

Feature construction can improve the classification performance by constructing high-level features using the original low-level features and function operators. Particle swarm optimisation (PSO) is an powerful global search technique, but it cannot be directly used for feature construction because of its representation scheme. This paper proposes two new representations, pair representation and array representation, which allow PSO to direct evolve function operators. Two PSO based feature construction algorithms (PSOFCPair and PSOFCArray) are then developed. The two new algorithms are examined and compared with the first PSO based feature construction algorithm (PSOFC), which employs an inner loop to select function operators. Experimental results show that both PSOFCPair and PSOFCArray can increase the classification performance by constructing a new high-level feature. PSOFCArray outperforms PSOFCPair and achieves similar results to PSOFC, but uses significantly shorter computational time. This paper represents the first work on using PSO to directly evolve function operators for feature construction.

In this paper, we describe a method for recognizing objects in the form of point clouds acquired with a laser scanner. This method is fully implemented on GPU and uses bio-inspired metaheuristics, namely PSO or DE, to evolve the rigid transformation that best aligns some references extracted from a dataset to the target point cloud. We compare the performance of our method with an established method based on Fast Point Feature Histograms (FPFH). The results prove that FPFH is more reliable under simple and controlled situations, but PSO and DE are more robust with respect to common problems as noise or occlusions.

Feature selection aims to select a small number of features from a large feature set to achieve similar or better classification performance than using all features. This paper develops a new binary particle swarm optimisation (PSO) algorithm (named PBPSO) based on which a new feature selection approach (PBPSOfs) is developed to reduce the number of features and increase the classification accuracy. The performance of PBPSOfs is compared with a standard binary PSO based feature selection algorithm (BPSOfs) and two traditional feature selection algorithms on 14 benchmark problems of varying difficulty. The results show that PBPSOfs can be successfully used for feature selection to select a small number of features and improve the classification performance over using all features. PBPSOfs further reduces the number of features selected by BPSOfs and simultaneously increases the classification accuracy, especially on datasets with a large number of features. Meanwhile, PBPSOfs achieves better performance than the two traditional feature selection algorithms. In addition, the results also show that PBPSO as a general binary optimisation technique can achieve better performance than standard binary PSO and uses less computational time.

This paper presents a new adaptive genetic algorithm (AGA) to select training data for support vector machines (SVMs). SVM training data selection strongly influences the classification accuracy and time, especially in the case of large and noisy data sets. In the proposed AGA, a population of solutions evolves with time. The AGA parameters, including the chromosome length, are adapted according to the current state of exploring the solution space. We propose a new multi-parent crossover operator for an efficient search. A new metric of distance between individuals is introduced and applied in the AGA. It is based on the fast analysis of the vectors distribution in the feature space obtained using principal component analysis. An extensive experimental study performed on the well-known benchmark sets along with the real-world and artificial data sets, confirms that the AGA outperforms a standard GA in terms of the convergence capabilities. Also, it reduces the number of support vectors and allows for faster SVM classification.

Genetic Algorithms (GAs) are known to be valuable tools for optimization purposes. In general, GAs can find good solutions by setting their configuration parameters, such as mutation and crossover rates, population size, etc., to standard (i.e., widely used) values. In some application domains, changing the values of these parameters does not improve the quality of the solution, but might influence the ability of the algorithm to find such solution. In other application domains, fine tuning these parameters could result into a significant improvement of the solution quality. In this paper we present an experimental study aimed at finding how fine tuning the parameters of a GA used for the insertion of a fragile watermark into a bitmap image influences the quality of the resulting digital object. However, when proposing a GA based new tool to non-expert users, selecting the best parameter setting is not an easy task. Therefore, we will suggest how to automatically set the GA parameters in order to meet the quality and/or running time performances requested by the user.

In this paper a classifier, designed by taking into account the user–friendliness issue, is described and is used to tackle the problem of classification of potential lesions in Multiple Sclerosis. This tool is based on the idea of making use of Differential Evolution (DE) to extract explicit knowledge from a database under the form of a set of IF–THEN rules, can use this set of rules to carry out the classification task, and can also provide clinicians with this knowledge, thus explaining the motivation for each of the proposed diagnoses. Each DE individual codes for a set of rules. The tool is compared over a database of Multiple Sclerosis potential lesions against a set of nine classification tools widely used in literature. Furthermore, the usefulness and the meaningfulness of the extracted knowledge have been assessed by comparing it against that provided by Multiple Sclerosis experts. No great differences have turned out to exist between these two forms of knowledge.

The fuel consumption of a simulation model of a real Hybrid Electric Vehicle is optimized on a standardized driving cycle using metaheuristics (PSO, ES, GA). Search space discretization and metamodels are considered for reducing the number of required, time-expensive simulations. Two hybrid metaheuristics for combining the discussed methods are presented. In experiments it is shown that the use of hybrid metaheuristics with discretization and metamodels can lower the number of required simulations without significant loss in solution quality.

The increasing complexity of current telecommunication satellite payloads has made their manual management a difficult and error prone task. As a consequence, efficient optimisation techniques are re- quired to help engineers to configure the payload. Recent works focusing on exact approaches faced scalability issues while metaheuristics provided unsatisfactory solution quality. This work therefore proposes three hybridisation schemes that combine both metaheuristics and an exact method. We focus on the initial configuration problem case and we consider as objective to minimise the length of the longest channel path. Experimental results on realistic payload sizes demonstrate the advantage of those approaches in terms of efficiency within a strict operational time constraint of ten minutes on a single CPU core.

Novel

Pre-processing

and

Post-processing

methodologies are designed to enhance the performance of the classical Genetic Algorithms (GA) approach so as to obtain efficient interval estimates in finding the real roots of a given nonlinear equation. The

Pre-processing

methodology suggests a mechanism that adaptively fixes the parameter-‘length of chromosome’ in GA. The proposed methodologies have been implemented and demonstrated through a set of benchmark functions to illustrate the effectiveness.

This paper describes a new evolutionary algorithm for multi-objective optimization, namely Multi-Objective Relative Clustering Genetic Algorithm (MO-RCGA), inspired by concepts borrowed from gene relatedness and kin selection theory. The proposed algorithm clusters the population into different families based on individual kinship, and adaptively chooses suitable individuals for reproduction. The idea is to use the information on the position of the individuals in the search space provided by such clustering schema to enhance the convergence rate of the algorithm, as well as improve its exploration. The proposed algorithm is tested on ten unconstrained benchmark functions proposed for the special session and competition on multi-objective optimizers held at IEEE CEC 2009. The Inverted Generational Distance (IGD) is used to assess the performance of the proposed algorithm, in comparison with the IGD obtained by state-of-the-art algorithms on the same benchmark.

It is known that evolution strategies in continuous domains might not converge in the presence of noise [

3

,

14

]. It is also known that, under mild assumptions, and using an increasing number of resamplings, one can mitigate the effect of additive noise [

4

] and recover convergence. We show new sufficient conditions for the convergence of an evolutionary algorithm with constant number of resamplings; in particular, we get fast rates (log-linear convergence) provided that the variance decreases around the optimum slightly faster than in the so-called multiplicative noise model.

The ensemble structure is a computational intelligence supervised strategy consisting of a pool of multiple operators that compete among each other for being selected, and an adaptation mechanism that tends to reward the most successful operators. In this paper we extend the idea of the ensemble to multiple local search logics. In a memetic fashion, the search structure of an ensemble framework cooperatively/competitively optimizes the problem jointly with a pool of diverse local search algorithms. In this way, the algorithm progressively adapts to a given problem and selects those search logics that appear to be the most appropriate to quickly detect high quality solutions. The resulting algorithm, namely Ensemble of Parameters and Strategies Differential Evolution empowered by Local Search (EPSDE-LS), is evaluated on multiple testbeds and dimensionality values. Numerical results show that the proposed EPSDE-LS robustly displays a very good performance in comparison with some of the state-of-the-art algorithms.

Electromagnetism-like Mechanism (EM) is a population based optimization approach, which has been recently adapted to solve multiobjective (MO) problems (MOEM). In this work, an enhanced multiobjective Electromagnetism-like Mechanism algorithm is proposed (EMOEM). To assess this new algorithm, a comparison with MOEM algorithm is performed. Our aim is to assess the ability of both algorithms in a wide range of continuous optimization problems including benchmark problems with two and three objective functions. Experiments show that EMOEM performs better in terms of convergence and diversity when compared with the MOEM algorithm.

Multiobjective optimization seeks simultaneous minimization of multiple scalar functions on

$$\mathbb {R}^n$$

. Unless weighted sums are made to replace the vector functions arising thus, such an optimization requires some partial- or quasi-ordering of points in the search space based on comparisons between the values attained by the functions to be optimized at those points. Many such orders can be defined, and search-based (mainly heuristic) optimization algorithms make use of such orders implicitly or explicitly for refining and accelerating search. In this work, such relations are studied by modeling them as graphs. Information apparent in the structure of such graphs is studied in the form of degree distribution. It is found that when the objective dimension grows, the degree distribution tends to follow a power-law. This can be a new beginning in the study of escalation of hardness of problems with dimension, as also a basis for designing new heuristics.

The traditional fields of improvement in parallelism have been orientated to experimentation on high-budget equipment, such as clusters of computers or shared memory machines thanks to their high-performance and scalability. In recent years, the generalization of multi-core microprocessors in almost all the computing platforms makes it possible to take advantage of parallel processing even for the desktop computer user. This paper analyzes how to improve the performance of population-based meta-heuristics using MPI, OpenMP, and hybrid MPI/OpenMP implementations in a workstation having a multi-core processor. The results obtained when solving large scale instances of the Capacitated Vehicle Routing Problem with hard Time Windows (VRPTW) show that, in all cases, the parallel implementations produce better quality solutions for a given amount of runtime than the sequential algorithm, and also solutions of similar quality in less runtime.

This paper investigates dynamic and partially connected ring topologies for cellular Evolutionary Algorithms (cEA). We hypothesize that these structures maintain population diversity at a higher level and reduce the risk of premature convergence to local optima on deceptive, multimodal and NP-hard fitness landscapes. A general framework for modelling partially connected topologies is proposed and three different schemes are tested. The results show that the structures improve the rate of convergence to global optima when compared to cEAs with standard topologies (ring, rectangular and square) on quasi-deceptive, deceptive and NP-hard problems. Optimal population size tests demonstrate that the proposed topologies require smaller populations when compared to traditional cEAs.

The Test Suite Minimization Problem (TSMP) is a

$$\mathcal {NP}$$

-hard real-world problem that arises in the field of software engineering. It lies in selecting the minimal set of test cases from a large test suite, ensuring that the test cases selected cover a given set of elements of a computer program under test. In this paper, we propose a Systolic Genetic Search (SGS) algorithm for solving the TSMP. We use the global concept of SGS to derive a particular algorithm to explicitly exploit the high degree of parallelism available in modern GPU architectures. The experimental evaluation on seven real-world programs shows that SGS is highly effective for the TSMP, as it obtains the optimal solution in almost every single run for all the tested software. It also outperforms two competitive Genetic Algorithms. The GPU-based implementation of SGS has achieved a high performance, obtaining runtime reductions of up to 40

$$\times $$

compared to its sequential implementation, and solving all the instances considered in less than nine seconds.

Cloud infrastructures are designed to simultaneously service many, diverse applications that consist of collections of Virtual Machines (VMs). The policy used to map applications onto physical servers (placement policy) has important effects in terms of application performance and resource efficiency. This paper proposes enhancing placement policies with network-aware optimizations trying to simultaneously improve application performance, resource efficiency and, as a consequence, power efficiency. The per-application placement decision is formulated as a bi-objective optimization problem (minimizing communication cost and minimizing the number of physical servers assigned to the application) whose solution is searched using an evolutionary algorithm with problem-specific crossover and mutation operators. Experiments carried out with a simulator demonstrate how a low-cost optimization technique results in improved placements that achieve all the target objectives.

Island Model parallel genetic algorithms rely on various migration models and their associated parameter settings. A fine understanding of how the islands interact and exchange informations is an important issue for the design of efficient algorithms. This article presents GridVis, an interactive tool for visualising the exchange of individuals and the propagation of fitness values between islands. We performed several experiments on a grid and on a cluster to evaluate GridVis’ ability to visualise the activity of each machine and the communication flow between machines. Experiments have been made on the optimisation of a Weierstrass function using the EASEA language, with two schemes: a scheme based on uniform islands and another based on specialised islands (Exploitation, Exploration and Storage Islands).

FPGA-based Genetic Algorithms (GAs) have been effective for optimisation of many real-world applications, but require extensive customisation of the hardware GA architecture. To promote these accelerated GAs to potential users without hardware design experience, this paper proposes an automated framework for creating and executing general-purpose GAs in FPGAs. The framework contains a scalable and customisable hardware architecture, which provides a unified platform for both binary and real-valued chromosomes. At compile-time, a user only needs to provide a high-level specification of the target application, without writing any hardware-specific code in low-level languages such as VHDL or Verilog. At run-time, a user can tune application inputs and GA parameters without time-consuming recompilation, in order to find a good configuration for further GA executions. The framework is demonstrated on a high performance FPGA platform to solve six problems and benchmarks, including a locating problem and the NP-hard set covering problem. Experiments show our custom GA is more flexible and easier to use compared to existing FPGA-based GAs, and achieves an average speed-up of 30 times compared to a multi-core CPU.

In this paper the effect of node unavailability in algorithms using EvoSpace, a pool-based evolutionary algorithm, is assessed. EvoSpace is a framework for developing evolutionary algorithms (EAs) using heterogeneous and unreliable resources. It is based on Linda’s tuple space coordination model. The core elements of EvoSpace are a central repository for the evolving population and remote clients, here called EvoWorkers, which pull random samples of the population to perform on them the basic evolutionary processes (selection, variation and survival), once the work is done, the modified sample is pushed back to the central population. To address the problem of unreliable EvoWorkers, EvoSpace uses a simple re-insertion algorithm using copies of samples stored in a global queue which also prevents the starvation of the population pool. Using a benchmark problem from the P-Peaks problem generator we have compared two approaches: (i) the re-insertion of previous individuals at the cost of keeping copies of each sample, and a common approach of other pool based EAs, (ii) inserting randomly generated individuals. We found that EvoSpace is fault tolerant to highly unreliable resources and also that the re-insertion algorithm is only needed when the population is near the point of starvation.

Hyper-heuristic techniques are problem independent meta-heuristics that automate the process of selecting a set of given low-level heuristics. Online path planning in an uncertain or unknown environment is one of the challenging problems for autonomous unmanned aerial vehicles (UAVs). This paper presents a hyper-heuristic approach to develop a 3-D online path planning for unmanned aerial vehicle (UAV) navigation under sensing uncertainty. The information regarding the state of a UAV is obtained from on-board sensors during the execution of a navigation plan. The trajectory of a UAV at each region is represented with B-spline curves, which is constructed by a set of dynamic control points. Experimental study performed on various terrains with different characteristics validates the usage of hyper-heuristics for online path planning. Our approach outperforms related work with respect to the quality of solutions and the number of feasible solutions produced.

ASHiCS (Automating the Search for Hazards in Complex Systems) uses evolutionary search on air traffic control simulations to find scenario configurations that generate high risk for a given air sector. Weighted heuristics are able to focus on specific events, flight paths or aircraft so that the search can effectively target incidents of interest. We describe how work on the characterization of our solution space suggests that destructive mutation operators perform badly in sensitive, high dimensional spaces. Finally, our work raises some issues about using collective risk assessment to discover significant safety events and whether the results are useful to safety analysts.

In this paper, we introduce a novel approach to the online evolution of robotic controllers. We propose accelerating and scaling online evolution to more complex tasks by giving the evolutionary process direct access to behavioural building blocks prespecified in the neural architecture as

macro-neurons

. During task execution, both the structure and the parameters of macro-neurons and of the entire neural network are under evolutionary control. We perform a series of simulation-based experiments in which an e-puck-like robot must learn to solve a deceptive and dynamic phototaxis task with three light sources. We show that: (i) evolution is able to progressively

complexify

controllers by using the behavioural building blocks as a substrate, (ii) macro-neurons, either evolved or preprogrammed, enable a significant reduction in the adaptation time and the synthesis of high performing solutions, and (iii) evolution is able to inhibit the execution of detrimental task-unrelated behaviours and adapt non-optimised macro-neurons.

This paper addresses a principal problem of

in vivo

evolution of modular multi-cellular robots, where robot ‘babies’ can be produced with arbitrary shapes and sizes. In such a system we need a generic learning mechanism that enables newborn morphologies to obtain a suitable gait quickly after ‘birth’. In this study we investigate and compare the reinforcement learning method RL PoWeR with HyperNEAT. We conduct simulation experiments using robot morphologies with different size and complexity. The experiments give insights into the differences in solution quality and algorithm efficiency, suggesting that reinforcement learning is the preferred option for this online learning problem.

In evolutionary robotics, the mapping from raw sensory input to neural network input is typically decided by the experimenter or encoded in the genome. Either way, the mapping remains fixed throughout a robot’s lifetime. Inspired by biological sensory organs and the mammalian brain’s capacity for selective attention, we evaluate an alternative approach in which a robot has active, real-time control over the mapping from sensory input to neural network input. We augment the neural controllers with additional output neurons that control key sensory parameters and evolve solutions for a single-robot foraging task. The results show that the capacity to control the mapping from raw input to neural network input is exploited by evolution and leads to novel solutions with higher fitness compared to traditional approaches.

This paper demonstrates the applicability of evolutionary computation methods to co-evolve a sensor morphology and a suitable control structure to optimally adjust a virtual adaptive wing structure. In contrast to approaches in which the structure of a sensor configuration is fixed early in the design stages, we target the simultaneous generation of information acquisition and information processing based on the optimization of a target function. We consider two aspects as main advantages. First the ability to generate optimal environmental sensors in the sense that the control structure can optimally utilize the information provided and secondly the abdication of detailed prior knowledge about the problem at hand. In this work we investigate the expected high correlation between the sensor morphology and the signal processing structures as well the quantity and quality of the information gathered from the environment.

This paper proposes a modification of Infeasibility Driven Evolutionary Algorithm that applies the anticipation mechanism following Feed-forward Prediction Strategy. The presented approach allows reacting on environmental changes more rapidly by directing some individuals into the areas of most probable occurrences of future optima. Also a novel population segmentation on exploring, exploiting and anticipating fractions is introduced to assure a better diversification of individuals and thus improve the ability to track moving optima. The experiments performed on the popular benchmarks confirmed the significant improvement in Dynamic Constrained Optimization Problems when using the proposed approach.

The purpose of this research is to provide an improved Evolutionary Algorithm (EA) in combination with Monte Carlo Simulation (MCS) to identify the robust number of a new type of intelligent vehicles in container terminals. This type of vehicles, named Intelligent Autonomous Vehicles (IAVs), has been developed in a European project. This research extends our previous study on combining MCS with EAs. This paper has three main contributions: first, it proposes a dynamic strategy to adjust the number of samples used by MCS to improve the performance of the EA; second, it incorporates different robustness measures into the EA to produce different robust solutions depending on user requirements; and third, it investigates the relation between different robust solutions using statistical analyses to provide insights into what would be the most appropriate robust solutions for port operators. These contributions have been verified using empirical experiments.

This paper describes a multi-objective evolutionary approach for solving cloud computing service provider selection problems with dynamic demands. In this investigated problem, not only the service purchase costs and transmission costs of service providers are different, but the demands of service requests also change over the given periods. The objective of this problem is to select a number of cloud service provider while optimizing the total service distance, the total number of serviced demand points, the total service purchase costs, and total transmission costs simultaneously in the given continuous time periods. A multi-objective genetic approach with a seeding mechanism is proposed to solve the investigated problems. Four trail benchmark problems are designed and solved using the proposed multi-objective evolutionary algorithm. The results indicate that the proposed approach is capable of obtaining a number of non-dominated solutions for decision makers.

This paper introduces jsEO, a new evolutionary computation library that is executed in web browsers, as it is written in Javascript. The library allows the rapid development of evolutionary algorithm, and makes easier the collaboration between different clients by means of individuals stored in a web server. In this work, jsEO has been tested against two simple problems, such as the Royal Road function and a 128-terms equation, and analysing how many machines and evaluations it yields. This paper attempts to reproduce results of older papers using modern browsers and all kind of devices that, nowadays, have JavaScript integrated in the browser, and is a complete rewrite of the code using the popular MooTools library. Results show that the system makes easier the development of evolutionary algorithms, suited for different chromosomes representations and problems, that can be simultaneously executed in many different operating systems and web browsers, sharing the best solutions previously found.

Network based analyses are commonly used as powerful tools to interpret the findings of genome-wide association studies (GWAS) in a functional context. In particular, identification of disease-associated functional modules, i.e., highly connected protein-protein interaction (PPI) subnetworks with high aggregate disease association, are shown to be promising in uncovering the functional relationships among genes and proteins associated with diseases. An important issue in this regard is the scoring of subnetworks by integrating two quantities that are not readily compatible: disease association of individual gene products and network connectivity among proteins. Current scoring schemes either disregard the level of connectivity and focus on the aggregate disease association of connected proteins or use a linear combination of these two quantities. However, such scoring schemes may produce arbitrarily large subnetworks which are often not statistically significant, or require tuning of parameters that are used to weigh the contributions of network connectivity and disease association. Here, we propose a parameter-free scoring scheme that aims to score subnetworks by assessing the disease association of pairwise interactions and incorporating the statistical significance of network connectivity and disease association. We test the proposed scoring scheme on a GWAS dataset for type II diabetes (T2D). Our results suggest that subnetworks identified by commonly used methods may fail tests of statistical significance after correction for multiple hypothesis testing. In contrast, the proposed scoring scheme yields highly significant subnetworks, which contain biologically relevant proteins that cannot be identified by analysis of genome-wide association data alone.

Imputation methods have been suggested as an efficient way to increase both utility and coverage in genome-wide association studies, especially when combining data generated from different genotyping arrays. We aim to demonstrate that imputation results are extremely accurate and the association analysis from imputed data does not over-inflate the results. Instead imputation leads to an increase in the power of the dataset without introducing any systematic biases. The majority of common variants can be imputed with very high accuracy (r2>0.9) and we validated the accuracy of imputations by comparing actual genotypes from low-throughput genotyping assays against imputed genotypes. Imputation was performed using IMPUTE2 and the 1000 Genomes cosmopolitan reference panel, which results in about 38 million SNPs. After quality control and filtering we performed case-control associations with 3,159,556 markers. We show a comparison of results from genotyped and imputed data and also determine how accurate ancestry is determined by imputations.

Epistasis is thought to be a pervasive part of complex phenotypes due to the dynamics and complexity of biological systems, and a further understanding of epistasis in the context of biological pathways may provide insight into the etiology of complex disease. In this study, we use genotype data from the International HapMap Project to characterize the functional dependencies between alleles in the human interactome as defined by KEGG pathways. We performed chi-square tests to identify non-independence between functionally-related SNP pairs within parental Caucasian and Yoruba samples. We further refine this list by testing for skewed transmission of pseudo-haplotypes to offspring using a haplotype-based TDT test. From these analyses, we identify pathways enriched for functional disequilibrium, and a set of 863 SNP pairs (representing 453 gene pairs) showing consistent non-independence and transmission distortion. These results represent gene pairs with strong evidence of epistasis within the context of a biological function.

The computational modeling of HIV-1proteins has become a useful framework allowing understanding the virus behavior (e.g. mutational patterns, replication process or resistance mechanism). For instance, predicting the drug resistance from genotype means to solve a complicated sequence classification problem. In such kind of problems proper feature selection could be essential to increase the classifiers performance. Several sequence positions that have been previously associated with resistance are known, although we believe that other positions could be discovered. More explicitly, we observed that using positions reported in the literature for the

reverse transcriptase

protein, the final decision system exhibited inconsistent mutations. However, finding a minimal subset of features characterizing the whole sequence involve a challenging combinatorial problem. This research proposes a model based on Variable Mesh Optimization and Rough Sets Theory for computing those sequence positions associated with resistance, leading to more consistent decision systems. Finally, our model is validated across eleven well-known

reverse transcriptase

inhibitors.

Alignment of samples from Liquid chromatography-mass spectrometry (LC-MS) measurements has a significant role in the detection of biomarkers and in metabolomic studies.The machine drift causes differences between LC-MS measurements, and an accurate alignment of the shifts introduced to the same peptide or metabolite is needed. In this paper, we propose the use of genetic programming (GP) for multiple alignment of LC-MS data. The proposed approach consists of two main phases. The first phase is the peak matching where the peaks from different LC-MS maps (peak lists) are matched to allow the calculation of the retention time deviation. The second phase is to use GP for multiple alignment of the peak lists with respect to a reference. In this paper, GP is designed to perform multiple-output regression by using a special node in the tree which divides the output of the tree into multiple outputs. Finally, the peaks that show the maximum correlation after dewarping the retention times are selected to form a consensus aligned map.The proposed approach is tested on one proteomics and two metabolomics LC-MS datasets with different number of samples. The method is compared to several benchmark methods and the results show that the proposed approach outperforms these methods in three fractions of the protoemics dataset and the metabolomics dataset with a larger number of maps. Moreover, the results on the rest of the datasets are highly competitive with the other methods.

Genetic variations among individuals account for a large portion of variability in drug response. The underlying mechanism of the variability is still not known, but it is expected to comprise of a wide range of genetic factors that interact and communicate with each other. Here, we present an integrated genome-wide approach to uncover the interactions among genetic factors that can explain some of the inter-individual variation in drug response. The International HapMap consortium generated genotyping data on human lymphoblastoid cell lines of (Center d’Etude du Polymorphisme Humain population - CEU) European descent and (Yoruba population - YRI) African descent. Using genome-wide analysis, Huang et al. identified SNPs that are associated with etoposide, a chemotherapeutic drug, response on the cell lines. Using the same lymphoblastoid cell lines, Fraser et al. generated genome-wide methylation profiles for gene promoter regions. We evaluated associations between candidate SNPs generated by Huang et al and genome-wide methylation sites. The analysis identified a set of methylation sites that are associated with etoposide related SNPs. Using the set of methylation sites and the candidate SNPs, we built an integrated model to explain etoposide response observed in CEU and YRI cell lines. This integrated method can be extended to combine any number of genomics data types to explain many phenotypes of interest.

The NAv1.5 sodium channel α subunit is the predominant α-subunit expressed in the heart and is associated with cardiac arrhythmias. We tested five previously identified

SCN5A

variants (rs7374138, rs7637849, rs7637849, rs7629265, and rs11129796) for an association with PR interval and QRS duration in two unique study populations: the Third National Health and Nutrition Examination Survey (NHANES III, n= 552) accessed by the Epidemiologic Architecture for Genes Linked to Environment (EAGLE) and a combined dataset (n= 455) from two biobanks linked to electronic medical records from Vanderbilt University (BioVU) and Northwestern University (NUgene) as part of the electronic Medical Records & Genomics (eMERGE) network. A meta-analysis including all three study populations (n~4,000) suggests that eight

SCN5A

associations were significant for both QRS duration and PR interval (p<5.0E-3) with little evidence for heterogeneity across the study populations. These results suggest that published

SCN5A

associations replicate across different study designs in a meta-analysis and represent an important first step in utility of multiple study designs for genetic studies and the identification/characterization of genetic variants associated with ECG traits in African-descent populations.

This paper describes a technique of penalty weight adjustment for the Cooperative Genetic Algorithm applied to the nurse scheduling problem. In this algorithm, coefficients and thresholds for each penalty function are automatically optimized. Therefore, this technique provides a parameter free algorithm of nurse scheduling. The nurse scheduling is very complex task, because many requirements must be considered. These requirements are implemented by a set of penalty function in this research. In real hospital, several changes of the schedule often happen. Such changes of the shift schedule yields various inconveniences, for example, imbalance of the number of the holidays and the number of the attendance. Such inconvenience causes the fall of the nursing level of the nurse organization. Reoptimization of the schedule including the changes is very hard task and requires very long computing time. We consider that this problem is caused by the solution space having many local minima. We propose a technique to adjust penalty weights and thresholds through the optimization to escape from the local minima.