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