毕业设计[论文]
题目：基于人工智能的路径查找优化算法
学生姓名： Weston 学号：090171021XXX
学部（系）：信息科学与技术学部
专业年级：计算机应用技术
指导教师：XXX 职称或学位： XX
2012 年 5 月 18 日
目录
摘要 (II)
ABSTRACT (III)
KEY WORDS (III)
1.前言 (1)
2.概述 (2)
2.1遗传算法优缺点 (2)
2.2遗传算法应用领域 (3)
2.3遗传算法基本流程 (3)
3.传统遗传算法解决旅行商问题 (5)
3.1常用概念 (5)
3.2基本过程 (5)
3.3关键步骤 (5)
3.4总结 (8)
4.改进后的遗传算法 (9)
4.1编码、设计遗传算子 (9)
4.2种群初始化 (9)
4.3评价 (10)
4.4选择复制 (10)
4.5交叉 (11)
4.6变异 (12)
4.7终结 (13)
5.系统设计与实现 (14)
5.1系统设计 (14)
5.2系统实现 (17)
5.3结果分析 (20)
6.总结 (21)
参考文献 (22)
致谢 (23)
基于人工智能的路径查找优化算法
摘要
旅行商是一个古老且有趣的问题它可以描述为：给定n个城市以及它们之间的距离（城市i到城市j的距离），求解从其中一个城市出发对每个城市访问，且仅访问一d
ij
次，最后回到出发的城市，应当选取怎样的路线才能使其访问完所有的城市后回到初始的城市且走过的路程最短。
旅行商问题已被证明是属优化组合领域的NP难题，而且在现实中的许多问题都可以转化为旅行商问题来加以解决。
解决旅行商问题最一般的方法就是枚举出所有可能的路线然后对每一条进行评估最后选取出路程最短的一条即为所求解。
解决旅行商问题的各种优化算法都是通过牺牲解的精确性来换取较少的耗时，其他一些启发式的搜索算法则依赖于特定的问题域，缺乏通用性，相比较而言遗传算法是一种通用性很好的全局搜索算法。
遗传算法GA( genetic algorithm) 最早由美国密歇根大学的John Holland 提出。
具有自组织、自适应、自学习和群体进化功能有很强的解决问题的能，在许多领域都得到了应用。
遗传算法以其广泛的适应性渗透到研究与工程的各个领域，已有专门的遗传算法国际会议，每两年召开一次，如今已开了数次，发表了数千篇论文，对其基本的理论、方法和技巧做了充分的研究。
今天，遗传算法的研究已成为国际学术界跨学科的热门话题之一。
关键词：人工智能；遗传算法；TSP；旅行商问题
Path search system based on artificial intelligence
algorithms
Abstract
Traveling salesman is an ancient and interesting it can be described as given n cities and the distance between them d ij (city i to city j, the distance), solving the access for each city, starting from one of the city and only one visit and finally back to the starting city, should select what route it back to the initial visit all the cities city and traveled the shortest.
Various optimization algorithms to solve the traveling salesman problem through the expense of the accuracy of the solution in exchange for less time-consuming, other heuristic search algorithm depends on the specific problem domain lack of universal so the genetic algorithm is compared to a common good global search algorithm.
GA( genetic algorithm) Was first proposed by John Holland of the University of Michigan. The GA has self-organizing, adaptive, self-learning and group evolution function so the GA has strong ability to solve problems, now the GA been applied in many fields.
Today, the genetic algorithm research has become one of the hot topics of the international academic community interdisciplinary.
Key words: Artificial Intelligence; Genetic Algorithm; TSP
1.前言
现代社会虽然交通发达，两地之间有时甚至可以转瞬既至，但路径问题仍是当今算法界中比较热门的话题，也是一门比较实用的话题，比如现在的导航设备中的导航路线，在现代繁华的大都市中，找寻到一条可行且路程较短的路线并不是一件容易的事，因此为了满足人们的需求，各种搜寻软件应运而生，如，google 的map等。
路径问题中一个经典的问题是旅行商问题，也证实了旅行商问题是NP难题，虽然旅行商现在已经拥有了各种解法，结果也很好，但仍是业界追捧的一大话题。
本文也是基于旅行商问题来进行研究。
本论文先从传统的遗传算法基本原理开始，简单的介绍遗传算法的基本流程和运行机制，然后逐步转变到优化后的遗传算法。
本系统是利用人工智能算法中的遗传算法作为算法基础，在其基础上进行了改进，使得可行性更高，性能也提高了，在很大程度上简化了算法的操作，使得算法更稳定、高效。
经过改进后的遗传算法实现起来简单，没有复杂的数学运算，且应用灵活，适应用于大量的搜索处理事件。