资源描述:
《基于均匀设计的遗传算法求解旅行商问题【毕业论文】》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、毕业论文本科毕业论文(20届)基于均匀设计的遗传算法求解旅行商问题专业:计算机科学与技术25毕业论文摘要旅行商问题(TSP)是古老的NP问题,目前的求解方法主要有:启发式算法、遗传算法、模拟退火算法、蚁群算法等。遗传算法是由美国密执安大学的Holland教授提出的,它通过模拟生物在自然环境中的遗传和进化过程来优化复杂问题的自适应算法。遗传算法对问题的种类具有很强的鲁棒性,因此广泛应用于很多领域,例如:自动控制、机器人学、图象处理、人工生命等。但是,在经典的遗传算法中是需要进行参数设定的,而这些参数的设定往往需要靠经验和
2、试验来确定,工作量非常大,而且很难得到最优的参数组合,影响了算法的使用性能,所以,在研究并设计有效且实用的参数组合问题上是具有重要理论和实现意义的。本文运用均匀设计的遗传算法来求解旅行商问题,一方面是旅行商问题本身是一种典型的需要使用编码方法求解的实际问题,这正好符合了遗传算法的特点。另一方面,在遗传算法中,需要对一些基本的运行参数(如:群体大小、交叉概率、变异概率等)进行设定,当参数水平个数增加时,其试验次数也大大增加,影响了算法的使用。因此利用均匀设计能够用较少的试验很快地设定出算法参数的取值,从而获得有效的近似最
3、优解。通过仿真试验表明,该方法是有效可行的。【关键词】遗传算法,旅行商问题,均匀设计,参数设定,组合优化25毕业论文GeneticAlgorithmtoSolvetheTravelingSalesmanProblemBasedonUniformDesignAbstractTravelingsalesmanproblem(TSP)isanoldNPproblem,thepresentsolutionmethodsare:heuristicalgorithm,geneticalgorithms,simulatedannea
4、ling,antcolonyalgorithm.GeneticalgorithmisputforwardbyProfessorHollandinMichiganUniversity,whichmadeitthroughthesimulationofthenaturalenvironment,bio-geneticandevolutionaryprocessestooptimizethecomplexproblemofadaptivealgorithm.Thetypeofgeneticalgorithmtotheprob
5、lemhasstrongrobustness,itiswidelyusedinmanyfields,suchas:automaticcontrol,robotics,imageprocessing,artificiallifeandsoon.However,intheclassicalgeneticalgorithmisneededforparametersetting,andsettingtheseparameterswhichareverylarge,oftenneedstorelyonexperienceandt
6、esttodeterminetheworkload.AnditisdifficulttoobtaintheoptimalcombinationofparametersthataffectthealgorithmPerformance,sohowtosettheparametersofstudyisofimportanttheoreticalandpracticalsignificance.Thisthesistriestosolvethetravelingsalesmanproblembyusinguniformdes
7、ignofgeneticalgorithm.Ontheonehand,thetravelingsalesmanproblemitselfisatypicalpracticalproblemthatrequiresencodingmethodtobesolved,whichfitsthecharacteristicsofthegeneticalgorithm.Ontheotherhand,geneticalgorithms,theneedforsomebasicoperatingparameters(suchas:pop
8、ulationsize,crossoverprobability,mutationprobability,etc.)tosetthelevel.whenthenumberofparametersincreases,thenumberoftestsalsoincreasedsignificantly,affectingAlgorit