Parallel Problem Solving from Nature - PPSN Vol. VIII : 8th International Conference, Birmingham, UK, September 18-22, 2004, Proceedings

by Yao, Xin; Burke, Edmund; Lozano, Jose A.; Smith, Jim; Merelo-Guervos, Juan J.

• ISBN13: 9783540230922
• ISBN10: 3540230920
• Format: Paperback
• Copyright: 2004-11-15
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the refereed proceedings of the 8th International Conference on Parallel Problem Solving from Nature, PPSN 2004, held in Birmingham, UK, in September 2004.The 119 revised full papers presented were carefully reviewed and selected from 358 submissions. The papers address all current issues in biologically inspired computing; they are organized in topical sections on theoretical and foundational issues, new algorithms, applications, multi-objective optimization, co-evolution, robotics and multi-agent systems, and learning classifier systems and data mining.

Table of Contents

Theory
On the Quality Gain of (1,λ)-ES Under Fitness Noise	1	(10)
Hans-Georg Beyer and Silja Meyer-Nieberg
Fitness Distributions and GA Hardness	11	(10)
Yossi Borenstein and Riccardo Poli
Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatorial Optimization	21	(10)
Patrick Briest, Dimo Brockhoff, Bastian Degener, Matthias Englert, Christian Gunia, Oliver Heering, Thomas Jansen, Michael Leifhelm, Kai Plociennik, Heiko Röglin, Andrea Schweer, Dirk Sudholt, Stefan Tannenbaum, and Ingo Wegener
The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes	31	(10)
Patrick Briest, Dimo Brockhoff, Bastian Degener, Matthias Englert, Christian Gunia, Oliver Heering, Thomas Jansen, Michael Leifhelm, Kai Plociennik, Heiko Röglin, Andrea Schweer, Dirk Sudholt, Stefan Tannenbaum, and Ingo Wegener
Evolutionary Algorithms with On-the-Fly Population Size Adjustment	41	(10)
A.E. Eiben, Elena Marchiori, and V.A. Valkó
Search Space Features Underlying the Performance of Stochastic Local Search Algorithms for MAX-SAT	51	(10)
Holger H. Hoos, Kevin Smyth, and Thomas Stützle
Bridging the Gap Between Theory and Practice	61	(11)
Thomas Jansen and R. Paul Wiegand
A Reduced Markov Model of GAs Without the Exact Transition Matrix	72	(9)
Cheah C.J. Moey and Jonathan E. Rowe
Expected Runtimes of a Simple Evolutionary Algorithm for the Multi-objective Minimum Spanning Tree Problem	81	(10)
Frank Neumann
On the Importance of Information Speed in Structured Populations	91	(10)
Mike Preuss and Christian Lasarczyk
Estimating the Number of Solutions for SAT Problems	101	(10)
Colin R. Reeves and Mériéma Aupetit-Bélaidouni
Behavior of Evolutionary Algorithms in Chaotically Changing Fitness Landscapes	111	(10)
Hendrik Richter
Expected Rates of Building Block Discovery, Retention and Combination Under 1-Point and Uniform Crossover	121	(10)
Cameron Skinner and Patricia Riddle
An Analysis of the Effectiveness of Multi-parent Crossover	131	(10)
Chuan-Kang Ting
On the Use of a Non-redundant Encoding for Learning Bayesian Networks from Data with a GA	141	(10)
Steven van Dijk and Dirk Thierens
Phase Transition Properties of Clustered Travelling Salesman Problem Instances Generated with Evolutionary Computation	151	(10)
Jano I. van Hemert and Neil B. Urquhart
A Simple Two-Module Problem to Exemplify Building-Block Assembly Under Crossover	161	(11)
Richard A. Watson
Statistical Racing Techniques for Improved Empirical Evaluation of Evolutionary Algorithms	172	(10)
Bo Yuan and Marcus Gallagher
New Algorithms
LS-CMA-ES: A Second-Order Algorithm for Covariance Matrix Adaptation	182	(10)
Anne Auger, Marc Schoenauer, and Nicolas Vanhaecke
Learning Probabilistic Tree Grammars for Genetic Programming	192	(10)
Peter A.N. Bosman and Edwin D. de Jong
Sequential Sampling in Noisy Environments	202	(10)
Jürgen Branke and Christian Schmidt
Evolutionary Continuous Optimization by Distribution Estimation with Variational Bayesian Independent Component Analyzers Mixture Model	212	(10)
Dong-Yeon Cho and Byoung-Tak Zhang
Spread of Vector Borne Diseases in a Population with Spatial Structure	222	(10)
Dominique Chu and Jonathan Rowe
Hierarchical Genetic Algorithms	232	(10)
Edwin D. de Jong, Dirk Thierens, and Richard A. Watson
Migration of Probability Models Instead of Individuals: An Alternative When Applying the Island Model to EDAs	242	(11)
Luis delaOssa, José A. Gámez, and José M. Puerta
Comparison of Steady-State and Generational Evolution Strategies for Parallel Architectures	253	(10)
Razvan Enache, Bernhard Sendhoff, Markus Olhofer, and Martina Hasenjäger
Control of Bloat in Genetic Programming by Means of the Island Model	263	(9)
Francisco Fernández de Vega, German Galeano Gil, Juan Antonio Gómez Pulido, and Jose Luis Guisado
Saving Resources with Plagues in Genetic Algorithms	272	(10)
Francisco Fernández de Vega, Erik Cantú-Paz, J.I. López, and T. Manzano
Evaluating the CMA Evolution Strategy on Multimodal Test Functions	282	(10)
Nikolaus Hansen and Stefan Kern
Exploring the Evolutionary Details of a Feasible-Infeasible Two-Population GA	292	(10)
Steven Orla Kimbrough, Ming Lu, and David Harlan Wood
An Evolutionary Algorithm for the Maximum Weight Trace Formulation of the Multiple Sequence Alignment Problem	302	(10)
Gabriele Koller and Günther R. Raidl
A Novel Programmable Molecular Computing Method Based on Signaling Pathways Regulated by Rho-GTPases in Living MDCK Epithelial Mammalian Cells	312	(10)
Jian-Qin Liu and Katsunori Shimohara
Empirical Investigations on Parallelized Linkage Identification	322	(10)
Masaharu Munetomo, Naoya Murao, and Kiyoshi Akama
The EAX Algorithm Considering Diversity Loss	332	(10)
Yuichi Nagata
Topology-Oriented Design of Analog Circuits Based on Evolutionary Graph Generation	342	(10)
Masanori Natsui, Naofumi Homma, Takafumi Aoki, and Tatsuo Higuchi
A Mixed Bayesian Optimization Algorithm with Variance Adaptation	352	(10)
Jiri Ocenasek, Stefan Kern, Nikolaus Hansen, and Petros Koumoutsakos
A Swarm Intelligence Based VLSI Multiplication-and-Add Scheme	362	(10)
Danilo Pani and Luigi Raffo
Distribution Tree-Building Real-Valued Evolutionary Algorithm	372	(10)
Petr Pošik
Optimization via Parameter Mapping with Genetic Programming	382	(9)
Joao C.F. Pujol and Riccardo Poli
Multi-cellular Development: Is There Scalability and Robustness to Gain?	391	(10)
Daniel Roggen and Diego Federici
Constrained Evolutionary Optimization by Approximate Ranking and Surrogate Models	401	(10)
Thomas Philip Runarsson
Robust Parallel Genetic Algorithms with Re-initialisation	411	(9)
Ivan Sekaj
Improving Evolutionary Algorithms with Multi-representation Island Models	420	(10)
Zbigniew Skolicki and Kenneth De Jong
A Powerful New Encoding for Tree-Based Combinatorial Optimisation Problems	430	(10)
Sang-Moon Soak, David Corne, and Byung-Ha Ahn
Partially Evaluated Genetic Algorithm Based on Fuzzy c-Means Algorithm	440	(10)
Si-Ho Yoo and Sung-Bae Cho
Applications
Metaheuristics for the Vehicle Routing Problem with Stochastic Demands	450	(11)
Leonora Bianchi, Mauro Birattari, Marco Chiarandini, Max Manfrin, Monaldo Mastrolilli, Luis Paquete, Olivia Rossi-Doria, and Tommaso Schiavinotto
AntHocNet: An Ant-Based Hybrid Routing Algorithm for Mobile Ad Hoc Networks	461	(10)
Gianni Di Caro, Frederick Ducatelle, and Luca Maria Gambardella
A Scatter Search Algorithm for the 3D Image Registration Problem	471	(10)
Oscar Cordón, Sergio Damas, and José Santamaria
A Hybrid GRASP-Evolutionary Algorithm Approach to Golomb Ruler Search	481	(10)
Carlos Cotta and Antonio J. Fernández
Design of an Efficient Search Algorithm for P2P Networks Using Concepts from Natural Immune Systems	491	(10)
Niloy Ganguly, Geoff Canright, and Andreas Deutsch
A Novel Ant Algorithm for Solving the Minimum Broadcast Time Problem	501	(10)
Yehudit Hasson and Moshe Sipper
Designing Multiple-Use Primer Set for Multiplex PCR by Using Compact GAs	511	(11)
Yu-Cheng Huang, Han-Yu Chuang, Huai-Kuang Tsai, Chun-Fan Chang, and Cheng- Yan Kao
Robust Inferential Sensors Based on Ensemble of Predictors Generated by Genetic Programming	522	(10)
Elsa Jordaan, Arthur Kordon, Leo Chiang, and Guido Smits
Searching Transcriptional Modules Using Evolutionary Algorithms	532	(9)
Je-Gun Joung, Sok June Oh, and Byoung-Tak Zhang
Evolution of Voronoi-Based Fuzzy Controllers	541	(10)
Carlos Kavka and Marc Schoenauer
Analyzing Sensor States and Internal States in the Tartarus Problem with Tree State Machines	551	(10)
DaeEun Kim
Evolving Genetic Regulatory Networks for Hardware Fault Tolerance	561	(10)
Arne Koopman and Daniel Roggen
Evolving Dynamics in an Artificial Regulatory Network Model	571	(10)
P. Dwight Kuo, André Leier, and Wolfgang Banzhaf
The Application of Bayesian Optimization and Classifier Systems in Nurse Scheduling	581	(10)
Jingpeng Li and Uwe Aickelin
An Evolutionary Approach to Modeling Radial Brightness Distributions in Elliptical Galaxies	591	(11)
Jin Li, Xin Yao, Colin Frayn, Habib G. Khosroshahi, and Somak Raychaudhury
Conference Paper Assignment Using a Combined Greedy/Evolutionary Algorithm	602	(10)
Juan Julián Merelo-Guervós and Pedro Castillo-Valdivieso
A Primer on the Evolution of Equivalence Classes of Bayesian-Network Structures	612	(10)
Jorge Muruzábal and Carlos Cotta
The Infection Algorithm: An Artificial Epidemic Approach for Dense Stereo Matching	622	(11)
Gustavo Olague, Francisco Fernández de Vega, Cynthia B. Pérez, and Evelyne Lutton
Optimising Cancer Chemotherapy Using Particle Swarm Optimisation and Genetic Algorithms	633	(9)
Andrei Petrovski, Bhavani Sudha, and John McCall
An Evolutionary Algorithm for Column Generation in Integer Programming: An Effective Approach for 2D Bin Packing	642	(10)
Jakob Puchinger and Günther R. Raidl
An Improved Evaluation Function for the Bandwidth Minimization Problem	652	(10)
Eduardo Rodriguez-Tello, Jin-Kao Hao, and Jose Torres-Jimenez
Coupling of Evolution and Learning to Optimize a Hierarchical Object Recognition Model	662	(10)
Georg Schneider, Heiko Wersing, Bernhard Sendhoff, and Edgar Körner
Evolution of Small-World Networks of Automata for Computation	672	(10)
Marco Tomassini, Mario Giacobini, and Christian Darabos
Recognizing Speed Limit Sign Numbers by Evolvable Hardware	682	(10)
Jim Torresen, Jorgen W. Bakke, and Lukas Sekanina
Dynamic Routing Problems with Fruitful Regions: Models and Evolutionary Computation	692	(10)
Jano I. van Hemert and J.A. La Poutré
Optimising the Performance of a Formula One Car Using a Genetic Algorithm	702	(10)
Krzysztof Wloch and Peter J. Bentley
Multi-objective Optimisation
An Inexpensive Cognitive Approach for Bi-objective Optimization Using Bliss Points and Interaction	712	(10)
Hussein A. Abbass
Finding Knees in Multi-objective Optimization	722	(10)
Jürgen Branke, Kalyanmoy Deb, Henning Dierolf, and Matthias Osswald
Multi-objective Parallel Tabu Search	732	(10)
Daniel Jaeggi, Chris Asselin-Miller, Geoff Parks, Timoleon Kipouros, Theo Bell, and John Clarkson
SPEA2+: Improving the Performance of the Strength Pareto Evolutionary Algorithm 2	742	(10)
Mifa Kim, Tomoyuki Hiroyasu, Mitsunori Miki, and Shinya Watanabe
An Extension of Generalized Differential Evolution fir Multi-objective Optimization with Constraints	752	(10)
Saku Kukkonen and Jouni Lampinen
Adaptive Weighted Particle Swarm Optimisation for Multi-objective Optimal Design of Alloy Steels	762	(10)
Mahdi Mahfouf, Min-You Chen, and Derek Arthur Linkens
Multi-objective Optimisation by Co-operative Co-evolution	772	(10)
Kuntinee Maneeratana, Kittipong Boonlong, and Nachol Chaiyaratana
Sequential Process Optimisation Using Genetic Algorithms	782	(10)
Victor Oduguwa, Ashutosh Tiwari, and Rajkumar Roy
On Test Functions for Evolutionary Multi-objective Optimization	792	(11)
Tatsuya Okabe, Yaochu Jin, Markus Olhofer, and Bernhard Sendhoff
Multi-objective Optimization of a Composite Material Spring Design Using an Evolutionary Algorithm	803	(9)
Frédéric Ratle, Benoit Lecarpentier, Richard Labib, and François Trochu
Dominance Based Crossover Operator for Evolutionary Multi-objective Algorithms	812	(10)
Olga Rudenko and Marc Schoenauer
Evolutionary Bi-objective Controlled Elevator Group Regulates Passenger Service Level and Minimises Energy Consumption	822	(10)
Tapio Tyni and Jari Ylinen
Indicator-Based Selection in Multiobjective Search	832	(11)
Eckart Zitzler and Simon Künzli
Co-evolution
Intransitivity in Coevolution	843	(9)
Edwin D. de Jong
Group Transport of an Object to a Target That Only Some Group Members May Sense	852	(10)
Roderich Groß and Marco Dorigo
Hawks, Doves and Lifetime Reproductive Success	862	(10)
Philip Hingston and Luigi Barone
Evolutionary Multi-agent Systems	872	(10)
Pieter J. 't Hoen and Edwin D. de Jong
Credit Assignment Among Neurons in Co-evolving Populations	882	(10)
Vineet R. Khare, Xin Yao, and Bernhard Sendhoff
A Visual Demonstration of Convergence Properties of Cooperative Coevolution	892	(10)
Liviu Panait, R. Paul Wiegand, and Sean Luke
Cooperative Coevolution of Image Feature Construction and Object Detection	902	(10)
Mark E. Roberts and Ela Claridge
Spatial Embedding and Loss of Gradient in Cooperative Coevolutionary Algorithms	912	(10)
R. Paul Wiegand and Jayshree Sarma
A High Performance Multi-objective Evolutionary Algorithm Based on the Principles of Thermodynamics	922	(10)
Xiufen Zou, Minzhong Liu, Lishan Kang, and Jun He
Robotics and Multi-agent Systems
Robustness in the Long Run: Auto-teaching vs Anticipation in Evolutionary Robotics	932	(10)
Nicolas Godzik, Marc Schoenauer, and Michèle Sebag
A Self-adaptive Neural Learning Classifier System with Constructivism for Mobile Robot Control	942	(10)
Jacob Hurst and Larry Bull
An Approach to Evolutionary Robotics Using a Genetic Algorithm with a Variable Mutation Rate Strategy	952	(10)
Yoshiaki Katada, Kazuhiro Ohkura, and Kanji Ueda
Translating the Dances of Honeybees into Resource Location	962	(10)
DaeEun Kim
Natural Policy Gradient Reinforcement Learning for a CPG Control of a Biped Robot	972	(10)
Yutaka Nakamura, Takeshi Mori, and Shin Ishii
Evaluation of Adaptive Nature Inspired Task Allocation Against Alternate Decentralised Multiagent Strategies	982	(9)
Richard Price and Peter Tino
A Neuroevolutionary Approach to Emergent Task Decomposition	991	(10)
Jekanthan Thangavelautham and Gabriele M.T. D'Eleuterio
Evolving the "Feeling" of Time Through Sensory-Motor Coordination: A Robot Based Model	1001	(10)
Elio Tuci, Vito Trianni, and Marco Dorigo
Learning Classifier Systems and Data Mining
An Artificial Immune System for Fuzzy-Rule Induction in Data Mining	1011	(10)
Roberto T. Alves, Myriam R. Delgado, Heitor S. Lopes, and Alex A. Freitas
Speeding-Up Pittsburgh Learning Classifier Systems: Modeling Time and Accuracy	1021	(11)
Jaume Bacardit, David E. Goldberg, Martin V. Butz, Xavier Llorà, and Josep M. Garrell
A Simple Payoff-Based Learning Classifier System	1032	(10)
Larry Bull
Lookahead and Latent Learning in a Simple Accuracy-Based Classifier System	1042	(9)
Larry Bull
Knowledge Extraction and Problem Structure Identification in XCS	1051	(10)
Martin V. Butz, Pier Luca Lanzi, Xavier Llorà, and David E. Goldberg
Forecasting Time Series by Means of Evolutionary Algorithms	1061	(10)
Cristóbal Luque del Arco-Calderón, Pedro Isasi Viñuela, and Julio César Hernández Castro
Detecting and Pruning Introns for Faster Decision Tree Evolution	1071	(10)
Jeroen Eggermont, Joost N. Kok, and Walter A. Kosters
Evolutionary Multiobjective Clustering	1081	(11)
Julia Handl and Joshua Knowles
Web Page Classification with an Ant Colony Algorithm	1092	(11)
Nicholas Holden and Alex A. Freitas
Oneiric Processing Utilising the Anticipatory Classifier System	1103	(10)
Julian C. Holley, Anthony G. Pipe, and Brian Carse
Self-organizing Neural Grove: Efficient Multiple Classifier System Using Pruned Self-generating Neural Trees	1113	(10)
Hirotaka Inoue and Hiroyuki Narihisa
Evolutionary Multiobjective Knowledge Extraction for High-Dimensional Pattern Classification Problems	1123	(10)
Hisao Ishibuchi and Satoshi Namba
Ensemble Learning with Evolutionary Computation: Application to Feature Ranking	1133	(10)
Kees Jong, Elena Marchiori, and Michèle Sebag
Fast Unsupervised Clustering with Artificial Ants	1143	(10)
Nicolas Labroche, Christiane Guinot, and Gilles Venturini
A Novel Method of Searching the Microarray Data for the Best Gene Subsets by Using a Genetic Algorithm	1153	(10)
Bin Ni and Juan Liu
Using Genetic Programming for Feature Creation with a Genetic Algorithm Feature Selector	1163	(9)
Matthew G. Smith and Larry Bull
AgentP Model: Learning Classifier System with Associative Perception	1172	(11)
Zhanna V. Zatuchna
Author Index	1183