Natural Computing Series Series Editors: G. Rozenberg (Managing) Th. Back A.E. Eiben J.N. Kok H.P. Spaink Leiden Center for Natural Computing Advisory Board: S. Amari G. Brassard M. Conrad K.A. De Jong C.C.A.M. Gielen T. Head L. Kari L. Landweber T. Martinetz Z. Michalewicz M.C. Mozer E. Oja G. Paun J. Reif H. Rubin A. Salomaa M. Schoenauer H.-P. Schwefel D. Whitley E. Winfree J.M. Zurada Springer-Verlag Berlin Heidelberg GmbH Hans-Paul Schwefel Ing o Wegener Klaus Weinert (Eds.) Advances in Computational Intelligence Theory and Practice With 91 Figures and 30 Tables Springer Editors Series Editors Prof. Dr. Hans-Paul Schwefel G. Rozenberg (Managing Editor) Universităt Dortmund Th. Băck, A.E. Eiben, J.N. Kok, Fachbereich Informatik H.P. Spaink Lehrstuhl Informatik XI Leiden Center for Natural Computing 44221 Dortmund, Germany Leiden University [email protected] Niels Bohrweg 1 2333 CA Leiden Prof. Dr. Ingo Wegener The Netherlands Universităt Dortmund [email protected] Lehrstuhl Informatik II 44221 Dortmund, Germany [email protected] Prof. Dr. Klaus Weinert Universităt Dortmund Fakultăt Maschinenbau Institut fUr Spannende Fertigung 44221 Dortmund, Germany [email protected] Library of Congress Cataloging-in-Publication Data Advances in computational intelligence: theory and practice/Hans-Paul Schwefel, rngo Wegener, Klaus Weinert (eds.) p. cm. - (Natural computing series) Includes bibliographical references and index. ISBN 978-3-642-07758-6 ISBN 978-3-662-05609-7 (eBook) DOI 10.1007/978-3-662-05609-7 1. Computational intelligence. 1. Schwefel, Hans-Paul. II. Wegener, Ingo. III. Weinert, Klaus, 1943-IV. Series. Q342 .A37 2002 006.3-dc21 2002021693 ACM Computing Classification (1998): El, E2, G.1.6, G.3, G.4, I.2.3, 1.2.8, 1.5.1, J.2, J.6 ISBN 978-3-642-07758-6 This work is subject to copyright. AII rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of iIIustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publicat ion 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 Berlin Heidelberg GmbH. Violations are liable for prosecution under the German Copyright Law. http://www.springer.de © Springer-Verlag Berlin Heidelberg 2003 Originally published by Springer-Verlag Berlin Heidelberg New York in 2003 Softcover reprint ofthe hardcover Ist edition 2003 The use of general descriptive names, trademarks, etc. in this publicat ion 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. Cover Design: KiinkelLopka, Heidelberg Typesetting: Camera ready by the editors Printed on acid-free paper SPIN 10865923 45/3142SR - 5 4 3 2 I O Preface Most authors of this book are, only a few were, members of the Collaborative Research Center De Sonderforschungsbereich Design sign and Management of Complex 'Und Management kornplexeT' tcch Technical Processes and Systems nischeT' PTozesse 'Und Systcme by Means of Comp'Utational Intel md Methoden deT' Cornpv.tational ligence Methods (SFB 531) Intelligence (SFB 531) This interdisciplinary research center was founded at the University of Dortmund in the beginning of 1997, and it is supported by the Deutsche Forsdmngsgemeinschaft (DFG). We arc very grateful for the support from both the DFG and our university. The book contains overviews of recent results of the SFB and, at the same time, provides a good introduction to modern trends in computational intel ligence ( CI). The areas of fu;-;;-;y logic, evolutionary algorithms, and machine learning are discussed by researchers from theoretical and applied computer science, as well as from the disciplines of mechanical engineering, electrical engineering, and chemical engineering. The results presented range in nature from theoretical to applied. They clearly illustrate how theoretical results make their way into real-world applications and how applications guide theo retical research. Altogether, the book reflects our interdisciplinary approach to Cl techniques. This is also the place to thank all those people who have helped behind the scenes, especially when different manuscripts had to be put together into a coherent whole for this publication. We cannot name everyone who helped, but at least Mrs. Gundel Jankord and Maria Bayer working as secretaries for the SFB should be thanked here as well as Lutz Schonemann, the present chid executive officer of the SFB. Last, but not least, we want to thank the <~clitors of this book series and Mrs. lngcborg Mayer, for their excellent collaboration, and Kenneth De Jong for "degermanizing" this preface. April 2002 The board of directors of the SFB 531 H.-P. Schwefel, I. Wegener, and K. Weinert Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Ulrich Hammel, Boris Na-ujoks, Hans-Paul Schwefel 1.1 Computational Intelligence Method:,; . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Parallel Problem Solving from Nature.. . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 On the Development of Computational Intelligence . . . . . . . . . . . . . 3 1.4 State of the Art and Trends in Computational Intelligence . . . . . . . 5 1.5 Goals of the Collaborative Research Center . . . . . . . . . . . . . . . . . . . . 6 1.6 On the Organization of the Chapters of This Book . . . . . . . . . . . . . 8 Part I. Fuzzy Logic 2 Mathematical Foundations of Fuzzy Inference............. 15 Stephan Lehmke, Bernd Reusch, Karl-Heinz Temme, Helmut Thiele 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Structure of Fuzzy Inference Mechanisms . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Interpretation of Fuzzy IF-THEN Rule Ba:,;es U:,;ing Concept:,; of Functional Analy::;is . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 The Generalized Modus Ponens and the Compositional Rule of Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Con:,;tructing Solutions for Fuzzy IF-THEN Rule Bases.......... 22 2.6 Uniqueness of Solutions for Fuzzy IF-THEN Rule Bases . . . . . . . . . 28 2.7 Functional Analytic Properties of Fuzzy Inference Operators..... 29 2.8 Approximate Rea:,;oning with Context-Dependent Fuzzy Sets. . . . . 30 2.9 Approximate Reasoning Under Uncertainty.................... 33 2.10 Axiomatic Characterization of Fuzzy Approximation Operator:,; . . 34 2.11 Algebraic Foundations of Information Granulation. . . . . . . . . . . . . . 36 2.12 Algebraic Foundations of Modeling with Words . . . . . . . . . . . . . . . . 37 2.13 Conclusion:,; and Further Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3 Data-Based Fuzzy Modeling for Complex Applications . . . . 46 Har·ro Kiendl, Peter Krause, Daniel Schauten, Timo Slawinski 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2 Efficient Rule Generation in High-dimensional Search Spaces. . . . . 48 3.3 Interpretable Fuzzy Model:,; with High Accuracy . . . . . . . . . . . . . . . . 58 VIII Contents 3.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4 Fuzzy Modeling to Cope with Ambiguities . . . . . . . . . . . . . . . . 78 Harro Kiendl, Peter Krause, Daniel Schauten, Timo Slawinski 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2 Rating and Reduction of Ambiguities . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.3 Reduction of Ambiguities by Negative Rules . . . . . . . . . . . . . . . . . . . 83 4.4 Resolution of Ambiguities by Defuzzification . . . . . . . . . . . . . . . . . . . 87 4.5 Ambiguity-Based Predesign. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.6 Implicit Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Part II. Evolutionary Algorithms 5 Theory of Evolutionary Algorithms and Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 Stefan Droste, Thomas Jansen, Gunter Rudolph, Hans-Paul Schwefcl, Karsten Tinnefeld, Ingo Wegener 5.1 Introduction ............................................... 107 5.2 A Contribution to the NFL Debate ........................... 109 5.3 On the Analysis of Simple Evolutionary Algorithms ............. 111 5.4 Multiobjective Evolutionary Algorithms ....................... 116 5.5 Populations and Crossover ................................... 119 5.6 Takeover Times and Related Key Measures .................... 123 5.7 Dynarnization and Adaptation ............................... 126 5.8 Metric-Based EA (MBEA) and an Application in GP ........... 130 5.9 Black-box Optimization ..................................... 134 6 Design of Evolutionary Algorithms and Applications in Surface Reconstruction .................................... 145 Thomas Beielstcin, Jorn Mehnen, Lutz Schonernann, Hans Paul Schwefel, Tobias Surrnann, Klaus WeineTt, Dirk Wiesrnann 6.1 Introduction ............................................... 145 6.2 Design of Evolutionary Algorithms ........................... 146 6.3 Evolutionary Algorithms: The General Framework .............. 146 6.4 Design of Evolutionary Algorithms and Integration of Domain Knowledge ................................................ 147 6.5 Structure Optimization and Evolutionary Programming ......... 155 6.6 An Analysis of Threshold Selection in Noisy Environments ...... 161 6. 7 Evolutionary Surface Reconstruction .......................... 165 6.8 Scanning Techniques ........................................ 167 6.9 Point Selection Schemes ..................................... 168 6.10 Surface Reconstruction Using Triangulations ................... 172 Contents IX 6.11 Surface Reconstruction Using Nonuniform Rational B-Splines .... 178 6.12 A Parallel Reconstruction System Using CSG-NURBS Hybrids ... 182 6.13 Parallel Evolution Strategies ................................. 185 6.14 Conclusions ................................................ 187 7 Genetic Programming and Its Application in Machining Technology ................................................ 194 Wo~fqang Banzhaf, Mark·us I3rarneier-, Marc Stautner, Klaus Weiner-t 7.1 Introduction ............................................... 194 7.2 Linear Genetic Programming ................................ 195 7.3 Removal of Non-effective Code ............................... 197 7.4 Graph Interpretation ....................................... 199 7.5 Linear Genetic Operators .................................... 201 7.6 Control of Variation Step Size ................................ 207 7.7 Control of Structural Diversity ............................... 212 7.8 Genetic Programming in Machining Technology ................ 218 7.9 Experimental Setup ........................................ 219 7.10 Gathering Data ............................................ 221 7.11 Tree-Based GP for Symbolic Regression ....................... 224 7.12 Graphical Representation .................................... 229 7.13 Results of the GP Kernel .................................... 231 7.14 Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 7.15 Conclusion ................................................ 237 Part III. Machine Learning and Optimization 8 Novel Learning Tasks, Optimization, and Their Application ......................................... 245 Gnido Daniel, Jan Dienst·uhl, Sebastian Engell, Sven Felske, KaTZ Goser, Ralf Klinkenber:q, Katharina Morik, Oliver Ritthoff, Hcnn!:'-T Schmidt-Traub 8.1 Novel Learning Tasks in Machine Learning .................... 246 8.2 Parameter Estimation for Chromatographic Processes .......... 278 8.3 Classification and Prediction of Device Parameters with Regard to the Quality of Integrated Microelectronic Systems ............ 294 Index ......................................................... 319 1 Introduction Ulrich Hammel1, Boris Naujoks2, and Hans-Paul Schwefer~ 1 NuTech Solutions GmbH, Martin-Schmei13er-Weg 15, 44227 Dortmund, Germany [email protected] 2 University of Dortmund, Department of Computer Science, Inforrnatik XI, 44221 Dortmund, Germany { naujoks, schwefel }CQ)Ls1l.cs. uni-dortmund.de Summary. This introduction aims at helping newcomers to the field of compu tational intelligence (CI) to understand the scope of Cl, to learn about its brief history, and to glimpse neighboring fields, be they well established already or still emerging from within the living system called science. 1.1 Computational Intelligence Methods Fut~:r.y systems, artificial neural networks, and evolutionary computation rderred to as CI methods - have many features in common: • Their basic concepts have been known for a long time and have been surrounded by controversy at times. Orw rem.;on, among others, for the hesitant acceptance of CI methods in the beginning was the lack of suffi cient computational power. Moreover, some resistance within established scientific communities had to be overcome. And finally, as in the case of other new fields, a critical mass of people had to accumulate in order to initiate research at a. visible scale. • They become more and more successful as applications spread into ever broader areas. Similar to other scientific domains, the critical mass in the field of CI first accumulated in applied research. Concrete practical problems exist, and they have to be solved, whether basic research is aware of them or not, and even if somebody proves that the problem at hand is generally unsolvable under certain premises. New methods arc often applied to such problems tentatively at first and dmnonstrate their practical utility without a priori existing formal proof of their applica bility. The observation that it works is sometimes all that is required to stimulate investigations to clarify the why and under which conditions a new method works. • Their theoretical foundations are not complet<). Basic research tends to keep an expectant attitude before it assimilates new methods, the op erability of which is difficult if not impossible to prove. In parts of CI, especially in the domain of fuz:r.y logic, substantial progress in laying its theoretical foundation has already been achieved; a. comprehensive pic ture, however, is still missing. H.-P. Schwefel et al. (eds.), Advances in Computational Intelligence © Springer-Verlag Berlin Heidelberg 2003 2 Hammel et al. • Repeatedly, new and speciali~ed variants of CI methods are created in a trial and error fashion. The main rea::;on for this very inefficient procedure of reinventing the wheel again and again is the lack of an appropriate theoretical basis. • The areas of applications are overlapping. To apply CI methods is reason able only when conventional concept::; fail or when exact solutions gained with such methods are by far too expensive. In these cases, CI methods may lead to good approximations or reasonable probability of success. Furthermore, they can often be applied alternatively. Typical applications are found in nonlinear control, optimi~ation, identification, clas::;ification, image processing, pattern recognition, and decision support, especially when there are multiple, conflicting objectives. • They supplement each other excellently. Sometimes, the application of one CI method results in a new problem, which is also not solvable in a canonical way, but by means of a second CI method. Examples are the combined structure and weight optimization in neural network::;, the pa rameterization and genetic operator selection in evolutionary algorithms, as well as the determination of fuzzy rule sets and appropriate member ship functions. Such tasks can often be tackled by combining different CI methods. At present, such hybridization is typically done in a sequential manner (method A as a pre-processing step for method B). One may :,;peculate that coupling methods with one another more intelligently will increase the overall performance. This holds in particular as soon as the foundations of the different methods are better understood in detail. • They are intermediate steps on a long march. The general goal is to push problem solving algorithms forward into problem classes of increasing complexity. There are many other methods aiming in the same direction, e.g., cellular automata, immune networks, agent systems, possibilistic ap proaches, multivalued logic as well as competitive, cooperative, and self organizing structures. Ideas for uses of CI methods in these areas are expected to continue growing in number. • They were not even mentioned in the 1988 edition of the well-known German encyclopedia Duden Infor-rnatik. The second edition of 1993 con tained already paragraphs on fuzzy logic, neural networks, and genetic algorithms. The latter concerns at least one of the two American variants of the broader class of evolutionary algorithms. Only the third edition of 2001 [7] briefly mentions further variants like evolution strategies and genetic programming. Research establishments have begun to recogni~c the power of CI methods. In industry and economy they have been in use since the early 1970s, and they are just entering worldwide the curricula of computer science.