分布式并行遗传算法

ASurveyofParallelDistributedGeneticAlgorithms5.ClassificationofParallelandSequentialGAs6.TechnicalIssuesinParallelDistributedGAs7.ImplementationIssues8.ConcludingRemarksPar.dGARef.YearMainCharacteristicsPGA[55]1987GenerationalislandsonanInteliPSChypercube(8CPUs).Migratethebest.DynamicTop.dGA[68]1989Distributedpopulations.Goodresultswith20%ofpopulationmigrantsevery20generationsGENITORII[73]1990Steady-StateislandswithrankedselectionandreducedsurrogatecrossoverPGA[51]1991Sub-populationsinacircularladder-like2-Dtopology.Migratethebest,localhill-climbingSGA-cube[23]1991MadefornCUBE2.Thisistheparallelextensionofthewell-knownsimpleGAofGoldbergPARAGENESIS---1992MadefortheCM-200.ThisplacesoneindividualineveryCPUPeGAsuS[59]1993TargetedforMIMDmachinesandwritteninaveryhighandflexibledescriptionlanguageGAMAS[56]1994Uses4veryheterogeneousspecies(islands)andquitespecializedmigrationsandgenotypesiiGA[44]1994InjectionislandGAwithhierarchicalheterogeneousnodesandasynchronousmigrationsSP1-GA[42]1994128steady-stateislandsonanIBMSP1machineof128nodes.2-Dtoroidalmesh.mr=1DGENESIS[47]1994Freetopology,flexiblemigration,andpoliciesforselection.Implementedwithsockets(UDP)GALOPPS[30]1996Veryflexible.ImplementedwithPVMandcomprisingalargenumberofoperatorsGDGA[34]1996Synchronous.Simulatedononeprocessor.Generational.UsesFuzzycrossoverandFPgenesCoPDEB[2]1996Everyislandusesitsownprobabilitiesformutation,crossover,andspecializedoperators5.ClassificationofParallelandSequentialGAsTABLEⅢOVERVIEWOFPARALLELDISTRIBUTEDGAsBYYEAR5.ClassificationofParallelandSequentialGAsReferenceApplicationDomain[7]Paralleltrainingofartificialneuralnetworks,fuzzylogiccontrollers,andcommunicationprotocols[19]SynthesisofVLSIcircuits[31]Functionoptimization[42]Setpartitioningproblem[44]Graphpartitioningproblem[49]ConstraintOptimization,reorderingproblems,...[51]Travelingsalespersonproblem(TSP),functionoptimization[53]Distributingthecomputingloadontoasetofprocessingnodes[56]Thefileallocationproblem,XORneuralnetwork,sineenvelopesinewavefunction[66]Systemsmodeling,proteintertiarystructureprediction,andtwo-dimensionalbinpackingproblems[68]Walshpolynomials[72]Optimizationoftheconnectionweightsofneuralnetworks(XOR,bin-adder,...),andfunctionoptimizationTABLEⅣSOMEAPPLICATIONSOFPARALLELDISTRIBUTEDGAs5.ClassificationofParallelandSequentialGAsNewgenotypesandoperatorsarebeingdesignedfordealingwithconstraintproblemsandcombinatorialoptimization.Besidesthat,theimportanceofcellularGAsisalsogrowingduetorecentstudiesininwhichthesearchisstillenhancedduetotheexistenceofneighborhoodlikespatialdispositions.TABLEⅤDETIALSOFSEVELPARALLELGAsParallelGAKindofParallelismTopologyPresentApplicationsASPARAGOSFinegrain.AppliesHill-ClimbingifnoimprovementLadderTSPCoPDEBCoarsegrain.Everysub-pop.appliesdifferentoperatorsFullConnectedFunc.Opt.andANN’sDGENESIS1.0Coarsegrainwithmigrationsamongsub-populationsAnyDesiredFunctionOptimizationECO-GAFinegrain.OneofthefirstofitsclassGridFunctionOptimizationEnGENEerGlobalparallelization(parallelevaluations)Master/SlaveVariousGALOPPS3.1Coarsegrain.AveryportablesoftwareAnyDesiredFunc.Opt.andTransportGAMASCoarsegrain.Uses4speciesofstrings(nodes)FixedHierarchyANN,Func.Opt.,...GAMEParallelversionnotavailableyet.ObjectOrientedAnyDesiredTSP,Func.Opt.,...GAucsd1.2/1.4Distributestheexperimentsoverthenetwork(notparallel)sequentialsameasGENESISGDGACoarseGrain.Admitsexplicitexploration/exploitationHierarchyFunc.Opt.(FP-genes.)GENITORIICoarsegrain.InterestingcrossoveroperatorRingFunc.Opt.andANN’sHSDGAHierarchicalcoarseandfinegrainGA.UsesE.S.Ring,Tree,Star,...FunctionOptimizationPARAGENESISGlobalP.&coarsegrain.MadefortheCM-200(1ind.-1cpu)Localsel.(seq.)FunctionOptimizationPeGAsuSCoarseorfinegrain.High-levelprogramming.MIMDMultipleTeachingandFunc.Opt.PGA2.5Spatiallystructuredselection.AllowsmigrationsMultipleKnapsackandFunc.Opt.PGAPackGlobalparallelization(parallelevaluations)Master/SlaveFunctionOptimizationRPL2Coarseandfinegrain.VeryflexibleandopentonewmodelsAnyDesiredResearchandBusinessSGA-CubeGlobalparallelization.MadeforthenCUBE2HypercubeFunctionOptimization5.ClassificationofParallelandSequentialGAswenowgiveanextensiveclassificationofsequentialandparallelGasintothreemajorcategoriesaccordingtotheirspecificobjectives.ApplicationOriented:Theseareblack-boxsystemsdesignedtohidethedetailsofGAsandhelptheuserindevelopingapplicationsforspecificdomains.Usuallytheyaremenu-driven,andeasilyparameterizable.AlgorithmOriented:Basedonspecificalgorithms.Thesourcecodeisavailableinordertoprovidetheireasyincorporationintonewapplications.Thisclassmaybefurthersub-dividedinto:-AlgorithmSpecific:TheycontainonesingleGA.-AlgorithmLibraries:Theysupportagroupofalgorithmsinalibraryformat.Theyarehighlyparameterizedandcontainmanydifferentoperatorstohelpfutureapplications.ToolKits:TheseareflexibleenvironmentsforprogrammingarangeofdifferentGAsandapplications.Theycanbesub-dividedinto:-Educational:UsedforintroducingGAconceptstonoviceusers.Thebasictech-niquestotrackexecutionsandresultsduringtheevolutionare