遗传算法与禁忌搜索算法的混合策略

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

李大卫①(,114002) 王 莉(,114005) 王梦光(,110006)   遗传算法与禁忌搜索算法的出现为解决高维组合优化问题提供了强有力工具.二者既有共性,又有个性.通过对遗传算法与禁忌搜索算法的分析,提出了一种遗传算法与禁忌搜索算法的混合策略,把禁忌搜索算法独有的记忆思想引入到遗传算法的搜索过程中,构造了新的重组算子,并把禁忌搜索算法作为遗传算法的变异算子,对旅行商问题的求解表明:混合策略在许多方面优于遗传算法.:,,,:N94GENETICALGORITHMANDTABUSEARCH:AHYBRIDSTRATEGYLiDawei(AnshanInstituteofIronandSteelTechnology,Anshan114002)WangLi(AnshanNormalCollege,Anshan114005)WangMengguang(NortheasternUniversity,Shenyang110006)Abstract Theappearanceofgeneticalgorithmsandtabusearchprovidepowerfultoolsforsolvingcombinatorialoptimizationproblemsinhighdimen-sions.Thetwomethodseitherhavesomecommonbonds,orsignificantdiffer-ences.Throughanalysing,weproposeahybridstrategyofgeneticalgorithmandtabusearch.Thememoryfunctionoftabusearchisintroducedintoprocedureofgeneticalgorithms.Anewrecombinationoperatorisconstructed,whilemutationoperatorisreplacedbytabusearch.Geneticalgorithmandhybridstrategyareusedseparatelytosolvetravelingsalesmanproblem.Theexperimentresultsshowthatthehybridstrategyissuperiortothestandardgeneticalgorithminmanyaspects.Keywords:geneticalgorithm,tabusearch,hybridstrategy0  20,Holland、(geneticalgorithms,GA)[1].GA,DarwinMendel.GA13319989          JOURNALOFSYSTEMSENGINEERING     Vol.13No.3Sep.1998①36,,,.36,male,Dr.,lecturer.1997411.,.,GA[2].(TabuSearch,TS),Glover[3].TS.TS,TS,,[5].GA,TS.,.GATS,,GATS,.GATS.,GATS,GATS(GATS),TSGA,,TSGA.1 GATS1.1 GAGA     GA=(Npop,Ngen,K,feval,fsel)Npop;Ngen;K();feval,;fsel.,GATS.GA4[2]:1),;2),;3),;4),.GA1:begin t=0;initializeP(t); evaluatestructuresinP(t); whileterminationconditionnotsatisfieddo  t=t+1;  selectP(t)fromP(t-1);  recombinestructuresinP(t);  evaluatestructuresinP(t);end(P(t)t)1 GA1.2 TS,TS·29·19989       :     TS=(Npop,Ngen,Λ,fmove,tabulist)Npop;Ngen;Λ;fmove;tabulistT,T,.TS2:begin t=0;generateNpop;setT; setthebestandpresentsolutionsx=x0=Npop; whileterminationconditionnotsatisfieddo  t=t+1;  movextox′;  update(x;x0;tabulist);end        2 TSTS.TS,,TS“”(),TS,,.2 GATS2.1 GAGA,,,,GA.,GA,,,GA.GA“”.,GA——,;,.,GA..,GA,GA,AckleySIGH[6].,GA.2.2 TSTSGA,TS.TS,TS.,TS.TS,,GA().·30·               13 33 GATSGATS,,.MǜhlenbeinGA[6],TSGloverGATS[7],GATS.GATS,Glover,GATSGATS.TSGA,TSR,GA,TS,TSGA,TSGATSM.GATSGATS,GA,GA.x(),TSM3:begin  t=0;setthebestsolutionx0=x;setT;  whileterminationconditionnotsatisfieddo   t=t+1;   movextox′;   update(x;x0;tabulist);end3 TSMTSM.,TSM()(),TSM,.TSM,,().TSMTS,,TSM().TSR,T,,.TSR,,,,;,,;,,4:begin  iffitnessofxaveragevalueofpopulation,thenacceptx  else   ifoffspringxisnotintabulist     acceptx   else     choosethebetteroftwoparentstothenextgeneration;   updatetabulist;end4 TSR·31·19989       :TSR,,,TSR,,,.GATSGATS:GATS:Step0(Ngen,Npop,pc,pm)Step1t=0;;Step2;Step3:Npop,;Step4 step4.10,1ri,i=1,2,…,Npop;ripc,i,pc*Npop; step4.2,; step4.3TSR;Stpe5 step5.10,1ri,i=1,2,…,Npop;ripm,TSMi; step5.2t=t+1;tNgen,Step2;,.4 GATS,GAGATSTSP,n=10,67TSP,[8,9].,.,TSM/TSRGA,GAGATS.,.4.1GATSP,,[2].,,TSP,..:          P={8,2,4,6,1,5,7,3}P,8,2,4,…,3,8.,,,.:          Q={2,4,6,1,5,7,3,8}QP,,PQ.4.2TSP,Pf(P):·32·               13 3     f(P)=Cmax-Cmax,.4.3GA,PMX,CXOX[2],,GATS,TSR,PMX,CXOX,TSM.4.4,1,2,…,nNpop,.,GAGATS:30,0.80.03.n=10,100.n=67,1000.12,56PMXGAGATS.1 10TSP(:km)GAGATSPMXCXOXPMXCXOX839580737373732 67TSP(:km)GAGATSPMXCXOXPMXCXOX17531795178016531679167216155 10TSPGAGATS(PMX)  5.5,GA40,GATS610,11,13.  67TSP,GA4002875,6002217,8001753,GATS6 67TSPGAGATS(PMX)4001737,6001653,.TSRGATS(GATSM).767TSP.  ,GATS,,700,TSRGATS.·33·19989       :7 TSRGATS(PMX)GATS.GATSGATS.N,GAO(N3)[2].GATSGA.67TSP,GATSGA1.2.GATSTSM,.5  TSRTSMGA,GATSGATS,GATSGA.TSP,GATSGA(),GA.1 HollandJ.Adaptioninnaturalandartificialsystems.TheUniversityofMichiganPress,AnnArbor,19752 GoldbergD.Geneticalgorithminsearch,optimizationandmachinelearning.Addison-WesleyPublish-ing,19893 GloverF.FuturePathsforintegerprogrammingandlinkstoartificialintelligence.ComputersOpsRes.,1986;5:533~5494 GloverF,LagunaM.Tabusearch.InModernHeuristicTechniquesforCombinatorialProblems(Edit-edbyC.Reeves),Oxford:BlackwellScientific,19935 AckleyD.Stochasticiteratedgenetichillclimbing.Ph.D.Diss.,Dept.Comp.Sci.CMU-CS-87-107,CarnegieMellonUniversity,March19876 MǜhlenbeinH.Parallelgeneticalgorithmsincombinatorialoptimization.ComputerScienceandOpera-tionsResearch(EditedbyOsmanBalci),Oxford:PergamonPress,19957 GloverF,KellyJ,LagunaM.Geneticalgorithmsandtabusearch:hybridsforoptimizations.Comput-ersOps.Res.,1995,22(1):111~1348 FouldsL.Combinatorialforundergraduates.Spring-VerlagNewYorkInc.,19849 NemhanserG,WolseyL.Integerandcombinatorialoptimization.Wiley-InterScience,1986·34·               13 3

1 / 7
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功