CN103324982A - 一种基于遗传算法的路径规划方法 - Google Patents

Abstract

一种基于遗传算法的路径规划方法，包括以下步骤：（1）建立路径优化数学模型，具体如下：设G为一条从起点1到达终点n的路径，路径G不包含重复路线和巡回路线，一条路线的耗费是这条线路上的权值之和；（2）路径搜索过程，具体如下：从起点开始，在搜索半径范围内采用遗传算法搜索一条最优路径，随着车辆移动到前一次搜索所得路径的下一个节点，以此节点作为当前搜索的起点，再次以搜索半径范围内的节点重新搜索出一条路径，不断实施此方法，直到搜索到目的地点。本发明提供了一种快速性良好、稳定性较好、适用性强的基于遗传算法的路径规划方法。

Description

一种基于遗传算法的路径规划方法

技术领域

本发明涉及一种路径规划方法。

背景技术

随着网络购物、电视购物之兴起，物流行业得到快速发展，物流业之间的竞争也不断加剧。物流成本和周期的缩短主要集中在路径的优化上。选择出最优路径已经成为物流企业最为迫切的需求。另一方面，城市交通工具数量迅速增长，引发了交通堵塞、交通事故、环境污染等一系列问题。动态路径选择是城市交通流诱导系统UTFGS(Urban Traffic Flow Guidance System)的核心。它主要解决的问题是：以实时的路况信息和交通需求为输入，在一定的优化目标下，为车辆提供最合理的行驶路线。这些问题都可以描述为最短路径问题。遗传算法已经成为解决此类问题的主流方法。

对于需要整数排列编码方式的问题，传统的遗传算法交叉或变异的时候可能会产生非法个体。随机键(random keys)编码方式对于解决此类问题是很有用的。

1985年，Goldberg等针对旅行商问题(TSP)提出了基于路径表示的部分匹配交叉(PMX)操作，PMX要求随机选取的两个交叉点，以便确定一个匹配度，根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个合法的子个体。

在路由选择算法中都要用到求最短路径算法。这类问题的已知条件是整个网络拓扑和各链路的长度。若将已知的各链路长度改为链路时延或费用，这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。

传统的路径优化算法以Dijkstra算法、Floyd算法为代表。Dijkstra算法适合于计算两点间的最短路径问题。但Dijkstra算法由于在计算时间、存储空间等方面存在很多不足，计算效率和存储效率都比较低。另一方面，这种方法对于具有各种特殊约束的网络将会无能为力。

Dijkstra算法能够在多项式时间内解决最短路径问题，它们在固定基础设施的无线或有限网络中是有效的。但是，它在涉及快速变化的网络拓扑的实时通信中展现了令人无法接受的高的计算复杂度。最短路径问题涉及了一个传统的在多种设计和计划环境中提出的组合优化问题。因为神经网络和遗传算法承诺了解决此类复杂问题。另一方面，神经网络和遗传算法也可能不是在移动ad hoc网络中解决实时应用的很好方法，因为它们一般涉及到大量的迭代。然而，神经网络和遗传算法的硬件的启用是非常快的。此外，它们对于网络规模不敏感。遗传算法解的质量可以作为种群大小的函数来调整。遗传算法硬件使用到甚至内存容不下的网络中。它通过几个节点采用并行遗传算法实现。

针对解决网络的路由问题，有人已经提出一个变长度染色体的遗传算法。染色体包含一个由正整数组成的序列，代表了一个路径。染色体的位置代表了节点在路径中被访问的次序。第一个和最后一个基因总是分别保存源节点和目的地节点。染色体的长度是可变的。一个染色体(路径)通过陈列节点的IDs—从源节点到目的节点，基于网络的拓扑信息库(路由表)。网络的拓扑信息库可以通过路由协议，例如RIP、OSFP、DSDV、DSR和VCRP轻松地得到和实时管理。

Dijkstra算法是按路径长度递增的次序来产生最短路径的算法。该算法的基本思想是，设置两个节点集合S和V，分别为已标记节点集合和未标记节点集合。初始状态时，集合S只包含源点V₀，集合V包含除源点V₀外的所有节点。然后按路径长度递增的顺序逐个把V集合中的节点加到S集合中去。集合S每加入一个节点V_j，都要比较计算更新源点V₀到集合V中剩余各节点的最短路径长度值。反复迭代,直至集合V中节点全部加入到S中为止。

目前，在路径规划方面，一般采用在全局范围内搜索最优路径，但在全局范围内只取少量的点。这对于解决交通路径优化没有很强的实用性。现有的各种启发式计算方法，在实时性方面有所欠缺。

发明内容

为了克服已有路径规划方法的快速性较差、稳定性较差、适用性不强的不足，本发明提供了一种快速性良好、稳定性较好、适用性强的基于遗传算法的路径规划方法。

本发明解决其技术问题所采用的技术方案是：

一种基于遗传算法的路径规划方法，所述规划方法包括以下步骤：

（1）建立路径优化数学模型，具体如下：

设V={1,2,3,…,n}表示路口的集合，其中n＞1为路口个数；E为路段的集合。设G=(V,E)是带正权的完全图；路段i→j为节点i,j之间的连接，权值为距离d_ij；c_ij表示它的可连接性，其中c_ij=1表示i到j可直接到达，c_ij=∞表示i到j不可直接到达；x_ij表示路段i→j是否包含在路径中；

设G为一条从起点1到达终点n的路径，路径G不包含重复路线和巡回路线；

标记当前节点的编号为1，在搜索半径内的所有节点依次编号为2,3,...,n-1，终点编号为节点n，求解x_ij：

${\min }_{x_{\mathrm{ij}}}F={\mathrm{\Σ}}_{i=1}^{n-1}{\mathrm{\Σ}}_{j=2,i\≠j}^n{x}_{\mathrm{ij}}{c}_{\mathrm{ij}}{g}_{\mathrm{ij}}{s}_{\mathrm{ij}}{d}_{\mathrm{ij}}---\left(1\right)$

s.t.

${\mathrm{\Σ}}_{i\≠j}^n{x}_{\mathrm{ij}}\≤1,j=\mathrm{2,3},...,n,---\left(4\right)$

${\mathrm{\Σ}}_{j\≠i}^n{x}_{\mathrm{ij}}\≤1,i=\mathrm{2,3},...,n,---\left(5\right)$

${\mathrm{\Σ}}_{j=2}^n{x}_{1j}=1,---\left(6\right)$

${\mathrm{\Σ}}_{j=1}^{n-1}{x}_{\mathrm{jn}}=1,---\left(7\right)$

上式中：

g_ij为道路等级系数，车道越多，该系数越小；

s_ij为交通拥堵系数，拥堵越严重，该系数越大；

d_ij用计算欧式距离通过i,j的坐标得到；

c_ij表示i,j两点之间的道路连接状况，当两点之间有道路导通时就设权值c_ij=1，两点之间没有道路导通时设定权值c_ij=∞；

x_ij表示边i→j是否在所搜索到的路径上；

式(3),(4)为了控制不出现重复路线和巡回路线，

确保路径所对应的矩阵的行最多只能产生一个1，

确保矩阵列的列只能产生一个1，式(6),(7)为了确保路径从起点1出发，到终点n结束。

（2）路径搜索过程，具体如下：

从起点开始，在搜索半径范围内采用遗传算法搜索一条最优路径，随着车辆移动到前一次搜索所得路径的下一个节点，以此节点作为当前搜索的起点，再次以搜索半径范围内的节点重新搜索出一条路径，不断实施此方法，直到搜索到目的地点。

进一步，所述步骤（2）中，遗传算法的处理过程如下：

2.1)设置运行参数：种群大小N，均匀变异概率p_m，节点数n；

2.2)采用半随机化方式产生初始种群

2.2.1)采用传统的路径表示方式或者随机键表示方式初始化种群；

2.2.2)非法个体修复；

2.3)评价各个个体的适应度；

2.4)精英保留：把群体中的最好的(0.05～0.2)N的个体保留，记为P₁；

2.5)交叉操作：

2.5.1)规模为2的锦标赛选择；

2.5.2)单点交叉；

2.6）对于交叉产生的后代进行变异操作：

2.6.1)(80～95)%的个体采用单点变异加上交换变异；

2.6.2)(5～15)%的个体采用均匀变异；

2.6.3)非法个体修复；

2.7)评价各个个体的适应度，并保留(0.7～0.9)N最优个体，记为P₂；

2.8)对P₂中最优秀的(0.05～0.15)N个体进行自学习，产生P₃；

2.9)每10代产生(0.05～0.15)N个体，记为P₄，检查P₂中适应度最大且相同的所有个体，如果他们的染色体完全相同，保留一个，其他全部被替代，同时也淘汰P₂中适应度最差的个体，更新后的P₂的种群大小为(0.6～0.8)N；

2.10)产生新一代群体：P₁∪P₂∪P₃∪P₄；

2.11)检验算法是否收敛或者达到指定的代数：

2.11.1)是，保存结果，结束搜索；

2.11.2)否，返回步骤2.3)；

2.12)结束。

本发明的有益效果主要表现在：快速性良好、稳定性较好、适用性强。

附图说明

图1是搜索策略原理图。

图2是遗传算法流程图。

图3是例2的Matlab生成的路径仿真图。

图4是例3的Matlab重新生成的路径仿真图。

图5是例4的Matlab重新生成的五十个路口随机交通网络图。

图6是例5中Matlab生成的交通网络图以及用动态规划法获得的最优路径示意图。

具体实施方式

下面结合附图对本发明作进一步描述。

参照图1～图6，一种基于遗传算法的路径规划方法，所述规划方法包括以下步骤：

（1）建立路径优化数学模型，具体如下：

路径优化问题类似于旅行商问题(TSP)。设V={1,2,3,…,n}表示节点(路口)的集合，其中n＞1为路口个数；E为路段的集合。设G=(V,E)是带正权的图；边(路段)i→j为节点i,j之间的连接，权值为距离d_ij；c_ij表示它的可连接性，其中c_ij=1表示i到j可直接到达，c_ij=∞表示i到j不可直接到达；x_ij表示路段i→j是否包含在路径中。

设G为一条从起点1到达终点n的路径，路径G不包含重复路线和巡回路线。一条路线的耗费是这条线路上的权值之和。我们的目标是最小化从节点1到n的路径的等效距离。

我们标记当前节点的编号为1。在搜索半径内的所有节点依次编号为2,3,...,n-1，终点编号为节点n。求解x_ij：

${\min }_{x_{\mathrm{ij}}}F={\mathrm{\Σ}}_{i=1}^{n-1}{\mathrm{\Σ}}_{j=2,i\≠j}^n{x}_{\mathrm{ij}}{c}_{\mathrm{ij}}{g}_{\mathrm{ij}}{s}_{\mathrm{ij}}{d}_{\mathrm{ij}}---\left(1\right)$

s.t.

${\mathrm{\Σ}}_{i\≠j}^n{x}_{\mathrm{ij}}\≤1,j=\mathrm{2,3},...,n,---\left(4\right)$

${\mathrm{\Σ}}_{j\≠i}^n{x}_{\mathrm{ij}}\≤1,i=\mathrm{2,3},...,n,---\left(5\right)$

${\mathrm{\Σ}}_{j=2}^n{x}_{1j}=1,---\left(6\right)$

${\mathrm{\Σ}}_{j=1}^{n-1}{x}_{\mathrm{jn}}=1,---\left(7\right)$

上式中：

d_ij用计算欧式距离通过i,j的坐标得到。

c_ij表示i,j两点之间的道路连接状况。当两点之间有道路导通时就设权值c_ij=1，两点之间没有道路导通时设定权值c_ij=∞。比如单行道i→j，其前向是通行的，c_ij=1，逆向不通，c_ji=∞。为了实施方便，通常∞用一个较大的数如10⁴替代。路网的缺省状态是双向通行。

g_ij表示从节点i到j的道路等级。通常双车道为标准车道数。缺省状态是双车道。

s_ij表示从节点i到j的交通状态，有畅通、繁忙、拥堵三种状态。缺省状态为畅通。

x_ij表示边i→j是否在所搜索到的路径上。例如1→4→7→5→17→21,这样一条路径可以形成一个21×21的矩阵，其中

x_1,4=x_4,7=x_7,5=x_s,17=x_17,21=1，其余元素都为0。

式(4)、(5)为了控制不出现重复路线和巡回路线。

确保路径所对应的矩阵的行最多只能产生一个1，

确保矩阵列的列只能产生一个1。式(6)、(6)为了确保路径从起点1出发，到终点n结束。

（2）路径搜索过程，具体如下：

从起点开始，在搜索半径范围内搜索一条最优路径。随着车辆移动到前一次搜索所得路径的下一个节点，以此节点作为当前搜索的起点，再次以搜索半径范围内的节点重新搜索出一条路径。不断实施此方法，直到搜索到目的地点。

对于节点数量很大的情况，这种方法是一个非常有效的分治(divide-and-conquer)方法。比如，对于从杭州到北京的道路诱导，涉及到的节点数以万计，车载的诱导设备无论在存储空间和计算能力上都难以满足要求。采用分治的方法可以有效地把一个大问题分解成很多小问题逐一解决。

对于每个子问题，此时，在一定搜索半径范围内搜索时，假定这个范围内的点与搜索范围外的未知点相连，如图1中的16,18,19,24,25,26,28等几点，则设定这些点与终点29有路径导通。图中以点1为起点，点29为所要达到的终点。图中的圆为搜索范围，以起点1为圆心，半径20。节点间的线段为已知路段，可以从地理信息系统中获取。一端为节点的路段为未知路段，即搜索范围内的点与搜索范围以外的某点相连。

另一种策略可以取代上述分治策略。在长途路径规划，比如从杭州到北京，涉及到的道路的路口可能数以万计。为了考虑问题的可解性，我们可以考虑在20公里半径范围内（杭州市内）的所有路口，超出此范围内，我们只计入高速或国道路口，以及在到达北京之后的局部路径规划。

每个节点可以用三元数组(m,x,y)来表示，其中m为编号，(x,y)表示坐标。根据交通部实施的《公路工程技术标准》，公路主要分为以下几个等级：高速公路、一级公路、二级公路、三级公路、四级公路。

遗传算法是一种模仿生物进化机制的随机全局搜索和优化方法。它借鉴了达尔文的进化论、孟菲尔的遗传学说和魏兹曼的自然选择原理。遗传算法是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获得和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法操作使用适者生存的原则，在潜在的解的种群中逐次产生优秀的解。遗传算法步骤主要包括初始种群的生成、适应度值评价检测、选择、交叉、变异、终止条件判断。算法流程如图2所示。当算法收敛或者循环到指定的代数时，终止算法，得到最优值。

编码和解码：这里考虑两种路径表示方式：直接表示方法和随机键编码方式。对于直接表示法，用整数编码路口编号，以各个节点到起点的距离由近到远进行依次编码。始终以1表示路径的起点，个体（染色体）就是一个解或一条路径，个体长度是指连同起点、终点在内的所有点的个数。对于n节点情况，染色体长度为n。因为路径表示为全排列，所以在每一条路径表示中随机填0。例如一条染色体(1,3,0,6,0,2,0,0,0,0,0,0,4,0,0,0,0,0,0,0,21)，可以简写为(1,3,6,2,4,21)或1→3→6→2→4→21，表示从起点(编号为1)顺序经过路口3,6,2,4，到达终点（编号为21）。

路径表示(染色体)可解码为n×n二进制矩阵[x_ij]。染色体非0位置相邻两位分别为行序号和列序号，在此位置赋值为1，其余位置赋值为0。对上述染色体，矩阵元素x_1,3=x_3,6=x_6,2=x_2,4=x_4,21=1，矩阵其余元素都赋值0。

对于随机键编码的染色体，染色体各个基因是区间(0,1)内的一个随机数。将其解码为路径表示，但是产生的是排列，没有0，随机填入0。然后，再解码成n×n二进制矩阵[x_ij]。

种群初始化和非法个体修复：随机产生初始种群。设定种群中个体数N。确定初始种群中个体的长度为节点数n。每个个体为一个1×n的随机行向量，其第一个个体是1，第n个个体是n，其余个体是从2到n-1之间的一个随机整数。随机产生的个体一般不是合法的个体。

非法个体修复能够确保将非法个体合法化。随机产生的个体可能会有大量重复整数，初始化的任务就是去除相同的节点，只保留一个，将后出现的基因强赋值为0，以保证没有重复路段。并且一条路径只有中间路段未知。例如路口数为8，如果个体为(2,5,2,8,4,2,7,6)，经过修复处理后变为(1,5,2,0,4,0,7,8)，代表路径1→5→2→4→7→8。对于染色体中相同的基因，将其所有基因位取出，随机保留一个基因位，其余的填0(删除)。这样可确保非零基因均匀分布在染色体中。

节点的编号规则是，距离起点1越近的节点编号越小。所以，离起点1近的节点应该比较小，离终点n近的节点应该比较大。从而，可以采用如下半随机方法产生初始种群。例如，对于100节点的路网，将种群分为两组。第一组把染色体分成三个片段（去除起点1和终点n），前32个基因位填入在[2,33]中随机整数，其后34个基因位填入在[34,67]中随机数，在最后32个基因位填入在[68,99]的随机整数。第二组把染色体分成两个片段（去除起点1和终点n），前49个基因位填入在[2,50]中随机整数，后49个基因位填入在[51,99]的随机整数。产生的染色体是在[2,99]中产生随机整数填入所有中间98个基因位。采用这两组的个体占所产生的所有个体各一半。

计算种群的适应度：首先将预处理后的染色体(路径)解码为矩阵表示[x_ij]，再计算目标函数 $F={\mathrm{\Σ}}_{i=1}^{n-1}{\mathrm{\Σ}}_{j=2,i\≠j}^n{x}_{\mathrm{ij}}{c}_{\mathrm{ij}}{g}_{\mathrm{ij}}{s}_{\mathrm{ij}}{d}_{\mathrm{ij}}$ 为目标函数。我们的目标是取值越小越好，而遗传算法要求最优个体的适应度值最高，所以适应度函数可定义为fitness=F_max-F，F_max可选为一个较大参数如10⁶。或者，可取fitness=1/F。

遗传操作：遗传操作主要包括选择、交叉、变异、个体自学习这几个步骤。个体自学习可以看作是一种变异操作。

1)精英保留的选择策略。首先进行排序，把最好的个体留在种群中，作为产生下一代的种子。选择最好的10%直接留到下一代的种群。

2)竞赛规模为2的锦标赛选择策略。每次随机选择两个合法个体，把较好的个体用于下一步的交叉操作。

3)对选择出来的种群进行单点交叉操作。在两条染色体上随机选择出一个点位，交换点位后面的基因片段。对个体进行两两配对，种群大小为N，则共有N/2对互相配对个体组。对每对互相配对的个体，随机设置某一基因座之后的位置为交叉点。交叉之后产生的个体可能是非法个体，需要修复成合法个体。

4)对于合法或者非法个体可以实施变异操作。

单点变异是除起点1和终点n外的随机选择个体的一个变异位置，从0,2至n-1中随机选取一个数代替原来的值。变异之后产生的个体可能是非法个体，需要修复成合法个体。

交换变异则是除起点1和终点n外的随机选择一点，然后选择与其对称的点进行比较，如果左边小于右边，则不变；如果左边大于右边，则互换。这样不会产生非法个体。

均匀变异是指依次对个体中各个基因座上的原有基因值按照概率p_m用在某一范围内均匀分布的随机数来替换。对于路径编码，均匀变异则是除起点1和终点n外对个体的每个基因座，以变异概率指定其为变异点。对每个指定的变异点，对其基因值从0,2至n-1中随机选取一个数代替原来的值。变异之后产生的个体可能是非法个体，需要修复成合法个体。

5)对于合法个体进行自学习。从染色体中随机抽取一个基因位，对此位置基因依次赋值0到n-1，产生n条染色体，丢弃其中的非法染色体。计算所有合法个体的适应度，从中选取适应度最佳的个体代替原来的个体。

6)对经过自学习的种群进行适应度计算，采用最佳保留的策略选取下一代种群。

有两种基本的选择策略模式：按比例的和排序的选择。按比例的选择基于染色体相对于种群其他染色体的适应度来挑选个体。这样的选择类型包括轮盘赌选择、随机剩余选择和随机遍历选择。基于排序的选择模式不根据它们的适应度值来选择染色体，而是根据它们在种群中的适应度值排序。锦标赛选择、(μ,λ)选择、截断选择和线性排序选择都是基于这种排序的选择类型。

没有重复的锦标赛选择被认为有更小的选择噪声。它通过在种群中选择含有S个个体的不重叠的随机集合，然后在每个集合中选择最优的染色体作为一个父体进入下一代。典型地，锦标赛的规模一般是2。而且，竞赛规模S越大，选择强度越大。考虑到选择强度是选择后的种群的期望的平均适应度。当选择强度增加时，产生错误解的概率以指数方式增加，虽然遗传算法可能会收敛的更快。对于没有重复的规模为2的锦标赛选择：选择两个个体出来，适应值好的被选择。相同的染色体不能被选为父体两次。

对于采用随机键编码的个体，交叉操作可以直接对为解码的个体进行线性重组。子个体的产生用下式表示：

$x_1^{\′}={\mathrm{\λx}}_1+(1-\mathrm{\λ})x_2,---\left(1\right)$

$x_2^{\′}={\mathrm{\λx}}_2+(1-\mathrm{\λ})x_1,---\left(2\right)$

其中，λ∈(0,1)是一个均匀分布随机数。其后的变异操作可以对随机键编码状态的个体进行，以(0,1)之间随机数来替换变异基因。当然，也可以将随机键解码为路径表示之后再进行交叉和变异操作。

每代的迭代操作中，由三组个体构成下一代。第一组，从当前代中选择10%的个体通过复制直接进入下一代。第二组，从当前代中通过交叉加上变异操作产生下一代所需的80%的个体。第三组，在第二组产生的最优10%的个体通过自学习进入下一代。

在计算过程后期，会出现局部收敛的情况，所有个体具有相同或基本相同的染色体，此时他们的适应度也相同。为了避免这种情况，把最大适应度的所有个体进行比较，判断它们是否完全相同；如果完全相同，保留其中的一个个体，并将其他个体替换成随机产生的个体。

以上算法中的交叉、变异、自学习操作都可以对路径表示和随机键表示分别进行。对于随机键表示，每次产生的是一条包含所有节点的完整路径，这需要随机地或者设定规则来删除一些节点。

本实施例给出5个算法仿真例，其中参数X_max=10⁶。

【例1】图1是n=29个节点例子。我们选取遗传代数T=100，种群大小N=200，均匀变异概率p_m=0.03。获取路径1→6→26→29，路程长度47.4，消耗时间0.37s。

【例2】由SUMO随机产生的20个节点。图中编号离路口1越近的路口编号越小。图中所画均为双行线。用SUMO软件读取的20个节点的xy坐标存储成Excel表格格式。最优值是1071，路径：1→3→7→12→17→20。

【例3】SUMO交通仿真软件产生的随机二十个路口交通网络图。寻找从1出发，到达20的最优路径。其中(8,14),(6,2),(10,15)为单行线。节点19为死胡同。全局最优解为991.7038,路径1→3→7→13→16→20。

【例4】SUMO软件产生的五十个路口的随机交通网络。所得的最优解为1679.714，最优路径为1→3→9→21→25→33→38→46→49→50。

【例5】采用SUMO软件生成的100个路口的随机交通网络图。采用的种群大小为1000，经过100代。最优解：1→3→2→8→20→25→27→40→49→63→75→81→85→91→94→100。仿真100次，每次平均运行时间为2.25s。产生此最优解的成功率为84%。

Claims (2)

1.一种基于遗传算法的路径规划方法，其特征在于：所述规划方法包括以下步骤：

（1）建立路径优化数学模型，具体如下：

设V={1,2,3,…,n}表示路口的集合，其中n＞1为路口个数；E为路段的集合，设G=(V,E)是带正权的完全图；路段i→j为节点i,j之间的连接，权值为距离d_ij；c_ij表示它的可连接性，其中c_ij=1表示i到j可直接到达，c_ij=∞表示i到j不可直接到达；x_ij表示路段i→j是否包含在路径中；

设G为一条从起点1到达终点n的路径，路径G不包含重复路线和巡回路线；

标记当前节点的编号为1，在搜索半径内的所有节点依次编号为2,3,...,n-1，终点编号为节点n，求解x_ij：

${\min }_{x_{\mathrm{ij}}}F={\mathrm{\Σ}}_{i=1}^{n-1}{\mathrm{\Σ}}_{j=2,i\≠j}^n{x}_{\mathrm{ij}}{c}_{\mathrm{ij}}{g}_{\mathrm{ij}}{s}_{\mathrm{ij}}{d}_{\mathrm{ij}}---\left(1\right)$

s.t.

${\mathrm{\Σ}}_{i\≠j}^n{x}_{\mathrm{ij}}\≤1,j=\mathrm{2,3},...,n,---\left(4\right)$

${\mathrm{\Σ}}_{j\≠i}^n{x}_{\mathrm{ij}}\≤1,i=\mathrm{2,3},...,n,---\left(5\right)$

${\mathrm{\Σ}}_{j=2}^n{x}_{1j}=1,---\left(6\right)$

${\mathrm{\Σ}}_{j=1}^{n-1}{x}_{\mathrm{jn}}=1,---\left(7\right)$

上式中：

g_ij为道路等级系数，车道越多，该系数越小；

s_ij为交通拥堵系数，拥堵越严重，该系数越大；

d_ij用计算欧式距离通过i,j的坐标得到；

c_ij表示i,j两点之间的道路连接状况，当两点之间有道路导通时就设权值c_ij=1，两点之间没有道路导通时设定权值c_ij=∞；

x_ij表示边i→j是否在所搜索到的路径上；

式(4),(5)为了控制不出现重复路线和巡回路线，

确保路径所对应的矩阵的行最多只能产生一个1，

确保矩阵列的列只能产生一个1，式(6),(7)为了确保路径从起点1出发，到终点n结束；

（2）路径搜索过程，具体如下：

从起点开始，在搜索半径范围内采用遗传算法搜索一条最优路径，随着车辆移动到前一次搜索所得路径的下一个节点，以此节点作为当前搜索的起点，再次以搜索半径范围内的节点重新搜索出一条路径，不断实施此方法，直到搜索到目的地点。

2.如权利要求1所述的基于遗传算法的路径规划方法，其特征在于：所述步骤（2）中，遗传算法的处理过程如下：

2.1)设置运行参数：种群大小N，均匀变异概率p_m，节点数n；

2.2)采用半随机化方式产生初始种群

2.2.1)采用传统的路径表示方式或者随机键表示方式初始化种群；

2.2.2)非法个体修复；

2.3)评价各个个体的适应度；

2.4)精英保留：把群体中的最好的(0.05～0.2)N的个体保留，记为P₁；

2.5)交叉操作：

2.5.1)规模为2的锦标赛选择；

2.5.2)单点交叉；

2.6）对于交叉产生的后代进行变异操作：

2.6.1)(80～95)%的个体采用单点变异加上交换变异；

2.6.2)(5～15)%的个体采用均匀变异；

2.6.3)非法个体修复；

2.7)评价各个个体的适应度，并保留(0.7～0.9)N最优个体，记为P₂；

2.8)对P₂中最优秀的(0.05～0.15)N个体进行自学习，产生P₃；

2.9)每10代产生(0.05～0.15)N个体，记为P₄，检查P₂中适应度最大且相同的所有个体，如果他们的染色体完全相同，保留一个，其他全部被替代，同时也淘汰P₂中适应度最差的个体，更新后的P₂的种群大小为(0.6～0.8)N；

2.10)产生新一代群体：P₁∪P₂∪P₃∪P₄；

2.11)检验算法是否收敛或者达到指定的代数：

2.11.1)是，保存结果，结束搜索；

2.11.2)否，返回步骤2.3)；

2.12)结束。

Images