Paper Presentation Schedule

Friday 9 July
Saturday 10 July
Sunday 11 July

Paper Presentation Schedule

Friday 9 July 10:40 - 12:20


RWA: Best Paper Nominees

Room: Salon A

Session Chair: Edgar Galvan-Lopez (Essex University)

10:40-11:05 * A Neuro-Evolutionary Approach to Micro Aerial Vehicle Control

Max Salichon, Kagan Tumer

Learning, Evolution, MAV Control

Applying classical control methods to Micro Aerial Vehicles (MAVs) is a difficult process due to the complexity of the control laws with fast and highly non-linear dynamics. Such methods rely heavily on difficult to obtain models and are particularly ill-suited to the stochastic and dynamic environments in which MAVs operate. Instead, in this paper, we focus on a neuro-evolutionary method that learns to map MAV states (position, velocity) to MAV actions (e.g., actuator position). Our results show significant improvements in response times to minor altitude and heading corrections over a traditional PID controller. In addition, we show that the MAV response to maintaining altitude in the presence of wind gusts improves by a factor of five. Similarly, we show that the MAV response to maintaining heading in the presence of turbulence improves by factors of three.

11:05-11:30 * Robust Neuro-Control for A Micro Quadrotor

Jack F. Shepherd III, Kagan Tumer


Quadrotors are unique among Micro Aerial Vehicles in providing excellent maneuverability (as opposed to winged flight), while maintaing a simple mechanical construction (as opposed to helicopters). This mechanical simplicity comes at a cost of increased controller complexity. Quadrotors are inherently unstable, and micro quadrotors are particularly difficult to control.

In this paper, we evolve a hierarchical neuro-controller for micro (0.5 kg) quadrotor control. The first stage of control aims to stabilize the craft and outputs rotor speeds based on a requested attitude (pitch, roll, yaw, and vertical velocity). This controller is developed in four parts around each of the variables, and then combined and trained further to increase robustness. The second stage of control aims to achieve a requested (x, y, z) position by providing the first stage with the appropriate attitude.

The results show that stable quadrotor control is achieved through this architecture. In addition, the results show that neuro-evolutionary control recovers from disturbances over an order of magnitude faster than a basic PID controller. Finally, the neuro-evolutionary controller provides stable flight in the presence of 5 times more sensor noise and 8 times more actuator noise as compared to the PID controller.

11:30-11:55 * Optimization of the Hölder Image Descriptor using a Genetic Algorithm

Leonardo Trujillo, Pierrick Legrand, Gustavo Olague, Cynthia Perez

Hölderian regularity, image descriptors, genetic algorithms

Local image features can provide the basis for robust and invariant recognition of objects and scenes. Therefore, compact and distinctive representations of local shape and appearance has become invaluable in modern computer vision. In this work, we study a local descriptor based on the Hölder exponent, a measure of signal regularity. The proposal is to find an optimal number of dimensions for the descriptor using a genetic algorithm (GA). To guide the GA search, fitness is computed based on the performance of the descriptor when applied to standard region matching problems. This criterion is quantified using the F-Measure, derived from recall and precision analysis. Results show that it is possible to reduce the size of the canonical Hölder descriptor without degrading the quality of its performance. In fact, the best descriptor found through the GA search is nearly 70% smaller and achieves similar performance on standard tests.



11:55-12:20 * Evolutionary-Based Conflict-Free Scheduling of Collective Communications on Spidergon NoCs

Jiri Jaros, Vaclav Dvorak

Collective communications, Communication scheduling, Evolutionary design, Spidergon, Wormhole switching, fat topologies

The Spidergon interconnection network has become popular recently in multiprocessor systems on chips. To the best of our knowledge, algorithms for collective communications (CC) have not been discussed in the literature as yet, contrary to pair-wise routing algorithms. The paper investigates complexity of CCs in terms of lower bounds on the number of communication steps at conflict-free scheduling. The considered networks on chip make use of wormhole switching, full duplex links and all-port non-combining nodes. A search for conflict-free scheduling of CCs has been done by means of evolutionary algorithms and the resulting numbers of communication steps have been summarized and compared to lower bounds. Time performance of CCs can be evaluated from the obtained number of steps, the given start-up time and link bandwidth. Performance prediction of applications with CCs among computing nodes of the Spidergon network is thus possible.



ACO-SI: Particle Swarm Optimization I

Room: Salon B

Session Chair: Kalyanmoy Deb (IIT Kanpur)

10:40-11:05 Particle Swarm Optimization with Triggered Mutation and Its Implementation based on GPU

You Zhou, Ying Tan

Particle Swarm Optimization, Mutation, GPU, Speedup

A novel particle swarm optimization with triggered mutation (PSO-TM) is presented in this paper for better performance. First, a technique is designed to evaluate the "health" of swarm. When the swarm is successively "unhealthy" for a certain number of iterations, uniform mutation is applied to the position of each particle in a probabilistic way. If the mutations produce worse particles, the memorized previous positions are retrieved as current positions of these particles, hence the normal evolution process of the swarm will not be fiercely interrupted by such bad mutations. Experiments are conducted on 29 benchmark test functions to show the promising performance of our proposed PSO-TM. The results show that the PSO-TM performs much better than the standard PSO on almost all of the 29 test functions, especially those multimodal, complex ones of hybrid composition. Besides, PSO-TM adds little computation complexity to the standard PSO, and runs almost equally fast. Furthermore, we have implemented PSO-TM based on Graphic Processing Unit (GPU) in parallel. Compared with the CPU-based standard PSO, the proposed PSO-TM can reach a speedup of 25 times, as well as an improved optimizing performance.

11:05-11:30 Development of Efficient Particle Swarm Optimizers by Using Concepts from Evolutionary Algorithms

Kalyanmoy Deb, Nikhil Padhye

Particle swarm optimization, Evolutionary optimization, G3-PCX, unimodal problems, recombination, steady-state PSO

Particle swarm optimization (PSO) has been in practice for more than 10 years now and has gained  wide popularity in various optimization tasks. In the context to single objective optimization, this paper studiestwo aspects of PSO: (i) its ability to approach an `optimal basin', and (ii) to find the optimum with high precision once it enters the region of interest. We test standard PSO algorithms and discover their inability in handling both aspects efficiently. To address these issues with PSO, we propose an evolutionary algorithm (EA) which is algorithmically similar to PSO, and then borrow different EA-specific operators to enhance the PSO's performance. Our final proposed PSO contains a parent-centric recombination operator instead of usual particle update rule, but maintains PSO's individualistic trait and has a demonstrated performance comparable to a well-known GA (and outperforms the GA in some occasions). Moreover, the modified PSO algorithm is found to scale up to solve as large as 100-variable problems. This study emphasizes the need for similar such studies in establishing an equivalence between various genetic/evolutionary and other bio-inspired algorithms, a process that may lead us to better understand the scope and usefulness of variousoperators associated with each algorithm.


11:30-11:55 An Empirical Comparison of Parallel and Distributed Particle Swarm Optimization Methods

Leonardo Vanneschi, Daniele Codecasa, Giancarlo Mauri

optimization, swarm intelligence, parallel and distributed algorithms

The goal of this paper is to present four new parallel and distributed particle swarm optimization methods and to experimentally compare their performances. These methods include a genetic algorithm whose individuals are co-evolving swarms, a different multi-swarm system and their respective variants enriched by adding a repulsive component to the particles. We have tried to carry out this comparison using the benchmark test suite that has been defined for the CEC-2005 numerical optimization competition and we have remarked that it is hard to have a clear picture of the experimental results on that benchmark suite. We believe that this is due to the fact that the CEC-2005 benchmark suite is only composed by either very easy or very hard test functions. For this reason, we introduce two new sets of test functions whose difficulty can be tuned by simply modifying the values of few real-valued parameters. We propose to integrate the CEC-2005 benchmark suite by adding these sets of test functions to it. Experimental results on these two sets of test functions clearly show that the proposed repulsive multi-swarm system outperforms all the other presented methods.


GA: Coevolution & Niching

Room: Salon C

Session Chair: Sushil Louis (UNR)

10:40-11:05 Generalized Crowding for Genetic Algorithms

Severino F. Galan, Ole J. Mengshoel

Genetic algorithms, Niching, Deterministic crowding, Probabilistic crowding, Markov chain analysis, Bayesian networks, Experiments

Crowding is a technique used in genetic algorithms to preserve diversity in the population and to prevent premature convergence to local optima. It consists of pairing each offspring with a similar individual in the current population (pairing phase) and deciding which of the two will remain in the population (replacement phase). The present work focuses on the replacement phase of crowding, which usually has been carried out by one of the following three approaches: Deterministic, Probabilistic, and Simulated Annealing. These approaches present some limitations regarding the way replacement is conducted. On the one hand, the first two apply the same selective pressure regardless of the problem being solved or the stage of the genetic algorithm. On the other hand, the third does not apply a uniform selective pressure over all the individuals in the population, which makes the control of selective pressure over the generations somewhat difficult. This work presents a Generalized Crowding approach that allows selective pressure to be controlled in a simple way in the replacement phase of crowding, thus overcoming limitations of the other approaches. Furthermore, the understanding of existing approaches is greatly improved, since both Deterministic and Probabilistic Crowding turn out to be special cases of Generalized Crowding. In addition, the temperature parameter used in Simulated Annealing is replaced by a parameter called scaling factor that controls the selective pressure applied. Theoretical analysis using Markov chains and empirical evaluation using Bayesian networks demonstrate the potential of this novel Generalized Crowding approach.


11:05-11:30 Complex Energy Landscape Mapping by Histogram Assisted Genetic Algorithm

Wenjin Chen, K.Y. Szeto

Histogram, Genetic Algorithm, Combinatorial Optimization, Complex Landscape Mapping

A histogram assisted adjustment of fitness distribution in standard genetic algorithm is introduced and tested on four benchmark functions of complex landscapes, with remarkable improvement in performance, such as the substantial enhancement in the  probability of detecting local minima. Numerical tests suggest that the idea of histogram assisted adjustment, or the renormalization of the fitness distribution, is generally advantageous for multi-modal function optimization. An analysis on the effect of the bin number of the histogram has also been carried out, showing that the performance of the algorithm is insensitive to this extra parameter as long as it is an order of magnitude smaller than the size of the population (N) in the genetic algorithm. This analysis suggests that the advantage of the introduction of histogram assisted fitness adjustment is a robust feature for genetic algorithm, since the adjustment of fitness enhances exploration by broadening the diversity of the population of chromosomes. In general, the advantage of this histogram assisted adjustment more than compensates the cost of computation resource in the construction of the histogram with O(N) time complexity. Suggestions of using this technique for the mapping of complex landscape are discussed.

11:30-11:55 Co-Evolution of Cooperative Strategies under Egoism

Ta-Chun Lien, Tian-Li Yu, Ying-Shiuan You

Game Theory, Coevolution, Genetic Algorithm

This paper examines which elements are necessary for coevolutionary genetic algorithms to evolve cooperative strategies under pure egoistic considerations. Since competitions and cooperations coexist in an auction-based manpower allocation problem, the problem is adopted for further investigation. To alleviate analytical burden, the problem is abstracted to a resource-bidding game under the Nash game framework. A mathematical model for the resource-bidding game is defined and several special cases are illustrated. One of these special cases, named c-mNE, is further investigated due to the existance of cooperative modes. Various kinds of egoistic fitness functions and evolutionary mechanisms are experimented on c-mNE. Based on the experimental results, this paper suggests that coevolutionary mechanisms which properly eliminate aggressive strategies and preserve cooperative strategies can evolve cooperative modes under the pure egoistic assumption.

11:55-12:20 Coevolving Influence Maps for Spatial Team Tactics in a RTS Game

Phillipa Avery, Sushil Louis

Co-evolution, RTS, Influence Maps

Real Time Strategy (RTS) games provide a representation of spatial tactics with group behaviour. Often tactics will involve using groups of entities to attack from different directions and at different times of the game, using coordinated techniques. Our goal in this research is to learn tactics which are challenging for human players. The method we apply to learn these tactics, is a coevolutionary system designed to generate effective team behavior. To do this, we present a unique Influence Map representation, with a coevolutionary technique that evolves the maps together for a group of entities. This allows the creation of autonomous entities that can move in a coordinated manner. We apply this technique to a naval RTS island scenario, and present the successful creation of strategies demonstrating complex tactics.


Human-Competitive Results

Room: Salon D

Session Chair:

10:40-12:20 Humie finalists will give short oral presentations about human-competitive results that they have produced by any form of genetic and evolutionary computation (e.g., genetic algorithms, genetic programming, evolution strategies, evolutionary programming, learning classifier systems, grammatical evolution, etc.)



ALIFE: Evolutionary Robotics

Room: Salon G

Session Chair: Hod Lipson (Cornell University)

10:40-11:05 Cooperative Self-Organization in a Heterogeneous Swarm Robotic System

Frederick Ducatelle, Gianni A. Di Caro, Luca M. Gambardella

swarm robotics, swarm intelligence, self-organization, ant foraging

We study how a swarm robotic system consisting of two different types of robots can solve a foraging task. The first type of robots are small wheeled robots, called foot-bots, and the second type are flying robots that can attach to the ceiling, called eye-bots. While the foot-bots perform the actual foraging, i.e. they move back and forth between a source and a target location, the eye-bots are deployed in stationary positions against the ceiling, with the goal of guiding the foot-bots. The key component of our approach is a process of mutual adaptation, in which foot-bots execute instructions given by eye-bots, and eye-bots observe the behavior of foot-bots to adapt the instructions they give. Through a simulation study, we show that this process allows the system to find a path for foraging in a cluttered environment. Moreover, it is able to converge onto the shortest of two paths, and spread over different paths in case of congestion. Since our approach involves mutual adaptation between two sub-swarms of different robots, we refer to it as cooperative self-organization. This is to our knowledge the first work that investigates such a system in swarm robotics.

11:05-11:30 Revising the Evolutionary Computation Abstraction: Minimal Criteria Novelty Search

Joel Lehman, Kenneth O. Stanley

Evolution of Complexity, Artificial Life, Novelty Search, NEAT

Though based on abstractions of nature, current evolutionary algorithms and artificial life models lack the drive to complexity characteristic of natural evolution. Thus this paper argues that the prevalent fitness-pressure-based abstraction does not capture how natural evolution discovers complexity. Alternatively, this paper proposes that natural evolution can be abstracted as a process that discovers many ways to express the same functionality. That is, all successful organisms must meet the same minimal criteria of survival and reproduction. This abstraction leads to the key idea in this paper: Searching for novel ways of meeting the same minimal criteria, which is an accelerated model of this new abstraction, may be an effective search algorithm. Thus the existing novelty search method, which rewards any new behavior, is extended to enforce minimal criteria. Such minimal criteria novelty search prunes the space of viable behaviors and may often be more efficient than the search for novelty alone. In fact, when compared to the raw search for novelty and traditional fitness-based search in the two maze navigation experiments in this paper, minimal criteria novelty search evolves solutions more consistently. It is possible that refining the evolutionary computation abstraction in this way may lead to solving more ambitious problems and evolving more complex artificial organisms.

11:30-11:55 Guarding Against Premature Convergence while Accelerating Evolutionary Search

Josh C Bongard, Gregory S Hornby

Evolutionary Robotics, Premature Convergence, Evolutionary Algorithms

The fundamental dichotomy in evolutionary algorithms is that between exploration and exploitation. Recently, several algorithms have been introduced that guard against premature convergence by allowing both exploration and exploitation to occur simultaneously. However, continuous exploration greatly increases search time. To reduce the cost of continuous exploration we combine one of these methods (the age-layered population structure (ALPS) algorithm ) with an early stopping (ES) method that greatly accelerates the time needed to evaluate a candidate solution during search. We show that this combined method outperforms an equivalent algorithm with neither ALPS nor ES, as well as regimes in which only one of these methods is used, on an evolutionary robotics task.


11:55-12:20 * Crossing the Reality Gap in Evolutionary Robotics by Promoting Transferable Controllers

Sylvain Koos, Jean-Baptiste Mouret, Stephane Doncieux

reality gap problem, Evolutionary Robotics, multiobjective optimization, simulation-to-reality disparity

The reality gap, that often makes controllers evolved in simulation inefficient once transferred onto the real system, remains a critical issue in Evolutionary Robotics (ER); it prevents ER application to real-world problems. We hypothesize that this gap mainly stems from a conflict between the efficiency of the solutions in simulation and their transferability from simulation to reality: best solutions in simulation often rely on bad simulated phenomena (e.g. the most dynamic ones). This hypothesis leads to a multi-objective formulation of ER in which two main objectives are optimized via a Pareto-based Multi-Objective Evolutionary Algorithm: (1) the fitness and (2) the transferability. To evaluate this second objective, a simulation-to-reality disparity value is approximated for each controller. The proposed method is applied to the evolution of walking controllers for a real 8-DOF quadrupedal robot. It successfully finds efficient and well-transferable controllers with only a few experiments in reality.


Theory: Best Paper Nominees

Room: Salon I

Session Chair: Carsten Witt (Technical University of Denmark)

10:40-11:05 * Necessary and Sufficient Conditions for Success of the Metropolis Algorithm for Optimization

Swagato Sanyal, Raja S, Somenath Biswas

Metropolis algorithm, optimization, success of Markov chain families, rapid mixing of Markov chains

This paper focusses on the performance of the Metropolis algorithm when employed for solving combinatorial optimization problems. One finds in the literature two notions of success for the Metropolis algorithm in the context of such problems. First, we show that both these notions are equivalent. Next, we provide two characterizations, or in other words, necessary and sufficient conditions, for the success of the algorithm, both characterizations being conditions on the family of Markov chains which the Metropolis algorithm gives rise to when applied to an optimization problem. The first characterization is that the Metropolis algorithm is successful iff in every chain, for every set A of states not containing the optimum, the ratio of the ergodic flow out of A to the capacity of A is high. The second characterization is that in every chain the stationary probability of the optimum is high and that the family of chains mixes rapidly. We illustrate the applicability of our results by giving alternative proofs of certain known results.

11:05-11:30 * Multiplicative Drift Analysis

Benjamin Doerr, Daniel Johannsen, Carola Winzen

Running time analysis, Theory

Drift analysis is one of the strongest tools in the analysis of evolutionary algorithms. Its main weakness is that it is often very hard to find a good drift function. In this paper, we make progress in this direction. We prove a multiplicative version of the classical drift theorem. This allows easier analyses in those settings, where the optimization progress is roughly proportional to the current objective value. Our drift theorem immediately gives natural proofs for the best known run-time bounds for the (1+1) Evolutionary Algorithm computing minimum spanning trees and shortest paths, since here we may simply take the objective function as drift function. As a more challenging example, we give a relatively simple proof for the fact that any linear function is optimized in time O(n log n). In the multiplicative setting, a simple linear function can be used as drift function (without taking any logarithms). However, we also show that, both in the classical and the multiplicative setting, drift functions yielding good results for all linear functions exist only if the mutation probability is at most c/n for a small constant c.



11:30-11:55 * Ant Colony Optimization for Stochastic Shortest Path Problems

Christian Horoba, Dirk Sudholt

Ant colony optimization, combinatorial optimization, running time analysis, shortest path problems, stochastic optimization

We consider Ant Colony Optimization (ACO) for stochastic shortest path problems where edge weights are subject to noise that reflects delays and uncertainty. The question is whether the ants can find or approximate shortest paths in the presence of noise. We first prove a general upper bound for the time until the algorithm finds an approximation for arbitrary, independent noise values. For independent gamma-distributed noise we prove lower bounds for the time until a good approximation is found. We construct a graph where the ants cannot find a reasonable approximation, even in exponential time. The last result changes when the noise is perfectly correlated as then the ants find shortest paths efficiently.

11:55-12:20 * Black-Box Search by Unbiased Variation

Per Kristian Lehre, Carsten Witt

Runtime Analysis, Black-Box Complexity

The complexity theory for black-box algorithms, introduced by Droste et al. (2006), describes common limits on the efficiency of a broad class of randomised search heuristics. There is an obvious trade-off between the generality of the black-box model and the strength of the bounds that can be proven in such a model. In particular, the original black-box model allows polynomial complexity for certain NP-complete problems and provides for well-known benchmark problems relatively small lower bounds, which are typically not met by popular search heuristics. In this paper, we introduce a more restricted black-box model which we claim captures the working principles of many randomised search heuristics including simulated annealing, evolutionary algorithms, randomised local search and others. The key concept worked out is an unbiased variation operator. Considering this class of algorithms, significantly better lower bounds on the black-box complexity are proved, amongst them an Ω(n log n) bound for functions with unique optimum. Moreover, a simple unimodal function and gap functions are considered. We show that a simple (1+1) EA is able to match the runtime bounds in several cases.



Room: Portland

Session Chair: Jorn Mehnen, Thomas BartzBeielstein, Thomas Baeck, Erik Goodman

10:40-12:20 Ask the Experts: EC questions from the audience (Open panel discussion)





GA: Best Paper Nominees

Room: Salon A

Session Chair: Dirk Thierens (Universiteit Utrecht)

14:00-14:25 * Phenotype Feedback Genetic Algorithm Operators for Heuristic Encoding of Snakes within Hypercubes

Benjamin P. Carlson, Dean F. Hougen

Genetic Algorithm, Heuristics, Phenotype, Genotype, Snake, Hypercube

Many complex problems can be solved by a sequence of steps or simple heuristics. In many cases a good solution relies on both good heuristics and proper ordering of their application. Problems such as creating a constrained path through a graph can be solved in this way if we can find a mechanism for ordering the heuristics. We propose using a genetic algorithm (GA) for this purpose to solve the snake-in-the-box problem. However, the additional layer of abstraction created by heuristics weakens the guiding effects of traditional GA operators. We also propose a new set of GA operators that solve this problem by, in the manipulation of the population, applying information from the paths (snakes) produced by the population members. In addition we show the efficacy of this approach by producing a new record length snake of 98 edges in an eight dimensional hypercube. We also compare our new operators with more traditional ones.

14:25-14:50 * NK Landscapes, Problem Difficulty, and Hybrid Evolutionary Algorithms

Martin Pelikan

NK fitness landscape, problem difficulty, performance analysis, fitness distance correlation, correlation length, escape rate, hybrid evolutionary algorithms, estimation of distribution algorithms, hierarchical BOA, hBOA

This paper presents an experimental study of NK landscapes with the main focus on the relationship between (1) problem parameters, (2) various measures of problem difficulty of fitness landscapes, and (3) performance of hybrid evolutionary algorithms. As the target class of problems, the study considers two types of NK landscapes: (1) Standard, unrestricted NK landscapes and (2) shuffled NK landscapes with nearest-neighbor interactions. As problem difficulty measures, the paper considers the fitness distance correlation, the correlation coefficient, the distance of local and global optima, and the escape rate. Experimental results are presented, analyzed and discussed. Promising avenues for future work are also outlined.

14:50-15:15 Edge-based Representation Beats Vertex-based Representation in Shortest Path Problems

Benjamin Doerr, Daniel Johannsen

Evolutionary algorithm, runtime analysis, shortest path

In this paper, we present a new representation for individuals in the single-source shortest path problem. Contrary to previous approaches, it has the natural property that different vertex degrees do not induce unfairness in the mutation step. In particular, at any time each edge has roughly the same probability of being added to or removed from the current individual. This turns out to be a crucial property. Mainly based on this, we prove superior bounds for the optimization time two evolutionary algorithms for the single-source shortest path problem. For both the multi-criteria formulation of the problem (introduced by Scharnow, Tinnefeld and Wegener (2002, 2004)) and the single-criteria one (regarded in Baswana et al. (2009)), we improve the existing bounds by a factor of n^2/m, where m denotes the number of edges and n the number of vertices of the underlying graph. Given that most graphs found in practical applications are sparse, this is a considerable gain.




Room: Salon B

Session Chair:

14:00-15:40 Competitions finalists presentations

Evolutionary Art

GPUs for Genetic and Evolutionary Computation

2010 Simulated Car Racing Championship

2010 GECCO-2010 Demolition Derby




SBSE: Best Paper Nominees

Room: Salon C

Session Chair: Mathew Hall (University of Sheffield)

14:00-14:25 On the Use of Genetic Programming for Automated Refactoring and the Introduction of Design Patterns

Adam C. Jensen, Betty H.C. Cheng

search-based software engineering, object-oriented design, refactoring, design patterns, software metrics, evolutionary computation, intelligent search

Maintaining an object-oriented design for a piece of software is a difficult, time-consuming task. Prior approaches to automated design refactoring have focused on making small, iterative changes to a given software design. However, such approaches do not take advantage of composition of design changes, thus limiting the richness of the refactoring strategies that they can generate. In order to address this problem, this paper introduces an approach that supports composition of design changes and makes the introduction of design patterns a primary goal of the refactoring process. The proposed approach uses genetic programming and software engineering metrics to identify the most suitable set of refactorings to apply to a software design. We illustrate the efficacy of this approach by applying it to a large set of published models, as well as a real-world case study.

14:25-14:50 * Empirically Studying the Role of Selection Operators DuringSearch-Based Test Suite Prioritization

Alexander P Conrad, Robert S Roos, Gregory M Kapfhammer

test prioritization, coverage testing, genetic algorithm

Regression test suite prioritization techniques reorder test cases so that, on average, more faults will be revealed earlier in the test suite's execution than would otherwise be possible. This paper presents a genetic algorithm-based test prioritization method that employs a wide variety of mutation, crossover, selection, and transformation operators to reorder a test suite. Leveraging statistical analysis techniques, such as tree model construction through binary recursive partitioning and kernel density estimation, the paper's empirical results highlight the unique role that the selection operators play in identifying an effective ordering of a test suite. The study also reveals that, while truncation selection consistently outperformed the tournament and roulette operators in terms of test suite effectiveness, increasing selection pressure consistently produces the best results within each class of operator.After further explicating the relationship between selection intensity, termination condition, fitness landscape, and the quality of the resulting test suite, this paper demonstrates that the genetic algorithm-based prioritizer is superior to random search and hill climbing and thus suitable for many regression testing environments.



14:50-15:15 * Search-Based Test Data Generation from Stateflow Statecharts

Andreas Windisch

Automation, Coverage, Model Testing, Optimization, Search-Based Testing, Signal Generation, Simulink, Stateflow, Structural Testing, Test Data Generation

This paper proposes an effective method for automating the test data generation process aiming at structurally covering Stateflow statecharts, while assuring the generation of suitable and - most notably - realistic and meaningful system inputs. For this purpose the principles of evolutionary structural testing have been adapted both for the application to statecharts and for the consideration of continuous signals. The approach is evaluated using a complex industrial case study in comparison to random testing. The results demonstrate the value of this approach in industrial settings due to both its search effectiveness and its high degree of automation, potentially contributing to an improvement in quality assurance of embedded software systems.

15:15-15:40 Factors Affecting the Use of Genetic Algorithms in Test Suite Augmentation

Zhihong Xu, Myra B. Cohen, Gregg Rothermel

Regression testing, test suite augmentation, genetic algorithms, empirical studies

Test suite augmentation techniques are used in regression testing to help engineers identify code elements affected by changes, and generate test cases to cover those elements. Researchers have created various approaches to identify affected code elements, but only recently have they considered integrating, with this task, approaches for generating test cases. In this paper we explore the use of genetic algorithms in test suite augmentation. We identify several factors that impact the effectiveness of this approach, and we present the results of a case study exploring the effects of one of these factors: the manner in which existing and newly generated test cases are utilized by the genetic algorithm. Our results reveal several ways in which this factor can influence augmentation results, and reveal open problems that researchers must address if they wish to create augmentation techniques that make use of genetic algorithms.


ACO-SI: Best Paper Nominees Ant Colony Optimization

Room: Salon D

Session Chair: Frederick Ducatelle (IDSIA)

14:00-14:25 * A Few Ants are Enough: ACO with Iteration-Best Update

Frank Neumann, Dirk Sudholt, Carsten Witt

Ant Colony Optimization, Iteration-Best Update, Runtime Analysis, Theory

Ant colony optimization (ACO) has found many applications in different problem domains. We carry out a first rigorous runtime analysis of ACO with iteration-best update, where the best solution in the each iteration is reinforced. This is similar to comma selection in evolutionary algorithms. We compare ACO to evolutionary algorithms for which it is well known that an offspring size of Ω(log n), n the problem dimension, is necessary to optimize even simple functions like ONEMAX. In sharp contrast, ACO is efficient on ONEMAX even for the smallest possible number of two ants. Remarkably, this only holds if the pheromone evaporation rate is small enough; the collective memory of many ants stored in the pheromones makes up for the small number of ants. We further prove an exponential lower bound for ACO with iteration-best update that depends on a trade-off between the number of ants and the evaporation rate.



14:25-14:50 * The Impact of Design Choices of Multiobjective AntColony Optimization Algorithms on Performance:An Experimental Study on the Biobjective TSP

Manuel Lopez-Ibañez, Thomas Stutzle

Multiobjective Optimization, Ant Colony Optimization, Travelling Salesman Problem

Over the last few years, there have been a number of proposals of ant colony optimization (ACO) algorithms for tackling multiobjective combinatorial optimization problems. These proposals adapt ACO concepts in various ways, for example, some use multiple pheromone matrices and multiple heuristic matrices and others use multiple ant colonies. In this article, we carefully examine several of the most prominent of these proposals. In particular, we identify commonalities among the approaches by recasting the original formulation of the algorithms in different terms. For example, several proposals described in terms of multiple colonies can be cast equivalently using a single ant colony, where ants use different weights for aggregating the pheromone and/or the heuristic information. We study algorithmic choices for the various proposals and we identify previously undetected trade-offs in their performance.


14:50-15:15 Pheromone-Distribution-Based Adaptive Ant Colony System

Wei-jie Yu, Jun Zhang

Ant colony optimization, ant colony system, adaptive parameters control, travelling salesman problem

Parameters values have significant effects on the performance of the ant colony system (ACS) algorithm. However, it is a difficult task to choose proper parameters values for achieving the best performance of the algorithm. That is because the best parameters values are not only dependent on specific problems, but also related to the optimization states during the search process. This paper proposes a novel adaptive parameters control scheme for ACS and develops an adaptive ACS (AACS) algorithm. Different from the existing parameters control schemes, the parameters values in AACS are adaptively controlled according to the current optimization state, which is estimated based on measuring the pheromone trails distribution. The proposed AACS algorithm is applied to solve a series of benchmark traveling salesman problems (TSPs). The resulting solution quality and the convergence rate of AACS are favorably compared with the results by the ACS using fixed parameters values and two existing adaptive parameters control methods. Experimental results show that our proposed method is effective and competitive.


15:15-15:40 An Ant-colony-system-based Activity Scheduling Method for the Lifetime Maximization of Heterogeneous Wireless Sensor Networks

Ying Lin, Xiao-min Hu, Jun Zhang

Wireless sensor networks (WSNs), coverage, connectivity, network lifetime, ant colony optimization (ACO).

Scheduling activities of network devices is an important and promising methodology for prolonging the lifetime of wireless sensor networks (WSNs). The existing scheduling methods in the literature are mostly designed for homogeneous WSNs. Heterogeneous WSNs, despite their wide applications, have received few research attentions. This paper proposes an ant-colony-system-based scheduling method (ACS-SM) for maximizing the lifetime of a typical type of heterogeneous WSNs. First, the lifetime maximization problem is formulated as finding the maximum number of disjoint sets of devices, with each set fulfilling sensing coverage and network connectivity simultaneously. Then ACS-SM adapts the incremental solution construction mechanism in ACS for building disjoint connected cover sets on the basis of a well-designed construction graph. Pheromone trails that record search experience and heuristic information that combines domain knowledge are utilized to guide the set building procedure. A local search process is also developed to further enhance the efficiency of the method. ACS-SM is applied to fifteen WSN cases in three series. Experimental results show that the proposed method can find high-quality solutions at a fast speed for WSNs with different characteristics.


ALIFE: Best Paper Nominees

Room: Salon G

Session Chair: Josh Bongard (University of Vermont)

14:00-14:25 * Resource Abundance Promotes the Evolution of Public Goods Cooperation

Brian D Connelly, Benjamin E Beckmann, Philip K McKinley

Artificial life, cooperation, public goods, digital evolution, virtual biofilms, structured populations

Understanding the evolution of cooperation as part of an evolutionary stable strategy (ESS) is a difficult problem that has been the focus of much work. The associated costs of cooperation may lower the fitness of an organism below that of its non-cooperating counterpart, allowing the more fit organism to persist and outcompete the cooperator. Insight into these behaviors can help provide a better understanding of many aspects of the natural world, as well as provide future avenues for fighting disease.In this study, we use digital evolution to examine how the abundance of a required resource affects the cooperative production of a public good in an adverse environment. Evolutionary computation is an excellent tool for examining these problems, as it offers researchers complete access to organisms and total control over their environment. We find that stable cooperation can occur in otherwise competitive environments at discrete levels corresponding to the availability of a required resource. When resource levels are low, organisms focus solely on competitive behaviors. However, once resource levels cross a critical threshold, cooperation persists in populations. Further, this cooperation occurs in patches, where it is most likely to benefit relatives. Finally, we find that in some cases this cooperative behavior allows organisms to increase their competitive abilities as well.

14:25-14:50 * Evolution of Vision Capabilities in Embodied Virtual Creatures

Marcin L. Pilat, Christian Jacob

Evolution, Learning, Artificial Life, Virtual Creatures, Genetic Algorithms, Vision

We evolve light following behaviours in virtual creatures through neural network training using an incremental evolution approach. The neural controllers of creatures evolved for movement are augmented with simple visual neurons and neural connections. Using an evolutionary algorithm, the resulting creatures are trained to identify and follow a light source. Through this process, we are able to train the neural controllers to create various light following behaviours. Many of the evolved behaviours show stability and adaptiveness to environmental perturbations of body orientation.


14:50-15:15 Coevolution of Heterogeneous Multi-Robot Teams

Matt Knudson, Kagan Tumer

Robot Coordination, Coevolution

Evolving multiple robots so that each robot acting independently can contribute to the maximization of a system level objective presents significant scientific challenges. For example, evolving multiple robots to maximize aggregate information in exploration domains (e.g., planetary exploration, search and rescue) requires coordination, which in turn requires the careful design of the evaluation functions. Additionally, where communication among robots is expensive (e.g., limited power or computation), the coordination must be achieved passively, without robots explicitly informing others of their states/intended actions. Coevolving robots in these situations is a potential solution to producing coordinated behavior, where the robots are coupled through their evaluation functions. In this work, we investigate coevolution in three types of domains: (i) where precisely n homogeneous robots need to perform a task; (ii) where n is the optimal number of homogeneous robots for the task; and (iii) where n is the optimal number of heterogeneous robots for the task. Our results show that coevolving robots with evaluation functions that are locally aligned with the system evaluation significantly improve performance over robots evolving using the system evaluation function directly, particularly in dynamic environments.


15:15-15:40 Evolution of Division of Labor in Genetically Homogenous Groups

Heather J Goldsby, David B. Knoester, Charles Ofria

Digital evolution, Avida, Eusociality, Division of Labor

Within nature, the success of many organisms, including certain species of insects, mammals, slime molds, and bacteria, is attributed to their performance of division of labor,  where individuals specialize on specific roles and cooperate to survive. The evolution of division of labor is challenging to study because of the slow pace of biological evolution and imperfect historical data. In this paper, we use digital evolution to evolve groups of clonal organisms that exhibit division of labor. We then investigate what mechanisms they use to perform division of labor (i.e., location awareness or communication) and discover that it varies according to the type of roles being performed. Lastly, we created an environment where groups of organisms needed to complete a set of tasks, but could do so as either generalists or specialists. We varied the costs of switching tasks and determined that increased costs can result in the evolution of division of labor. Moreover, a group used as a case study exhibited both division of labor and cooperative problem decomposition, where members of the group shared partial solutions to solve the full set of problems. This approach has the potential to inform predictions in biological studies, as well as achieving division of labor when using evolutionary computation to solve more complex engineering problems.



Theory: Landscapes and Convergence

Room: Salon I

Session Chair: Per Kristian Lehre (Technical University of Denmark)

14:00-14:25 Elementary Landscapes of Frequency Assignment Problems

Darrell Whitley, Francisco Chicano, Enrique Alba, Francisco Luna

Fitness Landscapes, Elementary Landscapes

We analyze various forms of the Frequency Assignment Problem using the theory of elementary landscapes. We show that three variants of the Frequency Assignment Problem are either directly an Elementary Landscape, or are a superposition of two Elementary Landscapes. We also examine the computability of neighborhood averages for partial neighborhoods.

14:25-14:50 Theoretical Analysis of Evolutionary Computation on Continuously Differentiable Functions

Youhei Akimoto, Yuichi Nagata, Isao Ono, Shigenobu Kobayashi

constrained minimization, Continuously differentiable functions, local convergence, CMAESs, EDAs

This paper investigates theoretically the convergence properties of the stochastic algorithms of a class including both CMAESs and EDAs on constrained minimization of continuously differentiable functions. We are interested in algorithms that do not get stuck on a slope of the function, but converge only to local optimal points. Convergence to a point that is neither a stationary point of the function nor a boundary point is evidence that the convergence properties are not well behaved. We investigate what properties are necessary/sufficient for the algorithm to avoid this type of behavior, i.e., what properties are necessary for the algorithm to converge only to local optimal points of the function. We also investigate the analogous conditions on the parameters of two variants of modern EC-based stochastic algorithms, namely, a CMAES employing rank-μ update and an EDA known as EMNAglobal. The comparison between the apparently similar two systems shows that they have significantly different theoretical behaviors. This result presents us with an insight into the way we design well-behaved optimization algorithms.

14:50-15:15 Elementary Landscape Decomposition of the Quadratic Assignment Problem

Francisco Chicano, Gabriel Luque, Enrique Alba

Fitness Landscapes, Elementary Landscapes, Quadratic Assignment Problem

The Quadratic Assignment Problem (QAP) is a well-known NP-hard combinatorial optimization problem that is at the core of many real-world optimization problems. We prove that QAP can be written as the sum of three elementary landscapes when the swap neighborhood is used. We present a closed formula for each of the three elementary components and we compute bounds for the autocorrelation coefficient.



Room: Portland

Session Chair: Thomas BartzBeielstein, Thomas Baeck, Erik Goodman

14:00-15:40 Managing an EC project for success, Emerging Technologies





GP Best Paper Nominees: Reliability and Robustness

Room: Salon A

Session Chair: Leonardo Vanneschi (University of Milano-Bicocca)

16:10-16:35 * Abstract Functions and Lifetime Learning in Genetic Programming for Symbolic Regression

R. Muhammad Atif Azad, Conor Ryan

Genetic Programming, Hill Climbing, Lifetime Learning, Symbolic Regression, Linear Scaling

Typically, an individual in Genetic Programming (GP) can not make the most of its genetic inheritance. Once it is mapped, its fitness is immediately evaluated and it survives only until the genetic operators and its competitors eliminate it. Thus, the key to survival is to be born strong. This paper proposes a simple alternative to this powerlessness by allowing an individual to tune its internal nodes and going through several evaluations before it has to compete with other individuals. We demonstrate that this system, Chameleon, outperforms standard GP over a selection of symbolic regression type problems on both training and test sets; that the system works harmoniously with two other well known extensions to GP, that is, linear scaling and a diversity promoting tournament selection method; that it can benefit dramatically from a simple cache; that adding to functions set does not always add to the tuning expense; and that tuning alone can be enough to promote smaller trees in the population. Finally, we touch upon the consequences of ignoring the effects of complexity when focusing on just the tree sizes to induce parsimony pressure in GP populations.

16:35-17:00 * The Estimation of Hölderian Regularity using Genetic Programming

Leonardo Trujillo, Pierrick Legrand, Jacques Levy-Vehel

Signal regularity, Hölder exponent, Genetic Programming

This paper presents a Genetic Programming (GP) approach to synthesize estimators for the pointwise Hölder exponent

in 2D signals. It is known that irregularities and singularities are the most salient and informative parts of a signal. Hence, explicitly measuring these variations can be important in various domains of signal processing. The pointwise Hölder exponent provides a characterization of these types of features. However, current methods for estimation cannot be considered to be optimal in any sense. Therefore, the goal of this work is to automatically synthesize operators that provide an estimation for the Hölderian regularity in a 2D signal. This goal is posed as an optimization problem in which we attempt to minimize the error between a prescribed regularity and the estimated regularity given by an image operator. The search for optimal estimators is then carried out using a GP algorithm. Experiments confirm that the GP-operators produce a good estimation of the Hölder exponent in images of multifractional Brownian motions. In fact, the evolved estimators significantly outperform a traditional method by as much as one order of magnitude. These results provide further empirical evidence that GP can solve difficult problems of applied mathematics.

17:00-17:25 Designing Better Fitness Functions for Automated Program Repair

Ethan Fast, Claire Le Gouse, Stephanie Forrest, Westley Weimer

software repair, genetic programming, software engineering

Evolutionary methods have been used to repair programs automatically, with promising results. However, the fitness function used to achieve these results was based on a few simple test cases and is likely too simplistic for larger programs and more complex bugs. We focus here on two aspects of fitness evaluation: efficiency and precision. Efficiency is an issue because many programs have hundreds of test cases, and it is costly to run each test on every individual in the population. Moreover, the precision of fitness functions based on test cases is limited by the fact that a program either passes a test case, or does not, which leads to a fitness function that can take on only a few distinct values. This paper investigates two approaches to enhancing fitness functions for program repair, incorporating (1) test suite selection to improve efficiency and (2) formal specifications to improve precision. We evaluate test suite selection on 10 programs, improving running time for automated repair by 81%. We evaluate program invariants using the Fitness Distance Correlation (FDC) metric, demonstrating significant improvements and smoother evolution of repairs.



17:25-17:50 Grammar Guided Genetic Programming for Multiple Instance Learning: An Experimental Study

Amelia Zafra, Sebastian Ventura

Multiple Instance Learning, Grammar Guided Genetic Programming, Rule Learning

This paper introduces a new Grammar-Guided Genetic Programming algorithm for solving multi-instance Learning problems. This algorithm, called G3P-MI, is evaluated and compared with other Multi-Instance classification techniques on different application domains. Computational experiments show that the G3P-MI often obtains consistently better results than other algorithms in terms of accuracy, sensitivity and specificity. Moreover, it adds comprehensibility and clarity into the knowledge discovery process, expressing the information in the form of IF-THEN rules. Our results confirm that evolutionary algorithms are appropriate for dealing with multi-instance learning problems.


RWA: Business and Food Science

Room: Salon B

Session Chair: Edgar Galvan-Lopez (Essex University)

16:10-16:35 A New Modular Genetic Programming for Finding AttractiveTechnical Patterns in Stock Markets

Seung-Kyu Lee, Byung-Ro Moon

stocks, patterns, technical patterns, modular genetic programming

We propose a new modular genetic programming for finding attractive and statistically sound technical patterns for stock trading. We restrict the problem space to combinations of modules for more e ective space search. We carefully prepared the set of modules based on existing studies of technical indicators and our own experience. Our modular genetic programming successfully found unknown attractive technical patterns for the Korean stock market. A trading simulation with the generated patterns by a commercial tool showed signi cantly higher accumulative returns than the KOSPI index.

16:35-17:00 Interday Foreign Exchange Trading using Linear Genetic Programming

Garnett Wilson, Wolfgang Banzhaf

foreign exchange markets, computational finance, linear genetic programming, technical analysis

Foreign exchange (forex) market trading using evolutionary algorithms is an active and controversial area of research. We investigate the use of a linear genetic programming (LGP) system for automated forex trading of four major currency pairs. Fitness functions with varying degrees of conservatism through the incorporation of maximum drawdown are considered. The use of the fitness types in the LGP system for different currency value trends are examined in terms of performance over time, underlying trading strategies, and overall profitability. An analysis of trade profitability shows that the LGP system is very accurate at both buying to achieve profit and selling to prevent loss, with moderate levels of trading activity.

17:00-17:25 Evolutionary Optimization of Flavors

Kalyan Veeramachaneni, Katya Vladislavleva, Matt Burland, Jason Parcon, Una-May O' Reilly

Machine Learning, Particle swarm optimization

We have acquired panelist data that provides hedonic (liking) ratings for a set of 40 flavors each composed of the same 7 ingredients at different concentration levels. Our goal is to use this data and predict other flavors, composed of the same ingredients in new combinations, which the panelist will like. We describe how we first employ Pareto-Genetic Programming (GP) to generate a surrogate for the human panelist from the 40 observations. This surrogate, in fact an ensemble of GP symbolic regression models,  can predict liking scores for flavors outside the observations and provide a confidence in the prediction.  We then employ a multi-objective particle swarm optimization (MOPSO) to design a well and consistently liked flavor suite for a panelist. The MOPSO identifies flavors that are well liked, i.e., high liking score, and consistently-liked, i.e., of maximum confidence. Further, we generate flavors that are well and consistently liked by a cluster of panelists, by giving the MOPSO slightly different objectives.

17:25-17:50 Mixed-Integer Evolution Strategy Using Multiobjective Selection Applied to Warehouse Design Optimization

Edgar Reehuis, Thomas Back

Business planning and operations research, evolution strategies, representations, multi-objective optimization, combinatorial optimization

This paper reports about the application of a new variant of multiobjective Mixed-Integer Evolution Strategy to a warehouse design optimization problem. The algorithm is able to deal with real-valued, integer, and discrete nominal input variables in a multiobjective problem, and utilizes a multiobjective selection procedure based on either crowding distance or hypervolume contribution (also called S metric). The warehouse design optimization problem investigated in this study is represented by a warehouse simulator (provided by our collaboration partner) which calculates four warehouse performance measures: total handling time, crate fill rate, order latency, and investment cost. Two of those are treated as objectives, while the other two are represented as constraints. As demonstrated by the results, the algorithm generates solutions which cover the whole Pareto front, as opposed to the expert-generated solutions. Moreover, the algorithm is able to fi nd solutions which improve on the expert-generated solutions with respect to both objectives.


SBSE: Requirements and Design

Room: Salon C

Session Chair: Myra Cohen (University of Nebraska-Lincoln)

16:10-16:35 Approximate Backbone Based Multilevel Algorithm for Next Release Problem

He Jiang, Jifeng Xuan, Zhilei Ren

Next Release Problem (NRP), Multilevel Algorithm, Requirement Engineering, Approximate Backbone

The next release problem (NRP) aims to effectively select software requirements in order to acquire maximum customer profits. As an NP-hard problem in software requirement engineering, NRP lacks efficient approximate algorithms for large scale instances. The backbone is a new tool for tackling large scale NP-hard problems in recent years. In this paper, we employ the backbone to design high performance approximate algorithms for large scale NRP instances. Firstly we show that it is NP-hard to obtain the backbone of NRP. Then, we illustrate by fitness landscape analysis that the backbone can be well approximated by the shared common parts of local optimal solutions. Therefore, we propose an approximate backbone based multilevel algorithm (ABMA) to solve large scale NRP instances. This algorithm iteratively explores the search spaces by multilevel reductions and refinements. Experimental results demonstrate that ABMA outperforms existing algorithms on large instances in terms of solution quality and running time.

16:35-17:00 Today/Future Importance Analysis

Yuanyuan Zhang, Enrique Alba, Juan J. Durillo, Sigrid Eldh, Mark Harman

Pareto optimality, Today/Future, multi-objective genetic algorithms

SBSE techniques have been widely applied to requirements selection and prioritization problems in order to ascertain a suitable set of requirements for the next release of a system. Unfortunately, it has been widely observed that requirements tend to be changed as the development process proceeds and what is suitable for today, may not serve well into the future. Though SBSE has been widely applied to requirements analysis, there has been no previous work that seeks to balance the requirements needs of today with those of the future. This paper addresses this problem. It introduces a multi-objective formulation of the problem which is implemented using multi-objective Pareto optimal evolutionary algorithms. The paper presents the results of experiments on both synthetic and real world data.


17:00-17:25 Superstate Identification for State Machines Using Search-Based Clustering

Mathew Hall, Phil McMinn, Neil Walkinshaw

state machines, search-based clustering, hill-climbing, Bunch

State machines are a popular method of representing a system at a high level of abstraction that enables developers to gain an overview of the system they represent and quickly understand it. Several techniques have been developed to reverse engineer state machines from software, so as to produce a concise and up-to-date document of how a system works. However, the machines that are recovered are usually flat and contain a large number of states. This means that the abstract picture they are supposed to provide is often itself very complex, requiring effort to understand. This paper proposes the use of search-based clustering as a means of overcoming this problem. Clustering state ma- chines opens up the possibility of recovering the structural hierarchy of a state machine, such that superstates may be identified. An evaluation study is performed using the Bunch search-based clustering tool, which demonstrates the usefulness of the approach.


ACO-SI: Particle Swarm Optimization II

Room: Salon D

Session Chair: Carlos A. Coello Coello (CINVESTAV-IPN)

16:10-16:35 Particle Swarm Optimizer with Self-adjusting Neighborhoods

Ziyu Chen, Zhongshi He, Cheng Zhang

Particle Swarm Optimization, Neighborhood Topology, Neighborhood Extension.

Aiming to keep a balance between exploration and exploitation capability, the paper presents a particle swarm optimizer with self-adjusting neighborhoods (PSOSN). In the new algorithm, the particles are initially arranged in ring topology and then automatically adjust their own neighborhood structure based on novel neighborhood extension and restriction strategies. For efficiently controlling the process of information diffusion, neighborhood extension factor (NEF) and local impact factor (LIF) are introduced to depict particle s extension state and neighborhood relation, respectively. The experiment results demonstrate good performance of PSOSN on five benchmark functions compared with the PSO algorithms using different neighborhood schemes.

16:35-17:00 Stigmergic Landmark Routing

Nyree Lemmens, Karl Tuyls

Wireless Mobile Ad-hoc Routing, Multi-Agent Systems, Swarm Intelligence, Bee Colony Optimization

Mobile Ad-hoc Networks (MANETs) pose a challenging problem to routing protocols. They consist of nodes with high mobility and there is no preset infrastructure available. Instead, connections are set-up wirelessly and the radio range is limited. Therefore, each node only perceives its local environment and has no complete information about the rest of the network. Moreover, an ad-hoc created infrastructure between nodes is temporary. Due to node mobility and antenna range, nodes may become unreachable. Nodes are also limited in resources, e.g., battery power and memory. Despite these properties, routing protocols are still able to route in MANETs. However, there is a cost involved. Routing efforts may experience high end-to-end delay, low scalability, and low average performance. In this paper we present a novel Swarm Intelligence routing algorithm for Wireless Mobile Ad-hoc Networks, named Stigmergic Landmark Routing (SLR). It is inspired by the behavior of bees and uses the concept of landmarks to indicate key nodes which store routing information. Consequently, little routing information needs to be stored and maintained in the network. This results in a significant performance increase when compared to state of the art algorithms in networks up to 100 nodes with multiple data sources.



17:00-17:25 Self-Adaptive Differential EvolutionBased on PSO Learning Strategy

Zhi-Hui Zhan, Jun Zhang

Differential evolution (DE), particle swarm optimization (PSO), learning strategy, parameter adaptation.

Differential evolution (DE) is an effective and efficient optimization algorithm that has been successfully applied to many problems. However, the DE performance significantly depends on the elaborate settings of its parameters. Designers of DE usually spend great efforts to find proper parameter settings because good parameter values usually vary with different problems. In order to enhance the efficiency and robustness of DE, this paper proposes a novel DE algorithm, PLADE, which uses the learning mechanism in particle swarm optimization (PSO), termed as PSO-Learning (PL) strategy, to adaptively control the DE parameters. PLADE encodes the DE parameters into each individual and evolve the parameters during the evolutionary process. The individuals that achieve good fitness and survive in the evolution imply good parameter settings, the poor individuals use the PL strategy to let their parameters learn from the parameters in the good individuals. With such a PL based parameter self-adaptation strategy, PLADE can evolve the parameters to better values and can adapt the parameters to match the requirements of different evolutionary states and different optimization problems. PLADE is tested by six benchmark functions with unimodal and multimodal characteristics. Experimental results show that PLADE not only outperforms conventional DE with fixed parameter settings, in terms of solution quality, convergence speed, and algorithm reliability, but also is better than or at least comparable to some other state-of-the-art adaptive DE variants.


EMO: Applications and Algorithms

Room: Salon G

Session Chair: Joshua D Knowles (University of Manchester)

16:10-16:35 Deterministic Helper-Objective Sequences Applied to Job-Shop Scheduling

Darrell F Lochtefeld, Frank W Ciarallo

Multi-objectivization, Helper-objective, Non-dominated Sorting Genetic Algorithm version II (NSGAII), Epistasis, Genetic Algorithms (GA), Evolutionary Algorithms (EA), Multiple Objective Evolutionary Algorithms (MOEA)

A Multiple Objective Evolutionary Algorithm (MOEA) applied to the Job-Shop Scheduling Problem has been shown in the past to perform better than a single objective Genetic Algorithm (GA). Helper-objectives, representing portions of the main objective, were used in the past to guide the MOEA search process. This paper explores additional understanding of helper-objective sequencing. The sequence in which helper-objectives are used is examined and it is shown that problem specific knowledge can be incorporated to determine a good helper-objective sequence. Results demonstrate how carefully sequenced helper-objectives can improve search quality. Explanations are provided for how helpers accelerate the search process by distinguishing between otherwise similar solutions and by partial removal of epistasis in one or more dimensions. Good helper-objective sequence appears to break epistasis early in a search which implies that it is important for helper-objective methods to examine the sequence of objectives.

16:35-17:00 Finding Multiple Solutions for Multimodal Optimization Problems Using a Multi-Objective Evolutionary Approach

Kalyanmoy Deb, Amit Saha

Multimodal optimization, multi-objective optimization, NSGA-II, Hooke-Jeeve's exploratory search

In a multimodal optimization task, the main purpose is to find multiple optimal (global and local) solutions associated with a single objective function. Starting with the preselection method suggested in 1970, most of the existing evolutionary  algorithms based methodologies employ variants of niching in an existing single-objective evolutionary algorithm framework so that similar solutions in a population are de-emphasized in order to focus and maintain multiple distant yet near-optimal solutions. In this paper, we use a completely different and generic strategy in which a single-objective multimodal optimization problem is converted into a suitable bi-objective optimization problem so that all local and global optimal solutions become members of the resulting weak Pareto-optimal set. We solve up to 16-variable test-problems having as many as 48 optima and also demonstrate successful results on constrained multimodal test-problems, suggested  for the first time. The concept of using multi-objective optimization for solving single-objective multimodal  problems seems novel and interesting, and importantly  opens further avenues for research.


17:00-17:25 Improved Step Size Adaptation for the MO-CMA-ES

Thomas Voß, Nikolaus Hansen, Christian Igel

multi-objective optimization, step size adaptation, covariance matrix adaptation, evolution strategy, MO-CMA-ES

The multi-objective covariance matrix adaptation evolution strategy (MO-CMA-ES) is an evolutionary algorithm for continuous vector-valued optimization. It combines indicator-based selection based on the contributing hypervolume with the efficient strategy parameter adaptation of the elitist covariance matrix adaptation evolution strategy (CMA-ES). Step sizes (i.e., mutation strengths) are adapted on individual-level using an improved implementation of the 1/5-th success rule. In the original MO-CMA-ES, a mutation is regarded as successful if the offspring ranks better than its parent in the elitist, rank-based selection procedure. In contrast, we propose to regard a mutation as successful if the offspring is selected into the next parental population. This criterion is easier to implement and reduces the computational complexity of the MO-CMA-ES,  in particular of its steady-state variant. The new step size adaptation improves the performance of the MO-CMA-ES as shown empirically using a large set of benchmark functions. The new update scheme in general leads to larger step sizes and thereby counteracts premature convergence. The experiments comprise the first evaluation f the MO-CMA-ES for problems with more than two objectives.

17:25-17:50 Evolving Agent Behavior In Multiobjective Domains Using Fitness-Based Shaping

Jacob Schrum, Risto Miikkulainen

Multi-objective optimization, Neural networks, Multi-agent systems, Shaping

Multiobjective evolutionary algorithms have long been applied to engineering problems. Lately they have also been used to evolve behaviors for intelligent agents. In such applications, it is often necessary to "shape" the behavior via increasingly difficult tasks. Such shaping requires extensive domain knowledge. An alternative is fitness-based shaping through changing selection pressures, which requires little to no domain knowledge. Two such methods are evaluated in this paper. The first approach, Targeting Unachieved Goals, dynamically chooses when an objective should be used for selection based on how well the population is performing in that objective. The second method, Behavioral Diversity, adds a behavioral diversity objective to the objective set. These approaches are implemented in the popular multiobjective evolutionary algorithm NSGA-II and evaluated in a multiobjective battle domain. Both methods outperform plain NSGA-II in evolution time and final performance, but differ in the profiles of final solution populations. Therefore, both methods should allow multiobjective evolution to be more extensively applied to various agent control problems in the future.


Theory: New Search Heuristics

Room: Salon I

Session Chair: Thomas Jansen (University College Cork)

16:10-16:35 Ant Colony Optimization and the Minimum Cut Problem

Timo Kotzing, Per Kristian Lehre, Frank Neumann, Pietro Simone Oliveto

Ant Colony Optimization, Min-cut

Ant Colony Optimization (ACO) is a powerful metaheuristic for solving combinatorial optimization problems. With this paper we contribute to the theoretical understanding of this kind of algorithm by investigating the classical minimum cut problem. An ACO algorithm similar to the one that was proved successful for the minimum spanning tree problem is studied. Using rigorous runtime analyses we show how the ACO algorithm behaves similarly to Karger and Stein's algorithm for the minimum cut problem as long as the use of pheromone values is limited. Hence optimal solutions are obtained in expected polynomial time. On the other hand, we show that high use of pheromones has a negative effect, and the ACO algorithm may get trapped in local optima resulting in an exponential runtime to obtain an optimal solution. This result indicates that ACO algorithms may be inappropriate for finding minimum cuts.


16:35-17:00 Quasirandom Evolutionary Algorithms

Benjamin Doerr, Mahmoud Fouz, Carsten Witt

Quasirandomness, Evolutionary Algorithms

Motivated by recent successful applications of the concept of quasirandomness, we investigate to what extent such ideas can be used in evolutionary computation. To this aim, we propose different variations of the classical (1+1) evolutionary algorithm, all imitating the property that the (1+1) EA over intervals of time touches all bits roughly the same number of times. We prove bounds on the optimization time of these algorithms for the simple OneMax function. Surprisingly, none of the algorithms achieves the seemingly obvious reduction of the runtime from θ(n log n) to O(n). On the contrary, one may even need Ω (n2) time. However, we also find that quasirandom ideas, if implemented correctly, can yield an over 50\, \% speed-up.

17:00-17:25 Can Quantum Search Accelerate Evolutionary Algorithms?

Daniel Johannsen, Piyush P Kurur, Johannes Lengler

Running time analysis, Quantum Algorithm, Theory

In this article, we formulate for the first time the notion of a quantum evolutionary algorithm. In fact we define a quantum analogue for any elitist (1+1) randomized search heuristic. The quantum evolutionary algorithm, which we call (1+1) quantum evolutionary algorithm (QEA), is the quantum version of the classical (1+1) evolutionary algorithm (EA), and runs only on a quantum computer. It uses Grover search to accelerate the search for improved offsprings. To understand the speedup of the (1+1) QEA over the (1+1) EA, we study the three well known pseudo-Boolean optimization problems OneMax, LeadingOnes, and Dis-crepancy. We show that although there is a speedup in the case of OneMax and LeadingOnes in the quantum setting, the speedup is less than quadratic. For Discrep-ancy, we show that the speedup is at best constant. The reason for this inconsistency is due to the difference in the probability of making a successful mutation. On the one hand, if the probability of making a successful mutation is large then quantum acceleration does not help much. On the other hand, if the probabilities of making a successful mutation is small then quantum enhancement indeed helps.


GDS: Best Paper Nominees

Room: Portland

Session Chair: Jeff Clune (Michigan State University)

16:10-16:35 * The Baldwin Effect in Developing Neural Networks

Keith L. Downing, None None, none none

Baldwin Effect, Genetic Algorithm, Neural Network

The Baldwin Effect is a very plausible, but unproven, biological theory concerning the power of learning to accelerate evolution. Simple computational models in the 1980's gave the first constructive proof of its potential existence, and subsequent work in evolutionary computation has shown the practical, computational, advantages of hybrid evolution-learning systems . However, the basic theory, particularly its second phase (involving genetic assimilation of acquired characteristics) is difficult to reconcile in systems controlled by neural networks, particularly those that arise from their genotypes via a complex developmental process. Our research uses new evidence of the blurred distinction between development and learning in natural neural systems as the basis for an abstract model displaying the Baldwin Effect in artificial neural networks that evolve, develop and learn.



16:35-17:00 * Task Transfer through Indirect Encoding

Phillip Verbancsics, Kenneth O. Stanley

Generative and Developmental Systems, Artifical Neural Networks, Task Transfer, RoboCup Soccer

An important goal for the generative and developmental systems (GDS) community is to show that GDS approaches can compete with more mainstream approaches in machine learning (ML). One popular ML domain is RoboCup and its subtasks (e.g. Keepaway). This paper shows how a GDS approach called HyperNEAT competes with the best results to date in Keepaway. Furthermore, a significant advantage of GDS is shown to be in transfer learning. For example, playing Keepaway should contribute to learning the full game of soccer. Previous approaches to transfer have focused on transforming the original representation to fit the new task. In contrast, this paper explores transfer with a representation designed to be the same even across different tasks. A bird's eye view (BEV) representation is introduced that can represent different tasks on the same two-dimensional map. Yet the problem is that a raw two-dimensional map is high-dimensional and unstructured. The problem is addressed naturally by indirect encoding, which compresses the representation in HyperNEAT by exploiting its geometry. The result is that the BEV learns a Keepaway policy that transfers from two different training domains without further learning or manipulation. The results in this paper thus show the power of GDS versus other ML methods.

17:00-17:25 * Image Compression of Natural Images Using Artificial Gene Regulatory Networks

Martin A. Trefzer, Tuze Kuyucu, Julian F. Miller, Andy M. Tyrrell

gene regulatory network, GRN, artificial development, image compression, GCI, evolutionary computation, artificial developmental system, ADS

A novel approach to image compression using a gene regulatory network (GRN) based artificial developmental system (ADS) is introduced. The proposed algorithm exploits the fact that a series of complex organisms (= developmental states) can be represented via a GRN description and the indices of the developmental steps in which they occur. Organisms are interpreted as tiles of an image at each developmental step which results in the (re-)construction of an image during the developmental process. It is shown that GRNs are suitable for image compression and achieve higher compression rates than JPEG when optimised for a particular image. It is also shown that the same GRN has the potential to encode multiple images, each represented by a different series of numbers of developmental steps.

17:25-17:50 * Evolving the Placement and Density of Neurons in the HyperNEAT Substrate

Sebastian Risi, Joel Lehman, Kenneth O. Stanley

Substrate Evolution, NEAT, HyperNEAT, Neuroevolution

The Hypercube-based NeuroEvolution of Augmenting Topologies (HyperNEAT) approach demonstrated that the pattern of weights across the connectivity of an artificial neural network (ANN) can be generated as a function of its geometry, thereby allowing large ANNs to be evolved for high-dimensional problems. Yet it left to the user the question of where hidden nodes should be placed in a geometry that is potentially infinitely dense. To relieve the user from this decision, this paper introduces an extension called evolvable-substrate HyperNEAT (ES-HyperNEAT) that determines the placement and density of the hidden nodes based on a quadtree-like decomposition of the hypercube of weights and a novel insight about the relationship between connectivity and node placement. The idea is that the representation in HyperNEAT that encodes the pattern of connectivity across the ANN contains implicit information on where the nodes should be placed and can therefore be exploited to avoid the need to evolve explicit placement. In this paper, as a proof of concept, ES-HyperNEAT discovers working placements of hidden nodes for a simple navigation domain on its own, thereby eliminating the need to configure the HyperNEAT substrate by hand and suggesting the potential power of the new approach.



   Saturday 10 July 14:00 - 15:40



EMO: Best Paper Nominees

Room: Salon A

Session Chair: Carlos A. Coello Coello (CINVESTAV-IPN)

10:40-11:05 * Integrating Decision Space Diversity into Hypervolume-based Multiobjective Search

Tamara Ulrich, Johannes Bader, Eckart Zitzler

Multiobjective Optimization, Diversity in Decision Space, Hypervolume Indicator

Multiobjective optimization in general aims at learning about the problem at hand. Usually the focus lies on objective space properties such as the front shape and the distribution of optimal solutions. However, structural characteristics in the decision space can also provide valuable insights. In certain applications, it may even be more important to find a structurally diverse set of close-to-optimal solutions than to identify a set of optimal but structurally similar solutions. Accordingly, multiobjective optimizers are required that are capable of considering both the objective space quality of a Pareto-set approximation and its diversity in the decision space. Although NSGA, one of the first multiobjective evolutionary algorithms, explicitly considered decision space diversity, only a few other studies address that issue. It therefore is an open research question how modern multiobjective evolutionary algorithms can be adapted to search for structurally diverse high-quality Pareto-set approximations. To this end we propose an approach to integrate decision space diversity into hypervolume-based multiobjective search. We present a modified hypervolume indicator and integrate it into an evolutionary algorithm. The proof-of-principle results show the potential of the approach and indicate further research directions for structure-oriented multiobjective search.

11:05-11:30 * A Grid-Based Fitness Strategy for Evolutionary Many-Objective Optimization

Miqing Li, Jinhua Zheng, Ruimin Shen, Ke Li, Qizhao Yuan

Multiobjective optimization, many-objective optimization, fitness assignment, grid

Grid has been widely used in the field of evolutionary multi-objective optimization (EMO) due to its property combining convergence and diversity naturally. Most EMO algorithms of grid-based fitness perform well on problems with two or three objectives, but encounter difficulties in their scalability to many-objective optimization. This paper develops the potential of using grid technique to balance convergence and diversity in fitness for many-objective optimization problems. To strengthen selection pressure and refine comparison level, three hierarchical grid-based criterions are incorporated into fitness to establish a completer order among individuals. Moreover, an adaptive fitness penalty mechanism in environmental selection is employed to guarantee the diversity of archive memory. Based on an extensive comparative study with three other EMO algorithms, the proposed algorithm is found to be remarkably successful in finding well-converged and well-distributed solution set.

11:30-11:55 * The Maximum Hypervolume Set Yields Near-optimal Approximation

Karl Bringmann, Tobias Friedrich

Multiobjective Optimization, Performance Measures, Hypervolume Indicator, Approximation

In order to allow a comparison of (otherwise incomparable) sets, many evolutionary multiobjective optimizers use indicator functions to guide the search and to evaluate the performance of search algorithms. The most widely used indicator is the hypervolume indicator. It measures the volume of the dominated portion of the objective space. Though the hypervolume indicator is very popular, it has not been shown that maximizing the hypervolume indicator is indeed equivalent to the overall objective of finding a good approximation of the Pareto front. To address this question, we compare the optimal approximation factor with the approximation factor achieved by sets maximizing the hypervolume indicator. We bound the optimal approximation factor of n points by 1+θ(1/n) for arbitrary Pareto fronts. Furthermore, we prove that the same asymptotic approximation ratio is achieved by sets of n points that maximize the hypervolume indicator. This shows that the speed of convergence of the approximation ratio achieved by maximizing the hypervolume indicator is asymptotically optimal. This implies that for large values of n, sets maximizing the hypervolume indicator quickly approach the optimal approximation ratio. Moreover, our bounds show that also for relatively small values of n, sets maximizing the hypervolume indicator achieve a near-optimal approximation ratio.


11:55-12:20 DBSCAN Based Multi-Objective Niching to Approximate Equivalent Pareto-Subsets

Oliver Kramer, Holger Danielsiek

Hybrid Evolutionary Multiobjective Algorithm, Local Search,  Memetic Algorithms, Hybrid Metaheuristics

In systems optimization and machine learning multiple alternative solutions may exist in different parts of decision space for the same parts of the Pareto-front. The detection of equivalent Pareto-subsets may be desirable. In this paper we introduce a niching method that approximates Pareto-optimal solutions with diversity mechanisms in objective and decision space. For diversity in objective space we use rake selection, a selection method based on the distances to reference lines in objective space. For diversity in decision space we introduce a niching approach that uses the density based clustering method DBSCAN. The clustering process assigns the population to niches while the multi-objective optimization process concentrates on each niche independently. We introduce an indicator for the adaptive control of clustering processes, and extend rake selection by the concept of adaptive corner points. The niching method is experimentally validated on parameterized test function with the help of the S-metric.


EDA: Best Paper Nominees and Multimodal EDAs

Room: Salon B

Session Chair: Peter A.N. Bosman (Centre for Mathematics and Computer Science)

10:40-11:05 * Effective Structure Learning for EDA via L1-RegularizedBayesian Networks

Jiadong Yang, Hua Xu, Yunpeng Cai, Peifa Jia

Bayesian optimization algorithm, Bayesian network, L1-penalized regression, Regularization paths, estimation of distribution algorithms

The Bayesian optimization algorithm (BOA) uses Bayesian networks to explore the dependencies between decision variables of an optimization problem in pursuit of both faster speed of convergence and better solution quality. In this paper, a novel method that learns the structure of Bayesian networks for BOA is proposed. The proposed method, called L1BOA, uses L1-regularized regression to find the candidate parents of each variable, which leads to a sparse but nearly optimized network structure. The proposed method improves the efficiency of the structure learning in BOA due to the reduction and automated control of network complexity introduced with L1-regularized learning. Experimental studies on different types of benchmark problems are carried out, which show that L1BOA outperforms the standard BOA when no a-priori knowledge about the problem structure is available, and nearly achieves the best performance of BOA that applies explicit complexity controls.

11:05-11:30 * Entropy-Based Substructural Local Search for the Bayesian Optimization Algorithm

Hoang N. Luong, Hai T.T. Nguyen, Chang Wook Ahn

Bayesian optimization algorithm, Estimation of distribution algorithm, Efficiency enhancement, Entropy measurement, Local/Global search hybridization

A customary paradigm of designing a competent optimization algorithm is to combine an effective global searcher with an efficient local searcher. This paper presents and analyzes an entropy-based substructural local search method (eSLS) for the Bayesian Optimization Algorithm (BOA). The local searcher (the mutation operator) explores the substructural neighborhood areas defined by the probabilistic model encoded in the Bayesian network. The improvement of each local search step can be estimated by considering the variation this mutation causes to the entropy measurement of the population. Experiments show that incorporating BOA with eSLS results in a substantial reduction in the number of costly fitness evaluations until convergence. Moreover, this paper provides original insights into how the randomness of populations can be exploited to enhance the performance of optimization processes.



11:30-11:55 * The Anticipated Mean Shift and Cluster Registration in Mixture-based EDAs for Multi-Objective Optimization

Peter A.N. Bosman

Estimation of Distribution Algorithms, Multi-Objective Optimization, Mixture Distribution, Anticipation

It is known that in real-valued Single-Objective (SO) optimization with Gaussian Estimation-of-Distribution Algorithms (EDAs), it is important to take into account how distribution parameters change in subsequent generations to prevent inefficient convergence as a result of overfitting, especially if dependencies are modelled. We illustrate that in Multi-Objective (MO) optimization the risk of overfitting is even larger and only further increased if clustered variation is used, a technique often employed in Multi-Objective EDAs (MOEDAs) in the form of mixture modelling via clustering selected solutions in objective space. We point out that a technique previously used in EDAs to remove the risk of overfitting for SO optimization, the anticipated mean shift (AMS), can also be used in MO optimization if clusters in subsequent generations are registered. We propose to compute this registration explicitly. Although computationally more intensive than existing approaches, the effectiveness of AMS is thereby increased. We further propose a new clustering technique to improve mixture modelling in EDAs by 1) allowing clusters to overlap substantially and 2) assigning each cluster the same number of solutions. This allows any existing EDA to be transformed into a mixture-based version straightforwardly. Finally, we point out the benefit of injecting solutions obtained from running equal-capacity SO optimizers in synchronous parallel and investigate experimentally, using 9 well-known benchmark problems, the advantages of each of the techniques.

11:55-12:20 Multivariate Multi-Model Approach for Globally Multimodal Problems

Chung-Yao Chuang, Wen-Lian Hsu

Estimation of distribution algorithms, EDAs, Global multimodality, Globally multimodal problems, Marginal product models, Multi-model approach, Extended compact genetic algorithm, ECGA, Genetic algorithms, Evolutionary algorithms, Evolutionary computation

This paper proposes an estimation of distribution algorithm (EDA) aiming at addressing globally multimodal problems, i.e., problems that present several global optima. It can be recognized that many real-world problems are of this nature, and this property generally degrades the efficiency and effectiveness of evolutionary algorithms. To overcome this source of difficulty, we designed an EDA that builds and samples multiple probabilistic models at each generation. Different from previous studies of globally multimodal problems that also use multiple models, we adopt multivariate probabilistic models. Furthermore, we have also devised a mechanism to automatically estimate the number of models that should be employed. The empirical results demonstrate that our approach obtains more global optima per run compared to the well-known EDA that employs the same class of probabilistic models but builds a single model at each generation. Moreover, the experiments also suggest that using multiple models reduces the generations spent to reach convergence.


GA: Parameter Tuning

Room: Salon C

Session Chair: Marc Schoenauer (INRIA Saclay)

10:40-11:05 Applying the Triple Parameter Hypothesis to Maintenance Scheduling

John Crofford, Brent E. Eskridge, Dean F. Hougen

Empirical Study, Evolution Dynamics, Performance Analysis, Working Principles of Evolutionary Computing, Genetic Algorithms, Theory, Parameter Tuning, Schema Theorem

A method for identifying values for a genetic algorithm's probability of crossover, mutation rate, and selection pressure that promote the evolution of better results in fewer generations has recently been proposed. This approach, termed the Triple Parameter Hypothesis, uses schema theory to derive these values. However, in initial experimental tests of the hypothesis, the schema distances used were at the extreme ends of the spectrum. In the work presented here, we evaluate the parameters predicted by the hypothesis in a series of maintenance scheduling experiments which use a schema distance in between these extremes. Results show that evolutionary runs which use parameters that satisfy the hypothesis statistically significantly outperform runs that use parameters that do not satisfy the hypothesis, indicating that the hypothesis can be a general purpose process for identifying "good" parameter values.


11:05-11:30 Optimizing Genetic Operator Rates Using A Markov Chain Model of Genetic Algorithms

Fatemeh Vafaee, Gyorgy Turan, Peter C. Nelson

Operator rate optimization, Genetic Algorithms, Markov chain models of Genetic Algorithms

This work is concerned with proposing a robust framework for optimizing operator rates of simple Genetic Algorithms (GAs) during a GA run. The suggested framework is built upon a formerly proposed GA Markov chain model to estimate the optimal values of the operator rates based on the time and the current state of the evolution. Though the proposed framework has been formalized for optimizing both mutation and crossover rates, in the current paper, we only implemented it as the mutation rate optimizer and kept the crossover rate constant. To demonstrate the efficacy of the proposed algorithm, the method is evaluated using a set of benchmark problems and the outcome is compared with a series of well-known relevant algorithms. The results demonstrate that the newly suggested algorithm significantly outperforms its rivals.

11:30-11:55 An Exploration into Dynamic Population Sizing

Jason E Cook, Daniel R Tauritz

Evolutionary Algorithm, Parameter Control, Population Sizing, Parameterless Evolutionary Algorithm, Optimization

Traditional evolutionary algorithms are powerful problem solvers that have several fixed parameters which require prior specification. Determining good values for any of these parameters can be difficult, as these parameters are generally very sensitive, requiring expert knowledge to set optimally without extensive use of trial and error. Parameter control is a promising approach to achieving this automation and has the added potential of increasing EA performance based on both theoretical and empirical evidence that the optimal values of EA strategy parameters change during the course of executing an evolutionary run. While many methods of parameter control have been published that focus on removing the population size parameter, mu, all hampered by a variety of problems. This paper investigates the benefits of making mu a dynamic parameter and introduces two novel methods for population control. These methods are then compared to state-of-the-art population sizing EAs, exploring the strengths and weaknesses of each.

11:55-12:20 Toward Comparison-based Adaptive Operator Selection

Alvaro Fialho, Marc Schoenauer, Michele Sebag

Parameter Control, Adaptive Operator Selection, ROC Area Under Curve, Multi-Armed Bandits

Adaptive Operator Selection (AOS) turns the impacts of the applications of variation operators into Operator Selection through a Credit Assignment mechanism. However, most Credit Assignment schemes make direct use of the fitness gain between parent and offspring. A first issue is that the Operator Selection technique that uses such kind of Credit Assignment is likely to be highly dependent on the a priori unknown bounds of the fitness function. Additionally, these bounds are likely to change along evolution, as fitness gains tend to get smaller as convergence occurs. Furthermore, and maybe more importantly, a fitness-based credit assignment forbid any invariance by monotonous transformation of the fitness, what is a usual source of robustness for comparison-based Evolutionary Algorithms. In this context, this paper proposes two new Credit Assignment mechanisms, one inspired by the Area Under the Curve paradigm, and the other close to the Sum of Ranks. Using fitness improvement as raw reward, and directly coupled to a Multi-Armed Bandit Operator Selection Rule, the resulting AOS obtain very good performances on both the OneMax problem and some artificial scenarios, while demonstrating their robustness with respect to hyper-parameter and fitness transformations. Furthermore, using fitness ranks as raw reward results in a fully comparison-based AOS with reasonable performances.


RWA: Manufacturing, Scheduling, Timetabling and Robotics

Room: Salon D

Session Chair: Christian Gagne (Informatique WGZ Inc.)

10:40-11:05 Evolutionary Multi-objective Optimization and Decision Making for Selective Laser Sintering

Nikhil Padhye, Kalyanmoy Deb

Multi-objective Optimization, SLS

This paper proposes an integrated approach to arrive at optimal build orientations, simultaneously minimizing surface roughness `Ra' and build time `T', for object manufacturing in SLS process. The optimization task is carried out by two popularly known multi-objective evolutionary optimizers - NSGA-II (non-dominated sorting genetic algorithm) and MOPSO (multi-objective particle swarm optimizer). The performance comparison of these two optimizers along with an approximation of Pareto-optimal front is done using two statistically significant performance measures. Three proposals addressing the task of decision making, i.e. selecting one solution in presence of multiple trade-off solutions, are introduced to facilitate the designer. The overall procedure is integrated into MORPE - Multi-objective Rapid Prototyping Engine. Several sample objects are considered for experimentation to demonstrate the working of MORPE. A careful study of optimal build directions for several components indicates a trend, providing insight into the SLS processes which can be regarded highly useful for various practical RP applications.

11:05-11:30 Evolving Robust Controller Parameters using Covariance Matrix Adaptation

Gerulf K. M. Pedersen, Martin V. Butz

covariance matrix adaptation, evolution strategies, parameter optimization

In this paper, the advantages of introducing an additional amount of tests when evolving parameters for specific purposes is discussed. A set of optimal PID-controller parameters are sought for an exemplary system, which simulates a human-like robotic arm. When evolving the controller parameters, the number of different movements included in the optimization process is varied. By including extra movements to the optimization process, the time it takes to evolve the parameters does increase, but the uncertainty due to noise is correspondingly lowered. Additionally, it is shown that the added movements, which improve robustness of the system, do not significantly lower the overall performance of the resulting system, when utilizing the evolved parameters.

11:30-11:55 Selection Mechanisms in Memory Consideration for Examination Timetabling with Harmony Search

Mohammed Azmi Al-Betar, Ahamad Tajudin Khader, Farhad Nadi

Examination Timetabling, Harmony Search Algorithm, Memory Consideration, Selection Mechanisms

In this paper, three selection mechanisms in memory consideration operator for Examination Timetabling Problem with Harmony Search Algorithm (HSA) are investigated: Random memory consideration which uses a random selection mechanism, global-best memory consideration which uses a selection mechanism inspired by a global best concept of Particle Swarm Optimisation (PSO), and Roulette-Wheel memory consideration which uses the survival for the fittest principle. The HSA with each proposed memory consideration operator is evaluated against a de facto dataset defined by Carter et al., (1996). The results suggest that the HSA with Roulette-Wheel memory consideration can produce good quality solutions. The Results are also compared with those obtained by 6 comparative methods that used Carter dataset demonstrating that the proposed method is able to obtain viable results with some best solutions for two testing datasets.


11:55-12:20 Evolutionary Algorithms in Large-Scale Open Pit Mine Scheduling

Christie Myburgh, Kalyanmoy Deb

Evolutionary optimization, open pit mine scheduling, combinatorial optimization, customized operators

With many years of research and application to real-world problems, evolutionary algorithms (EAs) have solved various problems having thousands of variables, hard heuristic constraints, and complex evaluation procedures. This paper reports another successful application of EAs in open pit mine scheduling. Typically an ore body is discretized as a 3D block model which, depending on factors such as the amount of data obtained, size of deposit, block dimensions etc. can be made up of over one million blocks, thereby requiring an optimization algorithm to handle over a million variables. Open pit mine scheduling is a complex task which is subject to very strict hard geometrical and other practical mining constraints. To the best of our knowledge there are currently no algorithm or software package that can cater for the large number of constraints and sheer scale of the data sets represented by open pit mine scheduling. Most packages are limited in the size of block model and the kind of objective and constraint functions they can efficiently handle. The proposed optimization algorithm and the resulting software (evORElution -- a trademark product of ORElogy) is developed by using the theoretical and fundamental results of evolutionary algorithms and has already been successfully used to produce complex multi-objective schedules for several large open pit iron ore mines involving hundreds of thousands to millions of variables.


GP: Models, Methods and Representations

Room: Salon G

Session Chair: Steven Gustafson (GE Research)

10:40-11:05 Towards an Understanding of Locality in Genetic Programming

Edgar Galvan-Lopez, James McDermott, Michael O'Neill, Anthony Brabazon

Locality, Problem Hardness, Fitness Landscape, Difficulty, Genetic Programming, Neutrality

Locality  how well neighbouring genotypes correspond to neighbouring phenotypes  has been defined as a key element affecting how Evolutionary Computation systems explore and exploit the search space. Locality has been studied empirically using the typical Genetic Algorithm (GA) representation (i.e., bitstrings), and it has been argued that locality plays an important role in EC performance. To our knowledge, there are few explicit studies of locality using the typical Genetic Programming (GP) representation (i.e., tree-like structures). The aim of this paper is to address this important research gap. We extend the genotype-phenotype definition of locality to GP by studying the relationship between genotypes and fitness. We consider a mutation-based GP system applied to two problems which are highly difficult to solve by GP (a multimodal deceptive landscape and a highly neutral landscape). To analyse in detail the locality in these instances, we adopt three popular mutation operators. We analyse the operators genotypic step sizes in terms of three distance measures taken from the specialised literature and in terms of corresponding fitness values. We also analyse the frequencies of different sizes of fitness change.

11:05-11:30 Measuring Bloat, Overfitting and Functional Complexity in Genetic Programming

Leonardo Vanneschi, Mauro Castelli, Sara Silva

Genetic Programming, Bloat, Overfitting, Complexity

Recent contributions clearly show that eliminating bloat in a genetic programming system does not necessarily eliminate overfitting and vice-versa. This fact seems to contradict a common agreement of many researchers known as the minimum description length principle, which states that the best model is the one that minimizes the amount of information needed to encode it. Another common agreement is that overfitting should be, in some sense, related to the functional complexity of the model. The goal of this paper is to define three measures to respectively quantify bloat, overfitting and functional complexity of solutions and show their suitability on a set of test problems including a simple bidimensional symbolic regression test function and two real-life multidimensional regression problems. The experimental results are encouraging and should pave the way to further investigation. Advantages and drawbacks of the proposed measures are discussed, and ways to improve them are suggested. In the future, these measures should be useful to study and better understand the relationship between bloat, overfitting and functional complexity of solutions.


11:30-11:55 Object-Level Recombination of Commodity Applications

Blair Foster, Anil Somayaji

genetic algorithms, genetic programming, software recombination, ObjRecombGA, object-level recombination, commodity programs

This paper presents ObjRecombGA, a genetic algorithm framework for recombining related programs at the object file level. A genetic algorithm guides the selection of object files, while a robust link resolver allows working program binaries to be produced from the object files derived from two ancestor programs. Tests on compiled C programs, including a simple web browser and a well-known 3D video game, show that functional program variants can be created that exhibit key features of both ancestor programs. This work illustrates the feasibility of applying evolutionary techniques directly to commodity applications.

11:55-12:20 Robust Symbolic Regression with Affine Arithmetic

Cassio L Pennachin, Moshe Looks, João A Vasconcelos

Symbolic regression, Affine arithmetic, Robustness

We use affine arithmetic to improve both the performance and the robustness of genetic programming for symbolic regression. During evolution, we use affine arithmetic to analyze expressions generated by the genetic operators,  estimating their output range given the ranges of their inputs over the training data. These estimated output ranges allow us to discard trees that contain asymptotes as well as those whose output is too far from the desired output range determined by the training instances. We also perform linear scaling of outputs before fitness evaluation. Experiments are performed on 15 problems, comparing the proposed system with a baseline genetic programming system with protected operators, and with a similar system based on interval arithmetic. Results show that integrating affine arithmetic with an implementation of standard genetic programming reduces the number of fitness evaluations during training and improves generalization performance, minimizes overfitting, and completely avoids extreme errors on unseen test data.


GDS: HyperNEAT & Related Algorithms

Room: Portland

Session Chair: Julian F. Miller (University of York)

10:40-11:05 Evolving Neural Networks in Compressed Weight Space

Jan Koutnik, Faustino Gomez, Juergen Schmidhuber

evolutionary algorithms, recurrent neural networks, neuroevolution, indirect encoding

We propose a new indirect encoding scheme for neural networks in which the weight matrices are represented in the frequency domain by sets Fourier coefficients. This scheme xploits spatial regularities in the matrix to reduce the dimensionality of the representation by ignoring high-frequency coefficients, as is done in lossy image compression. We compare the efficiency of searching in this "compressed" network space to searching in the space of directly encoded networks, using the CoSyNE neuroevolution algorithm on three benchmark problems: pole-balancing, ball throwing and octopus arm control. The results show that this encoding can dramatically reduce the search space dimensionality such that solutions can be found in significantly fewer evaluations.


11:05-11:30 Neuroevolution of Mobile Ad Hoc Networks

David B. Knoester, Heather J. Goldsby, Philip K. McKinley

Neuroevolution, neural network, generative, developmental, mobile ad-hoc networks, distributed systems

This paper describes a study of the evolution of distributed behavior, specifically the control of agents in a mobile ad hoc network, using neuroevolution. In neuroevolution, a population of artificial neural networks (ANNs) are subject to mutation and natural selection. For this study, we compare three different neuroevolutionary systems: a direct encoding, an indirect encoding, and an indirect encoding that supports heterogeneity. Multiple variations of each of these systems were tested on a problem where agents were able to coordinate their collective behavior. Specifically, movement of agents in a simulated physics environment affected which agents were able to communicate with each other. The results of experiments indicate that this is a challenging problem domain for neuroevolution, and although direct and indirect encodings tended to perform similarly in our tests, the strategies employed by indirect encodings tended to favor stable, cohesive groups, while the direct encoding versions appeared more stochastic in nature.

11:30-11:55 Evolving CPPNs to Grow Three-Dimensional Physical Structures

Joshua E Auerbach, Josh C Bongard

Evolutionary robotics, Generative and developmental systems

The majority of work in the field of evolutionary robotics concerns itself with evolving control strategies for human designed or bio-mimicked robot morphologies. However, there are reasons why co-evolving morphology along with control may provide a better path towards realizing intelligent agents. Towards this goal, a novel method for evolving three-dimensional physical structures using CPPN-NEAT is introduced which is capable of producing artifacts that capture the non-obvious yet close relationship between function and physical structure. Moreover, it is shown how more fit solutions can be achieved with less computational effort by using growth and environmental CPPN input parameters as well as incremental changes in resolution.

11:55-12:20 Investigating Whether HyperNEAT Produces Modular Neural Networks

Jeff Clune, Benjamin E Beckmann, Philip K McKinley, Charles Ofria

Artificial Neural Networks, Generative Encodings, Neuroevolution, HyperNEAT, Modularity, Developmental Encodings, Indirect Encodings, NEAT

HyperNEAT represents a class of neuroevolutionary algorithms that captures some of the power of natural development with a computationally efficient high-level abstraction of development. This class of algorithms is intended to provide many of the desirable properties produced in biological phenotypes by natural developmental processes, such as regularity, modularity and hierarchy. While it has been previously shown that HyperNEAT produces regular artificial neural network (ANN) phenotypes, in this paper we investigated the open question of whether HyperNEAT can produce modular ANNs. We conducted such research on problems where modularity should be beneficial, and found that HyperNEAT failed to generate modular ANNs. We then imposed modularity on HyperNEAT s phenotypes and its performance improved, demonstrating that modularity increases performance on this problem. We next tested two techniques to encourage modularity in HyperNEAT, but did not observe an increase in either modularity or performance. Finally, we conducted tests on a simpler problem that requires modularity and found that HyperNEAT was able to rapidly produce modular solutions that solved the problem. We therefore present the first documented case of HyperNEAT producing a modular phenotype, but our inability to encourage modularity on harder problems where modularity would have been beneficial suggests that more work is needed to increase the likelihood that HyperNEAT and similar algorithms produce modular ANNs in response to challenging, decomposable problems.



Room: Salem

Session Chair: Jorn Mehnen

10:40-12:20 EC in Design




ESEP: Best Paper Nominees

Room: Salon A

Session Chair: Anne Auger (INRIA)

14:00-14:25 * Exponential Natural Evolution Strategies

Tobias Glasmachers, Tom Schaul, Yi Sun, Daan Wierstra, Jürgen Schmidhuber

evolution strategies, natural gradient, black box optimization, unconstrained optimization

The family of natural evolution strategies (NES) offers a principled approach to real-valued evolutionary optimization by following the natural gradient of the expected fitness. Like the well-known CMA-ES, the most competitive algorithm in the field, NES comes with important invariance properties. In this paper, we introduce a number of elegant and efficient improvements of the basic NES algorithm. First, we propose to parameterize the positive definite covariance matrix using the exponential map, which allows the covariance matrix to be updated in a vector space. This new technique makes the algorithm completely invariant under linear transformations of the underlying search space, which was previously achieved only in the limit of small step sizes. Second, we compute all updates in the natural coordinate system, such that the natural gradient coincides with the vanilla gradient. This way we avoid the computation of the inverse Fisher information matrix, which is the main computational bottleneck of the original NES algorithm. Our new algorithm, exponential NES (xNES), is significantly simpler than its predecessors. We show that the various update rules in CMA-ES are closely related to the natural gradient updates of xNES. However, xNES is more principled than CMA-ES, as all the update rules needed for covariance matrix adaptation are derived from a single principle. We empirically assess the performance of the new algorithm on standard benchmark functions.

14:25-14:50 * On the Analysis of Self-Adaptive Evolution Strategies on Elliptic Model: First Results

Alexander Melkozerov, Hans-Georg Beyer

Evolution strategy, elliptic model, self-adaptation, progress rate, mutation strength

In this paper, first results on the analysis of self-adaptive evolution strategies (ES) with intermediate multirecombination on the elliptic model are presented. Equations describing the ES behavior on the ellipsoid will be derived using a deterministic approach and experimentally verified. A relationship between newly obtained formulae for the elliptic model and previous theoretical results will be discussed.

14:50-15:15 * Adaptive Strategy Selection in Differential Evolution

Wenyin Gong, Alvaro Fialho, Zhihua Cai

Differential Evolution, Strategy Adaptation, Adaptive Strategy Selection, Probability Matching

Differential evolution (DE) is a simple yet powerful evolutionary algorithm for global numerical optimization. Different strategies have been proposed for the offspring generation; but the selection of which of them should be applied is critical for the DE performance, besides being problem-dependent. In this paper, the probability matching technique is employed in DE to autonomously select the most suitable strategy while solving the problem. Four credit assignment methods, that update the known performance of each strategy based on the relative fitness improvement achieved by its recent applications, are analyzed. To evaluate the performance of our approach, thirteen widely used benchmark functions are used. Experimental results confirm that our approach is able to adaptively choose the suitable strategy for different problems. Compared to classical DE algorithms and to a recently proposed adaptive scheme (SaDE), it obtains better results in most of the functions, in terms of the quality of the final results and convergence speed.



15:15-15:40 * Active Covariance Matrix Adaptation for the (1+1)-CMA-ES

Dirk V. Arnold, Nikolaus Hansen

Stochastic optimisation, variable metric algorithm, evolution strategy, covariance matrix adaptation

We propose a novel variant of the (1+1)-CMA-ES that updates the distribution of mutation vectors based on both successful and unsuccessful trial steps. The computational costs of the adaptation procedure are quadratic in the dimensionality of the problem, and the algorithm retains all invariance properties. Its performance on a set of standard test functions is compared with that of the original strategy that updates the distribution of mutation vectors in response to successful steps only. The new variant is not observed to be more than marginally slower on any function, and it is up to two times faster on some of the test problems.


EDA: Scalability, Efficiency enhancement, and Applications

Room: Salon B

Session Chair: Chang Wook Ahn (Sungkyunkwan University)

14:00-14:25 Spurious Dependencies and EDA Scalability

Elizabeth Radetic, Martin Pelikan

population sizing, estimation of distribution algorithms, model accuracy, spurious dependencies, scalability, decision making, gambler's ruin model, initial supply

Numerous studies have shown that advanced estimation of distribution algorithms (EDAs) often discover spurious (unnecessary) dependencies. Nonetheless, only little prior work exists that would study the effects of spurious dependencies on EDA performance. This paper examines the effects of spurious dependencies on the performance and scalability of EDAs with the main focus on EDAs with marginal product models and the onemax problem. A theoretical model is proposed to analyze the effects of spurious dependencies on the population sizing in EDAs and the theory is verified with experiments. The effects of spurious dependencies on the number of generations are studied empirically. The effects of replacement strategies on the performance of EDAs with spurious linkage are also investigated.

14:25-14:50 A Robust Estimation of Distribution Algorithm for Power Electronic Circuits Design

Jing-hui Zhong, Jun Zhang

Estimation of Distribution Algorithm, Power Electronic Circuits, Histogram, Evolutionary Algorithm

The automated synthesis and optimization of power electronic circuits (PECs) is a significant and challenging task in the field of power electronics. Traditional methods such as the gradient-based methods, the hill-climbing techniques and the genetic algorithms (GA), are either prone to local optima or not efficient enough to find highly accurate solutions for this problem. To better optimize the design of PECs, this paper presents an extended histogram-based estimation of distribution algorithm with an adaptive refinement process (EDA/a-r). In the EDA/a-r, the histogram-based estimation of distribution algorithm is used to roughly locate the global optimum, while the adaptive refinement process is used to improve the accuracy of solutions. The adaptive refinement process, with its search radius adjusted adaptively during the evolution, is executed to search the surrounding region of the best-so-far solution in every generation. To maintain the diversity, a historic learning strategy is used in constructing the probabilistic model and a mutation strategy is hybridized in the sampling operation. The proposed EDA/a-r has been successfully used to optimize the design of a buck regulator. Experimental results show that compared with the GA and the particle swarm optimization (PSO), the EDA/a-r can obtain much better mean solution quality and is less likely to be trapped into local optima.


14:50-15:15 Entropy Measurement-Based Estimation Model for Bayesian Optimization Algorithm

Hai T.T. Nguyen, Hoang N. Luong, Chang Wook Ahn

Bayesian optimization algorithm, efficiency enhancement, Evaluation Relaxation, entropy

In evolutionary algorithms, the efficiency enhancement techniques are capable of solving difficult large scale problems in a scalable manner. This paper rigorously analyzes the Bayesian optimization algorithm (BOA) incorporated with an innovative evaluation relaxation method based on the entropy measurement theory (en-BOA). In particular, the concept of entropy is used to develop the evaluation relaxation strategy (ERS) and to determine the rate of convergence. Entropy measurement-based ERS is employed to recognize which candidate solution should be evaluated by the actual function or be estimated by the surrogate model. Experiments prove that en-BOA significantly reduces the number of actual evaluations and the scalability of BOA is not negatively affected. Moreover, the entropy measurement-based evaluation relaxation technique does not require any larger population sizes.

15:15-15:40 D-vine EDA: a new Estimation of Distribution Algorithm based on Regular Vines

Rogelio Salinas-Gutierrez, Arturo Hernandez-Aguirre, Enrique R. Villa-Diharce

Regular vines, D-vine, Gaussian copula, EDAs

A new Estimation of Distribution Algorithm is presented. The proposed algorithm, called D-vine EDA, uses a graphical model which is based on pair copula decomposition. By means of copula functions it is possible to model the dependence structure in a joint distribution with marginals of different type. Thus, this paper introduces the D-vine EDA and performs experiments and statistical tests to assess the best algorithm. The set of experiments shows the potential of the D-vine EDA.


GA: Theory

Room: Salon C

Session Chair: Thomas Jansen (University College Cork)

14:00-14:25 Analysis of the Effects of Lifetime Learning on Population Fitness using Vose Model

Roi Yehoshua, Mireille Avigal, Ron Unger

Vose model, genetic algorithms, Lamarckian evolution, Darwinian evolution, Baldwin effect, hybrid GA, SGA, Schema theory

Vose's dynamical systems model of the simple genetic algorithm (SGA) is an exact model that uses mathematical operations to capture the dynamical behavior of genetic algorithms. The original model was defined for a simple genetic algorithm. This paper suggests how to extend the model and incorporate two kinds of learning, Darwinian and Lamarckian, into the framework of the Vose model. The extension provides a new theoretical framework to examine the effects of lifetime learning on the fitness of a population. We analyze the asymptotic behavior of different hybrid algorithms on an infinite population vector and compare it to the behavior of the classical genetic algorithm on various population sizes. Our experiments show that Lamarckian-like inheritance - direct transfer of lifetime learning results to offsprings - allows quicker genetic adaptation. However, functions exist where the simple genetic algorithms without learning, as well as Lamarckian evolution, converge to the same local optimum, while genetic search based on Darwinian inheritance converges to the global optimum.


14:25-14:50 Investigating EA Solutions for Approximate KKT Conditions in Smooth Problems

Rupesh Tulshyan, Ramnik Arora, Kalyanmoy Deb, Joydeep Dutta

nonlinear programming, Karush-Kuhn-Tucker conditions, termination condition, Evolutionary Optimization

Evolutionary algorithms (EAs) are increasingly being applied to solve real-parameter optimization problems due to their flexibility in handling complexities such as non-convexity, non-differentiability, multi-modality and noise in problems. However, an EA's solution is never guaranteed to be optimal in generic problems, even for smooth problems, and importantly EAs still lack a theoretically motivated termination criterion for stopping an EA run only when a near-optimal point is found. We address both these issues in this paper by integrating the Karush-Kuhn-Tucker (KKT) optimality conditions that involve first-order derivatives of objective and constraint functions with an EA. For this purpose, we define a KKT-proximity measure by relaxing the complimentary slackness condition associated with the KKT conditions. Results on a number of standard constrained test problems indicate that in spite of not using any gradient information and any theoretical optimality conditions, an EA's selection, recombination and mutation operation  lead the search process to a point close to the KKT point. This suggests that the proposed KKT-proximity measure can be used a termination criterion in an EA simulation.

14:50-15:15 Aging Beyond Restarts

Thomas Jansen, Christine Zarges

aging, evolutionary algorithms, genetic algorithms, crossover, immune algorithms, runtime analysis

Aging is a general mechanism that is used to increase the diversity of the collection of search points a randomized search heuristic works on. This aims at improving the search heuristic's performance for difficult problems. Examples of randomized search heuristics where aging has been employed include evolutionary algorithms and artificial immune systems. While it is known that randomized search heuristics with aging can be very much superior to randomized search heuristics without aging, recently the point has been made that aging can often be replaced by appropriate restart strategies that are conceptionally simpler and computationally faster. Here, it is demonstrated that aging can achieve performance improvements that restarts cannot. This is done by means of an illustrative example that also involves crossover as an important component. In addition to the theoretical results an empirical study demonstrates the importance of appropriately sized populations.


RWA: Social Network Analysis and Music

Room: Salon D

Session Chair: Steven Kimbrough (University of Pennsylvania)

14:00-14:25 Evolving Viral Marketing Strategies

Forrest Stonedahl, William Rand, Uri Wilensky

Viral Marketing, Agent-Based Modeling, Diffusion, Social Networks, Business, Genetic Algorithms, Simulation

One method of viral marketing involves seeding certain consumers within a population to encourage faster adoption of the product throughout the entire population. However, determining how many and which consumers within a particular social network should be seeded to maximize adoption is challenging. We define a strategy space for consumer seeding by weighting a combination of network characteristics such as average path length, clustering coefficient, and degree. We measure strategy effectiveness by simulating adoption on a Bass-like agent-based model, with five different social network structures: four classic theoretical models (random, lattice, small-world, and preferential attachment) and one empirical (extracted from Twitter friendship data). To discover good seeding strategies, we have developed a new tool, called BehaviorSearch, which uses genetic algorithms to search through the parameter-space of agent-based models. This evolutionary search also provides insight into the interaction between strategies and network structure. Our results show that one simple strategy (ranking by node degree) is near-optimal for the four theoretical networks, but that a more nuanced strategy performs significantly better on the empirical Twitter-based network. We also find a correlation between the optimal seeding budget for a network, and the inequality of the degree distribution.


 14:25-14:50 On Heuristics for Two-Sided Matching: Revisiting the Stable Marriage Problem as a Multiobjective Problem

Steven O Kimbrough, Ann Kuo

centralized markets, agent-based models, evolutionary computation, two-sided matching, stable marriage problem, deferred acceptance algorithm

The stable marriage problem is prototypical of two-sided matching problems, widely encountered in practice, in which agents having preferences, interests and capacities for action of their own are paired up or matched. Standardly, variants of the well-known Gale-Shapley deferred acceptance algorithm (GS/DAA) are used to find stable matches. Using evolutionary computation and an agent-based model heuristics, this paper investigates the stable marriage problem as a multiobjective problem, looking at social welfare and equity or fairness, in addition to stability as important aspects of any proposed match. The paper finds that these heuristics are reliably able to discover matches that are Pareto superior to those found by the GS/DAA procedure. Ramifications of this finding are briefly explored, including the question of whether stability in a matching is often strictly required.

14:50-15:15 Multiobjective Evolutionary Algorithms for Dynamic Social Network Clustering

Keehyung Kim, RI (Bob) McKay, Byung-Ro Moon

graph clustering, dynamic optimisation, multi-objective evolutionary algorithm, social network, elitism-based immigrants

The main focus of this paper is to propose integration of dynamic and multiobjective algorithms for graph clustering in dynamic environments under multiple objectives. The primary application is to multiobjective clustering in social networks which change over time. Social networks, typically represented by graphs, contain information about the relations (or interactions) among online materials (or people). A typical social network tends to expand over time, with newly added nodes and edges being incorporated into the existing graph. We reflect these characteristics of social networks based on real-world data, and propose a suitable dynamic multiobjective evolutionary algorithm. Several variants of the algorithm are proposed and compared. Since social networks change continuously, the immigrant schemes effectively used in previous dynamic optimisation give useful ideas for new algorithms. An adaptive integration of multiobjective evolutionary algorithms outperformed other algorithms in dynamic social networks.

15:15-15:40 ConBreO: A Music Performance Rendering System using Hybrid Approach of IEC and Automated Evolution

Makoto Tanji, Hitoshi Iba

Interactive Evolutionary Computation, Genetic Programming, User Support

This paper presents an IEC (Interactive Evolutionary Computation) system named ConBreO to render expressive music performance using Genetic Programming. The central problem of IEC is the limitation of number of fitness evaluations because of user fatigue. In the system, we introduce two support techniques for IEC. The first one is a hybrid approach of IEC and automated evolution which allows the system to evolve both of IEC and automated evolution. The second one is the selective presentation which selects a new individual to be evaluated by the user based on its expected improvement of fitness. Using the system, obtained expression rule won an award at a performance rendering contest which evaluates computer systems generating expressive musical performances. Our experiment shows that the selective presentation reduces the number of fitness evaluations required to construct the fitness prediction model and prevents the system evaluating unfruitful individuals.



Bio: Best Paper Nominees: Systems, Diseases and Epidemiology

Room: Salon G

Session Chair: Marylyn Ritchie (Vanderbilt University)

14:00-14:25 On the Use of Genetic Programming for the Prediction of Survival in Cancer

Antonella Farinaccio, Leonardo Vanneschi, Mario Giacobini, Giancarlo Mauri, Paolo Provero

Genetic Programming, Computational Biology, Cancer Patients, Classification

The classification of cancer patients into risk classes is a very active field of research, with direct clinical applications. We have recently compared several machine learning methods on the well known 70-genes signature dataset. In that study, genetic programming showed promising results, given that it outperformed all the other techniques. Nevertheless, the study was preliminary, mainly because the validation dataset was preprocessed and all its features binarized in order to use logical operators for the genetic programming functional nodes. If this choice allowed simple interpretation of the solutions from the biological viewpoint, on the other hand the binarization of data was limiting, since it amounts to a sizable loss of information. The goal of this paper is to overcome this limitation, using the 70-genes signature dataset with real-valued expression data. The results we present show that genetic programming using the number of incorrectly classified instances as fitness function is not able to outperform the other machine learning methods. However, when a weighted average between false positives and false negatives is used to calculate fitness values, genetic programming obtains performances that are comparable with the other methods in the minimization of incorrectly classified instances and outperforms all the other methods in the minimization of false negatives, which is one of the main goals in breast cancer clinical applications. Also in this case,  the solutions returned by genetic programming are simple, easy to understand, and they use a rather limited subset of the available features.

14:25-14:50 * P System Model Optimisation by Means of Evolutionary Based Search Algorithms

Carlos García-Martínez, Claudio Lima, Jamie Twycross, Natalio Krasnogor, Manuel Lozano

Executable biology, P systems, Evolutionary algorithms, Real-valued parameter optimisation

Executable Biology, also called Algorithmic Systems Biology, uses rigorous concepts from computer science and mathematics to build computational models of biological entities. P systems are emerging as one of the key modelling frameworks within Executable Biology. In this paper, we address the continuous backward problem: given a P system model structure and a target phenotype (i.e.~an intended biological behaviour), one is tasked with finding the (near) optimal parameters for the model that would make the P system model produce the target behaviour as closely as possible. We test several real-valued parameter optimisation algorithms on this problem. More specifically, using four different test cases of increasing complexity, we perform experiments with four evolutionary algorithms, and one variable neighbourhood search method combining three other evolutionary algorithms. The results show that, when there are few parameters to optimise, a genetic and two differential evolution based algorithms are robust optimisers attaining the best results. However, when the number of parameters increases, the variable neighbourhood search approach performs better.



14:50-15:15 * The Application of Michigan-Style Learning ClassifierSystems to Address Genetic Heterogeneity and Epistasisin Association Studies

Ryan J Urbanowicz, Jason H Moore

Genetic Heterogeneity, Learning Classifier System, Genetics- Based Machine Learning, Epistasis, Genetic Algorithm, SNP, XCS, MCS, UCS, Gene Association Study

Genetic epidemiologists, tasked with the disentanglement of genotype-to-phenotype mappings, continue to struggle with a variety of phenomena which obscure the underlying etiologies of common complex diseases. For genetic association studies, genetic heterogeneity (GH) and epistasis (gene-gene interactions) epitomize well recognized phenomenon which represent a difficult, but accessible challenge for computational biologists. While progress has been made addressing epistasis, methods for dealing with GH tend to side-step the problem, limited by a dependence on potentially arbitrary cutoffs/covariates, and a loss in power synonymous with data stratification. In the present study, we explore an alternative strategy (Learning Classifier Systems (LCSs)) as a direct approach for the characterization, and modeling of disease in the presence of both GH and epistasis. This evaluation involves (1) implementing standardized versions of existing Michigan-Style LCSs (XCS, MCS, and UCS), (2) examining major run parameters, and (3) performing quantitative and qualitative evaluations across a spectrum of simulated datasets. The results of this study highlight the strengths and weaknesses of the Michigan LCS architectures examined, providing proof of principle for the application of LCSs to the GH/epistasis problem, and laying the foundation for the development of an LCS algorithm specifically designed to address GH.

15:15-15:40 Selecting Predictive Features for Recognition of Hypersensitive Sites of Regulatory Genomic Sequences with an Evolutionary Algorithm

Uday Kamath, Kenneth A De Jong, Amarda Shehu

DNase I Hypersensitive Sites, Evolutionary Algorithms, Support Vector Machines

This paper proposes a method to improve the recognition of regulatory genomic sequences. Annotating sequences that regulate gene transcription is an emerging challenge in genomics research. Identifying regulatory sequences promises to reveal underlying reasons for phenotypic differences among cells and for diseases associated with pathologies in protein expression. Computational approaches have been limited by the scarcity of experimentally-known features specific to regulatory sequences. High-throughput experimental technology is finally revealing a wealth of hypersensitive (HS) sequences that are reliable markers of regulatory sequences and currently the focus of classification methods. The contribution of this paper is a novel method that combines evolutionary computation and SVM classification to improve the recognition of HS sequences. Based on experimental evidence that HS regions employ sequence features to interact with enzymes, the method seeks motifs to discriminate between HS and non-HS sequences. An evolutionary algorithm (EA) searches the space of sequences of different lengths to obtain such motifs. Experiments reveal that these motifs improve recognition of HS sequences by more than 10% compared to state-of-the-art classification methods. Analysis of these motifs reveals interesting insight into features employed by regulatory sequences to interact with DNA-binding enzymes.


PES: Best Paper Nominees

Room: Salon I

Session Chair: Enrique Alba (University of Málaga)

14:00-14:25 * Parallel FPGA-based Implementation of Scatter Search

Maxwell Walton, Gary Grewal, Gerarda Darlington

Field programmable gate arrays; scatter search; data parallelism; pipelining; 0-1 knapsack problem; hardware acceleration

Scatter Search is an effective and established population-based meta-heuristic that has been used to solve a variety of hard optimization problems. However, like most population-based meta-heuristics, the time required to find high-quality solutions can become prohibitive as problem sizes grow. In this paper, we present a hardware implementation of scatter search on a Field-Programmable Gate-Array (FPGA). Our objective is to improve the runtime of scatter search by exploiting the potentially massive performance benefits that are available through the native parallelism in hardware. When implementing scatter search we employ Handel-C a programming language specifically designed to enable software developers to easily synthesize C-like programs into synchronous hardware. As far as we know, this is the first time that scatter search has been implemented in hardware (of any form). Our empirical results show that by effectively exploiting data parallelism and pipelining a 28x speedup over software can be achieved.

14:25-14:50 * The Benefit of Migration in Parallel Evolutionary Algorithms

Jorg Lassig, Dirk Sudholt

Parallel evolutionary algorithms, island model, migration, spatial structures, runtime analysis

Parallelization is becoming a more and more important issue for solving difficult optimization problems. Various implementations of parallel evolutionary algorithms (EAs) have been applied in the past decades. Island models combine phases of independent evolution with migration where genetic information is spread out to neighbored islands. Compared to panmictic models, this mechanism can lead to an increased diversity within the population. We perform a first rigorous runtime analysis for island models and construct a function where phases of independent evolution as well as communication among the islands is essential. A simple island model with migration finds a global optimum in polynomial time, while panmictic populations as well as island models without migration need exponential time, with very high probability. Our results lead to new insights on the usefulness of migration and contribute to the theoretical foundation of parallel EAs.

14:50-15:15 * Shared Memory Genetic Algorithms in a Multi-Agent Context

Dana Vrajitoru

Parallel genetic algorithms, shared memory, multi-agents

In this paper we present a concurrent implementation of genetic algorithms designed for shared memory architectures, intended to take advantage of multi-core processor platforms. Our algorithm divides the problems into sub-problems along the chromosome as opposed to the usual approach of dividing the population into niches. We show tests for timing and performance on a variety of platforms.


 GDS: General

Room: Portland

Session Chair: Kenneth O. Stanley (University of Central Florida)

14:00-14:25 Importing the Computational Neuroscience Toolbox into Neuro-Evolution---Application to Basal Ganglia

Jean-Baptiste Mouret, Stephane Doncieux, Benoit Girard

evolutionary algorithms, neural networks, computational neuroscience, basal ganglia, neuro-evolution

Neuro-evolution and computational neuroscience are two scientific domains that produce surprisingly different artificial neural networks. Inspired by the ``toolbox'' used by neuroscientists to create their models, this paper argues two main points: (1) neural maps (spatially-organized identical neurons) should be the building blocks to evolve neural networks able to perform cognitive functions and (2) well-identified modules of the brain for which there exists computational neuroscience models provide well-defined benchmarks for neuro-evolution. To support these claims, a method to evolve networks of neural maps is introduced then applied to evolve neural networks with a similar functionality to basal ganglia in animals (i.e. action selection). Results show that: (1) the map-based encoding easily achieves this task while a direct encoding never solves it; (2) this encoding is independent of the size of maps and can therefore be used to evolve large and brain-like neural networks; (3) the failure of direct encoding to solve the task validates the relevance of action selection as a benchmark for neuro-evolution.

14:25-14:50 Evolving heterochrony for cellular differentiation using vector field embryogeny

Till Steiner, Yaochu Jin, Bernhard Sendhoff

artificial development, development, dynamic system, embryogeny, heterochrony, phase space, vector field

Heterochrony is the evolutionary change of rates and timing of developmental processes. Many arti cial evolutionary development systems have the ability to produce heterochrony implicitly. However, few systems have the ability to employ heterochronic change as direct evolutionary means, i.e. to directly change heterochronic features of the developmental program. In this paper, we present and investigate a system that can directly modify heterochronic features of its basic dynamics. We show how heterochrony can be included in a novel developmental framework called vector eld embryogeny, and investigate the bene t of direct evolution of heterochronic change for four dierent cellular dierentiation tasks.

14:50-15:15 Sustaining Behavioral Diversity in NEAT

Hirotaka Moriguchi, Shinichi Honiden

NEAT, Neuroevolution, Behavioral Diversity, Niching, Premature Convergence

Niching schemes, which sustains population diversity and let an evolutionary population avoid premature convergence, have been extensively studied in the research field of evolutionary algorithms. Neuroevolutionary (NE) algorithms, such as NEAT, have also benefitted from niching. However, the latest research indicates that the use of genotype- or phenotype-similarity-based niching schemes in NE algorithms is not highly effective because these schemes have difficulty sustaining the behavioral diversity in the environment. In this paper, we propose a novel niching scheme that takes into consideration both the phenotypic and behavioral diversity, and then integrate it with NEAT. An experimental analysis revealed that the proposed algorithm outperforms the original NEAT for various problem settings. More interestingly, it performs especially well for problems with a high noise level and large state space. Since these features are common in problems to which NEAT is applied, the proposed algorithm should be effective in practice.


 15:15-15:40 Self Modifying Cartesian Genetic Programming: Finding Algorithms that Calculate pi and e to Arbitrary Precision

Simon Harding, Julian F Miller, Wolfgang Banzhaf

Genetic programming, developmental systems

Self Modifying Cartesian Genetic Programming (SMCGP) aims to be a general purpose form of developmental genetic programming. The evolved programs are iterated thus allowing an infinite sequence of phenotypes (programs) to be obtained from a single evolved genotype. In previous work this approach has already shown that it is possible to obtain mathematically provable general solutions to certain problems. We extend this class in this paper by showing how SMCGP can be used to find algorithms that converge to mathematical constants (pi and e). Mathematical proofs are given that show that some evolved formulae converge to pi and e in the limit as the number of iterations increase.



Room: Salem

Session Chair: Thomas BartzBeielstein

14:00-15:40 EC in Statistics and EA consultancy




 COM: Best Paper Nominees

Room: Salon A

Session Chair: Marc Schoenauer (INRIA Saclay)

16:10-16:35 * An Efficient Algorithm for Generalized Minimum Spanning Tree Problem

He Jiang, Yudong Chen

Local Search, Generalized Minimum Spanning Tree, Candidate Set

The Generalized Minimum Spanning Tree problem (GMST) has attracted much attention during the last few years. Since it is in-tractable, many heuristic algorithms have been proposed to solve large GMST instances. Motivated by the effectiveness and effi-ciency of the muscle (the union of all optimal solutions) for solv-ing other NP-hard problems, we investigate how to incorporate the muscle into heuristic design for GMST. Firstly, we demon-strate that it s NP-hard to obtain the muscle for GMST. Then we show that the muscle can be well approximated by the principle and subordinate candidate sets, which can be calculated on a re-duced version of GMST. Therefore, a Dynamic cAndidate set based Search Algorithm (DASA) is presented in this paper for GMST. In contrast to existing heuristics, DASA employs those candidate sets to initialize and optimize solutions. During the search process, those candidate sets are dynamically adjusted to include in new features provided by good solutions. Since those candidate sets cover almost all optimal solutions, the search space of DASA can be dramatically reduced so that elite solutions can be easily found in a short time. Extensive experiments demon-strate that our new algorithm slightly outperforms existing heuris-tic algorithms in terms of solution quality.

16:35-17:00 * Consultant-Guided Search - A New Metaheuristic for Combinatorial Optimization Problems

Serban Iordache

Metaheuristics, combinatorial optimization, swarm intelligence, traveling salesman problem

In this paper, we present Consultant-Guided Search (CGS), a new metaheuristic for combinatorial optimization problems, based on the direct exchange of information between individuals in a population. CGS is a swarm intelligence technique inspired by the way real people make decisions based on advice received from consultants. We exemplify the application of this metaheuristic to a specific class of problems by introducing the CGS-TSP algorithm, an instantiation of CGS for the Traveling Salesman Problem. To determine if our direct communication approach can compete with stigmergy-based methods, we compare the performance of CGS-TSP with that of Ant Colony Optimization algorithms. Our experimental results show that the solution quality obtained by CGS-TSP is comparable with or better than that obtained by Ant Colony System and MAX-MIN Ant System.

17:00-17:25 * A Hierarchical Cooperative Evolutionary Algorithm

Shelly Xiaonan Wu, Wolfgang Banzhaf

Cooperative evolutionary algorithms, Multilevel selection, Hierarchical model, Emergent decomposition, Coevolution

To successfully search multiple coadaptive subcomponents in a solution, we developed a novel cooperative evolutionary algorithm based on a new computational multilevel selection framework. This algorithm constructs cooperative solutions hierarchically by implementing the idea of group selection. We show that this simple and straightforward algorithm is able to accelerate evolutionary speed and improve solution accuracy on string covering problems as compared to other EAs used in literature. In addition, the structure of the solution and the roles played by each subcomponent in the solution emerge as a result of evolution without human interference.


ESEP: Parameter Tuning and Applications

Room: Salon B

Session Chair: Thomas Bartz-Beielstein (Cologne University of Applied Sciences)

16:10-16:35 Tuning Optimization Algorithms for Real-World Problems by Means of Surrogate Modeling

Mike Preuss, Günter Rudolph, Simon Wessing

parameter tuning, surrogate model, experimental study

The case-specific tuning of parameters of optimization metaheuristics like evolutionary algorithms almost always leads to significant improvements in performance. But if the evaluation of the objective function is computationally expensive, which is typically the case for real-worlds problems, an extensive parameter tuning phase on the original problem is prohibitive. Therefore we have developed another approach: Provided that a (computationally cheap) surrogate model is available that reflects the structural characteristics of the original problem then the parameter tuning can be run on the surrogate problem before using the best parameters thereby identified for the metaheuristic when optimizing the original problem. In this experimental study we aim to assess how many function evaluations on the original problem are necessary to build a surrogate model endowed with the characteristics of the original problem and to develop a methodology that measures to which extent such a matching has been achieved.

16:35-17:00 Fitting Multi-Planet Transit Models to Photometric Time-Data Series by Evolution Strategies

Andreas M. Chwatal, Gunther R. Raidl, Michael Zoch

Evolution Strategies, Exoplanets, Transits, Model Fitting, Multi-Planet Systems, GPU

In this paper we present the application of an evolution strategy to the problem of detecting multi-planet transit events in photometric time-data series. Planetary transits occur when a planet regularly eclipses its host star, reducing stellar luminosity. The transit method is amongst the most successful detection methods for exoplanets and is presently performed by space telescope missions. The goal of the presented algorithm is to find high quality fits of multi-planet transit models to observational data, which is a challenging computational task. In particular we present a method for an effective objective function evaluation and show how the algorithm can be implemented on graphics processing units. Results on artificial test data with three artificial planets are reported.


GP: Classification

Room: Salon C

Session Chair: James A. Foster (University of Idaho)

16:10-16:35 AUC Analysis of the Pareto-Front using Multi-objective GP for Classification with Unbalanced Data

Urvesh Bhowan, Mengjie Zhang, Mark Johnston

Genetic Programming, Classification, Class Imbalance, Evolutionary multi-objective Optimisation

Learning algorithms can suffer a performance bias when data sets are unbalanced. This paper proposes a Multi-Objective Genetic Programming (MOGP) approach using the accuracy of the minority and majority class as learning objectives. We focus our analysis on the classification ability of evolved Pareto-front solutions using the Area Under the ROC Curve (AUC) and investigate which regions of the objective trade-off surface favour high-scoring AUC solutions. We show that a diverse set of well-performing classifiers is simultaneously evolved along the Pareto-front using the MOGP approach compared to canonical GP where only one solution is found along the objective trade-off surface, and that in some problems the MOGP solutions had better AUC than solutions evolved with canonical GP using hand-crafted fitness functions.


16:35-17:00 Coevolutionary Multi-population Genetic Programming for Data Classification

Douglas Adriano Augusto, Helio Jos* Correa Barbosa, Nelson Francisco Favilla Ebecken

Distributed genetic programming, Coevolution, Ensemble method, Data classification

This work presents a new evolutionary ensemble method for data classification, which is inspired by the concepts of bagging and boosting, and aims at combining their good features while avoiding their weaknesses. The approach is based on a distributed multiple-population genetic programming (GP) algorithm which exploits the technique of coevolution at two levels. On the inter-population level the populations cooperate in a semi-isolated fashion, whereas on the intra-population level the candidate classifiers coevolve competitively with the training data samples. The final classifier is a voting committee composed by the best members of all the populations. The experiments performed in a varying number of populations show that our approach outperforms both bagging and boosting for a number of benchmark problems.


GBML: Best Paper Nominees

Room: Salon D

Session Chair: Pier Luca Lanzi (Politecnico di Milano)

16:10-16:35 * Negative Selection Algorithms Without Generating Detectors

Maciej Likiewicz, Johannes Textor

Artificial Immune Systems, Negative Selection, Consistent Learning

Negative selection algorithms are immune-inspired classifiers that are trained on negative examples only. Classification is performed by generating detectors that match none of the negative examples, and these detectors are then matched against the elements to be classified. This can be a performance bottleneck: A large number of detectors may be required for acceptable sensitivity, or finding detectors that match none of the negative examples may be difficult. In this paper, we show how negative selection can be implemented without generating detectors explicitly, which for many detector types leads to polynomial time algorithms whereas the common approach to sample detectors randomly takes exponential time in the worst case. In particular, we show that negative selection on strings with generating all detectors can be efficiently simulated without detectors if, and only if, an associated decision problem can be answered efficiently, regardless the detector type. We also show how to efficiently simulate the more general case in which only a limited number of detectors is generated. For many detector types, this non-exhaustive negative selection is more meaningful but it can be computationally more difficult, which we illustrate using Boolean monomials.

16:35-17:00 * How XCS Deals with Rarities in Domains with Continuous Attributes

Albert Orriols-Puig, Xavier Llora, David E Goldberg

class imbalance problem, small disjuncts, learning classifier systems, genetic-based machine learning

Michigan-style learning classifier systems solve problems by evolving distributed subsolutions online. Extracting accurate models for subsolutions which are represented by a low number of examples in the training data set has been identified as a key challenge in LCS, and facetwise analysis has been applied to identify the critical elements for success in unbalanced domains. While models for these elements have been developed for XCS with ternary representation, no study has been performed for XCS with interval-based representation, which is most often used in data mining tasks. This paper therefore takes the original design decomposition and adapts it to the interval-based representation. Theory and experimental evidence indicate that XCS with interval-based representation may fail to approximate concepts scarcely represented in the training data set. To overcome this problem, an online covering operator that introduces new specific genetic material in regions where we suspect that there are rarities is designed. The benefits of the online covering operator are empirically analyzed on a collection of artificial and real-world problems.



17:00-17:25 * Speeding Up the Evaluation of Evolutionary Learning Systems using GPGPUs

Maria A. Franco, Natalio Krasnogor, Jaume Bacardit

Evolutionary Algorithms, Learning Classifier Systems, Rule Induction, Large-scale Datasets, GPGPUs

In this paper we introduce a method for computing fitness in evolutionary learning systems based on NVIDIA's massive parallel technology using the CUDA library. Both the match process of a population of classifiers against a training set and the computation of the fitness of each classifier from its matches have been parallelized. This method has been integrated within the BioHEL evolutionary learning system. The methodology presented in this paper can be easily extended to any evolutionary learning system. The method has been tested using a broad set of problems with varying number of attributes and instances. The evaluation function by itself achieves speedups up to 52.4X while its integration with the entire learning process achieves speedups up to 58.1X. Moreover, the speedup increases when the CUDA-based fitness computation is combined with other efficiency enhancement mechanisms.


Bio: Genes, Sequences and Proteins

Room: Salon G

Session Chair: Kenneth De Jong (George Mason University)

16:10-16:35 Initialization Parameter Sweep in ATHENA: Optimizing Neural Networks for Detecting Gene-Gene Interactions in the Presence of Small Main Effects

Emily Rose Holzinger, Carrie C. Buchanan, Scott M. Dudek, Eric C. Torstenson, Stephen D. Turner, Marylyn D. Ritchie

grammatical evolution, epistasis, human genetics, neural networks

Recent advances in genotyping technology have led to the generation of an enormous quantity of genetic data. Traditional methods of statistical analysis have proved insufficient in extracting all of the information about the genetic components of common, complex human diseases. A contributing factor to the problem of analysis is that amongst the small main effects of each single gene on disease susceptibility, there are non-linear, gene-gene interactions that can be difficult for traditional, parametric analyses to detect. In addition, exhaustively searching all multi-locus combinations has proved computationally impractical. Novel strategies for analysis have been developed to address these issues. The Analysis Tool for Heritable and Environmental Network Associations (ATHENA) is an analytical tool that incorporates grammatical evolution neural networks (GENN) to detect interactions among genetic factors. Initial parameters define how the evolutionary process will be implemented. This research addresses how different parameter settings affect detection of disease models involving interactions.  In the current study, we iterate over multiple parameter values to determine which combinations appear optimal for detecting interactions in simulated data for multiple genetic models. Our results indicate that the factors that have the greatest influence on detection are: input variable encoding, population size, and parallel computation.

16:35-17:00 Protein Structure Prediction on a Lattice Model via Multimodal Optimization Techniques

Ka-Chun Wong, Kwong-Sak Leung, Man-Hon Wong

Protein Structure Prediction, Multimodal Optimization, HP Lattice Model, Relative Encoding, Absolute Encoding, Distance Metric, Crowding, Fitness Sharing, Evolutionary Algorithm

This paper considers the protein structure prediction problem as a multimodal optimization problem. In particular, de novo protein structure prediction problems on the 3D Hydrophobic-Polar (HP) lattice model are tackled by evolutionary algorithms using multimodal optimization techniques. In addition, a new mutation approach and performance metric are proposed for the problem. The experimental results indicate that the proposed algorithms are more effective than the state-of-the-arts algorithms, even though they are simple.


17:00-17:25 Challenges Rising from Learning Motif Evaluation Functions Using Genetic Programming

Leung-Yau Lo, Tak-Ming Chan, Kin-Hong Lee, Kwong-Sak Leung

Motif Discovery, Transcription Factor Binding Site (TFBS), Bioinformatics, Genetic Programming (GP), modelling

Motif discovery is an important Bioinformatics problem for deciphering gene regulation. Numerous sequence-based approaches have been proposed employing human specialist motif models (evaluation functions), but performance is so unsatisfactory on benchmarks that the underlying information seems to have already been exploited and have doomed. However, we have found that even a simple modified representation still achieves considerably high performance on a challenging benchmark, implying potential for sequence-based motif discovery. Thus we raise the problem of learning motif evaluation functions. We employ Genetic programming (GP) which has the potential to evolve human competitive models. We take advantage of the terminal set containing specialist-model-like components and have tried three fitness functions. Results exhibit both great challenges and potentials. No models learnt can perform universally well on the challenging benchmark, where one reason may be the data appropriateness for sequence-based motif discovery. However, when applied on different widely-tested datasets, the same models achieve comparable performance to existing approaches based on specialist models. The study calls for further novel GP to learn different levels of effective evaluation models from strict to loose ones on exploiting sequence information for motif discovery, namely quantitative functions, cardinal rankings, and learning feasibility classifications.


PES: Advanced Topics

Room: Salon I

Session Chair: Enrique Alba (University of Malaga)

16:10-16:35 Selection Pressure and Takeover Time of Distributed Evolutionary Algorithms

Gabriel Luque, Enrique Alba

Parallel Evolutionary Algorithms, Theory, Selection Pressure, Takeover Time, Theory vs. Practice

This paper presents a theoretical study about the selection pressure and the convergence speed of distributed evolutionary algorithms (dEA). In concrete, we model the best individual s growth curve and the takeover time for usual models of multipopulation EAs found in the literature. The calculation of the takeover time is a common analytical approach to measure the selection pressure of an EA. This work is another step forward to mathematically unify and describe the roles of all the parameters of the migration policy (the migration rate, the migration period, the topology, and the selection/replace schemes of immigrants) in the selection pressure induced by the dynamics of dEAs. In order to achieve these goals we analyze the behaviour of these algorithms and propose a mathematical formula which models that dynamic. The proposed mathematical model is later verified in practice.

16:35-17:00 GPU-based Island Model for Evolutionary Algorithms

The Van LUONG, Nouredine Melab, El-Ghazali Talbi

Island model, parallel, GPU

The island model for evolutionary algorithms allows to delay the global convergence of the evolution process and encourage diversity. However, solving large size and time-intensive combinatorial optimization problems with the island model requires a large amount of computational resources. GPU computing is recently revealed as a powerful way to harness these resources. In this paper, we focus on the parallel island model on GPU. We address its re-design, implementation, and associated issues related to the GPU execution context. The preliminary results demonstrate the effectiveness of the proposed approaches and their capabilities to fully exploit the GPU architecture.






Sunday 11 July 10:40 - 12:20



GP: Crossover

Room: Columbia

Session Chair: Riccardo Poli (University of Essex)

10:40-11:05 Semantics Based Crossover for Boolean Problems

Quang Uy Nguyen, Xuan Hoai Nguyen, Michael O'Neill, Bob McKay

Genetic Programming, Trace Semantics, Crossover Operators, Boolean Problems

This paper investigates the role of semantic diversity and locality of crossover operators in Genetic Programming (GP) for Boolean problems. We propose methods for measuring and storing semantics of subtrees in Boolean domains using Trace Semantics, and design several new crossovers on this basis. They can be categorised into two classes depending on their purposes: promoting semantic diversity or improving semantic locality. We test the operators on several well-known Boolean problems, comparing them with Standard GP Crossovers and with the Semantic Driven Crossover of Beadle and Johnson. The experimental results show the positive effects both of promoting semantic diversity, and of improving semantic locality, in crossover operators. They also show that the latter has a greater positive effect on GP performance than the former.

11:05-11:30 New Crossover Operators in Linear Genetic Programming for Multiclass Object Classification

Carlton Downey, Mengjie Zhang, Will N Browne

genetic programming, crossover operator, classification

Genetic programming (GP) has been successfully applied to solving multiclass classification problems, but the performance of GP classifiers still lags behind that of alternative techniques. This paper investigates an alternative form of GP, Linear GP (LGP), which demonstrates great promise as a classifier as the division of classes is inherent in this technique. By combining biological inspiration with detailed knowledge of program structure two new crossover operators that significantly improve performance are developed. The first is a new crossover operator that mimics biological crossover between alleles, which helps reduce the disruptive effect on building blocks of information. The second is an extension of the first where a heuristic is used to predict offspring fitness guiding search to promising solutions.

11:30-11:55 A Probabilistic Functional Crossover Operator for Genetic Programming

Josh C Bongard

homologous crossover, crossover operators, schema theory

The original mechanism by which evolutionary algorithms were to solve problems was to allow for the gradual discovery of sub-solutions to sub-problems, and the automated combination of these sub-solutions into larger solutions. This latter property is particularly challenging when recombination is performed on genomes encoded as trees, as crossover events tend to greatly alter the original genomes and therefore greatly reduce the chance of the crossover event being beneficial. A number of crossover operators designed for tree-based genetic encodings have been proposed, but most consider crossing genetic components based on their structural similarity. In this work we introduce a tree-based crossover operator that probabilistically crosses branches based on the behavioral similarity between the branches. It is shown that this method outperforms genetic programming without crossover, random crossover, and a deterministic form of the crossover operator in the symbolic regression domain.


 GA: Combinatorial Optimization

Room: Mt Hood

Session Chair: Franz Rothlauf (University of Mainz)

10:40-11:05 A Heuristic-based Hybrid Genetic Algorithm for Heterogeneous Multiprocessor Scheduling

Yun Wen, Hua Xu, Jiadong Yang

Genetic Algorithm, Variable Neighborhood Search, Heterogeneous Multiprocessor Scheduling, Memetic Algorithm

Effective task scheduling, which is essential for achieving high performance of parallel processing, remains challenging despite of extensive studies. In this paper, a heuristic-based hybrid Genetic Algorithm (GA) is proposed for solving the heterogeneous multiprocessor scheduling problem. The proposed algorithm extends traditional GA-based approaches in three aspects. First, it incorporates GA with Variable Neighborhood Search (VNS), a local search metaheuristic, to enhance the balance between global exploration and local exploitation of search space. Second, two novel neighborhood structures, in which problem-specific knowledge concerned with load balancing and communication reduction is utilized, are proposed to improve both the search quality and efficiency of VNS. Third, the use of GA is restricted to map tasks to processors while an upward-ranking heuristic is introduced to determine the task sequence assignment in each processor. Simulation results indicate that our proposed algorithm consistently outperforms several state-of-art scheduling algorithms in terms of the schedule quality while maintaining high performance within a wide range of parameter settings. Further experiments are carried out to validate the effectiveness of the hybridized VNS.

11:05-11:30 A Hybrid Genetic Algorithm for Automatic Graph Drawing Based on the Topology-Shape-Metric Approach.

Bernadete Maria de Mendonça Neta, Gustavo Henrique Diniz Araujo, Frederico Gadelha Guimaraes, Renato Cardoso Mesquita

Automatic Graph Drawing, topology-shape-metric, Genetic Algorithm, Combinatorial Optimization.

This paper presents a new approach for automatic graph drawing based on Genetic algorithms. The classical topologyshape-metric approach for orthogonal graph drawing keeps a fixed planar embedding obtained in its first step (planarization), using it for the next two steps (orthogonalization and compaction). However, each step is itself an NP-hard problem, and the choices made and heuristics used on previous stages have a direct impact on subsequent ones. We can, alternatively, obtain a large number of planar embeddings by varying the order of insertion of the graph s edges when constructing such embeddings. Following that, the genetic algorithm is applied to select the planar embeddings that would lead to the final best drawing, after evaluating its performance on the subsequent orthogonalization and compaction steps. We formulate the problem of finding an optimal planar embedding for the graph as a permutation-based combinatorial optimization problem. The problem is then solved with the genetic algorithm, using appropriate selection, crossover and mutation operators, which were adapted from other permutation-based optimization problems, such as scheduling problems. The results show that our approach is able to find better solutions, representing improved final graph drawings, than the ones found via the classical topology-shape-metric approach.


11:30-11:55 Solving Multiobjective Flexible Job-shop Scheduling Using an Adaptive Representation

Prakarn Unachak, Erik Goodman, N/A N/A

Flexible Job Shop Scheduling Problems, Genetic Algorithm, Multiobjective Optimization, Rescheduling, Representation

In this paper, we present an alternative representation for solving multiobjective Flexible Job-shop Scheduling Problems (FJSP). In FJSP, there may be a choice of machines that can perform any given operation. In order to schedule an operation, it needs to be assigned a machine first, a process known as routing. Most previous approaches to solving FJSP assigned machines to all schedules before beginning any scheduling. In our approach, Adaptive Representation (AdRep), we assign a machine to an operation just at the time it is ready to be scheduled, allowing the routing process to incorporate information from the scheduling environment. Experimental results show that although AdRep performance does not scale as well with problem size as some other approaches that are not simultaneously searching for machine assignments, it is able to find all best published solutions on a three-objective Pareto front including makespan, total workload, and maximum workload on any machine, while its simultaneous routing search opens up new possibilities for optimality of rescheduling in response to machine failure.

11:55-12:20 Breaking Ties with Secondary Fitness in a Genetic Algorithm for the Bin Packing Problem

Justin Benjamin, Bryant A Julstrom

Secondary fitness, tournament selection, tie breaking, bin packing, genetic algorithm

In a genetic algorithm with integer fitnesses, ties in selection tournaments result in the selection of parent chromosomes effectively at random. A secondary measure that estimates how likely chromosomes are to be improved by the GA's variation operators can break such ties to the algorithm's advantage. Such a secondary fitness for the Bin Packing Problem is based on the maximum unused capacity in any one bin. In tests on 70 instances of the Bin Packing Problem, a permutation-coded genetic algorithm performs better when it applies this measure as a tie-breaker in tournament selection and in elitism than when it does not. The results suggest that similar measures should improve the performance of other GAs that apply tournament selection to chromosomes with integer fitnesses.


COM: Methods and Approaches

Room: Meadowlark

Session Chair: Jiri Kubalik (Department of Cybernetics, Czech Technical University in Prague)


10:40-11:05 Heuristics for Sampling Repetitions in Noisy Landscapes with Fitness Caching

Forrest Stonedahl, Susa H Stonedahl

fitness caching, noise reduction, fitness landscapes, uncertainty, sampling, evolutionary algorithms, hill climbing

For many large-scale combinatorial search/optimization problems, meta-heuristic algorithms face noisy objective functions, coupled with computationally expensive evaluation times. In this work, we consider the interaction between the technique of "fitness caching" and the straightforward noise reduction approach of "fitness averaging" by repeated sampling. Fitness caching changes how noise affects a fitness landscapes, as noisy values become frozen in the cache. Assuming the use of fitness caching, we seek to develop heuristic methods for predicting the optimal number of sampling replications for fitness averaging. We derive two analytic measures for quantifying the effects of noise on a cached fitness landscape (probabilities of creating "false switches" and "false optima"). We empirically confirm that these measures correlate well with observed probabilities on a set of four well-known test-bed functions (sphere, Rosenbrock, Rastrigin, Schwefel). We also present results from a preliminary experimental study on these landscapes, investigating four possible heuristic approaches for predicting the optimal sampling, using a random-mutation hill-climber with fitness caching.



11:05-11:30 On the Generality of Parameter Tuning in Evolutionary Planning

Jacques Bibai, Pierre Saveant, Marc Schoenauer, Vincent Vidal

AI Planning, Memetic Algorithms, Parameter Tuning, Racing

Divide-and-Evolve (DaE) is an original memeticization of Evolutionary Computation and Artificial Intelligence Planning. However, like any Evolutionary Algorithm, DaE has several parameters that need to be tuned, and the already excellent experimental results demonstrated by DaE on benchmarks from the International Planning Competition, at the level of those of standard AI planners, have been obtained with parameters that had been tuned once and forall using the Racing method. This paper demonstrates that more specific parameter tuning (e.g. at the domain level or even at the instance level) can further improve DaE results, and discusses the trade-off between the gain in quality of the resulting plans and the overhead in terms of computational cost.

11:30-11:55 Efficient Stochastic Local Search Algorithm for Solving the Shortest Common Supersequence Problem

Jiri Kubalik

Combinatorial optimization, Evolutionary algorithms, Stochastic local search

The Shortest Common Supersequence (SCS) problem is a well-known hard combinatorial optimization problem that formalizes many real world problems. Recently, an application of the iterative optimization method called Prototype Optimization with Evolved Improvement Steps (POEMS) to the SCS problem has been proposed. The POEMS seeks the best variation of the current solution in each iteration. The variations, considered as structured hypermutations, are evolved by means of an evolutionary algorithm. This approach has been shown to work very well on synthetic as well as real biological data. However, the approach exhibited rather low scalability which is caused by very time demanding evaluation function. This paper proposes a new time efficient evaluation procedure and a new moving-window strategy for constructing and refining the supersequence. These two enhancements significantly improve an efficiency of the approach. Series of experiments with the modified POEMS method have been carried out. Results presented in this paper show that the method is competitive with current state-of-the-art algorithms for solving the SCS problem. Moreover, there is a potential for further improvement as discussed in the conclusions.



Room: Douglas Fir

Session Chair: Jorn Mehnen, Thomas Bartz Beielstein,Thomas Baeck, Erik Goodman

10:40-12:20 Getting a Job: What to do and what not to do






EMO: Preferences and Performance based EMO

Room: Salmon

Session Chair: Pierre Collet (Universit* de Strasbourg)

10:40-11:05 Set-based Multi-Objective Optimization, Indicators, and Deteriorative Cycles

Rudolf Berghammer, Tobias Friedrich, Frank Neumann

Multiobjective Optimization, Performance Measures, Hypervolume Indicator, Cycles

Evolutionary multi-objective optimization deals with the task of computing a minimal set of search points according to a given set of objective functions. The task has been made explicit in a recent paper by Zitzler et al. .We take an order-theoretic view on this task and examine how the use of indicator functions can help to direct the search towards Pareto optimal sets. Thereby, we point out that evolutionary algorithms for multi-objective optimization working on the dominance relation of search points have to deal with a cyclic behavior that may lead to worsenings with respect to the Pareto-dominance relation defined on sets. Later on, we point out in which situations well-known binary and unary indicators can help to avoid this cyclic behavior.

11:05-11:30 A Sphere-dominance based Preference Immune-inspired Algorithm for Dynamic Multi-objective Optimization

Ruochen Liu, Wei Zhang, Licheng Jiao, Fang Liu, Jingjing Ma

Artificial immune system, preference, multi-objective optimization, dynamic, reference point

Real-world optimization involving multiple objectives in changing environment known as dynamic multi-objective optimization (DMO) is a challenging task, especially special regions are preferred by decision maker (DM). Based on a novel preference dominance concept called sphere-dominance and the theory of artificial immune system (AIS), a sphere-dominance preference im- mune-inspired algorithm (SPIA) is proposed for DMO in this paper. The main contributions of SPIA are its preference mechanism and its sampling study, which are based on the novel sphere-dominance and probability statistics, respectively. Besides, SPIA introduces two hypermutation strategies based on history information and Gaussian mutation, respectively. In each generation, which way to do hypermutation is automatically determined by a sampling study for accelerating the search process. Furthermore, The interactive scheme of SPIA enables DM to include his/her preference without modifying the main structure of the algorithm. The results show that SPIA can obtain a well distributed solution set efficiently converging into the DM's preferred region for DMO.

11:30-11:55 Simultaneous Use of Different Scalarizing Functions in MOEA/D

Hisao Ishibuchi, Yuji Sakane, Noritaka Tsukamoto, Yusuke Nojima

Evolutionary multiobjective optimization (EMO), scalarizing function, MOEA/D

The use of Pareto dominance for fitness evaluation has been the mainstream in evolutionary multiobjective optimization for the last two decades. Recently, it has been pointed out in some studies that Pareto dominance-based algorithms do not always work well on multiobjective problems with many objectives. Scalarizing function-based fitness evaluation is a promising alternative to Pareto dominance especially for the case of many objectives. A representative scalarizing function-based algorithm is MOEA/D (multiobjective evolutionary algorithm based on decomposition) of Zhang & Li (2007). Its high search ability has already been shown for various problems. One important implementation issue of MOEA/D is a choice of a scalarizing function because its search ability strongly depends on this choice. It is, however, not easy to choose an appropriate scalarizing function for each multiobjective problem. In this paper, we propose an idea of using different types of scalarizing functions simultaneously. For example, both the weighted Tchebycheff (Chebyshev) and the weighted sum are used for fitness evaluation. We examine two methods for implementing our idea. One is to use multiple grids of weight vectors and the other is to assign a different scalarizing function alternately to each weight vector in a single grid.



11:55-12:20 Indicator-Based Evolutionary Algorithm with Hypervolume Approximation by Achievement Scalarizing Functions

Hisao Ishibuchi, Noritaka Tsukamoto, Yuji Sakane, Yusuke Nojima

hypervolume, indicator-based evolutionary algorithm (IBEA), many objectives, Evolutionary multiobjective optimization (EMO)

Pareto dominance-based algorithms have been the main stream in the field of evolutionary multiobjective optimization (EMO) for the last two decades. It is, however, well-known that Pareto-dominance-based algorithms do not always work well on many-objective problems with more than three objectives. Currently alternative frameworks are studied in the EMO community very actively. One promising framework is the use of an indicator function to find a good solution set of a multiobjective problem. EMO algorithms with this framework are called indicator-based evolutionary algorithms (IBEAs) where the hypervolume measure is frequently used as an indicator. IBEAs with the hypervolume measure have strong theoretical support and high search ability. One practical difficult of such an IBEA is that the hypervolume calculation needs long computation time especially when we have many objectives. In this paper, we propose an idea of using a scalarizing function-based hypervolume approximation method in IBEAs. We explain how the proposed idea can be implemented in IBEAs. We also demonstrate through computational experiments that the proposed idea can drastically decrease the computation time of IBEAs without severe performance deterioration.


GBML: Multi-Task and Multi-Agent Systems

Room: Sunstone

Session Chair: Martin Butz (University of Wurzburg)

10:40-11:05 Multi-Task Evolutionary Shaping Without Pre-Specified Representations

Matthijs Snel, Shimon Whiteson

reinforcement learning, genetic algorithms, feature selection, shaping

Shaping functions can be used in multi-task reinforcement learning (RL) to incorporate knowledge from previously experienced tasks to speed up learning on a new task. So far, researchers have pre-specified a separate representation for shaping and value functions in multi-task settings. However, no work has made precise what distinguishes these representations, or what makes a good representation for either function. This paper shows two alternative methods by which an evolutionary algorithm can find a shaping function in multi-task RL without pre-specifying a separate representation. The second method, which uses an indirect fitness measure, is demonstrated to achieve similar performance to the first against a significantly lower computational cost. In addition, we define a formal categorisation of representations that makes precise what makes a good representation for shaping and value functions. We validate the categorisation with an evolutionary feature selection method and show that this method chooses the representations that our definitions predict are suitable.

11:05-11:30 Adaption of XCS to Multi-Learner Predator/Prey Scenarios

Clemens Lode, Urban Richter, Hartmut Schmeck

Agent cooperation, evolutionary learning, XCS, multi-agent learning, coordination task, non-Markovian environments

Learning classifier systems (LCSs) are rule-based evolutionary reinforcement learning systems. Today, especially variants of Wilson's extended classifier system (XCS) are widely applied for machine learning. Despite their widespread application, LCSs have drawbacks, e. g., in multi-learner scennarios, since the Markov property is not fulfilled. In this paper, LCSs are investigated in an instance of the generic homogeneous and non-communicating predator/prey scenario. A group of predators collaboratively observe a (randomly) moving prey as long as possible, where each predator is equipped with a single, independent XCS. Results show that improvements in learning are achieved by cleverly adapting a multi-step approach to the characteristics of the investigated scenario. Firstly, the environmental reward function is expanded to include sensory information. Secondly, the learners are equipped with a memory to store and analyze the history of local actions and given payoffs.


11:30-11:55 Coevolution in a Large Search Space using Resource-limited Nash Memory

Edward P. Manning

Coevolution, Nash Equilibrium, Games, Evaluation Function

Cycling has been an obstacle to coevolution of machine-learning agents. Monotonic algorithms seek continual improvement with respect to a solution concept; seeking an agent or set of agents that approaches the true solution without cycling. Algorithms that guarantee monotonicity generally require unlimited storage. One such algorithm is the Nash Memory, which uses the Nash Equilibrium as the solution concept. The requirement for unbounded storage is an obstacle to the use of this algorithm in large applications. This paper demonstrates the performance of the Nash Memory algorithm with fixed storage in coevolving a population of moderately large agents (with knowledge represented as n-tuple networks) learning a function with a large state space (an evaluation function for the game of Othello). The success of the algorithm results from the diversity of the agents produced, and the corresponding need for improved global performance in order for agents to survive and reproduce. The algorithm can be expected to converge to a region of highest performance within the capability of the search operators.

11:55-12:20 A First Assessment of the Use of Extended Relational Alphabets in Accuracy Classifier Systems

Carlos D. Toledo-Suarez

Classifier systems, relational schemata, relational alphabets, st-alphabets, parity problem

It is proposed to extend the typical ternary {0, 1, #} representation used in classifier systems by including source and target relational characters, with mappings linking targets to sources expressed as rules of another system over ternary alphabet. After transforming such a system into bipolar neural networks, it is shown that the influence of these mappings can be interpreted as the creation of holes in the hyperplanes of rules over ternary alphabet. Relational schemata are reviewed as the main antecedent of extended alphabets (st-alphabets) presented, and it is shown that st-alphabets inherit from them the features that led their creators to refuse implementing them explicitly. Successful experiments on the parity problem and Woods2 are presented after showing two approaches for the measurement of the expressive power of st-alphabets, the minimal modifications that can be performed in an accuracy classifier system (XCS) to experiment with populations of rules over them, and how the use of these alphabets impact the rule evolution pressures identified in a run of a XCS. The article ends with suggestions for future exploitations of the features of st-alphabets in modular and hierarchical problems.


RWA: Hardware and Software

Room: Salon D

Session Chair: Giuseppe Nicosia (University of Catania)

10:40-11:05 Improving Reliability of Embedded Systems through Dynamic Memory Manager Optimization using Grammatical Evolution

J. Manuel Colmenar, Jose L. Risco-Martin, David Atienza, Oscar Garnica, J. Ignacio Hidalgo, Juan Lanchares

Genetic Programming, Grammatical Evolution, Evolutionary Computation, Embedded Systems Design

Technology scaling has offered advantages to embedded systems, such as increased performance, more available memory and reduced energy consumption. However, scaling also brings a number of problems like reliability degradation mechanisms. The intensive activity of devices and high operating temperatures are key factors for reliability degradation in latest technology nodes. Focusing on embedded systems, the memory is prone to suffer reliability problems due to the intensive use of dynamic memory on wireless and multimedia applications. In this work we present a new approach to automatically design dynamic memory managers considering reliability, and improving performance, memory footprint and energy consumption. Our approach, based on Grammatical Evolution, obtains a maximum improvement of 39% in execution time, 38% in memory usage and 50% in energy consumption over state-of-the-art dynamic memory managers for several real-life applications. In addition, the resulting distributions of memory accesses improve reliability. To the best of our knowledge, this is the first proposal for automatic dynamic memory manager design that considers reliability.



11:05-11:30 Multi-Objective Optimization of Doping Profile in Semiconductor Design

Giovanni Stracquadanio, Concetta Drago, Vittorio Romano, Giuseppe Nicosia

Multi-objective optimization, semiconductor design, electronic design automation.

A crucial task in designing semiconductor devices is to provide a doping profile that assures specific electrical properties. This research work is focused in redesigning doping profiles of semiconductor devices in order to obtain an increased output current; however, large doping levels can degenerate the devices and hence a trade-off between doping profile deviation and output current should be found. The doping profile optimization in semiconductor has been tackled as a multi-objective optimization problem using the Non-dominated Sorting Genetic Algorithm (NSGA-II). We focus on silicon diodes and MOSFET devices; firstly, we redesign the doping profile of diodes in order to obtain a trade-off between doping profile deviation and output current. Secondly, we find a trade-off between current and temperature for a MOSFET device. The experimental results confirm the effectiveness of the proposed approach to face this class of problems in electronic design automation.

11:30-11:55 Multiprocessor Systems-on-Chip Synthesis using Multi-Objective Evolutionary Computation

Marco Ceriani, Fabrizio Ferrandi, Pier Luca Lanzi, Donatella Sciuto, Antonino Tumeo

Systems-on-Chip Synthesis, Multi-objective Evolution

In this paper, we apply multi-objective evolutionary computation to the synthesis of real-time, embedded, heterogeneous, multipro- cessor systems (briefly, Multiprocessor Systems-on-Chip or MP- SoCs). Our approach simultaneously explores the architecture, the mapping and the scheduling of the system, by using multi-objective evolution. In particular, we considered three approaches: a multi- objective genetic algorithm, multi-objective Simulated Annealing, and multi-objective Tabu Search. The algorithms search for opti- mal architectures, in terms of processing elements (processors and hardware accelerators) and communication infrastructure, and for the best mappings and schedules of multi-rate real-time applica- tions given objectives such as: system area, hard and soft dead- lines violations, dimensions of memory buffers. We formalize the problem, describe our flow and compare the three algorithms, dis- cussing which one performs better with respect to different classes of applications.

11:55-12:20 Malware Detection based on Dependency Graph using Hybrid Genetic Algorithm

Keehyung Kim, Byung-Ro Moon

malware detection, subgraph isomorphism, genetic algorithm, dependency graph

Computer malware is becoming a serious threat to our daily life in the information-based society. Especially, script malwares has become famous recently, since a wide range of programs supported scripting, the fact that makes such malwares spread easily. Because of viral polymorphism, current malware detection technologies cannot catch up the exponential growth of polymorphic malwares. In this paper, we propose a detection mechanism for script malwares, using dependency graph analysis. Every script malware can be represented by a dependency graph and then the detection can be transformed to the problem finding maximum subgraph isomorphism in that polymorphism still maintains the core of logical structures of malwares. We also present efficient heuristic approaches for maximum subgraph isomorphism, which improve detection accuracy and reduce computational cost. The experimental results of their use in a hybrid GA showed superior detection accuracy against state-of-the-art anti-virus softwares.



GP: Fitness Evaluation, Feature Selection and Symbiosis

Room: Columbia

Session Chair: Wolfgang Banzhaf (Department of Computer Science, Memorial University of Newfoundland)

14:00-14:25 Predicting Solution Rank to Improve Performance

Michael D Schmidt, Hod Lipson

Fitness Prediction, Evolutionary Algorithms, Coevolution, Symbolic Regression

Many applications of evolutionary algorithms utilize fitness approximations, for example coarse-grained simulations in lieu of computationally intensive simulations. Here, we propose that it is better to learn approximations that accurately predict the ranks of individuals rather than explicitly estimating their real-valued fitness values. We present an algorithm that coevolves a rank-predictor which optimizes to accurately rank the evolving solution population. We compare this method with a similar algorithm that uses fitness-predictors to approximate real-valued fitnesses. We benchmark the two approaches using thousands of randomly-generated test problems in Symbolic Regression with varying difficulties. The rank prediction method showed a 5-fold reduction in computational effort for similar convergence rates. Rank prediction also produced less bloated solutions than fitness prediction.

14:25-14:50 Efficiently Evolving Programs through the Search for Novelty

Joel Lehman, Kenneth O. Stanley

Genetic programming, Premature convergence, Novelty search, Program bloat

A significant challenge in genetic programming is premature convergence to local optima, which often prevents evolution from solving problems. This paper introduces to genetic programming a method that originated in neuroevolution (i.e. the evolution of artificial neural networks) that circumvents the problem of deceptive local optima. The main idea is to search only for behavioral novelty instead of for higher fitness values. Although such novelty search abandons following the gradient of the fitness function, if such gradients are deceptive they may actually occlude paths through the search space towards the objective. Because there are only so many ways to behave, the search for behavioral novelty is often computationally feasible and differs significantly from random search. Counterintuitively, in both a deceptive maze navigation task and the artificial ant benchmark task, genetic programming with novelty search, which ignores the objective, outperforms traditional genetic programming that directly searches for optimal behavior. Additionally, novelty search evolves smaller program trees in every variation of the test domains. Novelty search thus appears less susceptible to bloat, another significant problem in genetic programming. The conclusion is that novelty search is a viable new tool for efficiently solving some deceptive problems in genetic programming.

14:50-15:15 Symbiosis, Complexification and Simplicity under GP

Peter Lichodzijewski, Malcolm I. Heywood

Symbiosis, Genetic Programming, Feature Selection, Problem Decomposition, Complexity

Models of Genetic Programming (GP) frequently reflect a neo-Darwinian view to evolution in which inheritance is based on a process of gradual refinement and the resulting solutions take the form of single monolithic programs. Conversely, introducing an explicitly symbiotic model of inheritance makes a divide-and-conquer metaphor for problem decomposition central to evolution. Benchmarking gradualist versus symbiotic models of evolution under a common evolutionary framework illustrates that not only does symbiosis result in more accurate solutions, but the solutions are also much simpler in terms of instruction and attribute count over a wide range of classification problem domains.



15:15-15:40 Knowledge Mining with Genetic Programming Methods for Variable Selection in Flavor Design

Katya Vladislavleva, Kalyan Veeramachaneni, Matt Burland, Jason Parcon, Una-May O'Reilly

Pareto, Symbolic regression, Variable Selection, Ensemble Modeling, Sensory data, Genetic programming

This paper presents a novel approach for knowledge mining from a sparse and repeated measures dataset. Genetic programming based symbolic regression is employed to generate multiple models that provide alternate explanations of the data. This set of models, called an ensemble, is generated for each of the repeated measures separately. These multiple ensembles are then utilized to generate information about, (a) which variables are important in each ensemble, (b) cluster the ensembles into different groups that have similar variables that drive their response variable, and (c) measure sensitivity of response with respect to the important variables. We apply our methodology to a sensory science dataset. The data contains hedonic evaluations (liking scores), assigned by a diverse set of human testers, for a small set of avors composed from seven ingredients. Our approach: (1) identi es the important ingredients that drive the liking score of a panelist and (2) segments the panelists into groups that are driven by the same ingredient, and (3) enables flavor scientists to perform the sensitivity analysis of liking scores relative to changes in the levels of important ingredients.


GA: EC Techniques

Room: Mt Hood

Session Chair: Martin Pelikan (University of Missouri in St. Louis)

14:00-14:25 Probabilistic Performance Profiles for the Experimental Evaluation of Stochastic Algorithms

Andre M. S. Barreto, Heder S. Bernardino, Helio J. C. Barbosa

Experimental Evaluation, Performance Profiles

One of the many difficulties that arise in the empirical evaluation of new computational techniques is the analysis and reporting of experiments involving a large number of test-problems and algorithms. The performance profiles are a methodology specifically developed for this purpose which provides a simple means of visualizing and interpreting the results of large-scale benchmarking experiments. However good, performance profiles do not take into account the uncertainty present in most experimental settings. This paper presents an extension of this analytic tool called probabilistic performance profiles. The basic idea is to endow the original performance profiles with a probabilistic interpretation, which makes it possible to represent the expected performance of a stochastic algorithm in a convenient way. The benefits of the new method are demonstrated with data from a real benchmark experiment involving several problems and algorithms.

14:25-14:50 Approaches to Multidimensional Scaling for Adaptive Landscape Visualization

Robert Collier, Mark Wineberg

Adaptive Landscapes, Multidimensional Scaling

The adaptive landscape has become a standard approach for genetic algorithm visualization, and the representation of the higher dimensional chromosome space onto a two-dimensional plane suitable for the construction of an adaptive landscape requires an accurate measurement of the distance between chromosomes. Although the shortcomings of traditional approaches to adaptive landscape construction are by no means unknown to the research community, the intuitions afforded by this visualization have kept it in widespread usage. Since the multidimensional scaling required for the creation of a representative landscape is often disregarded to avoid the computational overhead required, this paper demonstrated that distance measures are available that remain representative of the genetic operators of the genetic algorithm while being suitable for multidimensional scaling techniques. This paper also demonstrated that in spite of the complications expected when the distance between chromosomes is measured with respect to both a unary mutation operation and a binary recombination operation simultaneously, it is possible to construct adaptive landscapes that depict features indicative of the effects of both genetic operators.


 14:50-15:15 Network Crossover Performance on NK Landscapes and Deceptive Problems

Mark W Hauschild, Martin Pelikan

Crossover operators, Bayesian optimization algorithm, hierarchical BOA, efficiency enhancement, learning from experience, estimation of distribution algorithms

Practitioners often have some information about the problem being solved, which may be represented as a graph of dependencies or correlations between problem variables. Similar information can also be obtained automatically, for example by mining the probabilistic models obtained by EDAs or by using other methods for linkage learning. This information can be used to bias variation operators, be it in EDAs (where it can be used to speed up model building) or in GAs (where the linkages can be explored by modifying crossover). This can allow us to solve problems unsolvable with conventional, problem-independent variation operators, or speed up adaptive operators such as those of EDAs. This paper describes a method to build a network crossover operator that can be used in a GA to easily incorporate problem-specific knowledge. The performance of this operator in the simple genetic algorithm(GA) is then compared to other operators as well as the hierarchical Bayesian Optimization Algorithm (hBOA) on several different problem types, all with both elitism replacement and Restricted Tournament Replacement (RTR). The performance of all the algorithms are then analyzed and the results are discussed.


COM: Applications

Room: Meadowlark

Session Chair: Peter A.N. Bosman (Centre for Mathematics and Computer Science)

14:00-14:25 Towards Improved Dispatching Rules for Complex Shop Floor Scenarios

Torsten Hildebrandt, Jens Heger, Bernd Scholz-Reiter

Genetic Programming, Job Shop Scheduling, Dispatching Rules, Stochastic System Optimization

Developing dispatching rules for manufacturing systems is a tedious process, which is time- and cost-consuming. Since there is no good general rule for dierent scenarios and objectives automatic rule search mechanism are investigated. In this paper an approach using Genetic Programming (GP) is presented. The priority rules generated by GP are evaluated on dynamic job shop scenarios from literature and compared with manually developed rules yielding very promising results also interesting for Simulation Optimization in general.

14:25-14:50 Discrete versus Continuous Parametrization of Bank Credit Rating Systems Optimization Using Differential Evolution

K. M. Leung, Xi Zhang

Optimization, Global Optimization

Bank credit rating system is a clustering problem that aims to achieve the optimal classification of the clients' probability of defaults (PDs) into discrete buckets under a number of constraints. This global optimization problem can be parametrized either using continuous or discrete decision variables, and treated using basically the same differential evolution (DE) method that takes into account of real-world constraints imposed by the recent Basel Accord on Banking Supervision. This enables us to make interesting comparisons between continuous versus discrete parametrization of the same problem in terms of the efficiency, robustness and the rate of convergence. It turns out to be beneficial to use discrete parameters for all of these reasons. In addition we have also explored the use of the elitist as well as the classic strategies within the DE approach. The former choice turns out to perform better in terms of efficiency, robustness, and faster convergence, except when the number of required buckets is large.


 14:50-15:15 An Ant Colony Optimization Approach to the Multiple-Choice Multidimensional Knapsack Problem

Zhigang Ren, Zuren Feng

Ant Colony Optimization, Multiple-Choice Multidimensional Knapsack Problem, Lagrangian Relaxation

In this paper, we present an ant colony optimization (ACO) approach to solve the multiple-choice multidimensional knapsack problem (MMKP). This problem concerns many real life problems, and is hard to solve due to its strong constraints and NP-hard property. The ACO approach given in this paper follows the algorithmic scheme of max-min ant system, but has some new features with respect to the characteristics of the MMKP. First, a single-group-oriented solution construction method is proposed, which allows ants to generate solutions efficiently. Second, some Lagrangian dual information obtained from a Lagrangian relaxation of MMKP is integrated into ACO. In addition, we develop a novel repair operator, with which the possible infeasible solutions generated by ants can be fixed. The proposed approach has been tested on a number of MMKP instances. Computational results show that it is able to produce competitive solutions in comparison with existing algorithms.


RWA: Classification and Computing

Room: Douglas Fir

Session Chair: Kaoru Shimada (Waseda University)

14:00-14:25 Using Feature Construction to Avoid Large Feature Spaces in Text Classification

Elijah Mayfield, Carolyn Penstein-Ros

feature space design, text classification, sentiment analysis

Feature space design is a critical part of machine learning. This is an especially difficult challenge in the field of text classification, where an arbitrary number of features of varying complexity can be extracted from documents as a preprocessing step. A challenge for researchers has consistently been to balance expressiveness of features with the size of the corresponding feature space, due to issues with data sparsity that arise as feature spaces grow larger. Drawing on past successes utilizing genetic programming in similar problems outside of text classification, we propose and implement a technique for constructing complex features from simpler features, and adding these more complex features into a combined feature space which can then be utilized by more sophisticated machine learning classifiers. Applying this technique to a sentiment analysis problem, we show encouraging improvement in classification accuracy, with a small and constant increase in feature space size. We also show that the features we generate carry far more predictive power than any of the simple features they contain.

14:25-14:50 A Method of Association Rule Analysis for Incomplete Database Using Genetic Network Programming

Kaoru Shimada, Kotaro Hirasawa

Association Rules, Missing Data, Genetic Network Programming

A method of association rule mining from incomplete databases is proposed using Genetic Network Programming (GNP). GNP is one of the evolutionary optimization techniques, which uses the directed graph structure. An incomplete database includes missing data in some tuples. Previous rule mining approaches cannot handle incomplete data directly. The proposed method can extract rules directly from incomplete data without generating frequent itemsets used in conventional approaches. In this paper, the proposed method is combined with difference rule mining using GNP for flexible association analysis. We have evaluated the performances of the rule extraction from incomplete medical datasets generated by random missing values. In addition, artificial missing values for privacy hiding are considered using the proposed method.


 14:50-15:15 Biogeography-Based Optimization of Neuro-Fuzzy System Parameters for Diagnosis of Cardiac Disease

Mirela Ovreiu, Dan Simon

evolutionary algorithm, biogeography-based optimization, neuro-fuzzy system, electrocardiogram

Cardiomyopathy refers to diseases of the heart muscle that becomes enlarged, thick, or rigid. These changes affect the electrical stability of the myocardial cells, which in turn predisposes the heart to failure or arrhythmias. Cardiomyopathy in its two common forms, dilated and hypertrophic, implies enlargement of the atria; therefore, we investigate its diagnosis through P wave features. In particular, we design a neuro-fuzzy network trained with a new evolutionary algorithm called biogeography-based optimization (BBO). The neuro-fuzzy network recognizes and classifies P wave features for the diagnosis of cardiomyopathy. In addition, we incorporate opposition-based learning in the BBO algorithm for improved training. First we develop a neuro-fuzzy model structure to diagnose cardiomyopathy using P wave features. Next we train the network using BBO and a clinical database of ECG signals. Preliminary results indicate that cardiomyopathy can be reliably diagnosed with these techniques.

15:15-15:40 Constructing Numerically Stable Real Number Codes using Evolutionary Computation

Aaron Garrett, Zizhong Chen, Daniel Eric Smith

genetic algorithms, evolutionary computation, error-correcting codes

Real number codes have been widely used in many applications. However, it is di cult to analytically fi nd the numerically optimal codes even for three erasures. In this paper, an evolutionary computation approach is presented which can computationally construct real number codes that have near optimal numerical stability. Experimental results demonstrate that the evolutionary algorithm presented here produces real number codes close to the theoretical optimum for two erasures. The real number codes obtained from the evolutionary algorithm outperform any known existing real number codes for three erasures.


GBML: Classification and Datamining

Room: Sunstone

Session Chair: Jaume Bacardit (University of Nottingham)

14:00-14:25 In Search of Targeted-Complexity Problems

Nuria Macia, Albert Orriols-Puig, Ester Bernado-Mansilla

Data complexity, Evolutionary multiobjective optimization, Artificial data sets

Currently available real-world problems do not cover the whole complexity space and, therefore, do not allow us to thoroughly test learner behavior on the border of its domain of competence. Thus, the necessity of developing a more suitable testing scenario arises. With this in mind, data complexity analysis has shown promise in characterizing difficulty of classification problems through a set of complexity descriptors which used in artificial data sets generation could supply the required framework to refine and design learners. This paper, then, proposes the use of instance selection based on an evolutionary multiobjective technique to generate data sets that meet specific characteristics established by such complexity descriptors. These artificial targeted-complexity problems, which capture the essence of real-world structures, may help to define a set of benchmarks that contributes to test the properties of learners and to improve them.


 14:25-14:50 Genetic Rule Extraction Optimizing Brier Score

Ulf Johansson, Rikard Konig, Lars Niklasson

Rule extraction, Brier score, Genetic programming

Most highly accurate predictive modeling techniques produce opaque models. When comprehensible models are required, rule extraction is sometimes used to generate a transparent model, based on the opaque. Naturally, the extracted model should be as similar as possible to the opaque. This criterion, called fidelity, is therefore a key part of the optimization function in most rule extracting algorithms. To the best of our knowledge, all existing rule extraction algorithms targeting fidelity use 0/1 fidelity, i.e., maximize the number of identical classifications. In this paper, we suggest and evaluate a rule extraction algorithm utilizing a more informed fidelity criterion. More specifically, the novel algorithm, which is based on genetic programming, minimizes the difference in probability estimates between the extracted and the opaque models, by using the generalized Brier score as fitness function. Experimental results from 26 UCI data sets show that the suggested algorithm obtained considerably higher accuracy and significantly better AUC than both the exact same rule extraction algorithm maximizing 0/1 fidelity, and the standard tree inducer J48. Somewhat surprisingly, rule extraction using the more informed fidelity metric normally resulted in less complex models, making sure that the improved predictive performance was not achieved on the expense of comprehensibility.


EMO: Algorithms

Room: Salmon

Session Chair: Hisao Ishibuchi (Osaka Prefecture University)

14:00-14:25 A Mono Surrogate for Multiobjective Optimization

Ilya Loshchilov, Marc Schoenauer, Michele Sebag

Multiobjective Optimization, Surrogate Models, Support Vector Machine

Most surrogate approaches to multi-objective optimization build a surrogate model for each objective. These surrogates can be used inside a classical Evolutionary Multiobjective Optimization Algorithm (EMOA) in lieu of the actual objectives, without modifying the underlying EMOA; or to filter out points that the models predict to be uninteresting. In contrast, the proposed approach aims at building a global surrogate model defined on the decision space and tightly characterizing the current Pareto set and the dominated region, in order to speed up the evolution progress toward the true Pareto set. This surrogate model is specified by combining a One-class Support Vector Machine (SVMs) to characterize the dominated points, and a Regression SVM to clamp the Pareto front on a single value. The resulting surrogate model is then used within state-of-the-art EMOAs to pre-screen the individuals generated by application of standard variation operators. Empirical validation on classical MOO benchmark problems shows a significant reduction of the number of evaluations of the actual objective functions.

14:25-14:50 An Archived-Based Stochastic Ranking Evolutionary Algorithm (ASREA) for Multi-Objective Optimization

Deepak Sharma, Pierre Collet

Stochastic Ranking, Evolutionary Algorithms, Multiobjective Optimization, Performance Assessment

In this paper, we propose a new multi-objective optimization algorithm called Archived-based Stochastic Ranking Evolutionary Algorithm (ASREA) that ranks the population by comparing individuals with members of an archive. The stochastic comparison breaks the usual O(mn2) complexity into O(man) (m being the number of objectives, a the size of the archive and n the population size), whereas updating the archive with distinct and well-spread non-dominated solutions and developed selection strategy retain the quality of state of the art deterministic multi-objective evolutionary algorithms (MOEAs). Comparison on ZDT and 3-objective DTLZ functions shows that ASREA converges on the Pareto-optimal front at least as well as NSGA-II and SPEA2 while reaching it much faster, and being cheaper on ranking comparisons.







Genetic and Evolutionary Computation Conference (GECCO-2010)
GECCO 2009 site   GECCO 2008 site       GECCO 2007 site     GECCO 2006 site      GECCO 2005 site         GECCO 2004 site    
GECCO 2003 site       GECCO 2002 site         GECCO 2001 site      GECCO 2000 site      GECCO 1999 site