Thursday 28 April 14:30-16:00, room 5: Eraclito, Session 1
Chair: Ernesto Tarantino
Investigation of Hyper-heuristics for Designing Survivable Virtual Topologies in Optical WDM Networks (Best Paper Nomination)
Fatma Corut Ergin, Aysegul Yayimli, A. Şima Uyar
In optical WDM networks, a fiber failure may result in a serious amount of data loss, hence, designing survivable virtual topologies is a critical problem. We propose four different hyper-heuristic approaches to solve this problem, each of which is based on a different category of nature inspired heuristics: evolutionary algorithms, ant colony optimization, simulated annealing, and adaptive iterated constructive search are used as the heuristic selection methods in the hyper-heuristics. Experimental results show that, all proposed hyper-heuristic approaches are successful in designing survivable virtual topologies. Furthermore, the ant colony optimization based hyper-heuristic outperforms the others.
On Improving the Capacity of Solving Large-scale Wireless Network Design Problems by Genetic Algorithms Fabio D’Andreagiovanni
Over the last decade, wireless networks have experienced an impressive growth and now play a main role in many telecommunications systems. As a consequence, scarce radio resources, such as frequencies, became congested and the need for effective and efficient assignment methods arose. In this work, we present a Genetic Algorithm for solving large instances of the Power, Frequency and Modulation Assignment Problem, arising in the design of wireless networks. To our best knowledge, this is the first Genetic Algorithm that is proposed for such problem. Compared to previous works, our approach allows a wider exploration of the set of power solutions, while eliminating sources of numerical problems. The performance of the algorithm is assessed by tests over a set of large realistic instances of a Fixed WiMAX Network.
Ant-Based Multipath Routing for Wireless Mesh Networks (Best Paper Nomination) Laurent Paquereau, Bjarne E. Helvik
Wireless Mesh Networks (WMNs) are envisioned as a flexible alternative for providing Internet access. In this context, one of the key challenges is to improve the capacity. One approach is to spread the load along multiple paths. Results achieved in wired networks using ant-based systems for this purpose make them attractive candidates. However, applying similar techniques directly to WMNs may be counter-productive due to the characteristics of multi-hop wireless communications, in particular interferences. In this paper, a novel hybrid approach, based on recording the Internet gateway used by ants and marking pheromone trails accordingly, is presented. Results are promising and indicate that adaptive and efficient load distribution can be achieved.
Thursday 28 April 16:20-17:50, room 5: Eraclito, Session 2
Chair: Ernesto Tarantino
A Multiobjective Hybrid Gravitational Search Algorithm for the Static Routing and Wavelength Assignment Problem Álvaro Rubio-Largo, Miguel Á. Vega-Rodríguez, Juan A. Gómez-Pulido, Juan M. Sánchez-Pérez
One of the most favorable technology for exploiting the huge bandwidth of optical networks is known as Wavelength Division Multiplexing (WDM). Given a set of demands, the problem of setting up all connection requests is known as Routing and Wavelength Assignment (RWA) problem. In this work, we suggest the use of computational swarm intelligent for solving the RWA problem. A new heuristic based on the law of gravity and mass interactions (Gravitational Search Algorithm, GSA) is chosen for this purpose, but adapted to a multiobjective context (MO-GSA). To test the performance of the MO-GSA, we have used a real-world topology, the Nippon Telegraph and Telephone (NTT, Japan) network and six sets of demands. After performing several comparisons with other approaches published in the literature, we can conclude that this algorithm outperforms the results obtained by other authors.
Dynamic Routing Exponent Strategies for Ant-based Protocols (Best Paper Nomination) Rui Fang, Zequn Huang, Louis Rossi, Chien-Chung Shen
In ant-based routing protocols, the routing exponent controls how ants hop from node to node to discover routes based on pheromone values. It has been shown that stable multi-route solutions for small routing exponent values are dynamically connected to stable single-route solutions for large routing exponent values. These stable single-route solutions correspond to paths that have the smallest hop count. In this paper, we leverage this idea to improve the performance of ant-based routing protocols by dynamically adjusting the routing exponent. The results are validated via simulation.
A Population Based Incremental Learning for Delay Constrained Network Coding Resource Minimization Huanlai Xing, Rong Qu
In network coding based multicast, coding operations are expected to be minimized as they not only incur additional computational cost at corresponding nodes in network but also increase data transmission delay. On the other hand, delay constraint must be concerned particularly in delay sensitive applications, e.g. video conferencing. In this paper, we study the problem of minimizing the amount of coding operations required while meeting the end-to-end delay constraint in network coding based multicast. A population based incremental learning (PBIL) algorithm is developed, where a group of best so far individuals, rather than a single one, is maintained and used to update the probability vector, which enhances the global search capability of the algorithm. Simulation results demonstrate the effectiveness of our PBIL.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
Extremal Optimization Applied to Task Scheduling of Distributed Java Programs Eryk Laskowski, Marek Tudruj, Ivanoe De Falco, Umberto Scafuri, Ernesto Tarantino, Richard Olejnik
The paper presents new Java programs scheduling algorithms for execution on clusters of Java Virtual Machines (JVMs), which involve extremal optimization (EO) combined with task clustering. Two new scheduling algorithms are presented and compared. The first employs task clustering to reduce an initial program graph and then applies extremal optimization to schedule the reduced program graph to system resources. The second algorithm applies task clustering only to find an initial solution which is next improved by the EO algorithm working on the initial program graph. Both algorithms are also compared to an EO algorithm which does not use the clustering approach.
Data-Centered Scheduling for Addressing Performance Metrics on WSN Lia Susana d.C. Silva-Lopez, Jonatan Gomez Perdomo
In this paper, a novel combination of cross-layer strategies for addressing timeliness, handle latency times on a data-centred way, and improve energy management in a non-mobile WSN scenario, is proposed. A set of performance metrics is also introduced. The metrics evaluate timeliness, latencies and energy management, and are used to compare the strategies with a combination of Periodic Scheduling and Simplified Forwarding. The WSN is modelled as an Asynchronous Cellular Automata with irregular neighbourhoods, and four states. Only information from local neighbourhood is needed for communication. Results show that the strategies are useful for sensing data accurately, without excessive oversampling. [index]
Thursday 28 April 11:30-13:00, room 5: Eraclito, Session 1
Chair: Carlos Cotta
Evolving L-Systems as an intelligent design approach to find classes of difficult-to-solve Traveling Salesman Problem instances Farhan Ahammed, Pablo Moscato
The technique of computationally analysing a program by searching for instances which causes the program to run in its worst-case time is examined. Concorde, the state-of-the-art Traveling Salesperson Problem (TSP) solver, is the program used to test our approach. We seed our evolutionary approach with a fractal instance of the TSP, defined by a Lindenmayer system at a fixed order. The evolutionary algorithm produced modifications to the L-System rules such that the instances of the modified L-System become increasingly much harder for Concorde to solve to optimality. In some cases, while still having the same size, the evolved instances required a computation time which was 30,000 times greater than what was needed to solve the original instance that seeded the search. The success of this case study shows the potential of Evolutionary Search to provide new test-case scenarios for algorithms and their software implementations.
On the design of Boolean network robots Andrea Roli, Mattia Manfroni, Carlo Pinciroli, Mauro Birattari
Dynamical systems theory and complexity science provide powerful tools for analysing artificial agents and robots. Furthermore, they have been recently proposed also as a source of design principles and guidelines. Boolean networks are a prominent example of complex dynamical systems and they have been shown to effectively capture important phenomena in gene regulation. From an engineering perspective, these models are very compelling, because they can exhibit rich and complex behaviours, in spite of the compactness of their description. In this paper, we propose the use of Boolean networks for controlling robots’ behaviour. The network is designed by means of an automatic procedure based on stochastic local search techniques. We show that this approach makes it possible to design a network which enables the robot to accomplish a task that requires the capability of navigating the space using a light stimulus, as well as the formation and use of an internal memory.
A Study on the Mutation Rates of a Genetic Algorithm Interacting with a Sandpile Carlos Fernandes, Juan Laredo, Antonio Mora, Agostinho Rosa, Juan Merelo
This paper investigates the mutation rates of a Genetic Algorithm (GA) with the sandpile mutation. This operator, which was specifically designed for non-stationary (or dynamic) optimization problems, relies on a Self-Organized Criticality system called sandpile to self-adapt the mutation intensity during the run. The behaviour of the operator depends on the state of the sandpile and on the fitness values of the population. Therefore, it has been argued that the mutation distribution may depend on to the severity and frequency of changes and on the type of stationary function that is chosen as a base-function for the dynamic problems. An experimental setup is proposed for investigating these issues. The results show that, at least under the proposed framework, a GA with the sandpile mutation self-adapts the mutation rates to the dynamics of the problem and to the characteristics of the base-function.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
A Design Framework for Ultra-Large-Scale Autonomic Systems Michele Amoretti
The origins of ultra-large-scale (ULS) systems derive from social problems that are getting more and more complex, such as climatic monitoring, transportation, citizens protection and security. These factors imply a continuous increase of information systems that evolve towards ultra-dimension systems, requiring digital communication networks that allow for communication between people, between objects, and objects and people. The aim of this paper is to present novel approaches for the engineering of highly adaptive ULS systems, with the focus on computer-supported evolution, adaptable structure, emergent behaviors as well as advanced monitoring and control techniques. We illustrate the Networked Autonomic Machine (NAM), a framework for the characterization of the elements of self-*, highly dynamic ULS systems. Moreover, we recall the Adaptive Evolutionary Framework (AEF), for the implementation of distributed evolutionary strategies. Finally, we describe an example scenario of large peer-to-peer network under targeted attacks, showing the benefits of the NAM-AEF design.
Stochastic Local Search to Automatically Design Boolean Networks with Maximally Distant Attractors Stefano Benedettini, Andrea Roli, Roberto Serra, Marco Villani
In this work we address the issue of designing a Boolean network such that its attractors are maximally distant. The design objective is converted into an optimisation problem, that is solved via an iterated local search algorithm. This technique proves to be effective and enables us to design networks with size up to 200 nodes. We also show that the networks obtained through the optimisation technique exhibit a mixture of characteristics typical of networks in the critical and chaotic dynamical regime.
Thursday 28 April 14:30-16:00, room 4: Mendel, Session 1
Chair: Anthony Brabazon
Learning and Predicting Financial Time Series by Combining Natural Computation and Agent Simulation Filippo Neri
We investigate how, by combining natural computation and agent based simulation, it is possible to model financial time series. The agent based simulation can be used to functionally reproduce the structure of a financial market while the natural computation technique finds the most suitable parameter for the simulator. Our experimentation on the DJIA time series shows the effectiveness of this approach in modeling financial data. Also we compare the predictions made by our system to those obtained by other approaches.
Macro-Economic Time Series Modeling and Interaction Networks Gabriel Kronberger, Stefan Fink, Michael Kommenda, Michael Affenzeller
Macro-economic models describe the dynamics of economic quantities. The estimations and forecasts produced by such models play a substantial role for financial and political decisions. In this contribution we describe an approach based on genetic programming and symbolic regression to identify variable interactions in large datasets. In the proposed approach multiple symbolic regression runs are executed for each variable of the dataset to find potentially interesting models. The result is a variable interaction network that describes which variables are most relevant for the approximation of each variable of the dataset. This approach is applied to a macro-economic dataset with monthly observations of important economic indicators in order to identify potentially interesting dependencies of these indicators. The resulting interaction network of macro-economic indicators is briefly discussed and two of the identified models are presented in detail. The two models approximate the help wanted index and the CPI inflation in the US.
Market Microstructure: Can Dinosaurs Return? A Self-Organizing Map Approach under an Evolutionary Framework Michael Kampouridis, Shu-Heng Chen, Edward Tsang
This paper extends a previous market microstructure model, which investigated fraction dynamics of trading strategies. Our model consisted of two parts: Genetic Programming, which acted as an inference engine for trading rules, and Self-Organizing Maps (SOM), which was used for clustering the above rules into trading strategy types. However, for the purposes of the experiments of our previous work, we needed to make the assumption that SOM maps, and thus strategy types, remained the same over time. Nevertheless, this assumption could be considered as strict, and even unrealistic. In this paper, we relax this assumption. This offers a significant extension to our model, because it makes it more realistic. In addition, this extension allows us to investigate the dynamics of market behavior. We are interested in examining whether financial markets’ behavior is non-stationary, because this implies that strategies from the past cannot be applied to future time periods, unless they have co-evolved with the market. The results on an empirical financial market show that its behavior constantly changes; thus, agents’ strategies need to continuously adapt to the changes taking place in the market, in order to remain effective.
Thursday 28 April 16:20-17:50, room 4: Mendel, Session 2
Chair: Andrea Tettamanzi
A Preliminary Investigation of Overfitting in Evolutionary Driven Model Induction: Implications for Financial Modelling Clíodhna Tuite, Alexandros Agapitos, Michael O’Neill, Anthony Brabazon
This paper investigates the effects of early stopping as a method to counteract overfitting in evolutionary data modelling using Genetic Programming. Early stopping has been proposed as a method to avoid model overtraining, which has been shown to lead to a significant degradation of out-of-sample performance. If we assume some sort of performance metric maximisation, the most widely used early training stopping criterion is the moment within the learning process that an unbiased estimate of the performance of the model begins to decrease after a strictly monotonic increase through the earlier learning iterations. We are conducting an initial investigation on the effects of early stopping in the performance of Genetic Programming in symbolic regression and financial modelling. Empirical results suggest that early stopping using the above criterion increases the extrapolation abilities of symbolic regression models, but is by no means the optimal training-stopping criterion in the case of a real-world financial dataset.
Using Evolutionary Neural Networks to Test the Influence of the Choice of Numeraire on Financial Time Series Modeling Antonia Azzini, Mauro Dragoni, Andrea G.B. Tettamanzi
This work presents an evolutionary solution that aims to test the influence of the choice of numeraire on financial time series modeling. In particular, 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, to a couple of very liquid financial time series expressed in their trading currency and several alternative numeraires like gold, silver, and a currency like the euro, which is intended to be stable `by design’, and compare the results.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
On the Performance and Convergence Properties of Hybrid Intelligent Schemes:Application on Portfolio Optimization Domain Vassilios Vassiliadis, Nikolaos Thomaidis, George Dounias
Hybrid intelligent algorithms, especially those who combine nature-inspired techniques, are well known for their searching abilities in complex problem domains and their performance. One of their main characteristic is that they manage to escape getting trapped in local optima. In this study, two hybrid intelligent schemes are compared both in terms of performance and convergence ability in a complex financial problem. Particularly, both algorithms use a type of genetic algorithm for asset selection and they differ on the technique applied for weight optimization: the first hybrid uses a numerical function optimization method, while the second one uses a continuous ant colony optimization algorithm. Results indicate that there is great potential in combining characteristics of nature-inspired algorithms in order to solve NP-hard optimization problems.
Wednesday 27 April 11:30-13:00, room 4: Mendel, Board Games
Chair: Mike Preuss
Improving and Scaling Evolutionary Approaches to the MasterMind Problem Juan-Julian Merelo, Carlos Cotta, Antonio-M. Mora
Mastermind is a well-known board game in which one player must discover a hidden combination of colored pegs set up by an opponent, using the hints that the latter provides (the number of places –or pegs– correctly guessed, and the number of colors rightly guessed but out of place) in each move. The feasibility of evolutionary approaches to solve this problem has been already proved; in this paper we will assess different methods to improve the time it takes to find a solution by introducing endgames, that is, shortcuts for finding the solution when certain circumstances arise. Besides, we will measure the scalability of the evolutionary approaches by solving generalized Mastermind instances in several sizes. Tests show that endgames improve the average number of solutions without any influence on the quality of the game; at the same time, it speeds up solutions so that bigger problems can be approached. Tests performed with eight colors and four or five pegs and nine colors with five pegs show that scaling is quite good, and that the methodology yields an average number of games that is competitive with the best solutions published so far. Scaling with problem size depends on the method, being better for entropy-based solutions, but –besides raw problem size– there are complex dependencies on the number of pegs and colors.
Nested Look-Ahead Evolutionary Algorithm Based Planning for a Believable Diplomacy Bot Markus Kemmerling, Niels Ackermann, Mike Preuss
With regard to literature, improved estimations for the number of possible moves and placements are provided, showing that the complexity of Diplomacy is enormous, making it a good candidate for machine learning and evolutionary learning techniques. To enhance the playing strength of an existing Diplomacy bot and alleviate the distance to the presumed best current bot, a look-ahead planning component based on nested evolutionary algorithms, is then implanted into an already existing bot. The experimental investigation shows that the resulting bot is significantly improved.
Wednesday 27 April 14:30-16:00, room 4: Mendel, Game Applications
Chair: Julian Togelius
Evolving Interesting Maps for a First Person Shooter Luigi Cardamone, Georgios N. Yannakakis, Julian Togelius, Pier Luca Lanzi
We address the problem of automatically designing maps for first-person shooter (FPS) games. An efficient solution to this procedural content generation (PCG) problem could allow the design of FPS games of lower development cost with near-infinite replay value and capability to adapt to the skills and preferences of individual players. We propose a search-based solution, where maps are evolved to optimize a fitness function that is based on the players’ average fighting time. For that purpose, four different map representations are tested and compared. Results obtained showcase the clear advantage of some representations in generating interesting FPS maps and demonstrate the promise of the approach followed for automatic level design in that game genre.
Driving Faster Than a Human Player Jan Quadflieg, Mike Preuss, Guenter Rudolph
TORCS car racing bots have improved significantly in the last years. We show that accurate curvature information for the upcoming corners enables offline learning a near-optimal driving style that consistently beats an expert human player (and the fastest currently known bots). Generalization to other tracks often, but not always succeeds, so that the method is extended by an online error correction mechanism well suited to the warmup phase of the Simulated Car Racing Championships.
Learning Chasing Behaviours of Non-Player Characters in Games using SARSA Somnuk Phon-Amnuaisuk
In this paper, we investigate the application of reinforcement learning in the learning of chasing behaviours of non-player characters (NPCs). One popular method for encoding intelligent behaviours in game is by scripting where the behaviours on the scene are predetermined. Many popular games have their game intelligence encoded in this manner. The application of machine learning techniques to learn non-player character behaviours is still being explored by game AI researchers. The application of machine learning in games could enhance game playing experience. In this report, we investigate the design and implementation of reinforcement learning to learn the chasing behaviours of NPCs. The design and the simulation results are discussed and further work in this area is suggested.
Wednesday 27 April 16:20-17:00, room 4: Mendel, Best Paper Nominations
Chair: Mike Preuss
Towards Procedural Strategy Game Generation: Evolving Complementary Unit Types Tobias Mahlmann, Julian Togelius, Georgios N. Yannakakis
The Strategy Game Description Game Language (SGDL) is intended to become a complete description of all aspects of strategy games, including rules, parameters, scenarios, maps, and unit types. One of the main envisioned uses of SGDL, in combination with an evolutionary algorithm and appropriate fitness functions, is to allow the generation of complete new strategy games or variations of old ones. This paper presents a first version of SGDL, capable of describing unit types and their properties, together with plans for how it will be extended to other sub-domains of strategy games. As a proof of the viability of the idea and implementation, an experiment is presented where unit types are evolved so as to generate complementary properties. A fitness function based on Monte Carlo simulation of gameplay is devised to test complementarity.
Training Neural Networks to Play Backgammon Variants Using Reinforcement Learning Nikolaos Papahristou, Ioannis Refanidis
Backgammon is a board game that has been studied considerably by computer scientists. Apart from standard backgammon, several yet unexplored variants of the game exist, which use the same board, number of checkers, and dice but may have different rules for moving the checkers, starting positions and movement direction. This paper studies two popular variants in Greece and neighboring countries, named Fevga and Plakoto. Using reinforcement learning and Neural Network function approximation we train agents that learn a game position evaluation function for these games. We show that the resulting agents significantly outperform the open-source program Tavli3D.
Evolving Behavior Trees for the Mario AI Competition Using Grammatical Evolution Diego Perez, Miguel Nicolau, Michael O’Neill, Anthony Brabazon
This paper investigates the applicability of Genetic Programming type systems to dynamic game environments. Grammatical Evolution was used to evolved Behaviour Trees, in order to create controllers for the Mario AI Benchmark. The results obtained reinforce the applicability of evolutionary programming systems to the development of artificial intelligence in games, and in dynamic systems in general, illustrating their viability as an alternative to more standard AI techniques.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
Revisiting Monte-Carlo Tree Search on a Normal Form Game: NoGo C.-W. Chou, O. Teytaud, S.-J. Yen
We revisit Monte-Carlo Tree Search on a recent game, termed NoGo. Our goal is to check if known results in Computer-Go and various other games are general enough for being applied directly on a new game. We also test if the known limitations of Monte-Carlo Tree Search also hold in this case and which improvements of Monte-Carlo Tree Search are necessary for good performance and which have a minor effect. We also tested a generic Monte-Carlo simulator, designed for “no more moves” games.
Upper Confidence Trees with Short Term Partial Information Olivier Teytaud, Sebastien Flory
We show some mathematical links between partially observable (PO) games in which information is regularly revealed, and simultaneous actions games. Using this, we study the extension of Monte-Carlo Tree Search algorithms to PO games and to games with simultaneous actions. We apply the results to Urban Rivals, a free PO internet card game with more than 10 millions of registered users.
Multiple Tree for Partially Observable Monte-Carlo Tree Search David Auger
We propose an algorithm for computing approximate Nash equilibria of partially observable games using Monte-Carlo tree search based on recent bandit methods. We obtain experimental results for the game of phantom tic-tac-toe, showing that strong strategies can be efficiently computed by our algorithm.
Thursday 28 April 09:30-11:00, room 5: Eraclito, Session 1
Chair: Ernesto Tarantino
Improving ESOP-based Synthesis of Reversible Logic Using Evolutionary Algorithms Rolf Drechsler, Alexander Finder, Robert Wille
Reversible circuits, i.e. circuits which map each possible input vector to a unique output vector, build the basis for emerging applications e.g. in the domain of low-power design or quantum computation. As a result, researchers developed various approaches for synthesis of this kind of logic. In this paper, we consider the ESOP-based synthesis method. Here, functions given as Exclusive Sum of Products (ESOPs) are realized. In contrast to conventional circuit optimization, the quality of the resulting circuits depends thereby not only on the number of product terms, but on further criteria as well. In this paper, we present an approach based on an evolutionary algorithm which optimizes the function description with respect to these criteria. Instead of ESOPs,Pseudo Kronecker Expression (PSDKRO) are thereby utilized enabling minimization within reasonable time bounds. Experimental results confirm that the proposed approach enables the realization of circuits with significantly less cost.
Genetic Defect Based March Test Generation for SRAM Stefano Di Carlo, Gianfranco Politano, Paolo Prinetto, Alessandro Savino, Alberto Scionti
The continuos shrinking of semiconductor’s nodes makes semiconductor memories increasingly prone to electrical defects tightly related to the internal structure of the memory. Exploring the effect of fabrication defects in future technologies, and identifying new classes of functional fault models with their corresponding test sequences, is a time consuming task up to now mainly performed by hand. This paper proposes a new approach to automate this procedure exploiting a dedicated genetic algorithm.
Enhanced Reverse Engineering using Genetic-Algorithms-based Experimental Parallel Workflow for Optimum Design Damir Vucina, Igor Pehnec
Shape optimization is numerically very intensive due to multidisciplinary objectives and constraints, many shape variables, non linear models, geometric infeasibility of candidate designs, etc. It involves participation of numerical optimizers, computer- aided geometric modelers and subject-related simulators as well as their coupling at the process- and data levels. This paper develops a simple experimental workflow which employs existing commercial software for computer-aided design, finite element analysis and evolutionary optimization modules. It sets up parallel execution of multiple simulators to reduce the execution time, which is implemented inexpensively by means of a self-made .net- based cluster. Shape optimization is introduced in the generic context of ‘enhanced’ reverse engineering with optimization whereby the initial solution can be obtained by 3D optical scanning and parameterization of an existing solution. [index]
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
Evolution of Test Programs Exploiting a FSM Processor Model Ernesto Sanchez, Giovanni Squillero, Alberto Tonda
Microprocessor testing is becoming a challenging task, due to the increasing complexity of modern architectures. Nowadays, most architectures are tackled with a combination of scan chains and Software-Based Self-Test (SBST) methodologies. Among SBST techniques, evolutionary feedback-based ones prove effective in microprocessor testing: their main disadvantage, however, is the considerable time required to generate suitable test programs. A novel evolutionary-based approach, able to appreciably reduce the generation time, is presented. The proposed method exploits a high-level representation of the architecture under test and a dynamically built Finite State Machine (FSM) model to assess fault coverage without resorting to time-expensive simulations on low-level models. Experimental results, performed on an OpenRISC processor, show that the resulting test obtains a nearly complete fault coverage against the targeted fault model.
Fault-Tolerance Simulation of Brushless Motor Control Circuits Huicong Wu, Jie Chu, Liang Yuan, Qiang Zhao, Shanghe Liu
Brushless Motors are frequently employed in control systems. The reliability of the brushless motor control circuits is highly critical especially in harsh environments. This paper presents an Evolvable Hardware platform for automated design and adaptation of a brushless motors control circuit. The platform uses the principles of EHW to automate the configuration of FPGA dedicated to the implementation of the motor control circuit. The ability of the platform to adapt to a certain number of faults was investigated through introducing single logic unit faults and multi logic units faults. Results show that the functionality of the motor control circuit can be recovered through evolution. They also show that the location of faulty logic units can affect the ability of the evolutionary algorithm to evolve correct circuits, and the evolutionary recovery ability of the circuit decreases as the number of fault logic units is increasing.
Thursday 28 April 09:30-11:00, room 4: Mendel, Session 1
Chair: Stefano Cagnoni
A Hybrid Particle Swarm Optimisation with Differential Evolution Approach to Image Segmentation Wenlong Fu, Mark Johnston, Mengjie Zhang
Image segmentation is a key step in image analysis and many image segmentation methods are time-consuming. The Otsu method and Gaussian Mixture Model (GMM) method are popular in image segmentation, but it is computationally difficult to find their globally optimal threshold values. Particle Swarm Optimisation (PSO) is an intelligent search method and has been widely used in many fields. However it is also easily trapped in local optima. In this paper, we propose a hybrid between PSO and Differential Evolution (DE) to solve the optimisation problems associated with the Otsu model and GMM, and apply these methods to natural image segmentation. The hybrid PSO-DE method is compared with an exhaustive method for the Otsu model, and fitted GMMs are compared directly with image histograms. Hybrid PSO-DE is also compared with standard PSO on these models. The experimental results show that the hybrid PSO-DE approach to image segmentation is effective and efficient.
Evolutionary Synthesis of a Trajectory Integrator for an Analogue Brain-Computer Interface Mouse Riccardo Poli, Mathew Salvaris, Caterina Cinel
Recently significant steps have been made towards effective EEG-based brain-computer interfaces for mouse control. A major obstacle in this line of research, however, is the integration of the noisy and contradictory information provided at each time step by the signal processing systems into a coherent and precise trajectory for the mouse pointer. In this paper we attack this difficult problem using genetic programming, obtaining extremely promising results.
Transparent, Online Image Pattern Classification Using a Learning Classifier System Ignas Kukenys, Will Browne, Mengjie Zhang
Image pattern classification in computer vision problems is challenging due to large, sparse input spaces with the added demand for generalisation and accuracy of results. The Evolutionary Computation technique of Learning Classifier Systems (LCS) addresses such problems, but has not been applied previously to this domain. Instead, online, supervised techniques on fixed data sets have been shown to be highly accurate. This paper shows that LCS enable online, reinforcement learning on datasets that may change over time and produce transparent (human readable) classification rules. Further work is needed in domains applicable to online, supervised learning to achieve benchmark accuracy, but the promising initial results auger well for domains, such as mobile robotics, where compact, accurate and general rules learnt in a graceful manner are required
Thursday 28 April 11:30-13:00, room 4: Mendel, Session 2
Chair: Mengjie Zhang
Automatic Selection of Pareto-optimal Topologies of Hidden Markov Models using Multicriteria Evolutionary Algorithms
Pawel Swietojanski, Robert Wielgat, Tomasz Zielinski
In this paper a novel approach of automatic selection of Hidden Markov Models (HMM) structures under Pareto-optimality criteria is presented. Proof of concept is delivered in automatic speech recognition (ASR) discipline where two research scenarios including recognition of speech disorders as well as classi
cation of bird species using their voice are performed. The conducted research unveiled that the Pareto Optimal Hidden Markov Models (POHMM) topologies outperformed both manual structures selection based on theoretical prejudices as well as the automatic approaches that used a single objective only.
Advanced Metaheuristic Approaches and Population Doping for a Novel Modeling-Based Method of Positron Emission Tomography Data Analysis Jarkko Pekkarinen, Harri Pölönen, Ferrante Neri
This paper proposes a metaheuristic approach to solve a complex large scale optimization problem that originates from a recently introduced Positron Emission Tomography (PET) data analysis method that provides an estimate of tissue heterogeneity. More specifically three modern metaheuristics have been tested. These metaheustics are based on Differential Evolution, Particle Swarm Optimization, and Memetic Computing. On the basis of a preliminary analysis of the fitness landscape, an intelligent initialization technique has been proposed in this paper. More specifically, since the fitness landscape appears to have a strong basin of attraction containing a multimodal landscape, a local search method is applied to one solution at the beginning of the optimization process and inserted into a randomly generated population. The resulting “doped” population is then processed by the metaheuristics. Numerical results show that the application of the local search at the beginning of the optimization process leads to significant benefits in terms of algorithmic performance. Among the metaheuristics analyzed in this study, the DE based algorithm appears to display the best performance.
Segmentation of ultrasound breast images: optimization of algorithm parameters Leonardo Bocchi, Francesco Rogai
Segmentation of lesions in ultrasound imaging is one of the key issues in the development of Computer Aided Diagnosis systems. This paper presents a hybrid solution to the segmentation problem. A linear filter composed of a Gaussian and a Laplacian of Gaussian filter is used to smooth the image, before applying a dynamic threshold to extract a rough segmentation. In parallel, a despeckle filter based on a Cellular Automata (CA) is used to remove noise. Then, an accurate segmentation is obtained applying the GrowCut algorithm, initialized from the rough segmentation, to the CA-filtered image. The algorithm requires tuning of several parameters, which proved difficult to obtain by hand. Thus, a Genetic Algorithm has been used to find the optimal parameter set. The fitness of the algorithm has been derived from the segmentation error obtained comparing the automatic segmentation with a manual one. Results indicate that using the GA-optimized parameters, the average segmentation error decreases from 5.75% obtained by manual tuning to 1.5% with GA-optimized parameters.
Tracking Multiple Targets with Adaptive Swarm Optimization Jun Liu, Hongbin Ma, Xuemei Ren
This paper mainly concentrates on the problem of tracking multiple targets in the noisy environment. To better recognize the eccentric target in a specific environment, one proposed objective function gets the target’s shape in the subgraph. Inspired by particle swarm optimization, the proposed algorithm of tracking multiple targets adaptively modifies the covered radii of each subgroup in terms of the minimum distances among the subgroups, and successfully tracks the conflicting targets. The theoretic results as well as the experiments on tracking multiple ants indicate that this efficient method has successfully been applied to the complex and changing practical systems.
Wednesday 27 April 14:30-16:00, room 3: Leonardo, presented during the second session of evonum
When Novelty is Not Enough Giuseppe Cuccu, Faustino Gomez
The idea of evolving novel rather than fit solutions has recently been offered as a way to automatically discover the kind of complex
solutions that exhibit truly intelligent behavior. So far, novelty search has only been studied in the context of problems where the number of possible “different” solutions has been limited. In this paper, we show, using a task with a much larger solution space, that selecting for novelty alone does not offer an advantage over fitness-based selection. In addition, we examine how the idea of novelty search can be used to sustain diversity and improve the performance of standard, fitness-based search.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
A Part-Of-Speech Lexicographic Encoding for an Evolutionary Word Sense Disambiguation Approach Antonia Azzini, Mauro Dragoni, Andrea G.B. Tettamanzi
This work proposes a novel distributed scheme based on a part-of-speech tagged lexicographic encoding to represent the context in which a particular word occurs in an evolutionary approach for word sense disambiguation. Tagged dataset for every sense of a polysemous word are considered as inputs to supervised classifiers, Artificial Neural Networks (ANNs), which are evolved by a joint optimization of their structures and weights, together with a similarity based recombination operator. The viability of the approach has been demonstrated through experiments carried out on a representative set of polysemous words. Comparison with the best entries of the Semeval-2007 competition has shown that the proposed approach is competitive with state-of-the-art WSD approaches.
Migrating Birds Optimization: A New Meta-heuristic Approach and Its Application to the Quadratic Assignment Problem Ekrem Duman, Mitat Uysal, Ali Fuat Alkaya
In this study we propose a new nature inspired metaheuristic approach based on the V formation flight of the migrating birds which is proven to be an effective formation in energy minimization. Its performance is tested on quadratic assignment problem instances arising from a real life problem and very good results are obtained. The quality of the solutions turned out to be better than simulated annealing, tabu search and guided evolutionary simulated annealing approaches. These results indicate that our new metaheuristic approach could be an important player in metaheuristic based optimization.
Thursday 28 April 09:30-11:00, room 6: Copernico, Music
Chair: Juan Romero
Parallel Evolutionary Optimization of Digital Sound Synthesis Parameters Batuhan Bozkurt, Kamer Ali Yuksel
In this research, we propose a novel parallelizable architecture for the optimization of various sound synthesis parameters. The architecture employs genetic algorithms to match the parameters of different sound synthesizer topologies to target sounds. The fitness function is evaluated in parallel to decrease its convergence time. Based on the proposed architecture, we have implemented a framework using the SuperCollider audio synthesis and programming environment and conducted several experiments. The results of the experiments have shown that the framework can be utilized for accurate estimation of the sound synthesis parameters at promising speeds.
Weighted Markov Chain Model for Musical Composer Identification Maximos A. Kaliakatsos-Papakostas, Michael G. Epitropakis, Michael N. Vrahatis
Several approaches based on the ‘Markov chain model’ have been proposed to tackle the composer identification task. In the paper at hand, we propose to capture phrasing structural information from inter onset and pitch intervals of pairs of consecutive notes in a musical piece, by incorporating this information into a weighted variation of a first order Markov chain model. Additionally, we propose an evolutionary procedure that automatically tunes the introduced weights and exploits the full potential of the proposed model for tackling the composer identification task between two composers. Initial experimental results on string quartets of Haydn, Mozart and Beethoven suggest that the proposed model performs well and can provide insights on the inter onset and pitch intervals on the considered musical collection.
SANTIAGO – A Real-time Biological Neural Network Environment for Generative Music Creation (Best Paper Nomination) Hernán Kerlleñevich, Pablo Ernesto Riera, Manuel Camilo Eguía
In this work we present a novel approach for interactive music generation based on the dynamics of biological neural networks. We develop SANTIAGO, a real-time environment built in Pd-Gem, which allows to assemble networks of realistic neuron models and map the activity of individual neurons to sound events (notes) and to modulations of the sound event parameters (duration, pitch, intensity, spectral content). The rich behavior exhibited by this type of networks gives rise to complex rhythmic patterns, melodies and textures that are neither too random nor too uniform, and that can be modified by the user in an interactive way.
Thursday 28 April 11:30-13:00, room 6: Copernico, Architecture and Insdtallation
Chair: Juan Romero
Evolution of Architectural Floor Plans Robert Flack, Brian Ross
Layout planning is a process of sizing and placing rooms (e.g. in a house) while attempting to optimize various criteria. Often there are conflicting criteria such as construction cost, minimizing the distance between related activities, and meeting the area requirements for these activities. This paper describes new techniques for automating the layout planning process using evolutionary computation. New innovations include allowing polygonal exteriors and multiple floors. Multi-objective ranking algorithms are tested to balance the many objectives in this problem. The evolutionary representation and requirements specification used provide great flexibility in problem scope and depth of problems to be considered. A variety of pleasing plans have been evolved with the approach.
Combining Structural Analysis and Multi-Objective Criteria for Evolutionary Architectural Design (Best Paper Nomination) Jonathan Byrne, Michael Fenton, Erik Hemberg, James McDermott, Michael O’Neill, Elizabeth Shotton, Ciaran Nally
This study evolves and categorises a population of conceptual designs by their ability to handle physical constraints. The design process involves a trade-off between form and function. The aesthetic considerations of the designer are constrained by physical considerations and material cost. In previous work, we developed a design grammar capable of evolving aesthetically pleasing designs through the use of an interactive evolutionary algorithm. This work implements a fitness function capable of applying engineering objectives to automatically evaluate designs and, in turn, reduce the search space that is presented to the user.
Path of Patches: Implementing an Evolutionary Soundscape Art Installation José Fornari
Computational adaptive methods have already been used in Installation art. Among them, Generative artworks are those that value the artistic process, rather than its final product, which can now be of multimodal nature. Evolutionary Algorithms (EA) can be successfully applied to create a Generative art process that is self-similar yet always new. EAs allow the creation of dynamic complex systems from which identity can emerge. In computational sonic arts, this is ecological modeling; here named Evolutionary Soundscape. This article describes the development and application of an EA computing system developed to generate Evolutionary Soundscapes in a Multimodal Art Installation. Its physical structure uses paths of forking pipes attached to fans and microphones that capture audio to feed the EA system that creates the Soundscape. Here is described the EA system; its design in PureData (PD); its connection with the physical structure; its artistic endeavor and final sonic accomplishments.
Thursday 28 April 14:30-16:00, room 6: Copernico, Aesthetics
Chair: Gary Greenfield
Evolving Art using multiple Aesthetic Measures E. den Heijer, A.E. Eiben
In this paper we investigate the applicability of Multi-Objective Optimization (MOO) in Evolutionary Art. We evolve images using an unsupervised evolutionary algorithm and we use two aesthetic measures as fitness functions concurrently. We use three different pairs from a set of three aesthetic measures and we compare the output of each pair to the output of other pairs, and to the output of experiments with a single aesthetic measure (non-MOO). We investigate 1) whether properties of aesthetic measures can be combined using MOO and 2) whether the use of MOO in evolutionary art results in different images, or perhaps “better” images. All images in this paper can be viewed in colour at http://www.few.vu.nl/~eelco/
Using Grammatical Evolution to Parameterise Interactive 3D Image Generation (Best Paper Nomination) Miguel Nicolau, Dan Costelloe
This paper describes an Interactive Evolutionary system for generating pleasing 3D images using a combination of Grammatical Evolution and Jenn3d, a freely available visualiser of Cayley graphs of finite Coxeter groups. Using interactive GE with some novel enhancements, the parameter space of the Jenn3d image-generating system is navigated by the user, permitting the creation of realistic, unique and award winning images in just a few generations. One of the evolved images has been selected to illustrate the proceedings of the EvoStar conference in 2011.
Modelling human preference in evolutionary art (Best Paper Nomination) Aniko Ekart, Divya Sharma, Stayko Chalakov
Creative activities including arts are characteristic to humankind. Our understanding of creativity is limited, yet there is substantial research trying to mimic human creativity in artificial systems and in particular to produce systems that automatically evolve art appreciated by humans. We propose here to model human visual preference by a set of aesthetic measures identified through observation of human selection of images and then use these for automatic evolution of aesthetic images.
Thursday 28 April 16:20-17:50, room 6: Copernico, Generative Techniques
Chair: Gary Greenfield
Generative art inspired by nature, using NodeBox Tom De Smedt, Ludivine Lechat, Walter Daelemans
NodeBox is a free application for producing generative art. This paper gives an overview of the nature-inspired functionality in NodeBox and the artworks we created using it. We demonstrate how it can be used for evolutionary computation in the context of computer games and art, and discuss some of our recent research with the aim to simulate (artistic) brainstorming using language processing techniques and semantic networks.
The T. albipennis Sand Painting Artists Paulo Urbano
In recent years, we have seen some artificial artistic work that has drawn inspiration from swarm societies, in particular ant societies. Ant paintings are abstract images corresponding to visualizations of the paths made by a group of virtual ants on a bi-dimensional space. The research on ant paintings has been focused around a stigmergic mechanism of interaction: the deposition of pheromones, largely used by ants. In an effort to further on the research on ant inspired artificial art, we introduce the T. albipennis sand painting artists, which draw direct inspiration from the ant species Temnothorax albipennis (formerly tuberointerruptus). These ants build simple circular walls, composed of grains of sand or fragments of stones, at a given distance from the central cluster of adult ants and brood. The brood and ants cluster function as a template, which combined with self-organization are responsible for the particular wall pattern formation. The T. albipennis artists are artificial two-dimensional builders, starting from unorganized placement of virtual sand grains, they rearrange them, creating some interesting patterns composed of scattered pointillistic and imperfect circles, a colored moon-like landscape full of craters.
Creating Choreography with Interactive Evolutionary Algorithms Jonathan Eisenmann, Benjamin Schroeder, Matthew Lewis, Rick Parent
Directing a group behavior towards interesting and complex motion can and should be intuitive, iterative, and often participatory. Toward this end, we present a choreographic system that enables designers to explore a motion space based on a parametric model of behaviors. Designers may work with the system by moving back and forth through two complementary stages: first, using an evolutionary algorithm to traverse the space of behavior possibilities, allowing designers to emphasize desired kinds of motion while leaving room for an element of the unexpected, and second, using selected behaviors to direct the group motion of simple performing creatures. In the second stage, evolved group motion behaviors from the first stage are used alongside existing high-level parametric rules for local articulated motion.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
Music Translation of Tertiary Protein Structure: Auditory Patterns of the Protein Folding Riccardo Castagna, Alessandro Chiolerio, Valentina Margaria
We have translated genome-encoded protein sequence into musical notes and created a polyphonic harmony taking in account its tertiary structure. We did not use a diatonic musical scale to obtain a pleasant sound, focusing instead on the spatial relationship between aminoacids closely placed in the 3-dimensional protein folding. In this way, the result is a musical translation of the real morphology of the protein, that opens the challenge to bring musical harmony rules into the proteomic research field.
Ludic Considerations of Tablet-Based Evo-Art Simon Colton, Michael Cook, Azalea Raad
With the introduction of the iPad and similar devices, there is a unique opportunity to build tablet-based evolutionary art software for general consumption, and we describe here the i-ELVIRA iPad ap- plication for such purposes. To increase the ludic enjoyment users have with i-ELVIRA, we designed a GUI which gives the user a higher level of control and more efficient feedback than usual for desktop evo-art software. This relies on the efficient delivery of crossover and mutation images which bear an appropriate amount of resemblance to their parent(s). This requirement in turn led to technical difficulties which we resolved via the implementation and experimentation described here.
A Genetic Algorithm for Dodecaphonic Compositions Roberto De Prisco, Gianluca Zaccagnino, Rocco Zaccagnino
In this paper we propose an automatic music composition system for dodecaphonic music based on a genetic algorithm. Dodecaphonic music, introduced by A. Schoenberg, departs from the concept of tonality by considering all 12 notes equally important. Dodecaphonic compositions are constructed starting from a 12-note series, which is a sequence of all the 12 notes; the compositional process uses the starting 12-note series as a seed and builds the music creating new fragments of music obtained by transforming the seed series. The algorithm proposed in this paper automates the compositional process taking a seed series as input and automatically creating a dodecaphonic composition. We have implemented the algorithm and we have run several tests to study its behaviour.
A Customizable Recognizer for Orchestral Conducting Gestures based on Neural Networks Roberto De Prisco, Paolo Sabatino, ianluca Zaccagnino, Rocco Zaccagnino
In this paper we present a system for the recognition of orchestral conducting gestures using the Nintendo Wiimote controller. The system is based on a neural network. This is not the first of such systems; however compared to previous systems that use the Wiimote or other cheap hardware, it has several advantages: it is fully customizable, continuous and does not require third party commercial software. The system has been implemented in Java and we have run several tests to evaluate its behavior.
Evolving Four-Part Harmony Using Genetic Algorithms Patrick Donnelly, John Sheppard
This paper presents a genetic algorithm that evolves a four-part musical composition-melodically, harmonically, and rhythmically. Unlike similar attempts in the literature, our composition evolves from a single musical chord without human intervention or initial musical material. The mutation rules and fitness evaluation are based on common rules from music theory. The genetic operators and individual mutation rules are selected from probability distributions that evolve alongside the musical material.
A Sonic Eco-system of Self-Organising Musical Agents Arne Eigenfeldt, Philippe Pasquier
We present a population of autonomous agents that exist within a sonic eco-system derived from real-time analysis of live audio. In this system, entitled Coming Together: Shoals, agents search for food consisting of CataRT unit analyses, which, when found, are consumed through granulation. Individual agents are initialised with random synthesis parameters, but communicate these parameters to agents in local neighborhoods. Agents form social networks, and converge their parameters within these networks, thereby creating unified grain streams. Separate gestures thus emerge through the self-organisation of the population.
Neurogranular Synthesis: Granular Synthesis Controlled by a Pulse-coupled Network of Spiking Neurons James Kevin McCracken, John Matthias
We introduce a method of generating grain parameters of a granular synthesiser in real-time by using a network of artificial spiking neurons, the behaviour of which is determined by user-control of a small number of network parameters; ‘Neurogranular synthesis’. The artificial network can exhibit a wide variety of behaviour from loosely correlated to highly synchronised, which can produce interesting sonic results, particularly with regard to rhythmic textures.
Interactive Biomimetic Space: An Interactive Installation to Explore Living Architecture Liraz Mor, Chao Liu, Sebastian von Mammen
This paper describes a computer-based Interactive Biomimetic Space (IBS) installation. Through an interactive process, a user creates and relates new spaces. The simulation of a simplified ecosystem populates the created space with life. The installation attempts to inspire architectural design ideas by integrating biological principles. In particular, the biological concepts of stochastic motion, interaction and reproduction of artificial swarms have been explored and applied. Both the user and the swarm agents contribute to the design process, which results in interesting design outputs with a certain degree of unpredictability. We introduce the theoretical background of our work, outline its technical implementation, and present various interaction examples and scenarios.
Evolving Textures from High Level Descriptions: Gray with an Accent Color Craig Reynolds
This paper describes a prototype evolutionary texture synthesis tool meant to assist a designer or artist by automatically discovering many candidate textures that fit a given stylistic description. The textures used here are small color images, created by procedural texture synthesis. This prototype uses a single stylistic description: a textured gray image with a small amount of color accent. A hand-written prototype fitness function rates how well an image meets this description. Genetic programming uses the fitness function to evolve programs written in a texture synthesis language. A tool like this can automatically generate a catalog of variations on the given theme. A designer could then scan through these to pick out those that seem aesthetically interesting. Their procedural “genetic” representation would allow them to be further adjusted by interactive evolution. It also allows re-rendering them at arbitrary resolutions and provides a way to store them in a highly compressed form allowing lossless reconstruction.
Aesthetic Classification and Sorting Based on Image Compression Juan Romero, Penousal Machado, Adrian Carballal, Olga Osorio
One of the problems in evolutionary art is the lack of robust fitness functions. This work explores the use of image compression estimates to predict the aesthetic merit of images. The metrics proposed estimate the complexity of an image by means of JPEG and Fractal compression. The success rate achieved is 72.43% in aesthetic classification tasks of a problem belonging to the state of the art. Finally, the behavior of the system is shown in an image sorting task based on aesthetic criteria.
iSoundScape: Adaptive Walk on a Fitness Soundscape Reiji Suzuki, Souichiro Yamaguchi, Martin Cody, Charles Taylor, Takaya Arita
Adaptive walk on a fitness soundscape is a new kind of interactive evolutionary computation for musical works. This system provides a virtual two-dimensional grid called a “soundscape” in which each point corresponds to a genotype that generates a sound environment. By using the human abilities of localization and selective listening, the user can “walk” toward genotypes that generate more favorable sounds. This corresponds to a hill-climbing process on the “fitness soundscape.” This environment can be realized by multiple speakers or a headphone creating “surround sound.” In this work we describe two new applications of adaptive walk. The first is developed for creating spatially grounded musical pieces as an interactive art based on fitness soundscapes. The second provides a new way to explore the ecology and evolution of bird songs, from scientific and educational viewpoints, by exploring the ecological space of “nature’s music”, produced by populations of virtual songbirds.
Merging Aesthetics with Functionality: An Interactive Genetic Algorithm Based on the Principle of Weighted Mutation Eirini Vouliouri
This paper proposes an algorithm through which the development of computationally generated forms can be externally directed towards both functional objectives and intuitive design targets. More precisely, it presents a special version of Interactive Genetic Algorithm, which introduces Weighted Mutation as a method to support the long life of genes corresponding to favored phenotypic characteristics. At the same time, optimization processes towards operational goals are also enabled. A set of experiments is conducted on the case study of a building facade, which appears to provide a suitable means for the investigation of functional, as well as aesthetic issues. The results are positively assessed, since they prove that this new methodology broadens the capacities of standard Interactive Genetic Algorithms, shedding light on how a constructive human-machine relationship can benefit the design process.
Wednesday 27 April 11:30-13:00, room 3: Leonardo, Session 1
Chair: Anna I Esparcia-Alcazar
Opposition-Based Learning in Compact Differential Evolution Giovanni Iacca, Ferrante Neri, Ernesto Mininno
This paper proposes the integration of the generalized opposition based learning into compact Differential Evolution frameworks and tests its impact on the algorithmic performance. Opposition-based learning is a technique which has been applied, in several circumstances, to enhance the performance of Differential Evolution. It consists of the generation of additional points by means of a hyper-rectangle. These opposition points are simply generated by making use of a central symmetry within the hyper-rectangle. In the population based Differential Evolution, the inclusion of this search move corrects a limitation of the original algorithm, i.e. the scarcity of search moves, and sometimes leads to benefits in terms of algorithmic performance. The opposition-based learning scheme is further improved in the generalized scheme by integrating some randomness and progressive narrowing of the search. The proposed study shows how the generalized opposition-based learning can be encoded within a compact Differential Evolution framework and displays its effect on a set of diverse problems. Numerical results show that the generalized opposition-based learning is beneficial for compact Differential Evolution employing the binomial crossover while its implementation is not always successful when the exponential crossover is used. In particular, the opposition-based logic appears to be in general promising for non-separable problems whilst it seems detrimental for separable problems.
Data Mining using Unguided Symbolic Regression on a Blast Furnace Dataset Michael Kommenda, Gabriel Kronberger, Christoph Feilmayr, Michael Affenzeller
In this paper a data mining approach for variable selection and knowledge extraction from datasets is presented. The approach is based on unguided symbolic regression (every variable present in the dataset is treated as the target variable in multiple regression runs) and a novel variable relevance metric for genetic programming. The relevance of each input variable is calculated and a model approximating the target variable is created. The genetic programming configurations with different target variables are executed multiple times to reduce stochastic effects and the aggregated results are displayed as a variable interaction network. This interaction network highlights important system components and implicit relations between the variables. The whole approach is tested on a blast furnace dataset, because of the complexity of the blast furnace and the many interrelations between the variables. Finally the achieved results are discussed with respect to existing knowledge about the blast furnace process.
DISPAR-Tournament: a parallel population reduction operator that behaves like a tournament Ogier Maitre, Deepak Sharm, Nicolas Lachiche, Pierre Collet
This paper presents an experimental study of different variants of tournament selection, and proposes a new DISPAR-tournament (Disjoint Sets Parallel tournament) operator for population reduction to be used in parallel implementations of evolution strategies and other evolutionary algorithms.
Wednesday 27 April 14:30-16:00, room 3: Leonardo, Session 2
Chair: Aniko Ekart
Global characterization of the CEC 2005 fitness landscapes using fitness-distance analysis Christian Mueller, Ivo Sbalzarini
We interpret real-valued black-box optimization problems over continuous domains as black-box landscapes. The performance of a given optimization heuristic on a given problem largely depends on the characteristics of the corresponding landscape. Designing statistical measures that can be used to classify landscapes and quantify their topographical properties is hence of great importance. We transfer the concept of fitness-distance analysis from theoretical biology and discrete combinatorial optimization to continuous optimization and assess its potential to characterize black-box landscapes. Using the CEC 2005 benchmark functions, we empirically test the robustness and accuracy of the resulting landscape characterization and illustrate the limitations of fitness-distance analysis. This provides a first step toward a classification of real-valued black-box landscapes over continuous domains.
A Framework for Multi-Model EDAs with Model Recombination Thomas Weise, Stefan Niemczyk, Raymond Chiong, Mingxu Wan
Estimation of Distribution Algorithms (EDAs) are evolutionary optimization methods that build models which estimate the distribution of promising regions in the search space. Conventional EDAs use only one single model at a time. One way to efficiently explore multiple areas of the search space is to use multiple models in parallel. In this paper, we present a general framework for both single- and multi-model EDAs. We propose to use clustering to divide the selected individuals into different groups which are then utilized to build separate models. For the multi-model case, we introduce the concept of model recombination. This novel framework has great generality, encompassing the traditional Evolutionary Algorithm and the EDA as its extreme cases. We instantiate our framework in form of a real-valued algorithm and apply this algorithm to some well-known benchmark functions. Numerical results show that both single- and multi-model EDAs have their own strengths and weaknesses and that the multi-model EDA is able to prevent premature convergence.
Wednesday 27 April 16:20-17:50, room 3: Leonardo, Nature-inspired techniques in scheduling, planning and timetabling
Chair: A. Şima Uyar and Neil Urquhart
A Genetic Algorithm for Radiotherapy Pre-treatment Scheduling Sanja Petrovic, Elkin Castr
This paper is concerned with the radiotherapy pre-treatment patient scheduling. Radiotherapy pre-treatment deals with localisation of the area to be irradiated and generation of a treatment plan for a patient. A genetic algorithm is developed for patient scheduling which evolves priority rules for operations of radiotherapy pre-treatment. The fitness function takes into consideration the waiting time targets of patients and also the early idle time on resources. Real world data from a hospital in the UK are used in experiments.
Experimental Comparison of Selection Hyper-Heuristics for the Short-Term Electrical Power Generation Scheduling Problem Argun Berberoglu, A. Şima Uyar
Abstract.This paper presents an experimental comparison of a selection hyper-heuristic approach with several heuristic selection and move acceptance strategy combinations for the Short-Term Electrical Power Generation Scheduling problem. Tests are performed to analyze the efficiency of the combinations using problem instances taken from literature. Results show that the hyper-heuristic using the random permutation descent heuristic selection method and the only improving move acceptance scheme achieves the best results on the chosen problem instances. Because of the promising results, research will continue for further enhancements
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
Nature-inspired Optimization for Biped Robot Locomotion and Gait Planning Shahriar Asta, Sanem Sariel-Tala
Biped locomotion for humanoid robots is a challenging problem that has come into prominence in recent years. As the degrees of freedom of a humanoid robot approaches to that of humans, the need for a better, flexible and robust maneuverability becomes inevitable for real or realistic environments.This paper presents new motion types for a humanoid robot in coronal plane on the basis of Partial Fourier Series model. To the best of our knowledge, this is the first time that omni-directionality has been achieved for this motion model. Three different nature-inspired optimization algorithms have been used to improve the gait quality by tuning the parameters of the proposed model. It has been empirically shown that the trajectories of the two specific motion types, namely side walk and diagonal walk, can be successfully improved by using these optimization methods. The best results are obtained by the Simulated Annealing procedure with restarting.
Planning and optimising organisational travel plans using an Evolutionary Algorithm Neil Urquhart
Commuting to the workplace is a highly individualistic experience, especially where the private car is the chosen mode of transport. The costs of using cars with low occupancy rates are significant in environmental terms as well as requiring the provision of parking space at the workplace. This paper examines the use of an Evolutionary Algorithm based problem solver to construct travel plans for three sites with 248,404 and 520 employees respectively at each site. Results presented suggest that a significant saving in overall distance travelled and parking spaces required is possible. The algorithm employed takes into account both hard constraints and soft constraints (such as work patterns and journey flexibility).
Wednesday 27 April 14:30-16:00, room 5: Eraclito, Session 1
Chair: Hendrik Richter
Memory-Based Immigrants for Ant Colony Optimization in Changing Environments Michalis Mavrovouniotis, Shengxiang Yang
Ant colony optimization (ACO) algorithms have proved that they can adapt to dynamic optimization problems (DOPs) when they are enhanced to maintain diversity. DOPs are important due to their similarities to many real-world applications. Several approaches have been integrated with ACO to improve their performance in DOPs, where memory-based approaches and immigrants schemes have shown good results on different variations of the dynamic travelling salesman problem (DTSP). In this paper, we consider a different variation of DTSP where traffic jams occur in a cyclic pattern. This means that old environments will re-appear in the future. A hybrid method that combines memory and immigrants schemes is proposed into ACO to address this kind of DTSPs. The memory-based approach is useful to directly move the population to promising areas in the new environment by using solutions stored in the memory. The immigrants scheme is useful to maintain the diversity within the population. The experimental results based on different test cases of the DTSP show that the memory-based immigrants scheme enhances the performance of ACO in cyclic dynamic environments.
Flexible Variable Neighborhood Search in Dynamic Vehicle Routing Briseida Sarasola, Mostepha R. Khouadjia, Enrique Alba, Laetitia Jourdan, El-Ghazali Talbi
Many optimization problems are dynamic, which means that the available data may change while the problem is being solved. Incorporating elements into the algorithm that take into account these changes usually leads to more effective algorithms which provide better solutions. In this work, we propose a flexibility strategy for the Vehicle Routing Problem with Dynamic Requests. We show that early decissions, which are taken in the beginning of the optimization process, influence the quality of final solutions for the dynamic problem. Our flexible algorithm provides better results than the canonical one and is competitive with the results in the literature.
An Investigation of Selection Hyper-heuristics in Dynamic Environments Berna Kiraz, A. Şima Uyar, Ender Özcan
Hyper-heuristics are high level methodologies that perform search over the space of heuristics rather than solutions for solving computationally difficult problems. A selection hyper-heuristic framework provides means to exploit the strength of multiple low level heuristics where each heuristic can be useful at different stages of the search. In this study, the behavior of a range of selection hyper-heuristics is investigated in dynamic environments. The results show that hyper-heuristics embedding learning heuristic selection methods are sufficiently adaptive and can respond to different types of changes in a dynamic environment.
Wednesday 27 April 16:20-17:50, room 5: Eraclito, Session 2
Chair: Ferrante Neri
CHC-based Algorithms for the Dynamic Traveling Salesman Problem Anabela Simoes, Ernesto Costa
The CHC algorithm uses an elitist selection method which, combined with an incest prevention mechanism and a method to diverge the population whenever it converges, allows the maintenance of the population diversity. This algorithm was successfully used in the past for static optimization problems. In this paper we propose three new and improved CHC-based algorithms designed to deal with dynamic environments. The performance of the investigated CHC algorithms is tested in different instances of the dynamic Traveling Salesman Problem.
The experimental results show the efficiency, robustness and adaptability of the improved CHC variants solving different dynamic traveling salesman problems.
Solving dynamic constrained optimization problems with asynchronous change pattern Hendrik Richter, Franz Dietel
We consider optimization problems with a dynamic fitness landscape and dynamic constraints that may change independent of each other in terms of their respective time regimes. This generally leads to asynchronous change pattern with the possibility of occasional synchronization points. We present a framework for describing such a dynamical setting and for performing numerical experiments on the algorithm’s behavior.
Wednesday 27 April 11:30-13:00, room 5: Eraclito, Session 1
Chairs: Joern Grahl and Christian Prins
Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows Arpad Rimmel, Fabien Teytau, Tristan Cazenav
The traveling salesman problem with time windows is known to be a really difficult benchmark for optimization algorithms. In this paper, we are interested in the minimization of the travel cost. To solve this problem, we propose to use the nested Monte-Carlo algorithm combined with a Self-Adaptation Evolution Strategy. We compare the efficiency of several fitness functions. We show that with our technique we can reach the state of the art solutions for a lot of problems in a short period of time.
Heuristics for a real-world mail delivery problem Elisabeth Gussmagg-Pfliegl, Fabien Tricoire, Karl F. Doerner, Richard F. Hartl, Stefan Irnich
We are solving a mail delivery problem by combining exact and heuristic methods. The problem is a tactical routing problem as routes for all postpersons have to be planned in advance for a period of several months. As for many other routing problems, the task is to construct a set of feasible routes serving each customer exactly once at minimum cost. Four different modes (car, moped, bicycle, and walking) are available, but not all customers are accessible by all modes. Thus, the problem is characterized by three interdependent decisions: the clustering of customers into districts, the choice of a mode for each district, and the routing of the postperson through its district. We present a two-pahse solution approach that we have implemented and tested on seven real world instances. Results show that the approach can compete with solutions currently employed and is able to improve them by up to 9.5%.
A PSO-based Memetic Algorithm for the Team Orienteering Problem Duc-Cuong Dang, Rym Nesrine Guibad, Aziz Moukri
This paper proposes an effective Particle Swarm Optimization (PSO)-based Memetic Algorithm (PSOMA) for the Team Orienteering Problem (TOP). TOP is a particular vehicle routing problem whose aim is to maximize the profit gained from visiting clients while not exceeding a travel cost/time limit. Our PSOMA features optimal splitting techniques and genetic crossover operators. Furthermore, the memetic characteristic of our PSOMA is strengthened by an intensive use of local search techniques and also by a low value of 0.07 for inertia. In our experiments with the standard benchmark for TOP, PSOMA attained a gap of only 0.016%, as compared to 0.041%, the best known gap in the literature.
Integrated Generation of Working Time Models and Staff Schedules in Workforce Management Volker Nissen, Maik Günther, René Schumann
Our project addresses the question how to automatically and simultaneously assign staff to workstations and generate optimised working time models on the basis of fluctuating personnel demand while taking into account practical constraints. Two fundamentally different solution approaches, a specialized constructive heuristic (commercial) and a hybrid metaheuristic (the evolution strategy) that integrates a repair heuristic to remove contraint violations are compared on a complex real-world problem from a retailer. The hybrid approach clearly outperforms the tailored constructive method. Taken together with our similar findings on a related staff scheduling problem from logistics this result suggests that the evolution strategy, despite its original focus on continuous parameter optimisation, is a powerful tool in combinatorial optimisation and deserves more attention. Moreover, hybridising a metaheuristic with a problem-specific repair heuristic seems a useful approach of resolving the conflict between domain-specific characteristics of a real-world problem and the desire to employ generic optimisation techniques, at least in the domain of workforce management.
[index]
evocomnet
Talks
Thursday 28 April 14:30-16:00, room 5: Eraclito, Session 1
Chair: Ernesto Tarantino
Investigation of Hyper-heuristics for Designing Survivable Virtual Topologies in Optical WDM Networks (Best Paper Nomination)
Fatma Corut Ergin, Aysegul Yayimli, A. Şima Uyar
In optical WDM networks, a fiber failure may result in a serious amount of data loss, hence, designing survivable virtual topologies is a critical problem. We propose four different hyper-heuristic approaches to solve this problem, each of which is based on a different category of nature inspired heuristics: evolutionary algorithms, ant colony optimization, simulated annealing, and adaptive iterated constructive search are used as the heuristic selection methods in the hyper-heuristics. Experimental results show that, all proposed hyper-heuristic approaches are successful in designing survivable virtual topologies. Furthermore, the ant colony optimization based hyper-heuristic outperforms the others.
On Improving the Capacity of Solving Large-scale Wireless Network Design Problems by Genetic Algorithms
Fabio D’Andreagiovanni
Over the last decade, wireless networks have experienced an impressive growth and now play a main role in many telecommunications systems. As a consequence, scarce radio resources, such as frequencies, became congested and the need for effective and efficient assignment methods arose. In this work, we present a Genetic Algorithm for solving large instances of the Power, Frequency and Modulation Assignment Problem, arising in the design of wireless networks. To our best knowledge, this is the first Genetic Algorithm that is proposed for such problem. Compared to previous works, our approach allows a wider exploration of the set of power solutions, while eliminating sources of numerical problems. The performance of the algorithm is assessed by tests over a set of large realistic instances of a Fixed WiMAX Network.
Ant-Based Multipath Routing for Wireless Mesh Networks (Best Paper Nomination)
Laurent Paquereau, Bjarne E. Helvik
Wireless Mesh Networks (WMNs) are envisioned as a flexible alternative for providing Internet access. In this context, one of the key challenges is to improve the capacity. One approach is to spread the load along multiple paths. Results achieved in wired networks using ant-based systems for this purpose make them attractive candidates. However, applying similar techniques directly to WMNs may be counter-productive due to the characteristics of multi-hop wireless communications, in particular interferences. In this paper, a novel hybrid approach, based on recording the Internet gateway used by ants and marking pheromone trails accordingly, is presented. Results are promising and indicate that adaptive and efficient load distribution can be achieved.
Thursday 28 April 16:20-17:50, room 5: Eraclito, Session 2
Chair: Ernesto Tarantino
A Multiobjective Hybrid Gravitational Search Algorithm for the Static Routing and Wavelength Assignment Problem
Álvaro Rubio-Largo, Miguel Á. Vega-Rodríguez, Juan A. Gómez-Pulido, Juan M. Sánchez-Pérez
One of the most favorable technology for exploiting the huge bandwidth of optical networks is known as Wavelength Division Multiplexing (WDM). Given a set of demands, the problem of setting up all connection requests is known as Routing and Wavelength Assignment (RWA) problem. In this work, we suggest the use of computational swarm intelligent for solving the RWA problem. A new heuristic based on the law of gravity and mass interactions (Gravitational Search Algorithm, GSA) is chosen for this purpose, but adapted to a multiobjective context (MO-GSA). To test the performance of the MO-GSA, we have used a real-world topology, the Nippon Telegraph and Telephone (NTT, Japan) network and six sets of demands. After performing several comparisons with other approaches published in the literature, we can conclude that this algorithm outperforms the results obtained by other authors.
Dynamic Routing Exponent Strategies for Ant-based Protocols (Best Paper Nomination)
Rui Fang, Zequn Huang, Louis Rossi, Chien-Chung Shen
In ant-based routing protocols, the routing exponent controls how ants hop from node to node to discover routes based on pheromone values. It has been shown that stable multi-route solutions for small routing exponent values are dynamically connected to stable single-route solutions for large routing exponent values. These stable single-route solutions correspond to paths that have the smallest hop count. In this paper, we leverage this idea to improve the performance of ant-based routing protocols by dynamically adjusting the routing exponent. The results are validated via simulation.
A Population Based Incremental Learning for Delay Constrained Network Coding Resource Minimization
Huanlai Xing, Rong Qu
In network coding based multicast, coding operations are expected to be minimized as they not only incur additional computational cost at corresponding nodes in network but also increase data transmission delay. On the other hand, delay constraint must be concerned particularly in delay sensitive applications, e.g. video conferencing. In this paper, we study the problem of minimizing the amount of coding operations required while meeting the end-to-end delay constraint in network coding based multicast. A population based incremental learning (PBIL) algorithm is developed, where a group of best so far individuals, rather than a single one, is maintained and used to update the probability vector, which enhances the global search capability of the algorithm. Simulation results demonstrate the effectiveness of our PBIL.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
Extremal Optimization Applied to Task Scheduling of Distributed Java Programs
Eryk Laskowski, Marek Tudruj, Ivanoe De Falco, Umberto Scafuri, Ernesto Tarantino, Richard Olejnik
The paper presents new Java programs scheduling algorithms for execution on clusters of Java Virtual Machines (JVMs), which involve extremal optimization (EO) combined with task clustering. Two new scheduling algorithms are presented and compared. The first employs task clustering to reduce an initial program graph and then applies extremal optimization to schedule the reduced program graph to system resources. The second algorithm applies task clustering only to find an initial solution which is next improved by the EO algorithm working on the initial program graph. Both algorithms are also compared to an EO algorithm which does not use the clustering approach.
Data-Centered Scheduling for Addressing Performance Metrics on WSN
Lia Susana d.C. Silva-Lopez, Jonatan Gomez Perdomo
In this paper, a novel combination of cross-layer strategies for addressing timeliness, handle latency times on a data-centred way, and improve energy management in a non-mobile WSN scenario, is proposed. A set of performance metrics is also introduced. The metrics evaluate timeliness, latencies and energy management, and are used to compare the strategies with a combination of Periodic Scheduling and Simplified Forwarding. The WSN is modelled as an Asynchronous Cellular Automata with irregular neighbourhoods, and four states. Only information from local neighbourhood is needed for communication. Results show that the strategies are useful for sensing data accurately, without excessive oversampling.
[index]
evocomplex
Talks
Thursday 28 April 11:30-13:00, room 5: Eraclito, Session 1
Chair: Carlos Cotta
Evolving L-Systems as an intelligent design approach to find classes of difficult-to-solve Traveling Salesman Problem instances
Farhan Ahammed, Pablo Moscato
The technique of computationally analysing a program by searching for instances which causes the program to run in its worst-case time is examined. Concorde, the state-of-the-art Traveling Salesperson Problem (TSP) solver, is the program used to test our approach. We seed our evolutionary approach with a fractal instance of the TSP, defined by a Lindenmayer system at a fixed order. The evolutionary algorithm produced modifications to the L-System rules such that the instances of the modified L-System become increasingly much harder for Concorde to solve to optimality. In some cases, while still having the same size, the evolved instances required a computation time which was 30,000 times greater than what was needed to solve the original instance that seeded the search. The success of this case study shows the potential of Evolutionary Search to provide new test-case scenarios for algorithms and their software implementations.
On the design of Boolean network robots
Andrea Roli, Mattia Manfroni, Carlo Pinciroli, Mauro Birattari
Dynamical systems theory and complexity science provide powerful tools for analysing artificial agents and robots. Furthermore, they have been recently proposed also as a source of design principles and guidelines. Boolean networks are a prominent example of complex dynamical systems and they have been shown to effectively capture important phenomena in gene regulation. From an engineering perspective, these models are very compelling, because they can exhibit rich and complex behaviours, in spite of the compactness of their description. In this paper, we propose the use of Boolean networks for controlling robots’ behaviour. The network is designed by means of an automatic procedure based on stochastic local search techniques. We show that this approach makes it possible to design a network which enables the robot to accomplish a task that requires the capability of navigating the space using a light stimulus, as well as the formation and use of an internal memory.
A Study on the Mutation Rates of a Genetic Algorithm Interacting with a Sandpile
Carlos Fernandes, Juan Laredo, Antonio Mora, Agostinho Rosa, Juan Merelo
This paper investigates the mutation rates of a Genetic Algorithm (GA) with the sandpile mutation. This operator, which was specifically designed for non-stationary (or dynamic) optimization problems, relies on a Self-Organized Criticality system called sandpile to self-adapt the mutation intensity during the run. The behaviour of the operator depends on the state of the sandpile and on the fitness values of the population. Therefore, it has been argued that the mutation distribution may depend on to the severity and frequency of changes and on the type of stationary function that is chosen as a base-function for the dynamic problems. An experimental setup is proposed for investigating these issues. The results show that, at least under the proposed framework, a GA with the sandpile mutation self-adapts the mutation rates to the dynamics of the problem and to the characteristics of the base-function.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
A Design Framework for Ultra-Large-Scale Autonomic Systems
Michele Amoretti
The origins of ultra-large-scale (ULS) systems derive from social problems that are getting more and more complex, such as climatic monitoring, transportation, citizens protection and security. These factors imply a continuous increase of information systems that evolve towards ultra-dimension systems, requiring digital communication networks that allow for communication between people, between objects, and objects and people. The aim of this paper is to present novel approaches for the engineering of highly adaptive ULS systems, with the focus on computer-supported evolution, adaptable structure, emergent behaviors as well as advanced monitoring and control techniques. We illustrate the Networked Autonomic Machine (NAM), a framework for the characterization of the elements of self-*, highly dynamic ULS systems. Moreover, we recall the Adaptive Evolutionary Framework (AEF), for the implementation of distributed evolutionary strategies. Finally, we describe an example scenario of large peer-to-peer network under targeted attacks, showing the benefits of the NAM-AEF design.
Stochastic Local Search to Automatically Design Boolean Networks with Maximally Distant Attractors
Stefano Benedettini, Andrea Roli, Roberto Serra, Marco Villani
In this work we address the issue of designing a Boolean network such that its attractors are maximally distant. The design objective is converted into an optimisation problem, that is solved via an iterated local search algorithm. This technique proves to be effective and enables us to design networks with size up to 200 nodes. We also show that the networks obtained through the optimisation technique exhibit a mixture of characteristics typical of networks in the critical and chaotic dynamical regime.
[index]
evofin
Talks
Thursday 28 April 14:30-16:00, room 4: Mendel, Session 1
Chair: Anthony Brabazon
Learning and Predicting Financial Time Series by Combining Natural Computation and Agent Simulation
Filippo Neri
We investigate how, by combining natural computation and agent based simulation, it is possible to model financial time series. The agent based simulation can be used to functionally reproduce the structure of a financial market while the natural computation technique finds the most suitable parameter for the simulator. Our experimentation on the DJIA time series shows the effectiveness of this approach in modeling financial data. Also we compare the predictions made by our system to those obtained by other approaches.
Macro-Economic Time Series Modeling and Interaction Networks
Gabriel Kronberger, Stefan Fink, Michael Kommenda, Michael Affenzeller
Macro-economic models describe the dynamics of economic quantities. The estimations and forecasts produced by such models play a substantial role for financial and political decisions. In this contribution we describe an approach based on genetic programming and symbolic regression to identify variable interactions in large datasets. In the proposed approach multiple symbolic regression runs are executed for each variable of the dataset to find potentially interesting models. The result is a variable interaction network that describes which variables are most relevant for the approximation of each variable of the dataset. This approach is applied to a macro-economic dataset with monthly observations of important economic indicators in order to identify potentially interesting dependencies of these indicators. The resulting interaction network of macro-economic indicators is briefly discussed and two of the identified models are presented in detail. The two models approximate the help wanted index and the CPI inflation in the US.
Market Microstructure: Can Dinosaurs Return? A Self-Organizing Map Approach under an Evolutionary Framework
Michael Kampouridis, Shu-Heng Chen, Edward Tsang
This paper extends a previous market microstructure model, which investigated fraction dynamics of trading strategies. Our model consisted of two parts: Genetic Programming, which acted as an inference engine for trading rules, and Self-Organizing Maps (SOM), which was used for clustering the above rules into trading strategy types. However, for the purposes of the experiments of our previous work, we needed to make the assumption that SOM maps, and thus strategy types, remained the same over time. Nevertheless, this assumption could be considered as strict, and even unrealistic. In this paper, we relax this assumption. This offers a significant extension to our model, because it makes it more realistic. In addition, this extension allows us to investigate the dynamics of market behavior. We are interested in examining whether financial markets’ behavior is non-stationary, because this implies that strategies from the past cannot be applied to future time periods, unless they have co-evolved with the market. The results on an empirical financial market show that its behavior constantly changes; thus, agents’ strategies need to continuously adapt to the changes taking place in the market, in order to remain effective.
Thursday 28 April 16:20-17:50, room 4: Mendel, Session 2
Chair: Andrea Tettamanzi
A Preliminary Investigation of Overfitting in Evolutionary Driven Model Induction: Implications for Financial Modelling
Clíodhna Tuite, Alexandros Agapitos, Michael O’Neill, Anthony Brabazon
This paper investigates the effects of early stopping as a method to counteract overfitting in evolutionary data modelling using Genetic Programming. Early stopping has been proposed as a method to avoid model overtraining, which has been shown to lead to a significant degradation of out-of-sample performance. If we assume some sort of performance metric maximisation, the most widely used early training stopping criterion is the moment within the learning process that an unbiased estimate of the performance of the model begins to decrease after a strictly monotonic increase through the earlier learning iterations. We are conducting an initial investigation on the effects of early stopping in the performance of Genetic Programming in symbolic regression and financial modelling. Empirical results suggest that early stopping using the above criterion increases the extrapolation abilities of symbolic regression models, but is by no means the optimal training-stopping criterion in the case of a real-world financial dataset.
Using Evolutionary Neural Networks to Test the Influence of the Choice of Numeraire on Financial Time Series Modeling
Antonia Azzini, Mauro Dragoni, Andrea G.B. Tettamanzi
This work presents an evolutionary solution that aims to test the influence of the choice of numeraire on financial time series modeling. In particular, 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, to a couple of very liquid financial time series expressed in their trading currency and several alternative numeraires like gold, silver, and a currency like the euro, which is intended to be stable `by design’, and compare the results.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
On the Performance and Convergence Properties of Hybrid Intelligent Schemes:Application on Portfolio Optimization Domain
Vassilios Vassiliadis, Nikolaos Thomaidis, George Dounias
Hybrid intelligent algorithms, especially those who combine nature-inspired techniques, are well known for their searching abilities in complex problem domains and their performance. One of their main characteristic is that they manage to escape getting trapped in local optima. In this study, two hybrid intelligent schemes are compared both in terms of performance and convergence ability in a complex financial problem. Particularly, both algorithms use a type of genetic algorithm for asset selection and they differ on the technique applied for weight optimization: the first hybrid uses a numerical function optimization method, while the second one uses a continuous ant colony optimization algorithm. Results indicate that there is great potential in combining characteristics of nature-inspired algorithms in order to solve NP-hard optimization problems.
[index]
evogames
Talks
Wednesday 27 April 11:30-13:00, room 4: Mendel, Board Games
Chair: Mike Preuss
Improving and Scaling Evolutionary Approaches to the MasterMind Problem
Juan-Julian Merelo, Carlos Cotta, Antonio-M. Mora
Mastermind is a well-known board game in which one player must discover a hidden combination of colored pegs set up by an opponent, using the hints that the latter provides (the number of places –or pegs– correctly guessed, and the number of colors rightly guessed but out of place) in each move. The feasibility of evolutionary approaches to solve this problem has been already proved; in this paper we will assess different methods to improve the time it takes to find a solution by introducing endgames, that is, shortcuts for finding the solution when certain circumstances arise. Besides, we will measure the scalability of the evolutionary approaches by solving generalized Mastermind instances in several sizes. Tests show that endgames improve the average number of solutions without any influence on the quality of the game; at the same time, it speeds up solutions so that bigger problems can be approached. Tests performed with eight colors and four or five pegs and nine colors with five pegs show that scaling is quite good, and that the methodology yields an average number of games that is competitive with the best solutions published so far. Scaling with problem size depends on the method, being better for entropy-based solutions, but –besides raw problem size– there are complex dependencies on the number of pegs and colors.
Nested Look-Ahead Evolutionary Algorithm Based Planning for a Believable Diplomacy Bot
Markus Kemmerling, Niels Ackermann, Mike Preuss
With regard to literature, improved estimations for the number of possible moves and placements are provided, showing that the complexity of Diplomacy is enormous, making it a good candidate for machine learning and evolutionary learning techniques. To enhance the playing strength of an existing Diplomacy bot and alleviate the distance to the presumed best current bot, a look-ahead planning component based on nested evolutionary algorithms, is then implanted into an already existing bot. The experimental investigation shows that the resulting bot is significantly improved.
Wednesday 27 April 14:30-16:00, room 4: Mendel, Game Applications
Chair: Julian Togelius
Evolving Interesting Maps for a First Person Shooter
Luigi Cardamone, Georgios N. Yannakakis, Julian Togelius, Pier Luca Lanzi
We address the problem of automatically designing maps for first-person shooter (FPS) games. An efficient solution to this procedural content generation (PCG) problem could allow the design of FPS games of lower development cost with near-infinite replay value and capability to adapt to the skills and preferences of individual players. We propose a search-based solution, where maps are evolved to optimize a fitness function that is based on the players’ average fighting time. For that purpose, four different map representations are tested and compared. Results obtained showcase the clear advantage of some representations in generating interesting FPS maps and demonstrate the promise of the approach followed for automatic level design in that game genre.
Driving Faster Than a Human Player
Jan Quadflieg, Mike Preuss, Guenter Rudolph
TORCS car racing bots have improved significantly in the last years. We show that accurate curvature information for the upcoming corners enables offline learning a near-optimal driving style that consistently beats an expert human player (and the fastest currently known bots). Generalization to other tracks often, but not always succeeds, so that the method is extended by an online error correction mechanism well suited to the warmup phase of the Simulated Car Racing Championships.
Learning Chasing Behaviours of Non-Player Characters in Games using SARSA
Somnuk Phon-Amnuaisuk
In this paper, we investigate the application of reinforcement learning in the learning of chasing behaviours of non-player characters (NPCs). One popular method for encoding intelligent behaviours in game is by scripting where the behaviours on the scene are predetermined. Many popular games have their game intelligence encoded in this manner. The application of machine learning techniques to learn non-player character behaviours is still being explored by game AI researchers. The application of machine learning in games could enhance game playing experience. In this report, we investigate the design and implementation of reinforcement learning to learn the chasing behaviours of NPCs. The design and the simulation results are discussed and further work in this area is suggested.
Wednesday 27 April 16:20-17:00, room 4: Mendel, Best Paper Nominations
Chair: Mike Preuss
Towards Procedural Strategy Game Generation: Evolving Complementary Unit Types
Tobias Mahlmann, Julian Togelius, Georgios N. Yannakakis
The Strategy Game Description Game Language (SGDL) is intended to become a complete description of all aspects of strategy games, including rules, parameters, scenarios, maps, and unit types. One of the main envisioned uses of SGDL, in combination with an evolutionary algorithm and appropriate fitness functions, is to allow the generation of complete new strategy games or variations of old ones. This paper presents a first version of SGDL, capable of describing unit types and their properties, together with plans for how it will be extended to other sub-domains of strategy games. As a proof of the viability of the idea and implementation, an experiment is presented where unit types are evolved so as to generate complementary properties. A fitness function based on Monte Carlo simulation of gameplay is devised to test complementarity.
Training Neural Networks to Play Backgammon Variants Using Reinforcement Learning
Nikolaos Papahristou, Ioannis Refanidis
Backgammon is a board game that has been studied considerably by computer scientists. Apart from standard backgammon, several yet unexplored variants of the game exist, which use the same board, number of checkers, and dice but may have different rules for moving the checkers, starting positions and movement direction. This paper studies two popular variants in Greece and neighboring countries, named Fevga and Plakoto. Using reinforcement learning and Neural Network function approximation we train agents that learn a game position evaluation function for these games. We show that the resulting agents significantly outperform the open-source program Tavli3D.
Evolving Behavior Trees for the Mario AI Competition Using Grammatical Evolution
Diego Perez, Miguel Nicolau, Michael O’Neill, Anthony Brabazon
This paper investigates the applicability of Genetic Programming type systems to dynamic game environments. Grammatical Evolution was used to evolved Behaviour Trees, in order to create controllers for the Mario AI Benchmark. The results obtained reinforce the applicability of evolutionary programming systems to the development of artificial intelligence in games, and in dynamic systems in general, illustrating their viability as an alternative to more standard AI techniques.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
Revisiting Monte-Carlo Tree Search on a Normal Form Game: NoGo
C.-W. Chou, O. Teytaud, S.-J. Yen
We revisit Monte-Carlo Tree Search on a recent game, termed NoGo. Our goal is to check if known results in Computer-Go and various other games are general enough for being applied directly on a new game. We also test if the known limitations of Monte-Carlo Tree Search also hold in this case and which improvements of Monte-Carlo Tree Search are necessary for good performance and which have a minor effect. We also tested a generic Monte-Carlo simulator, designed for “no more moves” games.
Upper Confidence Trees with Short Term Partial Information
Olivier Teytaud, Sebastien Flory
We show some mathematical links between partially observable (PO) games in which information is regularly revealed, and simultaneous actions games. Using this, we study the extension of Monte-Carlo Tree Search algorithms to PO games and to games with simultaneous actions. We apply the results to Urban Rivals, a free PO internet card game with more than 10 millions of registered users.
Multiple Tree for Partially Observable Monte-Carlo Tree Search
David Auger
We propose an algorithm for computing approximate Nash equilibria of partially observable games using Monte-Carlo tree search based on recent bandit methods. We obtain experimental results for the game of phantom tic-tac-toe, showing that strong strategies can be efficiently computed by our algorithm.
[index]
evohot
Talks
Thursday 28 April 09:30-11:00, room 5: Eraclito, Session 1
Chair: Ernesto Tarantino
Improving ESOP-based Synthesis of Reversible Logic Using Evolutionary Algorithms
Rolf Drechsler, Alexander Finder, Robert Wille
Reversible circuits, i.e. circuits which map each possible input vector to a unique output vector, build the basis for emerging applications e.g. in the domain of low-power design or quantum computation. As a result, researchers developed various approaches for synthesis of this kind of logic. In this paper, we consider the ESOP-based synthesis method. Here, functions given as Exclusive Sum of Products (ESOPs) are realized. In contrast to conventional circuit optimization, the quality of the resulting circuits depends thereby not only on the number of product terms, but on further criteria as well. In this paper, we present an approach based on an evolutionary algorithm which optimizes the function description with respect to these criteria. Instead of ESOPs,Pseudo Kronecker Expression (PSDKRO) are thereby utilized enabling minimization within reasonable time bounds. Experimental results confirm that the proposed approach enables the realization of circuits with significantly less cost.
Genetic Defect Based March Test Generation for SRAM
Stefano Di Carlo, Gianfranco Politano, Paolo Prinetto, Alessandro Savino, Alberto Scionti
The continuos shrinking of semiconductor’s nodes makes semiconductor memories increasingly prone to electrical defects tightly related to the internal structure of the memory. Exploring the effect of fabrication defects in future technologies, and identifying new classes of functional fault models with their corresponding test sequences, is a time consuming task up to now mainly performed by hand. This paper proposes a new approach to automate this procedure exploiting a dedicated genetic algorithm.
Enhanced Reverse Engineering using Genetic-Algorithms-based Experimental Parallel Workflow for Optimum Design
Damir Vucina, Igor Pehnec
Shape optimization is numerically very intensive due to multidisciplinary objectives and constraints, many shape variables, non linear models, geometric infeasibility of candidate designs, etc. It involves participation of numerical optimizers, computer- aided geometric modelers and subject-related simulators as well as their coupling at the process- and data levels. This paper develops a simple experimental workflow which employs existing commercial software for computer-aided design, finite element analysis and evolutionary optimization modules. It sets up parallel execution of multiple simulators to reduce the execution time, which is implemented inexpensively by means of a self-made .net- based cluster. Shape optimization is introduced in the generic context of ‘enhanced’ reverse engineering with optimization whereby the initial solution can be obtained by 3D optical scanning and parameterization of an existing solution.
[index]
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
Evolution of Test Programs Exploiting a FSM Processor Model
Ernesto Sanchez, Giovanni Squillero, Alberto Tonda
Microprocessor testing is becoming a challenging task, due to the increasing complexity of modern architectures. Nowadays, most architectures are tackled with a combination of scan chains and Software-Based Self-Test (SBST) methodologies. Among SBST techniques, evolutionary feedback-based ones prove effective in microprocessor testing: their main disadvantage, however, is the considerable time required to generate suitable test programs. A novel evolutionary-based approach, able to appreciably reduce the generation time, is presented. The proposed method exploits a high-level representation of the architecture under test and a dynamically built Finite State Machine (FSM) model to assess fault coverage without resorting to time-expensive simulations on low-level models. Experimental results, performed on an OpenRISC processor, show that the resulting test obtains a nearly complete fault coverage against the targeted fault model.
Fault-Tolerance Simulation of Brushless Motor Control Circuits
Huicong Wu, Jie Chu, Liang Yuan, Qiang Zhao, Shanghe Liu
Brushless Motors are frequently employed in control systems. The reliability of the brushless motor control circuits is highly critical especially in harsh environments. This paper presents an Evolvable Hardware platform for automated design and adaptation of a brushless motors control circuit. The platform uses the principles of EHW to automate the configuration of FPGA dedicated to the implementation of the motor control circuit. The ability of the platform to adapt to a certain number of faults was investigated through introducing single logic unit faults and multi logic units faults. Results show that the functionality of the motor control circuit can be recovered through evolution. They also show that the location of faulty logic units can affect the ability of the evolutionary algorithm to evolve correct circuits, and the evolutionary recovery ability of the circuit decreases as the number of fault logic units is increasing.
evoiasp
Talks
Thursday 28 April 09:30-11:00, room 4: Mendel, Session 1
Chair: Stefano Cagnoni
A Hybrid Particle Swarm Optimisation with Differential Evolution Approach to Image Segmentation
Wenlong Fu, Mark Johnston, Mengjie Zhang
Image segmentation is a key step in image analysis and many image segmentation methods are time-consuming. The Otsu method and Gaussian Mixture Model (GMM) method are popular in image segmentation, but it is computationally difficult to find their globally optimal threshold values. Particle Swarm Optimisation (PSO) is an intelligent search method and has been widely used in many fields. However it is also easily trapped in local optima. In this paper, we propose a hybrid between PSO and Differential Evolution (DE) to solve the optimisation problems associated with the Otsu model and GMM, and apply these methods to natural image segmentation. The hybrid PSO-DE method is compared with an exhaustive method for the Otsu model, and fitted GMMs are compared directly with image histograms. Hybrid PSO-DE is also compared with standard PSO on these models. The experimental results show that the hybrid PSO-DE approach to image segmentation is effective and efficient.
Evolutionary Synthesis of a Trajectory Integrator for an Analogue Brain-Computer Interface Mouse
Riccardo Poli, Mathew Salvaris, Caterina Cinel
Recently significant steps have been made towards effective EEG-based brain-computer interfaces for mouse control. A major obstacle in this line of research, however, is the integration of the noisy and contradictory information provided at each time step by the signal processing systems into a coherent and precise trajectory for the mouse pointer. In this paper we attack this difficult problem using genetic programming, obtaining extremely promising results.
Transparent, Online Image Pattern Classification Using a Learning Classifier System
Ignas Kukenys, Will Browne, Mengjie Zhang
Image pattern classification in computer vision problems is challenging due to large, sparse input spaces with the added demand for generalisation and accuracy of results. The Evolutionary Computation technique of Learning Classifier Systems (LCS) addresses such problems, but has not been applied previously to this domain. Instead, online, supervised techniques on fixed data sets have been shown to be highly accurate. This paper shows that LCS enable online, reinforcement learning on datasets that may change over time and produce transparent (human readable) classification rules. Further work is needed in domains applicable to online, supervised learning to achieve benchmark accuracy, but the promising initial results auger well for domains, such as mobile robotics, where compact, accurate and general rules learnt in a graceful manner are required
Thursday 28 April 11:30-13:00, room 4: Mendel, Session 2
Chair: Mengjie Zhang
Automatic Selection of Pareto-optimal Topologies of Hidden Markov Models using Multicriteria Evolutionary Algorithms
Pawel Swietojanski, Robert Wielgat, Tomasz Zielinski
In this paper a novel approach of automatic selection of Hidden Markov Models (HMM) structures under Pareto-optimality criteria is presented. Proof of concept is delivered in automatic speech recognition (ASR) discipline where two research scenarios including recognition of speech disorders as well as classi
cation of bird species using their voice are performed. The conducted research unveiled that the Pareto Optimal Hidden Markov Models (POHMM) topologies outperformed both manual structures selection based on theoretical prejudices as well as the automatic approaches that used a single objective only.
Advanced Metaheuristic Approaches and Population Doping for a Novel Modeling-Based Method of Positron Emission Tomography Data Analysis
Jarkko Pekkarinen, Harri Pölönen, Ferrante Neri
This paper proposes a metaheuristic approach to solve a complex large scale optimization problem that originates from a recently introduced Positron Emission Tomography (PET) data analysis method that provides an estimate of tissue heterogeneity. More specifically three modern metaheuristics have been tested. These metaheustics are based on Differential Evolution, Particle Swarm Optimization, and Memetic Computing. On the basis of a preliminary analysis of the fitness landscape, an intelligent initialization technique has been proposed in this paper. More specifically, since the fitness landscape appears to have a strong basin of attraction containing a multimodal landscape, a local search method is applied to one solution at the beginning of the optimization process and inserted into a randomly generated population. The resulting “doped” population is then processed by the metaheuristics. Numerical results show that the application of the local search at the beginning of the optimization process leads to significant benefits in terms of algorithmic performance. Among the metaheuristics analyzed in this study, the DE based algorithm appears to display the best performance.
Segmentation of ultrasound breast images: optimization of algorithm parameters
Leonardo Bocchi, Francesco Rogai
Segmentation of lesions in ultrasound imaging is one of the key issues in the development of Computer Aided Diagnosis systems. This paper presents a hybrid solution to the segmentation problem. A linear filter composed of a Gaussian and a Laplacian of Gaussian filter is used to smooth the image, before applying a dynamic threshold to extract a rough segmentation. In parallel, a despeckle filter based on a Cellular Automata (CA) is used to remove noise. Then, an accurate segmentation is obtained applying the GrowCut algorithm, initialized from the rough segmentation, to the CA-filtered image. The algorithm requires tuning of several parameters, which proved difficult to obtain by hand. Thus, a Genetic Algorithm has been used to find the optimal parameter set. The fitness of the algorithm has been derived from the segmentation error obtained comparing the automatic segmentation with a manual one. Results indicate that using the GA-optimized parameters, the average segmentation error decreases from 5.75% obtained by manual tuning to 1.5% with GA-optimized parameters.
Tracking Multiple Targets with Adaptive Swarm Optimization
Jun Liu, Hongbin Ma, Xuemei Ren
This paper mainly concentrates on the problem of tracking multiple targets in the noisy environment. To better recognize the eccentric target in a specific environment, one proposed objective function gets the target’s shape in the subgraph. Inspired by particle swarm optimization, the proposed algorithm of tracking multiple targets adaptively modifies the covered radii of each subgroup in terms of the minimum distances among the subgroups, and successfully tracks the conflicting targets. The theoretic results as well as the experiments on tracking multiple ants indicate that this efficient method has successfully been applied to the complex and changing practical systems.
[index]
evointelligence
Talks
Wednesday 27 April 14:30-16:00, room 3: Leonardo, presented during the second session of evonum
When Novelty is Not Enough
Giuseppe Cuccu, Faustino Gomez
The idea of evolving novel rather than fit solutions has recently been offered as a way to automatically discover the kind of complex
solutions that exhibit truly intelligent behavior. So far, novelty search has only been studied in the context of problems where the number of possible “different” solutions has been limited. In this paper, we show, using a task with a much larger solution space, that selecting for novelty alone does not offer an advantage over fitness-based selection. In addition, we examine how the idea of novelty search can be used to sustain diversity and improve the performance of standard, fitness-based search.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
A Part-Of-Speech Lexicographic Encoding for an Evolutionary Word Sense Disambiguation Approach
Antonia Azzini, Mauro Dragoni, Andrea G.B. Tettamanzi
This work proposes a novel distributed scheme based on a part-of-speech tagged lexicographic encoding to represent the context in which a particular word occurs in an evolutionary approach for word sense disambiguation. Tagged dataset for every sense of a polysemous word are considered as inputs to supervised classifiers, Artificial Neural Networks (ANNs), which are evolved by a joint optimization of their structures and weights, together with a similarity based recombination operator. The viability of the approach has been demonstrated through experiments carried out on a representative set of polysemous words. Comparison with the best entries of the Semeval-2007 competition has shown that the proposed approach is competitive with state-of-the-art WSD approaches.
Migrating Birds Optimization: A New Meta-heuristic Approach and Its Application to the Quadratic Assignment Problem
Ekrem Duman, Mitat Uysal, Ali Fuat Alkaya
In this study we propose a new nature inspired metaheuristic approach based on the V formation flight of the migrating birds which is proven to be an effective formation in energy minimization. Its performance is tested on quadratic assignment problem instances arising from a real life problem and very good results are obtained. The quality of the solutions turned out to be better than simulated annealing, tabu search and guided evolutionary simulated annealing approaches. These results indicate that our new metaheuristic approach could be an important player in metaheuristic based optimization.
[index]
evomusart
Talks
Thursday 28 April 09:30-11:00, room 6: Copernico, Music
Chair: Juan Romero
Parallel Evolutionary Optimization of Digital Sound Synthesis Parameters
Batuhan Bozkurt, Kamer Ali Yuksel
In this research, we propose a novel parallelizable architecture for the optimization of various sound synthesis parameters. The architecture employs genetic algorithms to match the parameters of different sound synthesizer topologies to target sounds. The fitness function is evaluated in parallel to decrease its convergence time. Based on the proposed architecture, we have implemented a framework using the SuperCollider audio synthesis and programming environment and conducted several experiments. The results of the experiments have shown that the framework can be utilized for accurate estimation of the sound synthesis parameters at promising speeds.
Weighted Markov Chain Model for Musical Composer Identification
Maximos A. Kaliakatsos-Papakostas, Michael G. Epitropakis, Michael N. Vrahatis
Several approaches based on the ‘Markov chain model’ have been proposed to tackle the composer identification task. In the paper at hand, we propose to capture phrasing structural information from inter onset and pitch intervals of pairs of consecutive notes in a musical piece, by incorporating this information into a weighted variation of a first order Markov chain model. Additionally, we propose an evolutionary procedure that automatically tunes the introduced weights and exploits the full potential of the proposed model for tackling the composer identification task between two composers. Initial experimental results on string quartets of Haydn, Mozart and Beethoven suggest that the proposed model performs well and can provide insights on the inter onset and pitch intervals on the considered musical collection.
SANTIAGO – A Real-time Biological Neural Network Environment for Generative Music Creation (Best Paper Nomination)
Hernán Kerlleñevich, Pablo Ernesto Riera, Manuel Camilo Eguía
In this work we present a novel approach for interactive music generation based on the dynamics of biological neural networks. We develop SANTIAGO, a real-time environment built in Pd-Gem, which allows to assemble networks of realistic neuron models and map the activity of individual neurons to sound events (notes) and to modulations of the sound event parameters (duration, pitch, intensity, spectral content). The rich behavior exhibited by this type of networks gives rise to complex rhythmic patterns, melodies and textures that are neither too random nor too uniform, and that can be modified by the user in an interactive way.
Thursday 28 April 11:30-13:00, room 6: Copernico, Architecture and Insdtallation
Chair: Juan Romero
Evolution of Architectural Floor Plans
Robert Flack, Brian Ross
Layout planning is a process of sizing and placing rooms (e.g. in a house) while attempting to optimize various criteria. Often there are conflicting criteria such as construction cost, minimizing the distance between related activities, and meeting the area requirements for these activities. This paper describes new techniques for automating the layout planning process using evolutionary computation. New innovations include allowing polygonal exteriors and multiple floors. Multi-objective ranking algorithms are tested to balance the many objectives in this problem. The evolutionary representation and requirements specification used provide great flexibility in problem scope and depth of problems to be considered. A variety of pleasing plans have been evolved with the approach.
Combining Structural Analysis and Multi-Objective Criteria for Evolutionary Architectural Design (Best Paper Nomination)
Jonathan Byrne, Michael Fenton, Erik Hemberg, James McDermott, Michael O’Neill, Elizabeth Shotton, Ciaran Nally
This study evolves and categorises a population of conceptual designs by their ability to handle physical constraints. The design process involves a trade-off between form and function. The aesthetic considerations of the designer are constrained by physical considerations and material cost. In previous work, we developed a design grammar capable of evolving aesthetically pleasing designs through the use of an interactive evolutionary algorithm. This work implements a fitness function capable of applying engineering objectives to automatically evaluate designs and, in turn, reduce the search space that is presented to the user.
Path of Patches: Implementing an Evolutionary Soundscape Art Installation
José Fornari
Computational adaptive methods have already been used in Installation art. Among them, Generative artworks are those that value the artistic process, rather than its final product, which can now be of multimodal nature. Evolutionary Algorithms (EA) can be successfully applied to create a Generative art process that is self-similar yet always new. EAs allow the creation of dynamic complex systems from which identity can emerge. In computational sonic arts, this is ecological modeling; here named Evolutionary Soundscape. This article describes the development and application of an EA computing system developed to generate Evolutionary Soundscapes in a Multimodal Art Installation. Its physical structure uses paths of forking pipes attached to fans and microphones that capture audio to feed the EA system that creates the Soundscape. Here is described the EA system; its design in PureData (PD); its connection with the physical structure; its artistic endeavor and final sonic accomplishments.
Thursday 28 April 14:30-16:00, room 6: Copernico, Aesthetics
Chair: Gary Greenfield
Evolving Art using multiple Aesthetic Measures
E. den Heijer, A.E. Eiben
In this paper we investigate the applicability of Multi-Objective Optimization (MOO) in Evolutionary Art. We evolve images using an unsupervised evolutionary algorithm and we use two aesthetic measures as fitness functions concurrently. We use three different pairs from a set of three aesthetic measures and we compare the output of each pair to the output of other pairs, and to the output of experiments with a single aesthetic measure (non-MOO). We investigate 1) whether properties of aesthetic measures can be combined using MOO and 2) whether the use of MOO in evolutionary art results in different images, or perhaps “better” images. All images in this paper can be viewed in colour at http://www.few.vu.nl/~eelco/
Using Grammatical Evolution to Parameterise Interactive 3D Image Generation (Best Paper Nomination)
Miguel Nicolau, Dan Costelloe
This paper describes an Interactive Evolutionary system for generating pleasing 3D images using a combination of Grammatical Evolution and Jenn3d, a freely available visualiser of Cayley graphs of finite Coxeter groups. Using interactive GE with some novel enhancements, the parameter space of the Jenn3d image-generating system is navigated by the user, permitting the creation of realistic, unique and award winning images in just a few generations. One of the evolved images has been selected to illustrate the proceedings of the EvoStar conference in 2011.
Modelling human preference in evolutionary art (Best Paper Nomination)
Aniko Ekart, Divya Sharma, Stayko Chalakov
Creative activities including arts are characteristic to humankind. Our understanding of creativity is limited, yet there is substantial research trying to mimic human creativity in artificial systems and in particular to produce systems that automatically evolve art appreciated by humans. We propose here to model human visual preference by a set of aesthetic measures identified through observation of human selection of images and then use these for automatic evolution of aesthetic images.
Thursday 28 April 16:20-17:50, room 6: Copernico, Generative Techniques
Chair: Gary Greenfield
Generative art inspired by nature, using NodeBox
Tom De Smedt, Ludivine Lechat, Walter Daelemans
NodeBox is a free application for producing generative art. This paper gives an overview of the nature-inspired functionality in NodeBox and the artworks we created using it. We demonstrate how it can be used for evolutionary computation in the context of computer games and art, and discuss some of our recent research with the aim to simulate (artistic) brainstorming using language processing techniques and semantic networks.
The T. albipennis Sand Painting Artists
Paulo Urbano
In recent years, we have seen some artificial artistic work that has drawn inspiration from swarm societies, in particular ant societies. Ant paintings are abstract images corresponding to visualizations of the paths made by a group of virtual ants on a bi-dimensional space. The research on ant paintings has been focused around a stigmergic mechanism of interaction: the deposition of pheromones, largely used by ants. In an effort to further on the research on ant inspired artificial art, we introduce the T. albipennis sand painting artists, which draw direct inspiration from the ant species Temnothorax albipennis (formerly tuberointerruptus). These ants build simple circular walls, composed of grains of sand or fragments of stones, at a given distance from the central cluster of adult ants and brood. The brood and ants cluster function as a template, which combined with self-organization are responsible for the particular wall pattern formation. The T. albipennis artists are artificial two-dimensional builders, starting from unorganized placement of virtual sand grains, they rearrange them, creating some interesting patterns composed of scattered pointillistic and imperfect circles, a colored moon-like landscape full of craters.
Creating Choreography with Interactive Evolutionary Algorithms
Jonathan Eisenmann, Benjamin Schroeder, Matthew Lewis, Rick Parent
Directing a group behavior towards interesting and complex motion can and should be intuitive, iterative, and often participatory. Toward this end, we present a choreographic system that enables designers to explore a motion space based on a parametric model of behaviors. Designers may work with the system by moving back and forth through two complementary stages: first, using an evolutionary algorithm to traverse the space of behavior possibilities, allowing designers to emphasize desired kinds of motion while leaving room for an element of the unexpected, and second, using selected behaviors to direct the group motion of simple performing creatures. In the second stage, evolved group motion behaviors from the first stage are used alongside existing high-level parametric rules for local articulated motion.
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
Music Translation of Tertiary Protein Structure: Auditory Patterns of the Protein Folding
Riccardo Castagna, Alessandro Chiolerio, Valentina Margaria
We have translated genome-encoded protein sequence into musical notes and created a polyphonic harmony taking in account its tertiary structure. We did not use a diatonic musical scale to obtain a pleasant sound, focusing instead on the spatial relationship between aminoacids closely placed in the 3-dimensional protein folding. In this way, the result is a musical translation of the real morphology of the protein, that opens the challenge to bring musical harmony rules into the proteomic research field.
Ludic Considerations of Tablet-Based Evo-Art
Simon Colton, Michael Cook, Azalea Raad
With the introduction of the iPad and similar devices, there is a unique opportunity to build tablet-based evolutionary art software for general consumption, and we describe here the i-ELVIRA iPad ap- plication for such purposes. To increase the ludic enjoyment users have with i-ELVIRA, we designed a GUI which gives the user a higher level of control and more efficient feedback than usual for desktop evo-art software. This relies on the efficient delivery of crossover and mutation images which bear an appropriate amount of resemblance to their parent(s). This requirement in turn led to technical difficulties which we resolved via the implementation and experimentation described here.
A Genetic Algorithm for Dodecaphonic Compositions
Roberto De Prisco, Gianluca Zaccagnino, Rocco Zaccagnino
In this paper we propose an automatic music composition system for dodecaphonic music based on a genetic algorithm. Dodecaphonic music, introduced by A. Schoenberg, departs from the concept of tonality by considering all 12 notes equally important. Dodecaphonic compositions are constructed starting from a 12-note series, which is a sequence of all the 12 notes; the compositional process uses the starting 12-note series as a seed and builds the music creating new fragments of music obtained by transforming the seed series. The algorithm proposed in this paper automates the compositional process taking a seed series as input and automatically creating a dodecaphonic composition. We have implemented the algorithm and we have run several tests to study its behaviour.
A Customizable Recognizer for Orchestral Conducting Gestures based on Neural Networks
Roberto De Prisco, Paolo Sabatino, ianluca Zaccagnino, Rocco Zaccagnino
In this paper we present a system for the recognition of orchestral conducting gestures using the Nintendo Wiimote controller. The system is based on a neural network. This is not the first of such systems; however compared to previous systems that use the Wiimote or other cheap hardware, it has several advantages: it is fully customizable, continuous and does not require third party commercial software. The system has been implemented in Java and we have run several tests to evaluate its behavior.
Evolving Four-Part Harmony Using Genetic Algorithms
Patrick Donnelly, John Sheppard
This paper presents a genetic algorithm that evolves a four-part musical composition-melodically, harmonically, and rhythmically. Unlike similar attempts in the literature, our composition evolves from a single musical chord without human intervention or initial musical material. The mutation rules and fitness evaluation are based on common rules from music theory. The genetic operators and individual mutation rules are selected from probability distributions that evolve alongside the musical material.
A Sonic Eco-system of Self-Organising Musical Agents
Arne Eigenfeldt, Philippe Pasquier
We present a population of autonomous agents that exist within a sonic eco-system derived from real-time analysis of live audio. In this system, entitled Coming Together: Shoals, agents search for food consisting of CataRT unit analyses, which, when found, are consumed through granulation. Individual agents are initialised with random synthesis parameters, but communicate these parameters to agents in local neighborhoods. Agents form social networks, and converge their parameters within these networks, thereby creating unified grain streams. Separate gestures thus emerge through the self-organisation of the population.
Neurogranular Synthesis: Granular Synthesis Controlled by a Pulse-coupled Network of Spiking Neurons
James Kevin McCracken, John Matthias
We introduce a method of generating grain parameters of a granular synthesiser in real-time by using a network of artificial spiking neurons, the behaviour of which is determined by user-control of a small number of network parameters; ‘Neurogranular synthesis’. The artificial network can exhibit a wide variety of behaviour from loosely correlated to highly synchronised, which can produce interesting sonic results, particularly with regard to rhythmic textures.
Interactive Biomimetic Space: An Interactive Installation to Explore Living Architecture
Liraz Mor, Chao Liu, Sebastian von Mammen
This paper describes a computer-based Interactive Biomimetic Space (IBS) installation. Through an interactive process, a user creates and relates new spaces. The simulation of a simplified ecosystem populates the created space with life. The installation attempts to inspire architectural design ideas by integrating biological principles. In particular, the biological concepts of stochastic motion, interaction and reproduction of artificial swarms have been explored and applied. Both the user and the swarm agents contribute to the design process, which results in interesting design outputs with a certain degree of unpredictability. We introduce the theoretical background of our work, outline its technical implementation, and present various interaction examples and scenarios.
Evolving Textures from High Level Descriptions: Gray with an Accent Color
Craig Reynolds
This paper describes a prototype evolutionary texture synthesis tool meant to assist a designer or artist by automatically discovering many candidate textures that fit a given stylistic description. The textures used here are small color images, created by procedural texture synthesis. This prototype uses a single stylistic description: a textured gray image with a small amount of color accent. A hand-written prototype fitness function rates how well an image meets this description. Genetic programming uses the fitness function to evolve programs written in a texture synthesis language. A tool like this can automatically generate a catalog of variations on the given theme. A designer could then scan through these to pick out those that seem aesthetically interesting. Their procedural “genetic” representation would allow them to be further adjusted by interactive evolution. It also allows re-rendering them at arbitrary resolutions and provides a way to store them in a highly compressed form allowing lossless reconstruction.
Aesthetic Classification and Sorting Based on Image Compression
Juan Romero, Penousal Machado, Adrian Carballal, Olga Osorio
One of the problems in evolutionary art is the lack of robust fitness functions. This work explores the use of image compression estimates to predict the aesthetic merit of images. The metrics proposed estimate the complexity of an image by means of JPEG and Fractal compression. The success rate achieved is 72.43% in aesthetic classification tasks of a problem belonging to the state of the art. Finally, the behavior of the system is shown in an image sorting task based on aesthetic criteria.
iSoundScape: Adaptive Walk on a Fitness Soundscape
Reiji Suzuki, Souichiro Yamaguchi, Martin Cody, Charles Taylor, Takaya Arita
Adaptive walk on a fitness soundscape is a new kind of interactive evolutionary computation for musical works. This system provides a virtual two-dimensional grid called a “soundscape” in which each point corresponds to a genotype that generates a sound environment. By using the human abilities of localization and selective listening, the user can “walk” toward genotypes that generate more favorable sounds. This corresponds to a hill-climbing process on the “fitness soundscape.” This environment can be realized by multiple speakers or a headphone creating “surround sound.” In this work we describe two new applications of adaptive walk. The first is developed for creating spatially grounded musical pieces as an interactive art based on fitness soundscapes. The second provides a new way to explore the ecology and evolution of bird songs, from scientific and educational viewpoints, by exploring the ecological space of “nature’s music”, produced by populations of virtual songbirds.
Merging Aesthetics with Functionality: An Interactive Genetic Algorithm Based on the Principle of Weighted Mutation
Eirini Vouliouri
This paper proposes an algorithm through which the development of computationally generated forms can be externally directed towards both functional objectives and intuitive design targets. More precisely, it presents a special version of Interactive Genetic Algorithm, which introduces Weighted Mutation as a method to support the long life of genes corresponding to favored phenotypic characteristics. At the same time, optimization processes towards operational goals are also enabled. A set of experiments is conducted on the case study of a building facade, which appears to provide a suitable means for the investigation of functional, as well as aesthetic issues. The results are positively assessed, since they prove that this new methodology broadens the capacities of standard Interactive Genetic Algorithms, shedding light on how a constructive human-machine relationship can benefit the design process.
[index]
evonum
Talks
Wednesday 27 April 11:30-13:00, room 3: Leonardo, Session 1
Chair: Anna I Esparcia-Alcazar
Opposition-Based Learning in Compact Differential Evolution
Giovanni Iacca, Ferrante Neri, Ernesto Mininno
This paper proposes the integration of the generalized opposition based learning into compact Differential Evolution frameworks and tests its impact on the algorithmic performance. Opposition-based learning is a technique which has been applied, in several circumstances, to enhance the performance of Differential Evolution. It consists of the generation of additional points by means of a hyper-rectangle. These opposition points are simply generated by making use of a central symmetry within the hyper-rectangle. In the population based Differential Evolution, the inclusion of this search move corrects a limitation of the original algorithm, i.e. the scarcity of search moves, and sometimes leads to benefits in terms of algorithmic performance. The opposition-based learning scheme is further improved in the generalized scheme by integrating some randomness and progressive narrowing of the search. The proposed study shows how the generalized opposition-based learning can be encoded within a compact Differential Evolution framework and displays its effect on a set of diverse problems. Numerical results show that the generalized opposition-based learning is beneficial for compact Differential Evolution employing the binomial crossover while its implementation is not always successful when the exponential crossover is used. In particular, the opposition-based logic appears to be in general promising for non-separable problems whilst it seems detrimental for separable problems.
Data Mining using Unguided Symbolic Regression on a Blast Furnace Dataset
Michael Kommenda, Gabriel Kronberger, Christoph Feilmayr, Michael Affenzeller
In this paper a data mining approach for variable selection and knowledge extraction from datasets is presented. The approach is based on unguided symbolic regression (every variable present in the dataset is treated as the target variable in multiple regression runs) and a novel variable relevance metric for genetic programming. The relevance of each input variable is calculated and a model approximating the target variable is created. The genetic programming configurations with different target variables are executed multiple times to reduce stochastic effects and the aggregated results are displayed as a variable interaction network. This interaction network highlights important system components and implicit relations between the variables. The whole approach is tested on a blast furnace dataset, because of the complexity of the blast furnace and the many interrelations between the variables. Finally the achieved results are discussed with respect to existing knowledge about the blast furnace process.
DISPAR-Tournament: a parallel population reduction operator that behaves like a tournament
Ogier Maitre, Deepak Sharm, Nicolas Lachiche, Pierre Collet
This paper presents an experimental study of different variants of tournament selection, and proposes a new DISPAR-tournament (Disjoint Sets Parallel tournament) operator for population reduction to be used in parallel implementations of evolution strategies and other evolutionary algorithms.
Wednesday 27 April 14:30-16:00, room 3: Leonardo, Session 2
Chair: Aniko Ekart
Global characterization of the CEC 2005 fitness landscapes using fitness-distance analysis
Christian Mueller, Ivo Sbalzarini
We interpret real-valued black-box optimization problems over continuous domains as black-box landscapes. The performance of a given optimization heuristic on a given problem largely depends on the characteristics of the corresponding landscape. Designing statistical measures that can be used to classify landscapes and quantify their topographical properties is hence of great importance. We transfer the concept of fitness-distance analysis from theoretical biology and discrete combinatorial optimization to continuous optimization and assess its potential to characterize black-box landscapes. Using the CEC 2005 benchmark functions, we empirically test the robustness and accuracy of the resulting landscape characterization and illustrate the limitations of fitness-distance analysis. This provides a first step toward a classification of real-valued black-box landscapes over continuous domains.
A Framework for Multi-Model EDAs with Model Recombination
Thomas Weise, Stefan Niemczyk, Raymond Chiong, Mingxu Wan
Estimation of Distribution Algorithms (EDAs) are evolutionary optimization methods that build models which estimate the distribution of promising regions in the search space. Conventional EDAs use only one single model at a time. One way to efficiently explore multiple areas of the search space is to use multiple models in parallel. In this paper, we present a general framework for both single- and multi-model EDAs. We propose to use clustering to divide the selected individuals into different groups which are then utilized to build separate models. For the multi-model case, we introduce the concept of model recombination. This novel framework has great generality, encompassing the traditional Evolutionary Algorithm and the EDA as its extreme cases. We instantiate our framework in form of a real-valued algorithm and apply this algorithm to some well-known benchmark functions. Numerical results show that both single- and multi-model EDAs have their own strengths and weaknesses and that the multi-model EDA is able to prevent premature convergence.
[index]
evostim
Talks
Wednesday 27 April 16:20-17:50, room 3: Leonardo, Nature-inspired techniques in scheduling, planning and timetabling
Chair: A. Şima Uyar and Neil Urquhart
A Genetic Algorithm for Radiotherapy Pre-treatment Scheduling
Sanja Petrovic, Elkin Castr
This paper is concerned with the radiotherapy pre-treatment patient scheduling. Radiotherapy pre-treatment deals with localisation of the area to be irradiated and generation of a treatment plan for a patient. A genetic algorithm is developed for patient scheduling which evolves priority rules for operations of radiotherapy pre-treatment. The fitness function takes into consideration the waiting time targets of patients and also the early idle time on resources. Real world data from a hospital in the UK are used in experiments.
Experimental Comparison of Selection Hyper-Heuristics for the Short-Term Electrical Power Generation Scheduling Problem
Argun Berberoglu, A. Şima Uyar
Abstract.This paper presents an experimental comparison of a selection hyper-heuristic approach with several heuristic selection and move acceptance strategy combinations for the Short-Term Electrical Power Generation Scheduling problem. Tests are performed to analyze the efficiency of the combinations using problem instances taken from literature. Results show that the hyper-heuristic using the random permutation descent heuristic selection method and the only improving move acceptance scheme achieves the best results on the chosen problem instances. Because of the promising results, research will continue for further enhancements
Posters
Wednesday 27 April 18:15-19:00 in the Atrium
Nature-inspired Optimization for Biped Robot Locomotion and Gait Planning
Shahriar Asta, Sanem Sariel-Tala
Biped locomotion for humanoid robots is a challenging problem that has come into prominence in recent years. As the degrees of freedom of a humanoid robot approaches to that of humans, the need for a better, flexible and robust maneuverability becomes inevitable for real or realistic environments.This paper presents new motion types for a humanoid robot in coronal plane on the basis of Partial Fourier Series model. To the best of our knowledge, this is the first time that omni-directionality has been achieved for this motion model. Three different nature-inspired optimization algorithms have been used to improve the gait quality by tuning the parameters of the proposed model. It has been empirically shown that the trajectories of the two specific motion types, namely side walk and diagonal walk, can be successfully improved by using these optimization methods. The best results are obtained by the Simulated Annealing procedure with restarting.
Planning and optimising organisational travel plans using an Evolutionary Algorithm
Neil Urquhart
Commuting to the workplace is a highly individualistic experience, especially where the private car is the chosen mode of transport. The costs of using cars with low occupancy rates are significant in environmental terms as well as requiring the provision of parking space at the workplace. This paper examines the use of an Evolutionary Algorithm based problem solver to construct travel plans for three sites with 248,404 and 520 employees respectively at each site. Results presented suggest that a significant saving in overall distance travelled and parking spaces required is possible. The algorithm employed takes into account both hard constraints and soft constraints (such as work patterns and journey flexibility).
[index]
evostoc
Talks
Wednesday 27 April 14:30-16:00, room 5: Eraclito, Session 1
Chair: Hendrik Richter
Memory-Based Immigrants for Ant Colony Optimization in Changing Environments
Michalis Mavrovouniotis, Shengxiang Yang
Ant colony optimization (ACO) algorithms have proved that they can adapt to dynamic optimization problems (DOPs) when they are enhanced to maintain diversity. DOPs are important due to their similarities to many real-world applications. Several approaches have been integrated with ACO to improve their performance in DOPs, where memory-based approaches and immigrants schemes have shown good results on different variations of the dynamic travelling salesman problem (DTSP). In this paper, we consider a different variation of DTSP where traffic jams occur in a cyclic pattern. This means that old environments will re-appear in the future. A hybrid method that combines memory and immigrants schemes is proposed into ACO to address this kind of DTSPs. The memory-based approach is useful to directly move the population to promising areas in the new environment by using solutions stored in the memory. The immigrants scheme is useful to maintain the diversity within the population. The experimental results based on different test cases of the DTSP show that the memory-based immigrants scheme enhances the performance of ACO in cyclic dynamic environments.
Flexible Variable Neighborhood Search in Dynamic Vehicle Routing
Briseida Sarasola, Mostepha R. Khouadjia, Enrique Alba, Laetitia Jourdan, El-Ghazali Talbi
Many optimization problems are dynamic, which means that the available data may change while the problem is being solved. Incorporating elements into the algorithm that take into account these changes usually leads to more effective algorithms which provide better solutions. In this work, we propose a flexibility strategy for the Vehicle Routing Problem with Dynamic Requests. We show that early decissions, which are taken in the beginning of the optimization process, influence the quality of final solutions for the dynamic problem. Our flexible algorithm provides better results than the canonical one and is competitive with the results in the literature.
An Investigation of Selection Hyper-heuristics in Dynamic Environments
Berna Kiraz, A. Şima Uyar, Ender Özcan
Hyper-heuristics are high level methodologies that perform search over the space of heuristics rather than solutions for solving computationally difficult problems. A selection hyper-heuristic framework provides means to exploit the strength of multiple low level heuristics where each heuristic can be useful at different stages of the search. In this study, the behavior of a range of selection hyper-heuristics is investigated in dynamic environments. The results show that hyper-heuristics embedding learning heuristic selection methods are sufficiently adaptive and can respond to different types of changes in a dynamic environment.
Wednesday 27 April 16:20-17:50, room 5: Eraclito, Session 2
Chair: Ferrante Neri
CHC-based Algorithms for the Dynamic Traveling Salesman Problem
Anabela Simoes, Ernesto Costa
The CHC algorithm uses an elitist selection method which, combined with an incest prevention mechanism and a method to diverge the population whenever it converges, allows the maintenance of the population diversity. This algorithm was successfully used in the past for static optimization problems. In this paper we propose three new and improved CHC-based algorithms designed to deal with dynamic environments. The performance of the investigated CHC algorithms is tested in different instances of the dynamic Traveling Salesman Problem.
The experimental results show the efficiency, robustness and adaptability of the improved CHC variants solving different dynamic traveling salesman problems.
Solving dynamic constrained optimization problems with asynchronous change pattern
Hendrik Richter, Franz Dietel
We consider optimization problems with a dynamic fitness landscape and dynamic constraints that may change independent of each other in terms of their respective time regimes. This generally leads to asynchronous change pattern with the possibility of occasional synchronization points. We present a framework for describing such a dynamical setting and for performing numerical experiments on the algorithm’s behavior.
[index]
evotranslog
Talks
Wednesday 27 April 11:30-13:00, room 5: Eraclito, Session 1
Chairs: Joern Grahl and Christian Prins
Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows
Arpad Rimmel, Fabien Teytau, Tristan Cazenav
The traveling salesman problem with time windows is known to be a really difficult benchmark for optimization algorithms. In this paper, we are interested in the minimization of the travel cost. To solve this problem, we propose to use the nested Monte-Carlo algorithm combined with a Self-Adaptation Evolution Strategy. We compare the efficiency of several fitness functions. We show that with our technique we can reach the state of the art solutions for a lot of problems in a short period of time.
Heuristics for a real-world mail delivery problem
Elisabeth Gussmagg-Pfliegl, Fabien Tricoire, Karl F. Doerner, Richard F. Hartl, Stefan Irnich
We are solving a mail delivery problem by combining exact and heuristic methods. The problem is a tactical routing problem as routes for all postpersons have to be planned in advance for a period of several months. As for many other routing problems, the task is to construct a set of feasible routes serving each customer exactly once at minimum cost. Four different modes (car, moped, bicycle, and walking) are available, but not all customers are accessible by all modes. Thus, the problem is characterized by three interdependent decisions: the clustering of customers into districts, the choice of a mode for each district, and the routing of the postperson through its district. We present a two-pahse solution approach that we have implemented and tested on seven real world instances. Results show that the approach can compete with solutions currently employed and is able to improve them by up to 9.5%.
A PSO-based Memetic Algorithm for the Team Orienteering Problem
Duc-Cuong Dang, Rym Nesrine Guibad, Aziz Moukri
This paper proposes an effective Particle Swarm Optimization (PSO)-based Memetic Algorithm (PSOMA) for the Team Orienteering Problem (TOP). TOP is a particular vehicle routing problem whose aim is to maximize the profit gained from visiting clients while not exceeding a travel cost/time limit. Our PSOMA features optimal splitting techniques and genetic crossover operators. Furthermore, the memetic characteristic of our PSOMA is strengthened by an intensive use of local search techniques and also by a low value of 0.07 for inertia. In our experiments with the standard benchmark for TOP, PSOMA attained a gap of only 0.016%, as compared to 0.041%, the best known gap in the literature.
Integrated Generation of Working Time Models and Staff Schedules in Workforce Management
Volker Nissen, Maik Günther, René Schumann
Our project addresses the question how to automatically and simultaneously assign staff to workstations and generate optimised working time models on the basis of fluctuating personnel demand while taking into account practical constraints. Two fundamentally different solution approaches, a specialized constructive heuristic (commercial) and a hybrid metaheuristic (the evolution strategy) that integrates a repair heuristic to remove contraint violations are compared on a complex real-world problem from a retailer. The hybrid approach clearly outperforms the tailored constructive method. Taken together with our similar findings on a related staff scheduling problem from logistics this result suggests that the evolution strategy, despite its original focus on continuous parameter optimisation, is a powerful tool in combinatorial optimisation and deserves more attention. Moreover, hybridising a metaheuristic with a problem-specific repair heuristic seems a useful approach of resolving the conflict between domain-specific characteristics of a real-world problem and the desire to employ generic optimisation techniques, at least in the domain of workforce management.