Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the International Conference on the Applications of Evolutionary Computation, EvoApplications 2013, held in Vienna, Austria, in April 2013, colocated with the Evo* 2013 events EuroGP, EvoCOP, EvoBIO, and EvoMUSART. The 65 revised full papers presented were carefully reviewed and selected from 119 submissions. EvoApplications 2013 consisted of the following 12 tracks: EvoCOMNET (nature-inspired techniques for telecommunication networks and other parallel and distributed systems), EvoCOMPLEX (evolutionary algorithms and complex systems), EvoENERGY (evolutionary computation in energy applications), EvoFIN (evolutionary and natural computation in finance and economics), EvoGAMES (bio-inspired algorithms in games), EvoIASP (evolutionary computation in image analysis, signal processing, and pattern recognition), EvoINDUSTRY (nature-inspired techniques in industrial settings), EvoNUM (bio-inspired algorithms for continuous parameter optimization), EvoPAR (parallel implementation of evolutionary algorithms), EvoRISK (computational intelligence for risk management, security and defence applications), EvoROBOT (evolutionary computation in robotics), and EvoSTOC (evolutionary algorithms in stochastic and dynamic environments).

Inhaltsverzeichnis

Frontmatter

EvoCOMNET

An Evolutionary Framework for Routing Protocol Analysis in Wireless Sensor Networks

Wireless Sensor Networks (WSNs) are widely adopted for applications ranging from surveillance to environmental monitoring. While powerful and relatively inexpensive, they are subject to behavioural faults which make them unreliable. Due to the complex interactions between network nodes, it is difficult to uncover faults in a WSN by resorting to formal techniques for verification and analysis, or to testing. This paper proposes an evolutionary framework to detect anomalous behaviour related to energy consumption in WSN routing protocols. Given a collection protocol, the framework creates candidate topologies and evaluates them through simulation on the basis of metrics measuring the radio activity on nodes. Experimental results using the standard Collection Tree Protocol show that the proposed approach is able to unveil topologies plagued by excessive energy depletion over one or more nodes, and thus could be used as an offline debugging tool to understand and correct the issues before network deployment and during the development of new protocols.

Doina Bucur, Giovanni Iacca, Giovanni Squillero, Alberto Tonda

Routing Low-Speed Traffic Requests onto High-Speed Lightpaths by Using a Multiobjective Firefly Algorithm

Nowadays, the bandwidth requirements of the majority of traffic connection requests are in the range of Mbps. However, in optical networks each physical link is able to operate in the range of Gbps causing a huge waste of bandwidth as a result. Fortunately, using access station at each node of the optical network, several low-speed traffic requests may be multiplexed onto one high-speed channel. Multiplexing or grooming these low-speed requests is known in the literature as the Traffic Grooming problem - an NP-hard problem. Therefore, in this paper we propose the use of Evolutionary Computation for solving this telecommunication problem. The selected algorithm is an approach inspired by the flash pattern and characteristics of fireflies, the Firefly Algorithm (FA), but adapted to the multiobjective domain (MO-FA). After performing several experiments and comparing the results obtained by the MO-FA with those obtained by other approaches published in the literature, we can conclude that it is a good approach for solving this problem.

Álvaro Rubio-Largo, Miguel A. Vega-Rodríguez

Pareto-optimal Glowworm Swarms Optimization for Smart Grids Management

This paper presents a novel nature-inspired multi-objective optimization algorithm. The method extends the glowworm swarm particles optimization algorithm with algorithmical enhancements which allow to identify optimal pareto front in the objectives space. In addition, the system allows to specify constraining functions which are needed in practical applications. The framework has been applied to the power dispatch problem of distribution systems including Distributed Energy Resources (DER). Results for the test cases are reported and discussed elucidating both numerical and complexity analysis.

Eleonora Riva Sanseverino, Maria Luisa Di Silvestre, Roberto Gallea

An Overlay Approach for Optimising Small-World Properties in VANETs

Advantages of bringing small-world properties in mobile ad hoc networks (MANETs) in terms of quality of service has been studied and outlined in the past years. In this work, we focus on the specific class of vehicular ad hoc networks (VANETs) and propose to un-partition such networks and improve their small-world properties. To this end, a subset of nodes, called injection points, is chosen to provide backend connectivity and compose a fully-connected overlay network. The optimisation problem we consider is to find the minimal set of injection points to constitute the overlay that will optimise the small-world properties of the resulting network, i.e., (1) maximising the clustering coefficient (CC) so that it approaches the CC of a corresponding regular graph and (2) minimising the difference between the average path length (APL) of the considered graph and the APL of corresponding random graphs. In order to face this new multi-objective optimisation problem, the NSGAII algorithm was used on realistic instances in the city-centre of Luxembourg. The accurate tradeoff solutions found by NSGAII (assuming global knowledge of the network) will permit to better know and understand the problem. This will later ease the design of decentralised solutions to be used in real environments, as well as their future validation.

Julien Schleich, Grégoire Danoy, Bernabé Dorronsoro, Pascal Bouvry

Impact of the Number of Beacons in PSO-Based Auto-localization in UWB Networks

In this paper, we focus on auto-localization of nodes in a static wireless network, under the assumption of known position of a few initial nodes, denoted as “beacons”. Assuming that Ultra Wide Band (UWB) signals are used for inter-node communications, we analyze the impact of the number of beacons on the location accuracy. Three different approaches to localization are considered, namely: the Two-Stage Maximum-Likelihood (TSML) method ; the Plane Intersection (PI) method, and Particle Swarming Optimization (PSO). Simulation results show that PSO allows to obtain accurate postion estimates with a small number of beacons, making it an attractive choice to implement effective localization algorithm.

Stefania Monica, Gianluigi Ferrari

Load Balancing in Distributed Applications Based on Extremal Optimization

The paper shows how to use Extremal Optimization in load balancing of distributed applications executed in clusters of multicore processors interconnected by a message passing network. Composed of iterative optimization phases which improve program task placement on processors, the proposed load balancing method discovers dynamically the candidates for migration with the use of an Extremal Optimization algorithm and a special quality model which takes into account the computation and communication parameters of the constituent parallel tasks. Assessed by experiments with simulated load balancing of distributed program graphs, a comparison of the proposed Extremal Optimization approach against a deterministic approach based on a similar load balancing theoretical model is provided.

Ivanoe De Falco, Eryk Laskowski, Richard Olejnik, Umberto Scafuri, Ernesto Tarantino, Marek Tudruj

A Framework for Modeling Automatic Offloading of Mobile Applications Using Genetic Programming

The limited battery life of the modern mobile devices is one of the key problems limiting their usage. The offloading of computation on cloud computing platforms can considerably extend the battery duration. However, it is really hard not only to evaluate the cases in which the offloading guarantees real advantages on the basis of the requirements of application in terms of data transfer, computing power needed, etc., but also to evaluate if user requirements (i.e. the costs of using the clouds, a determined QoS required, etc.) are satisfied. To this aim, in this work it is presented a framework for generating models for taking automatic decisions on the offloading of mobile applications using a genetic programming (GP) approach. The GP system is designed using a taxonomy of the properties useful to the offloading process concerning the user, the network, the data and the application. Finally, the fitness function adopted permits to give different weights to the four categories considered during the process of building the model.

Gianluigi Folino, Francesco Sergio Pisani

Solving the Location Areas Scheme in Realistic Networks by Using a Multi-objective Algorithm

The optimization of the management tasks in current mobile networks is an interesting research field due to the exponential increase in the number of mobile subscribers. In this paper, we study two of the most important management tasks of the Public Land Mobile Networks: the location update and the paging, since these two procedures are used by the mobile network to locate and track the Mobile Stations. There are several strategies to manage the location update and the paging, but we focus on the Location Areas scheme with a two-cycle sequential paging, a strategy widely applied in current mobile networks. This scheme can be formulated as a multi-objective optimization problem with two objective functions: minimize the number of location updates and minimize the number of paging messages. In previous works, this multi-objective problem was solved with single-objective optimization algorithms by means of the linear aggregation of the objective functions. In order to avoid the drawbacks related to the linear aggregation, we propose an adaptation of the Non-dominated Sorting Genetic Algorithm II to solve the Location Areas Planning Problem. Furthermore, with the aim of studying a realistic mobile network, we apply our algorithm to a scenario located in the San Francisco Bay (USA). Results show that our algorithm outperforms the algorithms proposed by other authors, as well as the advantages of a multi-objective approach.

Víctor Berrocal-Plaza, Miguel A. Vega-Rodríguez, Juan M. Sánchez-Pérez, Juan A. Gómez-Pulido

EvoCOMPLEX

The Small-World Phenomenon Applied to a Self-adaptive Resources Selection Model

Small-world property is found in a wide range of natural, biological, social or transport networks. The main idea of this phenomenon is that seemingly distant nodes actually have very short path lengths due to the presence of a small number of shortcut edges running between clusters of nodes. In the present work, we apply this principle for solving the resources selection problem in grid computing environments (distributed systems composed by heterogeneous and geographically dispersed resources). The proposed model expects to find the most efficient resources for a particular grid application in a short number of steps. It also provides a self-adaptive ability for dealing with environmental changes. Finally, this selection model is tested in a real grid infrastructure. From the results obtained it is concluded that both a reduction in execution time and an increase in the successfully completed tasks rate are achieved.

María Botón-Fernández, Francisco Prieto Castrillo, Miguel A. Vega-Rodríguez

Partial Imitation Hinders Emergence of Cooperation in the Iterated Prisoner’s Dilemma with Direct Reciprocity

The evolutionary time scales for various strategies in the iterated Prisoner’s Dilemma on a fully connected network are investigated for players with finite memory, using two different kinds of imitation rules: the (commonly used) traditional imitation rule where the entire meta-strategy of the role model is copied, and the partial imitation rule where only the observed subset of moves is copied. If the players can memorize the last round of the game, a sufficiently large random initial population eventually reaches a cooperative equilibrium, even in an environment with bounded rationality (noise) and high temptation. With the traditional imitation rule the time scale to cooperation increases linearly with decreasing intensity of selection (or increasing noise) in the weak selection regime, whereas partial imitation results in an exponential dependence. Populations with finite lifetimes are therefore unlikely to ever reach a cooperative state in this setting. Instead, numerical experiments show the emergence and long persistence of a phase characterized by the dominance of always defecting strategies.

Mathis Antony, Degang Wu, K. Y. Szeto

A Memetic Approach to Bayesian Network Structure Learning

Bayesian networks are graphical statistical models that represent inference between data. For their effectiveness and versatility, they are widely adopted to represent knowledge in different domains. Several research lines address the NP-hard problem of Bayesian network structure learning starting from data: over the years, the machine learning community delivered effective heuristics, while different Evolutionary Algorithms have been devised to tackle this complex problem. This paper presents a Memetic Algorithm for Bayesian network structure learning, that combines the exploratory power of an Evolutionary Algorithm with the speed of local search. Experimental results show that the proposed approach is able to outperform state-of-the-art heuristics on two well-studied benchmarks.

Alberto Tonda, Evelyne Lutton, Giovanni Squillero, Pierre-Henri Wuillemin

Multiobjective Evolutionary Strategy for Finding Neighbourhoods of Pareto-optimal Solutions

In some cases of Multiobjective Optimization problems finding Pareto optimal solutions does not give enough knowledge about the shape of the landscape, especially with multimodal problems and non-connected Pareto fronts. In this paper we present a strategy which combines a hierarchic genetic algorithm consisting of multiple populations with rank selection. This strategy aims at finding neighbourhoods of solutions by recognizing regions with high density of individuals. We compare two variants of the presented strategy on a benchmark two-criteria minimization problem.

Ewa Gajda-Zagórska

Genetic Programming-Based Model Output Statistics for Short-Range Temperature Prediction

This paper introduces GP (Genetic Programming) based robust compensation technique for temperature prediction in short-range. MOS (Model Output Statistics) is a statistical technique that corrects the systematic errors of the model. Development of an efficient MOS is very important, but most of MOS are based on the idea of relating model forecasts to observations through a linear regression. Therefore it is hard to manage complex and irregular natures of the prediction. In order to solve the problem, a nonlinear and symbolic regression method using GP is suggested as the first attempt. The purpose of this study is to evaluate the accuracy of the estimation by GP based nonlinear MOS for the 3 days temperatures for Korean regions. This method is then compared to the UM model and shows superior results. The training period of summer in 2007-2009 is used, and the data of 2010 summer is adopted for verification.

Kisung Seo, Byeongyong Hyeon, Soohwan Hyun, Younghee Lee

Evolutionary Multi-Agent System in Hard Benchmark Continuous Optimisation

It turns out that hybridizing agent-based paradigm with evolutionary computation brings a new quality to the field of meta-heuristics, enhancing individuals with possibilities of perception, interaction with other individuals (agents), adaptation of parameters, etc. In the paper such technique—an evolutionary multi-agent system (EMAS)—is compared with a classical evolutionary algorithm (Michalewicz model) implemented with allopatric speciation (island model). Both algorithms are applied to the problem of continuous optimisation in selected benchmark problems. The results are very promising, as agent-based computing turns out to be more effective than classical one, especially in difficult benchmark problems, such as high-dimensional Rastrigin function.

Sebastian Pisarski, Adam Rugała, Aleksander Byrski, Marek Kisiel-Dorohinicki

EvoENERGY

Domestic Load Scheduling Using Genetic Algorithms

An approach using a genetic algorithm to optimize the scheduling of domestic electric loads, according to technical and user-defined constraints and input signals, is presented and illustrative results are shown. The aim is minimizing the end-user’s electricity bill according to his/her preferences, while accounting for the quality of the energy services provided. The constraints include the contracted power level, end-users’ preferences concerning the admissible and/or preferable time periods for operation of each load, and the amount of available usable power in each period of time to account for variations in the (non-manageable) base load. The load scheduling is done for the next 36 hours assuming that a dynamic pricing structure is known in advance. The results obtained present a noticeable decrease of the electricity bill when compared to a reference case in which there is no automated scheduling.

Ana Soares, Állvaro Gomes, Carlos Henggeler Antunes, Hugo Cardoso

Evolutionary Algorithm Based Control Policies for Flexible Optimal Power Flow over Time

General optimal power flow (OPF) is an important problem in the operation of electric power grids. Solution methods to the OPF have been studied extensively that mainly solve steady-state situations, ignoring uncertainties of state variables as well as their near-future. Thus, in a dynamic and uncertain power system, where the demand as well as the supply-side show volatile behavior, optimization methods are needed that provide solutions very quickly, eliminating issues on convergence speed or robustness of the optimization. This paper introduces a policy-based approach where optimal control policies are learned offline for a given power grid based on evolutionary computation, that later provide quick and accurate control actions in volatile situations. With such an approach, it’s no more necessary to solve the OPF in each new situation by applying a certain optimization procedure, but the policies provide (near-) optimal actions very quickly, satisfying all constraints in a reliable and robust way. Thus, a method is available for flexible and optimized power grid operation over time. This will be essential for meeting the claims for the future of smart grids.

Stephan Hutterer, Michael Affenzeller, Franz Auinger

Using a Genetic Algorithm for the Determination of Power Load Profiles

Electrical distribution companies struggle to find precise estimations of energy demand for their networks. They have at their disposal statistical tools such as power load profiles, which are however usually not precise enough and do not take into account factors such as the presence of electrical heating devices or the type of housing of the end users. In this paper, we show how a genetic algorithm generated with the EASEA language can be successfully applied to solve a noisy blind source separation problem and create accurate power load profiles using real world data provided by “Électricité de Strasbourg Réseaux”. The data includes load measurements of 20kV feeders as well as the energy consumption of more than 400,000 end users. The power load profiles obtained demonstrate considerable improvement in the estimation of load curves of 20kV feeders.

Frédéric Krüger, Daniel Wagner, Pierre Collet

Comparing Ensemble-Based Forecasting Methods for Smart-Metering Data

This work provides a preliminary study on applying state-of-the-art time-series forecasting methods to electrical energy consumption data recorded by smart metering equipment. We compare a custom-build commercial baseline method to modern ensemble-based methods from statistical time-series analysis and to a modern commercial GP system. Our preliminary results indicate that that modern ensemble-based methods, as well as GP, are an attractive alternative to custom-built approaches for electrical energy consumption forecasting.

Oliver Flasch, Martina Friese, Katya Vladislavleva, Thomas Bartz-Beielstein, Olaf Mersmann, Boris Naujoks, Jörg Stork, Martin Zaefferer

Evolving Non-Intrusive Load Monitoring

Non-intrusive load monitoring (NILM) identifies used appliances in a total power load according to their individual load characteristics. In this paper we propose an evolutionary optimization algorithm to identify appliances, which are modeled as on/off appliances. We evaluate our proposed evolutionary optimization by simulation with Matlab, where we use a random total load and randomly generated power profiles to make a statement of the applicability of the evolutionary algorithm as optimization technique for NILM. Our results shows that the evolutionary approach is feasible to be used in NILM systems and can reach satisfying detection probabilities.

Dominik Egarter, Anita Sobe, Wilfried Elmenreich

EvoFIN

On the Utility of Trading Criteria Based Retraining in Forex Markets

This research investigates the ability of genetic programming (GP) to build profitable trading strategies for the Foreign Exchange Market (FX) of three major currency pairs (EURUSD, USDCHF and EURCHF) using one hour prices from 2008 to 2011. We recognize that such environments are likely to be non-stationary. Thus, we do not require a single training partition to capture all likely future behaviours. We address this by detecting poor trading behaviours and use this to trigger retraining. In addition the task of evolving good technical indicators (TI) and the rules for deploying trading actions is explicitly separated. Thus, separate GP populations are used to coevolve TI and trading behaviours under a mutualistic symbiotic association. The results of 100 simulations demonstrate that an adaptive retraining algorithm significantly outperforms a single-strategy approach (population evolved once) and generates profitable solutions with a high probability.

Alexander Loginov, Malcolm I. Heywood

Identifying Market Price Levels Using Differential Evolution

Evolutionary data mining is used in this paper to investigate the concept of support and resistance levels in financial markets. Specifically, Differential Evolution is used to learn support/resistance levels from price data. The presence of these levels is then tested in out-of-sample data. Our results from a set of experiments covering five years worth of daily data across nine different US markets show that there is statistical evidence for price levels in certain markets, and that Differential Evolution can uncover them.

Michael Mayo

Evolving Hierarchical Temporal Memory-Based Trading Models

We explore the possibility of using the genetic algorithm to optimize trading models based on the Hierarchical Temporal Memory (HTM) machine learning technology. Technical indicators, derived from intraday tick data for the E-mini S&P 500 futures market (ES), were used as feature vectors to the HTM models. All models were configured as binary classifiers, using a simple buy-and-hold trading strategy, and followed a supervised training scheme. The data set was partitioned into multiple folds to enable a modified cross validation scheme. Artificial Neural Networks (ANNs) were used to benchmark HTM performance. The results show that the genetic algorithm succeeded in finding predictive models with good performance and generalization ability. The HTM models outperformed the neural network models on the chosen data set and both technologies yielded profitable results with above average accuracy.

Patrick Gabrielsson, Rikard König, Ulf Johansson

Robust Estimation of Vector Autoregression (VAR) Models Using Genetic Algorithms

In this paper we present an implementation of a Vector autoregression (VAR) estimation model using Genetic Algorithms. The algorithm was implemented in R and compared to standard estimation models using least squares. A numerical example is presented to outline advantages of the GA approach.

Ronald Hochreiter, Gerald Krottendorfer

Usage Patterns of Trading Rules in Stock Market Trading Strategies Optimized with Evolutionary Methods

This paper proposes an approach to analysis of usage patterns of trading rules in stock market trading strategies. Analyzed strategies generate trading decisions based on signals produced by trading rules. Weighted sets of trading rules are used with parameters optimized using evolutionary algorithms. A novel approach to trading rule pattern discovery, inspired by association rule mining methods, is proposed. In the experiments, patterns consisting of up to 5 trading rules were discovered which appear in no less than 50% of trading experts optimized by evolutonary algorithm.

Krzysztof Michalak, Patryk Filipiak, Piotr Lipinski

Combining Technical Analysis and Grammatical Evolution in a Trading System

Trading Systems are beneficial for financial investments due to the complexity of nowadays markets. On one hand, finance markets are influenced by a great amount of factors of different sources such as government policies, natural disasters, international trade, political factors etc. On the other hand, traders, brokers or practitioners in general could be affected by human emotions, so their behaviour in the stock market becomes nonobjective. The high pressure induced by handling a large volume of money is the main reason of the so-called market psychology. Trading systems are able to avoid a great amount of these factors, allowing investors to abstract the complex flow of information and the emotions related to the investments. In this paper we compare two trading systems based on Evolutionary Computation. The first is a GA-based one and was already proposed and tested with data from 2006. The second one is a grammatical evolution approach which uses a new evaluation method. Experimental results show that the later outperforms the GA approach with a set of selected companies of the spanish market with 2012 data.

Iván Contreras, J. Ignacio Hidalgo, Laura Núñez-Letamendia

EvoGAMES

A Card Game Description Language

We present initial research regarding a system capable of generating novel card games. We furthermore propose a method for computationally analysing existing games of the same genre. Ultimately, we present a formalisation of card game rules, and a context-free grammar

G

cardgame

capable of expressing the rules of a large variety of card games. Example derivations are given for the poker variant

Texas hold ’em

, Blackjack and UNO. Stochastic simulations are used both to verify the implementation of these well-known games, and to evaluate the results of new game rules derived from the grammar. In future work, this grammar will be used to evolve completely novel card games using a grammar-guided genetic program.

Jose M. Font, Tobias Mahlmann, Daniel Manrique, Julian Togelius

Generating Map Sketches for Strategy Games

How can a human and an algorithm productively collaborate on generating game content? In this paper, we try to answer this question in the context of generating balanced and interesting low-resolution sketches for game levels. We introduce six important criteria for successful strategy game maps, and present map sketches optimized for one or more of these criteria via a constrained evolutionary algorithm. The sketch-based map representation and the computationally lightweight evaluation methods are geared towards the integration of the evolutionary algorithm within a mixed-initiative tool, allowing for the co-creation of game content by a human and an artificial designer.

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

A Procedural Balanced Map Generator with Self-adaptive Complexity for the Real-Time Strategy Game Planet Wars

Procedural content generation (PCG) is the programmatic generation of game content using a random or pseudo-random process that results in an unpredictable range of possible gameplay spaces. This methodology brings many advantages to game developers, such as reduced memory consumption. This works presents a procedural balanced map generator for a real-time strategy game:

Planet Wars

. This generator uses an evolutionary strategy for generating and evolving maps and a tournament system for evaluating the quality of these maps in terms of their balance. We have run several experiments obtaining a set of playable and balanced maps.

Raúl Lara-Cabrera, Carlos Cotta, Antonio J. Fernández-Leiva

Mechanic Miner: Reflection-Driven Game Mechanic Discovery and Level Design

We introduce Mechanic Miner, an evolutionary system for discovering simple two-state game mechanics for puzzle platform games. We demonstrate how a reflection-driven generation technique can use a simulation of gameplay to select good mechanics, and how the simulation-driven process can be inverted to produce challenging levels specific to a generated mechanic. We give examples of levels and mechanics generated by the system, summarise a small pilot study conducted with example levels and mechanics, and point to further applications of the technique, including applications to automated game design.

Michael Cook, Simon Colton, Azalea Raad, Jeremy Gow

Generating Artificial Neural Networks for Value Function Approximation in a Domain Requiring a Shifting Strategy

Artificial neural networks have been successfully used as approximating value functions for tasks involving decision making. In domains where a shift in judgment for decisions is necessary as the overall state changes, it is hypothesized that multiple neural networks are likely be beneficial as an approximation of a value function over those that employ a single network. For our experiments, the card game Dominion was chosen as the domain. This work compares neural networks generated by various machine learning methods successfully applied to other games (such as in TD-Gammon) to a genetic algorithm method for generating two neural networks for different phases of the game along with evolving a transition point. The results demonstrate a greater success ratio with the method hypothesized. This suggests future work examining more complex multiple neural network configurations could apply to this game domain as well as being applicable to other problems.

Ransom K. Winder

Comparing Evolutionary Algorithms to Solve the Game of MasterMind

In this paper we propose a novel evolutionary approach to solve the Mastermind game, and compare the results obtained with that of existing algorithms. The new evolutionary approach consists of a hierarchical one involving two different evolutionary algorithms, one for searching the set of eligible codes, and the second one to choose the best code to be played at a given stage of the game. The comparison with existing algorithms provides interesting conclusions regarding the performance of the algorithms and how to improve it in the future. However, it is clear that Entropy is a better scoring strategy than Most Parts, at least for these sizes, being able to obtain better results, independently of the evolutionary algorithm.

Javier Maestro-Montojo, Juan Julián Merelo, Sancho Salcedo-Sanz

EvoIASP

A Genetic Algorithm for Color Image Segmentation

A genetic algorithm for color image segmentation is proposed. The method represents an image as a weighted undirected graph, where nodes correspond to pixels, and edges connect similar pixels. Similarity between two pixels is computed by taking into account not only brightness, but also color and texture content. Experiments on images from the Berkeley Image Segmentation Dataset show that the method is able to partition natural and human scenes in a number of regions consistent with human visual perception. A quantitative evaluation of the method compared with other approaches shows that the genetic algorithm can be very competitive in partitioning color images.

Alessia Amelio, Clara Pizzuti

Multiobjective Projection Pursuit for Semisupervised Feature Extraction

The current paper presents a framework for linear feature extraction applicable in both unsupervised and supervised data analysis, as well as in their hybrid - the semi-supervised scenario. New features are extracted in a filter manner with a multi-modal genetic algorithm that optimizes simultaneously several projection indices. Experimental results show that the new algorithm is able to provide a compact and improved representation of the data set. The use of mixed labeled and unlabeled data under this scenario improves considerably the performance of constrained clustering algorithms such as constrained k-Means.

Mihaela Elena Breaban

Land Cover/Land Use Multiclass Classification Using GP with Geometric Semantic Operators

Multiclass classification is a common requirement of many land cover/land use applications, one of the pillars of land science studies. Even though genetic programming has been applied with success to a large number of applications, it is not particularly suited for multiclass classification, thus limiting its use on such studies. In this paper we take a step forward towards filling this gap, investigating the performance of recently defined geometric semantic operators on two land cover/land use multiclass classification problems and also on a benchmark problem. Our results clearly indicate that genetic programming using the new geometric semantic operators outperforms standard genetic programming for all the studied problems, both on training and test data.

Mauro Castelli, Sara Silva, Leonardo Vanneschi, Ana Cabral, Maria J. Vasconcelos, Luís Catarino, João M. B. Carreiras

Adding Chaos to Differential Evolution for Range Image Registration

This paper presents a method for automatically pair–wise registering range images. Registration is effected adding chaos to a Differential Evolution technique and by applying the Grid Closest Point algorithm to find the best possible transformation of the second image causing 3D reconstruction of the original object. Experimental results show the capability of the method in picking up efficient transformations of images with respect to the classical Differential Evolution. The proposed method offers a good solution to build complete 3D models of objects from 3D scan datasets.

Ivanoe De Falco, Antonio Della Cioppa, Domenico Maisto, Umberto Scafuri, Ernesto Tarantino

Genetic Programming for Automatic Construction of Variant Features in Edge Detection

Basic features for edge detection, such as derivatives, can be further manipulated to improve detection performance. However, how to effectively combine different basic features remains an open issue and needs to be investigated. In this study, Genetic Programming (GP) is used to automatically and effectively construct rotation variant features based on basic features from derivatives,

F

-test, and histograms of images. To reduce computational cost in the training stage, the basic features only use the horizontal responses to construct new horizontal features. These new features are then combined with their own rotated versions in the vertical direction in the testing stage. The experimental results show that the rotation variant features constructed by GP combine advantages from the basic features, reduce drawbacks from basic features alone, and improve the detection performance.

Wenlong Fu, Mark Johnston, Mengjie Zhang

Automatic Construction of Gaussian-Based Edge Detectors Using Genetic Programming

Gaussian-based edge detectors have been developed for many years, but there are still problems with how to set scales for Gaussian filters and how to combine Gaussian filters. In order to address both problems, a Genetic Programming (GP) system is proposed to automatically choose scales for Gaussian filters and automatically combine Gaussian filters. In this study, the GP system is utilised to construct rotation invariant Gaussian-based edge detectors based on a benchmark image dataset. The experimental results show that the GP evolved Gaussian-based edge detectors are better than the Gaussian gradient and rotation invariant surround suppression to extract edge features.

Wenlong Fu, Mark Johnston, Mengjie Zhang

Implicit Fitness Sharing for Evolutionary Synthesis of License Plate Detectors

A genetic programming algorithm for synthesis of object detection systems is proposed and applied to the task of license plate recognition in uncontrolled lighting conditions. The method evolves solutions represented as data flows of high-level parametric image operators. In an extended variant, the algorithm employs implicit fitness sharing, which allows identifying the particularly difficult training examples and focusing the training process on them. The experiment, involving heterogeneous video sequences acquired in diverse conditions, demonstrates that implicit fitness sharing substantially improves the predictive performance of evolved detection systems, providing maximum recognition accuracy achievable for the considered setup and training data.

Krzysztof Krawiec, Mateusz Nawrocki

Feedback-Based Image Retrieval Using Probabilistic Hypergraph Ranking Augmented by Ant Colony Algorithm

One fundamental issue in image retrieval is its lack of ability to take advantage of relationships among images and relevance feedback information. In this paper, we propose a novel feedback-based image retrieval technique using probabilistic hypergraph ranking augmented by ant colony algorithm, which aims at enhancing affinity between the related images by incorporating both semantic pheromone and low-level feature similarities. It can effectively integrate the high-order information of hypergraph and the feedback mechanism of ant colony algorithm. Extensive performance evaluations on two public datasets show that our new method significantly outperforms the traditional probabilistic hypergraph ranking on image retrieval tasks.

Ling-Yan Pan, Yu-Bin Yang

An Evolutionary Approach for Automatic Seedpoint Setting in Brain Fiber Tracking

In this paper we present an evolutionary approach for optimising the seedpoint setting in brain fiber tracking. Our aim is to use Diffusion Tensor Imaging (DTI) data and Diffusion Magnetic Resonance Imaging (dMRI) data for feeding an automatic fiber tracking approach. Our work focusses on customising an evolutionary algorithm to find nerve fibers within diffusion data and allocate an appropriate number of seedpoints to them. This is necessary for the subsequent fiber reconstruction algorithms to work. The algorithm considerably enhances the speed and quality of the reconstruction and proves to be promising in leading to an automatic fiber tracking procedure used in medical imaging.

Tobias Pilic, Hendrik Richter

Prediction of Forest Aboveground Biomass: An Exercise on Avoiding Overfitting

Mapping and understanding the spatial distribution of forest aboveground biomass (AGB) is an important and challenging task. This paper describes an exercise of predicting the forest AGB of Guinea-Bissau, West Africa, using synthetic aperture radar data and measurements of tree size collected in field campaigns. Several methods were attempted, from linear regression to different variants and techniques of Genetic Programming (GP), including the cutting edge geometric semantic GP approach. The results were compared between each other in terms of root mean square error and correlation between predicted and expected values of AGB. None of the methods was able to produce a model that generalizes well to unseen data or significantly outperforms the model obtained by the state-of-the-art methodology, and the latter was also not better than a simple linear model. We conclude that the AGB prediction is a difficult problem, aggravated by the small size of the available data set.

Sara Silva, Vijay Ingalalli, Susana Vinga, João M. B. Carreiras, Joana B. Melo, Mauro Castelli, Leonardo Vanneschi, Ivo Gonçalves, José Caldas

Human Action Recognition from Multi-Sensor Stream Data by Genetic Programming

This paper presents an approach to recognition of human actions such as sitting, standing, walking or running by analysing the data produced by the sensors of a smart phone. The data comes as streams of parallel time series from 21 sensors. We have used genetic programming to evolve detectors for a number of actions and compared the detection accuracy of the evolved detectors with detectors built from the classical machine learning methods including Decision Trees, Naïve Bayes, Nearest Neighbour and Support Vector Machines. The evolved detectors were considerably more accurate. We conclude that the proposed GP method can capture complex interaction of variables in parallel time series without using predefined features.

Feng Xie, Andy Song, Vic Ciesielski

Novel Initialisation and Updating Mechanisms in PSO for Feature Selection in Classification

In classification, feature selection is an important, but difficult problem. Particle swarm optimisation (PSO) is an efficient evolutionary computation technique. However, the traditional personal best and global best updating mechanism in PSO limits its performance for feature selection and the potential of PSO for feature selection has not been fully investigated. This paper proposes a new initialisation strategy and a new personal best and global best updating mechanism in PSO to develop a novel feature selection algorithm with the goals of minimising the number of features, maximising the classification performance and simultaneously reducing the computational time. The proposed algorithm is compared with two traditional feature selection methods, a PSO based method with the goal of only maximising the classification performance, and a PSO based two-stage algorithm considering both the number of features and the classification performance. Experiments on eight benchmark datasets show that the proposed algorithm can automatically evolve a feature subset with a smaller number of features and higher classification performance than using all features. The proposed algorithm achieves significantly better classification performance than the two traditional methods. The proposed algorithm also outperforms the two PSO based feature selection algorithms in terms of the classification performance, the number of features and the computational cost.

Bing Xue, Mengjie Zhang, Will N. Browne

EvoINDUSTRY

CodeMonkey; a GUI Driven Platform for Swift Synthesis of Evolutionary Algorithms in Java

CodeMonkey is a GUI driven software development platform that allows non-experts and experts alike to turn an evolutionary algorithm design into a working Java program, with a minimal amount of manual code entry. This paper describes the concepts behind CodeMonkey, its internal architecture and manner of use. It concludes with a simple application that exhibits its utilization for multi-dimensional function optimization. CodeMonkey is provided free of charge, for non-commercial users, as a plug-in for the Eclipse platform.

Reza Etemadi, Nawwaf Kharma, Peter Grogono

Multi-Objective Optimizations of Structural Parameter Determination for Serpentine Channel Heat Sink

This paper presents an approach for modeling and optimization of the channel geometry of a serpentine channel heat sink using multi-objective genetic algorithm. A simple thermal resistance network model was developed to investigate the overall thermal performance of the serpentine channel heat sink. Based on a number of simulations, bend loss coefficient correlation for 1000<Re<2200 was obtained which was function of the aspect ratio (

a

), ratio of fins width to channel width (

b

). In this study, two objectives minimization of overall thermal resistance and pressure drop are carried out using multi-objective genetic algorithms. The channel width, fin width, channel height and inlet velocity are variables to be optimized subject to constraints of fixed length and width of heat sink. The study indicates that reduction in both thermal resistance and pressure drop can be achieved by optimizing the channel configuration and the inlet velocity.

Xuekang Li, Xiaohong Hao, Yi Chen, Muhao Zhang, Bei Peng

EvoNUM

Towards Non-linear Constraint Estimation for Expensive Optimization

Constraints can render a numerical optimization problem much more difficult to address. In many real-world optimization applications, however, such constraints are not explicitly given. Instead, one has access to some kind of a “black-box” that represents the (unknown) constraint function. Recently, we proposed a fast linear constraint estimator that was based on binary search. This paper extends these results by (a) providing an alternative scheme that resorts to the effective use of support vector machines and by (b) addressing the more general task of non-linear decision boundaries. In particular, we make use of active learning strategies from the field of machine learning to select reasonable training points for the recurrent application of the classifier. We compare both constraint estimation schemes on linear and non-linear constraint functions, and depict opportunities and pitfalls concerning the effective integration of such models into a global optimization process.

Fabian Gieseke, Oliver Kramer

Repair Methods for Box Constraints Revisited

Box constraints are possibly the simplest kind of constraints one could think of in real-valued optimization, because it is trivial to detect and repair any violation of them. But so far, the topic has only received marginal attention in the literature compared to the more general formulations, although it is a frequent use case. It is experimentally shown here that different repair methods can have a huge impact on the optimizer’s performance when using the covariance matrix self-adaptation evolution strategy (CMSA-ES). Also, two novel repair methods, specially designed for this algorithm, sometimes outperform the traditional ones.

Simon Wessing

Scalability of Population-Based Search Heuristics for Many-Objective Optimization

Beginning with Talagrand [16]’s seminal work, isoperimetric inequalities have been used extensively in analysing randomized algorithms. We develop similar inequalities and apply them to analysing population-based randomized search heuristics for multiobjective optimization in ℝ

n

space. We demonstrate the utility of the framework in explaining an empirical observation so far not explained analytically: the curse of dimensionality, for many-objective problems. The framework makes use of the black-box model now popular in EC research.

Ramprasad Joshi, Bharat Deshpande

EvoPAR

On GPU Based Fitness Evaluation with Decoupled Training Partition Cardinality

GPU acceleration of increasingly complex variants of evolutionary frameworks typically assume that all the training data used during evolution resides on the GPU. Such an assumption places limits on the style of application to which evolutionary computation can be applied. Conversely, several coevolutionary frameworks explicitly decouple fitness evaluation from the size of the training partition. Thus, a subset of training exemplars is coevolved with the population of evolved individuals. In this work we articulate the design decisions necessary to support Pareto archiving for Genetic Programming under a commodity GPU platform. Benchmarking of corresponding CPU and GPU implementations demonstrates that the GPU platform is still capable of providing a times ten reduction in computation time.

Jazz Alyxzander Turner-Baggs, Malcolm I. Heywood

EvoSpace: A Distributed Evolutionary Platform Based on the Tuple Space Model

This paper presents EvoSpace, a Cloud service for the development of distributed evolutionary algorithms. EvoSpace is based on the tuple space model, an associatively addressed memory space shared by several processes. Remote clients, called EvoWorkers, connect to EvoSpace and periodically take a subset of individuals from the global population, perform evolutionary operations on them, and return a set of new individuals. Several EvoWorkers carry out the evolutionary search in parallel and asynchronously, interacting with each other through the central repository. EvoSpace is designed to be domain independent and flexible, in the sense that in can be used with different types of evolutionary algorithms and applications. In this paper, a genetic algorithm is tested on the EvoSpace platform using a well-known benchmark problem, achieving promising results compared to a standard evolutionary system.

Mario García-Valdez, Leonardo Trujillo, Francisco Fernández de Vega, Juan J. Merelo Guervós, Gustavo Olague

Cloud Driven Design of a Distributed Genetic Programming Platform

We describe how we design FlexGP, a distributed genetic programming (GP) system to efficiently run on the cloud. The system has a decentralized, fault-tolerant, cascading startup where nodes start to compute while more nodes are launched. It has a peer-to-peer neighbor discovery protocol which constructs a robust communication network across the nodes. Concurrent with neighbor discovery, each node launches a GP run differing in parameterization and training data from its neighbors. This factoring of parameters across learners produces many diverse models for use in ensemble learning.

Owen Derby, Kalyan Veeramachaneni, Una-May O’Reilly

Cloud Scale Distributed Evolutionary Strategies for High Dimensional Problems

We develop and evaluate a cloud scale distributed covariance matrix adaptation based evolutionary strategy for problems with dimensions as high as 400. We adopt an island based distribution model and rely on a peer-to-peer communication protocol. We identify a variety of parameters in a distributed island model that could be randomized leading to a new dynamic migration protocol that can prove advantageous when computing on the cloud. Our approach enables efficient and high quality distributed sampling while mitigating the latencies and failure risks associated with running on a cloud. We evaluate performance on a real world problem from the domain of wind energy: wind farm turbine layout optimization.

Dennis Wilson, Kalyan Veeramachaneni, Una-May O’Reilly

EvoRISK

Malicious Automatically Generated Domain Name Detection Using Stateful-SBB

This work investigates the detection of Botnet Command and Control (C&C) activity by monitoring Domain Name System (DNS) traffic. Detection signatures are automatically generated using evolutionary computation technique based on Stateful-SBB. The evaluation performed shows that the proposed system can work on raw variable length domain name strings with very high accuracy.

Fariba Haddadi, H. Gunes Kayacik, A. Nur Zincir-Heywood, Malcolm I. Heywood

EvoROBOT

Evolving Gaits for Physical Robots with the HyperNEAT Generative Encoding: The Benefits of Simulation

Creating gaits for physical robots is a longstanding and open challenge. Recently, the HyperNEAT generative encoding was shown to automatically discover a variety of gait regularities, producing fast, coordinated gaits, but only for simulated robots. A follow-up study found that HyperNEAT did not produce impressive gaits when they were evolved directly on a physical robot. A simpler encoding hand-tuned to produce regular gaits was tried on the same robot, and outperformed HyperNEAT, but these gaits were first evolved in simulation before being transferred to the robot. In this paper, we tested the hypothesis that the beneficial properties of HyperNEAT would outperform the simpler encoding if HyperNEAT gaits are first evolved in simulation before being transferred to reality. That hypothesis was confirmed, resulting in the fastest gaits yet observed for this robot, including those produced by nine different algorithms from three previous papers describing gaitgenerating techniques for this robot. This result is important because it confirms that the early promise shown by generative encodings, specifically HyperNEAT, are not limited to simulation, but work on challenging real-world engineering challenges such as evolving gaits for real robots.

Suchan Lee, Jason Yosinski, Kyrre Glette, Hod Lipson, Jeff Clune

Co-evolutionary Approach to Design of Robotic Gait

Manual design of motion patterns for legged robots is difficult task often with suboptimal results. To automate this process variety of approaches have been tried including various evolutionary algorithms. In this work we present an algorithm capable of generating viable motion patterns for multi-legged robots. This algorithm consists of two evolutionary algorithms working in co-evolution. The GP is evolving motion of a single leg while the GA deploys the motion to all legs of the robot. Proof-of-concept experiments show that the co-evolutionary approach delivers significantly better results than those evolved for the same robot with simple genetic programming algorithm alone.

Jan Černý, Jiří Kubalík

A Comparison between Different Encoding Strategies for Snake-Like Robot Controllers

In this paper, we present the results of the tests we have performed with different encoding strategies for evolving controllers for a snake-like robot. This study is aimed at finding the best encoding for on-line learning of basic skills, such as locomotion (both free and directed to an objective) and obstacle avoidance. The snake moves in a virtual world, which realistically simulates all the physical conditions of the real world. This is the first step of our research on on-line, embedded and open-ended evolution of robot controllers, where robots have to learn how to survive during their lifetime, and occasionally mate with other robots. A simple (1+1) evolutionary strategy has been adopted for lifetime learning. The results of the tests have shown that the best results, tested on the locomotion skills, is the ’He1Sig’ controller, that uses a different set of parameters for each segment of the snake but only one mutation rate, common to all parameters, that is encoded in the chromosome and therefore undergoes evolution itself.

Dámaso Pérez-Moneo Suárez, Claudio Rossi

MONEE: Using Parental Investment to Combine Open-Ended and Task-Driven Evolution

This paper is inspired by a vision of self-sufficient robot collectives that adapt autonomously to deal with their environment and to perform user-defined tasks at the same time. We introduce the

monee

algorithm as a method of combining open-ended (to deal with the environment) and task-driven (to satisfy user demands) adaptation of robot controllers through evolution. A number of experiments with simulated e-pucks serve as proof of concept and show that with

monee

, the robots adapt to cope with the environment and to perform multiple tasks. Our experiments indicate that

monee

distributes the tasks evenly over the robot collective without undue emphasis on easy tasks.

Nikita Noskov, Evert Haasdijk, Berend Weel, A. E. Eiben

Virtual Spatiality in Agent Controllers: Encoding Compartmentalization

Applying methods of artificial evolution to synthesize robot controllers for complex tasks is still a challenging endeavor. We report an approach which might have the potential to improve the performance of evolutionary algorithms in the context of evolutionary robotics. We apply a controller concept that is inspired by signaling networks found in nature. The implementation of spatial features is based on Voronoi diagrams that describe a compartmentalization of the agent’s inner body. These compartments establish a virtual embodiment, including sensors and actuators, and influence the dynamics of virtual hormones. We report results for an exploring task and an object discrimination task. These results indicate that the controller, that determines the principle hormone dynamics, can successfully be evolved in parallel with the compartmentalizations, that determine the spatial features of the sensors, actuators, and hormones.

Jürgen Stradner, Heiko Hamann, Christopher S. F. Schwarzer, Nico K. Michiels, Thomas Schmickl

Evolving Counter-Propagation Neuro-controllers for Multi-objective Robot Navigation

This study follows a recent investigation on evolutionary training of counter-propagation neural-networks for multi-objective robot navigation in various environments. Here, in contrast to the original study, the training of the counter-propagation networks is done using an improved two-phase algorithm to achieve tuned weights for both classification of inputs and the control function. The proposed improvement concerns the crossover operation among the networks, which requires special attention due to the classification layer. The numerical simulations, which are reported here, suggest that both the current and original algorithms are superior to the classical approach of using a feed-forward network. It is also observed that the current version has better convergence properties as compared with the original one.

Amiram Moshaiov, Michael Zadok

Toward Automatic Gait Generation for Quadruped Robots Using Cartesian Genetic Programming

This paper introduces a new gait generation method for quadruped robots using CGP (Cartesian Genetic Programming) based on refinement of regression polynomials for a joint trajectory. CGP uses as genotype a linear string of integers that are mapped to a directed graph. Therefore, some evolved modules for regression polynomials in CGP can be shared and reused among multiple outputs for joint trajectories. To investigate the effectiveness of the proposed approach, experiments on gaits were executed for a Bioloid quadruped robot in the Webots environment.

Kisung Seo, Soohwan Hyun

EvoSTOC

Adapting the Pheromone Evaporation Rate in Dynamic Routing Problems

Ant colony optimization (ACO) algorithms have proved to be able to adapt to dynamic optimization problems (DOPs) when stagnation behaviour is avoided. Several approaches have been integrated with ACO to improve its performance for DOPs. The adaptation capabilities of ACO rely on the pheromone evaporation mechanism, where the rate is usually fixed. Pheromone evaporation may eliminate pheromone trails that represent bad solutions from previous environments. In this paper, an adaptive scheme is proposed to vary the evaporation rate in different periods of the optimization process. The experimental results show that ACO with an adaptive pheromone evaporation rate achieves promising results, when compared with an ACO with a fixed pheromone evaporation rate, for different DOPs.

Michalis Mavrovouniotis, Shengxiang Yang

Finding Robust Solutions to Dynamic Optimization Problems

Most research in evolutionary dynamic optimization is based on the assumption that the primary goal in solving Dynamic Optimization Problems (DOPs) is Tracking Moving Optimum (TMO). Yet, TMO is impractical in cases where keeping changing solutions in use is impossible. To solve DOPs more practically, a new formulation of DOPs was proposed recently, which is referred to as Robust Optimization Over Time (ROOT). In ROOT, the aim is to find solutions whose fitnesses are robust to future environmental changes. In this paper, we point out the inappropriateness of existing robustness definitions used in ROOT, and therefore propose two improved versions, namely

survival time

and

average fitness

. Two corresponding metrics are also developed, based on which

survival time

and

average fitness

are optimized respectively using population-based algorithms. Experimental results on benchmark problems demonstrate the advantages of our metrics over existing ones on robustness definitions

survival time

and

average fitness

.

Haobo Fu, Bernhard Sendhoff, Ke Tang, Xin Yao

An Ant-Based Selection Hyper-heuristic for Dynamic Environments

Dynamic environment problems require adaptive solution methodologies which can deal with the changes in the environment during the solution process for a given problem. A selection hyper-heuristic manages a set of low level heuristics (operators) and decides which one to apply at each iterative step. Recent studies show that selection hyper-heuristic methodologies are indeed suitable for solving dynamic environment problems with their ability of tracking the change dynamics in a given environment. The choice function based selection hyper-heuristic is reported to be the best hyper-heuristic on a set of benchmark problems. In this study, we investigate the performance of a new learning hyper-heuristic and its variants which are inspired from the ant colony optimization algorithm components. The proposed hyper-heuristic maintains a matrix of pheromone intensities (utility values) between all pairs of low level heuristics. A heuristic is selected based on the utility values between the previously invoked heuristic and each heuristic from the set of low level heuristics. The ant-based hyper-heuristic performs better than the choice function and even its improved version across a variety of dynamic environments produced by the Moving Peaks Benchmark generator.

Berna Kiraz, A. Şima Etaner-Uyar, Ender Özcan

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise