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

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

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

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 引 言

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

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

2.1 概述

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

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的有效性。参考文献

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

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

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