《遗传算法在云计算应用实例》由会员分享，可在线阅读，更多相关《遗传算法在云计算应用实例（4页珍藏版）》请在装配图网上搜索。
1、遗传算法在云计算应用实例-公交车智能调度一、应用实例背景城市公交车辆运营调度的任务就是有效管理和合理分配有限车辆资源 , 调整供 需平衡, 以解决供需矛盾 , 达到所求的目标最佳 , 而调度问题本身的组合优化特 征存在近似复杂性 , 实际调度系统所采用的数学模型都对运行环境作了大大简化 , 因此, 仅靠已有的寻优改进还远远不能满足运营调度方案的实时性和有效性要求。 文献 3- 6 的研究都未能从系统角度考虑公交调度系统的整体优化问题。公交时刻 表的生成与车辆调度之间存在着有机联系, 因此, 虽然按照这些既有的模型算法可 以得出上述公交调度问题较好的解决方案 , 却不能够保证系统的解决方案从总体
2、 上讲是最优的。本文将云模型理论与遗传算法( genetic algo rithm, GA) 相结合, 充 分利用云模型云滴的随机性和稳定倾向性特点 , 在 GA 中运用云模型理论进行交 叉、变异优化操作, 不但能够维持 GA 种群的多样性, 而且在寻优能力上也得到提 高, 改善了 GA 的优化性能及其鲁棒性 , 从而可提高公交车辆运营调度的效率与 车辆调度的稳定性。二、算法简介云模型是一个遵循正态分布规律并具有稳定倾向的随机数集 , 其三个数字特征 用期望值 Ex 、熵 En 和超熵 He 来表征, 反映了定性概念的整体GA 是一种求解问题的高效并行全局搜索算法。目前研究发现 , 在调整交叉
3、概 率 pc 和变异概率 pm 的过程中存在许多模糊概念和信息 , 这一特点决定了可以用 模糊理论工具来获取和处理这些不确定信息。本文充分利用云模型云滴的随机性和 稳定倾向性特点, 将云模型的 Y 条件云生成算法实现交叉操作 , 基本云生成算法 实现变异操作, 使概率值既具有传统的趋势性, 满足快速寻优能力, 又具有随机性, 实现 p c 和 p m 的自适应调整, 从而提高了避免陷入局部最优的能力, 构成了全 新的云遗传算法三、应用实验实例3.1 公交车辆调度问题公交车辆运输调度问题就是指在固定行驶线路上, 根据不同时段、依照一定的 先序关系, 合理编排运输车辆运行的作业形式 , 达到供需平
4、衡, 满足性能指标。这 里以公交车辆的先序关系调度作为研究对象 , 该调度问题有如下特点 : M 为公交 车辆集, 每辆车在运输运行中只从事一种运输方式。 J 为车站集, 如某运输线路有 J 1 .J j 等 j 个车站 , 每辆车必须依次停站 , 且可跨站运行 ( 如快车 ) 。 每辆车应 按时到达各车站, 尤其是重点车站, 尽量减少停站时间, 根据不同的运行时段 , 准时完成运输任务。公交车辆运输调度采用的优化指标是 : 在平峰或者高峰时段 , 根据公交车辆运行 定额, 使运输车辆的运营周转时间最短作为优化指标 , 并尽量不延误, 以避免出现 串车 或 大间隔 , 为此, 对超期延误车辆在
5、优化指标中添加惩罚项。此外 ,还应满足车辆运行的先序约束关系。其目标函数定义为:其中, T0 为从第 1 辆车发出到第 k 辆车返回后的运输车辆的周转时间; Ti 为第 i辆车完成整个运输任务的运行定额时间, 即起点到终点的运输时间; tsj 、tdj 分别为 到达第 j 车站的服务时间和规定的服务时间; 为惩罚项加权系数, 根据公交车辆不 同的运营时段采取相应的惩罚系数。3.2 遗传编码假设第m辆车的运行作业序列为:OP ( m) = Oml , Om2，,0mJ( m) 。其中,0mj为第 m辆车运行到第j个车站;J ( m)为第m辆车运行的车站数目，即第m辆车所属 的行车类型。车辆运营调
6、度序列可表示为:SOP(m)二 /QP(m) I /Ji 由于编码方式的选取是基于要求解的问题，若按照车辆的行车类型进行编码，即 自然编码方式, 则可对每辆车的运行序列分别进行编码, 每辆车的运行序列就相当 于子染色体, 由所有的子染色体构成个体, 各染色体均有一定的独立性。3. 3 遗传操作与适合度计算在公交车辆排序问题中强调的是基因位置,基因本身并不变化, 通过各基因位置的 改变而得到不同的排列序列。由于排序问题的特色, 使得应用 CGA 混合遗传算法 求解这类问题时，运用云模型进行个体更新，即由Y条件进行交叉优化操作，由 正向云进行变异优化操作。根据调度结果可计算每一染色体相对应的优化指
7、标 T 0 ， 从而可决定它的适合度值 f。式(1)要求最小化性能指标T 0，而GA中是最大化适合度值，因此采用变换 函数将染色体的优化指标值 T 0 映射为它的适合度值， 采用变换函数 f = cT 0 + d， 其中， c、d 为常数。 c、d 值的选取应使得群体规模在初始化后， 它们的适合度值映 射到区间 C， D 上， 其中 C = 300 对应性能指标最小值 T 0min ， D = 30 对应性 能指标最大值 T 0max ， 以便保持群体之间适合度值的差别， 并使得适合度最小的 个体也有机会参与竞争。3.4 优化调度仿真实验本文以北京市公交公司某车队 375 路运营线路 （西直门
8、-北宫门）为研究对象 ,运用 CGA 进行公交车辆运营调度方案或策略的研究。为了使仿真实验研究尽可能接近实 际情况,CGA直接采用十进制编码，由云模型进行个体更新，并通过性能指标函数式（1） 中惩罚项的不同取值,来反映公交车辆在不同时段的实际运行环境。经过调查得知,北京市公交公司 375 路运营车队共有 18 辆运营车,即 36 车次运营车 （往返）, 其中包括全程车、区间车、快车以及机动车四种类型。运营线路共设有 17 个停车站,起点到终点运营时间以 50min 为正点运营时间。当运营车辆最初和运输结 束后处于空闲等待状态时,其操作为 0。现在假定运营车辆各站间的行驶时间、各站 停靠时间相同
9、，其运营参数设定如下:运营车辆发车间隔为8min,即t_interval=8min; 每 站 停 靠 时 间 为 0.25min, 即 t_stop=0.25min; 每 站 间 行 驶 时 间 为 2.9min, 即 t_run=2.9min。为了便于研究，本文在平峰时段进行了仿真实验，这里仅取三种类型（全 程车为 0，快车为 1，区间车为 2）的 36 车次运营车辆，其中 36 车次中全程车占 2/3，快车 占 1/6，区间车占 1/6。这里研究的目标函数是在式（1）的基础上考虑在行车车次、行 车间隔一定，通过不同的行车顺序、不同的行车类型组合排序 ，达到最快的周转速度 （即minTO），
10、以提高公共车辆的运营速度,减少乘客的旅行时间。为方便起见，设定公交 车辆运行在平峰时段，惩罚项依照标准正态分布随机产生;运行在高峰时段，惩罚项采 取固定值方法。假设CGA中群体规模为40,采用十进制编码，由云模型进行个体更新。在公交运 营车辆 36 车次规模的情况下，达到最短的运营周转时间，得到的最终仿真实验结果为 。若发车间隔采用8min，只需13辆公交车就能满足一次周转，其周转时间为 366.2min，计算时间与代数分别为0.08s、7.83;若采用18辆公交车，采取上述的编排发 车方式，其发车间隔只需 5.5min 即可，其计算时间与代数分别为 0.11s、 12.37。由此可 见，采用 CGA 公交车辆运营优化调度，能够合理分配公交车辆资源，有效地调整供需 平衡，比文献1的优化效率高，这为建立完善的公交车辆运营调度措施提供了必要的 技术支持。关键词：云遗传，公交调度优化，有效管理
遗传算法在云计算应用实例
