遗传算法毕业论文

目录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模拟退火算法的优缺点.................................................................................................156结语.............................................................................................................................................15参考文献.........................................................................................................................................17附录：...............................................................................................................错误!未定义书签。廊坊师范学院本科生毕业论文论文题目：基于遗传算法与模拟退火算法的TSP算法求解10大城市最短旅途论文摘要：TSP问题为组合优化中的经典的NP完全问题.本论文以某旅行社为中国十大旅游城市--珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海制定最短旅途为例，分别利用基于遗传算法的TSP算法与基于模拟退火算法的TSP算法求解10大城市旅游路线问题.本论文给出了遗传算法与模拟退火算法中各算子的实现方法，并展示出求解系统的结构和求解系统基于MATLAB的实现机制．利用MATLAB软件编程，运行出结果，并对基于遗传算法的TSP算法结果与基于模拟退火算法的TSP算法的结果进行比较，描述其优缺点，并选择最为恰当的TSP算法，实现最短旅途的最优解.关键词：遗传算法；模拟退火算法；TSP；最短路径；Title：TSPAlgorithmBasedonGeneticAlgorithmorSimulatedAnnealingAlgorithmforSolvingtheShortestJourneyof10CitiesAbstract：TSPproblemisaclassicNPproblemaboutcombinatorialoptimization．ThisarticletakesatravelagencylookingfortheshortesttripoftentouristcitiesinChina－Zhuhai，Xi'an，Hangzhou，Lhasa，Beijing，Lijiang，Kunming，Chengdu，LuoyangandWeihaiforinstance，andsolvesthisproblembyTSPalgorithmbasedongeneticalgorithmandsimulatedannealingalgorithm．ThearticlegivestheimplementationsofeveryoperatorofgeneticalgorithmandsimulatedannealingalgorithmanddemonstratesthearchitectureandtheimplementationmechanismofthesolvingsystembasedonMATLAB．IprogramandoperatetheresultsbyMATLABsoftware，andcomparetheresultsbasedongeneticalgorithmandsimulatedannealingalgorithm．AnddescribetheiradvantagesanddisadvantagessothatchoosethemostappropriateTSPalgorithmtoachievetheoptimalsolutionfortheshortestpath．Keywords：geneticalgorithm；simulatedannealingalgorithm；TSP；theshortestpath11引言TSP问题为组合优化中的经典问题，已经证明为一NP完全问题[1]，即其最坏情况下的时间复杂性随着问题规模的扩大，按指数方式增长[2]，到目前为止不能找到一个多项式时间的有效算法.TSP问题可描述为:已知n个城市相互之间的距离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才使其所走路线最短.TSP问题不仅仅是一个简单的组合优化问题，其他许多的NP完全问题可以归结为TSP问题，如邮路问题、装配线上的螺帽问题和产品的生产安排问题等，使得TSP问题的有效求解具有重要的意义.本文中的TSP算法主要采用遗传算法与模拟退火算法．遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则[3]．遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉、变异以及进化逆转等运算对个体进行筛选和进化，使适应值大的个体被保留，适应值小的个体被淘汰[4]，新的群体继承了上一代的信息，又优于上一代，这样反复循环，直至满足条件，最后留下来的个体集中分布在最优解的周围，筛选出最优个体作为问题的解．模拟退火算法的出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性[5]，该算法是一种优化算法，其物理退火过程由三部分组成，分别为：加温过程、等温过程、冷却过程．其中，加温过程对应算法设定初温，等温过程对应算法的Metropolis[6]抽样过程，冷却过程对应控制参数的下降．这里能量的变化就是目标函数，要得到的最优解就是能量最低态[7]．Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱．22问题描述本案例为某旅行社为中国十大旅游城市，分别为珠海、西安、杭州、拉