基于遗传算法的网络路径分析-地图学与地理信息系统专业论文.docx

Network Network Analysis Based on Genetic Analysis Major：CartographyGeographical Information System Name：Zhang Kan Supervisor：Zhang Qingnian,Associate Professor Abstract Network analysis is one of the fundamental functions of GeoKraphic Information System(GfS)，which is based on the resolving of path．Genetic algorithm of artificial intelligence technique is useful tooI to solve the optimization problems in modern times．To resolve path problems using genetic analysis provide us another method．It uses the random research method which can converge to the optimal solution and let us not to for the detail of the resolved problem．So it has many characteristics such simple realizing thinking,simple program designing and omitting to study the detail process． Firstly this dissertation discussed researches of the traditional and classical shortest path algorithm,and realized to resolve experimentaI data of shortest path with computer advanced language．Then it gained the process of resolving shortest path with genetic algorithm and realized to resolve shortest path of more complex network with computer aided tool MATLAB by the research of genetic algorithm．After discussion of Dijkstra algorithm and genetic algorithm solution method，the dissertation compared with the two methods and gained the merits using genetic algorithm．In addition to the above,the dissertation resolved the shortest path and display to the national rail way network of GIS． Besides,this dissertation also researched the TSP{Traveling Salesman Problem)of NP complex problem,and realized to solution to China 81 cities TSP in MATLAB environment． The characteristics of this dissertafton as follows．It adopted the priority-based encoding,the cross—over and mutation operator which are conformable to this type problem,to resolve path problems of GIS with genetic algorithm and realized with MATLAB．Through a large amount of experiments，it gained we should adopt different encoding and operator to different complex scal