Applications of Evolutionary Computation

The purpose of this paper is to revisit the Multiobjective Population-Based Incremental Learning method and show how its performance can be improved in the context of a real-world financial optimization problem. The proposed enhancements lead to both better performance and improvements in the quality of solutions. Its performance was assessed in terms of runtime and speedup when parallelized. Also, metrics such as the average number of solutions, the average hypervolume, and coverage have been used in order to compare the Pareto frontiers obtained by both the original and enhanced methods. Results indicated that the proposed method is 22.1 % faster, present more solutions in the average (better defining the Pareto frontier) and often generates solutions having larger hypervolumes. The enhanced method achieves a speedup of 15.7 on 16 cores of a dual socket Intel multi-core machine when solving a Reinsurance Contract Optimization problem involving 15 Layers or sub-contracts.

A memory-enabled program representation in strongly-typed Genetic Programming (GP) is compared against the standard representation in a number of financial time-series modelling tasks. The paper first presents a survey of GP systems that utilise memory. Thereafter, a number of simulations show that memory-enabled programs generalise better than their standard counterparts in most datasets of this problem domain.

Credit card classification based on machine learning has attracted considerable interest from the research community. One of the most important tasks in this area is the ability of classifiers to handle the imbalance in credit card data. In this scenario, classifiers tend to yield poor accuracy on the minority class despite realizing high overall accuracy. This is due to the influence of the majority class on traditional training criteria. In this paper, we aim to apply genetic programming to address this issue by adapting existing fitness functions. We examine two fitness functions from previous studies and develop two new fitness functions to evolve GP classifiers with superior accuracy on the minority class and overall. Two UCI credit card datasets are used to evaluate the effectiveness of the proposed fitness functions. The results demonstrate that the proposed fitness functions augment GP classifiers, encouraging fitter solutions on both the minority and the majority classes.

Successful and timely completion of prospective clinical trials depends on patient recruitment as patients are critical to delivery of the prospective trial data. There exists a pressing need to develop better tools/techniques to optimise patient recruitment in multicentre clinical trials. In this study Grammatical Evolution (GE) is used to evolve classification models to predict future patient enrolment performance of investigators/site to be selected for the conduct of the trial. Prediction accuracy of the evolved models is compared with results of a range of machine learning algorithms widely used for classification. The results suggest that GE is able to successfully induce classification models and analysis of these models can help in our understanding of the factors providing advanced indication of a trial sites’ future performance.

Several machine learning paradigms have been applied to financial forecasting, attempting to predict the market’s behavior, with the final objective of profiting from trading shares. While anticipating the performance of such a complex system is far from trivial, this issue becomes even harder when the investors do not have large amounts of money available. In this paper, we present an evolutionary portfolio optimizer for the management of small budgets. The expected returns are modeled resorting to Multi-layer Perceptrons, trained on past market data, and the portfolio composition is chosen by approximating the solution to a multi-objective constrained problem. An investment simulator is then used to measure the portfolio performance. The proposed approach is tested on real-world data from Milan stock exchange, exploiting information from January 2000 to June 2010 to train the framework, and data from July 2010 to August 2011 to validate it. The presented tool is finally proven able to obtain a more than satisfying profit for the considered time frame.

Multi-objective Evolutionary algorithms are well suited to Portfolio Optimization and hence have been applied in complex situations were traditional mathematical programming falls short. Often they were used in portfolios scenario of classical Mean-Variance which are not applicable to the Emerging Markets. Emerging Markets are characterized by return distributions that have shown to exhibit significance departure from normality and are characterized by skewness and fat tails. Therefore higher moments models and median models have been suggested in the literature for asset allocation in this case. Three higher moment models namely the Mean-Variance-Skewness, Mean-Variance-Skewness-Kurtosis, Mean-Variance-Skewness-Kurtosis for return and liquidity and three median models namely the Median-Value at Risk, Median-Conditional Value at Risk and Median-Mean Absolute Deviation are formulated as a multi-objective problem and solved using a multi-objective evolutionary algorithm namely the non-dominated sorting genetic algorithm II. The six models are compared and tested on real financial data of the Egyptian Index EGX. The median models were found in general to outperform the higher moments models. The performance of the median models was found to be better as the out-sample time increases.

Protein-protein interaction networks and protein folding networks represent prominent research topics at the intersection of bioinformatics and network science. In this paper, we present a study of these networks from combinatorial optimisation point of view. Using a combination of classical heuristics and stochastic optimisation techniques, we were able to identify several interesting combinatorial properties of biological networks of the COSIN project. We obtained optimal or near-optimal solutions to maximum clique and chromatic number problems for these networks. We also explore patterns of both non-overlapping and overlapping cliques in these networks. Optimal or near-optimal solutions to partitioning of these networks into non-overlapping cliques and to maximum independent set problem were discovered. Maximal cliques are explored by enumerative techniques. Domination in these networks is briefly studied, too. Applications and extensions of our findings are discussed.

Mass spectrometry is currently the most commonly used technology in biochemical research for proteomic analysis. The main goal of proteomic profiling using mass spectrometry is the classification of samples from different clinical states. This requires the identification of proteins or peptides (biomarkers) that are expressed differentially between different clinical states. However, due to the high dimensionality of the data and the small number of samples, classification of mass spectrometry data is a challenging task. Therefore, an effective feature manipulation algorithm either through feature selection or construction is needed to enhance the classification performance and at the same time minimise the number of features. Most of the feature manipulation methods for mass spectrometry data treat this problem as a single objective task which focuses on improving the classification performance. This paper presents two new methods for biomarker detection through multi-objective feature selection and feature construction. The results show that the proposed multi-objective feature selection method can obtain better subsets of features than the single-objective algorithm and two traditional multi-objective approaches for feature selection. Moreover, the multi-objective feature construction algorithm further improves the perfomance over the multi-objective feature selection algorithm. This paper is the first multi-objective genetic programming approach for biomarker detection in mass spectrometry data.

Over the past decade, data science and machine learning has grown from a mysterious art form to a staple tool across a variety of fields in academia, business, and government. In this paper, we introduce the concept of tree-based pipeline optimization for automating one of the most tedious parts of machine learning—pipeline design. We implement a Tree-based Pipeline Optimization Tool (TPOT) and demonstrate its effectiveness on a series of simulated and real-world genetic data sets. In particular, we show that TPOT can build machine learning pipelines that achieve competitive classification accuracy and discover novel pipeline operators—such as synthetic feature constructors—that significantly improve classification accuracy on these data sets. We also highlight the current challenges to pipeline optimization, such as the tendency to produce pipelines that overfit the data, and suggest future research paths to overcome these challenges. As such, this work represents an early step toward fully automating machine learning pipeline design.

Networks representing complex biological interactions are often very intricate and rely on algorithmic tools for thorough quantitative analysis. In bi-layered graphs, identifying subgraphs of potential biological meaning relies on identifying bicliques between two sets of associated nodes, or variables – for example, diseases and genetic variants. Researchers have developed multiple approaches for forming bicliques and it is important to understand the features of these models and their applicability to real-life problems. We introduce a novel algorithm specifically designed for finding maximal bicliques in large datasets. In this study, we applied this algorithm to a variety of networks, including artificially generated networks as well as biological networks based on phenotype-genotype and phenotype-pathway interactions. We analyzed performance with respect to network features including density, node degree distribution, and correlation between nodes, with density being the major contributor to computational complexity. We also examined sample bicliques and postulate that these bicliques could be useful in elucidating the genetic and biological underpinnings of shared disease etiologies and in guiding hypothesis generation. Moving forward, we propose additional features, such as weighted edges between nodes, that could enhance our study of biological networks.

Hybrid methods are a branch of biclustering algorithms that emerge from combining selected aspects of pre-existing approaches. The syncretic nature of their construction enriches the existing methods providing them with new properties. In this paper the concept of hybrid biclustering algorithms is explained. A representative hybrid biclustering algorithm, inspired by neural networks and associative artificial intelligence, is introduced and the results of its application to microarray data are presented. Finally, the scope and application potential for hybrid biclustering algorithms is discussed.

Constrained non-negative matrix factorization (CNMF) is an effective machine learning technique to cluster documents in the presence of class label constraints. In this work, we provide a novel application of this technique in research on neuro-degenerative diseases. Specifically, we consider a dataset of documents from the Netherlands Brain Bank containing free text describing clinical and pathological information about donors affected by Multiple Sclerosis. The goal is to use CNMF for identifying clinical profiles with pathological information as constraints. After pre-processing the documents by means of standard filtering techniques, a feature representation of the documents in terms of bi-grams is constructed. The high dimensional feature space is reduced by applying a trimming procedure. The resulting datasets of clinical and pathological bi-grams are then clustered using non-negative matrix factorization (NMF) and, next, clinical data are clustered using CNMF with constraints induced by the clustering of pathological data. Results indicate the presence of interesting clinical profiles, for instance related to vision or movement problems. In particular, the use of CNMF leads to the identification of a clinical profile related to diabetes mellitus. Pathological characteristics and duration of disease of the identified profiles are analysed. Although highly promising, results of this investigation should be interpreted with care due to the relatively small size of the considered datasets.

Synthetic biology aims at reinvesting theoretical knowledge from various do-mains (biology, engineering, microelectronics) for the development of new bio-logical functions. Concerning the design of such functions, the classical trial-error approach is expensive and time consuming. Computer-aided design is therefore of key interest in this field. As for other domains, such as microelectronics or robotics, evolutionary algo-rithms can be used to this end. This article is a first step in this direction: it describes the optimization of an existing artificial gene regulatory network using evolutionary algorithms. Evolutionary algorithms successfully find a good set of parameters (the simu-lated response of the system which fits at 99 % the expected response) in about 200 s (corresponding to 5000 generations) on a standard computer. This is the proof of concept of our approach. Moreover, results analysis allows the biologist not only to save time during the design process but also to study the specificity of a system.

In this paper, a new algorithm is proposed for the solution of the Multicast Routing Problem. The algorithm is based on the Artificial Bee Colony approach hybridized with Variable Neighborhood Search. The quality of the algorithm is evaluated with experiments conducted on suitably modified benchmark instances of the Euclidean Traveling Salesman Problem from the TSP library. The results of the algorithm are compared to results obtained by several versions of the Particle Swarm Optimization algorithm. The comparisons indicated the effectiveness of the new approach.

Heterogeneous Cellular Networks are multi-tiered cellular networks comprised of Macro Cells and Small Cells in which all cells occupy the same bandwidth. User Equipments greedily attach to whichever cell provides the best signal strength. While Macro Cells are invariant, the power and selection bias for each Small Cell can be increased or decreased (subject to pre-defined limits) such that more or fewer UEs attach to that cell. Setting optimal power and selection bias levels for Small Cells is key for good network performance. The application of Genetic Programming techniques has been proven to produce good results in the control of Heterogenous Networks. Expanding on previous works, this paper uses grammatical GP to evolve distributed control functions for Small Cells in order to vary their power and bias settings. The objective of these control functions is to evolve control functions that maximise a proportional fair utility of UE throughputs.

In the last years the interest in multi-hop communications has gained momentum within the research community due to the challenging characteristics of the intra-vehicular radio environment and the stringent robustness imposed on critical sensors within the vehicle. As opposed to point-to-point network topologies, multi-hop networking allows for an enhanced communication reliability at the cost of an additional processing overhead. In this context this manuscript poses a novel bi-objective optimization problem aimed at jointly minimizing (1) the average Bit Error Rate (BER) of sensing nodes under a majority fusion rule at the central data collection unit; and (2) the mean delay experienced by packets forwarded by such nodes due to multi-hop networking, frequency channel switching time multiplexing at intermediate nodes. The formulated paradigm is shown to be computationally tractable via a combination of evolutionary meta-heuristic algorithms and Dandelion codes, the latter capable of representing tree-like structures like those modeling the multi-hop routing approach. Simulations are carried out for realistic values of intra-vehicular radio channels and co-channel interference due to nearby IEEE 802.11 signals. The obtained results are promising and pave the way towards assessing the practical performance of the proposed scheme in real setups.

In this paper, a Heuristic-Crossover Enhanced Evolutionary Algorithm for Cluster Head Selection is proposed. The algorithm uses a novel heuristic crossover operator to combine two different solutions in order to achieve a high quality solution that distributes the energy load evenly among the sensor nodes and enhances the distribution of cluster head nodes in a network. Additionally, we propose the Stochastic Selection of Inactive Nodes, a mechanism inspired by the Boltzmann Selection process in genetic algorithms. This mechanism stochastically considers coverage effect in the selection of nodes that are required to go into sleep mode in order to conserve energy of sensor nodes. The proposed selection of inactive node mechanisms and cluster head selections protocol are performed sequentially at every round and are part of the main algorithm proposed, namely the Heuristic Algorithm for Clustering Hierarchy (HACH). The main goal of HACH is to extend network lifetime of wireless sensor networks by reducing and balancing the energy consumption among sensor nodes during communication processes. Our protocol shows improved performance compared with state-of-the-art protocols like LEACH, TCAC and SEECH in terms of improved network lifetime for wireless sensor networks deployments.

Load balancing (LB) is an important and challenging optimisation problem in cloud computing. LB involves assigning a set of services into a set of machines for which the goal is to optimise machine usages. This study presents a memetic algorithm (MA) for the LB problem. MA is a hybrid method that combines the strength of population based evolutionary algorithms with local search. However the effectiveness of MA mainly depends on the local search method chosen for MA. This is because local search methods perform differently for different instances and under different stages of search. In addition, invoking local search at every generation can be computationally expensive and compromise the exploration capacity of search. To address these issues, this study proposes a variable local search based MA in the context of LB problem. The proposed MA uses multiple local search mechanisms. Each one navigates a different area in search space using a different search mechanism which can leads to a different search path with distinct local optima. This will not only help the search to avoid being trap in a local optima point, but can also effectively deal with various landscape search characteristics and dynamic changes of the problem. In addition, a diversity indicator is adopted to control the local search processes to encourage solution diversity. Our MA method is evaluated on instances of the Google machine reassignment problem proposed for the ROADEF/EURO 2012 challenge. Compared with the state of the art methods, our method achieved the best performance on most of instances, showing the effectiveness of variable local search based MA for the Load Balancing problem.

We investigate the 3-architecture Connected Facility Location Problem arising in the design of urban telecommunication access networks integrating wired and wireless technologies. We propose an original optimization model for the problem that includes additional variables and constraints to take into account wireless signal coverage represented through signal-to-interference ratios. Since the problem can prove very challenging even for modern state-of-the art optimization solvers, we propose to solve it by an original primal heuristic that combines a probabilistic fixing procedure, guided by peculiar Linear Programming relaxations, with an exact MIP heuristic, based on a very large neighborhood search. Computational experiments on a set of realistic instances show that our heuristic can find solutions associated with much lower optimality gaps than a state-of-the-art solver.

Newscast is a Peer-to-Peer, nature-inspired gossip-based data exchange protocol used for information dissemination and membership management in large-scale, agent-based distributed systems. The model follows a probabilistic scheme able to keep a self-organised, small-world equilibrium featuring a complex, spatially structured and dynamically changing environment. Newscast gained popularity since the early 2000 s thanks to its inherent resilience to node volatility as the protocol exhibits strong self-healing properties. However, the original design proved to be surprisingly fragile in a byzantine environment subjected to cheating faults. Indeed, a set of recent studies emphasized the hard-wired vulnerabilities of the protocol, leading to an efficient implementation of a malicious client, where a few naive cheaters are able to break the network connectivity in a very short time. Extending these previous works, we propose in this paper a modification of the seminal protocol with embedded counter-measures, improving the resilience of the scheme against malicious acts without significantly affecting the original Newscast’s properties nor its inherent performance. Concrete experiments were performed to support these claims, using a framework implementing all the solutions discussed in this work.

Modern intrusion detection systems must handle many complicated issues in real-time, as they have to cope with a real data stream; indeed, for the task of classification, typically the classes are unbalanced and, in addition, they have to cope with distributed attacks and they have to quickly react to changes in the data. Data mining techniques and, in particular, ensemble of classifiers permit to combine different classifiers that together provide complementary information and can be built in an incremental way. This paper introduces the architecture of a distributed intrusion detection framework and in particular, the detector module based on a meta-ensemble, which is used to cope with the problem of detecting intrusions, in which typically the number of attacks is minor than the number of normal connections. To this aim, we explore the usage of ensembles specialized to detect particular types of attack or normal connections, and Genetic Programming is adopted to generate a non-trainable function to combine each specialized ensemble. Non-trainable functions can be evolved without any extra phase of training and, therefore, they are particularly apt to handle concept drifts, also in the case of real-time constraints. Preliminary experiments, conducted on the well-known KDD dataset and on a more up-to-date dataset, ISCX IDS, show the effectiveness of the approach.

The last years, UAVs have been developed to address a variety of applications ranging from searching and tracking to the surveillance of an area. However, using a single UAV limits the range of possible applications. Therefore, fleets of UAVs are nowadays considered to work together on a common goal which requires novel distributed mobility management models. This work proposes a novel nature-inspired mobility model for UAV fleets based on Ant Colony Optimisation approaches (ACO). It relies on two types of pheromones, a repulsive pheromone to cover the designated area in an efficient way, and an attractive pheromone to detect and to track the maximum number of targets. Furthermore, all decision takings are taken online by each UAV and are fully distributed. Experimental results demonstrate promising target tracking performances together with a small increase in the exhaustivity of the coverage.

Gene regulatory networks (GRNs) are the complex dynamical systems that orchestrate the activities of biological cells. In order to design effective therapeutic interventions for diseases such as cancer, there is a need to control GRNs in more sophisticated ways. Computational control methods offer the potential for discovering such interventions, but the difficulty of the control problem means that current methods can only be applied to GRNs that are either very small or that are topologically restricted. In this paper, we consider an alternative approach that uses evolutionary algorithms to design GRNs that can control other GRNs. This is motivated by previous work showing that computational models of GRNs can express complex control behaviours in a relatively compact fashion. As a first step towards this goal, we consider abstract Boolean network models of GRNs, demonstrating that Boolean networks can be evolved to control trajectories within other Boolean networks. The Boolean approach also has the advantage of a relatively easy mapping to synthetic biology implementations, offering a potential path to in vivo realisation of evolved controllers.

According to evolutionary game theory, cooperation in public goods games is eliminated by free-riders, yet in nature, cooperation is ubiquitous. Artificial models resolve this contradiction via the mechanism of network reciprocity. However, existing research only addresses pre-existing networks and does not specifically consider their origins. Further, much work has focused on scale-free networks and so pre-supposes attachment mechanisms which may not exist in nature. We present a coevolutionary model of public goods games in networks, growing by random attachment, from small founding populations of simple agents. The model demonstrates the emergence of cooperation in moderately heterogeneous networks, regardless of original founders’ behaviour, and absent higher cognitive abilities such as recognition or memory. It may thus illustrate a more general mechanism for the evolution of cooperation, from early origins, in minimally cognitive organisms. It is the first example of a model explaining cooperation in public goods games on growing networks.

We live in a world of social networks. Our everyday choices are often influenced by social interactions. Word of mouth, meme diffusion on the Internet, and viral marketing are all examples of how social networks can affect our behaviour. In many practical applications, it is of great interest to determine which nodes have the highest influence over the network, i.e., which set of nodes will, indirectly, reach the largest audience when propagating information. These nodes might be, for instance, the target for early adopters of a product, the most influential endorsers in political elections, or the most important investors in financial operations, just to name a few examples. Here, we tackle the NP-hard problem of influence maximization on social networks by means of a Genetic Algorithm. We show that, by using simple genetic operators, it is possible to find in feasible runtime solutions of high-influence that are comparable, and occasionally better, than the solutions found by a number of known heuristics (one of which was previously proven to have the best possible approximation guarantee, in polynomial time, of the optimal solution). The advantages of Genetic Algorithms show, however, in them not requiring any assumptions about the graph underlying the network, and in them obtaining more diverse sets of feasible solutions than current heuristics.

In our recent research, we implemented an enhancement of Ant Colony Optimization incorporating the socio-cognitive dimension of perspective taking. Our initial results suggested that increasing the diversity of ant population — introducing different pheromones, different species and dedicated inter-species relations — yielded better results. In this paper, we explore the diversity issue by introducing novel diversity measurement strategies for ACO. Based on these strategies we compare both classic ACO and its socio-cognitive variation.

Genetic algorithms are a group of powerful tools for solving ill-posed global optimization problems in continuous domains. In case in which the insensitivity of the fitness function is the main obstacle, the most desired feature of a genetic algorithm is its ability to explore plateaus of the fitness function, surrounding its minimizers. In this paper we suggest a way of maintaining diversity of the population in the plateau regions, based on a new approach for the selection based on the theory of multiwinner elections among autonomous agents. The paper delivers a detailed description of the new selection algorithm, computational experiments that guide the choice of the proper multiwinner rule to use, and a preliminary experiment showing the proposed algorithm’s effectiveness in exploring a fitness function’s plateau.

A steadily increasing pervasion of the distribution grid with rather small renewable energy resources imposes fluctuating and hardly predictable feed-in and thus calls for new predictive load planning strategies. On the other hand, combined with controllable, shiftable loads and electrical storages, these energy units set up a flexibility potential for fine-grained control. To tap the full potential, distributed control strategies are discussed for scheduling due to the expected large number of controlled entities. Decoder strategies for unit independent algorithm implementation and feasibility assurance had recently been applied to some first optimization approaches for scheduling in smart grid. We extended a distributed particle swarm to harnesses such decoder approach for model independent constraint-handling and achieved a higher accuracy compared with other approaches. A multi swarm is integrated after the island model into a decentralized agent-based solution and compared with an established decentralized approach for predictive scheduling within virtual power plants. We demonstrate the superiority of the particle swarm in terms of achieved solution accuracy and the competitiveness in terms of sent messages.

The optimization of operating times and operation modes of devices and systems that consume or generate electricity in buildings by building energy management systems promises to alleviate problems arising in today’s electricity grids. Conflicting objectives may have to be pursued in this context, giving rise to a multi-objective optimization problem. This paper presents the optimization of appliances as well as heating and air-conditioning devices in two distinct settings of smart buildings, a residential and a commercial building, with respect to the minimization of energy costs, CO₂ emissions, discomfort, and technical wearout. We propose new encodings for appliances that are based on a combined categorization of devices respecting both, the optimization of operating times as well as operation modes, e.g., of hybrid devices. To identify an evolutionary algorithm that promises to lead to good optimization results of the devices in our real-world lab environments, we compare four state-of-the-art algorithms in realistic simulations: ESPEA, NSGA-II, NSGA-III, and SPEA2. The results show that ESPEA and NSGA-II significantly outperform the other two algorithms in our scenario.

In this paper a bilevel programming model is proposed for modeling the interaction between electricity retailers and consumers endowed with energy management systems capable of providing demand response to variable prices. The model intends to determine the optimal pricing scheme to be established by the retailer (upper level decision maker) and the optimal load schedule adopted by the consumer (lower level decision maker) under this price setting. The lower level optimization problem is formulated as a mixed-integer linear programming (MILP) problem. A hybrid approach consisting of a genetic algorithm and an exact MILP solver is proposed. The individuals of the population represent the retailer’s choices (electricity prices). For each price setting, the exact optimal solution to the consumer’s problem is obtained in a very efficient way using the MILP solver. An illustrative case is analyzed and discussed.

In this paper, we address the rescheduling of shiftable loads in a sub-section of the power grid (micro-grid) to maximize the utilization of renewable energy sources (RES). The objective is to achieve a schedule for all customers in the micro-grid such that the RES output utilization is maximized. Customers correspond to residential households provided with intelligent appliances with the ability to recalculate their operation times. We propose an approach based on stigmergy to efficiently find a close-to-optimal solution to the general problem. An empirical analysis of the internal functioning of the algorithm is performed. Furthermore, the performance of the algorithm is compared to a price-based approach.

Electrical Load Pattern Shape (LPS) clustering of customers is an important part of the tariff formulation process. Nevertheless, the patterns describing the energy consumption of a customer have some characteristics (e.g., a high number of features corresponding to time series reflecting the measurements of a typical day) that make their analysis different from other pattern recognition applications. In this paper, we propose a clustering algorithm based on ant colony optimization (ACO) to solve the LPS clustering problem. We use four well-known clustering metrics (i.e., CDI, SI, DEV and CONN), showing that the selection of a clustering quality metric plays an important role in the LPS clustering problem. Also, we compare our LPS-ACO algorithm with traditional algorithms, such as k-means and single-linkage, and a state-of-the-art Electrical Pattern Ant Colony Clustering (EPACC) algorithm designed for this task. Our results show that LPS-ACO performs remarkably well using any of the metrics presented here.

To support the utilization of renewable energies, an optimized operation of energy systems is important. Often, the use of battery energy storage systems is stated as one of the most important measures to support the integration of intermittent renewable energy sources into the energy system. Additionally, the complexity of the energy system with its many interdependent entities as well as the economic efficiency call for an elaborate dimensioning and control of these storage systems. In this paper, we present an approach that combines the forward-looking nature of optimization and prediction with the feedback control of closed-loop controllers. An evolutionary algorithm is used to determine the parameters for a closed-loop controller that controls the charging and discharging control strategy of a battery in a smart building. The simulation and evaluation of a smart residential building scenario demonstrates the ability to improve the operation and control of a battery energy storage system. The optimization of the control strategy allows for the optimization with respect to variable tariffs while being conducive for the integration of renewable energy sources into the energy system.

Computer games are most engaging when their difficulty is well matched to the player’s ability, thereby providing an experience in which the player is neither overwhelmed nor bored. In games where the player interacts with computer-controlled opponents, the difficulty of the game can be adjusted not only by changing the distribution of opponents or game resources, but also through modifying the skill of the opponents. Applying evolutionary algorithms to evolve the artificial intelligence that controls opponent agents is one established method for adjusting opponent difficulty. Less-evolved agents (i.e., agents subject to fewer generations of evolution) make for easier opponents, while highly-evolved agents are more challenging to overcome. In this publication we test a new approach for difficulty adjustment in games: orthogonally evolved AI, where the player receives support from collaborating agents that are co-evolved with opponent agents (where collaborators and opponents have orthogonal incentives). The advantage is that game difficulty can be adjusted more granularly by manipulating two independent axes: by having more or less adept collaborators, and by having more or less adept opponents. Furthermore, human interaction can modulate (and be informed by) the performance and behavior of collaborating agents. In this way, orthogonally evolved AI both facilitates smoother difficulty adjustment and enables new game experiences.

This paper proposes an evolutionary algorithm for evolving game bots that eschews an explicit fitness function using instead a match between individuals called joust and implemented as a selection mechanism where only the winner survives. This algorithm has been designed as an optimization approach to generate the behavioural engine of bots for the RTS game Planet Wars using Genetic Programming and has two objectives: first, to deal with the noisy nature of the fitness function and second, to obtain more general bots than those evolved using a specific opponent. In addition, avoiding the explicit evaluation step reduce the number of combats to perform during the evolution and thus, the algorithm time consumption is decreased. Results show that the approach performs converges, is less sensitive to noise than other methods and it yields very competitive bots in the comparison against other bots available in the literature.

This paper introduces an evolutionary method for generating levels for adventure games, combining speed, guaranteed solvability of levels and authorial control. For this purpose, a new graph-based two-phase level encoding scheme is developed. This method encodes the structure of the level as well as its contents into two abstraction layers: the higher level defines an abstract representation of the game level and the distribution of its content among different inter-connected game zones. The lower level describes the content of each game zone as a set of graphs containing rooms, doors, monsters, keys and treasure chests. Using this representation, game worlds are encoded as individuals in an evolutionary algorithm and evolved according to an evaluation function meant to approximate the entertainment provided by the game level. The algorithm is implemented into a design tool that can be used by game designers to specify several constraints of the worlds to be generated. This tool could be used to facilitate the design of game levels, for example to make professional-level content production possible for non-experts.

We deal with the problem of automatic generation of complete rules of an arbitrary game. This requires a generic and accurate evaluating function that is used to score games. Recently, the idea that game quality can be measured using differences in performance of various game-playing algorithms of different strengths has been proposed; this is called Relative Algorithm Performance Profiles.We formalize this method into a generally application algorithm estimating game quality, according to some set of model games with properties that we want to reproduce. We applied our method to evolve chess-like boardgames. The results show that we can obtain playable and balanced games of high quality.

We present Online Evolution, a novel method for playing turn-based multi-action adversarial games. Such games, which include most strategy games, have extremely high branching factors due to each turn having multiple actions. In Online Evolution, an evolutionary algorithm is used to evolve the combination of atomic actions that make up a single move, with a state evaluation function used for fitness. We implement Online Evolution for the turn-based multi-action game Hero Academy and compare it with a standard Monte Carlo Tree Search implementation as well as two types of greedy algorithms. Online Evolution is shown to outperform these methods by a large margin. This shows that evolutionary planning on the level of a single move can be very effective for this sort of problems.

The procedural generation of massive subplots and backstories in secondary characters that inhabit Open World videogames usually lead to stereotyped characters that act as a mere backdrop for the virtual world; however, many game designers claim that the stories can be very relevant for the player’s experience. For this reason we are looking for a methodology that improves the variability of the characters’ personality while enhancing the quality of their backstories following artistic or literary guidelines. In previous works, we used multi agent systems in order to obtain stochastic, but regulated, inter-relations that became backstories; later, we have used genetic algorithms to promote the appearance of high level behaviors inside them. Our current work continues the previous research line and propose a three layered system (Evolutionary computation - Agent-Based Model - Logical Reasoner) that is applied to the promotion of the monomyth, commonly known as the hero’s journey, a social pattern that constantly appears in literature, films, and videogames. As far as we know, there is no previous attempt to model the monomyth as a logical theory, and no attempt to use the sub-solutions for narrating purposes. Moreover, this paper shows for the first time this multi-paradigm three-layered methodology to generate massive backstories. Different metrics have been tested in the experimental phase, from those that sum all the monomyth-related tropes to those that promote distribution of archetypes in the characters. Results confirm that the system can make the monomyth emerge and that the metric has to take into account facilitator predicates in order to guide the evolutionary process.

In this paper, we show how a dangerousness metric can be used to modify the input of a gene regulatory network when plugged to a virtual car. In the context of the 2015 Simulated Car Racing Championship organized during GECCO 2015, we have developed a new cartography methodology able to inform the controller of the car about the incoming complexity of the track: turns (slipperiness, angle, etc.) and bumps. We show how this dangerousness metric improves the results of our controller and outperforms other approaches on the tracks used in the competition.

The virtual terrain for a video game generally needs to exhibit a collection of gameplay elements, such as some areas suitable for hiding and others for large scale battles. A key problem in automating terrain design is the lack of a quantitative definition of terrain gameplay elements. In this paper, we address the problem by proposing a representation for gameplay elements based on a combination of space-based isovist measures from the field of architecture and graph-connectivity metrics. We then propose a genetic algorithm-based approach that evolves a set of modifications to an existing terrain so as to exhibit the gameplay element characteristics. The potential for this approach in the design of computer game environments is examined by generating terrain containing instances of the “hidden area” game element type. Results from four preliminary tests are described to show the potential of this research.

This paper presents a spatially-structured evolutionary algorithm (EA) to procedurally generate game maps of different levels of difficulty to be solved, in Gravityvolve!, a physics-based simulation videogame that we have implemented and which is inspired by the n-body problem, a classical problem in the field of physics and mathematics. The proposal consists of a steady-state EA whose population is partitioned into three groups according to the difficulty of the generated content (hard, medium or easy) which can be easily adapted to handle the automatic creation of content of diverse nature in other games. In addition, we present three fitness functions, based on multiple criteria (i.e., intersections, gravitational acceleration and simulations), that were used experimentally to conduct the search process for creating a database of maps with different difficulty in Gravityvolve!.

Due to the manifold challenges that arise when developing an artificial intelligence that can compete with human players, the popular realtime-strategy game Starcraft: Broodwar (BW) has received attention from the computational intelligence research community. It is an ideal testbed for methods for self-adaption at runtime designed to work in complex technical systems. In this work, we utilize the broadlys-used Extended Classifier System (XCS) as a basis to develop different models of BW micro AIs: the Defender, the Attacker, the Explorer and the Strategist. We evaluate theses AIs with a focus on their adaptive and co-evolutionary behaviors. To this end, we stage and analyze the outcomes of a tournament among the proposed AIs and we also test them against a non-adaptive player to provide a proper baseline for comparison and learning evolution. Of the proposed AIs, we found the Explorer to be the best performing design, but, also that the Strategist shows an interesting behavioral evolution.

Many industrial and real-world datasets suffer from an unavoidable problem of missing values. The problem of missing data has been addressed extensively in the statistical analysis literature, and also, but to a lesser extent in the classification literature. The ability to deal with missing data is an essential requirement for classification because inadequate treatment of missing data may lead to large errors on classification. Feature selection has been successfully used to improve classification, but it has been applied mainly to complete data. This paper develops a wrapper feature selection approach to classification with missing data and investigates the impact of this approach. Empirical results on 10 datasets with missing values using C4.5 for an evaluation and particle swarm optimisation as a search technique in feature selection show that a wrapper feature selection for missing data not only can help to improve accuracy of the classifier, but also can help to reduce the complexity of the learned classification model.

Feature selection and discretisation have shown their effectiveness for data preprocessing especially for high-dimensional data with many irrelevant features. While feature selection selects only relevant features, feature discretisation finds a discrete representation of data that contains enough information but ignoring some minor fluctuation. These techniques are usually applied in two stages, discretisation and then selection since many feature selection methods work only on discrete features. Most commonly used discretisation methods are univariate in which each feature is discretised independently; therefore, the feature selection stage may not work efficiently since information showing feature interaction is not considered in the discretisation process. In this study, we propose a new method called PSO-DFS using bare-bone particle swarm optimisation (BBPSO) for discretisation and feature selection in a single stage. The results on ten high-dimensional datasets show that PSO-DFS obtains a substantial dimensionality reduction for all datasets. The classification performance is significantly improved or at least maintained on nine out of ten datasets by using the transformed “small” data obtained from PSO-DFS. Compared to applying the two-stage approach which uses PSO for feature selection on the discretised data, PSO-DFS achieves better performance on six datasets, and similar performance on three datasets with a much smaller number of features selected.

Feature selection is a pre-processing step in classification, which selects a small set of important features to improve the classification performance and efficiency. Mutual information is very popular in feature selection because it is able to detect non-linear relationship between features. However the existing mutual information approaches only consider two-way interaction between features. In addition, in most methods, mutual information is calculated by a counting approach, which may lead to an inaccurate results. This paper proposes a filter feature selection algorithm based on particle swarm optimization (PSO) named PSOMIE, which employs a novel fitness function using nearest neighbor mutual information estimation (NNE) to measure the quality of a feature set. PSOMIE is compared with using all features and two traditional feature selection approaches. The experiment results show that the mutual information estimation successfully guides PSO to search for a small number of features while maintaining or improving the classification performance over using all features and the traditional feature selection methods. In addition, PSOMIE provides a strong consistency between training and test results, which may be used to avoid overfitting problem.

Automatic Speaker Verification (ASV) is a highly unbalanced binary classification problem, in which any given speaker must be verified against everyone else. We apply Genetic programming (GP) to this problem with the aim of both prediction and inference. We examine the generalisation of evolved programs using a variety of fitness functions and data sampling techniques found in the literature. A significant difference between train and test performance, which can indicate overfitting, is found in the evolutionary runs of all to-be-verified speakers. Nevertheless, in all speakers, the best test performance attained is always superior than just merely predicting the majority class. We examine which features are used in good-generalising individuals. The findings can inform future applications of GP or other machine learning techniques to ASV about the suitability of feature-extraction techniques.

This paper presents a novel reconstruction algorithm for binary tomography based on the movement of particles. Particle Aggregate Reconstruction Technique (PART) supposes that pixel values are particles, and that the particles can diffuse through the image, sticking together in regions of uniform pixel value known as aggregates. The algorithm is tested on four phantoms of varying sizes and numbers of forward projections and compared to a random search algorithm and to SART, a standard algebraic reconstruction method. PART, in this small study, is shown to be capable of zero error reconstruction and compares favourably with SART and random search.

A population based ant optimization algorithm (PACO) for reconstructing electrocardiogram (ECG) signals is proposed in this paper. In particular, the PACO algorithm is used to find a subset of nonzero positions of a sparse wavelet domain ECG signal vector which is used for the reconstruction of a signal. The proposed PACO algorithm uses a time window for fixing certain decisions of the ants during the run of the algorithm. The optimization behaviour of the PACO is compared with two random search heuristics and several algorithms from the literature for ECG signal reconstruction. Experimental results are presented for ECG signals from the MIT-BIT Arrhythmia database. The results show that the proposed PACO reconstructs ECG signals very successfully.

Finding the best possible sequence of control actions for a hybrid car in order to minimize fuel consumption is a well-studied problem. A standard method is Dynamic Programming (DP) that is generally considered to provide solutions close to the global optimum in relatively short time. To our knowledge Evolutionary Algorithms (EAs) have so far not been used for this setting, due to the success of DP. In this work we compare DP and EA for a well-studied example and find that for the basic scenario EA is indeed clearly outperformed by DP in terms of calculation time and quality of solutions. But, we also find that when going beyond the standard scenario towards more realistic (and complex) scenarios, EAs can actually deliver a performance en par or in some cases even exceeding DP, making them useful in a number of relevant application scenarios.

This paper introduces an auto-calibration mechanism for an Automatic Number Plate Recognition camera dedicated to a vehicle speed measurement. A calibration task is formulated as a multi-objective optimization problem and solved with Non-dominated Sorting Genetic Algorithm. For simplicity a uniform motion profile of a majority of vehicles is assumed. The proposed speed estimation method is based on tracing licence plates quadrangles recognized on video frames. The results are compared with concurrent measurements performed with piezoelectric sensors.

Reactive systems interact continuously with their environments. In order to test such systems, one needs to design executable environment models. Such models are intrinsically stochastic, because environment may vary a lot, and also because they are not perfectly known. We propose an environment-model based testing framework optimized for reactive systems, where Differential Evolution (de ) is used to fine-tune the environment model and to optimize test input generation. In order to evaluate the proposed method, we present a case study involving a real-world scade system from the domain of railway automation. The problem specification was proposed by our industrial partner, Siemens. Our experimental data shows that de can be used efficiently to increase the structural coverage of the System Under Test.

Call centres are an important tool that businesses use to interact with their clients. Their efficiency is especially significant since long queuing times can reduce customer satisfaction. Assembling the call centre work schedule is a complex task that needs to take various and often mutually conflicting goals into account. In this paper, we present a workforce scheduling system suited for small to medium call centres and adjusted to the needs of two real–world client institutions. The scheduling problem is to minimise the difference between allocated and forecasted number of staff members while also caring for numerous legal and organisational constraints as well as staff preferences. A flexible constraint handling framework is devised to enable rapid prototyping methodology used during the development. Based on it, two metaheuristics are devised for schedule construction: GRASP and iterated local search. Performance analysis and comparisons for these two methods are provided, on a real–world problem example. The devised system is successfully implemented in a real world setting of call centres at PBZCard, Croatian largest credit card vendor and PBZ (Intesa Sanpaolo), one of the largest Croatian banks.