遗传算法在求解最短路径问题中的研究应用.docx

遗传算法在求解最短路径问题中的研究应用

摘要

TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种常用方法。本文针对解决TSP问题,在MATLAB中用遗传算法施行对TSP问题进行了求解，进行了选择、交叉和变异算子进行了算法设计，最后在JAVA软件上进行编程实现。最后探讨了遗传算法解决旅行商问题自身具备的特点[1]。

关键词：遗传算法；TSP问题；JAVA软件
SOLVINGTSP(TravellingSalesmanProblem)BASEDONGENETICALGORITHM

Author:ZongMan-yi
Tutor:QiaoLi-hong
Abstract
TSP(TravelingSalesmanProblem)isatypicalNPcompleteproblem,geneticalgorithmistheperfectmethodforsolvingNPcompleteproblem.ThispaperusegeneticalgorithmintheMATLABsoftwaretosolvetheatypicalTSPproblem.ItprobesintotherealizationofgeneticoperatorprogramthroughTSPsolvingbygeneticalgorithm,designtheeachfunctionofeachgeneticoperator(select,intercross,mutate).Finally,WeprogramminMatlablanguageanddiscussthecharacteristicofgeneticalgorithminsolvingTSP

Keywords:geneticalgorithm;TSPJAVA;

目录
TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc185778015"引言 PAGEREF_Toc185778015\h4
HYPERLINK\l"_Toc185778016"1GA概述 PAGEREF_Toc185778016\h4
HYPERLINK\l"_Toc185778017"2旅行商问题(TSP) PAGEREF_Toc185778017\h4
HYPERLINK\l"_Toc185778018"3用遗传算法解决旅行商问题 PAGEREF_Toc185778018\h5
HYPERLINK\l"_Toc185778019"4论文的主要构成 PAGEREF_Toc185778019\h5
HYPERLINK\l"_Toc185778020"遗传算法的设计 PAGEREF_Toc185778020\h6
HYPERLINK\l"_Toc185778021"1问题分析 PAGEREF_Toc185778021\h6
HYPERLINK\l"_Toc185778022"2总体设计 PAGEREF_Toc185778022\h7
HYPERLINK\l"_Toc185778023"3详细设计 PAGEREF_Toc185778023\h8
HYPERLINK\l"_Toc185778024"3.1编码与随机和初始群体生成 PAGEREF_Toc185778024\h8
HYPERLINK\l"_Toc185778025"3.2城市位置及距离矩阵和适应度函数 PAGEREF_Toc185778025\h8
HYPERLINK\l"_Toc185778026"3.4选择 PAGEREF_Toc185778026\h9
HYPERLINK\l"_Toc185778027"3.4交叉 PAGEREF_Toc185778027\h9
HYPERLINK\l"_Toc185778028"3.5变异 PAGEREF_Toc185778028\h10
HYPERLINK\l"_Toc185778029"3.6群体的跟新和终止条件 PAGEREF_Toc185778029\h10
HYPERLINK\l"_Toc185778030"MATLAB编程验证 PAGEREF_Toc185778030\h11
HYPERLINK\l"_Toc185778031"1MATLAB计算 PAGEREF_Toc185778031\h11
HYPERLINK\l"_Toc185778032"2算法分析优化 PAGEREF_Toc185778032\h13
HYPERLINK\l"_Toc18