基于改进遗传算法的多目标城市交通路径选择系统建模与仿真

卫小伟

(陕西交通职业技术学院信息工程系　西安　710018)



基于改进遗传算法的多目标城市交通路径选择系统建模与仿真

卫小伟

(陕西交通职业技术学院信息工程系西安710018)

摘要传统路径最优算法把路径最短作为目标,不考虑交通拥堵,红绿灯等待等实时路况,这种算法存在着它的局限性。为了满足不同人群的不同出行需求,提出一种城市交通路径选择模型,并用改进的遗传算法仿真实现。首先通过城市交通现有系统,采集城市交通路况数据,并通过路径选择系统对路网数据进行预处理,得到各路段实时加权长度值,然后通过遗传算法进行寻优解,为了提高搜索效率,提出了一种以路段为单位进行基因交叉与基因重组的方法对遗传算法加以改进,大大提高了遗传算法路径搜索时间,并在Matlab平台上仿真实现。仿真结果表明,用改进遗传算法进行城市交通路径选择,可以减少路径搜索的时间,提高搜索效率。

关键词遗传算法; 城市交通; 路径选择; 建模与仿真

Multi-objective City Traffic Routing System Modeling and Simulation Based on the Improved Genetic Algorithm

WEI Xiaowei

(Department of Information Engineering, Shanxi College of Communication Technology, Xi’an710018)

AbstractTraditional optimal path algorithm shortest path as the goal, regardless of the traffic jam, traffic lights waiting for real-time traffic, such as the algorithm exists its limitations. In order to meet different people of different travel demand, a model of urban traffic route choice is put forward, and simulated by the improved genetic algorithm. Firstly through the existing urban traffic system, urban road traffic data, data preprocessing and through the path selection system of road network, road real-time weighted length value is obtained, and then through the genetic algorithm optimization solution, in order to improve the search efficiency, a genetic crossover and gene recombination in sections as the unit of the method is proposed to improve genetic algorithm, greatly improving the path search time genetic algorithm, and the simulation on Matlab platform. The simulation results show that with the improved genetic algorithm for urban traffic route choice, it can reduce the time of the search path.

Key Wordsgenetic algorithm, city traffic, route choice, modeling and simulation

Class NumberTP391

1引言

传统的交通路径搜索算法中,多采用Dijkstra方法来解决单源单目标最优路径算法[1]。该类方法的数据结构及其实现方法是以牺牲时间效率来换取空间节省,存在计算时间较长,性能低下的问题[2]。目前在GPS导航系统中遇到的单源多目标路径问题,可以采用Steiner解决,途径有两种,一种是精确算法,另一种是启发算法,前者需要很长的时间,而启发算法能在较短时间内得到解,但算法缺乏全局性,很容易陷入局部最优解[3]。道路交通的路径选择也不仅仅是传统意义上的路径最短或时间最少的问题,出行时还会考虑到路况、天气、流量、资金等因素,如果只是距离上微弱的优势,并

不能成为路线选择的关键。目前多目标交通路径选择多采用智能路径优化算法,如遗传算法与蚁群算法,具有全局收敛和动态适应等优点,并且容易与其他智能算法结合[4],对于蚁群算法当生成的蚁群较大,算法初期又缺乏信息素时,要在短时间内找出一条较好的路径就显得比较困难,并且有搜索停滞和无效搜索问题存在[5];遗传算法使用概率机制进行迭代,具有随机性,可避免陷入局部最优解,但搜索没有反馈机制,搜索具有盲目性,最优解的收敛速度也较慢,求解效率低。

为了实现城市交通最优路径搜索,并提高搜索效率,首先利用城市智能交通系统,获得城市道路相关数据,建立城市动态交通信息模型,然后利用遗传算法全局搜索能力强的优点进行搜索,并对遗传算法的初始种群、交叉重组与变异操作采用基于路段的启发算法改进,消除路径搜索过程中产生的“回路”与“死路”,避免产生大量的无效染色体,解决遗传算法收敛速度较慢、求解效率低的问题,最后通过仿真实验对其性能进行验证,实践证明该算法具有较快的收敛速度与求解效率。

2城市动态交通路径选择数学模型

城市交通路径选择系统分成两个部分,其一是建立城市交通路径拓扑结构,其二是建立城市道路交通路径选择数据模型。每个城市均有城市交通控制系统,利用城市交通控制系统中的城市交通地图,抽象出城市交通拓扑结构,以浙江省丽水市莲都区某中心区域地图为例,如图1,其对应的路径拓扑结构如图2,其中节点标示交叉路口,单实线表示道路路段。

图1　丽水市莲都区中心城区地图

每个交通路口均有摄像头、红绿灯等控制系统与城市交通控制系统相连,从城市交通控制系统中可以提取城市道路相关信息,每条道路的相关信息主要包括:道路标志、道路名称、道路等级、车道数、设计车速;路段标志、路段名称、路段长度;事件影响标志(道路维修、恶劣天气、车辆故障、货物散落、交通事故、节假日等)、排队长度、延误时间;交叉口标志、流量、速度、红绿灯转换时间等,将网络图中每个节点与每段道路的这些实时数据存入数据库,并进行分析与预处理,得到每个路段的权值,本文采用路段长度与路段行驶时间相结合选择路段权值,若两节点之间不连通,则两节点间距离为∞,用一个非常大的数来表示[6],本文采用10000来表示。

图2　带权莲都区中心城区道路拓扑结构

路网中的行驶时间分为下面几部分: 1) 路段正常行驶时间Tijr(t)。可根据数据库预处理数据获取,数据预处理方法为

其中,Lij为i,j节点间路段长度,Vij为i,j节点间路段行驶的设计车速或高峰平均车速。其中i与j为邻节点。

通过一条路段ij及节点j的时间Tj为

因此,从出发节点到目标节点的行驶时间,即整条路径的行驶时间Tp(t)为

其中,m为从起点到终点的路段数。

从出发节点到目标节点的路段长度Lp,也是路径选择需要考虑的重要因素:

根据用户的实际需求,选择权重系数,设时间权重系数为α1,路径长权重系统为α2,α1+α2=1。

因此,可以得到路径的目标函数为

Fp(x)=α1*Tp(x)+α2*Lp(x)

上述函数在使用时还要注意单位的转换,因为时间单位与路径单位不在一同级别上,用权重系统去直接衡量时,可能会有失重的现象产生,若时间以分为单位,路径以公里为单位,则每分钟相当于多少公里,可根据汽车行驶的平均速度进行转换,可使权重系数一致。假设α1=0.7,α2=0.3时,则某一时刻从交通网络控制中心提取上述路段路径物理长度、实时车速、影响事件以及各交通路口的排队长度与红绿灯时间等,用上述数学模型在交通路径选择预处理系统中处理后得到各路段的权值如图2所示。

3改进遗传算法的城市最优路径选择方法设计

遗传算法有六个主要要素:参数的编码、初始种群的设定、适应度函数的设计、遗传操作、算法控制参数的设定与约束条件。

3.1个体编码

染色体编码(即个体编码)是城市路径最优选择关键之一,编码的好坏将直接影响选择、交叉、变异等遗传操作。在本算法中,将一条路径作为一个染色体,将一个节点作为一个基因。为了方便个体编码,采用等长编码的方法,例如丽水市莲都区城区道路结构中共有33个结点,则染色体的长度为33。为了方便编码及容易理解,采用符号编码法,用自然数来表示顶点,顶点的顺序即按顺序通过各交通路口的顺序。设定在始点到终点之间不走回头路,即每个顶点一条路径中只出现一次,且两个顶点之间没有连通路段的顶点不能顺序出现,因为不连通路段顶点顺序出现则该路径为无效路径,结束点之后的其他点用0替代,表示没有行驶过的路段。例如从1出发到33结束,其中一条路径编码为:1 2 8 19 25 26 27 28 22 23 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0。

3.2初始种群与优化

若采用传统的随机方法产生初始种群,理论上不影响最终的最优路径选择,但由于一开始就产生了大量无效路径,比如随机选择二节点之前的路段不存在等。这将大大降低算法效率,为了避免在开始种群里产生大量无效路径,又不影响群种中个体的随机性,避免陷入局部最优解,采用随机选择节点与路段启发算法相结合的方法,既可提高搜索效率又可得到全局最优解。具体方法是:将开始结点作为第一个基因,在本例中第一个基因为V1,然后扫描数据中与V1相连的所有顶点,随机选择其邻近的任一节点作为染色体中下一基因,如V2,再以V2为出发点随机选择一个邻接点作为下一个基因,如V8,依次类推,直到终止节点,如V1-V2-V8-V19-V25-V26-V27-V28-V22-V23-V33即为用启发算法得到的一条染色体(即一条路径)。但用该启发算发时有可能出现两种例外情况:第一是在某顶点中选择领接点作为下一基因时,该邻接点在该条染色体中之前己作为基因被选择过,就会出现回路的情况,例如:V1-V2-V8-V19-V18-V7-V8-V3-V4-V5-V6-V11-V16-V23-V33这条路径出现两个V8,两个V8之间的路段即多余的回头路,虽然遗传算法不影响最终结果,但大量这样路段的出现,会导致算法效率大大降低,本算法中采用将所有33个节点作为一个向量存放,路径选择时每选择一个节点就从该节点向量中除去该元素,下一邻接点选择时只能从该向量中存在的元素中选择,如此可避免出现“回路”;第二是当路径中的顶点按邻接点的方向选择,且每个节点只能出现一次时,会出现某条路径选择到某个节点时,在节点向量中的元素里己没有与该节点的邻接点,即该路径是一条“死路”,在本规则的约束下,不能到达目的地,例如:V1-V2-V8-V7-V12-V17-V18-V19-V20-V13-V14-V15-V22-V21,到V21后,与该节点相连的节点只有V20与V14,而这两个节点己被该路径选择过,在剩余节点中不存在,解决此问题的方法,是直接将该条染色体从初始种群里删除,从新选择符合条件的路径作为染色体。如此循环选择路径,直到需要的初始种群大小。

3.3适应度函数

适应度函数所计算的适应度应该是非负且适应度一般是越大其个体越优良[7]。而城市路径选择中对于个体的路径加权长度值越小越好,故需要对适应度函数进行变换,采用1减去每条路径的加权长度值与所有路径中最大路径长度值的比值作为适应度函数,故个体的适应度函数Fit(x)定义为

Fit(x)=(1-Pl(x)/max(Pi(X))

(1)

式中,Pl(x)为某条路径的加权长度,max(Pi(X))为种群中所有路径中最长路径。适应度函数值在0~1之间,函度值越大,适应度越好。

3.4遗传操作

遗传操作有选择、交叉重组、变异几个部分。

· 选择:本研究采用比例选择法,根据各个体适应度值的大小,择优选择适应度大的个体进入下一代[8]。

· 交叉重组:为避免节点随机交叉后,出现不存在的路段的状况即“死路”,本算法采用在父代两条染体色中任意抽出一段首尾相同节点进行交叉,并判断交叉后的染色体中是否出现“回路”,若有回路,则删除此回路。如图3,父代两条染色体间V18与V24之间的路段交叉。

图3　交叉重组方法

· 变异:为避免随机选择节点变异产生死路与回路的问题,本文采用重选路段变异算子方法。

4仿真实验

4.1实验环境

P4双核3.6G CPU,8G内存,操作系统为Windows 7,采用Matlab改进的遗传算法进行仿真实现,并与经典算法在实现效率上进行对比。

4.2城市道路最优化路径仿真实现

4.2.1初始化种群

本算法设初始种群大小为50,按上述启发式种群初始化方法,将图2的带权城市道路拓扑结构所有路段用矩阵V存放,其中每个元素V(i,j)存放节点i到节点j之间的路段值,i取1~33自然数,j取1~33的自然数,当节点i与节点j不连或i等于j时,取一个相对很大的数,如10000,V矩阵一部分如图4所示。

图4　V矩阵部分元素

接着定义一个50*33的零矩阵P,用于存放50条路径,然用三重循环来实现随机选取50条1~33的路径。最内层用于查询所有与i相连并且还没有被当前路径选择过的邻接点,并从这些邻接点中随机选择一个节点作为与i相连的节点j,修改P(i,j)元素值为j;第二层循环用于控制一条路径是否被正常选择,正常选择的标准是邻接点随机选择的方法,最终选择到终节点33,若在选择过程中出现前述所述“死路”状况,则直接中断该循环,并将该路径删除,删除的方法是该路径上所有节点重新置0,并返回重选该路径,最外层控制选择50条路径。其中某次运行结果一部分如图6所示。从程序结果可以发现,路径中既不存在回路,也不存在死路。

图5　初始种群P中一部分

4.2.2目标函数

该研究中的目标函数就是计算每条路径的加权长度,方法是将P矩阵中每一行不为0节点顺序二节点之间的路段V(P(i,j),P(i,j+1)累加,其中i从1~50,j从1~节点32所对应的列号,每条路径目标函数值存入PL矩阵。

4.2.3适应度函数

由于适应度函数值一般是由0~1之间的一个值,并且值越大适应度越好,本研究中计算最短路径,因此目标函数值越小,其对应染色体越优秀,本研究采用式(1)方法,将种群中每条路径与最大路径值相除,得到0~1之间的值,但因为该值越大适应度应该越小,所以本研究中再用1去减该值,得到0~1之间的值,其值越大适应度越好,计算机结果存于向量FIX中。

4.2.4选择算子

本研究采用比例选择法,根据适应度值分配,然后采用随机遍历采样的方法选择进入下一代的个体。其调用函数为:SelCh=Select('sus',Chrom,Fix,GGAP)。Select函数中sus为底层随机遍历函数。Chrom为种群,Fix为适应度值,GGAP为代沟,本研究取0.9。

4.2.5交叉重组操作

交叉概率控制着交叉操作的频率,该算子太大会使高适应值的结构很快破坏掉,该算子太小,则会使搜索停滞不前。本研究取0.7。研究的思路是,随机抽取交叉样本数的一半个体,每一个交叉样本都与未被选取样本却未交叉过的剩余个体匹配。交叉匹配后路径同样要解决“死路”、“回路”以及交叉后的个体与原父代的个体相同的问题,采用3.4中图3的实现方法为:将父代的两条染色体从第一个节点开始比较,直到有不相同节点,标志该节点位置flag1,再将第一个个体中的flag1后每个节点与第二个个体中falg1后的所有节点匹配,直到找到相同节点,将这两个相同节点的第一个个体节点位置标志为flag2,第二个个体的节点位置标志为flag3,再将第一个个体的flag1与flag2之间的路段与第二个个体的flag1与flag3之间的路段交叉,得到两个新的子代个体,若在flag1之后找不到相同节点,则放弃第二个父代个体,重新选择新的父代个体,直到两个个体间满足上述条件,这样方法交叉后的个体不会存在死路以及交叉后子代与父代相同问题。上述交叉过程如图6所示。

图6　交叉重组

但交叉后的两个子代染色体可能会存在回路,而且有可能存在多条回路,因为回路的存在,交叉后的子代染色体节点数也有可能超过原地图的节点总数,本例中有可能超过33,导致种群矩阵列数增加,因此必须删除所有回路,例如:如下两条父代染色体:

1-2-8-3-4-9-14-13-20-26-25-24-18-17-29-30-31-32-33

1-12-7-18-17-29-30-31-25-26-27-32-33

在第2~第10点位置发生交叉,交叉后的子代染色体如下:

1-12-7-18-17-29-30-31-25-26-25-24-18-17-29-30-31-32-33

1-2-8-3-4-9-14-13-20-26-27-32-33

其中子代第一条染色体的18节点出现回路,将回路删除后第一个子代染色体为

1-12-7-18-17-29-30-31-32-33

删除回路后有可能还存在别的回路,用同样的方法继续删除回路。并使种群的行列数回复到原来大小。

4.2.6变异操作

本文变异操作采用重选路径变异操作,采用方法为在路径中随机选择一个节点,从这个节点出发,重新随机选择一条与原路径不同的路径做为变异后的染色体,重新选择路径的方法同选择操作,不同点在于不是从1节点开始选择,而是从随机选择的节点开始,因此该方法同样可以避免回路与死路的产生,但有可能使收敛速度过快,很容易陷入局部最优解,因此适当的加大交叉重组与变异率可以避免收敛速度过快的问题,本文中变异率设为0.1。

4.2.7实验结果

实验结果,经多次运行,在3代以内就能得到最优解,上例最优路径值为1166,最优路径为:1-2-3-4-5-6-11-16-23-33。得到最优解运行时间为15s,运行结果如图7所示。

由图可知,上例有33个节点的莲都区城市交通路径的仿真结果,收敛速度极快,效率极高。

若将道路结构进行扩大,当再扩大一个小区,得到60个节点的加权道路拓扑结构如下:

图7　实验结果

图8　60节点带权莲都区道路拓扑结构

当扩展到60个节点时,经多次运行5代以内能得最优解,其中一次运行结果如图9,最优路径值为1351,最优路径为:1-2-3-4-5-6-11-39-40-42-45-46-47-60,得到最优解运行时间为58s。

图9　60节点莲都区道路选择实实验结果

4.2.8与Dijkstra比对

求解单源最优路径的经典算法为Dijkstra,上例有33个节点的莲都区城市交通路径同条件下Matlab最短路径实验结果为1166,路径为:1-2-8-19-20-26-27-32-33与1-2-8-19-20-26-27-32-33,运行时间为28s,运行速度比优化遗传算法慢约46%。当地图扩展到60个节点时,最短路径实验结果为1351,路径为:1-2-3-4-5-6-11-39-40-42-45-46-47-60。运行时间为74s,比本研究中遗传算法运行速度慢约21%。

5结语

从实验结果可看出在遗传算法中引入一种改进的交叉与变异方法,在现代社会城市间复杂的路网中,在求解车辆的行驶路径时,能快速准确地给出当前车辆行驶的最优路线,证明该方法的有效性[10]。本文提出一种城市最优路径寻径解决模型并在Matlab上采用遗传算法仿真实现。仿真结果表明,相对于其它算法,可以很快地找到最优路径,缩短了寻径时间,满足了实际应用对其的实时性要求,具有较好的收敛速度,解决城市最优路径问题。

参 考 文 献

[1] Psiaki Mark L. Block Acquisition of weak GPS signals in a software receiver[C]//The Institute of Navigation. SaltLake City; IEEE,2001:2838-2850.

[2] 侯燕.Steiner树遗传蚁群算法在路径选择中的应用[J].微电子学与计算机,2013,30(11):88-92.

HOU Yan. The Application of Steiner Tree-based Genetic and Ant Colony Algorithm Path Selection[J]. Microelectronics & Computer,2013,30(11):88-92.

[3] Tsui JB. Fundamentals of Blobal positioning system receivers: a software apporach[M]. New York: Wiley,2000.

[4] Gunes M, Sorges U, Bouazizi I. ARA the ant colony based routing algorithm for MANETs[C]//International Conference on Parallel Processing Workshop(sICPPW02). Vancouver BC, Canada: IEEE,2002:79-85.

[5] Perkins CE, Belding-Royer EM, Das SR. Adhoc on demand distance vector(AODV) routing. IETF Internet Draft, draft-ietf-manet-aodv-13 txt[R]. US: publisher RFC editor,2003.

[6] 张敏捷,蔡延光,等.基于改进遗传算法的路网路径优化方法[J].微计算机信息,2010,26:226-227.

ZHANG Minjie, CAI Yanguang, et al. The approach of Road Net Traffic Flow Guidance Based on an Improved Genetic Algorithm[J]. Microcomputer Information,2010,26:226-227.

[7] 邱敏,王公宝,等.一种求解最优路径的改进遗传算法[J].计算机与现代化,2010,4:6-8.

QIU Ming, WANG Gongbao, et al. An Improved Genetic Algorithm for Optimal Path Planning[J]. Computer and Modernization,2010,4:6-8.

[8] Ong CJ. Distance computation between smoo thconvex objects[C]//Proceedings of IEEE International Conference on Robotics and Automation. Minnesota, USA,1996:785-790.

[9] 袁云,邵时.基于多核处理器并行系统的任务调度算法[J].计算机应用,2008,28(S2):280-282.

YUAN Yun, SHAO Shi. Tasks Scheduling Algorithm for Parallel System with Multi-core Processor[J]. Computer Applications,2008,28(S2):280-282.

[10] 王海雄,郭剑毅,张月红.改进遗传算法求解交通最优路径的实现[J].昆明理工大学学报(理工版),2009,8:42-46.

WANG Haixiong, GUO Jianyi, ZHANG Yuehong. Improved Genetic Algorithm for Solution of Optimal Traffic Path[J]. Journal of Kunming University of Science and Technology(Science and Technology),2009,8:42-46.

中图分类号TP391

DOI:10.3969/j.issn.1672-9722.2016.01.003

作者简介:卫小伟,男,博士,副教授,研究方向:交通智能控制、移动计算。

收稿日期:2015年7月8日,修回日期:2015年8月23日