Friday 9 July 10:40  12:20
RWA: Best Paper Nominees
Room: Salon A
Session Chair: Edgar GalvanLopez (Essex University)
10:4011:05 * A NeuroEvolutionary Approach to Micro Aerial Vehicle Control
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 nonlinear dynamics. Such methods rely heavily on difficult to obtain models and are particularly illsuited to the stochastic and dynamic environments in which MAVs operate. Instead, in this paper, we focus on a neuroevolutionary 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:0511:30 * Robust NeuroControl for A Micro Quadrotor
Learning
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 neurocontroller 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 neuroevolutionary control recovers from disturbances over an order of magnitude faster than a basic PID controller. Finally, the neuroevolutionary 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:3011:55 * Optimization of the Hölder Image Descriptor using a Genetic Algorithm
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 FMeasure, 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:5512:20 * EvolutionaryBased ConflictFree Scheduling of Collective Communications on Spidergon NoCs
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 pairwise routing algorithms. The paper investigates complexity of CCs in terms of lower bounds on the number of communication steps at conflictfree scheduling. The considered networks on chip make use of wormhole switching, full duplex links and allport noncombining nodes. A search for conflictfree 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 startup time and link bandwidth. Performance prediction of applications with CCs among computing nodes of the Spidergon network is thus possible.
ACOSI: Particle Swarm Optimization I
Room: Salon B
Session Chair: Kalyanmoy Deb (IIT Kanpur)
10:4011:05 Particle Swarm Optimization with Triggered Mutation and Its Implementation based on GPU
Particle Swarm Optimization, Mutation, GPU, Speedup
A novel particle swarm optimization with triggered mutation (PSOTM) 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 PSOTM. The results show that the PSOTM performs much better than the standard PSO on almost all of the 29 test functions, especially those multimodal, complex ones of hybrid composition. Besides, PSOTM adds little computation complexity to the standard PSO, and runs almost equally fast. Furthermore, we have implemented PSOTM based on Graphic Processing Unit (GPU) in parallel. Compared with the CPUbased standard PSO, the proposed PSOTM can reach a speedup of 25 times, as well as an improved optimizing performance.
11:0511:30 Development of Efficient Particle Swarm Optimizers by Using Concepts from Evolutionary Algorithms
Particle swarm optimization, Evolutionary optimization, G3PCX, unimodal problems, recombination, steadystate 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 EAspecific operators to enhance the PSO's performance. Our final proposed PSO contains a parentcentric recombination operator instead of usual particle update rule, but maintains PSO's individualistic trait and has a demonstrated performance comparable to a wellknown GA (and outperforms the GA in some occasions). Moreover, the modified PSO algorithm is found to scale up to solve as large as 100variable problems. This study emphasizes the need for similar such studies in establishing an equivalence between various genetic/evolutionary and other bioinspired algorithms, a process that may lead us to better understand the scope and usefulness of variousoperators associated with each algorithm.
11:3011:55 An Empirical Comparison of Parallel and Distributed Particle Swarm Optimization Methods
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 coevolving swarms, a different multiswarm 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 CEC2005 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 CEC2005 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 realvalued parameters. We propose to integrate the CEC2005 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 multiswarm system outperforms all the other presented methods.
GA: Coevolution & Niching
Room: Salon C
Session Chair: Sushil Louis (UNR)
10:4011:05 Generalized Crowding for Genetic Algorithms
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:0511:30 Complex Energy Landscape Mapping by Histogram Assisted Genetic Algorithm
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 multimodal 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:3011:55 CoEvolution of Cooperative Strategies under Egoism
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 auctionbased manpower allocation problem, the problem is adopted for further investigation. To alleviate analytical burden, the problem is abstracted to a resourcebidding game under the Nash game framework. A mathematical model for the resourcebidding game is defined and several special cases are illustrated. One of these special cases, named cmNE, is further investigated due to the existance of cooperative modes. Various kinds of egoistic fitness functions and evolutionary mechanisms are experimented on cmNE. 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:5512:20 Coevolving Influence Maps for Spatial Team Tactics in a RTS Game
Coevolution, 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.
HumanCompetitive Results
Room: Salon D
Session Chair:
10:4012:20 Humie finalists will give short oral presentations about humancompetitive 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:4011:05 Cooperative SelfOrganization in a Heterogeneous Swarm Robotic System
swarm robotics, swarm intelligence, selforganization, 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 footbots, and the second type are flying robots that can attach to the ceiling, called eyebots. While the footbots perform the actual foraging, i.e. they move back and forth between a source and a target location, the eyebots are deployed in stationary positions against the ceiling, with the goal of guiding the footbots. The key component of our approach is a process of mutual adaptation, in which footbots execute instructions given by eyebots, and eyebots observe the behavior of footbots 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 subswarms of different robots, we refer to it as cooperative selforganization. This is to our knowledge the first work that investigates such a system in swarm robotics.
11:0511:30 Revising the Evolutionary Computation Abstraction: Minimal Criteria Novelty Search
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 fitnesspressurebased 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 fitnessbased 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:3011:55 Guarding Against Premature Convergence while Accelerating Evolutionary Search
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 agelayered 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:5512:20 * Crossing the Reality Gap in Evolutionary Robotics by Promoting Transferable Controllers
reality gap problem, Evolutionary Robotics, multiobjective optimization, simulationtoreality 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 realworld 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 multiobjective formulation of ER in which two main objectives are optimized via a Paretobased MultiObjective Evolutionary Algorithm: (1) the fitness and (2) the transferability. To evaluate this second objective, a simulationtoreality disparity value is approximated for each controller. The proposed method is applied to the evolution of walking controllers for a real 8DOF quadrupedal robot. It successfully finds efficient and welltransferable controllers with only a few experiments in reality.
Theory: Best Paper Nominees
Room: Salon I
Session Chair: Carsten Witt (Technical University of Denmark)
10:4011:05 * Necessary and Sufficient Conditions for Success of the Metropolis Algorithm for Optimization
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:0511:30 * Multiplicative Drift Analysis
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 runtime 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:3011:55 * Ant Colony Optimization for Stochastic Shortest Path Problems
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 gammadistributed 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:5512:20 * BlackBox Search by Unbiased Variation
Runtime Analysis, BlackBox Complexity
The complexity theory for blackbox 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 tradeoff between the generality of the blackbox model and the strength of the bounds that can be proven in such a model. In particular, the original blackbox model allows polynomial complexity for certain NPcomplete problems and provides for wellknown benchmark problems relatively small lower bounds, which are typically not met by popular search heuristics. In this paper, we introduce a more restricted blackbox 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 blackbox 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.
ECP
Room: Portland
Session Chair: Jorn Mehnen, Thomas BartzBeielstein, Thomas Baeck, Erik Goodman
10:4012: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:0014:25 * Phenotype Feedback Genetic Algorithm Operators for Heuristic Encoding of Snakes within Hypercubes
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 snakeinthebox 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:2514:50 * NK Landscapes, Problem Difficulty, and Hybrid Evolutionary Algorithms
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 nearestneighbor 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:5015:15 Edgebased Representation Beats Vertexbased Representation in Shortest Path Problems
Evolutionary algorithm, runtime analysis, shortest path
In this paper, we present a new representation for individuals in the singlesource 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 singlesource shortest path problem. For both the multicriteria formulation of the problem (introduced by Scharnow, Tinnefeld and Wegener (2002, 2004)) and the singlecriteria 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.
Competitions
Room: Salon B
Session Chair:
14:0015:40 Competitions finalists presentations
SBSE: Best Paper Nominees
Room: Salon C
Session Chair: Mathew Hall (University of Sheffield)
14:0014:25 On the Use of Genetic Programming for Automated Refactoring and the Introduction of Design Patterns
searchbased software engineering, objectoriented design, refactoring, design patterns, software metrics, evolutionary computation, intelligent search
Maintaining an objectoriented design for a piece of software is a difficult, timeconsuming 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 realworld case study.
14:2514:50 * Empirically Studying the Role of Selection Operators DuringSearchBased Test Suite Prioritization
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 algorithmbased 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 algorithmbased prioritizer is superior to random search and hill climbing and thus suitable for many regression testing environments.
14:5015:15 * SearchBased Test Data Generation from Stateflow Statecharts
Automation, Coverage, Model Testing, Optimization, SearchBased 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:1515:40 Factors Affecting the Use of Genetic Algorithms in Test Suite Augmentation
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.
ACOSI: Best Paper Nominees Ant Colony Optimization
Room: Salon D
Session Chair: Frederick Ducatelle (IDSIA)
14:0014:25 * A Few Ants are Enough: ACO with IterationBest Update
Ant Colony Optimization, IterationBest 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 iterationbest 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 iterationbest update that depends on a tradeoff between the number of ants and the evaporation rate.
14:2514:50 * The Impact of Design Choices of Multiobjective AntColony Optimization Algorithms on Performance:An Experimental Study on the Biobjective TSP
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 tradeoffs in their performance.
14:5015:15 PheromoneDistributionBased Adaptive Ant Colony System
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:1515:40 An Antcolonysystembased Activity Scheduling Method for the Lifetime Maximization of Heterogeneous Wireless Sensor Networks
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 antcolonysystembased scheduling method (ACSSM) 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 ACSSM adapts the incremental solution construction mechanism in ACS for building disjoint connected cover sets on the basis of a welldesigned 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. ACSSM is applied to fifteen WSN cases in three series. Experimental results show that the proposed method can find highquality 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:0014:25 * Resource Abundance Promotes the Evolution of Public Goods Cooperation
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 noncooperating 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:2514:50 * Evolution of Vision Capabilities in Embodied Virtual Creatures
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:5015:15 Coevolution of Heterogeneous MultiRobot Teams
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:1515:40 Evolution of Division of Labor in Genetically Homogenous Groups
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:0014:25 Elementary Landscapes of Frequency Assignment Problems
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:2514:50 Theoretical Analysis of Evolutionary Computation on Continuously Differentiable Functions
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 ECbased stochastic algorithms, namely, a CMAES employing rankμ update and an EDA known as EMNA_{global}. 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 wellbehaved optimization algorithms.
14:5015:15 Elementary Landscape Decomposition of the Quadratic Assignment Problem
Fitness Landscapes, Elementary Landscapes, Quadratic Assignment Problem
The Quadratic Assignment Problem (QAP) is a wellknown NPhard combinatorial optimization problem that is at the core of many realworld 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.
ECP
Room: Portland
Session Chair: Thomas BartzBeielstein, Thomas Baeck, Erik Goodman
14:0015: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 MilanoBicocca)
16:1016:35 * Abstract Functions and Lifetime Learning in Genetic Programming for Symbolic Regression
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:3517:00 * The Estimation of Hölderian Regularity using Genetic Programming
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 GPoperators 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:0017:25 Designing Better Fitness Functions for Automated Program Repair
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:2517:50 Grammar Guided Genetic Programming for Multiple Instance Learning: An Experimental Study
Multiple Instance Learning, Grammar Guided Genetic Programming, Rule Learning
This paper introduces a new GrammarGuided Genetic Programming algorithm for solving multiinstance Learning problems. This algorithm, called G3PMI, is evaluated and compared with other MultiInstance classification techniques on different application domains. Computational experiments show that the G3PMI 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 IFTHEN rules. Our results confirm that evolutionary algorithms are appropriate for dealing with multiinstance learning problems.
RWA: Business and Food Science
Room: Salon B
Session Chair: Edgar GalvanLopez (Essex University)
16:1016:35 A New Modular Genetic Programming for Finding AttractiveTechnical Patterns in Stock Markets
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:3517:00 Interday Foreign Exchange Trading using Linear Genetic Programming
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:0017:25 Evolutionary Optimization of Flavors
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 ParetoGenetic 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 multiobjective 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 consistentlyliked, 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:2517:50 MixedInteger Evolution Strategy Using Multiobjective Selection Applied to Warehouse Design Optimization
Business planning and operations research, evolution strategies, representations, multiobjective optimization, combinatorial optimization
This paper reports about the application of a new variant of multiobjective MixedInteger Evolution Strategy to a warehouse design optimization problem. The algorithm is able to deal with realvalued, 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 expertgenerated solutions. Moreover, the algorithm is able to fi nd solutions which improve on the expertgenerated solutions with respect to both objectives.
SBSE: Requirements and Design
Room: Salon C
Session Chair: Myra Cohen (University of NebraskaLincoln)
16:1016:35 Approximate Backbone Based Multilevel Algorithm for Next Release Problem
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 NPhard problem in software requirement engineering, NRP lacks efficient approximate algorithms for large scale instances. The backbone is a new tool for tackling large scale NPhard 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 NPhard 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:3517:00 Today/Future Importance Analysis
Pareto optimality, Today/Future, multiobjective 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 multiobjective formulation of the problem which is implemented using multiobjective Pareto optimal evolutionary algorithms. The paper presents the results of experiments on both synthetic and real world data.
17:0017:25 Superstate Identification for State Machines Using SearchBased Clustering
state machines, searchbased clustering, hillclimbing, 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 uptodate 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 searchbased 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 searchbased clustering tool, which demonstrates the usefulness of the approach.
ACOSI: Particle Swarm Optimization II
Room: Salon D
Session Chair: Carlos A. Coello Coello (CINVESTAVIPN)
16:1016:35 Particle Swarm Optimizer with Selfadjusting Neighborhoods
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 selfadjusting 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:3517:00 Stigmergic Landmark Routing
Wireless Mobile Adhoc Routing, MultiAgent Systems, Swarm Intelligence, Bee Colony Optimization
Mobile Adhoc 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 setup 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 adhoc 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 endtoend delay, low scalability, and low average performance. In this paper we present a novel Swarm Intelligence routing algorithm for Wireless Mobile Adhoc 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:0017:25 SelfAdaptive Differential EvolutionBased on PSO Learning Strategy
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 PSOLearning (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 selfadaptation 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 stateoftheart adaptive DE variants.
EMO: Applications and Algorithms
Room: Salon G
Session Chair: Joshua D Knowles (University of Manchester)
16:1016:35 Deterministic HelperObjective Sequences Applied to JobShop Scheduling
Multiobjectivization, Helperobjective, Nondominated 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 JobShop Scheduling Problem has been shown in the past to perform better than a single objective Genetic Algorithm (GA). Helperobjectives, representing portions of the main objective, were used in the past to guide the MOEA search process. This paper explores additional understanding of helperobjective sequencing. The sequence in which helperobjectives are used is examined and it is shown that problem specific knowledge can be incorporated to determine a good helperobjective sequence. Results demonstrate how carefully sequenced helperobjectives 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 helperobjective sequence appears to break epistasis early in a search which implies that it is important for helperobjective methods to examine the sequence of objectives.
16:3517:00 Finding Multiple Solutions for Multimodal Optimization Problems Using a MultiObjective Evolutionary Approach
Multimodal optimization, multiobjective optimization, NSGAII, HookeJeeve'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 singleobjective evolutionary algorithm framework so that similar solutions in a population are deemphasized in order to focus and maintain multiple distant yet nearoptimal solutions. In this paper, we use a completely different and generic strategy in which a singleobjective multimodal optimization problem is converted into a suitable biobjective optimization problem so that all local and global optimal solutions become members of the resulting weak Paretooptimal set. We solve up to 16variable testproblems having as many as 48 optima and also demonstrate successful results on constrained multimodal testproblems, suggested for the first time. The concept of using multiobjective optimization for solving singleobjective multimodal problems seems novel and interesting, and importantly opens further avenues for research.
17:0017:25 Improved Step Size Adaptation for the MOCMAES
multiobjective optimization, step size adaptation, covariance matrix adaptation, evolution strategy, MOCMAES
The multiobjective covariance matrix adaptation evolution strategy (MOCMAES) is an evolutionary algorithm for continuous vectorvalued optimization. It combines indicatorbased selection based on the contributing hypervolume with the efficient strategy parameter adaptation of the elitist covariance matrix adaptation evolution strategy (CMAES). Step sizes (i.e., mutation strengths) are adapted on individuallevel using an improved implementation of the 1/5th success rule. In the original MOCMAES, a mutation is regarded as successful if the offspring ranks better than its parent in the elitist, rankbased 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 MOCMAES, in particular of its steadystate variant. The new step size adaptation improves the performance of the MOCMAES 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 MOCMAES for problems with more than two objectives.
17:2517:50 Evolving Agent Behavior In Multiobjective Domains Using FitnessBased Shaping
Multiobjective optimization, Neural networks, Multiagent 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 fitnessbased 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 NSGAII and evaluated in a multiobjective battle domain. Both methods outperform plain NSGAII 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:1016:35 Ant Colony Optimization and the Minimum Cut Problem
Ant Colony Optimization, Mincut
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:3517:00 Quasirandom Evolutionary Algorithms
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 Ω (n^{2}) time. However, we also find that quasirandom ideas, if implemented correctly, can yield an over 50\, \% speedup.
17:0017:25 Can Quantum Search Accelerate Evolutionary Algorithms?
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 pseudoBoolean optimization problems OneMax, LeadingOnes, and Discrepancy. 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 Discrepancy, 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:1016:35 * The Baldwin Effect in Developing Neural Networks
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 evolutionlearning 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:3517:00 * Task Transfer through Indirect Encoding
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 twodimensional map. Yet the problem is that a raw twodimensional map is highdimensional 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:0017:25 * Image Compression of Natural Images Using Artificial Gene Regulatory Networks
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:2517:50 * Evolving the Placement and Density of Neurons in the HyperNEAT Substrate
Substrate Evolution, NEAT, HyperNEAT, Neuroevolution
The Hypercubebased 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 highdimensional 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 evolvablesubstrate HyperNEAT (ESHyperNEAT) that determines the placement and density of the hidden nodes based on a quadtreelike 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, ESHyperNEAT 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 (CINVESTAVIPN) 10:4011:05 * Integrating Decision Space Diversity into Hypervolumebased Multiobjective Search 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 closetooptimal 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 Paretoset 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 highquality Paretoset approximations. To this end we propose an approach to integrate decision space diversity into hypervolumebased multiobjective search. We present a modified hypervolume indicator and integrate it into an evolutionary algorithm. The proofofprinciple results show the potential of the approach and indicate further research directions for structureoriented multiobjective search. 11:0511:30 * A GridBased Fitness Strategy for Evolutionary ManyObjective Optimization Multiobjective optimization, manyobjective optimization, fitness assignment, grid Grid has been widely used in the field of evolutionary multiobjective optimization (EMO) due to its property combining convergence and diversity naturally. Most EMO algorithms of gridbased fitness perform well on problems with two or three objectives, but encounter difficulties in their scalability to manyobjective optimization. This paper develops the potential of using grid technique to balance convergence and diversity in fitness for manyobjective optimization problems. To strengthen selection pressure and refine comparison level, three hierarchical gridbased 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 wellconverged and welldistributed solution set. 11:3011:55 * The Maximum Hypervolume Set Yields Nearoptimal Approximation 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 nearoptimal approximation ratio.
11:5512:20 DBSCAN Based MultiObjective Niching to Approximate Equivalent ParetoSubsets 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 Paretofront. The detection of equivalent Paretosubsets may be desirable. In this paper we introduce a niching method that approximates Paretooptimal 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 multiobjective 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 Smetric.
EDA: Best Paper Nominees and Multimodal EDAs Room: Salon B Session Chair: Peter A.N. Bosman (Centre for Mathematics and Computer Science) 10:4011:05 * Effective Structure Learning for EDA via L1RegularizedBayesian Networks Bayesian optimization algorithm, Bayesian network, L1penalized 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 L1regularized 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 L1regularized learning. Experimental studies on different types of benchmark problems are carried out, which show that L1BOA outperforms the standard BOA when no apriori knowledge about the problem structure is available, and nearly achieves the best performance of BOA that applies explicit complexity controls. 11:0511:30 * EntropyBased Substructural Local Search for the Bayesian Optimization Algorithm 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 entropybased 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:3011:55 * The Anticipated Mean Shift and Cluster Registration in Mixturebased EDAs for MultiObjective Optimization Estimation of Distribution Algorithms, MultiObjective Optimization, Mixture Distribution, Anticipation It is known that in realvalued SingleObjective (SO) optimization with Gaussian EstimationofDistribution 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 MultiObjective (MO) optimization the risk of overfitting is even larger and only further increased if clustered variation is used, a technique often employed in MultiObjective 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 mixturebased version straightforwardly. Finally, we point out the benefit of injecting solutions obtained from running equalcapacity SO optimizers in synchronous parallel and investigate experimentally, using 9 wellknown benchmark problems, the advantages of each of the techniques. 11:5512:20 Multivariate MultiModel Approach for Globally Multimodal Problems Estimation of distribution algorithms, EDAs, Global multimodality, Globally multimodal problems, Marginal product models, Multimodel 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 realworld 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 wellknown 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:4011:05 Applying the Triple Parameter Hypothesis to Maintenance Scheduling 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:0511:30 Optimizing Genetic Operator Rates Using A Markov Chain Model of Genetic Algorithms 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 wellknown relevant algorithms. The results demonstrate that the newly suggested algorithm significantly outperforms its rivals. 11:3011:55 An Exploration into Dynamic Population Sizing 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 stateoftheart population sizing EAs, exploring the strengths and weaknesses of each. 11:5512:20 Toward Comparisonbased Adaptive Operator Selection Parameter Control, Adaptive Operator Selection, ROC Area Under Curve, MultiArmed 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 fitnessbased credit assignment forbid any invariance by monotonous transformation of the fitness, what is a usual source of robustness for comparisonbased 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 MultiArmed 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 hyperparameter and fitness transformations. Furthermore, using fitness ranks as raw reward results in a fully comparisonbased AOS with reasonable performances.
RWA: Manufacturing, Scheduling, Timetabling and Robotics Room: Salon D Session Chair: Christian Gagne (Informatique WGZ Inc.) 10:4011:05 Evolutionary Multiobjective Optimization and Decision Making for Selective Laser Sintering Multiobjective 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 multiobjective evolutionary optimizers  NSGAII (nondominated sorting genetic algorithm) and MOPSO (multiobjective particle swarm optimizer). The performance comparison of these two optimizers along with an approximation of Paretooptimal 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 tradeoff solutions, are introduced to facilitate the designer. The overall procedure is integrated into MORPE  Multiobjective 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:0511:30 Evolving Robust Controller Parameters using Covariance Matrix Adaptation 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 PIDcontroller parameters are sought for an exemplary system, which simulates a humanlike 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:3011:55 Selection Mechanisms in Memory Consideration for Examination Timetabling with Harmony Search 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, globalbest memory consideration which uses a selection mechanism inspired by a global best concept of Particle Swarm Optimisation (PSO), and RouletteWheel 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 RouletteWheel 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:5512:20 Evolutionary Algorithms in LargeScale Open Pit Mine Scheduling Evolutionary optimization, open pit mine scheduling, combinatorial optimization, customized operators With many years of research and application to realworld 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 multiobjective 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:4011:05 Towards an Understanding of Locality in Genetic Programming 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., treelike structures). The aim of this paper is to address this important research gap. We extend the genotypephenotype definition of locality to GP by studying the relationship between genotypes and fitness. We consider a mutationbased 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:0511:30 Measuring Bloat, Overfitting and Functional Complexity in Genetic Programming Genetic Programming, Bloat, Overfitting, Complexity Recent contributions clearly show that eliminating bloat in a genetic programming system does not necessarily eliminate overfitting and viceversa. 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 reallife 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:3011:55 ObjectLevel Recombination of Commodity Applications genetic algorithms, genetic programming, software recombination, ObjRecombGA, objectlevel 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 wellknown 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:5512:20 Robust Symbolic Regression with Affine Arithmetic 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:4011:05 Evolving Neural Networks in Compressed Weight Space 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 highfrequency 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: polebalancing, 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:0511:30 Neuroevolution of Mobile Ad Hoc Networks Neuroevolution, neural network, generative, developmental, mobile adhoc 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:3011:55 Evolving CPPNs to Grow ThreeDimensional Physical Structures 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 biomimicked robot morphologies. However, there are reasons why coevolving morphology along with control may provide a better path towards realizing intelligent agents. Towards this goal, a novel method for evolving threedimensional physical structures using CPPNNEAT is introduced which is capable of producing artifacts that capture the nonobvious 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:5512:20 Investigating Whether HyperNEAT Produces Modular Neural Networks 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 highlevel 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.
ECP Room: Salem Session Chair: Jorn Mehnen 10:4012:20 EC in Design
ESEP: Best Paper Nominees Room: Salon A Session Chair: Anne Auger (INRIA) 14:0014:25 * Exponential Natural Evolution Strategies evolution strategies, natural gradient, black box optimization, unconstrained optimization The family of natural evolution strategies (NES) offers a principled approach to realvalued evolutionary optimization by following the natural gradient of the expected fitness. Like the wellknown CMAES, 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 CMAES are closely related to the natural gradient updates of xNES. However, xNES is more principled than CMAES, 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:2514:50 * On the Analysis of SelfAdaptive Evolution Strategies on Elliptic Model: First Results Evolution strategy, elliptic model, selfadaptation, progress rate, mutation strength In this paper, first results on the analysis of selfadaptive 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:5015:15 * Adaptive Strategy Selection in Differential Evolution 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 problemdependent. 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:1515:40 * Active Covariance Matrix Adaptation for the (1+1)CMAES Stochastic optimisation, variable metric algorithm, evolution strategy, covariance matrix adaptation We propose a novel variant of the (1+1)CMAES 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:0014:25 Spurious Dependencies and EDA Scalability 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:2514:50 A Robust Estimation of Distribution Algorithm for Power Electronic Circuits Design 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 gradientbased methods, the hillclimbing 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 histogrambased estimation of distribution algorithm with an adaptive refinement process (EDA/ar). In the EDA/ar, the histogrambased 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 bestsofar 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/ar 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/ar can obtain much better mean solution quality and is less likely to be trapped into local optima.
14:5015:15 Entropy MeasurementBased Estimation Model for Bayesian Optimization Algorithm 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 (enBOA). In particular, the concept of entropy is used to develop the evaluation relaxation strategy (ERS) and to determine the rate of convergence. Entropy measurementbased 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 enBOA significantly reduces the number of actual evaluations and the scalability of BOA is not negatively affected. Moreover, the entropy measurementbased evaluation relaxation technique does not require any larger population sizes. 15:1515:40 Dvine EDA: a new Estimation of Distribution Algorithm based on Regular Vines Regular vines, Dvine, Gaussian copula, EDAs A new Estimation of Distribution Algorithm is presented. The proposed algorithm, called Dvine 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 Dvine EDA and performs experiments and statistical tests to assess the best algorithm. The set of experiments shows the potential of the Dvine EDA.
GA: Theory Room: Salon C Session Chair: Thomas Jansen (University College Cork) 14:0014:25 Analysis of the Effects of Lifetime Learning on Population Fitness using Vose Model 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 Lamarckianlike 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:2514:50 Investigating EA Solutions for Approximate KKT Conditions in Smooth Problems nonlinear programming, KarushKuhnTucker conditions, termination condition, Evolutionary Optimization Evolutionary algorithms (EAs) are increasingly being applied to solve realparameter optimization problems due to their flexibility in handling complexities such as nonconvexity, nondifferentiability, multimodality 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 nearoptimal point is found. We address both these issues in this paper by integrating the KarushKuhnTucker (KKT) optimality conditions that involve firstorder derivatives of objective and constraint functions with an EA. For this purpose, we define a KKTproximity 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 KKTproximity measure can be used a termination criterion in an EA simulation. 14:5015:15 Aging Beyond Restarts 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:0014:25 Evolving Viral Marketing Strategies Viral Marketing, AgentBased 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 Basslike agentbased model, with five different social network structures: four classic theoretical models (random, lattice, smallworld, 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 parameterspace of agentbased 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 nearoptimal for the four theoretical networks, but that a more nuanced strategy performs significantly better on the empirical Twitterbased network. We also find a correlation between the optimal seeding budget for a network, and the inequality of the degree distribution.
14:2514:50 On Heuristics for TwoSided Matching: Revisiting the Stable Marriage Problem as a Multiobjective Problem centralized markets, agentbased models, evolutionary computation, twosided matching, stable marriage problem, deferred acceptance algorithm The stable marriage problem is prototypical of twosided 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 wellknown GaleShapley deferred acceptance algorithm (GS/DAA) are used to find stable matches. Using evolutionary computation and an agentbased 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:5015:15 Multiobjective Evolutionary Algorithms for Dynamic Social Network Clustering graph clustering, dynamic optimisation, multiobjective evolutionary algorithm, social network, elitismbased 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 realworld 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:1515:40 ConBreO: A Music Performance Rendering System using Hybrid Approach of IEC and Automated Evolution 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:0014:25 On the Use of Genetic Programming for the Prediction of Survival in Cancer 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 70genes 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 70genes signature dataset with realvalued 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:2514:50 * P System Model Optimisation by Means of Evolutionary Based Search Algorithms Executable biology, P systems, Evolutionary algorithms, Realvalued 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 realvalued 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:5015:15 * The Application of MichiganStyle Learning ClassifierSystems to Address Genetic Heterogeneity and Epistasisin Association Studies 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 genotypetophenotype 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 (genegene 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 sidestep 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 MichiganStyle 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:1515:40 Selecting Predictive Features for Recognition of Hypersensitive Sites of Regulatory Genomic Sequences with an Evolutionary Algorithm 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 experimentallyknown features specific to regulatory sequences. Highthroughput 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 nonHS 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 stateoftheart classification methods. Analysis of these motifs reveals interesting insight into features employed by regulatory sequences to interact with DNAbinding enzymes.
PES: Best Paper Nominees Room: Salon I Session Chair: Enrique Alba (University of Málaga) 14:0014:25 * Parallel FPGAbased Implementation of Scatter Search Field programmable gate arrays; scatter search; data parallelism; pipelining; 01 knapsack problem; hardware acceleration Scatter Search is an effective and established populationbased metaheuristic that has been used to solve a variety of hard optimization problems. However, like most populationbased metaheuristics, the time required to find highquality solutions can become prohibitive as problem sizes grow. In this paper, we present a hardware implementation of scatter search on a FieldProgrammable GateArray (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 HandelC a programming language specifically designed to enable software developers to easily synthesize Clike 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:2514:50 * The Benefit of Migration in Parallel Evolutionary Algorithms 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:5015:15 * Shared Memory Genetic Algorithms in a MultiAgent Context Parallel genetic algorithms, shared memory, multiagents In this paper we present a concurrent implementation of genetic algorithms designed for shared memory architectures, intended to take advantage of multicore processor platforms. Our algorithm divides the problems into subproblems 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:0014:25 Importing the Computational Neuroscience Toolbox into NeuroEvolutionApplication to Basal Ganglia evolutionary algorithms, neural networks, computational neuroscience, basal ganglia, neuroevolution Neuroevolution 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 (spatiallyorganized identical neurons) should be the building blocks to evolve neural networks able to perform cognitive functions and (2) wellidentified modules of the brain for which there exists computational neuroscience models provide welldefined benchmarks for neuroevolution. 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 mapbased 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 brainlike neural networks; (3) the failure of direct encoding to solve the task validates the relevance of action selection as a benchmark for neuroevolution. 14:2514:50 Evolving heterochrony for cellular differentiation using vector field embryogeny 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:5015:15 Sustaining Behavioral Diversity in NEAT 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 phenotypesimilaritybased 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:1515:40 Self Modifying Cartesian Genetic Programming: Finding Algorithms that Calculate pi and e to Arbitrary Precision 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.
ECP Room: Salem Session Chair: Thomas BartzBeielstein 14:0015:40 EC in Statistics and EA consultancy
COM: Best Paper Nominees Room: Salon A Session Chair: Marc Schoenauer (INRIA Saclay) 16:1016:35 * An Efficient Algorithm for Generalized Minimum Spanning Tree Problem 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 intractable, many heuristic algorithms have been proposed to solve large GMST instances. Motivated by the effectiveness and efficiency of the muscle (the union of all optimal solutions) for solving other NPhard problems, we investigate how to incorporate the muscle into heuristic design for GMST. Firstly, we demonstrate that it s NPhard 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 reduced 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 demonstrate that our new algorithm slightly outperforms existing heuristic algorithms in terms of solution quality. 16:3517:00 * ConsultantGuided Search  A New Metaheuristic for Combinatorial Optimization Problems Metaheuristics, combinatorial optimization, swarm intelligence, traveling salesman problem In this paper, we present ConsultantGuided 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 CGSTSP algorithm, an instantiation of CGS for the Traveling Salesman Problem. To determine if our direct communication approach can compete with stigmergybased methods, we compare the performance of CGSTSP with that of Ant Colony Optimization algorithms. Our experimental results show that the solution quality obtained by CGSTSP is comparable with or better than that obtained by Ant Colony System and MAXMIN Ant System. 17:0017:25 * A Hierarchical Cooperative Evolutionary Algorithm 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 BartzBeielstein (Cologne University of Applied Sciences) 16:1016:35 Tuning Optimization Algorithms for RealWorld Problems by Means of Surrogate Modeling parameter tuning, surrogate model, experimental study The casespecific 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 realworlds 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:3517:00 Fitting MultiPlanet Transit Models to Photometric TimeData Series by Evolution Strategies Evolution Strategies, Exoplanets, Transits, Model Fitting, MultiPlanet Systems, GPU In this paper we present the application of an evolution strategy to the problem of detecting multiplanet transit events in photometric timedata 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 multiplanet 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:1016:35 AUC Analysis of the ParetoFront using Multiobjective GP for Classification with Unbalanced Data Genetic Programming, Classification, Class Imbalance, Evolutionary multiobjective Optimisation Learning algorithms can suffer a performance bias when data sets are unbalanced. This paper proposes a MultiObjective 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 Paretofront solutions using the Area Under the ROC Curve (AUC) and investigate which regions of the objective tradeoff surface favour highscoring AUC solutions. We show that a diverse set of wellperforming classifiers is simultaneously evolved along the Paretofront using the MOGP approach compared to canonical GP where only one solution is found along the objective tradeoff surface, and that in some problems the MOGP solutions had better AUC than solutions evolved with canonical GP using handcrafted fitness functions.
16:3517:00 Coevolutionary Multipopulation Genetic Programming for Data Classification 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 multiplepopulation genetic programming (GP) algorithm which exploits the technique of coevolution at two levels. On the interpopulation level the populations cooperate in a semiisolated fashion, whereas on the intrapopulation 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:1016:35 * Negative Selection Algorithms Without Generating Detectors Artificial Immune Systems, Negative Selection, Consistent Learning Negative selection algorithms are immuneinspired 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 nonexhaustive negative selection is more meaningful but it can be computationally more difficult, which we illustrate using Boolean monomials. 16:3517:00 * How XCS Deals with Rarities in Domains with Continuous Attributes class imbalance problem, small disjuncts, learning classifier systems, geneticbased machine learning Michiganstyle 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 intervalbased representation, which is most often used in data mining tasks. This paper therefore takes the original design decomposition and adapts it to the intervalbased representation. Theory and experimental evidence indicate that XCS with intervalbased 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 realworld problems.
17:0017:25 * Speeding Up the Evaluation of Evolutionary Learning Systems using GPGPUs Evolutionary Algorithms, Learning Classifier Systems, Rule Induction, Largescale 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 CUDAbased 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:1016:35 Initialization Parameter Sweep in ATHENA: Optimizing Neural Networks for Detecting GeneGene Interactions in the Presence of Small Main Effects 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 nonlinear, genegene interactions that can be difficult for traditional, parametric analyses to detect. In addition, exhaustively searching all multilocus 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:3517:00 Protein Structure Prediction on a Lattice Model via Multimodal Optimization Techniques 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 HydrophobicPolar (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 stateofthearts algorithms, even though they are simple.
17:0017:25 Challenges Rising from Learning Motif Evaluation Functions Using Genetic Programming Motif Discovery, Transcription Factor Binding Site (TFBS), Bioinformatics, Genetic Programming (GP), modelling Motif discovery is an important Bioinformatics problem for deciphering gene regulation. Numerous sequencebased 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 sequencebased 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 specialistmodellike 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 sequencebased motif discovery. However, when applied on different widelytested 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:1016:35 Selection Pressure and Takeover Time of Distributed Evolutionary Algorithms 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:3517:00 GPUbased Island Model for Evolutionary Algorithms 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 timeintensive 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 redesign, 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:4011:05 Semantics Based Crossover for Boolean Problems
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 wellknown 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:0511:30 New Crossover Operators in Linear Genetic Programming for Multiclass Object Classification
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:3011:55 A Probabilistic Functional Crossover Operator for Genetic Programming
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 subsolutions to subproblems, and the automated combination of these subsolutions 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 treebased genetic encodings have been proposed, but most consider crossing genetic components based on their structural similarity. In this work we introduce a treebased 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:4011:05 A Heuristicbased Hybrid Genetic Algorithm for Heterogeneous Multiprocessor Scheduling
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 heuristicbased hybrid Genetic Algorithm (GA) is proposed for solving the heterogeneous multiprocessor scheduling problem. The proposed algorithm extends traditional GAbased 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 problemspecific 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 upwardranking heuristic is introduced to determine the task sequence assignment in each processor. Simulation results indicate that our proposed algorithm consistently outperforms several stateofart 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:0511:30 A Hybrid Genetic Algorithm for Automatic Graph Drawing Based on the TopologyShapeMetric Approach.
Automatic Graph Drawing, topologyshapemetric, Genetic Algorithm, Combinatorial Optimization.
This paper presents a new approach for automatic graph drawing based on Genetic algorithms. The classical topologyshapemetric 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 NPhard 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 permutationbased combinatorial optimization problem. The problem is then solved with the genetic algorithm, using appropriate selection, crossover and mutation operators, which were adapted from other permutationbased 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 topologyshapemetric approach.
11:3011:55 Solving Multiobjective Flexible Jobshop Scheduling Using an Adaptive Representation
Flexible Job Shop Scheduling Problems, Genetic Algorithm, Multiobjective Optimization, Rescheduling, Representation
In this paper, we present an alternative representation for solving multiobjective Flexible Jobshop 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 threeobjective 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:5512:20 Breaking Ties with Secondary Fitness in a Genetic Algorithm for the Bin Packing Problem
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 permutationcoded genetic algorithm performs better when it applies this measure as a tiebreaker 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:4011:05 Heuristics for Sampling Repetitions in Noisy Landscapes with Fitness Caching
fitness caching, noise reduction, fitness landscapes, uncertainty, sampling, evolutionary algorithms, hill climbing
For many largescale combinatorial search/optimization problems, metaheuristic 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 wellknown testbed 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 randommutation hillclimber with fitness caching.
11:0511:30 On the Generality of Parameter Tuning in Evolutionary Planning
AI Planning, Memetic Algorithms, Parameter Tuning, Racing
DivideandEvolve (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 tradeoff between the gain in quality of the resulting plans and the overhead in terms of computational cost.
11:3011:55 Efficient Stochastic Local Search Algorithm for Solving the Shortest Common Supersequence Problem
Combinatorial optimization, Evolutionary algorithms, Stochastic local search
The Shortest Common Supersequence (SCS) problem is a wellknown 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 movingwindow 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 stateoftheart algorithms for solving the SCS problem. Moreover, there is a potential for further improvement as discussed in the conclusions.
ECP
Room: Douglas Fir
Session Chair: Jorn Mehnen, Thomas Bartz Beielstein,Thomas Baeck, Erik Goodman
10:4012: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:4011:05 Setbased MultiObjective Optimization, Indicators, and Deteriorative Cycles
Multiobjective Optimization, Performance Measures, Hypervolume Indicator, Cycles
Evolutionary multiobjective 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 ordertheoretic 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 multiobjective 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 Paretodominance relation defined on sets. Later on, we point out in which situations wellknown binary and unary indicators can help to avoid this cyclic behavior.
11:0511:30 A Spheredominance based Preference Immuneinspired Algorithm for Dynamic Multiobjective Optimization
Artificial immune system, preference, multiobjective optimization, dynamic, reference point
Realworld optimization involving multiple objectives in changing environment known as dynamic multiobjective optimization (DMO) is a challenging task, especially special regions are preferred by decision maker (DM). Based on a novel preference dominance concept called spheredominance and the theory of artificial immune system (AIS), a spheredominance preference im muneinspired 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 spheredominance 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:3011:55 Simultaneous Use of Different Scalarizing Functions in MOEA/D
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 dominancebased algorithms do not always work well on multiobjective problems with many objectives. Scalarizing functionbased fitness evaluation is a promising alternative to Pareto dominance especially for the case of many objectives. A representative scalarizing functionbased 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:5512:20 IndicatorBased Evolutionary Algorithm with Hypervolume Approximation by Achievement Scalarizing Functions
hypervolume, indicatorbased evolutionary algorithm (IBEA), many objectives, Evolutionary multiobjective optimization (EMO)
Pareto dominancebased algorithms have been the main stream in the field of evolutionary multiobjective optimization (EMO) for the last two decades. It is, however, wellknown that Paretodominancebased algorithms do not always work well on manyobjective 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 indicatorbased 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 functionbased 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: MultiTask and MultiAgent Systems
Room: Sunstone
Session Chair: Martin Butz (University of Wurzburg)
10:4011:05 MultiTask Evolutionary Shaping Without PreSpecified Representations
reinforcement learning, genetic algorithms, feature selection, shaping
Shaping functions can be used in multitask reinforcement learning (RL) to incorporate knowledge from previously experienced tasks to speed up learning on a new task. So far, researchers have prespecified a separate representation for shaping and value functions in multitask 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 multitask RL without prespecifying 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:0511:30 Adaption of XCS to MultiLearner Predator/Prey Scenarios
Agent cooperation, evolutionary learning, XCS, multiagent learning, coordination task, nonMarkovian environments
Learning classifier systems (LCSs) are rulebased 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 multilearner scennarios, since the Markov property is not fulfilled. In this paper, LCSs are investigated in an instance of the generic homogeneous and noncommunicating 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 multistep 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:3011:55 Coevolution in a Large Search Space using Resourcelimited Nash Memory
Coevolution, Nash Equilibrium, Games, Evaluation Function
Cycling has been an obstacle to coevolution of machinelearning 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 ntuple 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:5512:20 A First Assessment of the Use of Extended Relational Alphabets in Accuracy Classifier Systems
Classifier systems, relational schemata, relational alphabets, stalphabets, 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 (stalphabets) presented, and it is shown that stalphabets 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 stalphabets, 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 stalphabets in modular and hierarchical problems.
RWA: Hardware and Software
Room: Salon D
Session Chair: Giuseppe Nicosia (University of Catania)
10:4011:05 Improving Reliability of Embedded Systems through Dynamic Memory Manager Optimization using Grammatical Evolution
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 stateoftheart dynamic memory managers for several reallife 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:0511:30 MultiObjective Optimization of Doping Profile in Semiconductor Design
Multiobjective 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 tradeoff between doping profile deviation and output current should be found. The doping profile optimization in semiconductor has been tackled as a multiobjective optimization problem using the Nondominated Sorting Genetic Algorithm (NSGAII). We focus on silicon diodes and MOSFET devices; firstly, we redesign the doping profile of diodes in order to obtain a tradeoff between doping profile deviation and output current. Secondly, we find a tradeoff 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:3011:55 Multiprocessor SystemsonChip Synthesis using MultiObjective Evolutionary Computation
SystemsonChip Synthesis, Multiobjective Evolution
In this paper, we apply multiobjective evolutionary computation to the synthesis of realtime, embedded, heterogeneous, multipro cessor systems (briefly, Multiprocessor SystemsonChip or MP SoCs). Our approach simultaneously explores the architecture, the mapping and the scheduling of the system, by using multiobjective evolution. In particular, we considered three approaches: a multi objective genetic algorithm, multiobjective Simulated Annealing, and multiobjective 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 multirate realtime 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:5512:20 Malware Detection based on Dependency Graph using Hybrid Genetic Algorithm
malware detection, subgraph isomorphism, genetic algorithm, dependency graph
Computer malware is becoming a serious threat to our daily life in the informationbased 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 stateoftheart antivirus softwares.
GP: Fitness Evaluation, Feature Selection and Symbiosis
Room: Columbia
Session Chair: Wolfgang Banzhaf (Department of Computer Science, Memorial University of Newfoundland)
14:0014:25 Predicting Solution Rank to Improve Performance
Fitness Prediction, Evolutionary Algorithms, Coevolution, Symbolic Regression
Many applications of evolutionary algorithms utilize fitness approximations, for example coarsegrained 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 realvalued fitness values. We present an algorithm that coevolves a rankpredictor which optimizes to accurately rank the evolving solution population. We compare this method with a similar algorithm that uses fitnesspredictors to approximate realvalued fitnesses. We benchmark the two approaches using thousands of randomlygenerated test problems in Symbolic Regression with varying difficulties. The rank prediction method showed a 5fold reduction in computational effort for similar convergence rates. Rank prediction also produced less bloated solutions than fitness prediction.
14:2514:50 Efficiently Evolving Programs through the Search for Novelty
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:5015:15 Symbiosis, Complexification and Simplicity under GP
Symbiosis, Genetic Programming, Feature Selection, Problem Decomposition, Complexity
Models of Genetic Programming (GP) frequently reflect a neoDarwinian 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 divideandconquer 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:1515:40 Knowledge Mining with Genetic Programming Methods for Variable Selection in Flavor Design
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:0014:25 Probabilistic Performance Profiles for the Experimental Evaluation of Stochastic Algorithms
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 testproblems 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 largescale 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:2514:50 Approaches to Multidimensional Scaling for Adaptive Landscape Visualization
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 twodimensional 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:5015:15 Network Crossover Performance on NK Landscapes and Deceptive Problems
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, problemindependent 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 problemspecific 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:0014:25 Towards Improved Dispatching Rules for Complex Shop Floor Scenarios
Genetic Programming, Job Shop Scheduling, Dispatching Rules, Stochastic System Optimization
Developing dispatching rules for manufacturing systems is a tedious process, which is time and costconsuming. 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:2514:50 Discrete versus Continuous Parametrization of Bank Credit Rating Systems Optimization Using Differential Evolution
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 realworld 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:5015:15 An Ant Colony Optimization Approach to the MultipleChoice Multidimensional Knapsack Problem
Ant Colony Optimization, MultipleChoice Multidimensional Knapsack Problem, Lagrangian Relaxation
In this paper, we present an ant colony optimization (ACO) approach to solve the multiplechoice multidimensional knapsack problem (MMKP). This problem concerns many real life problems, and is hard to solve due to its strong constraints and NPhard property. The ACO approach given in this paper follows the algorithmic scheme of maxmin ant system, but has some new features with respect to the characteristics of the MMKP. First, a singlegrouporiented 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:0014:25 Using Feature Construction to Avoid Large Feature Spaces in Text Classification
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:2514:50 A Method of Association Rule Analysis for Incomplete Database Using Genetic Network Programming
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:5015:15 BiogeographyBased Optimization of NeuroFuzzy System Parameters for Diagnosis of Cardiac Disease
evolutionary algorithm, biogeographybased optimization, neurofuzzy 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 neurofuzzy network trained with a new evolutionary algorithm called biogeographybased optimization (BBO). The neurofuzzy network recognizes and classifies P wave features for the diagnosis of cardiomyopathy. In addition, we incorporate oppositionbased learning in the BBO algorithm for improved training. First we develop a neurofuzzy 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:1515:40 Constructing Numerically Stable Real Number Codes using Evolutionary Computation
genetic algorithms, evolutionary computation, errorcorrecting 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:0014:25 In Search of TargetedComplexity Problems
Data complexity, Evolutionary multiobjective optimization, Artificial data sets
Currently available realworld 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 targetedcomplexity problems, which capture the essence of realworld structures, may help to define a set of benchmarks that contributes to test the properties of learners and to improve them.
14:2514:50 Genetic Rule Extraction Optimizing Brier Score
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:0014:25 A Mono Surrogate for Multiobjective Optimization
Multiobjective Optimization, Surrogate Models, Support Vector Machine
Most surrogate approaches to multiobjective 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 Oneclass 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 stateoftheart EMOAs to prescreen 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:2514:50 An ArchivedBased Stochastic Ranking Evolutionary Algorithm (ASREA) for MultiObjective Optimization
Stochastic Ranking, Evolutionary Algorithms, Multiobjective Optimization, Performance Assessment
In this paper, we propose a new multiobjective optimization algorithm called Archivedbased Stochastic Ranking Evolutionary Algorithm (ASREA) that ranks the population by comparing individuals with members of an archive. The stochastic comparison breaks the usual O(mn^{2}) 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 wellspread nondominated solutions and developed selection strategy retain the quality of state of the art deterministic multiobjective evolutionary algorithms (MOEAs). Comparison on ZDT and 3objective DTLZ functions shows that ASREA converges on the Paretooptimal front at least as well as NSGAII and SPEA2 while reaching it much faster, and being cheaper on ranking comparisons.