please note that the final order of presentations may change
Wednesday 11th April
Parallel 1 (11:20 – 13:00)
evopar (room 3)
A Fair Comparison of Modern CPUs and GPUs Running the Genetic Algorithm under the Knapsack Benchmark (best paper nominee)
Jiri Jaros, Petr Pospochal
The paper introduces an optimized multicore CPU implementation of the genetic algorithm and compares its performance with a fine-tuned GPU version. The main goal is to show the true performance relation between modern CPUs and GPUs and eradicate some of myths surrounding GPU performance. It is essential for the evolutionary community to provide the same conditions and designer effort to both implementations when benchmarking CPUs and GPUs. Here we show the performance comparison supported by architecture characteristics narrowing the performance gain of GPUs.
Validating a Peer-to-Peer Evolutionary Algorithm
Juan Luis Jiménez Laredo, Pascal Bouvry, Sanaz Mostaghim, Juan-J Merelo-Guervós
This paper proposes a simple experiment for validating a Peer-to-Peer Evolutionary Algorithm in a real computing infrastructure in order to verify that results meet those obtained by simulations. The validation method consists of conducting a well-characterized experiment in a large computer cluster of up to a number of processors equal to the population estimated by the simulator. We argue that the validation stage is usually missing in the design of large-scale distributed meta-heuristics given the difficulty of harnessing a large number of computing resources. That way, most of the approaches in the literature focus on studying the model viability throughout a simulation-driven experimentation. However, simulations assume idealistic conditions that can influence the algorithmic performance and bias results when conducted in a real platform. Therefore, we aim at validating simulations by running a real version of the algorithm. Results show that the algorithmic performance is rather accurate to the predicted one whilst times-to-solutions can be drastically decreased when compared to the estimation of a sequential run.
OpenCL Implementation of Particle Swarm Optimization: A Fair Comparison between CPU and GPU Performances
Stefano Cagnoni, Alessandro Bacchini, Luca Mussi
GPU-based parallel implementations of algorithms are usually compared against the corresponding sequential versions compiled for a single-core CPU machine, without taking advantage of the multi-core and SIMD capabilities of modern processors. This leads to unfair comparisons, where speed-up figures are much larger than what could actually be obtained if the CPU-based version were properly parallelized and optimized. The availability of OpenCL, which compiles parallel code for both GPUs and multi-core CPUs, has made it much easier to compare execution speed of different architectures fully exploiting each architecture’s best features. We tested our latest parallel implementations of Particle Swarm Optimization (PSO), compiled under OpenCL for both GPUs and multi-core CPUs, and separately optimized for the two hardware architectures. Our results show that, for PSO, a GPU-based parallelization is still generally more efficient than a multi-core CPU-based one. However, the speed-up obtained by the GPU-based with respect to the CPU-based version is by far lower than the orders-of-magnitude figures reported by the papers which compare GPU-based parallel implementations to basic single-thread CPU code.
FlexGP: Genetic Programming on the Cloud (best paper nominee)
Dylan Sherry, Kalyan Veeramachaneni, James McDermott, Una-May O’Reilly
We describe FlexGP, which we believe to be the first large-scale genetic programming cloud computing system. We took advantage of existing software and selected a socket-based, client-server architecture and an island-based distribution model. We developed core components required for deployment on Amazon’s Elastic Compute Cloud. Scaling the system to hundreds of nodes presented several unexpected challenges and required the development of software for automatically managing deployment, reporting, and error handling. The system’s performance was evaluated on two metrics, performance and speed, on a difficult symbolic regression problem. Our largest successful FlexGP runs reached 350 nodes and taught us valuable lessons for the next phase of scaling.
evocomplex (room 4)
Small-World Optimization applied to Job Scheduling on Grid Environments from a Multi-Objective perspective
María Arsuaga-Ríos, Francisco Prieto-Castrillo, Miguel A. Vega-Rodríguez
Grid scheduling techniques are widely studied in the related literature to fulfill scientist requirements of deadline or budget for their experiments. Due to the conflictive nature of these requirements -minimum response time usually implies expensive resources – a multi-objective approach is implemented to solve this problem. In this paper, we present the Multi-Objective Small World Optimization (MOSWO) as a multi-objective adaptation from algorithms based on the small world phenomenon. This novel algorithm exploits the so-called small-world effect from complex networks, to optimize the job scheduling on Grid environments. Our algorithm has been compared with the well-known multi-objective algorithm Non-dominated Sorting Genetic Algorithm-II (NSGA-II) to evaluate the multi-objective properties and prove its reliability. Moreover, MOSWO has been compared with real schedulers, the Workload Management System (WMS) from gLite and the Deadline Budget Constraint (DBC) from Nimrod-G, improving their results.
Sales Potential Optimization on Directed Social Networks: A Quasi-Parallel Genetic Algorithm Approach
Crown Guan Wang, Kwok Yip Szeto
A new node centrality measurement for directed networks called the Sales Potential is introduced with the property that nodes with high Sales Potential have small in-degree and high second-shell in-degree. Such nodes are of great importance in online marketing strategies for sales agents and IT security in social networks. We propose an optimization problem that aims at finding a finite set of nodes, so that their collective Sales Potential is maximized. This problem can be efficiently solved with a Quasi-parallel Genetic Algorithm defined on a given topology of sub-populations. We find that the algorithm with a small number of sub-populations gives results with higher quality than one with a large number of sub-populations, though at the price of slower convergence.
An Empirical Tool for Analysing the Collective Behaviour of Population-based Algorithms (best paper nominee)
Mikdam Turkey, Riccardo Poli
Understanding the emergent collective behaviour (and the properties associated with it) of population-based algorithms is an important prerequisite for making technically sound choices of algorithms and also for designing new algorithms for specific applications. In this paper, we present an empirical approach to analyse and quantify the collective emergent behaviour of populations. In particular, our long term objective is to understand and characterise the notions of exploration and exploitation and to make it possible to characterise and compare algorithms based on such notions. The proposed approach uses self-organising maps as a tool to track the population dynamics and extract features that describe a population “functionality” and “structure”.
The Emergence of Multi-Robot Organisms using On-line On-board evolution (best paper nominee)
Berend Weel, Evert Haasdijk, A.E. Eiben
We investigate whether a swarm of robots can evolve controllers that cause aggregation into `multi-cellular’ robot organisms without a specific reward to do so. To this end, we create a world where aggregated robots receive more energy than individual ones and enable robots to evolve their controllers on-the-fly, during their lifetime. We perform experiments in six different implementations of the basic idea distinguished by the system of energy distribution and the level of advantage aggregated robots have over individual ones. The results show that `multi-cellular’ robot organisms emerge in all of these cases.
evofin (room 5)
Evolutionary Data Selection for Enhancing Models of Intraday Forex Time Series
Michael Mayo
The hypothesis in this paper is that a significant amount of intraday market data is either noise or redundant, and that if it is eliminated, then predictive models built using the remaining intraday data will be more accurate. To test this hypothesis, we use an evolutionary method (called Evolutionary Data Selection, EDS) to selectively remove out portions of training data that is to be made available to an intraday market predictor. After performing experiments in which data-selected and non-data-selected versions of the same predictive models are compared, it is shown that EDS is effective and does indeed boost predictor accuracy. It is also shown in the paper that building multiple models using EDS and placing them into an ensemble further increases performance. The datasets for evaluation are large intraday forex time series, specifically series from the EUR/USD, the USD/JPY and the EUR/JPY markets, and predictive models for two primary tasks per market are built: intraday return prediction and intraday volatility prediction.
Steepest Ascent Hill Climbing for Portfolio Selection (best paper nominee)
Jonathan Arriaga, Manuel Valenzuela-Rendón
The construction of a portfolio in the financial field is a problem faced by individuals and institutions worldwide. In this paper we present an approach to solve the portfolio selection problem with the Steepest Ascent Hill Climbing algorithm. There are many works reported in the literature that attempt to solve this problem using evolutionary methods. We analyze the quality of the solutions found by a simpler algorithm and show that its performance is similar to a Genetic Algorithm, a more complex method. Real world restrictions such as portfolio value and rounded lots are considered to give a realistic approach to the problem.
A GA combining Technical and Fundamental Analysis for trading the Stock Market
Iván Contreras, José Ignacio Hidalgo, Laura Núñez-Letamendia
Nowadays, there are two types of financial analysis oriented to design trading systems: fundamental and technical. Fundamental analysis consists in the study of all information (both financial and nonfinancial) available on the market, with the aim of carrying out efficient investments. By contrast, technical analysis works under the assumption that when we analyze the price action in a specific market, we are (indirectly) analyzing all the factors related to the market. In this paper we propose the use of an Evolutionary Algorithm to optimize the parameters of a trading system which combines Fundamental and Technical analysis (indicators). The algorithm takes advantage of a new operator called Filling Operator which avoids problems of premature convergence and reduce the number of evaluations needed. The experimental results are promising, since when the methodology is applied to values of 100 companies in a year, they show a possible return of 830% compared with a 180% of the Buy and Hold strategy.
A Neuro-Evolutionary Approach to Intraday Financial Modeling (best paper nominee)
Antonia Azzini, Mauro Dragoni, Andrea G.B. Tettamanzi
We investigate the correlations among the intraday prices of the major stocks of the Milan Stock Exchange by means of a neuro-evolutionary modeling method. In particular, the method used to approach such problem is to apply a very powerful natural computing analysis tool, namely evolutionary neural networks, based on the joint evolution of the topology and the connection weights together with a novel similarity-based crossover, to the analysis of a financial intraday time series expressing the stock quote variations of the FTSE MIB components. We show that it is possible to obtain extremely accurate models of the variations of the price of one stock based on the price variations of the other components of the stock list, which may be used for statistical arbitrage.
Parallel 2 (14:30 – 16:10)
evogames (room 3)
Evolving Third-Person Shooter Enemies to Optimize Player Satisfaction in Real-Time
José M. Font
A grammar-guided genetic program is presented to automatically build and evolve populations of AI controlled enemies in a 2D third-person shooter called Genes of War. This evolutionary system constantly adapts enemy behaviour, encoded by a multi-layered fuzzy control system, while the game is being played. Thus the enemy behaviour fits a target challenge level for the purpose of maximizing player satisfaction. Two different methods to calculate this challenge level are presented: “hardwired” that allows the desired difficulty level to be programed at every stage of the gameplay, and “adaptive” that automatically determines difficulty by analyzing several features extracted from the player’s gameplay. Results show that the genetic program successfully adapts armies of ten enemies to different kinds of players and difficulty distributions.
Why Simulate? Hybrid Biological-Digital Games
Maarten H. Lamers, Wim van Eck
Biologically inspired algorithms (neural networks, evolutionary computation, swarm intelligence, etcetera) are commonly applied in development of digital games. We argue that there are opportunities and possibilities for integrating real biological organisms inside computer games, with potential added value to the game’s player, developer and integrated organism. In this approach, live organisms are an integral part of digital gaming technology or player experience. To spark further thought and research into the concept of hybrid biological-digital games, we present an overview of its opportunities for creating computer games. Opportunities are categorized by their mainly affected stakeholder: game player, game designer, and bio-digital integrated organism. We clarify the categorization via numerous examples of existing hybrid bio-digital games. Based on our review work we present conclusions about the current state and future outlook for hybrid bio-digital games.
Monte-Carlo Tree Search for the Physical Travelling Salesman Problem
Diego Perez, Philipp Rohlfshagen, Simon Lucas
The significant success of MCTS in recent years, particularly in the game Go, has led to the application of MCTS to numerous other domains. In an ongoing effort to better understand the performance of MCTS in open-ended real-time video games, we apply MCTS to the Physical Travelling Salesman Problem (PTSP). We discuss different approaches to tailor MCTS to this particular problem domain and subsequently identify and attempt to overcome some of the apparent shortcomings. Results show that suitable heuristics can boost the performance of MCTS significantly in this domain. However, visualisations of the search indicate that MCTS is currently seeking solutions in a rather greedy manner, and coercing it to balance short term and long term constraints for the PTSP remains an open problem.
Dealing with Noisy Fitness in a RTS Game Bot Design (best paper nominee)
Antonio Mora, Antonio Fernández-Ares, Juan-J Merelo-Guervós, Pablo García-Sánchez
This work describes an evolutionary algorithm (EA) for evolving the constants, weights and probabilities of a rule-based decision engine of a bot designed to play the Planet Wars game. The evaluation of the individuals is based on the result of some non-deterministic combats, whose outcome depends on random draws as well as the enemy action, and is thus noisy. This noisy fitness is addressed in the EA and then, its effects are deeply analysed in the experimental section. The conclusions shows that reducing randomness via repeated combats and re-evaluations reduces the effect of the noisy fitness, making then the EA an effective approach for solving the problem.
evocomplex (room 4)
Evolutionary Optimization of Pheromone-based Stigmergic Communication
Tuze Kuyucu, Ivan Tanev, Katsunori Shimohara
Pheromone-based stigmergic communication is well suited for the coordination of swarm of robots in the exploration of unknown areas. We introduce a guided probabilistic exploration of an unknown environment by combining random movement and stigmergic guidance. Pheromone-based stigmergic communication among simple entities features various complexities that have significant effects on the overall swarm coordination, but are poorly understood. We propose a genetic algorithm for the optimization of parameters related to pheromone-based stigmergic communication. As a result, we achieve human-competitive tuning and obtain a better understanding of these parameters.
Analyzing Dynamic Fitness Landscapes of the Targeting Problem of Chaotic Systems (best paper nominee)
Hendrik Richter
Targeting is a control concept using fundamental properties of chaotic systems. Calculating the targeting control can be related to solving a dynamic optimization problem for which a dynamic fitness landscape can be formulated. We define the dynamic fitness landscape for the targeting problem and analyze numerically its properties. In particular, we are interested in the modality of the landscape and its fractal characteristics.
Hyperparameter Tuning in Bandit-Based Adaptive Operator Selection
Maciej Pacula, Jason Ansel, Saman Amarasinghe, Una-May O’Reilly
We are using bandit-based adaptive operator selection while autotuning parallel computer programs. The autotuning, which uses evolutionary algorithm-based stochastic sampling, takes place over an extended duration and occurs in situ as programs execute. The environment or context during tuning is either largely static in one scenario or dynamic in another. We rely upon adaptive operator selection to dynamically generate worthy test configurations of the program. In this paper, we study how the choice of hyperparameters, which control the trade-off between exploration and exploitation, affects the effectiveness of adaptive operator selection which in turn affects the performance of the autotuner. We show that while the optimal assignment of hyperparameters varies greatly between different benchmarks, there exists a single assignment, for a context, of hyperparameters that performs well regardless of the program being tuned.
evofin (room 5)
Evolving Seasonal Forecasting Models with Genetic Programming for Pricing Weather-derivatives (best paper nominee)
Alexandros Agapitos, Michael O’Neill, Anthony Brabazon
In this study we evolve seasonal forecasting temperature models, using Genetic Programming (GP), in order to provide an accurate, localised, long-term forecast of a temperature profile as part of the broader process of determining appropriate pricing model for weather-derivatives, financial instruments that allow organisations to protect themselves against the commercial risks posed by weather fluctuations. Two different approaches for time-series modelling are adopted. The first is based on a simple system identification approach whereby the temporal index of the time-series is used as the sole regressor of the evolved model. The second is based on iterated single-step prediction that resembles autoregressive and moving average models in statistical time-series modelling. Empirical results suggest that GP is able to successfully induce seasonal forecasting models, and that autoregressive models compose a more stable unit of evolution in terms of generalisation performance for the three datasets investigated.
A Comparative Study of Multi-Objective Evolutionary Algorithms to Optimize the Selection of Investment Portfolios with Cardinality Constraints
Feijoo E. Colomine Duran, Carlos Cotta, Antonio J. Fernández-Leiva
We consider the problem of selecting investment components according to two partially opposed measures: the portfolio performance and its risk. We approach this within Markowitz’s model, considering the case of mutual funds market in Europe until July 2010. Comparisons were made on three multi-objective evolutionary algorithms, namely NSGA-II, SPEA2 and IBEA. Two well-known performance measures are considered for this purpose: hypervolume and R_2 indicator. The comparative analysis also includes an assessment of the financial efficiency of the investment portfolio selected according to Sharpe’s index, which is a measure of performance/risk. The experimental results hint at the superiority of the indicator-based evolutionary algorithm.
evostim (room 5)
Optimizing the Unlimited Shift Generation Problem
Nico Kyngas, Dries Goossens, Kimmo Nurmi, Jari Kyngas
Good rosters have many benefits for an organization, such as lower costs, more effective utilization of resources and fairer workloads. This paper introduces the unlimited shift generation problem. The problem is to construct a set of shifts such that the staff demand at each timeslot is covered by a suitable number of employees. A set of real-world instances derived from the actual problems solved for various companies is presented, along with our results. This research has contributed to better systems for our industry partners.
A Novel Multiobjective Formulation of the Robust Software Project Scheduling Problem
Francisco Chicano, Alejandro Cervantes, Francisco Luna, Gustavo Recio
The Software Project Scheduling (SPS) problem refers to the distribution of tasks during a software project lifetime. Software development involves managing human resources and a total budget in an optimal way for a successful project which, in turn, demonstrates the importance of the SPS problem for software companies. This paper proposes a novel formulation for the SPS problem which takes into account actual issues such as the productivity of the employees at performing different tasks. The formulation also provides project managers with robust solutions arising from an analysis of the inaccuracies in task-cost estimations. An experimental study is presented which compares the resulting project plans and analyses the performance of four different well-know evolutionary algorithms over two sets of realistic instances representing the problem. Statistical parameters are also provided in order to help the project manager in the decision process.
Parallel 3 (16:30 – 18:10)
evogames (room 3)
Initial Results From Co-operative Co-evolution For Automated Platformer Design (best paper nominee)
Michael Cook, Simon Colton, Jeremy Gow
We present initial results from ACCME, A Co-operative Co-evolutionary Metroidvania Engine, which uses co-operative co-evolution to automatically evolve simple platform games. We describe the system in detail and justify the use of co-operative co-evolution. We then address two fundamental questions about the use of this method in automated game design, both in terms of its ability to maximise fitness functions, and whether our choice of fitness function produces scores which correlate with player preference in the resulting games.
Digging Deeper into Platform Game Level Design: Session Size and Sequential Features (best paper nominee)
Noor Shaker, Georgios Yannakakis, Julian Togelius
A recent trend within computational intelligence and games research is to investigate how to affect video game players’ in-game experience by designing and/or modifying aspects of game content. Analysing the relationship between game content, player behaviour and self-reported affective states constitutes an important step towards understanding game experience and constructing effective game adaptation mechanisms. This papers reports on further refinement of a method to understand this relationship by analysing data collected from players, building models that predict player experience and analysing what features of game and player data predict player affect best. We analyse data from players playing 780 pairs of short game sessions of the platform game Super Mario Bros, investigate the impact of the session size and what part of the level that has the major affect on player experience. Several types of features are explored, including item frequencies and patterns extracted through frequent sequence mining.
Diversified Virtual Camera Composition (best paper nominee)
Mike Preuss, Paolo Burelli, Georgios Yannakakis
The expressive use of virtual cameras and the automatic generation of cinematics within 3D environments shows potential to extend the communicative power of films into games and virtual worlds. In this paper we present a novel solution to the problem of virtual camera composition based on niching and restart evolutionary algorithms that addresses the problem of diversity in shot generation by simultaneously identifying multiple valid camera camera configurations. We asses the performance of the proposed solution against a set of state-of-the-art algorithms in virtual camera optimisation.
TORCS Competition: Presentation of the Results of the Evo* leg
Lanzi, Loiacono
Thursday 12th April
Posters (09:30 – 11:00)
evocomnet
Frequency Robustness Optimization with respect to Traffic Distribution for LTE System
Nourredine Tabia, Alexandre Gondran, Oumaya Baala, Alexandre Caminada
The Long Term Evolution (LTE) cellular network is based on Orthogonal Frequency Division Multiple Access (OFDMA) to meet several services and performance requirement. This paper shows the interest of robustness approach due to the uncertainty of traffic distribution while evaluating some antenna parameters. We use a greedy algorithm with different variants to show how a frequency parameter setting can impact the coverage performance indicator based on the SINR metric. The well-known frequency reuse schemes 1x3x3, whereby the entire bandwidth is divided into 3 non-overlapping groups and assigned to 3 co-site sectors within each cell, have been used in our model. Further work must be done on algorithmic approach.
evocomplex
Testing Diversity-Enhancing Migration Policies for Hybrid On-line Evolution of Robot Controllers
Pablo García-Sánchez, A.E. Eiben, Evert Haasdijk, Berend Weel, Juan-J Merelo-Guervós
We investigate on-line on-board evolution of robot controllers based on the so-called hybrid approach (island-based). Inherently to this approach each robot hosts a population (island) of evolving controllers and exchanges controllers with other robots at certain times. We compare different exchange (migration) policies in order to optimize this evolutionary system and compare the best hybrid setup with the encapsulated and distributed alternatives. We conclude that adding a difference-based migrant selection scheme increases the performance.
Self-Organization and Specialization in Multiagent Systems through Open-ended Natural Evolution
Pedro Trueba, Abraham Prieto, Francisco Bellas, Pilar Caamaño, Richard J. Duro
This paper deals with the problem of autonomously organizing the behavior of a multiagent system through a distributed approach based on open-ended natural evolution. We computationally simulate life-like dynamics and their evolution from the definition of local and low level interactions, as used in Artificial Life simulations, in a distributed evolutionary algorithm called ASiCo (Asynchronous Situated Coevolution). In this algorithm, the agents that make up the population are situated in the environment and interact in an open-ended fashion, leading to emergent states or solutions. The aim of this paper is to ana-lyze the capabilities of ASiCo for obtaining specialization in the multiagent sys-tem if required by the task. Furthermore, we want to study such specialization under changing conditions to show the intrinsic self-organization of this type of algorithm. The particular task selected here is multi-robot collective gathering, due to the suitability of ASiCo for its application to real robotic systems.
evogames
On Modeling, Evaluating and Increasing Players’ Satisfaction Quantitatively: Steps towards a Taxonomy
Mariela Nogueira, Carlos Cotta, Antonio J. Fernández-Leiva
This paper shows the results of a review about modeling, evaluating and increasing players’ satisfaction in computer games. The paper starts discussing the main stages of development of quantitative solutions, and then it tries to propose a taxonomy that represents the most common trends. In the first part of this paper we take as base some approaches that were already described in the literature for quantitatively capturing and increasing the real-time entertainment value in computer games. In a second part we analyze the stage in which the game’s environment is adapted in response to player needs, and the main trends on this theme are discussed.
Spicing up Map Generation
Tobias Mahlmann, Julian Togelius, Georgios N. Yannakakis
We describe a search-based map generator for the classic real-time strategy game Dune 2. The generator is capable of creating playable maps in seconds, which can be used with a partial recreation of Dune 2 that has been implemented using the Strategy Game Description Language. Map genotypes are represented as low-resolution matrices, which are then converted to higher-resolution maps through a stochastic process involving cellular automata. Map phenotypes are evaluated using a set of heuristics based on the gameplay requirements of Dune 2.
evonum
Applying (Hybrid) Metaheuristics to Fuel Consumption Optimization of Hybrid Electric Vehicles
Thorsten Krenek, Mario Ruthmair, Günther Raidl, Michael Planer
This work deals with the application of metaheuristics to the fuel consumption minimization problem of hybrid electric vehicles (HEV) considering exactly specified driving cycles. A genetic algorithm, a downhill-simplex method and an algorithm based on swarm intelligence are used to find appropriate parameter values aiming at fuel consumption minimization. Finally, the individual metaheuristics are combined to a hybrid optimization algorithm taking into account the strengths and weaknesses of the single procedures. Due to the required time-consuming simulations it is crucial to keep the number of candidate solutions to be evaluated low. This is partly achieved by starting the heuristic search with already meaningful solutions identified by a Monte-Carlo procedure. Experimental results indicate that the implemented hybrid algorithm achieves better results than previously existing optimization methods on a simplified HEV model.
evopar
Migration and Replacement Policies for Preserving Diversity in Dynamic Environments
David Millán-Ruiz, José Ignacio Hidalgo
This paper seeks to resolve the difficulties arising from the configuration and fine-tuning of a Parallel Genetic Algorithm (PGA) based on the Island Model, when the application domain is highly dynamic. This way, the reader will find a number of useful guidelines for setting up a PGA in a real, representative dynamic environment. To achieve this purpose, we examine different (existing and new) migration and replacement policies for three different topologies. Of course, there are many other factors that affect the performance of a PGA such as the topology, migrant selection, migration frequency, amount of migrants, replacement policy, number of processing nodes, synchronism type, configuration in the isolated islands, diversity of policies in different islands, etc which are also considered as a part of this study. The pivotal point of all the experiments conducted is the preservation of diversity by means of an appropriate balance between exploration and exploitation in the PGA’s search process when the application domain is highly dynamic and strong time constraints arise. The experimental phase is performed over two problem instances from a real-world dynamic environment which is the multi-skill call centre.
Distributed Simulated Annealing with MapReduce
Atanas Radenski
Simulated annealing’s high computational intensity has stimulated researchers to experiment with various parallel and distributed simulated annealing algorithms for shared memory, message-passing, and hybrid-parallel platforms. MapReduce is an emerging distributed computing framework for large-scale data processing on clusters of commodity servers; to our knowledge, MapReduce has not been used for simulated annealing yet. In this paper, we investigate the applicability of MapReduce to distributed simulated annealing in general, and to the TSP in particular. We (i) design six algorithmic patterns of distributed simulated annealing with MapReduce, (ii) instantiate the patterns into MR implementations to solve a sample TSP problem, and (iii) evaluate the solution quality and the speedup of the implementations on a cloud computing platform, Amazon’s Elastic MapReduce. Some of our patterns integrate simulated annealing with genetic algorithms. The paper can be beneficial for those interested in the potential of MapReduce in computationally intensive nature-inspired methods in general and simulated annealing in particular.
Pool-based Distributed Evolutionary Algorithms using an Object Database
Juan-J Merelo-Guervós, Antonio Mora, J. Albert Cruz, Anna I Esparcia
This work presents the mapping of an evolutionary algorithm to the CouchDB object store. This mapping decouples the population from the evolutionary algorithm, and allows a distributed and asynchronous operation of clients written in different languages. In this paper we present initial tests which prove that the novel algorithm design still performs as an evolutionary algorithm and try to find out what are the main issues concerning it, what kind of speedups should we expect, and how all this affects the fundamentals of the evolutionary algorithm.
A Library to Run Evolutionary Algorithms in the Cloud using MapReduce
Pedro Fazenda, James McDermott, Una-May O’Reilly
We discuss ongoing development of an evolutionary algorithm library to run on the cloud. We relate how we have used the Hadoop open-source MapReduce distributed data processing framework to implement a single “island” with a potentially very large population. The design generalizes beyond the current, one-off kind of MapReduce implementations. It is in preparation for the library becoming a modeling or optimization service in a service oriented architecture or a development tool for designing new evolutionary algorithms.
evorisk
Customized Normalcy Profiles for the Detection of Targeted Attacks
Victor Skormin, Tomas Nykodym, Andrey Dolgikh, James Antonakos
Functionality is the highest semantic level of the software behavior pyramid that reflects goals of the software rather than its specific implementation. Detection of malicious functionalities presents an effective way to detect malware in behavior-based IDS. A technology for mining system call data, discussed herein, results in the detection of functionalities representing operation of legitimate software within a closed network environment. The set of such functionalities combined with the frequencies of their execution constitutes a normalcy profile typical for this environment. Detection of deviations from this normalcy profile, new functionalities and/or changes in the execution frequencies, provides evidence of abnormal activity in the network caused by malware. This approach could be especially valuable for the detection of targeted zero-day attacks. The paper presents the results of the implementation and testing of the described technology on the computer network testbed.
Parallel 5 (14:30 – 16:10)
evoiasp (room 5)
Evolutionary Regression Machines for Precision Agriculture (best paper nominee)
Heikki Salo, Ville Tirronen, Ferrante Neri
This paper proposes an image processing/machine learning system for estimating the amount of biomass in a field. This piece of information is precious in agriculture as it would allow a controlled adjustment of water and fertilizer. This system consists of a flying robot device which captures multiple images of the area under interest. Subsequently, this set of images is processed by means of a combined action of digital elevation models and multispectral images in order to reconstruct a three-dimensional model of the area. This model is then processed by a machine learning device, i.e. a support vector regressor with multiple kernel functions, for estimating the biomass present in the area. The training of the system has been performed by means of three modern meta-heuristics representing the state-of-the-art in computational intelligence optimization. These three algorithms are based on differential evolution, particle swarm optimization, and evolution strategy frameworks, respectively. Numerical Results derived by empirical simulations show that the proposed approach can be of a great support in precision agriculture. In addition, the most promising results have been attained by means of an algorithm based on the differential evolution framework.
Electrocardiographic Signal Classification with Evolutionary Artificial Neural Networks
Antonia Azzini, Mauro Dragoni, Andrea G.B. Tettamanzi
This work presents an evolutionary ANN classifier system as an heart beat classification algorithm suitable for implementation on the PhysioNet/Computing in Cardiology Challenge 2011, whose aim is to develop an efficient algorithm able to run within a mobile phone, that can provide useful feedback in the process of acquiring a diagnostically useful 12-lead Electrocardiography (ECG) recording. The method used in such a problem is to apply a very powerful natural computing analysis tool, namely evolutionary neural networks, based on the joint evolution of the topology and the connection weights together with a novel similarity-based crossover. The work focuses on discerning between usable and unusable electrocardiograms tele-medically acquired from mobile embedded devices. A prepropcessing algorithm based on the Discrete Fourier Trasform has been applied before the evolutionary approach in order to extract the ECG feature dataset in the frequency domain. Finally, a series of tests has been carried out in order to evaluate the performance and the accuracy of the classifier system for such a challenge.
Evolving Visual Attention Programs through EVO Features
León Dozal, Gustavo Olague, Eddie Clemente, Marco Sánchez
Brain informatics (BI) is a field of interdisciplinary study covering topics such as attention, memory, language, computation, learning and creativity, just to say a few. The BI is responsible for studying the mechanisms of human information processing. The dorsal stream, or “where”stream, is intimately related to the processing of visual attention. This paper proposes to evolve VAPs that learn to attend a given object within a scene. Visual attention is usually divided in two stages: feature acquisition and feature integration. In both phases there are specialized operators in the acquisition of a specific feature, called EV Os, and on the fusion of these features, called EFI. In previous research, those referred operators were established without considering the goal to be achieved. Instead of using established operators the idea is to learn and optimize them for the visual attention task. During the experiments we used a standard database of images for visual attention. The results provided in this paper show that our approach achieves impressive performance in the problem of focus visual attention over complex objects in challenging real world images on the first try.
Evolutionary Purposive or Behavioral Vision: The Link between Perception and Action
Daniel Hernández, Gustavo Olague, Eddie Clemente, León Dozal
Active, animate, purposive or behavioral vision are all understood as a research area where a seeing system interacts with the world in such a way of creating a balance between perception and action. In particular, it is said that a selective perception process in combination with a specific motion-action works as a unique complex system that accomplishes a visuomotor task. In the present work, this is understood as a visual behavior. This work describes a real-working system composed of a camera mounted on a robotic manipulator that is used as a research platform for evolving a visual routine specially designed in the estimation of specific motion-actions. The idea is to evolve an interest point detector with the goal of simplifying a well-known simultaneous localization and map building system. Experimental results shows as a proof-of-concept that the proposed system is able to design a specific interest point detector for the case of a straight-line displacement with the advantage of eliminating a number of heuristics.
Parallel 6 (16:30 – 18:10)
evoiasp (room 5)
Object Recognition with an Optimized Visual Cortex Model using Genetic Programming (best paper nominee)
Eddie Clemente, Gustavo Olague, León Dozal, Martín Mancilla
Computational neuroscience is a discipline devoted to the study of brain function from an information processing standpoint. The ventral stream, also known as the “what” pathway, is widely accepted as the model for processing the visual information related to object identification. This paper proposes to evolve a mathematical description of the ventral stream where key features are identified in order to simplify the whole information processing. The idea is to create an artificial ventral stream by evolving the structure through an evolutionary computing approach. In previous research, the “what” pathway is described as being composed of two main stages: the interest region detection and feature description. For both stages a set of operations were identified with the aim of simplifying the total computational cost by avoiding a number of costly operations that are normally executed in the template matching and bag of feature approaches. Therefore, instead of applying a set of previously learned patches, product of an off-line training process, the idea is to enforce a functional approach. Experiments were carried out with a standard database and the results show that instead of 1200 operations, the new model needs about 200 operations.
A Genetic Fuzzy Rules Learning Approach for Unseeded Segmentation in Echography (best paper nominee)
Leonardo Bocchi, Francesco Rogai
Clinical practice in echotomography often requires effective and time-efficient procedures for segmenting anatomical structures to take medical decisions for therapy and diagnosis. In this work we present a methodology for image segmentation in echography with the aim to assist the clinician in these delicate tasks. A generic segmentation algorithm, based on region evaluation by means of a fuzzy rules based inference system (FRBS), is refined in a fully unseeded segmentation algorithm. Rules composing knowledge base are learned with a genetic algorithm, by comparing computed segmentation with human expert segmentation. Generalization capabilities of the approach are assessed with a larger test set and over different applications: breast lesions, ovarian follicles and anesthetic detection during brachial anesthesia.
On Evolutionary Approaches to Unsupervised Nearest Neighbor Regression
Oliver Kramer
The detection of structures in high-dimensional data has an important part to play in machine learning. Recently, we proposed a fast iterative strategy for non-linear dimensionality reduction based on the unsupervised formulation of K-nearest neighbor regression. As the unsupervised nearest neighbor (UNN) optimization problem does not allow the computation of derivatives, the employment of direct search methods is reasonable. In this paper we introduce evolutionary optimization approaches for learning UNN embeddings. Two continuous variants are based on the CMA-ES employing regularization with domain restriction, and penalizing extension in latent space. A combinatorial variant is based on embedding the latent variables on a grid, and performing stochastic swaps. We compare the results on artificial dimensionality reduction problems.
Friday 13th April<
Parallel 7 (09:30 – 11:10)
evostoc (room 2)
Ant Colony Optimization with Immigrants Schemes for the Dynamic Vehicle Routing Problem
Michalis Mavrovouniotis, Shengxiang Yang
Ant colony optimization (ACO) algorithms have proved to be able to adapt to dynamic optimization problems (DOPs) when they are enhanced to maintain diversity and transfer knowledge. Several approaches have been integrated with ACO to improve its performance for DOPs. Among these integrations, the ACO algorithm with immigrants schemes has shown good results on the dynamic travelling salesman problem. In this paper, we investigate ACO algorithms to solve a more realistic DOP, the dynamic vehicle routing problem (DVRP) with traffic factors. Random immigrants and elitism-based immigrants are applied to ACO algorithms, which are then investigated on different DVRP test cases. The results show that the proposed ACO algorithms achieve promising results, especially when elitism-based immigrants are used.
Virtual Loser Genetic Algorithm for Dynamic Environments
Anabela Simões, Ernesto Costa
Memory-based Evolutionary Algorithms in Dynamic Optimization Problems (DOPs) store the best solutions in order to reuse them in future situations. The memorization of the best solutions can be direct (the best individual of the current population is stored) or associative (additional information from the current population is also stored). This paper explores a different type of associative memory to use in Evolutionary Algorithms for DOPs. The memory stores the current best individual and a vector of inhibitions that reflect past errors performed during the evolutionary process. When a change is detected in the environment the best solution is retrieved from memory and the vector of inhibitions associated to this individual is used to create new solutions avoiding the repetition of past errors. This algorithm is called Virtual Loser Genetic Algorithm and was tested in different dynamic environments created using the XOR DOP generator. The results show that the proposed memory scheme significantly enhances the Evolutionary Algorithms in cyclic dynamic environments.
Evolving Communication in Robotic Swarms using On-line, On-board, Distributed Evolutionary Algorithms
Luis E. Pineda, A.E. Eiben, Marteen van Steen
Robotic swarms offer flexibility, robustness, and scalability. For successful operation they need appropriate communication strategies that should be dynamically adaptable to possibly changing environmental requirements. In this paper we try to achieve this through evolving communication on-the-fly. As a test case we use a scenario where robots need to cooperate to gather energy and the necessity to cooperate is scalable. We implement an evolutionary algorithm that works during the actual operation of the robots (on-line), where evolutionary operators are performed by the robots themselves (on-board) and robots exchange genomes with other robots for reproduction (distributed). We perform experiments with different cooperation pressures and observe that communication strategies can be successfully adapted to the particular demands of the environment.
evonum (room 4)
Towards a Deeper Understanding of Trade-offs using Multi-objective Evolutionary Algorithms
Pradyumn Kumar Shukla, Christian Hirsch, Hartmut Schmeck
A multi-objective optimization problem is characterized by multiple and conflicting objective functions. The conflicting nature of the objectives gives rise to the notion of trade-offs. A trade-off represents the ratio of change in the objective function values, when one of the objective function values increases and the value of some other objective function decreases. Various notions of trade-offs have been present in the classical multiple criteria decision making community and many scalarization approaches have been proposed in the literature to find a solution satisfying some given trade-off requirements. Almost all of these approaches are point-by-point algorithms. On the other hand, multi-objective evolutionary algorithms work with a population and, if properly designed, are able to find the complete preferred subset of the Pareto-optimal set satisfying a priori given bound on trade-offs. In this paper, we analyze and put together various notions of trade-offs that we find in the classical literature, classifying them into two groups. We then go on to propose multi-objective evolutionary algorithms to find solutions belonging to the two classified groups. This is done by modifying a state-of-the-art evolutionary algorithm NSGA-II. An extensive computational study substantiates the claims of the paper.
A Generic Approach to Parameter Control
Giorgos Karafotias, S.K. Smit, A.E. Eiben
On-line control of EA parameters is an approach to parameter setting that offers the advantage of values changing during the run. In this paper, we investigate parameter control from a generic and parameter-independent perspective. We propose a generic control mechanism that is targeted to repetitive applications, can be applied to any numeric parameter and is tailored to specific types of problems through an off-line calibration process. We present proof-of-concept experiments using this mechanism to control the mutation step size of an Evolutionary Strategy (ES). Results show that our method is viable and performs very well, compared to the tuning approach and traditional control methods.
Improved Topological Niching for Real-Valued Global Optimization
Mike Preuss
We show how nearest-better clustering, the core component of the NBC-CMA niching evolutionary algorithm, is improved by appyling a second heuristic rule. This leads to enhanced basin identification for higher dimensional (5D to 20D) optimization problems, where the NBC-CMA has previously shown only mediocre performance compared to other niching and global optimization algorithms. The new method is integrated into a niching algorithm (NEA2) and compared to NBC-CMA and BIPOP-CMA-ES via the BBOB benchmarking suite. It performs very well on problems that enable recognizing basins at all with reasonable effort (number of basins not too high, e.g. the Gallagher problems), as expected. Beyond that point, niching is obviously not applicable any more and random restarts as done by the CMA-ES are the method of choice.
evohot (room 4)
Robot Base Disturbance Optimization with Compact Differential Evolution Light
Giovanni Iacca, Fabio Caraffini, Ferrante Neri, Ernesto Mininno
Despite the constant growth of the computational power in consumer electronics, very simple hardware is still used in space applications. In order to obtain the highest possible reliability, in space systems limited-power but fully tested and certified hardware is used, thus reducing fault risks. Some space applications require the solution of an optimization problem, often plagued by real-time and memory constraints. In this paper, the disturbance to the base of a robotic arm mounted on a spacecraft is modeled, and it is used as a cost function for an online trajectory optimization process. In order to tackle this problem in a computationally efficient manner, addressing not only the memory saving necessities but also real-time requirements, we propose a novel compact algorithm, namely compact Differential Evolution light (cDElight). cDElight belongs to the class of Estimation of Distribution Algorithms (EDAs), which mimic the behavior of population-based algorithms by means of a probabilistic model of the population of candidate solutions. This model has a more limited memory footprint than the actual population. Compared to a selected set of memory-saving algorithms, cDElight is able to obtain the best results, despite a lower computational overhead.
evocomnet (room 5)
Evolutionary Design of Active Free Space Optical Networks Based on Digital Mirror Devices
Steffen Limmer, Dietmar Fey, Ulrich Lohmann, Jürgen Jahns
Optical connections have several advantages compared to conventional electrical connections, especially a higher attainable bandwidth. While long distance optical connections are already established, optical board- and chip-level connections are still a subject of current research. In this paper we describe a new setup for optical board-level connections which is based on free space optics and allows the switching of signals within the optical domain. We describe the evolutionary optimization of design parameters for the proposed setup, done with a memetic evolutionary algorithm and present the optimization results.
Optimizing Energy Consumption in Heterogeneous Wireless Sensor Networks by Means of Evolutionary Algorithms
José Manuel Lanza-Gutiérrez, Juan Antonio Gómez-Pulido, Miguel A. Vega-Rodríguez, Juan Manuel Sánchez-Pérez
The use of wireless sensor networks has been increased substantially. One of the main inconveniences of this kind of networks is the energy efficiency; for this reason, there are some works trying to solve it. Traditionally, these networks were only composed by sensors, but now auxiliary elements called routers have been included to facilitate communications and reduce energy consumption. In this work, we have studied the inclusion of routers in a previously established traditional wireless sensor network in order to increase its energy efficiency, optimizing lifetime and average energy effort. For this purpose, we have used two multi-objective evolutionary algorithms: NSGA-II and SPEA-2. We have done experiments over various sceneries, checking by means of statically techniques that SPEA-2 offers better results for more complex instances.
Protocol Discovery and Analysis via Live Interaction
Patrick LaRoche, A. Nur Zincir-Heywood, Malcolm I. Heywood
In this work, we explore the use of evolutionary computing toward protocol analysis. The ability to discover, analyse, and experiment with unknown protocols is paramount within the realm of network security; our approach to this crucial analysis is to interact with a network service, discovering sequences of commands that do not result in error messages. In so doing, our work investigates the real-life responses of a service, allowing for exploration and analysis of the protocol in question. Our system initiates sequences of commands randomly, interacts with and learns from the responses, and modifies its next set of sequences accordingly. Such an exploration results in a set of command sequences that reflect correct uses of the service in testing. These discovered sequences can then be used to identify the service, unforeseen uses of the service, and, most importantly, potential weaknesses.
draft programme evoapplications 2012
please note that the final order of presentations may change
Wednesday 11th April
Parallel 1 (11:20 – 13:00)
evopar (room 3)
A Fair Comparison of Modern CPUs and GPUs Running the Genetic Algorithm under the Knapsack Benchmark (best paper nominee)
Jiri Jaros, Petr Pospochal
The paper introduces an optimized multicore CPU implementation of the genetic algorithm and compares its performance with a fine-tuned GPU version. The main goal is to show the true performance relation between modern CPUs and GPUs and eradicate some of myths surrounding GPU performance. It is essential for the evolutionary community to provide the same conditions and designer effort to both implementations when benchmarking CPUs and GPUs. Here we show the performance comparison supported by architecture characteristics narrowing the performance gain of GPUs.
Validating a Peer-to-Peer Evolutionary Algorithm
Juan Luis Jiménez Laredo, Pascal Bouvry, Sanaz Mostaghim, Juan-J Merelo-Guervós
This paper proposes a simple experiment for validating a Peer-to-Peer Evolutionary Algorithm in a real computing infrastructure in order to verify that results meet those obtained by simulations. The validation method consists of conducting a well-characterized experiment in a large computer cluster of up to a number of processors equal to the population estimated by the simulator. We argue that the validation stage is usually missing in the design of large-scale distributed meta-heuristics given the difficulty of harnessing a large number of computing resources. That way, most of the approaches in the literature focus on studying the model viability throughout a simulation-driven experimentation. However, simulations assume idealistic conditions that can influence the algorithmic performance and bias results when conducted in a real platform. Therefore, we aim at validating simulations by running a real version of the algorithm. Results show that the algorithmic performance is rather accurate to the predicted one whilst times-to-solutions can be drastically decreased when compared to the estimation of a sequential run.
OpenCL Implementation of Particle Swarm Optimization: A Fair Comparison between CPU and GPU Performances
Stefano Cagnoni, Alessandro Bacchini, Luca Mussi
GPU-based parallel implementations of algorithms are usually compared against the corresponding sequential versions compiled for a single-core CPU machine, without taking advantage of the multi-core and SIMD capabilities of modern processors. This leads to unfair comparisons, where speed-up figures are much larger than what could actually be obtained if the CPU-based version were properly parallelized and optimized. The availability of OpenCL, which compiles parallel code for both GPUs and multi-core CPUs, has made it much easier to compare execution speed of different architectures fully exploiting each architecture’s best features. We tested our latest parallel implementations of Particle Swarm Optimization (PSO), compiled under OpenCL for both GPUs and multi-core CPUs, and separately optimized for the two hardware architectures. Our results show that, for PSO, a GPU-based parallelization is still generally more efficient than a multi-core CPU-based one. However, the speed-up obtained by the GPU-based with respect to the CPU-based version is by far lower than the orders-of-magnitude figures reported by the papers which compare GPU-based parallel implementations to basic single-thread CPU code.
FlexGP: Genetic Programming on the Cloud (best paper nominee)
Dylan Sherry, Kalyan Veeramachaneni, James McDermott, Una-May O’Reilly
We describe FlexGP, which we believe to be the first large-scale genetic programming cloud computing system. We took advantage of existing software and selected a socket-based, client-server architecture and an island-based distribution model. We developed core components required for deployment on Amazon’s Elastic Compute Cloud. Scaling the system to hundreds of nodes presented several unexpected challenges and required the development of software for automatically managing deployment, reporting, and error handling. The system’s performance was evaluated on two metrics, performance and speed, on a difficult symbolic regression problem. Our largest successful FlexGP runs reached 350 nodes and taught us valuable lessons for the next phase of scaling.
evocomplex (room 4)
Small-World Optimization applied to Job Scheduling on Grid Environments from a Multi-Objective perspective
María Arsuaga-Ríos, Francisco Prieto-Castrillo, Miguel A. Vega-Rodríguez
Grid scheduling techniques are widely studied in the related literature to fulfill scientist requirements of deadline or budget for their experiments. Due to the conflictive nature of these requirements -minimum response time usually implies expensive resources – a multi-objective approach is implemented to solve this problem. In this paper, we present the Multi-Objective Small World Optimization (MOSWO) as a multi-objective adaptation from algorithms based on the small world phenomenon. This novel algorithm exploits the so-called small-world effect from complex networks, to optimize the job scheduling on Grid environments. Our algorithm has been compared with the well-known multi-objective algorithm Non-dominated Sorting Genetic Algorithm-II (NSGA-II) to evaluate the multi-objective properties and prove its reliability. Moreover, MOSWO has been compared with real schedulers, the Workload Management System (WMS) from gLite and the Deadline Budget Constraint (DBC) from Nimrod-G, improving their results.
Sales Potential Optimization on Directed Social Networks: A Quasi-Parallel Genetic Algorithm Approach
Crown Guan Wang, Kwok Yip Szeto
A new node centrality measurement for directed networks called the Sales Potential is introduced with the property that nodes with high Sales Potential have small in-degree and high second-shell in-degree. Such nodes are of great importance in online marketing strategies for sales agents and IT security in social networks. We propose an optimization problem that aims at finding a finite set of nodes, so that their collective Sales Potential is maximized. This problem can be efficiently solved with a Quasi-parallel Genetic Algorithm defined on a given topology of sub-populations. We find that the algorithm with a small number of sub-populations gives results with higher quality than one with a large number of sub-populations, though at the price of slower convergence.
An Empirical Tool for Analysing the Collective Behaviour of Population-based Algorithms (best paper nominee)
Mikdam Turkey, Riccardo Poli
Understanding the emergent collective behaviour (and the properties associated with it) of population-based algorithms is an important prerequisite for making technically sound choices of algorithms and also for designing new algorithms for specific applications. In this paper, we present an empirical approach to analyse and quantify the collective emergent behaviour of populations. In particular, our long term objective is to understand and characterise the notions of exploration and exploitation and to make it possible to characterise and compare algorithms based on such notions. The proposed approach uses self-organising maps as a tool to track the population dynamics and extract features that describe a population “functionality” and “structure”.
The Emergence of Multi-Robot Organisms using On-line On-board evolution (best paper nominee)
Berend Weel, Evert Haasdijk, A.E. Eiben
We investigate whether a swarm of robots can evolve controllers that cause aggregation into `multi-cellular’ robot organisms without a specific reward to do so. To this end, we create a world where aggregated robots receive more energy than individual ones and enable robots to evolve their controllers on-the-fly, during their lifetime. We perform experiments in six different implementations of the basic idea distinguished by the system of energy distribution and the level of advantage aggregated robots have over individual ones. The results show that `multi-cellular’ robot organisms emerge in all of these cases.
evofin (room 5)
Evolutionary Data Selection for Enhancing Models of Intraday Forex Time Series
Michael Mayo
The hypothesis in this paper is that a significant amount of intraday market data is either noise or redundant, and that if it is eliminated, then predictive models built using the remaining intraday data will be more accurate. To test this hypothesis, we use an evolutionary method (called Evolutionary Data Selection, EDS) to selectively remove out portions of training data that is to be made available to an intraday market predictor. After performing experiments in which data-selected and non-data-selected versions of the same predictive models are compared, it is shown that EDS is effective and does indeed boost predictor accuracy. It is also shown in the paper that building multiple models using EDS and placing them into an ensemble further increases performance. The datasets for evaluation are large intraday forex time series, specifically series from the EUR/USD, the USD/JPY and the EUR/JPY markets, and predictive models for two primary tasks per market are built: intraday return prediction and intraday volatility prediction.
Steepest Ascent Hill Climbing for Portfolio Selection (best paper nominee)
Jonathan Arriaga, Manuel Valenzuela-Rendón
The construction of a portfolio in the financial field is a problem faced by individuals and institutions worldwide. In this paper we present an approach to solve the portfolio selection problem with the Steepest Ascent Hill Climbing algorithm. There are many works reported in the literature that attempt to solve this problem using evolutionary methods. We analyze the quality of the solutions found by a simpler algorithm and show that its performance is similar to a Genetic Algorithm, a more complex method. Real world restrictions such as portfolio value and rounded lots are considered to give a realistic approach to the problem.
A GA combining Technical and Fundamental Analysis for trading the Stock Market
Iván Contreras, José Ignacio Hidalgo, Laura Núñez-Letamendia
Nowadays, there are two types of financial analysis oriented to design trading systems: fundamental and technical. Fundamental analysis consists in the study of all information (both financial and nonfinancial) available on the market, with the aim of carrying out efficient investments. By contrast, technical analysis works under the assumption that when we analyze the price action in a specific market, we are (indirectly) analyzing all the factors related to the market. In this paper we propose the use of an Evolutionary Algorithm to optimize the parameters of a trading system which combines Fundamental and Technical analysis (indicators). The algorithm takes advantage of a new operator called Filling Operator which avoids problems of premature convergence and reduce the number of evaluations needed. The experimental results are promising, since when the methodology is applied to values of 100 companies in a year, they show a possible return of 830% compared with a 180% of the Buy and Hold strategy.
A Neuro-Evolutionary Approach to Intraday Financial Modeling (best paper nominee)
Antonia Azzini, Mauro Dragoni, Andrea G.B. Tettamanzi
We investigate the correlations among the intraday prices of the major stocks of the Milan Stock Exchange by means of a neuro-evolutionary modeling method. In particular, the method used to approach such problem is to apply a very powerful natural computing analysis tool, namely evolutionary neural networks, based on the joint evolution of the topology and the connection weights together with a novel similarity-based crossover, to the analysis of a financial intraday time series expressing the stock quote variations of the FTSE MIB components. We show that it is possible to obtain extremely accurate models of the variations of the price of one stock based on the price variations of the other components of the stock list, which may be used for statistical arbitrage.
Parallel 2 (14:30 – 16:10)
evogames (room 3)
Evolving Third-Person Shooter Enemies to Optimize Player Satisfaction in Real-Time
José M. Font
A grammar-guided genetic program is presented to automatically build and evolve populations of AI controlled enemies in a 2D third-person shooter called Genes of War. This evolutionary system constantly adapts enemy behaviour, encoded by a multi-layered fuzzy control system, while the game is being played. Thus the enemy behaviour fits a target challenge level for the purpose of maximizing player satisfaction. Two different methods to calculate this challenge level are presented: “hardwired” that allows the desired difficulty level to be programed at every stage of the gameplay, and “adaptive” that automatically determines difficulty by analyzing several features extracted from the player’s gameplay. Results show that the genetic program successfully adapts armies of ten enemies to different kinds of players and difficulty distributions.
Why Simulate? Hybrid Biological-Digital Games
Maarten H. Lamers, Wim van Eck
Biologically inspired algorithms (neural networks, evolutionary computation, swarm intelligence, etcetera) are commonly applied in development of digital games. We argue that there are opportunities and possibilities for integrating real biological organisms inside computer games, with potential added value to the game’s player, developer and integrated organism. In this approach, live organisms are an integral part of digital gaming technology or player experience. To spark further thought and research into the concept of hybrid biological-digital games, we present an overview of its opportunities for creating computer games. Opportunities are categorized by their mainly affected stakeholder: game player, game designer, and bio-digital integrated organism. We clarify the categorization via numerous examples of existing hybrid bio-digital games. Based on our review work we present conclusions about the current state and future outlook for hybrid bio-digital games.
Monte-Carlo Tree Search for the Physical Travelling Salesman Problem
Diego Perez, Philipp Rohlfshagen, Simon Lucas
The significant success of MCTS in recent years, particularly in the game Go, has led to the application of MCTS to numerous other domains. In an ongoing effort to better understand the performance of MCTS in open-ended real-time video games, we apply MCTS to the Physical Travelling Salesman Problem (PTSP). We discuss different approaches to tailor MCTS to this particular problem domain and subsequently identify and attempt to overcome some of the apparent shortcomings. Results show that suitable heuristics can boost the performance of MCTS significantly in this domain. However, visualisations of the search indicate that MCTS is currently seeking solutions in a rather greedy manner, and coercing it to balance short term and long term constraints for the PTSP remains an open problem.
Dealing with Noisy Fitness in a RTS Game Bot Design (best paper nominee)
Antonio Mora, Antonio Fernández-Ares, Juan-J Merelo-Guervós, Pablo García-Sánchez
This work describes an evolutionary algorithm (EA) for evolving the constants, weights and probabilities of a rule-based decision engine of a bot designed to play the Planet Wars game. The evaluation of the individuals is based on the result of some non-deterministic combats, whose outcome depends on random draws as well as the enemy action, and is thus noisy. This noisy fitness is addressed in the EA and then, its effects are deeply analysed in the experimental section. The conclusions shows that reducing randomness via repeated combats and re-evaluations reduces the effect of the noisy fitness, making then the EA an effective approach for solving the problem.
evocomplex (room 4)
Evolutionary Optimization of Pheromone-based Stigmergic Communication
Tuze Kuyucu, Ivan Tanev, Katsunori Shimohara
Pheromone-based stigmergic communication is well suited for the coordination of swarm of robots in the exploration of unknown areas. We introduce a guided probabilistic exploration of an unknown environment by combining random movement and stigmergic guidance. Pheromone-based stigmergic communication among simple entities features various complexities that have significant effects on the overall swarm coordination, but are poorly understood. We propose a genetic algorithm for the optimization of parameters related to pheromone-based stigmergic communication. As a result, we achieve human-competitive tuning and obtain a better understanding of these parameters.
Analyzing Dynamic Fitness Landscapes of the Targeting Problem of Chaotic Systems (best paper nominee)
Hendrik Richter
Targeting is a control concept using fundamental properties of chaotic systems. Calculating the targeting control can be related to solving a dynamic optimization problem for which a dynamic fitness landscape can be formulated. We define the dynamic fitness landscape for the targeting problem and analyze numerically its properties. In particular, we are interested in the modality of the landscape and its fractal characteristics.
Hyperparameter Tuning in Bandit-Based Adaptive Operator Selection
Maciej Pacula, Jason Ansel, Saman Amarasinghe, Una-May O’Reilly
We are using bandit-based adaptive operator selection while autotuning parallel computer programs. The autotuning, which uses evolutionary algorithm-based stochastic sampling, takes place over an extended duration and occurs in situ as programs execute. The environment or context during tuning is either largely static in one scenario or dynamic in another. We rely upon adaptive operator selection to dynamically generate worthy test configurations of the program. In this paper, we study how the choice of hyperparameters, which control the trade-off between exploration and exploitation, affects the effectiveness of adaptive operator selection which in turn affects the performance of the autotuner. We show that while the optimal assignment of hyperparameters varies greatly between different benchmarks, there exists a single assignment, for a context, of hyperparameters that performs well regardless of the program being tuned.
evofin (room 5)
Evolving Seasonal Forecasting Models with Genetic Programming for Pricing Weather-derivatives (best paper nominee)
Alexandros Agapitos, Michael O’Neill, Anthony Brabazon
In this study we evolve seasonal forecasting temperature models, using Genetic Programming (GP), in order to provide an accurate, localised, long-term forecast of a temperature profile as part of the broader process of determining appropriate pricing model for weather-derivatives, financial instruments that allow organisations to protect themselves against the commercial risks posed by weather fluctuations. Two different approaches for time-series modelling are adopted. The first is based on a simple system identification approach whereby the temporal index of the time-series is used as the sole regressor of the evolved model. The second is based on iterated single-step prediction that resembles autoregressive and moving average models in statistical time-series modelling. Empirical results suggest that GP is able to successfully induce seasonal forecasting models, and that autoregressive models compose a more stable unit of evolution in terms of generalisation performance for the three datasets investigated.
A Comparative Study of Multi-Objective Evolutionary Algorithms to Optimize the Selection of Investment Portfolios with Cardinality Constraints
Feijoo E. Colomine Duran, Carlos Cotta, Antonio J. Fernández-Leiva
We consider the problem of selecting investment components according to two partially opposed measures: the portfolio performance and its risk. We approach this within Markowitz’s model, considering the case of mutual funds market in Europe until July 2010. Comparisons were made on three multi-objective evolutionary algorithms, namely NSGA-II, SPEA2 and IBEA. Two well-known performance measures are considered for this purpose: hypervolume and R_2 indicator. The comparative analysis also includes an assessment of the financial efficiency of the investment portfolio selected according to Sharpe’s index, which is a measure of performance/risk. The experimental results hint at the superiority of the indicator-based evolutionary algorithm.
evostim (room 5)
Optimizing the Unlimited Shift Generation Problem
Nico Kyngas, Dries Goossens, Kimmo Nurmi, Jari Kyngas
Good rosters have many benefits for an organization, such as lower costs, more effective utilization of resources and fairer workloads. This paper introduces the unlimited shift generation problem. The problem is to construct a set of shifts such that the staff demand at each timeslot is covered by a suitable number of employees. A set of real-world instances derived from the actual problems solved for various companies is presented, along with our results. This research has contributed to better systems for our industry partners.
A Novel Multiobjective Formulation of the Robust Software Project Scheduling Problem
Francisco Chicano, Alejandro Cervantes, Francisco Luna, Gustavo Recio
The Software Project Scheduling (SPS) problem refers to the distribution of tasks during a software project lifetime. Software development involves managing human resources and a total budget in an optimal way for a successful project which, in turn, demonstrates the importance of the SPS problem for software companies. This paper proposes a novel formulation for the SPS problem which takes into account actual issues such as the productivity of the employees at performing different tasks. The formulation also provides project managers with robust solutions arising from an analysis of the inaccuracies in task-cost estimations. An experimental study is presented which compares the resulting project plans and analyses the performance of four different well-know evolutionary algorithms over two sets of realistic instances representing the problem. Statistical parameters are also provided in order to help the project manager in the decision process.
Parallel 3 (16:30 – 18:10)
evogames (room 3)
Initial Results From Co-operative Co-evolution For Automated Platformer Design (best paper nominee)
Michael Cook, Simon Colton, Jeremy Gow
We present initial results from ACCME, A Co-operative Co-evolutionary Metroidvania Engine, which uses co-operative co-evolution to automatically evolve simple platform games. We describe the system in detail and justify the use of co-operative co-evolution. We then address two fundamental questions about the use of this method in automated game design, both in terms of its ability to maximise fitness functions, and whether our choice of fitness function produces scores which correlate with player preference in the resulting games.
Digging Deeper into Platform Game Level Design: Session Size and Sequential Features (best paper nominee)
Noor Shaker, Georgios Yannakakis, Julian Togelius
A recent trend within computational intelligence and games research is to investigate how to affect video game players’ in-game experience by designing and/or modifying aspects of game content. Analysing the relationship between game content, player behaviour and self-reported affective states constitutes an important step towards understanding game experience and constructing effective game adaptation mechanisms. This papers reports on further refinement of a method to understand this relationship by analysing data collected from players, building models that predict player experience and analysing what features of game and player data predict player affect best. We analyse data from players playing 780 pairs of short game sessions of the platform game Super Mario Bros, investigate the impact of the session size and what part of the level that has the major affect on player experience. Several types of features are explored, including item frequencies and patterns extracted through frequent sequence mining.
Diversified Virtual Camera Composition (best paper nominee)
Mike Preuss, Paolo Burelli, Georgios Yannakakis
The expressive use of virtual cameras and the automatic generation of cinematics within 3D environments shows potential to extend the communicative power of films into games and virtual worlds. In this paper we present a novel solution to the problem of virtual camera composition based on niching and restart evolutionary algorithms that addresses the problem of diversity in shot generation by simultaneously identifying multiple valid camera camera configurations. We asses the performance of the proposed solution against a set of state-of-the-art algorithms in virtual camera optimisation.
TORCS Competition: Presentation of the Results of the Evo* leg
Lanzi, Loiacono
Thursday 12th April
Posters (09:30 – 11:00)
evocomnet
Frequency Robustness Optimization with respect to Traffic Distribution for LTE System
Nourredine Tabia, Alexandre Gondran, Oumaya Baala, Alexandre Caminada
The Long Term Evolution (LTE) cellular network is based on Orthogonal Frequency Division Multiple Access (OFDMA) to meet several services and performance requirement. This paper shows the interest of robustness approach due to the uncertainty of traffic distribution while evaluating some antenna parameters. We use a greedy algorithm with different variants to show how a frequency parameter setting can impact the coverage performance indicator based on the SINR metric. The well-known frequency reuse schemes 1x3x3, whereby the entire bandwidth is divided into 3 non-overlapping groups and assigned to 3 co-site sectors within each cell, have been used in our model. Further work must be done on algorithmic approach.
evocomplex
Testing Diversity-Enhancing Migration Policies for Hybrid On-line Evolution of Robot Controllers
Pablo García-Sánchez, A.E. Eiben, Evert Haasdijk, Berend Weel, Juan-J Merelo-Guervós
We investigate on-line on-board evolution of robot controllers based on the so-called hybrid approach (island-based). Inherently to this approach each robot hosts a population (island) of evolving controllers and exchanges controllers with other robots at certain times. We compare different exchange (migration) policies in order to optimize this evolutionary system and compare the best hybrid setup with the encapsulated and distributed alternatives. We conclude that adding a difference-based migrant selection scheme increases the performance.
Self-Organization and Specialization in Multiagent Systems through Open-ended Natural Evolution
Pedro Trueba, Abraham Prieto, Francisco Bellas, Pilar Caamaño, Richard J. Duro
This paper deals with the problem of autonomously organizing the behavior of a multiagent system through a distributed approach based on open-ended natural evolution. We computationally simulate life-like dynamics and their evolution from the definition of local and low level interactions, as used in Artificial Life simulations, in a distributed evolutionary algorithm called ASiCo (Asynchronous Situated Coevolution). In this algorithm, the agents that make up the population are situated in the environment and interact in an open-ended fashion, leading to emergent states or solutions. The aim of this paper is to ana-lyze the capabilities of ASiCo for obtaining specialization in the multiagent sys-tem if required by the task. Furthermore, we want to study such specialization under changing conditions to show the intrinsic self-organization of this type of algorithm. The particular task selected here is multi-robot collective gathering, due to the suitability of ASiCo for its application to real robotic systems.
evogames
On Modeling, Evaluating and Increasing Players’ Satisfaction Quantitatively: Steps towards a Taxonomy
Mariela Nogueira, Carlos Cotta, Antonio J. Fernández-Leiva
This paper shows the results of a review about modeling, evaluating and increasing players’ satisfaction in computer games. The paper starts discussing the main stages of development of quantitative solutions, and then it tries to propose a taxonomy that represents the most common trends. In the first part of this paper we take as base some approaches that were already described in the literature for quantitatively capturing and increasing the real-time entertainment value in computer games. In a second part we analyze the stage in which the game’s environment is adapted in response to player needs, and the main trends on this theme are discussed.
Spicing up Map Generation
Tobias Mahlmann, Julian Togelius, Georgios N. Yannakakis
We describe a search-based map generator for the classic real-time strategy game Dune 2. The generator is capable of creating playable maps in seconds, which can be used with a partial recreation of Dune 2 that has been implemented using the Strategy Game Description Language. Map genotypes are represented as low-resolution matrices, which are then converted to higher-resolution maps through a stochastic process involving cellular automata. Map phenotypes are evaluated using a set of heuristics based on the gameplay requirements of Dune 2.
evonum
Applying (Hybrid) Metaheuristics to Fuel Consumption Optimization of Hybrid Electric Vehicles
Thorsten Krenek, Mario Ruthmair, Günther Raidl, Michael Planer
This work deals with the application of metaheuristics to the fuel consumption minimization problem of hybrid electric vehicles (HEV) considering exactly specified driving cycles. A genetic algorithm, a downhill-simplex method and an algorithm based on swarm intelligence are used to find appropriate parameter values aiming at fuel consumption minimization. Finally, the individual metaheuristics are combined to a hybrid optimization algorithm taking into account the strengths and weaknesses of the single procedures. Due to the required time-consuming simulations it is crucial to keep the number of candidate solutions to be evaluated low. This is partly achieved by starting the heuristic search with already meaningful solutions identified by a Monte-Carlo procedure. Experimental results indicate that the implemented hybrid algorithm achieves better results than previously existing optimization methods on a simplified HEV model.
evopar
Migration and Replacement Policies for Preserving Diversity in Dynamic Environments
David Millán-Ruiz, José Ignacio Hidalgo
This paper seeks to resolve the difficulties arising from the configuration and fine-tuning of a Parallel Genetic Algorithm (PGA) based on the Island Model, when the application domain is highly dynamic. This way, the reader will find a number of useful guidelines for setting up a PGA in a real, representative dynamic environment. To achieve this purpose, we examine different (existing and new) migration and replacement policies for three different topologies. Of course, there are many other factors that affect the performance of a PGA such as the topology, migrant selection, migration frequency, amount of migrants, replacement policy, number of processing nodes, synchronism type, configuration in the isolated islands, diversity of policies in different islands, etc which are also considered as a part of this study. The pivotal point of all the experiments conducted is the preservation of diversity by means of an appropriate balance between exploration and exploitation in the PGA’s search process when the application domain is highly dynamic and strong time constraints arise. The experimental phase is performed over two problem instances from a real-world dynamic environment which is the multi-skill call centre.
Distributed Simulated Annealing with MapReduce
Atanas Radenski
Simulated annealing’s high computational intensity has stimulated researchers to experiment with various parallel and distributed simulated annealing algorithms for shared memory, message-passing, and hybrid-parallel platforms. MapReduce is an emerging distributed computing framework for large-scale data processing on clusters of commodity servers; to our knowledge, MapReduce has not been used for simulated annealing yet. In this paper, we investigate the applicability of MapReduce to distributed simulated annealing in general, and to the TSP in particular. We (i) design six algorithmic patterns of distributed simulated annealing with MapReduce, (ii) instantiate the patterns into MR implementations to solve a sample TSP problem, and (iii) evaluate the solution quality and the speedup of the implementations on a cloud computing platform, Amazon’s Elastic MapReduce. Some of our patterns integrate simulated annealing with genetic algorithms. The paper can be beneficial for those interested in the potential of MapReduce in computationally intensive nature-inspired methods in general and simulated annealing in particular.
Pool-based Distributed Evolutionary Algorithms using an Object Database
Juan-J Merelo-Guervós, Antonio Mora, J. Albert Cruz, Anna I Esparcia
This work presents the mapping of an evolutionary algorithm to the CouchDB object store. This mapping decouples the population from the evolutionary algorithm, and allows a distributed and asynchronous operation of clients written in different languages. In this paper we present initial tests which prove that the novel algorithm design still performs as an evolutionary algorithm and try to find out what are the main issues concerning it, what kind of speedups should we expect, and how all this affects the fundamentals of the evolutionary algorithm.
A Library to Run Evolutionary Algorithms in the Cloud using MapReduce
Pedro Fazenda, James McDermott, Una-May O’Reilly
We discuss ongoing development of an evolutionary algorithm library to run on the cloud. We relate how we have used the Hadoop open-source MapReduce distributed data processing framework to implement a single “island” with a potentially very large population. The design generalizes beyond the current, one-off kind of MapReduce implementations. It is in preparation for the library becoming a modeling or optimization service in a service oriented architecture or a development tool for designing new evolutionary algorithms.
evorisk
Customized Normalcy Profiles for the Detection of Targeted Attacks
Victor Skormin, Tomas Nykodym, Andrey Dolgikh, James Antonakos
Functionality is the highest semantic level of the software behavior pyramid that reflects goals of the software rather than its specific implementation. Detection of malicious functionalities presents an effective way to detect malware in behavior-based IDS. A technology for mining system call data, discussed herein, results in the detection of functionalities representing operation of legitimate software within a closed network environment. The set of such functionalities combined with the frequencies of their execution constitutes a normalcy profile typical for this environment. Detection of deviations from this normalcy profile, new functionalities and/or changes in the execution frequencies, provides evidence of abnormal activity in the network caused by malware. This approach could be especially valuable for the detection of targeted zero-day attacks. The paper presents the results of the implementation and testing of the described technology on the computer network testbed.
Parallel 5 (14:30 – 16:10)
evoiasp (room 5)
Evolutionary Regression Machines for Precision Agriculture (best paper nominee)
Heikki Salo, Ville Tirronen, Ferrante Neri
This paper proposes an image processing/machine learning system for estimating the amount of biomass in a field. This piece of information is precious in agriculture as it would allow a controlled adjustment of water and fertilizer. This system consists of a flying robot device which captures multiple images of the area under interest. Subsequently, this set of images is processed by means of a combined action of digital elevation models and multispectral images in order to reconstruct a three-dimensional model of the area. This model is then processed by a machine learning device, i.e. a support vector regressor with multiple kernel functions, for estimating the biomass present in the area. The training of the system has been performed by means of three modern meta-heuristics representing the state-of-the-art in computational intelligence optimization. These three algorithms are based on differential evolution, particle swarm optimization, and evolution strategy frameworks, respectively. Numerical Results derived by empirical simulations show that the proposed approach can be of a great support in precision agriculture. In addition, the most promising results have been attained by means of an algorithm based on the differential evolution framework.
Electrocardiographic Signal Classification with Evolutionary Artificial Neural Networks
Antonia Azzini, Mauro Dragoni, Andrea G.B. Tettamanzi
This work presents an evolutionary ANN classifier system as an heart beat classification algorithm suitable for implementation on the PhysioNet/Computing in Cardiology Challenge 2011, whose aim is to develop an efficient algorithm able to run within a mobile phone, that can provide useful feedback in the process of acquiring a diagnostically useful 12-lead Electrocardiography (ECG) recording. The method used in such a problem is to apply a very powerful natural computing analysis tool, namely evolutionary neural networks, based on the joint evolution of the topology and the connection weights together with a novel similarity-based crossover. The work focuses on discerning between usable and unusable electrocardiograms tele-medically acquired from mobile embedded devices. A prepropcessing algorithm based on the Discrete Fourier Trasform has been applied before the evolutionary approach in order to extract the ECG feature dataset in the frequency domain. Finally, a series of tests has been carried out in order to evaluate the performance and the accuracy of the classifier system for such a challenge.
Evolving Visual Attention Programs through EVO Features
León Dozal, Gustavo Olague, Eddie Clemente, Marco Sánchez
Brain informatics (BI) is a field of interdisciplinary study covering topics such as attention, memory, language, computation, learning and creativity, just to say a few. The BI is responsible for studying the mechanisms of human information processing. The dorsal stream, or “where”stream, is intimately related to the processing of visual attention. This paper proposes to evolve VAPs that learn to attend a given object within a scene. Visual attention is usually divided in two stages: feature acquisition and feature integration. In both phases there are specialized operators in the acquisition of a specific feature, called EV Os, and on the fusion of these features, called EFI. In previous research, those referred operators were established without considering the goal to be achieved. Instead of using established operators the idea is to learn and optimize them for the visual attention task. During the experiments we used a standard database of images for visual attention. The results provided in this paper show that our approach achieves impressive performance in the problem of focus visual attention over complex objects in challenging real world images on the first try.
Evolutionary Purposive or Behavioral Vision: The Link between Perception and Action
Daniel Hernández, Gustavo Olague, Eddie Clemente, León Dozal
Active, animate, purposive or behavioral vision are all understood as a research area where a seeing system interacts with the world in such a way of creating a balance between perception and action. In particular, it is said that a selective perception process in combination with a specific motion-action works as a unique complex system that accomplishes a visuomotor task. In the present work, this is understood as a visual behavior. This work describes a real-working system composed of a camera mounted on a robotic manipulator that is used as a research platform for evolving a visual routine specially designed in the estimation of specific motion-actions. The idea is to evolve an interest point detector with the goal of simplifying a well-known simultaneous localization and map building system. Experimental results shows as a proof-of-concept that the proposed system is able to design a specific interest point detector for the case of a straight-line displacement with the advantage of eliminating a number of heuristics.
Parallel 6 (16:30 – 18:10)
evoiasp (room 5)
Object Recognition with an Optimized Visual Cortex Model using Genetic Programming (best paper nominee)
Eddie Clemente, Gustavo Olague, León Dozal, Martín Mancilla
Computational neuroscience is a discipline devoted to the study of brain function from an information processing standpoint. The ventral stream, also known as the “what” pathway, is widely accepted as the model for processing the visual information related to object identification. This paper proposes to evolve a mathematical description of the ventral stream where key features are identified in order to simplify the whole information processing. The idea is to create an artificial ventral stream by evolving the structure through an evolutionary computing approach. In previous research, the “what” pathway is described as being composed of two main stages: the interest region detection and feature description. For both stages a set of operations were identified with the aim of simplifying the total computational cost by avoiding a number of costly operations that are normally executed in the template matching and bag of feature approaches. Therefore, instead of applying a set of previously learned patches, product of an off-line training process, the idea is to enforce a functional approach. Experiments were carried out with a standard database and the results show that instead of 1200 operations, the new model needs about 200 operations.
A Genetic Fuzzy Rules Learning Approach for Unseeded Segmentation in Echography (best paper nominee)
Leonardo Bocchi, Francesco Rogai
Clinical practice in echotomography often requires effective and time-efficient procedures for segmenting anatomical structures to take medical decisions for therapy and diagnosis. In this work we present a methodology for image segmentation in echography with the aim to assist the clinician in these delicate tasks. A generic segmentation algorithm, based on region evaluation by means of a fuzzy rules based inference system (FRBS), is refined in a fully unseeded segmentation algorithm. Rules composing knowledge base are learned with a genetic algorithm, by comparing computed segmentation with human expert segmentation. Generalization capabilities of the approach are assessed with a larger test set and over different applications: breast lesions, ovarian follicles and anesthetic detection during brachial anesthesia.
On Evolutionary Approaches to Unsupervised Nearest Neighbor Regression
Oliver Kramer
The detection of structures in high-dimensional data has an important part to play in machine learning. Recently, we proposed a fast iterative strategy for non-linear dimensionality reduction based on the unsupervised formulation of K-nearest neighbor regression. As the unsupervised nearest neighbor (UNN) optimization problem does not allow the computation of derivatives, the employment of direct search methods is reasonable. In this paper we introduce evolutionary optimization approaches for learning UNN embeddings. Two continuous variants are based on the CMA-ES employing regularization with domain restriction, and penalizing extension in latent space. A combinatorial variant is based on embedding the latent variables on a grid, and performing stochastic swaps. We compare the results on artificial dimensionality reduction problems.
Friday 13th April<
Parallel 7 (09:30 – 11:10)
evostoc (room 2)
Ant Colony Optimization with Immigrants Schemes for the Dynamic Vehicle Routing Problem
Michalis Mavrovouniotis, Shengxiang Yang
Ant colony optimization (ACO) algorithms have proved to be able to adapt to dynamic optimization problems (DOPs) when they are enhanced to maintain diversity and transfer knowledge. Several approaches have been integrated with ACO to improve its performance for DOPs. Among these integrations, the ACO algorithm with immigrants schemes has shown good results on the dynamic travelling salesman problem. In this paper, we investigate ACO algorithms to solve a more realistic DOP, the dynamic vehicle routing problem (DVRP) with traffic factors. Random immigrants and elitism-based immigrants are applied to ACO algorithms, which are then investigated on different DVRP test cases. The results show that the proposed ACO algorithms achieve promising results, especially when elitism-based immigrants are used.
Virtual Loser Genetic Algorithm for Dynamic Environments
Anabela Simões, Ernesto Costa
Memory-based Evolutionary Algorithms in Dynamic Optimization Problems (DOPs) store the best solutions in order to reuse them in future situations. The memorization of the best solutions can be direct (the best individual of the current population is stored) or associative (additional information from the current population is also stored). This paper explores a different type of associative memory to use in Evolutionary Algorithms for DOPs. The memory stores the current best individual and a vector of inhibitions that reflect past errors performed during the evolutionary process. When a change is detected in the environment the best solution is retrieved from memory and the vector of inhibitions associated to this individual is used to create new solutions avoiding the repetition of past errors. This algorithm is called Virtual Loser Genetic Algorithm and was tested in different dynamic environments created using the XOR DOP generator. The results show that the proposed memory scheme significantly enhances the Evolutionary Algorithms in cyclic dynamic environments.
Evolving Communication in Robotic Swarms using On-line, On-board, Distributed Evolutionary Algorithms
Luis E. Pineda, A.E. Eiben, Marteen van Steen
Robotic swarms offer flexibility, robustness, and scalability. For successful operation they need appropriate communication strategies that should be dynamically adaptable to possibly changing environmental requirements. In this paper we try to achieve this through evolving communication on-the-fly. As a test case we use a scenario where robots need to cooperate to gather energy and the necessity to cooperate is scalable. We implement an evolutionary algorithm that works during the actual operation of the robots (on-line), where evolutionary operators are performed by the robots themselves (on-board) and robots exchange genomes with other robots for reproduction (distributed). We perform experiments with different cooperation pressures and observe that communication strategies can be successfully adapted to the particular demands of the environment.
evonum (room 4)
Towards a Deeper Understanding of Trade-offs using Multi-objective Evolutionary Algorithms
Pradyumn Kumar Shukla, Christian Hirsch, Hartmut Schmeck
A multi-objective optimization problem is characterized by multiple and conflicting objective functions. The conflicting nature of the objectives gives rise to the notion of trade-offs. A trade-off represents the ratio of change in the objective function values, when one of the objective function values increases and the value of some other objective function decreases. Various notions of trade-offs have been present in the classical multiple criteria decision making community and many scalarization approaches have been proposed in the literature to find a solution satisfying some given trade-off requirements. Almost all of these approaches are point-by-point algorithms. On the other hand, multi-objective evolutionary algorithms work with a population and, if properly designed, are able to find the complete preferred subset of the Pareto-optimal set satisfying a priori given bound on trade-offs. In this paper, we analyze and put together various notions of trade-offs that we find in the classical literature, classifying them into two groups. We then go on to propose multi-objective evolutionary algorithms to find solutions belonging to the two classified groups. This is done by modifying a state-of-the-art evolutionary algorithm NSGA-II. An extensive computational study substantiates the claims of the paper.
A Generic Approach to Parameter Control
Giorgos Karafotias, S.K. Smit, A.E. Eiben
On-line control of EA parameters is an approach to parameter setting that offers the advantage of values changing during the run. In this paper, we investigate parameter control from a generic and parameter-independent perspective. We propose a generic control mechanism that is targeted to repetitive applications, can be applied to any numeric parameter and is tailored to specific types of problems through an off-line calibration process. We present proof-of-concept experiments using this mechanism to control the mutation step size of an Evolutionary Strategy (ES). Results show that our method is viable and performs very well, compared to the tuning approach and traditional control methods.
Improved Topological Niching for Real-Valued Global Optimization
Mike Preuss
We show how nearest-better clustering, the core component of the NBC-CMA niching evolutionary algorithm, is improved by appyling a second heuristic rule. This leads to enhanced basin identification for higher dimensional (5D to 20D) optimization problems, where the NBC-CMA has previously shown only mediocre performance compared to other niching and global optimization algorithms. The new method is integrated into a niching algorithm (NEA2) and compared to NBC-CMA and BIPOP-CMA-ES via the BBOB benchmarking suite. It performs very well on problems that enable recognizing basins at all with reasonable effort (number of basins not too high, e.g. the Gallagher problems), as expected. Beyond that point, niching is obviously not applicable any more and random restarts as done by the CMA-ES are the method of choice.
evohot (room 4)
Robot Base Disturbance Optimization with Compact Differential Evolution Light
Giovanni Iacca, Fabio Caraffini, Ferrante Neri, Ernesto Mininno
Despite the constant growth of the computational power in consumer electronics, very simple hardware is still used in space applications. In order to obtain the highest possible reliability, in space systems limited-power but fully tested and certified hardware is used, thus reducing fault risks. Some space applications require the solution of an optimization problem, often plagued by real-time and memory constraints. In this paper, the disturbance to the base of a robotic arm mounted on a spacecraft is modeled, and it is used as a cost function for an online trajectory optimization process. In order to tackle this problem in a computationally efficient manner, addressing not only the memory saving necessities but also real-time requirements, we propose a novel compact algorithm, namely compact Differential Evolution light (cDElight). cDElight belongs to the class of Estimation of Distribution Algorithms (EDAs), which mimic the behavior of population-based algorithms by means of a probabilistic model of the population of candidate solutions. This model has a more limited memory footprint than the actual population. Compared to a selected set of memory-saving algorithms, cDElight is able to obtain the best results, despite a lower computational overhead.
evocomnet (room 5)
Evolutionary Design of Active Free Space Optical Networks Based on Digital Mirror Devices
Steffen Limmer, Dietmar Fey, Ulrich Lohmann, Jürgen Jahns
Optical connections have several advantages compared to conventional electrical connections, especially a higher attainable bandwidth. While long distance optical connections are already established, optical board- and chip-level connections are still a subject of current research. In this paper we describe a new setup for optical board-level connections which is based on free space optics and allows the switching of signals within the optical domain. We describe the evolutionary optimization of design parameters for the proposed setup, done with a memetic evolutionary algorithm and present the optimization results.
Optimizing Energy Consumption in Heterogeneous Wireless Sensor Networks by Means of Evolutionary Algorithms
José Manuel Lanza-Gutiérrez, Juan Antonio Gómez-Pulido, Miguel A. Vega-Rodríguez, Juan Manuel Sánchez-Pérez
The use of wireless sensor networks has been increased substantially. One of the main inconveniences of this kind of networks is the energy efficiency; for this reason, there are some works trying to solve it. Traditionally, these networks were only composed by sensors, but now auxiliary elements called routers have been included to facilitate communications and reduce energy consumption. In this work, we have studied the inclusion of routers in a previously established traditional wireless sensor network in order to increase its energy efficiency, optimizing lifetime and average energy effort. For this purpose, we have used two multi-objective evolutionary algorithms: NSGA-II and SPEA-2. We have done experiments over various sceneries, checking by means of statically techniques that SPEA-2 offers better results for more complex instances.
Protocol Discovery and Analysis via Live Interaction
Patrick LaRoche, A. Nur Zincir-Heywood, Malcolm I. Heywood
In this work, we explore the use of evolutionary computing toward protocol analysis. The ability to discover, analyse, and experiment with unknown protocols is paramount within the realm of network security; our approach to this crucial analysis is to interact with a network service, discovering sequences of commands that do not result in error messages. In so doing, our work investigates the real-life responses of a service, allowing for exploration and analysis of the protocol in question. Our system initiates sequences of commands randomly, interacts with and learns from the responses, and modifies its next set of sequences accordingly. Such an exploration results in a set of command sequences that reflect correct uses of the service in testing. These discovered sequences can then be used to identify the service, unforeseen uses of the service, and, most importantly, potential weaknesses.