基于文化蚁群系统的轨道交通多模式最优换乘查询方法

摘要

本发明涉及一种基于文化蚁群系统的轨道交通多模式最优换乘查询方法，包括以下步骤：1)中央处理器通过触摸屏接收查询请求，并根据查询请求从数据库中获取站点信息，构建路径选择模型；2)中央处理器基于路径选择模型执行文化蚁群系统，计算获得不同最优目标下的最优轨道交通换乘方案，输出最优路径；3)对路径选择模型的数值进行更新，并判断优化是否结束，若是，则将计算结果反馈给触摸屏，执行步骤4)，若否，返回步骤2)；4)触摸屏显示计算结果。与现有技术相比，本发明通过文化蚁群系统高速、精确地计算不同最优目标下的轨道交通最优换乘方案，提高了居民出行对轨道交通换乘的灵活性和高效性。

说明书

技术领域

本发明涉及一种轨道交通最优换乘计算方法，尤其是涉及一种基于文化蚁群 系统的轨道交通多模式最优换乘查询方法。

背景技术

城市轨道交通系统是与城市居民日常生活联系最为紧密的环节之一，甚至在一 定程度上决定着城市居民的生活方式，因而，时下众多城市的电子地图产品都把实 现轨道交通网络最优路径查询作为其重中之重，以期使电子地图能够更好地满足用 户的需求，但现有的查询系统不但容易出错，而且效率低下，同时不能进行多模式 换乘：

一方面，大多数软件开发者认为，轨道交通网络最优路径分析同其他网络分析 一样，也应该是以最短为基础的，但用户的最优不仅仅是最短路径，所以其离用户 要求还有很大的差距；

另一方面，多数用户认为，最少换乘才是关键问题。最少换乘和最短路径看似 统一，但其实不然，因此如何做到两者的统一，提出现实可行的优化换乘模型和算 法已经成为迫切需要解决的问题。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种计算速度 快、精度高的基于文化蚁群系统的轨道交通多模式最优换乘查询方法，提高了居民 出行对轨道交通换乘的灵活性和高效性。

本发明的目的可以通过以下技术方案来实现：

一种基于文化蚁群系统的轨道交通多模式最优换乘查询方法，该方法包括以下 步骤：

1)中央处理器通过触摸屏接收查询请求，并根据查询请求从数据库中获取站 点信息，构建路径选择模型；

2)中央处理器基于路径选择模型执行多种群文化蚁群系统，计算获得不同最 优目标下的最优轨道交通换乘方案，输出最优路径；

3)对路径选择模型的数值进行更新，并判断优化是否结束，若是，则将计算 结果反馈给触摸屏，执行步骤4)，若否，返回步骤2)；

4)触摸屏显示计算结果。

所述的查询请求包括起始站点和最终站点。

所述的最优目标包括时间最短、换乘最少和路程最少。

所述的文化蚁群系统包括群体空间的蚁群演化过程和信仰空间的知识更新过 程，所述的群体空间的蚁群演化过程包括以下步骤：

a1)初始化群体空间的信息素分布，并将群体空间划分为多个子群，各子群分 别采用不同行为的蚁群系统进行并行演化，获得各子群的局部最优解；

a2)各子群间根据基于学习机制的信息交互策略更新各自的局部信息素；

a3)根据各子群的局部最优解更新全局最优解，并将其通过接受函数存储到信 仰空间；

a4)根据信仰空间的输出进行全局信息素更新；

a5)判断是否满足算法终止条件，若满足，则算法终止；否则，转步骤a2)；

所述的信仰空间的知识更新过程包括以下步骤：

b1)初始化信仰空间；

b2)通过接收函数接收群体空间提供的当前全局最优解；

b3)对信仰空间实施2-OPT操作，优化信仰空间；

b4)输出最优解，并通过影响函数将其提供给步骤a4)。

所述的各子群分别采用不同行为的蚁群系统进行并行演化具体为：

a101)各子群将不同数量的m个蚂蚁随机地置于n个站点中的一个站点上；

a102)各子群根据各自的行为方式进行状态转移，选择下一节点，同时进行局 部信息素更新，所述的行为方式包括随机、从众、贪婪或混合；

a103)重复步骤a102)，直至每只蚂蚁均形成一条完整路径，即各子群分别遍 历所有节点，获得各自的局部最优解。

所述的基于学习机制的信息交互策略为：

每一子群与比邻的其他两个子群进行信息交互，将当前的局部最优解与比邻的 其他两个子群的局部最优解进行比较，并以更优的局部最优解更新自身的局部信息 素。

所述的接受函数Accept()为：

                           Accept()＝T

T为设定的常数。

所述的对信仰空间实施2-OPT操作具体为：

b301)设置r₀为一个给定的在[0，1]的常数，产生一个[0，1]范围的随机数r，如 果r＞r₀则转步骤b4)；

b302)如果当前最优路径中存在节点c_i、c_j，其中j≥i+2，且

               d(c_i，c_i+1)+d(c_j，c_j+1)＞d(c_i，c_j)+d(c_i+1，c_j+1)

那么将边(c_i，c_j)、(c_i+1，c_j+1)代替(c_i，c_i+1)、(c_j，c_j+1)，交换后线路中的路径 (c_j，…，c_i+1)被反向；否则转步骤b4)。

所述的影响函数Influence()为：

$\mathrm{Influence}\left(\right)=\left(\begin{array}{cc}\mathrm{BaseNum},& \mathrm{CurrentStep}\le C\\ \mathrm{BaseNum}*\frac{\mathrm{EndStep}-\mathrm{CurrentStep}}{\mathrm{EndStep}-C},& \mathrm{otherwise}\end{array}\right)$

其中，EndStep为预先设定的蚁群系统最大演化代数，CurrentStep为蚁群演化 当前代数，BaseNum和C为常数。

与现有技术相比，本发明具有以下优点：

1、本发明采用文化蚁群系统进行最优路径求解，文化蚁群系统是一种将蚁群 系统纳入文化算法框架的新的高效优化方法，该计算模型包含基于蚁群系统的群体 空间和基于当前最优解的信仰空间，两空间具有各自群体并独立并行演化，提高了 算法求解的速度和精度；

2、本发明采用多种群并行演化的蚁群系统，且各子群间通过基于学习机制的 信息交互策略进行交互，提高了算法的精度；

3、本发明文化蚁群系统的信仰空间采用随机2-OPT交换操作，对最优解进行 变异优化，经演化后的解个体用来对群体空间全局信息素更新，帮助指导群体空间 的进化过程，从而达到提高种群的多样性，防止早熟，降低计算代价的目的；

4、本发明方法具有更好的精确度和鲁棒性，即使对于大规模问题，也能以较 小的种群数目和较短的运行时间求得相对误差较小的满意解。

总之，本发明的有益效果在于：本发明设计和实现了一种新型的智能计算方法， 能够对不同居民多模式换乘进行高效的优化设计，提高了居民出行对轨道交通换乘 的灵活性、高效性。本发明适应了城市交通发展的未来需求，可持续对规模和复杂 程度日益增长的轨道交通换乘进行科学的管理。

附图说明

图1为本发明的流程示意图；

图2为本发明多种群文化蚁群系统的系统框架图；

图3为本发明多种群并行演化的框架示意图；

图4为本发明文化蚁群系统的原理示意图。

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。本实施例以本发明技术方 案为前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范 围不限于下述的实施例。

如图1所示，一种基于文化蚁群系统的轨道交通多模式最优换乘查询方法，该 方法包括以下步骤：

1)中央处理器通过触摸屏接收查询请求，包括起始站点和最终站点，并根据 查询请求从数据库中获取站点信息，构建路径选择模型；

2)中央处理器基于路径选择模型执行多种群文化蚁群系统，计算获得不同最 优目标(包括时间最短、换乘最少和路程最少等)下的最优轨道交通换乘方案，输 出最优路径；

3)对路径选择模型的数值进行更新，并判断优化是否结束，若是，则将计算 结果反馈给触摸屏，执行步骤4)，若否，返回步骤2)；

4)触摸屏显示计算结果，展示路径选择模型，展现内容包括轨道交通换乘信 息和线路图。

如图2-图4所示，所述的文化蚁群系统包括群体空间的蚁群演化过程和信仰 空间的知识更新过程，所述的群体空间的蚁群演化过程包括以下步骤：

a1)初始化群体空间的信息素分布，并将群体空间划分为多个子群(如图2、 图3中的子群1、子群2、子群3、子群4)，各子群将不同数量的m个蚂蚁随机地 置于n个站点中的一个站点上，根据各自的行为方式进行状态转移，选择下一节点， 同时进行局部信息素更新，所述的行为方式包括随机、从众、贪婪或混合；直至每 只蚂蚁均形成一条完整路径，即各子群分别遍历所有节点，获得各自的局部最优解。

每一子群进行演化的具体步骤为：

a101)初始化：t＝0，Nc＝0，τ_ij(t)＝τ₀，Δτ_ij(t)＝0，将m个蚂蚁随机地置于 n个站点上；

a102)置禁忌表索引s＝1，并将其起点站点加入各自禁忌表中，判断禁忌表是 否已满，若是，则执行步骤a104)，若否，则s＝s+1，执行步骤a103)，

a103)各蚂蚁按其各自计算的转移概率选择下一站点，并将该站点加入禁 忌表中，同时进行局部信息素更新：

                        τ_ij＝(1-ρ)τ_ij+ρτ₀

其中：ρ(0＜ρ＜1)是信息素的局部挥发因子；τ₀是各条路径上的初始信息素 浓度值；

a104)每只蚂蚁均形成一条完整路径，即遍历所有节点，计算所有蚂蚁走过的 周游长度L_k，更新当前最优解，获得局部最优解。

a2)各子群间根据基于学习机制的信息交互策略更新各自的局部信息素。

如图3所示，各子群呈环状连接，每一子群与比邻的其他两个子群进行信息交 互，将当前的局部最优解与比邻的其他两个子群的局部最优解进行比较，并以更优 的局部最优解更新自身的局部信息素。

a3)根据各子群的局部最优解更新全局最优解，并将其通过接受函数存储到信 仰空间；

所述的接受函数Accept()为：

                          Accept()＝T

T为设定的常数，可设为20；

a4)根据信仰空间的输出进行全局信息素更新：

${\tau }_{\mathrm{ij}}=(1-\partial ){\tau }_{\mathrm{ij}}+\partial \Delta {\tau }_{\mathrm{ij}}$

其中：是信息素的全局挥发因子，

L_gb代表当前全局最优解的路径长度(从试验开始所得到的全局最优路径的长 度)；

a5)判断是否满足算法终止条件，若满足，则算法终止；否则，清空所有禁忌 表，转步骤a103)：

算法终止条件为达到设定的最大演化代数或全局最优解在设定代数内连续不 发生变化。

各子群空间采用的蚁群系统是一种用信息素的局部更新规则和全局更新规则 进行路径上的信息素更新，从而使扩大算法的搜索空间和算法得以收敛能有机统一 起来。如图3所示，A表示各子群通过局部合作交流最优解更新局部信息素，B表 示各子群交互将全局最优解提供给信仰空间更新全局信息素。

所述的信仰空间的知识更新过程包括以下步骤：

b1)初始化信仰空间；

b2)通过接收函数接收群体空间提供的当前全局最优解；

b3)对信仰空间实施2-OPT操作，优化信仰空间；

所述的对信仰空间实施2-OPT操作具体为：

b301)设置r₀为一个给定的在[0，1]的常数，产生一个[0，1]范围的随机数r，如 果r＞r₀则转步骤b4)；

b302)如果当前最优路径中存在节点c_i、c_j，其中j≥i+2，且

               d(c_i，c_i+1)+d(c_j，c_j+1)＞d(c_i，c_j)+d(c_i+1，c_j+1)

那么将边(c_i，c_j)、(c_i+1，c_j+1)代替(c_i，c_i+1)、(c_j，c_j+1)，交换后线路中的路径 (c_i，…，c_i+1)被反向；否则转步骤b4)。

b4)输出最优解，并通过影响函数将其提供给步骤a4)。

所述的影响函数Influence()为：

$\mathrm{Influence}\left(\right)=\left(\begin{array}{cc}\mathrm{BaseNum},& \mathrm{CurrentStep}\le C\\ \mathrm{BaseNum}*\frac{\mathrm{EndStep}-\mathrm{CurrentStep}}{\mathrm{EndStep}-C},& \mathrm{otherwise}\end{array}\right)$

其中，EndStep为预先设定的蚁群系统最大演化代数，CurrentStep为蚁群演化 当前代数，BaseNum和C为常数，由用户设定。通常BaseNum取值为30，C：EndStep 取值为1∶3，这样在蚁群演化的初始阶段，信仰空间的知识解对其影响较小，使其 能够保证快速演化，在蚁群演化的后期，知识解对其影响逐渐加大，使其能够更多 地接受知识空间的引导，同时扩大搜索空间，具备更好的全局搜索能力。

群体空间个体在进化过程中形成个体经验，通过函数accept()将个体经验传递 到信仰空间，信仰空间将收到的个体经验根据一定的行为规则进行比较和优化，形 成最优解。信仰空间对进化过程中所发现的最优解，采用随机2-OPT交换操作， 对最优解进行变异优化，并充分利用随机2-OPT算法简洁高效的特点，完成自身 的变异，经演化后的解个体用来对群体空间全局信息素更新，帮助指导群体空间的 进化过程，从而达到提高种群的多样性，防止早熟，降低计算代价的目的。信仰空 间在形成群体经验后通过影响函数对群体空间中个体的行为规则进行修改，以使个 体空间获得更高的进化效率。