NadiaNedjah,AjithAbraham,LuizadeMacedoMourelle(Eds.) GeneticSystemsProgramming StudiesinComputationalIntelligence,Volume13 Editor-in-chief Prof.JanuszKacprzyk SystemsResearchInstitute PolishAcademyofSciences ul.Newelska6 01-447Warsaw Poland E-mail:[email protected] Furthervolumesofthisseries Vol.8.SrikantaPatnaik,LakhmiC.Jain, canbefoundonourhomepage: SpyrosG.Tzafestas,GermanoResconi, AmitKonar(Eds.) springer.com InnovationsinRobotMobilityandControl, 2005 Vol.1.TetsuyaHoya ISBN3-540-26892-8 ArtificialMindSystem–KernelMemory Vol.9.TsauYoungLin,SetsuoOhsuga, Approach,2005 Churn-JungLiau,XiaohuaHu(Eds.) ISBN3-540-26072-2 FoundationsandNovelApproachesinData Vol.2.SamanK.Halgamuge,LipoWang Mining,2005 (Eds.) ISBN3-540-28315-3 ComputationalIntelligenceforModelling Vol.10.AndrzejP.Wierzbicki,Yoshiteru andPrediction,2005 Nakamori ISBN3-540-26071-4 CreativeSpace,2005 Vol.3.Boz˙enaKostek ISBN3-540-28458-3 Perception-BasedDataProcessingin Vol.11.AntoniLigêza Acoustics,2005 LogicalFoundationsforRule-Based ISBN3-540-25729-2 Systems,2006 Vol.4.SamanK.Halgamuge,LipoWang ISBN3-540-29117-2 (Eds.) Vol.13.NadiaNedjah,AjithAbraham, ClassificationandClusteringforKnowledge LuizadeMacedoMourelle(Eds.) Discovery,2005 GeneticSystemsProgramming,2006 ISBN3-540-26073-0 ISBN3-540-29849-5 Vol.5.DaRuan,GuoqingChen,EtienneE. Kerre,GeertWets(Eds.) IntelligentDataMining,2005 ISBN3-540-26256-3 Vol.6.TsauYoungLin,SetsuoOhsuga, Churn-JungLiau,XiaohuaHu,Shusaku Tsumoto(Eds.) FoundationsofDataMiningandKnowledge Discovery,2005 ISBN3-540-26257-1 Vol.7.BrunoApolloni,AshishGhosh,Ferda Alpaslan,LakhmiC.Jain,SrikantaPatnaik (Eds.) MachineLearningandRobotPerception, 2005 ISBN3-540-26549-X Nadia Nedjah Ajith Abraham Luiza de Macedo Mourelle (Eds.) Genetic Systems Programming Theory and Experiences ABC Dr.NadiaNedjah Dr.AjithAbraham Dr.LuizadeMacedoMourelle SchoolforComputerScience and,Engineering FaculdadedeEngenharia Chung-AngUniversity UniversidadedoEstado Heukseok-dong221 doRiodeJaneiro 156-756Seoul,Korea RuaSa˜oFranciscoXavier Republicof(SouthKorea) 524,20550-900Maracana˜,RiodeJaneiro E-mail:[email protected] Brazil E-mail:[email protected] LibraryofCongressControlNumber:2005936350 ISSNprintedition:1860-949X ISSNelectronicedition:1860-9503 ISBN-10 3-540-29849-5SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-29849-6SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation,broadcasting, reproductiononmicrofilmorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9, 1965,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsare liableforprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com (cid:1)c Springer-VerlagBerlinHeidelberg2006 PrintedinTheNetherlands Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply, evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelaws andregulationsandthereforefreeforgeneraluse. Typesetting:bytheauthorsandTechBooksusingaSpringerLATEXmacropackage Printedonacid-freepaper SPIN:11521433 89/TechBooks 543210 Foreword The editors of this volume, Nadia Nedjah, Ajith Abraham and Luiza de Macedo Mourelle, have done a superb job of assembling some of the most innovative and intriguing applications and additions to the methodology and theory of genetic programming – an automatic programming technique that startsfromahigh-levelstatementofwhatneedstobedoneandautomatically creates a computer program to solve the problem. Whenthegeneticalgorithmfirstappearedinthe1960sand1970s,itwasan academiccuriositythatwasprimarilyusefulinunderstandingcertainaspects ofhowevolutionworkedinnature.Inthe1980s,intandemwiththeincreased availability of computing power, practical applications of genetic and evolu- tionary computation first began to appear in specialized fields. In the 1990s, the relentless iteration of Moore’s law – which tracks the 100-fold increase in computational power every 10 years – enabled genetic and evolutionary computationtodeliverthefirstresultsthatwerecomparableandcompetitive with the work of creative humans. As can be seen from the preface and table of contents, the field has already begun the 21st century with a cornucopia ofapplications, aswellasadditions tothemethodology andtheory,including applicationstoinformationsecuritysystems,compilers,dataminingsystems, stock market prediction systems, robotics, and automatic programming. Looking forward three decades, there will be a 1,000,000-fold increase in computationalpower.Giventheimpressivehuman-competitiveresultsalready delivered by genetic programming and other techniques of evolutionary com- putation, the best is yet to come. September 2005 Professor John R. Koza Preface Designing complex programs such as operating systems, compilers, filing sys- tems, data base systems, etc. is an old ever lasting research area. Genetic programmingisarelativelynewpromisingandgrowingresearcharea.Among other uses, it provides efficient tools to deal with hard problems by evolving creativeand competitive solutions.SystemsProgramming isgenerally strewn with such hard problems. This book is devoted to reporting innovative and significantprogressaboutthecontributionofgeneticprogramminginsystems programming.Thecontributionsofthisbookclearlydemonstratethatgenetic programming is very effective in solving hard and yet-open problems in sys- tems programming. Followed by an introductory chapter, in the remaining contributedchapters,thereadercaneasilylearnaboutsystemswheregenetic programming can be applied successfully. These include but are not limited to, information security systems (see Chapter 3), compilers (see Chapter 4), data mining systems (see Chapter 5), stock market prediction systems (see Chapter6),robots(seeChapter8)andautomaticprogramming(seeChapters 7 and 9). In Chapter 1, which is entitled Evolutionary Computation: from Genetic Algorithms to Genetic Programming, the authors introduce and review the development of the field of evolutionary computations from standard genetic algorithmstogeneticprogramming,passingbyevolutionstrategiesandevolu- tionary programming. The main differences among the different evolutionary computation techniques are also illustrated in this Chapter. In Chapter 2, which is entitled Automatically Defined Functions in Gene Expression Programming, the author introduces the cellular system of Gene Expression Programming with Automatically Defined Functions (ADF) and discusses the importance of ADFs in Automatic Programming by compar- ing the performance of sophisticated learning systems with ADFs with much simpler ones without ADFs on a benchmark problem of symbolic regression. VIII Preface In Chapter 3, which is entitled Evolving Intrusion Detection Systems, the authorspresentanIntrusionDetectionSystem(IDS),whichisaprogramthat analyzeswhathappensorhashappenedduringanexecutionandtriestofind indications that the computer has been misused. An IDS does not eliminate theuseofpreventivemechanismbutitworksasthelastdefensivemechanism in securing the system. The authors also evaluate the performances of two Genetic Programming techniques for IDS namely Linear Genetic Program- ming (LGP) and Multi-Expression Programming (MEP). They compare the obtained results with some machine learning techniques like Support Vector Machines (SVM) and Decision Trees (DT). The authors claim that empiri- cal results clearly show that GP techniques could play an important role in designing real time intrusion detection systems. In Chapter 4, which is entitled Evolutionary Pattern Matching Using Ge- netic Programming,theauthorsapplyGPtothehardproblemofengineering pattern matching automata for non-sequential pattern set, which is almost always the case in functional programming. They engineer good traversal or- dersthatallowonetodesignanefficientadaptive pattern-matchersthatvisit necessary positions only. The authors claim that doing so the evolved pat- tern matching automata improves time and space requirements of pattern- matching as well as the termination properties of term evaluation. In Chapter 5, which is entitled Genetic Programming in Data Modelling, theauthordemonstratessomeabilitiesofGeneticProgramming(GP)inData Modelling (DM). The author shows that GP can make data collected in large databasesmoreusefulandunderstandable.Theauthorconcentratesonmath- ematical modelling, classification, prediction and modelling of time series. InChapter6,whichisentitledStock Market Modeling Using Genetic Pro- gramming Ensembles, the authors introduce and use two Genetic Program- ming(GP)techniques:Multi-ExpressionProgramming(MEP)andLinearGe- netic Programming (LGP) for the prediction of two stock indices. They com- pare the performance of the GP techniques with an artificial neural network trainedusingLevenberg-MarquardtalgorithmandTakagi-Sugenoneuro-fuzzy model. As a case study, the authors consider Nasdaq-100 index of Nasdaq Stock Market and the S&P CNX NIFTY stock index as test data. Based on the empirical results obtained the authors conclude that Genetic Program- ming techniques are promising methods for stock prediction. Finally, they formulate an ensemble of these two techniques using a multiobjective evolu- tionaryalgorithmandclaimthatresultsreachedbyensembleofGPtechniques are better than the results obtained by each GP technique individually. In Chapter 7, which is entitled Evolutionary Digital Circuit Design Us- ing Genetic Programming, the authors study two different circuit encodings used for digital circuit evolution. The first approach is based on genetic pro- gramming, wherein digital circuits consist of their data flow based specifica- tions. In this approach, individuals are internally represented by the abstract trees/DAGofthecorrespondingcircuitspecifications.Inthesecondapproach, digital circuits are thought of as a map of rooted gates. So individuals are Preface IX represented by two-dimensional arrays of cells. The authors compare the im- pact of both individual representations on the evolution process of digital circuits. The authors reach the conclusion that employing either of these ap- proaches yields circuits of almost the same characteristics in terms of space and response time. However, the evolutionary process is much shorter with the second linear encoding. InChapter8,whichisentitledEvolving Complex Robotic Behaviors Using GeneticProgramming,theauthorreviewsdifferentmethodsforevolvingcom- plex robotic behaviors. The methods surveyed use two different approaches: The first one introduces hierarchy into GP by using library of procedures or new primitive functions and the second one uses GP to evolve the build- ing modules of robot controller hierarchy. The author comments on including practicalissuesofevolutionaswellascomparisonbetweenthetwoapproaches. InChapter9,whichisentitledAutomaticSynthesisofMicrocontrollerAs- sembly Code Through Linear Genetic Programming, the authors focus on the potential of linear genetic programming in the automatic synthesis of micro- controller assembly language programs. For them, these programs implement strategies for time-optimal or sub-optimal control of the system to be con- trolled, based on mathematical modeling through dynamic equations. They also believe that within this application class, the best model is the one used in linear genetic programming, in which each chromosome is represented by aninstructionlist.Theauthorsfindthesynthesisofprogramsthatimplement optimal-time control strategies for microcontrollers, directly in assembly lan- guage, as an attractive alternative that overcomes the difficulties presented by the conventional design of optimal control systems. This chapter widens the perspective of broad usage of genetic programming in automatic control. We are very much grateful to the authors of this volume and to the re- viewers for their tremendous service by critically reviewing the chapters. The editors would like also to thank Prof. Janusz Kacprzyk, the editor-in-chief of the Studies in Computational Intelligence Book Series and Dr. Thomas Ditzinger,SpringerVerlag,Germanyfortheeditorialassistanceandexcellent cooperative collaboration to produce this important scientific work. We hope that the reader will share our excitement to present this volume on Genetic Systems Programming and will find it useful. Brazil Nadia Nedjah August 2005 Ajith Abraham Luiza M. Mourelle Contents 1 Evolutionary Computation: from Genetic Algorithms to Genetic Programming Ajith Abraham, Nadia Nedjah, Luiza de Macedo Mourelle ............. 1 1.1 Introduction ............................................... 2 1.1.1Advantages of Evolutionary Algorithms................... 3 1.2 Genetic Algorithms ......................................... 3 1.2.1Encoding and Decoding................................. 4 1.2.2Schema Theorem and Selection Strategies................. 5 1.2.3Reproduction Operators ................................ 6 1.3 Evolution Strategies ........................................ 9 1.3.1Mutation in Evolution Strategies......................... 9 1.3.2Crossover (Recombination) in Evolution Strategies ......... 10 1.3.3Controling the Evolution................................ 10 1.4 Evolutionary Programming .................................. 11 1.5 Genetic Programming....................................... 12 1.5.1Computer Program Encoding............................ 13 1.5.2Reproduction of Computer Programs..................... 14 1.6 Variants of Genetic Programming............................. 15 1.6.1Linear Genetic Programming ............................ 16 1.6.2Gene Expression Programming (GEP).................... 16 1.6.3Multi Expression Programming .......................... 17 1.6.4Cartesian Genetic Programming ......................... 18 1.6.5Traceless Genetic Programming ( TGP) .................. 18 1.6.6Grammatical Evolution ................................. 19 1.6.7Genetic Algorithm for Deriving Software (GADS) .......... 19 1.7 Summary.................................................. 19 References ...................................................... 19 XII Contents 2 Automatically Defined Functions in Gene Expression Programming Caˆndida Ferreira................................................. 21 2.1 Genetic Algorithms: Historical Background .................... 21 2.1.1Genetic Algorithms .................................... 22 2.1.2Genetic Programming .................................. 22 2.1.3Gene Expression Programming .......................... 25 2.2 The Architecture of GEP Individuals.......................... 27 2.2.1Open Reading Frames and Genes ........................ 28 2.2.2Structural Organization of Genes ........................ 30 2.2.3Multigenic Chromosomes and Linking Functions ........... 32 2.3 Chromosome Domains and Random Numerical Constants............................ 33 2.4 Cells and the Creation of Automatically Defined Functions ........................... 36 2.4.1Homeotic Genes and the Cellular System of GEP .......... 37 2.4.2Multicellular Systems................................... 37 2.4.3Incorporating Random Numerical Constants in ADFs ...... 39 2.5 Analyzing the Importance of ADFs in Automatic Programming .................................. 40 2.5.1General Settings ....................................... 40 2.5.2Results without ADFs .................................. 42 2.5.3Results with ADFs..................................... 46 2.6 Summary.................................................. 54 References ...................................................... 55 3 Evolving Intrusion Detection Systems Ajith Abraham, Crina Grosan ..................................... 57 3.1 Introduction ............................................... 57 3.2 Intrusion Detection ......................................... 58 3.3 Related Research ........................................... 60 3.4 Evolving IDS Using Genetic Programming (GP)................ 63 3.4.1Linear Genetic Programming (LGP)...................... 63 3.4.2Multi Expression Programming (MEP) ................... 64 3.4.3Solution Representation................................. 64 3.4.4Fitness Assignment .................................... 66 3.5 Machine Learning Techniques ................................ 66 3.5.1Decision Trees ......................................... 67 3.5.2Support Vector Machines (SVMs)........................ 67 3.6 Experiment Setup and Results ............................... 68 3.7 Conclusions................................................ 77 References ...................................................... 77