文档介绍：基于遗传算法的最短路径探索摘要:最短路径问题是图论中的典型问题,它在生产和生活中具有广泛的实例。本文对遗传算法求解最短路径问题作了有益的尝试,详细分析了求解最佳路径的遗传算法的构成要素,着重探讨遗传算法求解最短路径问题的可行性。关键词:遗传算法;最短路径;适应函数;选择;交叉;变异;icalgorithmsAbstract:Asthedevelopmentofhumansociety,peoplearefortherequestonproblemsolvingdoesnotmerelystopatthepointoffeasibility,butturnstoconcision,’sneedsforthegeneralstudyandlife,butalsorequiresusingtheleastresources,suchastimeandspace,,icalgorithm,:icalgorithm;shortestpath;feasibility1引言遗传算法(icalgorithm,下面简称GA)是基于生物进化原理的一种全局性优化算法,是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法,是生物遗传技术和计算机技术结合的产物。它采用的是启发性知识的智能搜索算法,在高空间复杂问题上比以往有更好的结果。它提供给我们的是一种通用的算法框架,具有很强的适应性,对特殊问题提供了极大的灵活性。GIS领域中所涉及的很多有关最优化问题的算法具备了遗传算法的结构特征,这些问题包括最佳路径分析、资源分配、连通分析、流分析以及决策支持系统中的决策理论等。本文选择了其中最富有代表性的最短路径问题,着重探讨遗传算法求解最短路径问题的可行性。最短路径问题是图论中的一个典范问题。从网络模型的角度看最短路径分析就是在指定网络的两节点间找一条阻碍强度最小的路径。但最短路径的含义并不是地理位置的最短距离,还可以引申到其它的度量,如:时间、费用、容量等,实际中常用于车载导航系统及各种城市应急系统中。最短路径问题通常有两类:一类是求取从某一源点到其余各点的最短路径,另一类是求取每一对顶点之间的最短路径。目前的研究工作主要集中于算法实现的优化改进与应用方面。最短路径计算分静态最短路计算和动态最短路计算。静态路径最短路是外界环境不变,计算最短路径。主要有Dijkstra算法,A*算法。动态路径最短路是外界环境不断发生变化,即不能计算预测的情况下计算最短路径。最短路径问题,用图论术语描述如下:在图G(V,A)=(v,v,…,v)对G中的某一条边(v,v).相应地有一个数d(v,v)。如果G中不存在边(v,v),则令d(v,v)=∞,如把d(v,v)认为是边(v,v)的长度(也可认为是边(v,v)的费用或权),则路的长度定义为组成路的各条边的长度的总和。顶点v,v之间是否有边相连,由邻接矩阵来决定。邻接矩阵A:对一个具有V个顶点,e条边的图G的邻接矩阵A=[a]是一个v*v阶方阵,其中a=1,表示v和v邻接,a=0,表示v和v不相邻接(或i=j)。2最