基于人工智能的路径查找优化算法.doc

1、 目 录摘 要IIABSTRACTIIIKEY WORDSIII1.前 言12.概述22.1遗传算法优缺点22.2遗传算法应用领域32.3遗传算法基本流程33.传统遗传算法解决旅行商问题53.1常用概念53.2基本过程53.3关键步骤53.4总结84.改进后的遗传算法94.1编码、设计遗传算子94.2种群初始化94.3评价104.4选择复制104.5交叉114.6变异124.7终结135.系统设计与实现145.1系统设计145.2系统实现175.3结果分析206.总结21参考文献22致谢23基于人工智能的路径查找优化算法摘 要旅行商是一个古老且有趣的问题它可以描述为：给定n个城市以及它们之间的

2、距离dij（城市i到城市j的距离），求解从其中一个城市出发对每个城市访问，且仅访问一次，最后回到出发的城市，应当选取怎样的路线才能使其访问完所有的城市后回到初始的城市且走过的路程最短。旅行商问题已被证明是属优化组合领域的NP难题，而且在现实中的许多问题都可以转化为旅行商问题来加以解决。解决旅行商问题最一般的方法就是枚举出所有可能的路线然后对每一条进行评估最后选取出路程最短的一条即为所求解。解决旅行商问题的各种优化算法都是通过牺牲解的精确性来换取较少的耗时，其他一些启发式的搜索算法则依赖于特定的问题域，缺乏通用性，相比较而言遗传算法是一种通用性很好的全局搜索算法。遗传算法GA( genetic

3、algorithm) 最早由美国密歇根大学的John Holland 提出。具有自组织、自适应、自学习和群体进化功能 有很强的解决问题的能，在许多领域都得到了应用。遗传算法以其广泛的适应性渗透到研究与工程的各个领域，已有专门的遗传算法国际会议，每两年召开一次，如今已开了数次，发表了数千篇论文，对其基本的理论、方法和技巧做了充分的研究。今天，遗传算法的研究已成为国际学术界跨学科的热门话题之一。关键词：人工智能；遗传算法；TSP；旅行商问题Path search system based on artificial intelligence algorithmsAbstractTraveling

4、salesman is an ancient and interesting it can be described as given n cities and the distance between them dij (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

5、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

6、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 s

7、olve 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; TSP231. 前 言现代社会虽然交通发达，两地之间有时甚至可以转瞬既至，但路径问题仍是当今算法界中比较热门的话题，也是一

8、门比较实用的话题，比如现在的导航设备中的导航路线，在现代繁华的大都市中，找寻到一条可行且路程较短的路线并不是一件容易的事，因此为了满足人们的需求，各种搜寻软件应运而生，如， google 的map等。路径问题中一个经典的问题是旅行商问题，也证实了旅行商问题是NP难题，虽然旅行商现在已经拥有了各种解法，结果也很好，但仍是业界追捧的一大话题。本文也是基于旅行商问题来进行研究。本论文先从传统的遗传算法基本原理开始，简单的介绍遗传算法的基本流程和运行机制，然后逐步转变到优化后的遗传算法。本系统是利用人工智能算法中的遗传算法作为算法基础，在其基础上进行了改进，使得可行性更高，性能也提高了，在很大程度上简

9、化了算法的操作，使得算法更稳定、高效。经过改进后的遗传算法实现起来简单，没有复杂的数学运算，且应用灵活，适应用于大量的搜索处理事件。2. 概述近年，随着计算机软硬件的飞速发展，计算机在人类的日常、生活、学习工作中也成为了不可分割的部分。在工作上，某些危险行业或是专业性较强的工作，计算机在慢慢的代替人们作业，而且也比人类做的更好、更有效率。在学习上，国内不管是哪所大学，一进入大学，必学的一门课就是大学计算机基础，然后是一门编程语言。计算机在日常的娱乐、生活也起着不可估量的作用。随着计算机在生活、学习、工作中的分量越来越大，对于计算机的各项性能指标也是要求越来越高，硬件上，追求更快、更安全、更稳定

10、；软件上追求智能、安全、人性化、更美观。随着对软件各项指标的增长，在上世纪发展缓慢的人工智能，现在也突飞猛进的发展了。而本文研究的对象正是最近几年风头正劲的遗传算法在路径选取上的应用。遗传算法(Genetic Algorithm ，GA) 是借鉴生物界自然选择复制和群体进化机制形成的一种全局寻优算法。与传统的优化算法相比，具有的优缺点如下。1.2.2.1. 遗传算法优缺点任何一种算法都不可能十全十美，遗传算法依旧如此，它的优势是可以从多点出发，在解空间内搜寻最优解，而缺点同样较大，首先在编码上，传统的遗传算法是用二进制来编码的。下面从不同角度来对传统的遗传算法的优劣进行分析。1.2.2.1.2

11、.1.1. 遗传算法优点不是从单个点，而是从多个点构成的群体开始搜索。之所以说是从多点而不是从单点出发，那是因为整个算法的开始是从一个初始种群开始搜索演练最优解，是从多个点开始搜索进化寻找，这样的做的一个好处是避免局部寻找最优解，从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。同时也缩短了整个搜寻额时间，整体上效率更高、结果更接近最优解。实现简单，没有复杂的数学计算，在算法中，一般都有大量且复杂的计算作为整个算法的支撑，同时数学计算也是一步比较耗资源和时间的操作，然后在遗传算法中，在搜索最优解过程中，只需要由目

12、标函数值转换得来的适应度信息再加上简单的比较，而不需要导数等其它辅助信息，操作流程也比较简单，没有过多的转换控制操作，中间也没有多少中间变量，算法具有较强的自适应性。搜索过程不易陷入局部最优点。目前，该算法已渗透到许多领域，并成为解决各领域复杂问题的有力工具，因为是在整个求解空间中探索最优解，所以，基本上不会陷入局部最优解中去。在遗传算法中，将问题空间中的决策变量通过一定编码方法表示成遗传空间的一个个体，它是一个基因型串结构数据；同时，可以将目标函数值转换成适应值，它用来评价个体的优劣，并作为遗传操作的依据。但是，传统的遗传算法同样拥有缺陷。2.1.2. 遗传算法缺点首先，传统的遗传算法编码和

13、解码比较复杂，因为传统的遗传算法的染色体是用二进制编制的，一个染色体就是一串0和1组成的位串或是字符串，在进化前需要做复杂的编码工作，而在得到最优解后还要做复杂的解码工作，比较繁琐和复杂，在遗传操作过程中也不易掌控，容易出错；其次，算法对初始种群的选择有一定的依赖性。2.2. 遗传算法应用领域遗传算法在人工智能的众多领域便得到了广泛应用2。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。另一方面，

14、人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。2.3. 遗传算法基本流程因为遗传算法是模拟生物的进化过程的一类人工智能算法，所以，在算法的初始阶段，应该给一个初始种群给算法来进化演练。因此，第一步是初始化种群，在初始化种群时，种群的大小要设计科学，这样才能最大力度的发挥遗传算法的性能。在初始化种群后，就要开始进入遗传演练阶段，遗传的第一步操作是对种群的每个个体计算适应度，然后进入遗传演练。在演练过程中，模仿生物的进化过程，有双亲结合产生下一代个体，为了能够保证种群的多样化和过早的收敛于某一个局部最

15、优解，有了变异操作。在遗传操作过程中，如果某一代中有个体符合最优解的特征，那么整个演练过程就可以提前结束了，否则，遗传演练会一直进行下去，知道收敛于某一个最优解或是到达最大遗传代数。生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止 ？结束图2-1遗传算法流程图本论文的研究则是基于遗传算法的TSP路径问题。3. 传统遗传算法解决旅行商问题3.3.1. 常用概念3.3.1.个体( chromosome)3：遗传算法处理的基本对象，也是遗传基因的载体，是遗传操作中的对象，在遗传操作中，首先将问题的可能解通过编码表示成一定长度符号串。每个位置上的符号称为基因(gene)。一个个对应问题的一个

16、可能解，也被称为染色体(individual)。群体( population)：每一代的个体的集合，一个群体表示了问题在这一代中所有可能解的集合，又称作种群，也称作解空间，在遗传算法中，种群的大小在遗传繁衍过程中一般不会改变，改变的只是其中的个体。适应度( fitness)：个体对环境的适应程度，也是反映问题的目标函数，是操作过程中的一个重要衡量标准。遗传算子：选择后代、遗传后代和变异操作的一个选择参数。3.2. 基本过程算法的基本过程可以表述为：将问题的可能解编码后以字串或数组的方式表示为染色体，在算法的开始部分随机产生一个染色体群体做为初代种群，然后将群体中的染色体个体放在一定的环境中，按

17、照自然进化的适者生存的原则，从中选出适应环境较好的个体，进行复制( reproduction )、交叉( crossover )、变异( mutation )等操作，产生下一代更加适应环境的个体。一代一代的进化，当满足一定的收敛条件时，进化停止，得到问题的最优解( 有可能在局部最优解处收敛)。算法的伪代码如下(t为当前代数， MAXGENS为进化的代数)4：Begint=0;Initialize P (t);Evaluate P (t);While (t 4286751来依次访问各座城市。以该条路线的总路程长度为适应函数f(n)，评价标准是适应度越小，路径越好。这样编码容易理解，对于后续的操作

18、也比较简单，而且也容易计算路程，在变异操作中也容易，只需交换两个城市的位置，效率也比传统的遗传算法中的变异操作高效。最主要的是，在交叉遗传时的检测，不存在复杂的转换工作，只需检查路径中是否有相同的序号，以此来判断路径中是否有重复的城市。遗传算子保留了传统的遗传算法中的设计方式，仍旧采用选取0,1之间的浮点数作为遗传算子，然后来进行比较判断，根据是否满足条件来判断是否能够做下一步操作。4.2. 种群初始化改进后的遗传算法在种群初始化上做了较大改变，初代种群作为整个算法的入口，有必要在上面多多改进。遗传算法与退火算法的结合也体现在此处。此处的结合不是指将退火算法完全整合到遗传算法中，而是摒弃了退火

19、算法中的缺点，选择其优点来弥补遗传算法中的某些步骤，在本系统中，选取了退火算法中的一个重要步骤来产生遗传算法的初始种群，这样有目的的初始化虽然在某种意义上干涉了自然进化，但好处在于，只是干涉了初代，并不妨碍后代的进化。这样做主要是为了克服传统遗传算法中初始化种群的盲目性，这样初始化种群使得初代的原始基因更优秀。甚至，有一定的机率直接产生现阶段已知的最优解。4.3. 评价经过改进后遗传算法，在评价这一步操作，仅仅只是计算出每个个体对应路径的总路程，然后将其排序，方便后续的操作。另外，本系统在计算个体的适应度上有了较大的改进，在传统的遗传算法中，适应度越大代表该个体越优秀，那么同理，在本系统中，也

20、应该是适应度越大那么就越好，然而个体的适应度是基于总路程来计算的，从理论上来讲，路程应该是越短，那么该个体就越优秀，这与遗传算法的适应值得定义背道而驰。为了解决这一大难题，最终想到了，求倒数的方法，计算简单，效果也很明显。基本步骤是，计算出每个个体的总路程之和后，然后求出它们的倒数，为了让后面的选择更顺利、高效，在此处将求得的倒数扩大了几倍，使得每个个体间的倒数差值增大。扩大倒数的方法也很简单，没有什么复杂的计算，只是将每个个体的总路程的倒数扩大1000以上（因为每个个体的总路程的倒数值较小，必须扩大），然后将扩大后的倒数在幂指数级别上扩大，扩大后的值之间的差值均匀且高效。4.4. 选择复制本

21、系统的选择基本上也是同传统的遗传算法一样，采用经典的轮盘赌选择方法。轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：Pi = Fi / 具体操作为：计算群体中所有个体的适应度函数值；利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。本系统在经过改进后，在适应度函数值的计算上有了适当的调整和变化。系统在评价每个个体时就算出了它们个体

22、总路程的倒数，并做了适当放大处理，然后存储起来，并给它命名为伪适应值。在计算每个个体的适应值的时候，先将所有的伪适应值累加起来，得到一个总的伪适应值，然后用每一个伪适应值来除以这个总的伪适应值，获得结果就是最终的适应值。在计算出每一个个体的适应值后，接着就是轮盘选取操作了。轮盘操作是将整个选取范围看做一个圆盘，然后将圆盘按一定的规则划成小块，而每个个体通过适应值被选取的几率范围刚好与那些小块一一重合，然后每次一个小针都从固定的地方旋转来选取个体，适应值越大的个体所占的区域就越大，那么该个体被选取的机会也就越大。而这个区域也不是适应值，先将种群按适应值排序，然后将适应值累加，适应值最小的那个个体

23、的适应值为f1，那么它对应的区域w1则是0,f1，后面的区域wi则是自己的适应值fi加上wi-1，计算公式如下：wi = fi + wi-1图4-1轮盘区域划分图随后，随机产生一个0,1之间的浮点数，来模拟轮盘赌中的指针，根据这个浮点数所在的区间来判断选取个体到下一代中。这种操作的好处是，越优秀的个体，那么它被选取的机会也就越大，这样积累下去，整个种群的进化也是朝着一个良性方向去进化。4.5. 交叉在选取好亲代种群后，接下来便是交叉遗传了，在上面的传统遗传算法的介绍中，已经剖析了传统遗传算法的好与坏，交叉操作在整个遗传过程中是重点中的重点，同时也是难点中的难点。本系统在吸取了前人的经验的基础上

24、做了大量的改进，摒弃了传统遗传算法中不好的地方，吸收了现代的优良设计，使得算法的效率大大提升了。在传统的遗传算法，交叉操作都是基于单点或多点交叉运算，本系统也是基于这种想法，只是具体实现上做了较大改变。具体想法是，首先从两个亲代中随机选取一个基因作为一个子代的开始，也就是这个子代的第一个基因，然后从第二子代开始，每次都随机抽取一个亲代，从中来选择基因，当确定了从哪个亲代中继承基因后，然后从当前子代取得现在已有基因片段的最后一个基因ci，拿到这个基因后找到要继承的亲代中该基因的位置li，然后拿到该位置相邻位置右边的基因，拿到右边的基因后，在子代基因中查看是否已经存在该基因，如果存在，那么就取得亲

25、代li左边的基因，然后同样在子代中查看该基因是否已经存在，如果同样存在，那么重新随机在该亲代中获取一个基因，接着在子代中查看此基因是否已经存在，如果有，则重复，直至找到一个不存在的基因。其它的基因重复上述操作，直至两个子代都产生了，例如，现有两个亲代F1，F2，基因片段分别如下：F1=4,5,2,6,7,3,1,8,9F2=6,2,3,8,7,9,1,5,4对上面两个亲代个体做遗传操作时，预期结果是产生两个子代C1和C2，如果先来产生出C1，先随机抽取一个亲代的一个基因作为C1的第一个基因，随机抽取F1的第二个基因作为C1的第一个基因，那么C1=5，在确定了第一个基因后，再来产生第二个基因，假

26、设这次从第二个亲代F2来继承第二个基因，那么先取得C1最后的一个基因5，然后在F2中找到基因5的位置，拿到基因5右边的基因，此处是4,4在C1中没出现过，所以是合法基因，那么C1=5,4，接着是第三个基因，假如这次是从亲代F1中来继承第三个基因，那么取得C1最后的基因4，再取得F1中4右边的基因5，经过验证后5已经在C1中了，那么就得获取4左边的基因了，然而4已经是最左边了，那么怎么办呢？此处的解决方案是，将F1首尾衔接起来构成一个环，那么4的左边就是9了，9在C1中没出现过，所以C1=5,4,9。重复上述步骤，得到的两个子代C1，C2分别是：C1=5,4,9,1,8,7,3,2,6C2=8,

27、9,1,3,2,6,4,5,7遗传操作的基本思想是优胜劣汰，适者生存，而在选择复制操作过程中，采用的是轮盘赌算法，其理论是适应性越大，那么被选取的几率也就越大，所以在经过选择复制操作后，越优秀的个体在群体中所占的比例也就越大，所以，在群体中，会有大量相同的优秀个体，在传统的遗传算法中，在交叉操作时两个相同的亲代会产生两个如亲代相同的子代。从上面的操作过程和结果可以看出，经过改进后的遗传算法，克服了这一弊端，相同的两个亲代个体也可以产生两个互不相同的子代。如果两个亲代F1、F2都是2,3,4,8,1,7,9,6,5，随机第一个子代C1的第一个基因就是4.6. 变异变异操作在原理和思想上与传统的差

28、别较大，传统的遗传算法是将需要变异的基因中的某个或几个基因做方向操作，进过改进后的遗传算法，个体是用序号串做基因的，所以原来的传统的变异操作在此处不可取，也行不通。所以，在此处，采用了另外的方案，具体操作是，先用变异算子来决定个体是否需要做变异操作，在决定要做变异操作后，传统的遗传算法是随机抽取一个或几个基因进行反向操作，在这里，同样效仿了这种操作，随机抽取两个不同位置的基因，然后将它们的位置交换，已达到变异操作的目的，这种方式简单，效率也比较高。如，个体P1=3,2,5,8,1,4,7,6,9，如果该个体产生的变异随机数符合变异操作，那么针对该个体的变异操作则是，先是产生两个随机数，来确定哪

29、两个地方变异，假如此处的产生的随机数是4和8，那么第4个位子和第8个位子上的基因需交换而来产生经过变异后的个体（设定从0开始编号），此处产生的新个体P2是：P2=3,2,5,8,6,4,7,8,9，可以看出，系统很好的达到了变异的操作效果。4.7. 终结在传统的遗传算法中，本应该是在变异操作过后对种群的个体进行评价，评价完后应该来判断是到达遗传的代数，如果到达遗传的代数在本系统里没有设置终结遗传操作的终结条件，因为在路径寻找中没有一个好的参考条件，路径的搜寻没有固定的最优解，只有更优解，所以，在此处是采用自然终结的方式来终结系统的遗传操作，当然，遗传的代数需要人手动来指定，当遗传的代数到达指定

30、的代数时，本应该是退出系统，但本系统在采用了精英策略，每代繁殖出来后会从中选取最优秀的个体，与以前的最优个体比较，并保留最优秀的那个个体，确保算法最终得到的是整个遗传过程的最优解，以避免错过最优解机会。5. 系统设计与实现因为设计上的需要，系统是用C语言实现的，没有界面图，只有dos的运行界面，现将运行结果展示如下：图5-1程序运行结果图在上面的运行结果图里面，寻找的是中国31个城市之间的最短路径，现在已证实，这31个城市之间的最短路径的路程是15377，而本程序在运行一次的情况下获得最优解是15416，初始种群和末代种群，打印出来的都是每个个体的路径总路程，在最后打印出来的一串数值是代表路径

31、的序号。5.5.1. 系统设计系统采用结构化设计、结构化实现，为了最大限度的体现出遗传算法的各项指标（包括有点和缺点），所以用C语言来实现了此系统。大体流程基本上也是采用的传统遗传算法的流程。为了最大限度的解耦，故将遗传算法的每一个步骤都构成了一个函数，然后在主函数中调用各部分的函数。初始化种群评价种群个体、计算适应度寻找最优个体并保留选择复制交叉遗传突变达到遗传代数？生成新一代终止图5-2改进后遗传算法流程图4.5.5.1.5.1.1. 数据结构设计为了简化后面的操作，容易操控，每座城市都是用序号来表示的，然后将每座城市抽象成一个坐标系中的一个点，所以，城市与城市间的距离就可以转换为坐标系中

32、两个点之间的距离。例如，武汉，序号是1，坐标是(1304, 2312)那么武汉则可表示为1(1304, 2312)，另外，为了使系统更灵活，并没有将这些城市坐标定死，而是写在一个外部文本文件中，在系统运行的初期，会通过文件操作将这些数据加载到程序的几个数组中去，具体数据结构和类型是：double XN_CITIES;double YN_CITIES;double DistancesN_CITIESN_CITIES;其中X,Y是指城市的具体横纵坐标，而Distances则是通过计算后的城市之间的距离，X和Y的维数N_CITIES是一个宏定义常量，表示城市的数量，也是基因的长度，下同。在本系统对遗

33、传算法的实现中，因为采用的是C语言，种群的个体包含的信息太多，为了能够让每个个体容纳下这些这信息，而C语言中的复杂对象数据类型只有结构体、枚举等，此处只有结构体符合条件，所以，系统采用结构体来充当个体，具体的结构体构造是：struct genotypeint pathN_CITIES;/ 表示路径，个体的基因int labelN_CITIES;/ 标记在遗传中是否遗传int localN_CITIES;/ 映射城市在串中的位置int sum_distance;/ 存储该路径的总路程int value;int sum;double fitness;/ 个体的适应度double cdown;dou

34、ble rfitness;/ relative fitnessdouble cfitness;/ curmulation fitness;在上面的结构体中，path表示个体的路径，也是个体的基因所在，其中的值类型是int，因为我们的城市是用序号来表示的，这样做的好处就是可以很方便的从距离数组中取得任意两个城市间的距离；label是一个标志性数组，用来在后期的交叉操作中来判断城市是否已经出现在路径中，当path中的某个位置上出现了一个城市，也就是一个序号，那么label数组中与城市序号对应的下标的位置的值就为1，这样可以免去每次都要扫描每个个体的基因，可以理解为用空间资源换取时间资源，label

35、中的值在种群初始化时都是0，local数组是存放个体中每个基因（城市序号）在path中的位置，这样设计是为了在后期的交叉操作中不用遍历去寻找某个基因，而是直接根据位置来索引，这样做的好处是同样节省了搜寻时间。sum_distance则是存储个体的总路程，在整个遗传操作中占有很重要的作用；fitness、cdown、rfitness则是在计算和存储适应度上起作用。至于没用的几个属性，则是扩展属性，给系统留有发展的空间。系统中，种群是用一个全局的genotype来表示的：struct genotype populationPOPSIZE+1;struct genotype newpopulationPOPSIZE+1;其中，population表示当前种群，种群有宏POPSIZE来确定，种群实际大小要比宏POPSIZE大一个单位，是为了保存每一代的精英个体。newpopulation是一个临时种群，主要在交叉遗传和选择复制中起辅助作用。5.1.2. 模块设计因为系统采用结构化设计，所以，对应于每个模块都设计了一个函数，以此来符合结构化实现和设计。系统包含的所有函数有：表5-1系统函数说明表