搜索
19201110ChineseJournalofManagementScienceVol.19SpecialIssueOctober20111003－2072011zk－0084－07518060。。。TSPF275TP18A2011－07－142011－08－0571001072201004807059451806001002294JC2010052804921980－、．1、、。、。TravelingSalesmanProblemTSP、TSP。NP。。TSP232425。TSPTSP。TSP19、12。。24ParticleSwarmOptimizationPSO、5NeuralNetwork、7AntColonyOptimizationACO、818GeneticAlgorithmsGA、9SimulatedAnnealingSA。TSP3TSPTSPTSP。。11113ArtificialBeeColonyAl-gorithmABCKaraboga2005、。14、15PID16。AlokSingh200815201030－1、200921ABC、200910TSPBeeColonyOptimizationBCOABCAnanBanharnsakun201011GreedySubtourCrossoverTSPABC-GSX。ABC-GSX。、、。TSP。2ABC2005Karaboga1。ABC3、、。1。、。“”。2。、。。。。。3。3、、。①。。vij=xij+rxij－xkj11vijxijxkjr－11k∈12…{}SNj∈12…{}DSND。。②。Pi=fiti∑fitn22fitii。1。③。ABClimit。limit。xij=xjmin+rand01xjmax－xjmin3xjminj·58·2011xjmaxj。3ABCABC。nTSPS=aii=12…n2。SOi1i2Sai1ai2SSOi1i2Snew=S+SOi1i2。10TSPS=35186102749SO49SSnew=S+SO49=35186102749+SO49=35146102789SSSS=SO1SO2…SOnSO1SO2…SOnSSSSSSSSOiSSnew=S+SS=SO1SO2SO3…SOn=S+SO1+SO2+…+SOn。TSP1TSPABC1Colony、limit、Maxcycle、runtime。21SSSj=SOj1SOj2SOj3…SOjmj=12…nnm。2SSS1Snew。3SnewSSnewSSnewSStrail。312Son。2SonSS1Sonew。3SonewSonSonewSonSonewSStrail。4trailMM＞limit3。5Maxcycle。1TSPTSP4PCIntelI3－370MCPU2GBofmemoryWin2007Matlab7．0TSPLIBBURMA14BAYS29DA-NTZIG42BERLIN52KROA100CH130TSP。。4．1NselimitBURMA14DANTZIG42。Nse。NseNTSPColony2NMaxcycle200limit50。TSPBURMA14Nse1571014DANTZIG4251021324212。limit·68·BURMA14NseNDANTZIG42NseN/2limit10204010012034。12Nse。TSPBURMA14NseTSPN/2。DA-NTZIG42NseN/2NseN/2。Nse。TSPNseTSPNse。1BURMA142DANTZIG423BURMA144DANTZIG42limitlimit。34limitlimit。limit。4．2DABCPSODiscreteArtificialBeeColonyAlgorithmDABC2PSO2αβPSO·78·2011。3ScaleTSPBest20Average20Worst20ErrorError=Average-Best/Best*100%。2ColonyruntimeMaxcyclelimitNseβDABCPSO2*N2*N202010001000100noN/2N/2no0．25no0．253ScaleBestAverageWorstError%BURMA1414DABC34．483834．760735．95490．80PSO35．378836．925338．82744．37BAYS2929DABC1602416751172214．54PSO1699517953185335．64DANTZIG4242DABC1622．61733．11835．26．41PSO1933．81987．72038．62．79BERLIN5252DABC2103121338217681．46PSO2127421827225322．60KROA100100DABC1291101299601317200．66PSO1302101324001354501．68CH130130DABC3703937243381210．55PSO3707937982387132．44DABCPSOTSP。Error20。TSPPSODABCDABC6GeneticAlgorithmGA。BURMA14DANTZIG42。5DABC、PSOGATSPBURMA146TSPDANTZIG42。DABC、PSOGADABC。DABCGATSPBURMA14DABCGA。DABCGA。5BURMA146DANTZIG425TSP6TSPPSO·88·。。。。TSPTSP。。。、、。1KarabogaD．．AnIdeaBasedonHoneyBeeSwarmforNumericalOptimization．TechnicalReportTR06RComputerEngineer-ingDepartmentErciyesUniversityTurkey2005．2WangK．P．HuangL．ZhouC．G．PangW．．ParticleswarmoptimizationfortravelingsalesmanproblemJ．In2ndIEEEInternationalConferenceonMachineLearningandCybernet-ics20031583－1585．3．．2010．4MarinakisY．MarinakiM．DouniasG．．AhybridparticleswarmoptimizationalgorithmforthevehicleroutingproblemJ．EngineeringApplicationsofArtificialIntelligence201023463－472．5MasuttiT．A．S．CastroL．N．D．．Aself-organizingneuralnet-workusingideasfromtheimmunesystemtosolvethetravelingsalesmanproblemJ．InformationSciences20091791454－1468．6GloverF．．ArtificialintelligenceheuristicsframeworksandtabusearchJ．Managerial＆DecisionEconomics199011365－378．7TsaiC．F．TsaiC．W．TsengC．C．．AnewhybridheuristicapproachforsolvinglargetravelingsalesmanproblemJ．Informa-tionSciences200416667－81．8HeinrichB．．OnsolvingtravelingsalesmanproblemsbygeneticalgorithmsJ．InSchwefelH．R．MannerR．eds．Paral-lelProblemSolvingfromNatureLNCS1991496129－133．9MeerK．．SimulatedannealingversusmetropolisforaTSPIn-stanceJ．InformationProcessingLetters2007104216－219．10．TSPJ．200929978－982．11BanharnsakunA．AchalakulT．SirinaovakulB．．ABC-GSXAhybridmethodforsolvingthetravelingsalesmanproblemJ．In2ndIEEEWorldCongressonNatureandBiologicallyIn-spiredComputing20107－12．12FinkeG．ClausA．GunnE．．Atwo-commoditynetworkflowapproachtothetravelingsalesmanproblemJ．CongressusNumerantium198441167－178．13KarabogaD．BasturkB．．OntheperformanceofartificialbeecolonyABCalgorithmJ．AppliedSoftComputing20088687－697．14KarabogaN．．AnewdesignmethodbasedonartificialbeecolonyalgorithmfordigitalIIRfiltersJ．JournaloftheFranklinInstitu-te2009346328－348．15SinghA．．Anartificialbeecolonyalgorithmfortheleaf-con-strainedminimumspanningtreeproblemJ．AppliedSoftCom-puting20099625－631．16KarabogaD．AkayB．．PIDcontrollerdesignbyusingartificialbeecolonyharmonyaearchandthebeesalgorithmsJ．JournalofSystemsandControlEngineering2010224869－883．17PanQ．K．TasgetirenM．F．SuganthanP．N．ChuaT．J．．Adiscreteartificialbeecolonyalgorithmforthelot-streamingflowshopschedulingproblemJ．InformationSciences20101812455－2468．18YangJ．WuC．LeeH．P．LiangY．．SolvingtravelingsalesmanproblemusinggeneralizedchromosomegeneticalgorithmJ．ProgressinNaturalScience200818887－892．19MiliotisP．．UsingcuttingplanestosolvethesymmetrictravelingsalesmanproblemJ．MathematicalProgramming197815177－188．20．J．201017－11．21．J．20093993－96．22KarabogaD．BasturkB．．ApowerfulandefficientalgorithmfornumericalfunctionoptimizationArtificialbeecolonyABCalgorithmJ．JournalofGlobalOptimization200739459－471．23．J．2011281647－1650．24．J．20112940－46．25．J．2011321201－1204．·98·2011ADiscreteArtificialBeeCo