C O M P U T A T I O N AL I N T E L L I G E N CE F OR O P T I M I Z A T I ON C O M P U T A T I O N AL I N T E L L I G E N CE F O R O P T I M I Z A T I ON Nirwan ANSARI Edwin HOU Department of Electrical and Computer Engineering New Jersey Institute of Technology Newark, New Jersey 07102 Springer Science+Business Media, LLC ISBN 978-1-4613-7907-2 ISBN 978-1-4615-6331-0 (eBook) DOI 10.1007/978-1-4615-6331-0 Library of Congress Cataloging-in-Publication Data A CLP. Catalogue record for this book is available from the Library of Congress. Copyright © 1997 by Springer Science+Business Media New York Originally published by Kluwer Academic Publishers in 1997 Softcover reprint of the hardcover 1st edition 1997 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher, Springer Science+Business Media, LLC. Printed on acid-free paper. to the True Vine CONTENTS PREFACE 1 INTRODUCTION 1 1.1 Computational Complexity 2 1.2 Survey of Optimization Techniques 5 1.3 Organization of the Book 8 1.4 Exploratory Problems 10 2 HEURISTIC SEARCH METHODS 11 2.1 Graph Search Algorithm 12 2.2 Heuristic Functions 17 2.3 A * Search Algorithm 21 2.4 Exploratory Problems 25 3 HOPFIELD NEURAL NETWORKS 27 3.1 Discrete Hopfield Net 28 3.2 Continuous Hopfield Net 32 3.3 Content-Addressable Memory 34 3.4 Combinatorial Optimization 35 3.5 Exploratory Problems 44 4 SIMULATED ANNEALING AND STOCHASTIC MACHINES 47 4.1 Statistical Mechanics and The Metropolis Algorithm 47 4.2 Simulated Annealing 51 4.3 Stochastic Machines 59 4.4 Exploratory Problems 68 COMPUTATIONAL INTELLIGENCE FOR OPTIMIZATION 5 MEAN FIELD ANNEALING 71 5.1 Mean Field Approximation 72 5.2 Saddle-Point Expansion 73 5.3 Stability 75 5.4 Parameters of the Mean Field Net 76 5.5 Graph Bipartition - An Example 79 5.6 Exploratory Problems 81 6 GENETIC ALGORITHMS 83 6.1 Simple genetic Operators 84 6.2 An Illustrative Example 88 6.3 Why Do Genetic Algorithms Work? 90 6.4 Other Genetic Operators 94 6.5 Exploratory Problems 97 7 THE TRAVELING SALESMAN PROBLEM 99 7.1 Why Does the Hopfield Net Frequently Fail to Produce Valid Solutions? 99 7.2 Solving the TSP with Heuristic Search Algorithms 109 7.3 Solving the TSP with Simulated Annealing 117 7.4 Solving the TSP with Genetic Algorithms 119 7.5 An Overview of Eigenvalue Analysis 121 7.6 Derivation of )1] of the Connection Matrix 124 7.7 Exploratory Problems 125 8 TELECOMMUNICATIONS 127 8.1 Satellite Broadcast Scheduling 127 8.2 Maximizing Data Throughput in An Integrated TDMA Com- munications System 139 8.3 Summary 146 8.4 Exploratory Problems 148 Contents 9 POINT PATTERN MATCHING 149 9.1 Problem Formulation 150 9.2 The Simulated Annealing Framework 152 9.3 Evolutionary Programming 155 9.4 Summary 165 9.5 Exploratory Problems 166 10 MULTIPROCESSOR SCHEDULING 167 10.1 Model and Definitions 168 10.2 Mean Field Annealing 170 10.3 Genetic Algorithm 175 10.4 Exploratory Problems 188 11 JOB SHOP SCHEDULING 189 11.1 Types of Schedules 190 11.2 A Genetic Algorithm for JSP 192 11.3 Simulation Results 199 11.4 Exploratory Problems 201 REFERENCES 203 INDEX 219 PREFACE The field of optimization is interdisciplinary in nature, and has been making a significant impact on many disciplines. As a result, it is an indispensable tool for many practitioners in various fields. Conventional optimization techniques have been well established and widely published in many excellent textbooks. However, there are new techniques, such as neural networks, simulated anneal ing, stochastic machines, mean field theory, and genetic algorithms, which have been proven to be effective in solving global optimization problems. This book is intended to provide a technical description on the state-of-the-art development in advanced optimization techniques, specifically heuristic search, neural networks, simulated annealing, stochastic machines, mean field theory, and genetic algorithms, with emphasis on mathematical theory, implementa tion, and practical applications. The text is suitable for a first-year graduate course in electrical and computer engineering, computer science, and opera tional research programs. It may also be used as a reference for practicing engineers, scientists, operational researchers, and other specialists. This book is an outgrowth of a couple of special topic courses that we have been teaching for the past five years. In addition, it includes many results from our inter disciplinary research on the topic. The aforementioned advanced optimization techniques have received increasing attention over the last decade, but relatively few books have been produced. Most of the theory and their applications are widely scattered in journals, technical reports, and conference proceedings of various fields, making it difficult for people new in the field to learn the sub ject. We hope this book will bring together a comprehensive treatment of these techniques, thus filling an existing gap in the scientific literature. The material of the text is structured in a modular fashion, with each chapter reasonably independent of each other. In part I, each chapter covers the basic theory of an optimization technique, and in part II, practical applications of the optimization technique in various domains are presented. The individual chapter can be studied independently or as part of a larger, more comprehensive course. COMPUTATIONAL INTELLIGENCE FOR OPTIMIZATION We are deeply indebted to many graduate students who haven taken our grad uate courses on Advanced Optimization Techniques and Artificial Neural Net works at the New Jersey Institute of Technology during the past five years. In particular, we wish to thank G. Wang, J. Chen, D. Liu, A. Agrawal, Y. Yu, Z. Zhang, A. Arulumbalam, S. Balasekar, J. Li, and N. Sezgin. Their feed backs and comments over the years have helped shape the book into its present form. We are most grateful to L. Fitton for her editorial assistance. We also appreciate the pointers provided by S. Rumsey of Kluwer Academic Publishers in typesetting the manuscript. Last, but not least, we are truly grateful to A. Greene of Kluwer Academic Publishers for his constant encouragement to complete the manuscript. Nirwan Ansan Edwin Hou 1 INTRODUCTION Many scientific and engineering problems can be formulated as a constrained optimization problem described mathematically as min/ex) subject to g(x), (1.1 ) xES where 5 is the solution space, / is the cost function, and g is the set of con straints. Various optimization problems can be cat.egorized based on the char acteristics of 5, /, and g. If / and g are linear functions, then Equation (1.1) describes a linear optimization problem which can be readily solved. Other wise, Equation (1.1) becomes a nonlinear optimization problem which is more difficult to solve. A prime example of a linear optimization problem is the lin ear programming problem where the constraints are in the form of g( x) 2: 0 = or g( x) O. The linear programming problem can be solved by the simplex algorithm [125] where the optimal solution can be found in a finite number of steps. However, many optimization problems encountered in engineering and other fields, such as the traveling salesman problem (TSP), various scheduling problems, etc., belong to a class of "difficult to solve" problems where deter ministic algorithms are not applicable. With the discovery and advances of various new optimization techniques, such as neural networks, simulated annealing, stochastic machines, mean field an nealing, and genetic algorithms, some of the well-defined difficult problems may be solved more effectively. The focus of this book will be on these new optimization techniques and their practical applications. N. Ansari et al., Computational Intelligence for Optimization © Kluwer Academic Publishers 1997