遗传算法的并行处理分析

194200412JOURNALOFSOUTHWESTUNIVERSITYOFSCIENCEANDTECHNOLOGYVol.19No.4Dec.2004收稿日期:2004-06-15李涛1罗瑜2(1.达县师范高等专科学校计科系四川达州635000;2.西南交通大学计算机与通信工程学院四川成都610031):随着高性能计算机与网络的发展,将遗传算法与并行处理相结合,可大大提高遗传算法的执行效率分析了遗传算法并行化的动因和实现模型:遗传算法并行计算:TP301.6:A:16718755(2004)04002706AnalysisforParallelProcessofGeneticAlgorithmsLiTao1,YuoYu2(1.DaxianTeachersCollege,Dazhou635000,Sichuan,China;2.SouthwestJiaotongUniversity,Chengdu610031,Sichuan,China)Abstract:Becauseofthedevelopmentofhigh-speedcomputerandnetwork,combininggeneticalgorithmswithparallelprocesscanimprovetheefficiencyofGas.Someparallelizationmotivationsandimplementationmodelsforgeneticalgorithmsareanalyzed,theidealofcombiningGAswithparallelcomputationandthedifficultiesforusingitexpatiatedon.Keywords:GeneticAlgorithms;ParallelComputation(),J.Holland1975[1],,,,,!,,,,[2],,,,,,,,,,,,,,();,,,1隐并行性[3](*)*!(),(*101)(0101)(1101),,,2r(r*!),l2l,n2ln∀2l,Holland[4](implicitParallelism,)Goldberg[5]O(n3)n,ll,(H,(H)ls2ls-1∀(l-ls+1),n∀2ls-1∀(l-ls+1),,,,n=2ls/2,ls/1,,ls/2ls/2,ns#n∀2ls-1∀(l-ls+1)/2n=2ls/2,ns#n∀2ls-1∀(l-ls+1)/2=n∀n2∀(l-ls+1)/4=n3∀(l-ls+1)/4ns=cn3=O(n3),c:,O(n3),,O(n3)2并行遗传算法,,,,[2]:(1);(2);(3)Goldberg,,4:(1),,(2)(3),,,282004,:voidGeneticAlgorithm{initializationpopulation();//evaluatepopulation();//do{operatorselection();//operatorcrossover();//operatormutation();//evaluationpopulation();//updatepopulation();//,}while(!);}2.1(),,,(slaves),(master),:voidMasterSlaveGA(){initializationpopulation();//parallelevaluatepopulation();//do{operatorselection();//operatorcrossover();//operatormutation();//parallelevaluation_population();//updatepopulation();//,}while(!);},,,(),,,,,,2.2,,,,[6],,294,:,,,,,,MIMD(),,,,,;,,,:voidCoarseGrainGA(){initializationpopulation();//partitionpopulation();//nnfor(i=1;i=n;i++)//n,{evaluatesubpopulation();//do{for(j=1;j=m;m++)//m{operatorselection();//operatorcrossover();//operatormutation();//evaluationsubpopulation();//updatesubpopulation();//,}selectemigrant();//sendemigrant();//receiveimmigrant();////,}while(!);}},,,,,PrahladahHansdah[7](EDGA),,EDGA,,,,,123020042.3,,[6],,()(,,),,,,:voidFineGrainGA(){initializationpopulation();//,n,nindividualsdistributing();//nfor(i=1;i=n;i++)//n,{do{receiveimmigrants();//sendself();//evaluateimmigrants();//selectmate();//operatorcrossover();//operatormutation();//evaluateself();//evaluatechild();//if()replaceself();//}while(!);}}ManderickSpiessens[8],,,,,,,SIMD()for,,,,314,:3结束语,,NP,,,,,,,,1Holland,J.H.AdaptationinNatureandArtificialSystems[M].TheUniversityofMichiganPress,19752,[M].:,20003,.ZbigniewMichalewicz,GeneticAlgorithms+DataStructures=EvolutionPrograms[M].:,20004Holland,J.H.OutlineforaLogicalTheoryofAdaptiveSystems[J].JournaloftheAssociationforComputingMachinery,19625Goldberg,D.E.GeneticAlgorithmsinSearch,OptimizationandMachineLearning,Addison-wisley[J].Reading,MA.19896,.[M].:,19967Prahlada,B.B.andHansdah,R.C.ExtendedDistributedGeneticAlgorithmforChannelRouting[J].IEEETransonNeuralNetworks,19938Manderick,B.andSpiessens,P.Fine-grainedParallelGeneticAlgorithms[M].ProcofthethirdICGA,19899,.[M].:,200010,.[M].:,200011BarryWilkinson,MichaelAllen,.[M].:,2002(上接第8页)PID,,,SVC,1,.[M].:,19932Y.Wang,H.ChenandR.Zhou,etal.StudiesofVoltageStabilityviaaNonlinearSVCControlofIEEETransonPowerSystem[C].2000.1348~13533.SVC[J].,1998,13(4):1~44,.PID[J].,2002,22(11):41~445,.PID[J].,2003,24(6):10~15322004