Foundations of Generic Optimization MATHEMATICAL MODELLING: Theory and Applications VOLUME 20 This series is aimed at publishing work dealing with the definition, development and application of fundamental theory and methodolo gy, computational and al gorithmic implementations and comprehensive empirical studies in mathematical modelling. Work on new mathematics inspired by the construction of mathematical models, combining theory and experiment and furthering the understanding of the systems being modelled are particularly welcomed. Manuscripts to be considered for publication lie within the following, non-exhaustive list of areas: mathematical modelling in engineering, industrial mathematics, control theory, operations research, decision theory, economic modelling, mathematical programmering, mathematical system theory, geophysical sciences, climate modelling, environmental processes, mathematical modelling in psychology, political science, sociology and behavioural sciences, mathematical biology, mathematical ecology, image process ing, computer vision, artificial intelligence, fuzzy systems, and approximate reasoning, genetic algorithms, neural networ ks, expert s ystems, pattern recognition, clustering, chaos and fractals. Original monographs, comprehensive surveys as well as edited collections will be considered for publication. Editor: R. Lowen (Antwerp, Belgium) Editorial Board: J.-P. Aubin (Université de Paris IX, France) E. Jouini (Université Paris IX - Dauphine, France ) G.J. Klir (New York, U.S.A.) P.G. Mezey (Saskatchewan, Canada) F. Pfeiffer (München, Germany) A. Stevens (Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany) H.-J. Zimmerman (Aachen, Germany) The titles published in this series are listed at the end of this volume. Foundations of Generic Optimization Volume 1: A Combinatorial Approach to Epistasis by M. Iglesias Universidade da Coruña, A Co r u ñ Sap, a i n B . N a u d t s Un i v e r s i t e i t pAenn t, w e r An t w e r p e ng,i uBme l A . V e r s c h o r e n Un i v e r s i t e i t pAenn t, w e r An t w e r p e ng,i uBme l and C . V i d a l Un i v e r s i d a d e d a, C o r u ñ a A Co r u ñ Sap, a i n e di t de by R . L o w e n a n d A . V e r s c h o r e n U n i v e r s iAtnetiwt e r p e n , A n t w e r p e ng,i uBme l A C.I.P. Catalogue record for this book is available from the Library of Congress. ISBN-10 1-4020-3666-3 (HB) ISBN-13 978-1-4020-3666-8 (HB) ISBN-10 1-4020-3665-5 (e-book) ISBN-13 978-1-4020-3665-1 (e-book) Published by Springer, P.O. Box 17, 3300 AA Dordrecht, The Netherlands. www.springeronline.com Printed on acid-free paper All Rights Reserved © 2005 Springer No part of this work may be reproduced, stored in a retrieval s ystem, or transmitted in any form or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written permission from the Publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exc lusive use by the purchaser of the work. Printed in the Netherlands. Do or do not – there is no try (Yoda, The Empire Strikes Back) Preface This book deals with combinatorial aspects of epistasis, a notion that existed for years in genetics and appeared in the field of evolutionary algorithms in the early 1990s. Even though the first chapter puts epistasis in the perspective of evolutionary algorithms and artificial intelligence, and applications occasionally pop up in other chapters, this book is essentially about mathematics, about combinatorial techniques to compute in an efficient and mathematically elegant way what will be defined as normalized epistasis. Some of the material in this book finds its origin in the PhD theses of Hugo Van Hove [97] and Dominique Suys [95]. The sixth chapter also contains material that appeared in the dissertation of Luk Schoofs [84]. Together with that of M. Teresa Iglesias [36], these dissertations form the backbone of a decade of mathematical ventures in the world of epistasis. The authors wish to acknowledge support from the Flemish Fund of Scientific re- search (FWO-Vlaanderen) and of the Xunta de Galicia. They also wish to explicitly mention the intellectual and moral support they received throughout the preparation of this work from their family and their colleagues Emilio Villanueva, Jose Mar´a Barja and Arnold Beckelheimer, as well as our local TEXpert Jan Adriaenssens. Contents O Genetic algorithms: a guide for absolute beginners 1 I Evolutionary algorithms and their theory 21 1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 The GA in detail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Describing the GA dynamics . . . . . . . . . . . . . . . . . . . . . . . 29 4 rosTfGoloAngi.sde........................... 13 5 On the role of toy problems. . . . . . . . . . . . . . . . . . . . . . . . . 33 5.1 Flat fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.2 One needle, two needles . . . . . . . . . . . . . . . . . . . . . 34 5.3 Unitation functions . . . . . . . . . . . . . . . . . . . . . . . . 36 5.4 nosyinutdnelcfi.rf.C-r.evos.sor............... 83 6 . . . and more serious search problems . . . . . . . . . . . . . . . . . . 44 7 Anomeiboltpyrocrffitdiedpiu.rplrc................. 4 6 7.1 noitalenacr.trosc.d–is.snet.Fi............... 4 6 7.2 nositIcar.ent........................... 4 7 7.3 The epistasis measure ...................... 49 II Epistasis 51 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2 Vnosiuostfiidneira............................ 25 x Contents 2.1 Epistasis variance . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.2 Normalized epistasis variance . . . . . . . . . . . . . . . . . . 54 2.3 noitaElesro.cipsa.ts.i.................... 5 5 3 Matrix formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.1 The matrices Gℓ and Eℓ ..................... 5 5 3.2 The rank of the matrix Gℓ .................... 60 4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5 Extreme values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.1 The minimal value of normalized epistasis . . . . . . . . . . . 65 5.2 The maximal value of normalized epistasis . . . . . . . . . . . 71 IIIExamples 77 1 Royal Road functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 1.1 Generalized Royal Road functions of type I . . . . . . . . . . . 78 1.2 Generalized Royal Road functions of type II .......... 87 1.3 sStmoumlselaei.ntrexpre................... 9 2 2 nosUnoiutnic.tfat.ni.......................... 93 2.1 seiGt.i.larne.e......................... 9 3 2.2 noixmMtaroiulfr.ta....................... 94 2.3 The epistasis of a unitation function . . . . . . . . . . . . . . 95 2.4 The matrix Bℓ .......................... 96 2.5 Experimental results . . . . . . . . . . . . . . . . . . . . . . . 100 3 Template functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.1 Basic properties . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.2 Epistasis of template functions . . . . . . . . . . . . . . . . . . 110 3.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . 116 IV Walsh transforms 119 1 The Walsh transform . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 1.1 Walsh functions . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Contents xi 1.2 Properties of Walsh functions . . . . . . . . . . . . . . . . . . 121 1.3 The Walsh matrix . . . . . . . . . . . . . . . . . . . . . . . . . 124 2 Link with schema averages . . . . . . . . . . . . . . . . . . . . . . . . 127 3 Link with partition coefficients . . . . . . . . . . . . . . . . . . . . . . 132 4 Link with epistasis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 5.1 Some first, easy examples . . . . . . . . . . . . . . . . . . . . 141 5.2 A dmenostaecxmraoi:meoemecuetintactpflpl.......541 6 Minimal epistasis and Walsh coefficients . . . . . . . . . . . . . . . . 151 V Multary epistasis 155 1 Multary representations . . . . . . . . . . . . . . . . . . . . . . . . . 155 2 Epistasis in the multary case . . . . . . . . . . . . . . . . . . . . . . . 157 2.1 The epistasis value of a function . . . . . . . . . . . . . . . . . 158 2.2 Matrix representation . . . . . . . . . . . . . . . . . . . . . . . 158 2.3 Comparing epistasis . ...................... 166 3 Extreme values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 3.1 Minimal epistasis . . . . . . . . . . . . . . . . . . . . . . . . . 169 3.2 Msi.samts.xailapie.......................71 2 4 Example: Generalized unitation functions . . . . . . . . . . . . . . . 181 4.1 Normalized epistasis . . . . . . . . . . . . . . . . . . . . . . . 182 4.2 Extreme values of normalized epistasis . . . . . . . . . . . . . 196 VI Generalized Walsh transforms 205 1 Generalized Walsh transforms . . . . . . . . . . . . . . . . . . . . . . 205 1.1 First generalization to the multary case . . . . . . . . . . . . . 206 1.2 noioStatzhetyinoradmectesalacrunleg...........12 8 2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 2.1 Minimal epistasis . . . . . . . . . . . . . . . . . . . . . . . . . 225 2.2 Generalized camel functions . . . . . . . . . . . . . . . . . . . 228 xii Contents 2.3 Generalized unitation functions . . . . . . . . . . . . . . . . . 229 2.4 Snosnodceirutdnecro.f.....................32 1 3 Odsnadndes ..............................2 36 3.1 Notations and terminology . . . . . . . . . . . . . . . . . . . . 237 3.2 Bdenacumlasmerohest .....................2 37 3.3 Partition coefficients revisited . . . . . . . . . . . . . . . . . . 239 3.4 Application: moments of schemata and fitness function . . . . 242 3.5 ysronracno:AbfuimCistaSPscmsiy.taraplt.s......42 A The schema theorem (variations on a theme) 249 1 A Fuzzy Schema Theorem . . . . . . . . . . . . . . . . . . . . . . . . 250 2 The schema theorem on measure spaces . . . . . . . . . . . . . . . . . 255 B Algebraic background 261 1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 1.1 seiGt.i.larne.e.........................62 1 1.2 secblmiIirtar.env.......................2 65 1.3 sesdGerzenvila.rne......................2 67 2 Vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 2.1 seiGt.i.larne.e.........................2 68 2.2 Linear independence, generators and bases . . . . . . . . . . . 269 2.3 Euclidean spaces . . . . . . . . . . . . . . . . . . . . . . . . . 273 3 Lranemipas................................572 3.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . 275 3.2 Linear maps and matrices . . . . . . . . . . . . . . . . . . . . 276 3.3 Orthogonal projections . . . . . . . . . . . . . . . . . . . . . . 277 4 Diagonalization . . . ...........................2 78 4.1 Eigenvalues and eigenvectors . . . . . . . . . . . . . . . . . . . 278 4.2 Diagonalizable matrices . ....................2 80