볆쯣믺폫쿖듺뮯ꆡ2008쓪뗚2웚JISUANJIYUXIANDAIHUAퟜ뗚150웚컄헂뇠뫅:100622475(2008)0220043202믹폚틅뒫쯣램뗄TSP컊쳢폅뮯쟳뷢쇵쟠럯,샮ꆡ쏴(낲퇴릤톧풺,뫓쓏낲퇴455000)햪튪:싃탐짌컊쳢(TSP)쫇뗤탍뗄NP췪좫컊쳢,놾컄퓋폃틅뒫쯣램쟳뷢TSP컊쳢,쳡돶쇋룃쯣램퓚뷢뻶헢튻컊쳢훐뗄튻킩뒦샭랽램,쪹폃룃쯣램쓜릻뷏뿬뗘쟳돶튻엺ퟮ뛌슷뺶,뿉룹뻝탨튪짨훃뗾듺듺쫽,쟳뗃샭쿫ퟮ폅뷢ꆣ맘볼듊:TSP;틅뒫쯣램;ퟮ뛌슷뺶훐춼럖샠뫅:TP311ꆡꆡꆡꆡ컄쿗뇪쪶싫:AOptimizingSolutionforSolvingTSPProblemBasedonGeneticAlgorithmLIUQing2feng,LIMin(AnyangInstituteofTechnology,Anyang455000,China)Abstract:TravelingSalesmanProblem(TSP):TravellingSalesmanProblem(TSP);GeneticAlgorithm(GA);shortestpath1ꆡ룅ꆡ쫶컒쏇쾰맟짏냑Holland1975쓪쳡돶뗄GA돆캪뒫춳뗄GAꆣ쯼뗄훷튪늽훨죧쿂:틅뒫쯣램(Gen뇠싫:GA퓚뷸탐쯑쯷횮잰쿈붫뷢뿕볤뗄뷢쫽뻝뇭쪾돉틅eticAlgorithm볲킴GA)쫇튻샠뷨본짺컯뷧뗄뷸뮯맦싉(쫊헟짺듦뒫뿕볤뗄믹틲탍뒮뷡릹쫽뻝,헢킩뒮뷡릹쫽뻝뗄늻춬ퟩ뫏뇣,폅쪤쇓청틅뒫믺훆릹돉쇋늻춬뗄뗣ꆣ)퇝뮯뛸살뗄쯦믺뮯쯑쯷랽램ꆣ쯼쫇평쏀맺뗄J.돵쪼좺쳥뗄짺돉:쯦믺닺짺N룶돵쪼뒮뷡릹쫽뻝,쎿룶뒮Holland뷌쫚1975쓪쫗쿈쳡돶뗄ꆣ퓚틅뒫쯣램훐,좾즫쳥뛔펦뗄쫇쫽뻝믲쫽ퟩ뷡릹쫽뻝돆캪튻룶룶쳥,N룶룶쳥릹돉쇋튻룶좺쳥ꆣGA틔,춨헢N룶뒮뷡릹쫽뻝ퟷ캪돵쪼뗣뾪쪼뗼듺ꆣ뎣쫇평튻캬뗄뒮뷡릹쫽뻝살뇭쪾,뒮짏룷룶캻훃뛔펦쫊펦탔횵움맀볬닢:쫊펦탔몯쫽뇭쏷룶쳥믲뷢뗄폅쇓탔ꆣ믹틲뗄좡횵ꆣ믹틲ퟩ돉뗄뒮뻍쫇좾즫쳥,믲헟뷐믹틲늻춬뗄컊쳢,쫊펦탔몯쫽뗄뚨틥랽쪽튲늻춬ꆣ탍룶쳥(Individuals)ꆣ튻뚨쫽솿뗄룶쳥ퟩ돉쇋좺쳥톡퓱:톡퓱뗄쒿뗄쫇캪쇋듓떱잰좺쳥훐톡돶폅솼뗄룶쳥,(Population)ꆣ좺쳥훐룶쳥뗄쫽쒿돆캪좺쳥듳킡쪹쯼쏇폐믺믡ퟷ캪뢸듺캪쿂튻듺랱횳ퟓ쯯ꆣ틅뒫쯣램춨맽톡(Popu퓱맽돌쳥쿖헢튻쮼쿫,뷸탐톡퓱뗄풭퓲쫇쫊펦탔잿뗄룶쳥캪lationSize),튲뷐좺쳥맦쒣ꆣ뛸룷룶룶쳥뛔뮷뺳뗄쫊펦돌뛈뷐ퟶ쫊펦뛈쿂튻듺릱쿗튻룶믲뛠룶뫳듺뗄룅싊듳ꆣ톡퓱쪵쿖쇋듯뛻컄뗄(Fitness)ꆣ틅뒫쯣램쫇튻훖좺쳥탍닙ퟷ,룃닙ퟷ틔좺쳥훐뗄쫊헟짺듦풭퓲ꆣ쯹폐룶쳥캪뛔쿳ꆣ톡퓱붻뮻:붻뮻닙ퟷ쫇틅뒫쯣램훐ퟮ훷튪뗄틅뒫닙ퟷꆣ춨맽(Selecation)ꆢ붻닦(Cross2붻뮻닙ퟷ뿉틔뗃떽탂튻듺룶쳥,탂룶쳥ퟩ뫏쇋웤뢸놲룶쳥뗄over)뫍뇤틬(Mutation)쫇틅뒫쯣램뗄3룶훷튪닙ퟷ쳘탔ꆣ붻뮻쳥쿖쇋탅쾢붻뮻뗄쮼쿫ꆣ쯣ퟓ,쯼쏇릹돉쇋틅뒫닙ퟷ(GeneticOperation),쪹틅뇤틬:뇤틬쫗쿈퓚좺쳥훐쯦믺톡퓱튻룶룶쳥,뛔폚톡훐뗄뒫쯣램뻟폐쇋웤쯻뒫춳랽램쯹쎻폐뗄쳘탔ꆣ룶쳥틔튻뚨뗄룅싊쯦믺뗘룄뇤뒮뷡릹쫽뻝훐쒳룶뒮뗄횵ꆣ춬(1)틅뒫쯣램뗄믹놾늽훨:짺컯뷧튻퇹,GA훐뇤틬랢짺뗄룅싊뫜뗍,춨뎣좡횵퓚쫕룥죕웚:2007201229ퟷ헟볲뷩:쇵쟠럯(19702),얮,뫓쓏낲퇴죋,낲퇴릤톧풺붲쪦,퇐뺿랽쿲:볆쯣믺죭볾폫샭싛;샮쏴(19762),얮,뫓쓏낲퇴죋,붲쪦,퇐뺿랽쿲:볆쯣믺펦폃ꆣ
ꆡ44볆ꆡ쯣ꆡ믺ꆡ폫ꆡ쿖ꆡ듺ꆡ뮯2008쓪뗚2웚ꆫ횮볤ꆣ뇤틬캪탂룶쳥뗄닺짺쳡릩쇋믺믡ꆣꆡꆡBegin(2)틅뒫쯣램(GA)뗄볆쯣맽돌캪:Fori=1to10do톡퓱뇠싫랽쪽Forj=1to9do닺짺돵쪼좺쳥t(i)=int(random()310)볆쯣돵쪼좺쳥뗄쫊펦탔횵(&&쯦믺닺짺1ꆫ9횮볤뗄튻룶헻쫽ꆣ)죧맻늻싺ퟣ쳵볾{end톡퓱돵쪼뮯뻠샫뻘헳뗄쯣램:붻뮻뇤틬ꆡꆡbegin볆쯣탂튻듺좺쳥뗄쫊펦탔횵fori=1to9doforj=i+1to9do}d(i,j)=int(rand()3100)2ꆡ틅뒫쯣램뫍싃탐짌컊쳢printd(i,j);endퟮ뛌슷뺶:쯹캽ퟮ뛌슷뺶컊쳢,뻍쫇퓚룸뚨뗄웰힢틢:i=j쪱,d(i,j)=0뗣S떽훕뗣T뗄춨슷벯뫏훐,톰쟳뎤뛈ퟮ킡뗄춨슷,볆쯣쎿룶룶쳥뗄쫊펦횵eval(i)=minꇆd(t(i),t(i+1))헢퇹뗄춨슷돆캪S뗣떽T뗣뗄ퟮ뛌슷뺶ꆣi=1,2,3,4,5,6,7,8,9,10싃탐짌컊쳢(TSP)쫇볆쯣믺뿆톧훐뗄튻룶뗤탍볆쯣10룶룶쳥쫊펦횵횮뫍F=ꇆeval(i)컊쳢:싃탐짌뇘탫퓚웤믮뚯쟸폲쓚뛔쎿룶돇쫐럃컊튻i=1,2,3,4,5,6,7,8,9,10듎쟒뷶튻듎볆쯣쎿룶룶쳥뗄톡퓱룅싊p(i)=12eval(i)/F,늢쟒ퟮ훕략믘떽웰쪼뗣ꆣ쟳뷢뗄죎컱쫇,죧뫎쪹ퟟ맽뗄슷돌ퟮ뛌ꆣi=1,2,3,4,5,6,7,8,9,10컊쳢뿉맩뷡떽춼싛짏볆쯣쎿룶룶쳥뗄샛볆룅싊q(i)=ꇆp(i),볙짨폐튻룶춼G=(V,E),웤훐V쫇뚥뗣벯,E쫇뇟벯i=1,2,3,4,5,6,7,8,9,10,짨d=d(ij)쫇평뚥뗣(4)듦믮톡퓱닟싔ꆣi뫍뚥뗣j횮볤뗄뻠샫쯹ퟩ돉뗄뻠샫뻘헳,싃탐짌컊쳢뻍쫇쟳돶튻쳵춨맽쯹폐뚥뗣쟒쎿룶뚥뗣횻춨맽닉폃싖엌뛄뗄랽쪽,톡좡쫊펦횵킡뗄룶쳥ퟷ캪뢸쳥ꆣ튻듎뗄뻟폐ퟮ뛌뻠샫뗄믘슷ꆣ톡퓱맽돌:톡퓱맽돌쫇틔탽뛄싖10듎캪믹뒡,쎿듎탽뚼캪탂뗄훖좺톡퓱튻룶룶쳥ꆣ뛄싖쫇내쎿룶룶쳥뗄쫊펦뛈싃탐짌컊쳢쫇튻룶뗤탍뗄ퟩ뫏폅뮯컊쳢,늢쟒쫇뷸탐톡퓱뗄ꆣ쯣램죧쿂:튻룶NP쓑컊쳢,웤뿉쓜뗄슷뺶쫽쒿폫돇쫐쫽쒿n쫇step1뛔쎿룶룶쳥v(i),볆쯣샛볆룅싊q(i)돉횸쫽탍퓶뎤뗄,쯹틔튻냣뫜쓑뺫좷뗘쟳돶웤ퟮ폅step2듓쟸볤[0,1ꆽ훐닺짺튻룶쯦믺쫽r;뷢,놾컄닉폃틅뒫쯣램쟳웤뷼쯆뷢ꆣstep3죴q(i)>r,퓲톡좡q(i)뛔펦뗄룶쳥v(i);step4훘뢴step2뫍step3릲10듎,헢퇹3ꆡTSP컊쳢뗄틅뒫쯣램맽돌볲뷩뿉틔뗃떽10룶뢴훆뗄룶쳥ꆣ(1)뇠싫ꆣ(5)틅뒫쯣ퟓ짨볆ꆣ닉폃헻쫽업쇐뇠싫랽램ꆣꋙ퓓붻쯣ퟓ:죴뛔폚돇쫐V={v1,v2,v3,ꆭ,vn}뗄튻룶럃컊쮳탲캪t놾컄닉폃늿럖펳짤퓓붻,좷뚨붻닦닙ퟷ뗄뢸듺,붫10룶=(t1,t2,t3,ꆭ,ti,ꆭ,tn),웤훐t캪{1,2,3,ꆭ,n}뗄튻룶업퇹놾솽솽럖ퟩ,럖캪5ퟩꆣ듓1떽5훘뢴틔쿂맽돌:쇐,쟒볇tn+1=t1,d(t(i),t(i+1))캪돇쫐ti폫ti+1횮볤step1:듓[0,1]훐닺짺솽룶쯦믺쫽a1뫍a2,쇮r1=a13뗄뻠샫,퓲싃탐짌컊쳢뗄쫽톧쒣탍캪:10뫍r2=a2310,좷뚨솽룶캻훃,뛔솽캻훃뗄훐볤쫽뻝뷸탐붻minꇆd(t(i),t(i+1))(i=1,ꆭ,n)닦,죧:r1=4,r2=9(2)쫊펦뛈몯쫽ꆣ횱뷓폃틔짏쫽뻝쒣탍ퟷ캪쫊펦뛈몯쫽,eval(i)=minꇆd(t(i),t(i+1))ꆣ(3)훖좺돵쪼뮯ꆣ붻닦뫳캪:놾컄틔9룶돇쫐캪샽,돇쫐폃뇠뫅1,2,3,4,5,6,7,8,9뇭쪾횮ꆣ톡폃10룶퇹놾룶쳥ퟷ캪훖좺,벴쯦믺톡좡{1,2,3,4,5,6,7,8,9}뗄10룶업쇐ꆣ쇭쯦믺닺짺돇쫐볤뗄뻠샫뻘헳step2:붻닦뫳,춬튻퇹놾훐폐훘뢴뗄돇쫐,늻훘뢴뗄쫽ퟖd,볆쯣돶쪮룶퇹놾뗄쫊펦횵ꆣ돵쪼뮯훖좺쯣램뿉뇭쪾죧쿂:놣쇴,폐돥춻뗄쫽ퟖ(듸3캻훃)닉폃늿럖펳(쿂뗚56튳)
ꆡ56볆ꆡ쯣ꆡ믺ꆡ폫ꆡ쿖ꆡ듺ꆡ뮯2008쓪뗚2웚[1]ꆡ돂뺩쏱.쫽뻝닖뿢풭샭ꆢ짨볆폫펦폃[M].놱뺩:훐맺쮮5ꆡ뷡쫸폯샻쮮뗧돶냦짧,2004.놾컄훷튪뛔뗣믷쇷쫽뻝닖뿢뗄펦폃쾵춳뗄쿠맘[2]ꆡ[쏀]MarkSweiger,MarkRMadsen,뗈.뗣믷쇷쫽뻝닖뿢짨볆컊쳢ퟶ쇋싛쫶,쳖싛쇋퓚짨볆맽돌훐탨튪뾼싇뗄[M].슽닽믔,헅맢붣,돂ퟴ,헅샶,뗈틫.놱뺩:뗧ퟓ릤튻킩컊쳢,죧쫽뻝풴벰폃뮧짭럝뗄본뇰뫍룺ퟙ컊쳢ꆢ튵돶냦짧,2004.뗣믷쇷쫽뻝닖뿢뗄풪쒣쪽뗄짨볆컊쳢ꆢ쫽뻝돩좡뮻[3]ꆡMobasherB,CooleyR,[J].Communicationsof뫍볓퓘릤뻟(ETL)뗄쿠맘컊쳢ꆢ쫽뻝럖컶릤뻟theACM,2000,43(8):1422151.(OLAP)뗄쿠맘컊쳢ꆢ폃뮧뗄Web펦폃쒣쪽뗄췚뻲컊[4]ꆡMassegliaF,TanasaD,:쳢뗈,틽죫뗣믷쇷쫽뻝닖뿢뿉틔폐킧뗘쳡짽폃뮧뗄짌Sequentialpatternextractionwithaverylowsupport[C]//컱훇쓜펦폃쮮욽ꆣProceedingsofthe6thAsia2PacificWebConference,퓚쫽뻝췚뻲늿럖,놾컄틽죫튻훖룄뷸뗄맘솪맦퓲2004:5132522.쯣램[5]ꆡHuangJZ,YangQ,NgM,,폫뗣믷쇷쫽뻝닖뿢뷡뫏웰살뿉틔폐킧룄뷸췚뻲뗄킧싊ꆣ떫퓚뛠닣듎럖컶랽쏦죔탨룄뷸,뛸쟒쯣램킧prediction2basedWebprefetching[J].JournalofIntelli2싊놾짭뮹폐뷸튻늽쳡룟뗄뿕볤ꆣgenceInformationSystems,2003,20(1):11230.[6]ꆡ컢킡늨,탬캬쿩.뛠횧돖뛈맘솪맦퓲퓚췸싧쪹폃췚뻲훐ETL짨볆늿럖쫇쫽뻝닖뿢짨볆훐ퟮ캪뢴퓓뗄늿럖,뿉틔뾼싇짨볆춨폃뗄뗄펦폃[J].볆쯣믺릤돌폫펦폃,2005,41(31):1642Web펦폃쇬폲뗄릹볾뿢살쳡룟쾵167.춳쪵쪩뗄킧싊,헢룶랽쏦뮹탨ퟶ뷸튻늽뗄퇐뺿ꆣ[7]ꆡ탁횾,쇵짙믔,쪷훒횲.맘솪맦퓲쯣램뗄쪵쿖폫룄뷸[J].볆쯣믺릤돌폫펦폃,2002,38(24):1902192.닎뾼컄쿗:(짏뷓뗚44튳)뒫쯣램쫇퓚뗣좺훐톰폅;쯼뷶쪹폃컊쳢놾짭쯹뻟폐뗄짤뗄랽램쿻돽돥춻ꆣ벴샻폃훐볤뛎뗄뛔펦맘쾵,뷸탐펳짤ꆣ쒿뇪쫽뻝뷸탐릤ퟷ,뛸늻탨웤쯼죎뫎쿈뻶쳵볾믲뢨훺뷡맻캪:탅쾢;쯼쪹폃뗄쫇쯦믺맦퓲ꆣ닎뾼컄쿗:ꋚ뇤틬맽돌[1]ꆡ닜슳틺,싞뇳,쟕쏷뫆.폃틅뒫쯣램쟳뷢ퟮ뛌슷뺶컊쳢:놾컄닉폃떹캻뇤틬ꆣ샠쯆붻닦닙ퟷ맽돌,쯦믺톡퓱솽룶뗣r1뫍r2,붻뮻캻훃,늢붫솽뗣볤뗄쫽ퟖ,듓r2뾪[J].뫏럊릤튵듳톧톧놨(ퟔ좻뿆톧냦),1996,19(3):쪼1122116.,떹탲럅훃ꆣ죧:쇮r1=3,r2=7[2]ꆡ[쏀]ZbigniewMichalewicz,DavidBFogel.죧뫎쟳뷢컊쳢842735961-쿖듺웴랢쪽랽램[M].닜뫪쟬,샮퇞,뚭뫬뇳,뗈틫.뇤틬뫳:849537261놱뺩:훐맺쮮샻쮮뗧돶냦짧,20031뛔쎿룶퇹놾뷸탐붻닦뇤틬,좻뫳듺죫쫊펦뛈몯쫽뷸탐움[3]ꆡ맀,톡퓱돶쫊펦횵킡뗄퇹놾뷸탐쿂튻듺뗄붻닦뫍뇤틬ꆣ톭뮷MTSP[J].커몺샭릤듳톧톧놨(붻춨뿆톧폫릤돌냦),닙ퟷ:에뛏쫇럱싺ퟣ짨뚨뗄듺쫽x,럱,퓲쳸죫쫊펦뛈eval뗄볆2002(12):22225.쯣[4]ꆡ폠폐쏷,쇵폱쫷,퇖맢캰1틅뒫쯣램뗄뇠싫샭싛폫펦폃;쫇,뷡쫸틅뒫닙ퟷ,췋돶ꆣ틅뒫쯣램훐,붻닦쯣ퟓ틲웤좫뻖쯑쯷쓜솦뛸ퟷ캪훷튪쯣[J]1볆쯣믺릤돌폫펦폃,2006(3):862891ퟓ[5]ꆡ췵뎬톧,듞뛅커,췵훱죙,럑죘1튻훖쟳뷢TSP뗄룟킧틅,뇤틬쯣ퟓ틲웤뻖늿쯑쯷쓜솦뛸ퟷ캪뢨훺쯣ퟓꆣ틅뒫쯣램춨맽붻닦뫍뇤틬헢튻뛔쿠뮥엤뫏폖쿠뮥뺺헹뗄닙ퟷ뛸쪹웤뻟뒫쯣램[J]1컷낲샭릤듳톧톧놨,2006,22(1):372411놸볦맋좫뻖뫍뻖늿뗄뻹뫢쯑쯷쓜솦ꆣ쯹캽쿠뮥엤뫏,쫇횸떱[6]ꆡ닌횮뮪,역뷵맺,룟캰1튻훖룄뷸뗄쟳뷢TSP컊쳢뗄퇝좺쳥퓚뷸뮯훐쿝폚쯑쯷뿕볤훐쒳룶뎬욽쏦뛸뷶뾿붻닦늻쓜냚뮯쯣램[J]1볆쯣믺톧놨,2005,28(5):82328281췑쪱[7]ꆡBaragiliaR,HidalgoJi,,춨맽뇤틬닙ퟷ뿉폐훺폚헢훖냚췑ꆣ쯹캽쿠뮥뺺헹,쫇횸떱춨맽붻닦틑탎돉쯹웚췻뗄쒣쪽쪱,뇤틬닙ퟷ폐뿉쓜웆뮵헢thetravelingsalesmanproblem[J]1IEEETransactionson킩쒣쪽ꆣ틲듋,죧뫎폐킧뗘엤뫏쪹폃붻닦뫍뇤틬닙ퟷ,쫇쒿잰EvolutionaryComputation,2001(5):6132622.튻룶훘튪퇐뺿쓚죝ꆣ[8]ꆡ[J]1ComplexityInternational,4ꆡ뷡쫸폯1995(2):5482553.[9]ꆡ퇠훒,풬뒺캰1폃틏좺쯣램쟳뷢훐맺싃탐짌컊쳢[J]1춨맽폃틅뒫쯣램뷢쳢뿉횪,틅뒫쯣램뗄폅뗣:틅뗧슷폫쾵춳톧놨,2004,9(3):12221261ΗΗ
