遗传算法毕业论文.doc

《遗传算法毕业论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、遗传算法毕业论文目录1引言12问题描述23基于遗传算法TSP算法23.1基于遗传算法的TSP算法总体框架23.2　算法的详细设计33.2.1解空间的表示方式33.2.2种群初始化43.2.3　适应度函数43.2.4　选择操作43.2.5　交叉操作53.2.6　变异操作63.2.7进化逆转操作63.3实验结果分析74基于模拟退火算法的TSP算法104.1SA算法的实现过程104.2算法流程图104.3模拟退火算法的实现过程104.4实验结果115对两种算法的评价145.1遗传算法优缺点145.2模拟

2、退火算法的优缺点156结语15参考文献17附录：19廊坊师范学院本科生毕业论文论文题目：基于遗传算法与模拟退火算法的TSP算法求解10大城市最短旅途论文摘要：TSP问题为组合优化中的经典的NP完全问题.本论文以某旅行社为中国十大旅游城市--珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海制定最短旅途为例，分别利用基于遗传算法的TSP算法与基于模拟退火算法的TSP算法求解10大城市旅游路线问题.本论文给出了遗传算法与模拟退火算法中各算子的实现方法，并展示出求解系统的结构和求解系统基于MAT

3、LAB的实现机制．利用MATLAB软件编程，运行出结果，并对基于遗传算法的TSP算法结果与基于模拟退火算法的TSP算法的结果进行比较，描述其优缺点，并选择最为恰当的TSP算法，实现最短旅途的最优解.关键词：遗传算法；模拟退火算法；TSP；最短路径；Title：TSPAlgorithmBasedonGeneticAlgorithmorSimulatedAnnealingAlgorithmforSolvingtheShortestJourneyof10CitiesAbstract：TSPproblem

4、isaclassicNPproblemaboutcombinatorialoptimization．ThisarticletakesatravelagencylookingfortheshortesttripoftentouristcitiesinChina－Zhuhai，Xi'an，Hangzhou，Lhasa，Beijing，Lijiang，Kunming，Chengdu，LuoyangandWeihaiforinstance，andsolvesthisproblembyTSPalgorith

5、mbasedongeneticalgorithmandsimulatedannealingalgorithm．ThearticlegivestheimplementationsofeveryoperatorofgeneticalgorithmandsimulatedannealingalgorithmanddemonstratesthearchitectureandtheimplementationmechanismofthesolvingsystembasedonMATLAB．Iprograma

6、ndoperatetheresultsbyMATLABsoftware，andcomparetheresultsbasedongeneticalgorithmandsimulatedannealingalgorithm．AnddescribetheiradvantagesanddisadvantagessothatchoosethemostappropriateTSPalgorithmtoachievetheoptimalsolutionfortheshortestpath．Keywords：ge

7、neticalgorithm；simulatedannealingalgorithm；TSP；theshortestpath1引言TSP问题为组合优化中的经典问题，已经证明为一NP完全问题，即其最坏情况下的时间复杂性随着问题规模的扩大，按指数方式增长，到目前为止不能找到一个多项式时间的有效算法.TSP问题可描述为:已知n个城市相互之间的距离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才使其所走路线最短.TSP问题不仅仅是一个简单的组合优化问题，其他许多的NP完全问

8、题可以归结为TSP问题，如邮路问题、装配线上的螺帽问题和产品的生产安排问题等，使得TSP问题的有效求解具有重要的意义.本文中的TSP算法主要采用遗传算法与模拟退火算法．遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则．遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉、变异以及进化逆转等运算对个体进行筛选和进化，使适应值大的个体被保留，适应值小的个体被淘汰，新的群体继承了上一代的信息，又优于上一代，这样反复循环，