Second Edition Intelligent Systems for Engineers and Scientists © 2001 by CRC Press LLC Second Edition Intelligent Systems for Engineers and Scientists Adrian A. Hopgood CRC Press Boca Raton London New York Washington, D. disclaimer3 Page 1 Thursday, August 2, 2001 1:50 PM Library of Congress Cataloging-in-Publication Data Hopgood, Adrian A. Intelligent systems for engineers and scientists / Adrian A.
Includes bibliographical references and index. Computer-aided engineering.3′3′02462--dc21 00-010341 This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted with permission, and sources are indicated. A wide variety of references are listed.
Reasonable efforts have been made to publish reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials or for the consequences of their use. Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, microfilming, and recording, or by any information storage or retrieval system, without prior permission in writing from the publisher. The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for creating new works, or for resale. Specific permission must be obtained in writing from CRC Press LLC for such copying.
Direct all inquiries to CRC Press LLC, 2000 N., Boca Raton, Florida 33431. 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 CRC Press Web site at www.crcpress © 2001 by CRC Press LLC No claim to original U. Government works International Standard Book Number 0-8493-0456-3 Library of Congress Card Number 00-010341 Printed in the United States of America 3 4 5 6 7 8 9 0 Printed on acid-free paper Preface “Intelligent systems” is a broad term, covering a range of computing techniques that have emerged from research into artificial intelligence.
It includes symbolic approaches — in which knowledge is explicitly expressed in words and symbols — and numerical approaches such as neural networks, genetic algorithms, and fuzzy logic. In fact, many practical intelligent systems are a hybrid of different approaches. Whether any of these systems is really capable of displaying intelligent behavior is a moot point. Nevertheless, they are extremely useful and they have enabled elegant solutions to a wide variety of difficult problems.
There are plenty of other books available on intelligent systems and related technologies, but I hope this one is substantially different. It takes a practical view, showing the issues encountered in the development of applied systems. I have tried to describe a wide range of intelligent systems techniques, with the help of realistic problems in engineering and science. The examples included here have been specifically selected for the details of the techniques that they illustrate, rather than merely to survey current practice.
The book can be roughly divided into two parts. Chapters 1 to 10 describe the techniques of intelligent systems, while Chapters 11 to 14 look at four broad categories of applications. These latter chapters explore in depth the design and implementation issues of applied systems, together with their advantages and difficulties. The four application areas have much in common, as they all concern automated decision making, while making the best use of the available information.
The first edition of this book was published as Knowledge-Based Systems for Engineers and Scientists. It was adopted by the Open University for its course T396: Artificial Intelligence for Technology and, as a result, I have received a lot of useful feedback. I hope that this new edition addresses the weaknesses of the previous one, while retaining and building upon its strengths. As well as updating the entire book, I have added new chapters on intelligent agents, neural networks, optimization algorithms (especially genetic algorithms), and hybrid systems.
A new title was therefore needed to reflect the broader scope of this new edition. Intelligent Systems for Engineers and © 2001 by CRC Press LLC Scientists seems appropriate, as it embraces both the explicit knowledge-based models that are retained from the first edition and the implicit numerical models represented by neural networks and optimization algorithms. I hope the book will appeal to a wide readership. In particular, I hope that students will be drawn toward this fascinating area from all scientific and engineering subjects, not just from the computer sciences.
Beyond academia, the book will appeal to engineers and scientists who either are building intelligent systems or simply want to know more about them. The first edition was mostly written while I was working at the Telstra Research Laboratories in Victoria, Australia, and subsequently finished upon my return to the Open University in the UK. I am still at the Open University, where this second edition was written. Many people have helped me, and I am grateful to them all.
The following all helped either directly or indirectly with the first edition (in alphabetical order): Mike Brayshaw, David Carpenter, Nicholas Hallam, David Hopgood, Sue Hopgood, Adam Kowalzyk, Sean Ogden, Phil Picton, Chris Price, Peter Richardson, Philip Sargent, Navin Sullivan, Neil Woodcock, and John Zucker. I am also indebted to those who have helped in any way with this new edition. I am particularly grateful to Tony Hirst for his detailed suggestions for inclusion and for his thoughtful comments on the drafts. I also extend my thanks to Lars Nolle for his helpful comments and for supplying Figures 7.18; to Jon Hall for his comments on Chapter 5; to Sara Parkin and Carole Gustafson for their careful proofreading; and to Dawn Mesa for making the publication arrangements.
Finally, I am indebted to Sue and Emily for letting me get on with it. Normal family life can now resume. Adrian Hopgood www.com Email me: adrian.uk © 2001 by CRC Press LLC The author Adrian Hopgood has earned his BSc from Bristol University, PhD from Oxford University, and MBA from the Open University. After completing his PhD in 1984, he spent two years developing applied intelligent systems for Systems Designers PLC.
He subsequently joined the academic staff of the Open University, where he has established his research in intelligent systems and their application in engineering and science. Between 1990 and 1992 he worked for Telstra Research Laboratories in Australia, where he contributed to the development of intelligent systems for telecommunications applications. Following his return to the Open University he led the development of the course T396 – Artificial Intelligence for Technology. He has further developed his interests in intelligent systems and pioneered the development of the blackboard system, ARBS.
© 2001 by CRC Press LLC For Sue and Emily © 2001 by CRC Press LLC Contents Chapter one: Introduction 1.2 Knowledge-based systems 1.3 The knowledge base 1.4 Deduction, abduction, and induction 1.5 The inference engine 1.6 Declarative and procedural programming 1.11 Integration with other software References Further reading Chapter two: Rule-based systems 2.1 Rules and facts 2.2 A rule-based system for boiler control 2.3 Rule examination and rule firing 2.5 The closed-world assumption 2.6 Use of variables within rules 2.1 Single and multiple instantiation of variables 2.1 First come, first served 2.1 The backward-chaining mechanism 2.2 Implementation of backward-chaining 2.3 Variations of backward-chaining 2.11 Explanation facilities © 2001 by CRC Press LLC 2.12 Summary References Further reading Chapter three: Dealing with uncertainty 3.1 Sources of uncertainty 3.1 Representing uncertainty by probability 3.2 Direct application of Bayes’ theorem 3.4 Using the likelihood ratios 3.5 Dealing with uncertain evidence 3.7 Combining Bayesian rules with production rules 3.8 A worked example of Bayesian updating 3.9 Discussion of the worked example 3.10 Advantages and disadvantages of Bayesian updating 3.2 Making uncertain hypotheses 3.3 Logical combinations of evidence 3.4 A worked example of certainty theory 3.5 Discussion of the worked example 3.6 Relating certainty factors to probabilities 3.4 Possibility theory: fuzzy sets and fuzzy logic 3.1 Crisp sets and fuzzy sets 3.1 Dempster–Shafer theory of evidence 3.6 Summary References Further reading Chapter four: Object-oriented systems 4.1 Objects and frames 4.2 An illustrative example 4.5 Creation and deletion of instances 4.5 Inheritance © 2001 by CRC Press LLC 4.2 Multiple and repeated inheritance 4.3 Specialization of methods 4.7 Unified Modeling Language (UML) 4.9 Message passing and function calls 4.11 Further aspects of OOP 4.4 Active values and daemons 4.12 Frame-based systems 4.13 Summary References Further reading Chapter five: Intelligent agents 5.1 Characteristics of an intelligent agent 5.2 Agents and objects 5.1 Logic-based architectures 5.2 Emergent behavior architectures 5.3 Knowledge-level architectures 5.1 Benefits of a multiagent system 5.2 Building a multiagent system 5.3 Communication between agents 5.5 Summary References Further reading Chapter six: Symbolic learning 6.2 Learning by induction 6.2 Learning viewed as a search problem 6.3 Techniques for generalization and specialization 6.3 Case-based reasoning (CBR) 6.2 Retrieving cases © 2001 by CRC Press LLC 6.3 Adapting case histories 6.4 Dealing with mistaken conclusions 6.4 Summary References Further reading Chapter seven: Optimization algorithms 7.2 The search space 7.3 Searching the search space 7.4 Hill-climbing and gradient descent algorithms 7.2 Steepest gradient descent or ascent 7.3 Gradient-proportional descent 7.4 Conjugate gradient descent or ascent 7.1 The basic GA 7.4 Variable length chromosomes 7.5 Building block hypothesis 7.6 Selecting GA parameters 7.9 Finding multiple optima 7.7 Summary References Further reading Chapter eight: Neural networks 8.2 Neural network applications 8.4 Content-addressable memory 8.3 Nodes and interconnections 8.4 Single and multilayer perceptrons 8.2 Perceptrons as classifiers 8.5 Some practical considerations 8.5 The Hopfield network © 2001 by CRC Press LLC 8.7 The Hamming network 8.8 Adaptive Resonance Theory (ART) networks 8.9 Kohonen self-organizing networks 8.10 Radial basis function networks 8.11 Summary References Further reading Chapter nine: Hybrid systems 9.1 Convergence of techniques 9.3 Genetic-fuzzy systems 9.4 Neuro-fuzzy systems 9.5 Genetic-neural systems 9.6 Clarifying and verifying neural networks 9.7 Learning classifier systems 9.8 Summary References Further reading Chapter ten: Tools and languages 10.1 A range of intelligent systems tools 10.2 Expert system shells 10.3 Toolkits and libraries 10.4 Artificial intelligence languages 10.2 Other data types 10.3 Backtracking in Prolog 10.7 Comparison of AI languages 10.8 Summary References Further reading Chapter eleven: Systems for interpretation and diagnosis 11.2 Deduction and abduction for diagnosis © 2001 by CRC Press LLC 11.3 Depth of knowledge 11.3 Combining shallow and deep knowledge 11.4 Model-based reasoning 11.1 The limitations of rules 11.2 Modeling function, structure, and state 11.3 Using the model 11.8 Using problem trees 11.9 Summary of model-based reasoning 11.5 Case study: a blackboard system for interpreting ultrasonic images 11.2 Knowledge sources in ARBS 11.3 Rules in ARBS 11.4 Inference engines in ARBS 11.5 The stages of image interpretation 11.6 The use of neural networks 11.7 Rules for verifying neural networks 11.6 Summary References Further reading Chapter twelve: Systems for design and selection 12.1 The design process 12.2 Design as a search problem 12.3 Computer aided design 12.4 The product design specification (PDS): a telecommunications case study 12.2 Alternative views of a network 12.5 Summary of PDS case study 12.6 Constraint propagation and truth maintenance 12.7 Case study: the design of a lightweight beam 12.2 Optimization and evaluation 12.8 Design as a selection exercise 12.1 Overview © 2001 by CRC Press LLC 12.3 The polymer selection example 12.4 Two-stage selection 12.6 A naive approach to scoring 12.7 A better approach to scoring 12.8 Case study: the design of a kettle 12.9 Reducing the search space by classification 12.9 Failure mode and effects analysis (FMEA) 12.10 Summary References Further reading Chapter thirteen: Systems for planning 13.2 Classical planning systems 13.2 An example problem 13.3 A simple planning system in Prolog 13.4 Considering the side effects of actions 13.1 Maintaining a world model 13.2 Benefits of hierarchical planning 13.3 Hierarchical planning with ABSTRIPS 13.6 Postponement of commitment 13.1 Partial ordering of plans 13.2 The use of planning variables 13.7 Job-shop scheduling 13.2 Some approaches to scheduling 13.8 Constraint-based analysis 13.1 Constraints and preferences 13.2 Formalizing the constraints 13.3 Identifying the critical sets of operations 13.4 Sequencing in the disjunctive case 13.5 Sequencing in the nondisjunctive case 13.