Friday 9 July 10:40 - 12:20

Room: Salon A

Session Chair: Edgar Galvan-Lopez (Essex University)

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

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

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

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

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

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

Room: Salon B

Session Chair: Kalyanmoy Deb (IIT Kanpur)

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

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

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

Room: Salon C

Session Chair: Sushil Louis (UNR)

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.

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

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

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.

Room: Salon D

Session Chair:

Room: Salon G

Session Chair: Hod Lipson (Cornell University)

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

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

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

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

Room: Salon I

Session Chair: Carsten Witt (Technical University of Denmark)

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.

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

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

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

Room: Portland

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

Room: Salon A

Session Chair: Dirk Thierens (Universiteit Utrecht)

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

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

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

Room: Salon B

Session Chair:

Room: Salon C

Session Chair: Mathew Hall (University of Sheffield)

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

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

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.

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.

Room: Salon D

Session Chair: Frederick Ducatelle (IDSIA)

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

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

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.

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

Room: Salon G

Session Chair: Josh Bongard (University of Vermont)

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

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.

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.

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.

Room: Salon I

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

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.

This paper investigates theoretically the convergence properties of the stochastic algorithms of a class including both CMAESs and EDAs on constrained minimization of continuously differentiable functions. We are interested in algorithms that do not get stuck on a slope of the function, but converge only to local optimal points. Convergence to a point that is neither a stationary point of the function nor a boundary point is evidence that the convergence properties are not well behaved. We investigate what properties are necessary/sufficient for the algorithm to avoid this type of behavior, i.e., what properties are necessary for the algorithm to converge only to local optimal points of the function. We also investigate the analogous conditions on the parameters of two variants of modern EC-based stochastic algorithms, namely, a CMAES employing rank-μ update and an EDA known as 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 well-behaved optimization algorithms.

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

Room: Portland

Session Chair: Thomas BartzBeielstein, Thomas Baeck, Erik Goodman

Room: Salon A

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

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.

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

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

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.

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

Room: Salon B

Session Chair: Edgar Galvan-Lopez (Essex University)

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.

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.

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

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

Room: Salon C

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

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

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

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

Room: Salon D

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

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

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

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

Room: Salon G

Session Chair: Joshua D Knowles (University of Manchester)

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

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

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

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

Room: Salon I

Session Chair: Thomas Jansen (University College Cork)

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.

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²) time. However, we also find that quasirandom ideas, if implemented correctly, can yield an over 50\, \% speed-up.

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

Room: Portland

Session Chair: Jeff Clune (Michigan State University)

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

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

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.

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

Sunday 11 July 10:40 - 12:20

Room: Columbia

Session Chair: Riccardo Poli (University of Essex)

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

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.

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

Room: Mt Hood

Session Chair: Franz Rothlauf (University of Mainz)

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

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

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

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

Room: Meadowlark

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

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

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

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

Room: Douglas Fir

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

Room: Salmon

Session Chair: Pierre Collet (Universit* de Strasbourg)

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

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

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

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

Room: Sunstone

Session Chair: Martin Butz (University of Wurzburg)

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

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

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

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

Room: Salon D

Session Chair: Giuseppe Nicosia (University of Catania)

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

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

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

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

Room: Columbia

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

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

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.

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

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.

Room: Mt Hood

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

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

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

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

Room: Meadowlark

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

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

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

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

Room: Douglas Fir

Session Chair: Kaoru Shimada (Waseda University)

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.

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.

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

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.

Room: Sunstone

Session Chair: Jaume Bacardit (University of Nottingham)

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

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.

Room: Salmon

Session Chair: Hisao Ishibuchi (Osaka Prefecture University)

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

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