GabrielLuqueandEnriqueAlba ParallelGeneticAlgorithms StudiesinComputationalIntelligence,Volume367 Editor-in-Chief Prof.JanuszKacprzyk SystemsResearchInstitute PolishAcademyofSciences ul.Newelska6 01-447Warsaw Poland E-mail:[email protected] Furthervolumesofthisseriescanbefoundonour Vol.357.NadiaNedjah,LeandroSantosCoelho, homepage:springer.com VivianaCoccoMariani,andLuizadeMacedoMourelle(Eds.) InnovativeComputingMethodsandtheirApplicationsto Vol.346.WeisiLin,DachengTao,JanuszKacprzyk,ZhuLi, EngineeringProblems,2011 EbroulIzquierdo,andHaohongWang(Eds.) ISBN978-3-642-20957-4 MultimediaAnalysis,ProcessingandCommunications,2011 ISBN978-3-642-19550-1 Vol.358.NorbertJankowski,W(cid:2)lodzis(cid:2)lawDuch,and KrzysztofGra¸bczewski(Eds.) Vol.347.SvenHelmer,AlexandraPoulovassilis,and Meta-LearninginComputationalIntelligence,2011 FatosXhafa ISBN978-3-642-20979-6 ReasoninginEvent-BasedDistributedSystems,2011 ISBN978-3-642-19723-9 Vol.359.Xin-SheYang,andSlawomirKoziel(Eds.) Vol.348.BeniaminoMurgante,GiuseppeBorruso,and ComputationalOptimizationandApplicationsin AlessandraLapucci(Eds.) EngineeringandIndustry,2011 Geocomputation,SustainabilityandEnvironmental ISBN978-3-642-20985-7 Planning,2011 ISBN978-3-642-19732-1 Vol.360.MikhailMoshkovandBeataZielosko CombinatorialMachineLearning,2011 Vol.349.VitorR.Carvalho ISBN978-3-642-20994-9 ModelingIntentioninEmail,2011 ISBN978-3-642-19955-4 Vol.361.VincenzoPallotta,AlessandroSoro,and Vol.350.ThanasisDaradoumis,SantiCaballe´, EloisaVargiu(Eds.) AngelA.Juan,andFatosXhafa(Eds.) AdvancesinDistributedAgent-BasedRetrievalTools,2011 Technology-EnhancedSystemsandToolsforCollaborative ISBN978-3-642-21383-0 LearningScaffolding,2011 Vol.362.PascalBouvry,HoracioGonzález-Vélez,and ISBN978-3-642-19813-7 JoannaKolodziej(Eds.) Vol.351.NgocThanhNguyen,BogdanTrawin´ski,and IntelligentDecisionSystemsinLarge-ScaleDistributed JasonJ.Jung(Eds.) Environments,2011 NewChallengesforIntelligentInformationandDatabase ISBN978-3-642-21270-3 Systems,2011 ISBN978-3-642-19952-3 Vol.363.KishanG.Mehrotra,ChilukuriMohan,JaeC.Oh, PramodK.Varshney,andMoonisAli(Eds.) Vol.352.NikBessisandFatosXhafa(Eds.) DevelopingConceptsinAppliedIntelligence,2011 NextGenerationDataTechnologiesforCollective ISBN978-3-642-21331-1 ComputationalIntelligence,2011 ISBN978-3-642-20343-5 Vol.364.RogerLee(Ed.) Vol.353.IgorAizenberg ComputerandInformationScience,2011 Complex-ValuedNeuralNetworkswithMulti-Valued ISBN978-3-642-21377-9 Neurons,2011 ISBN978-3-642-20352-7 Vol.365.RogerLee(Ed.) Computers,Networks,Systems,andIndustrial Vol.354.LjupcoKocarevandShiguoLian(Eds.) Engineering2011,2011 Chaos-BasedCryptography,2011 ISBN978-3-642-21374-8 ISBN978-3-642-20541-5 Vol.355.YanMengandYaochuJin(Eds.) Vol.366.MarioKöppen,GeraldSchaefer,and Bio-InspiredSelf-OrganizingRoboticSystems,2011 AjithAbraham(Eds.) ISBN978-3-642-20759-4 IntelligentComputationalOptimizationinEngineering,2011 ISBN978-3-642-21704-3 Vol.356.SlawomirKozielandXin-SheYang (Eds.) Vol.367.GabrielLuqueandEnriqueAlba ComputationalOptimization,MethodsandAlgorithms,2011 ParallelGeneticAlgorithms,2011 ISBN978-3-642-20858-4 ISBN978-3-642-22083-8 Gabriel Luque and EnriqueAlba Parallel Genetic Algorithms Theory and Real World Applications 123 Authors Dr.GabrielLuque Prof.EnriqueAlba E.T.S.I.Informática E.T.S.I.Informática UniversityofMálaga UniversityofMálaga CampusdeTeatinos CampusdeTeatinos 29071Málaga 29071Málaga Spain Spain Email:[email protected] Email:[email protected] ISBN 978-3-642-22083-8 e-ISBN978-3-642-22084-5 DOI 10.1007/978-3-642-22084-5 Studiesin Computational Intelligence ISSN1860-949X Library of Congress Control Number:2011930858 (cid:2)c 2011 Springer-VerlagBerlin Heidelberg Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpart of the material is concerned, specifically therights of translation, reprinting,reuse ofillustrations, recitation,broadcasting, reproductiononmicrofilmorinanyother way, and storage in data banks. Duplication of this publication or parts thereof is permittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution undertheGerman Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication 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. Typeset&CoverDesign:ScientificPublishing ServicesPvt. Ltd., Chennai, India. Printed on acid-free paper 9 8 7 6 5 4 3 2 1 springer.com To my family Gabriel Luque To my family, for their continuous support Enrique Alba Preface Thisbookistheresultofseveralyearsofresearchtryingtobettercharacterize parallelgeneticalgorithms(pGAs)asapowerfultoolforoptimization,search, and learning. Wehereofferapresentationstructuredinthreeparts.Thefirstoneistar- getedtothealgorithmsthemselves,discussingtheircomponents,thephysical parallelism, and best practices in using and evaluating them. A second part deals with theoretical results relevant to the research with pGAs. Here we stress several issues related to actual and common pGAs. A final third part offers a very wide study of pGAs as problem solvers, addressing domains such as natural language processing, circuits design, scheduling, and genomics. With such a diverse analysis, we intend to show the big success of these techniques in Science and Industry. We hope this book will be helpful both for researchers and practitioners. The first part shows pGAs to either beginners or researchers looking for a unified view of the field. The second part partially solves (and also opens) new investigation lines in theory of pGAs. The third part can be accessed independently for readers interested in those applications. A small note on MALLBA, one of our software libraries for parallel GAs is also included to ease laboratorypractices and actual applications. We hope the readerwill enjoy the contents as muchwe did in writing this book. Ma´laga, Gabriel Luque May 2010 Enrique Alba Contents Part I: Introduction 1 Introduction............................................. 3 1.1 Optimization ......................................... 4 1.2 Metaheuritics ......................................... 5 1.3 Evolutionary Algorithms ............................... 7 1.4 Decentralized Genetic Algorithms ....................... 10 1.5 Conclusions........................................... 12 2 Parallel Models for Genetic Algorithms.................. 15 2.1 Panmictic Genetic Algorithms .......................... 17 2.2 Structured Genetic Algorithms.......................... 18 2.3 ParallelGenetic Algorithms............................. 19 2.3.1 ParallelModels ................................. 20 2.3.2 A Brief Survey on ParallelGAs ................... 23 2.3.3 New Trends in pGAs ............................ 25 2.4 First Experimental Results ............................. 26 2.4.1 MAXSAT Problem .............................. 26 2.4.2 Analysis of Results .............................. 27 2.5 Summary............................................. 29 3 Best Practices in Reporting Results with Parallel Genetic Algorithms...................................... 31 3.1 ParallelPerformanceMeasures .......................... 32 3.1.1 Speedup ....................................... 32 3.1.2 Other ParallelMeasures.......................... 36 3.2 How to Report Results in pGAs......................... 37 3.2.1 Experimentation ................................ 37 3.2.2 Measuring Performance .......................... 39 3.2.3 Quality of the Solutions .......................... 39 3.2.4 Computational Effort ............................ 40 X Contents 3.2.5 Statistical Analysis .............................. 41 3.2.6 Reporting Results ............................... 42 3.3 Inadequate Utilization of ParallelMetrics................. 43 3.4 Illustrating the Influence of Measures .................... 45 3.4.1 Example 1: On the Absence of Information ......... 46 3.4.2 Example 2: Relaxing the Optimum Helps........... 47 3.4.3 Example 3: Clear Conclusions do Exist............. 48 3.4.4 Example 4: Meaningfulness Does Not Mean Clear Superiority ..................................... 48 3.4.5 Example 5: Speedup: Avoid Comparing Apples against Oranges................................. 49 3.4.6 Example6:APredefinedEffortCouldHinderClear Conclusions..................................... 50 3.5 Conclusions........................................... 51 Part II: Characterization of Parallel Genetic Algorithms 4 Theoretical Models of Selection Pressure for Distributed GAs......................................... 55 4.1 Existing Theoretical Models ............................ 57 4.1.1 The Logistic Model.............................. 57 4.1.2 The Hypergraph Model .......................... 57 4.1.3 Other Models................................... 58 4.2 Analyzed Models ...................................... 59 4.3 Effects of the Migration Policy on the Actual Growth Curves ............................................... 60 4.3.1 Parameters ..................................... 61 4.3.2 Migration Topology.............................. 61 4.3.3 Migration Frequency............................. 63 4.3.4 Migration Rate ................................. 64 4.3.5 Analysis of the Results........................... 65 4.4 Takeover Time Analysis ................................ 68 4.5 Conclusions........................................... 71 Part III: Applications of Parallel Genetic Algorithms 5 Natural Language Tagging with Parallel Genetic Algorithms...................................... 75 5.1 Statistical Tagging..................................... 77 5.2 Automatic Tagging with Metaheuristics .................. 79 5.2.1 Genetic Algorithm............................... 79 5.2.2 CHC Algorithm................................. 80 5.2.3 Simulated Annealing............................. 80 5.2.4 ParallelVersions ................................ 80 Contents XI 5.3 Algorithm Decisions: Representation, Evaluation, and Operators ............................................ 81 5.3.1 Individuals ..................................... 81 5.3.2 Fitness Evaluation............................... 82 5.3.3 Genetic Operators............................... 82 5.4 Experimental Design and Analysis....................... 83 5.5 Conclusions........................................... 89 6 Design of Combinational Logic Circuits.................. 91 6.1 Problem Definition .................................... 92 6.2 Encoding Solutions into Strings ......................... 94 6.3 Related Works ........................................ 97 6.4 Sequential, Parallel,and Hybrid Approaches .............. 97 6.5 Computational Experiments and Analysis of Their Results............................................... 102 6.5.1 Case Study 1: Sasao ............................. 104 6.5.2 Case Study 2: Catherine ......................... 106 6.5.3 Case Study 3: Katz 1 ............................ 108 6.5.4 Case Study 4: 2-Bit Multiplier .................... 109 6.5.5 Case Study 5: Katz 2 ............................ 110 6.6 OverallDiscussion..................................... 113 6.7 Conclusions and Future Work........................... 114 7 Parallel Genetic Algorithm for the Workforce Planning Problem ................................................. 115 7.1 The Workforce Planning Problem ....................... 116 7.2 Design of a Genetic Algorithm .......................... 118 7.2.1 Solution Encoding............................... 118 7.2.2 Evaluation the Quality of a Solution ............... 119 7.2.3 Repairing/ImprovingOperator.................... 120 7.2.4 Recombination Operator ......................... 120 7.2.5 Mutation Operator .............................. 122 7.2.6 The ProposedParallelGA........................ 122 7.3 Scatter Search ........................................ 123 7.3.1 Seeding the Initial Population..................... 124 7.3.2 Improvement Method ............................ 124 7.3.3 ParallelSS ..................................... 125 7.4 Computational Experiments and Analysis of Results ....... 125 7.4.1 Problem Instances............................... 126 7.4.2 Results: Workforce Planning Performance .......... 126 7.4.3 Results: Computational Times .................... 129 7.4.4 A ParallelHybrid GA............................ 132 7.5 Conclusions........................................... 134