Abstracts
From Ea09
[edit]
Elementary Landscapes and why they matter
The Traveling Salesman Problem, Graph Coloring and Max-Cut Graph Partitioning all display elementary landscapes under common "natural" local search operators.
Let x be a point in the search space, let N(x) enumerate the neighbors of x, and let AVG(N(x)) compute the average of the evaluation of the neighbors of x. AVG(N(x)) is computable for an elementary landscape without actually evaluating the neighbors N(x).
A new "component" model of elementary landscapes makes it possible to compute AVG(N(x)) over partial neighborhoods. Also, we show that MAX-3SAT is a superposition of 3 elementary landscapes.
Thus AVG(N(x)) is also computable for MAX-3SAT for any point x. In regular elementary landscapes, given two points x and y then f(x)=f(y) implies AVG(N(x))=AVG(N(y)). But in partial and superposition elementary landscapes this is not true.
Thus, for MAX-3SAT, two points that have the same evaluation do not typically have neighbors with the same evaluation, and this information can be used to guide local search that would otherwise be stuck on a plateau.
[edit]
Short Bio:
Prof Darrell Whitley is Chair of the Department of Computer Science at Colorado State University. From 1993 to 1997 Prof. Whitley served as Chair of the Governing Board of the International Society for Genetic Algorithms. From 1997 to 2002 Prof. Whitley served as Editor-in-Chief for the journal Evolutionary Computation published by MIT Press. In 2007 Prof. Whitley was elected Chair of the ACM Sigevo Executive Committee.
[edit]
Abstracts
| Title: | Improving the Scalability of EA Techniques: A Case Study in Clustering |
| Authors: | Stefan R. Bach, A. Sima Uyar, Jürgen Branke |
| Abstract: | This paper studies the scalability of evolutionary algorithms (EA) for clustering similarity data with a fixed number of clusters. A simple EA and improved versions using problem-dependent knowledge are experimentally evaluated for clustering up to 100,000 objects. We find that a problem-dependent crossover operator or the use of hybridization can achieve near-linear scalability, while the simple EA, even with problem-dependent initialization, fails at moderately large problems. |
| Title: | An Analysis of Algorithmic Components for Multiobjective Ant Colony Optimization: A Case Study on the Biobjective TSP |
| Authors: | Manuel López-Ibáñez, Thomas Stuetzle |
| Abstract: | In many practical problems, several conflicting criteria exist for evaluating solutions. In recent years, a notable research effort has been made to develop efficient algorithmic techniques for tackling such multi-objective optimization problems. Many of these algorithms are extensions of well-known metaheuristics. In particular, over the last few years, several extensions of ant colony optimization algorithms have been proposed for solving multi-objective problems. These extensions often propose multiple answers to algorithmic design questions introduced by the multi-objective approach. However, the benefits of each one of these answers are rarely examined against the alternative approaches. This article reports initial results of an empirical research effort aimed at analysing the components of ACO algorithms for tackling multi-objective combinatorial problems. These initial results focus on the bi-objective travelling salesman problem. The goals are (i) to identify the algorithmic components (or design choices) available for extending state-of-the-art ACO algorithms to multi-objective problems, and (ii) to study the possible interactions of these components and their effect on the outcome of a multi-objective ACO algorithm. Examples of design choices are the use of local search, one versus several pheromone matrices, and one or several colonies. The analysis of the results is carried out by means of exploratory graphical tools based on the attainment function methodology. These tools allow to identify regions of the objective space where there is a strong difference between two alternative strategies. |
| Title: | Gap Search in Particle Swarm Optimization |
| Authors: | Markus Kress, Sanaz Mostaghim, Hartmut Schmeck, Detlef Seese |
| Abstract: | In this paper, we study the influence of Gap Search (GS) on Particle Swarm Optimization (PSO) and Multi-Objective PSO (MOPSO). Inspired from Binary Search, which is known to be an effective search mechanism with a balanced Exploration-Exploitation mechanism, we propose to employ GS in the initialization, diversity, and feasibility preservation mechanisms in PSO and MOPSO. The behavior of PSO (MOPSO) variants is examined on a large variety of single-, multi-, and many-objective problems. The experiments indicate that applying GS to PSO improves the results, in particular, when employing it for the diversity preservation and the initialization of particles. For the MOPSO variants, the feasibility preserving methods including the GS variant show a higher impact on the quality of the solutions. |
| Title: | Alternative Fitness Assignment Methods for Many-Objective Optimization Problems |
| Authors: | Mario Garza-Fabre, Gregorio Toscano-Pulido, Carlos Coello-Coello |
| Abstract: | Fitness comparison among solutions in single-objective optimization is straightforward,fbut when dealing with multiple objectives, it becomes a non-trivial task. Pareto dominance has been the most commonly adopted relation to compare solutions in the multiobjective optimization context. However, it has been shown that when the number of objectives increases, its convergence behavior decreases. In this paper, we perform a comparative study of some of the state-of-the-art fitness assignment methods available for many-objective optimization (i.e., multiobjective optimization problems having 4 or more objectives) in order to compare their convergence ability as the number of objectives increases. Also, based on some observed drawbacks of one of the methods analyzed, we propose a novel approach. Experimental results indicate that the proposed method is able to properly guide the search process in high-dimensional objective spaces for two well-known test problems. |
| Title: | Semantic Similarity based Crossover in GP: The case for Real-valued Function Regression |
| Authors: | Quang Uy Nguyen, Michael O'Neill, Xuan Hoai Nguyen, Bob McKay, Edgar Galvan Lopez |
| Abstract: | In this paper we propose a new method for implementing the crossover operator in Genetic Programming (GP) called Semantic Similarity based Crossover (SSC). This new operator is inspired by Semantic Aware Crossover (SAC) [20]. SSC extends SAC by adding semantics to control the change of the semantics of the individuals during the evolutionary process. The new crossover operator is then tested on a family of symbolic regression problems and compared with SAC as well as Standard Crossover (SC). The results from the experiments show that the change of the semantics (fitness) in the new SSC is smoother compared to SAC and SC. This leads to performance improvement in terms of percentage of succesful runs and mean best fitness. |
| Title: | An interactive ant algorithm for real-time music accompaniment |
| Authors: | Romain Clair, Mohamed Slimane, Nicolas Monmarché |
| Abstract: | This paper describes a work on interactive bio-inspired method. Conceiving an accessible tool to make music, we used an artificial ant colony algorithm as an automatic accompaniment provider. This algorithm has been adapted to generate music in interaction with a human user. |
| Title: | A Hybrid Genetic Algorithm / Variable Neighborhood Search Approach to Maximizing Residual Bandwidth of Links for Route Planning |
| Authors: | Gajaruban Kandavanam, Dmitri Botvich, Sasitharan Balasubramaniam, Brendan Jennings |
| Abstract: | This paper proposes a novel approach to performing residual bandwidth optimization with QoS guarantees in multi-class networks. The approach combines the use of a new highly scalable hybrid GA-VNS algorithm (Genetic Algorithm with Variable Neighborhood Search) with the efficient and accurate estimation of QoS requirements using empirical effective bandwidth estimations. Given a QoS-aware demand matrix, experimental results indicate that the GA-VNS algorithm shows much higher success rate in terms of converging to optimum/near optimum solution in comparison to pure GA and another combination of GA and local search heuristic, and also exhibits better scalability and performance. Additional results also show that the proposed solution performs significantly better than OSPF in optimizing residual bandwidth in a medium to large sized network. |
| Title: | MC-ANT: a Multi-colony Ant Algorithm |
| Authors: | Leonor Melo, Francisco Pereira, Ernesto Costa |
| Abstract: | In this paper we propose an ant colony optimization variant where several independent colonies try to simultaneously solve the same problem. The approach includes a migration mechanism that ensures the exchange of information between colonies and a mutation operator that aims to adjust the parameter settings during the optimization. The proposed method was applied to several benchmark instances of the node placement problem. The results obtained shown that the multi-colony approach is more effective than the single-colony. A detailed analysis of the algorithm behavior also reveals that it is able to delay the premature convergence. |
| Title: | A priori knowledge integration in intelligent optimization |
| Authors: | Paul Pitiot, Thierry Coudert, Laurent Geneste, Claude Baron |
| Abstract: | Several recent works have examined the effectiveness of using knowledge models to guide search algorithms in high dimensional spaces. The aim of such methods, often called "Intelligent optimization methods", is to reach good solutions using simultaneously evolutionary search and knowledge guidance. The idea proposed in this paper is use a bayesian network in order to store and apply the knowledge model and, as a consequence, to accelerate the search process. A traditional evolutionary algorithm is modified in order to allow the reuse of the capitalized knowledge. The approach has been applied to a problem of selection of project scenarios in a multi-objective context. A preliminary version of this method was presented at EA' 07 conference [1]. An experimentation platform has been developed to validate the approach and to study different modes of knowledge injection. The obtained experimental results are presented. |
| Title: | Genetic Programming as a Predictor of Data Compression Saving |
| Authors: | Ahmed Kattan, Riccardo Poli |
| Abstract: | We use Genetic Programming (GP) to generate programs that predict data compression ratio for compression algorithms. GP evolves programs with multiple components. One component analyses statistical features extracted from the files’ byte frequency distribution to come up with a compression ratio prediction. Another component does the same but by analysing statistical features extracted from the files’ raw ASCII representation. A further (evolved) component acts as a decision tree to determine the overall output (compression ratio estimation) returned by an individual. The decision tree produces its result based on a series of comparisons among statistical features extracted from the files and the outputs of the two prediction components. The evolved decision tree has the choice to select either the outputs of the other components or alternatively, to integrate them into an evolved mathematical formula. Experiments with the proposed approach show that GP is able to accurately estimate the compression ratio of unseen files without the need to run every compression algorithm in question. |
| Title: | Bias and variance in continuous EDA |
| Authors: | Olivier Teytaud, Fabien Teytaud |
| Abstract: | Estimation of Distribution Algorithms are based on statistical estimates. We show that when combining classical tools from statistics, namely bias/variance decomposition, reweighting and quasi-randomization, we can strongly improve the convergence rate. All modifications are easy, compliant with most algorithms, and experimentally very efficient in particular in the parallel case (large offsprings). |
| Title: | Artificial Evolution for 3D PET Reconstruction |
| Authors: | Franck Vidal, Delphine Lazaro-Ponthus, Samuel Legoupil, Jean Louchet, Evelyne Lutton, Jean-Marie Rocchisani |
| Abstract: | This paper presents a method to take advantage of artificial evolution in positron emission tomography reconstruction. This imaging technique produces datasets that correspond to the concentration of positron emitters through the patient. Fully 3D tomographic reconstruction requires high computing power and leads to many challenges. Our aim is to reduce the computing cost and produce datasets while retaining the required quality. Our method is based on a coevolution strategy (also called Parisian evolution) named ``fly algorithm. Each fly represents a point of the space and acts as a positron emitter. The final population of flies corresponds to the reconstructed data. Using ``marginal evaluation, the fly's fitness is the positive or negative contribution of this fly to the performance of the population. This is also used to skip the relatively costly step of selection and simplify the evolutionary algorithm. |
| Title: | The Transfer of Evolved Artificial Immune System Behaviours between Small and Large Scale Robotic Platforms |
| Authors: | Amanda Whitbrook, Uwe Aickelin, Jonathan Garibaldi |
| Abstract: | This paper demonstrates that a set of behaviours evolved in simulation on a miniature robot (epuck) can be transferred to a much larger scale platform (a virtual Pioneer P3-DX) that also differs in shape, sensor type, sensor configuration and programming interface. The chosen architecture uses a reinforcement learning-assisted genetic algorithm to evolve the epuck behaviours, which are encoded as a genetic sequence. This sequence is then used by the Pioneers as part of an adaptive, idiotypic artificial immune system (AIS) control architecture. Testing in three different simulated worlds shows that the Pioneer can use these behaviours to navigate and solve object-tracking tasks successfully, as long as its adaptive AIS mechanism is in place. |
| Title: | On-line, On-board Evolution of Robot Controllers |
| Authors: | Nicolas Bredeche, Evert Haasdijk, A.E. Eiben |
| Abstract: | This paper reports on a feasibility study into the evolution of robot controllers during the actual operation of robots (on-line), using only the computational resources within the robots themselves (on-board). We identify the main challenges that these restrictions imply and propose mechanisms to handle them. The resulting algorithm is evaluated in a hybrid system, using the actual robots’ processors interfaced with a simulator that represents the environment. The results show that the proposed algorithm is indeed feasible and the particular problems we encountered during this study give hints for further research. |
| Title: | Binary versus Real-valued Reward Functions under Coevolutionary Reinforcement Learning |
| Authors: | Peter Lichodzijewski, Malcolm Heywood |
| Abstract: | Models of coevolution supporting competitive and cooperative behaviours can be used to decompose the problem while scaling to large environmental state spaces. This work examines the significance of various design decisions that impact the deployment of a distinction-based formulation of competitive coevolution. Specifically, competitive coevolutionary formulations with and without point population speciation are compared to stochastic sampling of the environment under both binary and real-valued rewards. The additional structure implicit in the competitive coevolutionary models is shown to be of significant benefit under binary rewards, however, stochastic sampling results in more dependable performance under real-valued feedback. It is also observed that cooperation between multiple solutions results in a two-to three-fold improvement in performance over that of a single solution. |
| Title: | Parallelization of an Evolutionary Algorithm on a Computing Platform with Multi-core Processors |
| Authors: | Shigeyoshi Tsutsui |
| Abstract: | This paper proposes methods of parallelization of an evolutionary algorithm using multi-thread programming on a computing platform with multi-core processors. For this study, we revise the previously proposed edge histogram sampling algorithm (EHBSA) which we call the enhanced EHBSA ($e$EHBSA). The parallelization models are designed using $e$EHBSA to increase the execution speed of the algorithm. We propose two types of parallel models; one is a synchronous multi-thread model (SMTM), and the other is an asynchronous multi-thread model (AMTM). Experiments are performed using several sizes of TSP. The results showed that both parallel methods increased the speed of the computation times nearly proportional to the number of cores for all test problems. The AMTM produced especially good run time results for small TSP instances without local search. |
| Title: | Evolving Efficient List Search Algorithms |
| Authors: | Kfir Wolfson, Moshe Sipper |
| Abstract: | We peruse the idea of algorithmic design through Darwinian evolution, focusing on the problem of evolving list search algorithms. Specifically, we employ genetic programming (GP) to evolve iterative algorithms for searching for a given key in an array of integers. Our judicious design of an evolutionary language renders the evolution of linear-time search algorithms easy. We then turn to the far more difficult problem of logarithmic-time search, and show that our evolutionary system successfully handles this case. Subsequently, because our setup might be perceived as being geared towards the emergence of binary search, we generalize our genomic representation, allowing evolution to assemble its own useful functions via the mechanism of automatically defined functions (ADFs). We show that our approach routinely and repeatedly evolves general and correct efficient algorithms. |
| Title: | A New ACO Approach for Solving Dynamic Problems |
| Authors: | Olfa Aouf SAMMOUD, Christine SOLNON, Khaled GHEDIRA |
| Abstract: | Many real-world optimization problems evolve in a dynamically changing environment: the problem to solve changes through time, and no information about changes and problem evolution is available ahead of time. When solving such problems, we need an optimization technique which is able not only to converge around optimal solutions but also to follow their shifting through time as closely as possible. In this paper, we propose a new ACO (Ant Colony Optimization) approach for solving dynamic problems. Like in {tt PACO, instead of restarting from scratch every time the problem changes, pheromone trails are re-computed at each time w.r.t a set of already found solutions. However, in order to avoid the algorithm to be misguided, the new pheromone trails are first tested. The goal is to study the relevancy of the re-computed pheromone trails w.r.t the changes and consequently to adjust/correct their values. The proposed algorithm is tested on Dynamic TSP (Traveling Salesman Problem) instances. |
| Title: | Memetic Algorithms for Constructing Binary Covering Arrays of Strength Three |
| Authors: | Eduardo Rodriguez-Tello, Jose Torres-Jimenez |
| Abstract: | This paper presents a new Memetic Algorithm (MA) designed to compute near optimal solutions for the covering array construction problem. It incorporates several distinguished features including an efficient heuristic to generate a good quality initial population, and a local search operator based on a fine tuned Simulated Annealing (SA) algorithm employing a carefully designed compound neighborhood. Its performance is investigated through extensive experimentation over well known benchmarks and compared with other state-of-the-art algorithms, showing improvements on some previous best-known results. |
| Title: | Extremal Optimization Dynamics in Neutral Landscapes |
| Authors: | Ivanoe De Falco, Antonio Della Cioppa, Domenico Maisto, Umberto Scafuti, Ernesto Tarantino |
| Abstract: | In recent years a new view of evolutionary dynamics has emerged based on both neutrality and balance between adaptation and exaptation. Differently from the canonical adaptive paradigm where the genotypic variability is strictly related to the change at fitness level, such a paradigm has raised awareness of the importance of both selective neutrality and co-option by exaptation. This paper investigates an innovative method based on Extremal Optimization, a coevolutionary algorithm successfully applied to NP--hard combinatorial problems, with the aim of exploring the ability of its extremal dynamics to face neutral fitness landscapes by exploiting co-option by exaptation. A well--known neutral fitness landscape, i.e., the Royal Road, has been chosen, and a comparison has been effected between Extremal Optimization and a Random Mutation Hill Climber on several problem instances. |
| Title: | On the Characteristics of Sequential Decision Problems and Their Impact on Evolutionary Computation and Reinforcement Learning |
| Authors: | Andre' Barreto, Douglas Augusto, Helio Barbosa |
| Abstract: | Evolutionary computation and reinforcement learning address the sequential decision-making problem in completely different ways, and their strengths and weaknesses may be emphasized or disguised by the features of a specific task. Therefore, an important goal is to discover characteristics of a decision problem that can be easily identified and at the same time provide some hint as to which of the two approaches should be adopted to solve the problem. This work provides a systematic review of the criteria most commonly used to classify decision problems and discusses their impact on the performance of reinforcement learning and evolutionary computation. The paper also proposes a further division of one class of decision problems in two subcategories, which delimits a set of decision problems particularly difficult for optimization techniques in general and evolutionary methods in particular. A simple computational experiment is presented to illustrate the subject. |
| Title: | Controlling behavioral and structural parameters in Evolutionary Algorithms |
| Authors: | Jorge Maturana, Frédéric Lardeux, Frédéric Saubion |
| Abstract: | Evolutionary algorithms have been efficiently used for solving combinatorial problems. However, their practical use induces to define carefully the suitable operators for the resolution and also to fix a set of functional parameters. Similarly to majority of metaheuristics methods, the performance of an evolutionary algorithm is intrinsically linked to its ability to properly manage the balance between exploitation and exploration of the search space. Recently, new approaches have emerged to make these algorithms more independent, especially by automating the tuning and/or control of parameters. We propose a new approach whose objective is twofold: (1) to manage an important set of potential operators, whose performances are a priori unknown, and (2) to dynamically control the behavior of operators in a evolutionary algorithm, thanks to their probabilities of application. |
| Title: | On the difficulty of inferring gene regulatory networks: A study of the fitness landscape generated by relative squared error |
| Authors: | Francesco Sambo, Marco A. Montes de Oca, Barbara Di Camillo, Thomas Stuetzle |
| Abstract: | Inferring gene regulatory networks from expression profiles is a challenging problem that has been tackled using many different approaches. When posed as an optimization problem, the typical goal is to minimize the value of an error measure, such as the relative squared error, between the real profiles and those generated with a model whose parameters are to be optimized. In this paper, we use recurrent neural networks to model regulatory interactions and study systematically the ``fitness landscape that results from measuring the relative squared error. Although the results of the study indicate that the generated landscapes have a positive fitness-distance correlation, the error values span several orders of magnitude over very short distance variations. This suggests that the fitness landscape has extremely deep valleys, which can make general-purpose state-of-the-art continuous optimization algorithms exhibit a very poor performance. Further results obtained from an analysis based on perturbations of the optimal network topology support approaches in which the spaces of network topologies and of network parameters are decoupled. |
