基于状态空间模型的智能优化算法及其应用

李雪　李茂军　王鼎湘　成立　张家臣

摘 要：针对城市公共交通系统中公交优化调度问题的具体特征，提出一种基于状态空间模型的实数编码智能优化算法（SIA）。SIA引入遗传算法（GA）的基本理念。通过构造状态进化矩阵来指导算法的搜索方向，再通过选种池的优胜劣汰的选择机理来实现算法朝最优解逼近。将该算法与GA分别应用到公交优化调度问题中，考虑发车时间间隔的约束，建立以企业和乘客的利益最大化为目标的数学模型。实例仿真结果表明，SIA在寻优精度和计算量方面优于GA，验证了该算法的有效性。

关键词：公交调度；时间间隔；状态空间模型；状态进化矩阵；选种池

中图分类号：U491.2TP18 文献标识码：A

Abstract：An intelligent optimization algorithm with real strings based on state space model （SIA） was presented to solve bus dispatching problem in urban public transport system. The basic idea of genetic algorithm （GA） was introduced to SIA. The state evolution matrix was constructed to guide the search direction of the algorithm， then through the selection mechanism of selection pool to approach optimal solution. This algorithm and GA were applied to the public transport optimization dispatching problem. Mathematical model was set up by considering the time interval，and the benefit maximization of enterprises and passengers. The results of example simulation show that SIA is better than GA in optimization accuracy and amount of calculation.

Key words：pubic transport dispatching；time interval；state space model；state evolution matrix； selection pool

1 引 言

随着现实世界中交通拥堵情况日趋严重，调节城市公共交通运营工作成为舒缓交通状况、改善城区生活质量的重要手段之一。城市公共交通运营工作可以转化为公交优化调度问题进行处理，而本文以公交线路发车间隔的设定来进行公交优化，即要求在一个调度周期（公交线路一天的运营时间）内，根据车流情况，在满足整体社会效益和经济效益的情况下，优化各时段的发车时间间隔，以使得公交公司和乘客花费成本最低。随着对公交优化调度问题研究的不断深入，国内外许多学者提出了大量方法来解决该问题，取得了一定的成果。如Qing和Han[1-2]等人从发车间隔对公交系统的影响出发，提出用遗传算法进行公交车发车时间间隔优化；Gong和Cheng[3-5]等人了改进型遗传算法用以优化发车频率问题；文献[6]通过两种算法融合，采用优势互补的特点为优化公交调度问题提供了一种有效途径；文献[7-9]则分别介绍了不同算法在求解公交调度问题最优解过程中的方法。

以上所提及的优化方法对于本文进行优化公交车调度问题具有重要的指导意义。本文提出一种基于离散系统状态空间模型的实数编码智能优化算法[10]。由于状态空间模型的引入不仅能把种群信息以最小信息形式描述出来，而且还能清楚显示算法迭代寻优过程中个体的状态变化，因而该模型可以将问题的求解过程表示为动力学求解过程。基于此，该算法通过构造一个状态进化矩阵来替代遗传算法中的交叉与变异算子功能来产生一组进化解。通过选种池的选择作用产生较优解。相比于遗传算法易陷入早熟停滞、计算量大和局部搜索能力差等缺点[11]，本文提出的算法具有计算量较小、计算精度较高、计算速度较快等特点。最后给出一个公交车发车时间间隔优化实例，仿真结果验证了这种算法的有效性。

2 基于状态空间模型的智能优化算法

2.1 概述

近年来，国内外有不少学者热衷于用不同的方法来解决公交调度优化问题。其中，遗传算法成为人们寻求解决优化问题的重要途径，它通过迭代执行选择、交叉、变异三个遗传算子的遗传操作，使问题的解逐步向最优解方向靠近。本文提出的基于状态空间模型的实数编码智能优化算法是一种以离散系统状态空间模型为基础，引入遗传算法理念的优化算法。它将实数编码问题的解方便地以状态空间模型的方式表示，使得问题的求解过程更直观、高效。

基于状态空间模型的智能优化算法将问题的求解过程表示为离散系统的动力学求解过程，即X′（k+1）=GX（k）（1）其中，状态向量X（k）表示为第k代群体，它是一个N×M矩阵（N表示为种群中个体总数量，M为每个个体包含的变量数）。G为状态进化矩阵（N×N方阵），G的构造是本算法研究的核心内容，可以依照遗传算法的基本思想构造。本文以遗传算法的基本理念构造G，此矩阵替代了在遗传算法中起交叉、变异的遗传操作。本算法采用在约束范围内随机生成的方式来产生初始群体X（0），再通过G矩阵生成群体X′（1），即种群X（k）通过G矩阵生成新的种群X′（k+1）（k=0，1，….）。在种群X′（k+1）中判断其个体是否满足算法约束条件，若不满足，则需进行约束处理，再将包含X（k）与X′（k+1）的共2N个投入选种池。选种池是依照遗传算法中优胜劣汰的思想启发而设计，通过计算2N个个体适应度函数值选择适应度值较大的N个个体组成新一代群体X（k+1），再置X（k+1）为X（k），如此循环迭代，直到满足停机条件后结束，如图1所示。

3 SIA用于公交优化调度

3.1 公交优化调度问题的数学描述

1）模型假设条件

公交发车时间间隔模型的建立要考虑到多种因素的影响，如公交公司满意度、乘客满意度、运行环境等。在同一时段内，若发车间隔较短，公交公司发车次数较多，平均每辆车的载客量减少，环境污染指数升高，不利于公交公司的经济效益和社会效益；若发车间隔较长，乘客平均等待时间较长，乘客的时间损失较大，会影响乘客的情绪，车内人流拥挤，也会影响乘客的舒适度，从而进一步影响乘客一天的生活和工作质量，乘客损失费用较高；若公交车运行环境拥挤，平均每辆车走完全程耗时相对较多，影响公交公司和乘客的整体利益，应适当的调整发车间隔，以舒缓城市交通环境。综上所述，本文对此模型作如下假设：

（1）公车各时段运行环境良好，且营运期间无特殊状况发生；

（2）公车运行期间为恒速行驶；

（3）公车额定载客人数相同；

（4）公车运营一趟的成本为固定值；

（5）同一时段公车发车频率相同；

（6）各时段内到达站点的乘客服从均匀分布；

（7）将乘客上下车时间算入等车时间；

（8）全程实行统一票价，票价2元/人。

2）数学模型的建立

从以上仿真结果可以看出，在α=0.7的情况下，即充分考虑公交公司利益时，发车间隔明显比其他两种情况大；α=0.3时，充分考虑乘客利益，发车间隔明显比其他两种情况小，符合现实情况。同时，根据表2中的客流情况可以看出，时段1和时段4的客流量相对较大，在仿真结果中，这两个时段的发车间隔整体较其他时段小，达到了根据客流合理分配发车间隔的目的。对比GA和SIA优化的发车间隔及其对应的目标函数，可以看出SIA的优化结果明显优于GA，SIA有效性得到验证。

相较于传统遗传算法，SIA的优势在于，通过状态空间模型中矩阵的乘法操作来搜索可行域区间，替代了GA的交叉和变异操作，也在一定程度上减小了算法的计算量。同时，SIA采用实数编码，虽然需要对连续的可行域区间进行离散化，但离散化的计算量较小。而一般情况下，GA采用二进制编码，编码长度决定了算法的寻优精度，精度要求越高，算法编码越长，过长的二进制编码在解码的过程中大大增加了算法的计算量，影响算法效率。故在对寻优精度要求更高的情况下，SIA的优势更加突出。

5 结 论

本文针对公交车调度优化中传统智能算法的不足，提出了一种基于离散系统状态空间模型的实数编码智能优化算法。主要分析了SIA相较于GA在寻优精度和计算量方面的优势。仿真结果表明，在相同的算法条件下，SIA的优化结果明显优于GA，验证了SIA的有效性。参考文献

[1] 韩印.基于遗传算法的智能公交发车频率优化研究[J].计算机工程与应用，2008，44（33）：243-245.

[2] 覃运梅，王玲玲.基于遗传算法的公交发车间隔模型[J].交通标准化，2009，（2）：190-192.

[3] 龚成清.改进遗传算法在公交调度优化中的应用[J].微型电脑应用，2012，28（10）：48-51.

[4] 陈玲玲，苏勇.改进遗传算法在公交车优化调度中的应用[J].科学技术与工程，2009，9（12）：3567-3569.

[5] Jinling Du， Chunxiao Wang， Feng Zhang. Multi-objective Optimization of Bus Dispatching Based on Improved Genetic Algorithm[C]//2011 Seventh International Conference on Computational Intelligence and Security.China：IEEE，2011.

[6] Minan TANG， Enen REN， Chunyan ZHAO. Route Optimization for Bus Dispatching Based on Genetic Algorithm-Ant Colony Algorithm[C]//2009 International Conference on Information Management， Innovation Management and Industrial Engineering.China：IEEE，2009.

[7] 付阿利，雷秀娟.粒子群优化算法在公交车智能调度中的应用[J].计算机工程与应用，2008，44（15）：239-241.

[8] 王敏.免疫克隆算法求解公交发车频率问题[J].计算机应用研究，2010，27（12）：4483-4485.

[9] 白子健.快速公交线路组合频率优化的禁忌模拟退火算法仿真[J].计算机应用研究，2008，25（2）：355-358.

[10]李茂军，贾玲. 一种基于状态空间模型的进化算法[J]. 计算技术与自动化. 2014，33（2）：85-88.

[11]江中央.求解全局优化问题的混合自适应正交遗传算法[J].软件学报，2010，21（6）：1296-1307.