基于粒子群算法的电子地图路径规划软件设计

2018-09-21王磊杨思燕

微型电脑应用 2018年9期

王磊，杨思燕

(陕西广播电视大学信息与智能技术学院，西安 710119)

0 引言

电子地图不仅能够提供路线规划的多种功能，还能够提供道路的详细信息，规划出最佳的路线供用户选择。设计了西安市电子地图路径规划软件，该软件具有地图放大、缩小、定位、搜索等基本功能，可以根据Dijsktra算法实现路径导航功能，完成任意起始点和终点之间的最短路径计算，基于粒子群算法能够在选定的节点范围内寻找一条优化路径，达到路径规划目的，如公交线路规划、机器人路线规划、物流配送[1]等。

1 路径规划软件设计模块与功能

路径规划软件主要模型主要分为地图操作和路径规划，其中地图操作主要有放大、缩小、定位搜索等，路径规划主要是路径导航与路径寻优。

点击“地图操作”，会弹出“放大”、“缩小”、“定位”、“搜索”子菜单，各个功能如下：

(1)放大：点击地图上任意位置，地图将以该地点为中心放大一倍比例尺显示。

(2)缩小：点击地图上任意位置，地图将以该地点为中心缩小一倍比例尺显示。

(3)定位：可以通过定位系统实时定位。

(4)搜索：在地图上寻找目标位置。

点击“路径寻优”，会弹出“路径导航”及“路径规划”子菜单，各个功能如下：

(1)路径导航：输入起始点和终点，可以计算出一条最短路径。

(2)路径规划：选择若干个结点，可以计算出经过这些结点的一条较优路径。

路径规划软件模块与功能，如图1所示。

图1 路径规划软件模块与功能

2 路径规划软件实现技术

2.1 MapInfo软件简介

MapInfo由美国MapInfo公司开发，是一款地理信息系统二次开发软件，能够提供数据可视化、信息地图化的桌面解决方案。它集成多种数据库数据、结合计算机地图方法、采用数据库技术、融入地理信息系统分析功能，可以为各行各业所用的软件系统提供服务[2]。MapInfo全称为Mapping+Information即地图对象+属性数据。MapInfo采用“空间实体+空间索引”的拓扑关系模型，其空间实体是地理实体的抽象，类型包括点、线、面，每个空间实体对象都具有自身所有属性，一个图层由多个空间实体构成。空间索引能够定位到给定的空间坐标，快速搜索到坐标范围中的空间对象。MapInfo利用双数据库存储模式(空间、属性数据)，空间数据以MapInfo的自定义格式保存在文件中，属性数据存储在关系数据库的属性表中，他们之间通过一定的索引机制互相通信[3]。

2.2 Mapx控件简介

MapInfo公司在1996年推出了基于ActiveX技术的MapX控件，MapX控件随着MapInfo的功能升级而不断完善。MapX控件提供了二次开发的功能强大的地图化组件。可以嵌入到在可视化程序开发环境中如Visual Basic、Visual C++等，只需将MapX控件放入到窗体中，进行设置属性、调用方法和事件，就可实现地理空间数据的常用操作及可视化，并可以实现空间查询、地理编码等复杂的地图信息系统功能[4]。

MapX与MapInfo使用一致的地图数据格式，主要功能有显示MapInfo格式的地图数据，支持地图的放大、缩小、平移、选择等操作，图层的自由控制，支持动态图层和自定义图层，专题地图制作，简单的地理查询等。本软件基于MapX组件进行二次开发。

2.3 路径规划软件实现

本软件把西安市路网电子地图数据显示在单文档上，安装MapX、MapInfo及Visual Studio 2008开发平台，导入MapX.h 和 MapX.cpp到工程。其中MapX内置了常用的标准地图工具，例如放大、缩小、平移、选择等，在菜单的单击事件中编写相关的代码即可实现相应的功能。在地图操作中的放大、缩小、搜索及定位等操作用以下函数实现[5-6]：

m_ctrlMapX.SetFocus();

m_ctrlMapX.SetCurrentTool(miZoomInTool);

m_ctrlMapX.SetCurrentTool(miPanTool);

m_ctrlMapX.SetCurrentTool(miZoomOutTool);

m_ctrlMapX.ZoomTo(2, centerX, centerY);

其中路径导航dijkstra算法主要代码如下：

void CMapShowView::OnDijkstra(){

DijDialog m_dijParameter;

m_dijParameter.DoModal();

}

其中路径规划粒子群算法代码如下：

void CMapShowView::OnPSO() {

PsoParaDialog psoPDlg;

PsoPDlg.DoModal();

PsoParaDialog* pDlg = new PsoParaDialog();

pDlg->Create(IDD_DIALOG2);

}

3 路径规划软件功能算法实现

3.1 基于Dijkstra算法路径导航功能实现

3.1.1 Dijkstra算法简介

软件路径导航功能利用Dijkstra算法实现，Dijkstra算法思想[7]：迅速地扩展顶点集S中的每一个顶点v, S中s顶点和v顶点之间的最短路径已经计算出来。顶点集S初始化为{s}，在搜索s和v之间最短路径的过程中，S不断扩展，Dijkstra最短路径算法本身便可以寻找距离源点s最短路径的顶点v(v∈V-S)，以此类推，顺着顶点v的边，寻找是否存在一条最短路径到达另外一个顶点v2。当处理完v2后，算法通过这条路径计算得到s到v2的最短距离。当s扩展到等于v时，算法终止。

3.1.2 基于Dijkstra算法路径导航功能实现步骤

(a)初始时，S只包含源点，即S={v}，v的距离为0。U包含除v外的其他顶点，若v与u有边，U中顶点u距离为边上的权，若u不是v的出边邻接点，u距离无穷大。

(b)从U中选取一个距离v最小的顶点k，把k加入S中(该选定的距离就是v到k的最短路径长度)。

(c)以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

(d)重复步骤第(b)步和第(c)步直到所有顶点都包含在S中。

软件导航功能操作：在对话框中输入起点和终点，如图2所示。

图2 Dijkstra参数设置

路径结果红色轨迹，如图3所示。

图3 Dijkstra路径轨迹

3.2 基于粒子群算法路径规划功能实现

3.2.1 粒子群算法简介[8-9]

设有n个粒子组成的一个粒子群算法，其搜索区域空间为D维，Xid=(X1,X2,…XD)指粒子i在D维空间中的位置，Vid=(V1,V2,…VD)指粒子i在D维空间中的飞行速度。Pid为粒子的个体极值，即粒子i在自己的寻优历史中找到的最优解，Pgd是目前为止整个群体中所有粒子发现的最好位置。基本粒子群算法是用于实值连续空间，然而路径规划属于组合优化问题，引入交换子和交换序来解决路径规划问题，每个粒子速度位置按照式(1)、式(2)更新。

Vid=Vid(c1(Pid-Xid) (c2(Pgd-Xid)

(1)

Xid=Xid+Vid

(2)

其中，c1、c2是两个随机数。路径规划问题n个节点依次用序号1,2,3,…,n表示，设d为节点i与节点j之间的距离，1≤i,j≤n，引入决策变量x见式(3)。

(3)

路径规划问题的适应度函数M为式(4)。

(4)

3.2.2 粒子群算法进行电子地图路径寻优步骤[8-9]

(a)在西安市地图4 525个节点中选取n个必经节点，初始化粒子个数m(m

(b)初始化粒子群，每个粒子的位置表示一条路径，粒子的速度表示一个随机交换序。

(c)据粒子当前位置计算其下一个位置Xid。计算A=Pid-Xid，A是一个基本交换序，表示A作用于Xid得到Pid，计算B=Pgd-Xid，B是基本交换序，根据式(1)计算速度Vid，并将交换序Vid转换为一个基本交换序，根据式(2)计算搜索到的新解。

(d)根据路径规划问题的适应度函数M，如式(4)，计算每个粒子的适应度值，例如，有10个节点，某个粒子个体适应度值为这10个必经节点的最短距离，将每个粒子的个体适应度值与历史记录中其个体最优值比较，若优于个体最优值，则用此个体适应度值替代个体最优适应度值，同样，把每个粒子的个体最优值与粒子群算法的全局最优值进行比较，若优于全局最优值，则利用个体最优值进行更新。

(e) 判断当前迭代是否达到最大迭代次数，满足则终止，输出最优解，否则转至步骤(c)。

粒子群算法参数设置，如图4所示。

图4 参数设置

找出的最优路径，如图5所示。

3.2.3 与基于蚁群算法的路径寻优比较

路径寻优问题是在给定节点的条件下，找到一条遍历所有节点且每个节点只能访问一次的距离最短的路线。蚁群算法在路径寻优问题应用中取得了良好的效果，但是也存在一些问题：如参数α，β值设置不当，求解速度会很慢且所得解的结果不理想；蚁群算法计算量大，求解时间较长，最优线路是所有的蚂蚁选择同一路线，但实际在给定一定循环数的条件下很难达收敛，如本软件用蚁群算法进行路径规划时在给定1 000次迭代下，每次执行出现的结果会不同；蚁群算法收敛速度慢、易陷入局部最优，规划路径不一定是最优路线。

图5 粒子群算法路径轨迹

为缓解以上问题，采用粒子群算法进行路径规划。粒子群优化算法的基本思想是通过粒子之间的协作和信息共享来寻找最优解，优点在于不用调节过多参数。粒子群算法利用当前位置、全局极值和个体极值，指导粒子下一步位置，每个粒子利用自身经验和群体经验调整自身的状态。粒子群算法可以优化参数，具有相当快的求解速度。实验表明，粒子群算法在给定迭代条件下，得到的规划路径比较稳定，运行时间也较蚁群算法快。