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

李大卫①(,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