Hill climbing matlab

Basic Concepts, Algorithms, and Applications

FUNDAMENTALS OF NATURAL COMPUTING

PUBLISHED TITLES

HANDBOOK OF SCHEDULING: ALGORITHMS, MODELS, AND PERFORMANCE ANALYSIS Joseph Y.-T. Leung

THE PRACTICAL HANDBOOK OF INTERNET COMPUTING Munindar P. Singh

HANDBOOK OF DATA STRUCTURES AND APPLICATIONS Dinesh P. Mehta and Sartaj Sahni

DISTRIBUTED SENSOR NETWORKS S. Sitharama Iyengar and Richard R. Brooks

SPECULATIVE EXECUTION IN HIGH PERFORMANCE COMPUTER ARCHITECTURES David Kaeli and Pen-Chung Yew

SCALABLE AND SECURE INTERNET SERVICES AND ARCHITECTURE Cheng-Zhong Xu

HANDBOOK OF BIOINSPIRED ALGORITHMS AND APPLICATIONS Stephan Olariu and Albert Y. Zomaya

HANDBOOK OF ALGORITHMS FOR WIRELESS NETWORKING AND MOBILE COMPUTING Azzedine Boukerche

HANDBOOK OF COMPUTATIONAL MOLECULAR BIOLOGY Srinivas Aluru

FUNDEMENTALS OF NATURAL COMPUTING: BASIC CONCEPTS, ALGORITHMS, AND APPLICATIONS Leandro Nunes de Castro

CHAPMAN & HALL/CRC COMPUTER and INFORMATION SCIENCE SERIES

Series Editor: Sartaj Sahni

Basic Concepts, Algorithms, and Applications

Leandro Nunes de Castro

FUNDAMENTALS OF NATURAL COMPUTING

Catholic University of Santos (UniSantos) Brazil

Cover designed by Sandro de Castro.

CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742

© 2007 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works Version Date: 20110713

International Standard Book Number-13: 978-1-4200-1144-9 (eBook - PDF)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmit- ted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright. com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe.

Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com

and the CRC Press Web site at http://www.crcpress.com

To Nature,

Lásara, José and Elizabete

This new science started from the assumption

that in the end it is possible to bring together

completely different fields of investigation.

FOREWORD

The idea of writing this book was based on two main motivations. First, to bring together several topics relating computing and nature in a single volume. Some of these topics have been dealt with by specific texts for some time (e.g., neural networks and evolutionary algorithms), but some are quite young (e.g., swarm intelligence, artificial immune systems, DNA and quantum computing). A sec- ond motivation was because all natural computing topics are, by themselves, sources of endless fascination and usefulness, and I would like to bring such excitement to a broad audience and to potentially new researchers in the field.

Although there are some popular science books that discourse about all or most of these subjects in an informal and illustrative way (see Appendix C), I wanted to do it more formally, providing the reader with the conceptual and algorithmic fundaments of natural computing, together with some design princi- ples, exercises, illustrations and lists of potential applications.

This book has started from my own research background over ten years ago, but mostly from lectures given at the University of Kent at Canterbury (UK) on a final year undergraduate course called, at that time, Novel Computing Para- digms. This same course has been adapted and is currently called Natural Com- puting, and has been further extended to become a graduate course in Computer Science and Engineering at the Universities of Campinas (Unicamp) and of Santos (UniSantos) in Brazil. But certainly these are not the only courses related to the subject matters presented in this book. Nowadays, there are several courses throughout the world on bio-inspired computing, bioinformatics, artifi- cial life, fractal geometry, molecular computing, etc., that could benefit from this text, mainly graduate and final year undergraduate courses.

The writing of this text started on June 2002. Any lengthy document that in- volves so many concepts and ideas, and that takes so long to be written contains errors and omissions, and this book is surely no exception to this rule. If you find errors or have other comments to improve this volume, please e-mail them to me at lnunes@unisantos.br. The errata will be added to the book’s website: http://lsin.unisantos.br/lnunes/books.

Leandro Nunes de Castro

PREFACE

Natural computing is a new and broad field of investigation that brings together not only words but also subjects that were once believed to be mutually exclu- sive: nature and computing. Some problems strike researchers for the difficulty in providing (feasible) solutions. They cannot be resolved using the standard computing and problem solving techniques. They stimulate hard thinking and the search for solutions in the best problem-solver ever known – Nature.

The hallmark of any new discipline or field of investigation is that it must be able to provide successful solutions and models to old, yet unresolved, problems and to new ones as well. But this is only one of the benefits of natural comput- ing. It also gives us a new form of understanding and interacting with nature; new methods of simulating, emulating and even realizing natural phenomena have been proposed. Natural computing simulations of nature are now being used as realistic models of plant growth, development, landscapes, complex behaviors, etc.

If we acknowledge the fact that computing may need a change in paradigm soon, when current computer technology reaches its limit in processing power and information storage, then natural computing has closed its loop and com- pleted all its three main branches:

a) The use of nature to inspire the development of novel computing tech- niques for solving complex problems.

b) The use of computers to recreate natural phenomena and organisms.

c) The use of natural materials (e.g., biomolecules) to compute.

What follows is a tour of fields never gathered between the same book jacket covers. We will look at the fundaments of the three main branches of natural computing: computing inspired by nature, the simulation and emulation of na- ture in computers, and computing with natural materials. What unites these different systems, processes and theories is a recurring inspiration, use and in- teraction with nature. At each scale you will be able to see the imprint of nature and how it can be used for computational purposes.

Over the last few decades, there has been a considerable expansion of interest in the exchange of ideas between the natural sciences and computing. Numerous conferences have been organized, books edited and written, and journals started (cf. Appendix C). In summary, this book is an attempt to consolidate and inte- grate the basic concepts, algorithms, and applications across a wide range of interrelated fields of research and disciplines into a single coherent text. At one level the result can be viewed as just that - an integration and consolidation of knowledge. Nevertheless, I have felt that the process of putting all these ideas together into a single volume has led to the emergent phenomenon in which the whole is more than the sum of its parts.

Main Features

The contents of this book are very attractive for undergraduate students, lectur- ers, academic researchers (mainly newcomers) and industry parties in Biology, Computing, Engineering, (Applied) Mathematics and Physics, interested in developing and applying alternative problem solving techniques inspired by nature, knowing the most recent computing paradigms, and discovering how computers can aid the understanding and simulation of nature. The book is writ- ten in a textbook style with illustrative and worked examples, and provides dif- ferent types of exercises to assess the comprehension of the contents presented and stimulate further investigation into each of the subjects. The many ques- tions, computational exercises, thought exercises and projects that appear at the end of each chapter are aimed at complementing, solidifying, practicing and developing the readers’ ability to explore the many concepts and tools intro- duced. With few exceptions, such as the thought questions, projects and chal- lenges, these should be solved with a fairly small amount of work, what may depend on the readers’ background.

Most chapters contain a brief description of the main ideas and algorithms about selected applications from the literature. In most cases either real-world or benchmark problems were chosen for presentation. These examples serve the purpose of illustrating some types of problems that can be solved using the methods introduced, not to provide an in depth description of how the problems were effectively solved using the techniques. They are illustrations of potential applications instead of case studies, what allows the presentation of a larger number of applications in detriment of a detailed, lengthier description.

The innovative concepts and tools described in this volume have already be- come very good candidates to be applied as solution tools to real-world prob- lems, and have also been incorporated as part of academic degrees in disciplines related to computing, biological modeling, biomedical engineering, and bioin- formatics. Although there are books in the literature dealing with each of these parts separately, there is no single volume dealing with these subjects altogether. Similarly to the standard well-known Artificial Intelligence books, this volume was primarily written to support first courses on the many subjects covered.

Structure of the Book

The book is composed of eleven chapters divided into three main parts, plus three appendices. Each of its three main parts is composed of a set of topics which, by themselves, would constitute a discipline on their own. It would be impracticable to cover all subjects in detail, include the most recent advances in each field, and provide the necessary biological and mathematical background in the main text. The approach taken was, thus, to present the fundaments of each technique; that is, the simplest and pioneer proposals in each field. Recent de- velopments can be found in the cited specialized literature, and are being pro- posed each day.

The eleven chapters composing the main body of the text are:

Chapter 1: From Nature to Natural Computing

Chapter 2: Conceptualization

Part I – Computing Inspired by Nature

Chapter 3: Evolutionary Computing

Chapter 4: Neurocomputing

Chapter 5: Swarm Intelligence

Chapter 6: Immunocomputing

Part II – The Simulation and Emulation of Natural Phenomena in Computers

Chapter 7: Fractal Geometry of Nature

Chapter 8: Artificial Life

Part III – Computing with New Natural Materials

Chapter 9: DNA Computing

Chapter 10: Quantum Computing

Chapter 11: Afterwords

The motivation from nature is stressed in all chapters independently and an appendix (Appendix A) was created to support the search and quick access for the meaning of the biological, chemical and physical terminology. Another ap- pendix (Appendix B) was especially created to provide the reader with some minimal background knowledge and reference to the mathematics and basic theoretical foundations necessary to understand the contents of the book. The reader is pointed to the appendices when necessary. One last appendix (Appen- dix C) was written to guide the reader, mainly newcomers, to the literature. Appendix C contains my personal comments on selected bibliography (reason why the list is incomplete and others’ comments may differ from mine), and a list of journals and conferences in which to publish and find information on the subjects.

A quick glance through the book is enough to note that emphasis was given to Part I of the text. The reasons are twofold. First, some fields of investigation composing this part are older than those composing parts II and III or are used as a basis for Part II and, thus, have a wider bibliography and set of well- established techniques. Second, the first part could serve as a general reference for the many existing courses on bio-inspired computing, but for which there is no single volume available to date. For Part II there are several books on Frac- tals and on Artificial Life that could be used as standard references. In Part III there are not only specific books on DNA and Quantum computing, but also books involving both paradigms. See Appendix C and the respective chapters for a list of these references.

How to Use this Book

Natural computing is a very broad area and, therefore, this is a big book. The text has been written to be used by newcomers to the field, lecturers (as a text-

book) and independent readers. Each one of these may approach the text differ- ently. This section provides a brief guidance on how to use this book.

For independent students and newcomers

This book is supposed to be a self-contained and accessible introduction to natu- ral computing, even to the independent reader. The readers are assumed to have some background knowledge on linear algebra, discrete mathematics, notions from computing and basic programming skills. If this is not the case, they are strongly encouraged to go through Appendix B thoroughly before start reading the main text. Even if the reader is familiar with all these concepts, he/she is encouraged to have a quick look at Appendix B and certify the familiarity with all the concepts presented, because these were selected due to their importance to a basic understanding of natural computing. As a guide, an independent reader may want to go through the suggested programs for a one-term or a full- year course, as described below.

The appendices and exercises were designed so as to help the reader get to know and understand each field independently and as a single discipline. The Table of Contents and introductions to each chapter provide a brief description of their contents that may be useful while choosing what topics to study. The Natural Computing Virtual Laboratory (LVCoN http://lsin.unisantos.br/lvcon) can also be used as a platform to play with many of the techniques discussed in this text. The reader is also invited to download the book slides from the web- site: (http://lsin.unisantos.br/lnunes/books).

For instructors

As this book covers a diverse range of topics, it may be used in various different courses and in distinct ways. An ideal course would take two semesters, but an introductory (general overview) natural computing course could be taught in a single semester.

In a one-semester general introductory course about the whole book, the fol- lowing chapters/sections are suggested: Chapters 1 and 2 (all sections); Chapter 3 (Sections 3.2, 3.4 and 3.5); Chapter 4 (Sections 4.2, 4.3, 4.4.2, 4.4.3, 4.4.5); Chapter 5 (Sections 5.2, and 5.4); Chapter 6 (Sections 6.2, 6.3, 6.5, 6.6, 6.7.1); Chapter 7 (Sections 7.2, 7.3, 7.7); Chapter 8 (Sections 8.2, 8.3.1, 8.3.2, 8.3.3, 8.3.9, 8.3.10, 8.3.11); Chapter 9 (Sections 9.2 and 9.3); Chapter 10 (Sections 10.2, 10.3, and 10.4). In addition to these, the introductory sections of each chapter are mandatory, and the sections that make a parallel between the natural and the computational systems are highly recommended so that the student can understand the loop ‘nature ↔ computing’.