N. Nedjah, L. M. Mourelle (Eds.) Evolvable Machines Studies in Fuzziness and Soft Computing, Volume 161 Editor-in-chief Prof. Janusz Kacprzyk Systems Research Institute Polish Academy of Sciences ul. Newelska 6 01-447 Warsaw Poland E-mail: [email protected] Further volumes of this series Vol. 152. J. Rajapakse, L. Wang (Eds.) Neural Information Processing: Research can be found on our homepage: and Development, 2004 springeronline.com ISBN 3-540-21123-3 Vol. 144. Z. Sun, G.R. Finnie Vol. 153. J. Fulcher, L.C. Jain (Eds.) Intelligent Techniques in E-Commerce, 2004 Applied Intelligent Systems, 2004 ISBN 3-540-20518-7 ISBN 3-540-21153-5 Vol. 145. J. Gil-Aluja Vol. 154. B. Liu Fuzzy Sets in the Management of Uncertainty Theory, 2004 Uncertainty, 2004 ISBN 3-540-21333-3 ISBN 3-540-20341-9 Vol. 155. G. Resconi, J.L. Jain Vol. 146. J.A. Gamez, S. Moral, A. Salmeron Intelligent Agen ts, 2004 (Eds.) ISBN 3-540-22003-8 Advances in Bayesian Networks, 2004 ISBN 3-540-20876-3 Vol. 156. R. Tadeusiewicz, M.R. Ogiela Medical Image Understanding Technology, Vol. 147. K. Watanabe, M.M.A. Hashem 2004 New Algorithms and their Applications to ISBN 3-540-21985-4 Evolutionary Robots, 2004 ISBN 3-540-20901-8 Vol. 157. R.A. Aliev, F. Fazlollahi, R.R. Aliev Soft Computing and its Applications in Vol. 148. C. Martin-Vide, V. Mitrana, Business and Economics, 2004 G. Pitun (Eds.) ISBN 3-540-22138-7 Formal Languages and Applications, 2004 ISBN 3-540-20907-7 Vol. 158. K.K. Dompere Cost-Benefit Analysis and the Theory of Fuzzy Decisions - Identification and Vol. 149. J.J. Buckley Measurement Theory, 2004 Fuzzy Statistics, 2004 ISBN 3-540-22154-9 ISBN 3-540-21084-9 Vol. 159. E. Damiani, L.C. Jain, M. Madravia Vol. 150. L. Bull (Ed.) Soft Computing in Software Engineering, Applications ofLearning Classifier Systems, 2004 2004 ISBN 3-540-22030-5 ISBN 3-540-21109-8 Vol. 160. K.K. Dompere Vol. 151. T. Kowalczyk, E. Pleszczyliska, Cost-Benefit Analysis and the Theory F. Ruland (Eds.) ofFuzzy Decisions - Fuzzy Value Theory, Grade Models and Methods for Data 2004 Analysis, 2004 ISBN 3-540-22161-1 ISBN 3-540-21120-9 Nadia Nedjah Luiza de Macedo Mourelle (Eds.) Evolvable Machines Theory & Practice a - Springer Nadia Nedjah Luiza de Macedo Mourelle Universidade do Estado do Rio de Janeiro Departamento de Engenharia de Sistemas e Computapio Rua SBo Francisco Xavier, 524 MaracanH, CEP, 20550-900 Rio de Janeiro, RJ Brazil E-mail: [email protected] [email protected] ISSN 1434-9922 ISBN 3-540-22905-1 Springer Berlin Heidelberg New York Library of Congress Control Number: 2004110948 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, reuse of illustrations, recitations, broadcasting, reproduction on microfilm 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-Verlag. Violations are liable to prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springeronline.com 0 Springer-Verlag Berlin Heidelberg 2005 Printed in Germany The use of general descriptive names, registered names trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typesetting: data delivered by editors Cover design: E. Kirchner, Springer-Verlag, Heidelberg Printed on acid free paper 6213020lM - 5 4 3 2 1 0 To the memory of my father Ali and my beloved mother Fatiha, Nadia To my beloved parents Neuxa and Luix, Luiza Preface Evolutionary algorithms are computer-based solving systems, which use the evolutionary computational models as key element in their design and im- plementation. A variety of evolutionary algorithms have been proposed. The most popular ones are genetic algorithms. They have a conceptual base of simulating the evolution of individual structures via the Darwinian natural selection process. The process depends on the adherence of the individual structures as defined by its environment to the problem pre-determined con- straints. Genetic algorithms are well suited to provide an efficient solution of hard problems. Methods for artificial evolution of active components, such as programs and hardware, are rapidly developing branches of adaptive computation and adaptive engineering. The evolutionary process can produce, as results, com- putational expressions, e.g. algorithms, or machines, e.g. mechanical or elec- tronic devices. The evolved components generally present creativity as well as inventiveness. Furthermore, they are usually efficient in terms of the specified requirements. This book is devoted to reporting innovative and significant progress in automatic and evolutionary methodology of applied to machine design. The- oretical as well as practical chapters are contemplated. The content of this book is divided into three main parts. The first part consists of four chapters while the second and third part have three chapters. In the following, we give a brief description of the main contribution of each of these chapters. Part I: Evolvable Robots In Chapter 1, which is entitled Learning for Cooperative Transportation by Autonomous Humanoid Robots, the authors, Yutaka Inoue, Takahiro To- VIII Preface hge and Hitoshi Iba, first clarify the practical difficulties we face from the cooperative transportation task with two bodies of humanoid robots. After- wards, we propose a solution to these difficulties and empirically show the effectiveness both by simulation and by real robots. In Chapter 2, which is entitled Evolution, Robustness and Adaptation of Sidewinding Locomotion of Simulated Snake-like Robot, the authors, namely Ivan Tanev, Thomas Ray and Andrzej Buller, inspired by the effi- cient method of locomotion of the rattlesnake, propose an automatic design through genetic programming, of the fastest possible sidewinding locomotion of simulated limbless, wheelless snake-like robot or snakebot. this work can be considered as a step forward towards building real Snakebots that are able to perform robustly in difficult environment. In Chapter 3, which entitled Evolution of Khepera Robotic Controllers with Hierarchical Genetic Programming Techniques, the authors, namely Marcin L. Pilat and Franz Oppacher, show how to evolve robotic controllers for a miniature mobile Khepera robot. They concentrate on control tasks for ob- stacle avoidance, wall following, and light avoidance. The robotic controllers are evolved through canonical GP implementation, linear genome GP system, and hierarchical GP methods (Automatically Defined Functions, Module Ac- quisition, Adaptive Representation through Learning). In Chapter 4, which entitled Evolving Controllers for Miniature Robots, the author, namely Michael Botros, presents a series of experiments in evolutionary robotics that used the miniature mobile robot Khepera. Khepera robot is widely used in evolutionary experiments due to its small size and light weight which simplify the setup of the environments needed for the experiments. The controllers evolved in the presented experiments include classical and spiking neural networks controllers, fuzzy logic controllers and computer program obtained by Genetic Programming. Part 11: Evolvable Hardware Synthesis In Chapter 5, which is entitled Evolutionary Synthesis of Synchronous Fi- nite State Machines, the authors, namely Nadia Nedjah and Luiza de Macedo Mourelle, propose an evolutionary methodology synthesise finite state machines. First, they optimally solve the state assignment NP-complete problem, which is inherent to designing any synchronous finite state machines using genetic algorithms. This is motivated by the fact that with an optimal state assignment one can physically implement the state machine in question using a minimal hardware area and response time. Second, with the optimal state assignment provided, we propose to use the evolutionary methodology to yield optimal evolvable hardware that implement the state machine con- trol component. The evolved hardware requires a minimal hardware area and introduces a minimal propagation delay of the machine output signals. Preface IX In Chapter 6, which is entitled Automating the Hierarchical Synthesis of MEMS Using Evolutionary Approaches, the authors, namely Zhun Fan, Ji- achuan Wang, Kisung Seo, Jianjun Hu, Ronald Rosenberg, Janis Terpenny and Erik Goodman, first discuss the hierarchy that is involved in a typical MEMS design. Then they move on to discuss how evolutionary approaches can be used to automate the hierarchical design and synthesis pro- cess for MEMS. At the system level, genetic programming, as a strong search tool, is used to generate and search in the topologically open-ended design space. A multiple-resonator microsystem design is taken as an example to il- lustrate the integrated design automation idea using evolutionary approaches at multiple levels. In Chapter 7, which is entitled An Evolutionary Approach to Multi-FPGAs System Synthesis, the authors, namely F. Ferndndez de Veja, J.I. Hi- dalgo, J.M. SQnchez and J. Lanchares, explain in details a methodology for Multi-FPGA systems design. They describe a set of techniques based on evolutionary algorithms, and we show that they are capable of solving all of the design tasks, which are partitioning, placement and routing. Firstly a hybrid compact genetic algorithm is used solves the partitioning problem and then genetic programming is exploited to evolve a solution for the two remaining tasks. Part 111: Evolvable Designs In Chapter 8, which is entitled Evolutionary Computation and Parallel Pro- cessing Applied to the Design of Multilayer Perceptrons, the authors namely, Ana Claudia M. L. Albuquerque, Jorge D. Melo and Adriiio D. D6ria Neto, present the use of genetic algorithms in defining the neural net- work's architecture and in refining its synaptic weights. A different approach of a cooperative parallel genetic algorithm with different evolution behaviors is given. Applications on approximation of functions will be illustrated. In Chapter 9, which is entitled Evolvable Fuzzy Hardware for Real-time Embedded Control in Packet Switching, the authors, namely Ju Hui Li, Meng Hiot Lim, Qi Cao, describe a scheme to implement an Evolvable Fuzzy Hardware for real-time Packet Switching Problem. The proposed evolv- able fuzzy hardware addresses many issues effectively. For the hardware im- plementation of the evolvable fuzzy hardware, real-time fuzzy inference with high-speed context switching capability is necessary. This aspect is addressed through implementation based on a context independent reconfigurable fuzzy inference chip. In Chapter 10, which is entitled Improving Multi Expression Programming: An Ascending Trail from Sea-Level Even-3-Parity Problem to Alpine Even-18- Parity Problem, the author, namely Mihai Oltean, proposes and uses several techniques for improving the search performed by Multi Expression Program- ming. Some of the most important improvements are Automatically Defined X Preface Functions and Sub-symbolic node representation. Several experiments with Multi Expression Programming are performed in this chapter. Numerical re- sults show that Multi Expression programming performs very well for the considered test problems. Nadia Nedjah, Ph.D. Luiza de Macedo Mourelle, Ph.D. Department of System Engineering & Computation Faculty of Engineering State University of Rio de Janeiro (nadia I ldmm) @eng .u er j .b r http://www.eng.uerj.br Contents Part I Evolvable Robots 1 Learning for Cooperative Transportation by Autonomous Humanoid Robots Yutaka Inoue. Takahiro Tohge. Hitoshi Iba .......................... 3 1.1 Introduction ................................................. 3 1.2 Problem in cooperative Transportation by humanoid Robots ....... 4 1.3 Approach of Transportation Control ............................ 7 1.4 Learning to Correct Positioning ................................ 9 1.4.1 Learning Model ......................................... 9 1A .2 Learning in Simulator .................................... 11 1.4.3 Result of Simulator Learning .............................. 11 1.4.4 Experiments with Real Robots ............................ 13 1.4.5 Experimental results ..................................... 15 1.5 Cooperative Transportation to Target Position ................... 15 1.5.1 Experiments with Real robots ............................. 15 1.5.2 Experimental results ..................................... 17 1.6 Discussion ................................................... 17 1.7 Conclusion .................................................. 19 References ...................................................... 19 Bibliography .................................................... 19 2 Evolution. Robustness and Adaptation of Sidewinding Locomotion of Simulated Snake-like Robot Ivan Tanev. Thomas Ray. Andrzej Buller ........................... 21 2.1 Introduction ................................................. 22 2.2 Approach ................................................... 23 2.2.1 Representation of Snakebot ............................... 23 2.2.2 Algorithmic paradigm .................................... 24 2.3 Experimental Results ......................................... 27 2.3.1 Evolution of fastest locomotion gaits ....................... 28