Artifical Evolution

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Alfred Kobsa University of California, Irvine, CA, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen TU Dortmund University, Germany Madhu Sudan Microsoft Research, Cambridge, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany 5975 Pierre Collet Nicolas Monmarché Pierrick Legrand Marc Schoenauer Evelyne Lutton (Eds.) Artificial Evolution 9th International Conference Evolution Artificielle, EA 2009 Strasbourg, France, October 26-28, 2009 Revised Selected Papers 13 Volume Editors Pierre Collet Université de Strasbourg, France E-mail: [email protected] Nicolas Monmarché Ecole Polytechnique de l’Université de Tours, France E-mail: [email protected] Pierrick Legrand Université de Bordeaux 2, France E-mail: [email protected] Marc Schoenauer INRIA Futurs, Université Paris-Sud, Orsay, France E-mail: [email protected] Evelyne Lutton INRIA Saclay - Ile-de-France, Orsay, France E-mail: [email protected] Library of Congress Control Number: 2010929492 CR Subject Classification (1998): I.2, F.1, J.3, H.3, I.5, F.2 LNCS Sublibrary: SL 1 – Theoretical Computer Science and General Issues ISSN ISBN-10 ISBN-13 0302-9743 3-642-14155-2 Springer Berlin Heidelberg New York 978-3-642-14155-3 Springer Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. springer.com © Springer-Verlag Berlin Heidelberg 2010 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper 06/3180 Preface This LNCS volume contains the best papers presented at the 9th Conference on Artificial Evolution, EA1 2009, held in Strasbourg (France). Previous EA events took place in Tours (2007, LNCS 4926), Lille (2005, LNCS 3871), Marseille (2003, LNCS 2936), Le Creusot (2001, LNCS 2310), Dunkerque (1999, LNCS 1829), Nimes (1997, LNCS 1363), Brest (1995, LNCS 1063) and Toulouse (1994, LNCS 1063). For this ninth edition, authors were invited to present their original work relevant to artificial evolution, including, but not limited to: evolutionary computation, evolutionary optimization, co-evolution, artificial life, population dynamics, theory, algorithmics and modeling, implementations, application of evolutionary paradigms to the real world (industry, biosciences, ...), other biologically-inspired paradigms (swarm, artificial ants, artificial immune systems, ...), memetic algorithms, multi-objective optimization, constraint handling, parallel algorithms, dynamic optimization, machine learning and hybridization with other soft computing techniques. Submitted papers were reviewed by at least four members of the International Program Committee, which selected 23 papers to be presented during the conference out of 43 submissions. However, only 17 papers were included in the present volume, resulting in a 39.5% acceptance rate. We would like to thank the members of the Program Committee for their conscientious work, the authors for their greatly appreciated contributions, but also the members of the Organizing Committee who, once more, managed to put together a really enjoyable conference in Strasbourg. Finally, financial and material support coming from ENSPS, Université de Strasbourg, CNRS, Région Alsace and the EA association contributed to the success of the conference and helped to keep registration fees very low. November 2009 1 Pierre Collet Nicolas Monmarché Pierrick Legrand Evelyne Lutton Marc Schoenauer As for previous editions of the conference, the EA acronym is based on the original French name of the conference: “Évolution Artificielle.” Organization Évolution Artificielle 2009 – EA 2009 October 26–28, 2009 Université de Strasbourg, France 9th International Conference on Artificial Evolution Steering Committee Pierre Collet Nicolas Monmarché Pierrick Legrand Evelyne Lutton Marc Schoenauer Université Louis Pasteur de Strasbourg Université François Rabelais de Tours Université Bordeaux 2 INRIA Saclay Ile de France INRIA Saclay Ile de France Organizing Committee General Chair Treasurer Publicity Chair Publication Chair Fund Raising Submissions Webmaster Local Organization Pierre Collet, University of Strasbourg Sébastien Vérel, University of Nice Sophia-Antipolis Laetitia Jourdan, INRIA Futurs Lille Pierrick Legrand, University of Bordeaux Cedric Wemmert, University of Strasbourg Alexandre Blansché, University of Strasbourg Aline Deruyver, University of Strasbourg Germain Forestier, University of Strasbourg Jonathan Weber, University of Strasbourg Aurélie Bertaux, University of Strasbourg International Program Committee Enrique Alba Anne Auger Sébastien Aupetit Mehmet Aydin Wolfgang Banzhaf Hans-Georg Beyer Peter Bentley Alexandre Blansché Amine Boumaza Universidad de Málaga, Spain INRIA Saclay, France Université de Tours, France University of Bedfordshire, UK University of Newfoundland, Canada Vorarlberg University of Applied Sciences, Austria University College London, UK Université de Strasbourg, France Université du Littoral, France VIII Organization Nicolas Bredeche Larry Bull Edmund Burke Stefano Cagnoni Alexandre Caminada Nirupam Chakraborti Uday Chakraborty Maurice Clerc Carlos Coello Philippe Collard Pierre Collet David Corne Ernesto Costa Luis Da Costa Daniel Delahaye Alexandre Devert Nicolas Durand Marc Ebner Aniko Ekart Christian Gagné Mario Giacobini Jens Gottlieb Frédéric Guinand Steven Gustafson Jin-Kao Hao Jano van Hemert Daniel Howard Colin Johnson Laetitia Jourdan Natalio Krasnogor Nicolas Labroche Nicolas Lachiche Pier Luca Lanzi Claude Lattaud Pierrick Legrand Jean Louchet Simon Lucas Evelyne Lutton Bob McKay Julian Miller Université Paris-Sud XI, France UWE Bristol, UK University of Nottingham, UK Università di Parma, Italy Université de Technologie de Belfort-Montbéliard, France Indian Institute of Technology Kharagpur, India University of Missouri, USA Independant Consultant, France Instituto Politécnico Nacional, Mexico Université de Nice - Sophia Antipolis, France Université de Strasbourg, France Heriot Watt University, UK University of Coimbra, Portugal Paris XI University, France Ecole Nationale Aviation Civile, France Polytechnic Institute of Ha Noi, Vietnam Institut de Recherche en Informatique de Toulouse, France Eberhard Karls Universität Tübingen, Germany Aston University, UK Université Laval, Canada University of Turin, Italy SAP AG, Germany Le Havre University, France GE Global Research, USA Université d’Angers, France University of Edinburgh, UK Qinetiq, UK University of Kent, UK INRIA Lille, France University of Nottingham, UK LIP6 Paris, France Université de Strasbourg, France Politecnico di Milano, Italy Université René Descartes, France Université de Bordeaux, France Inria Saclay, France University of Essex, UK Inria Saclay, France Seoul National University, South Korea University of York, UK Organization Nicolas Monmarché Jean-Baptiste Mouret Yuichi Nagata Miguel Nicolau Gabriela Ochoa Michael O’Neill Martin Pelikan Jean-Philippe Rennard Denis Robilliard El-Ghazali Talbi Emmanuel Sapin Marc Schoenauer Deepak Sharma Patrick Siarry Moshe Sipper Stephen Smith Christine Solnon Terence Soule Thomas Stuetzle Hideyuki Takagi Olivier Teytaud Marco Tomassini Shigeyoshi Tsutsui Paulo Urbano Gilles Venturini Sebastien Verel Darrell Whitley Xin-She Yang Tina Yu Mengjie Zhang Université de Tours, France Université Paris VI, France Japan Advanced Institute of Science and Technology, Japan INRIA Saclay - ı̂le-de-France, France University of Nottingham, UK University College Dublin, Ireland University of Missouri, USA École de Management de Grenoble, France Université du Littoral, France INRIA Lille, France INRIA Saclay - ı̂le-de-France, France INRIA Saclay - ı̂le-de-France, France Université de Strasbourg, France Université Paris Val de Marne, France Ben-Gurion University of the Negev, Israel University of York, UK Université Lyon 1, France University of Idaho, USA Université Libre de Bruxelles, Belgique Kyushu University, Japan INRIA Saclay, France Université de Lausanne, Switzerland Hannan University, Japan University of Lisbon, Portugal Université de Tours, France Université de Nice-Sophia Antipolis, France Colorado State University, USA University of Cambridge, UK Memorial University of Newfoundland, Canada Victoria University of Wellington, New Zealand Invited Talk Elementary Landscapes and Why they Matter, Darrell Whitley. Sponsoring Institutions EA association ENSPS CNRS Région Alsace Université de Strasbourg IX Table of Contents Theory Extremal Optimization Dynamics in Neutral Landscapes: The Royal Road Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I. De Falco, A. Della Cioppa, D. Maisto, U. Scafuri, and E. Tarantino Improving the Scalability of EA Techniques: A Case Study in Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stefan R. Bach, A. Şima Uyar, and Jürgen Branke 1 13 Ant Colony Optimization MC-ANT: A Multi-Colony Ant Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . Leonor Melo, Francisco Pereira, and Ernesto Costa 25 Applications Artificial Evolution for 3D PET Reconstruction . . . . . . . . . . . . . . . . . . . . . . Franck P. Vidal, Delphine Lazaro-Ponthus, Samuel Legoupil, Jean Louchet, Évelyne Lutton, and Jean-Marie Rocchisani A Hybrid Genetic Algorithm/Variable Neighborhood Search Approach to Maximizing Residual Bandwidth of Links for Route Planning . . . . . . . Gajaruban Kandavanam, Dmitri Botvich, Sasitharan Balasubramaniam, and Brendan Jennings Parallelization of an Evolutionary Algorithm on a Platform with Multi-core Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Shigeyoshi Tsutsui On the Difficulty of Inferring Gene Regulatory Networks: A Study of the Fitness Landscape Generated by Relative Squared Error . . . . . . . . . . . Francesco Sambo, Marco A. Montes de Oca, Barbara Di Camillo, and Thomas Stützle 37 49 61 74 Combinatorial Optimization Memetic Algorithms for Constructing Binary Covering Arrays of Strength Three . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Eduardo Rodriguez-Tello and Jose Torres-Jimenez 86 XII Table of Contents A Priori Knowledge Integration in Evolutionary Optimization . . . . . . . . . Paul Pitiot, Thierry Coudert, Laurent Geneste, and Claude Baron 98 Robotics On-Line, On-Board Evolution of Robot Controllers . . . . . . . . . . . . . . . . . . . N. Bredeche, E. Haasdijk, and A.E. Eiben The Transfer of Evolved Artificial Immune System Behaviours between Small and Large Scale Robotic Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . Amanda M. Whitbrook, Uwe Aickelin, and Jonathan M. Garibaldi 110 122 Multi-objective Optimization An Analysis of Algorithmic Components for Multiobjective Ant Colony Optimization: A Case Study on the Biobjective TSP . . . . . . . . . . . . . . . . . Manuel López-Ibáñez and Thomas Stützle Alternative Fitness Assignment Methods for Many-Objective Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mario Garza Fabre, Gregorio Toscano Pulido, and Carlos A. Coello Coello 134 146 Genetic Programming Evolving Efficient List Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . Kfir Wolfson and Moshe Sipper Semantic Similarity Based Crossover in GP: The Case for Real-Valued Function Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nguyen Quang Uy, Michael O’Neill, Nguyen Xuan Hoai, Bob Mckay, and Edgar Galván-López Genetic-Programming Based Prediction of Data Compression Saving . . . Ahmed Kattan and Riccardo Poli 158 170 182 Machine Learning On the Characteristics of Sequential Decision Problems and Their Impact on Evolutionary Computation and Reinforcement Learning . . . . . André M.S. Barreto, Douglas A. Augusto, and Helio J.C. Barbosa 194 Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207