文档介绍：遗传算法在云计算应用实例
一、应用实例背景
城市公交车辆运营调度的任务就是有效管理和合理分配有限车辆资源, 调整供需平衡, 以解决供需矛盾, 达到所求的目标最佳, 而调度问题本身的组合优化特征存在近似复杂性, 实际调度系统所采用的数学模型都对运行环境作了大大简化, 因此, 仅靠已有的寻优改进还远远不能满足运营调度方案的实时性和有效性要求。文献[ 3- 6] 的研究都未能从系统角度考虑公交调度系统的整体优化问题。公交时刻表的生成与车辆调度之间存在着有机联系, 因此, 虽然按照这些既有的模型算法可以得出上述公交调度问题较好的解决方案, 却不能够保证系统的解决方案从总体上讲是最优的。本文将云模型理论与遗传算法( ic algo rithm, GA) 相结合, 充分利用云模型云滴的随机性和稳定倾向性特点, 在 GA 中运用云模型理论进行交叉、变异优化操作, 不但能够维持 GA 种群的多样性, 而且在寻优能力上也得到提高, 改善了 GA 的优化性能及其鲁棒性, 从而可提高公交车辆运营调度的效率与车辆调度的稳定性。
二、算法简介
云模型是一个遵循正态分布规律并具有稳定倾向的随机数集, 其三个数字特征用期望值 Ex 、熵 En 和超熵He 来表征, 反映了定性概念的整体
GA 是一种求解问题的高效并行全局搜索算法。目前研究发现, 在调整交叉概率pc和变异概率pm 的过程中存在许多模糊概念和信息, 这一特
点决定了可以用模糊理论工具来获取和处理这些不确定信息。本文充分利用云模型云滴的随机性和稳定倾向性特点, 将云模型的 Y 条件云生成算法实现交叉操作, 基本云生成算法实现变异操作, 使概率值既具有传统的趋势性, 满足快速寻优能力, 又具有随机性, 实现 p c 和 p m 的自适应调整, 从而提高了避免陷入局部最优的能力, 构成了全新的云遗传算法
三、应用实验实例
公交车辆运输调度问题就是指在固定行驶线路上, 根据不同时段、依照一定的先序关系, 合理编排运输车辆运行的作业形式, 达到供需平衡, 满足性能指标。这里以公交车辆的先序关系调度作为研究对象, 该调度问题有如下特点: M 为公交车辆集, 每辆车在运输运行中只从事一种运输方式。 J 为车站集, 如某运输线路有 J 1 ...J j 等j 个车站, 每辆车必须依次停站, 且可跨站运行( 如快车) 。每辆车应按时到达各车站, 尤其是重点车站, 尽量减少停站时间, 根据不同的运行时段, 准
时完成运输任务。
公交车辆运输调度采用的优化指标是: 在平峰或者高峰时段, 根据公交车辆运行定额, 使运输车辆的运营周转时间最短作为优化指标, 并尽量不延误, 以避免出现串车或大间隔, 为此, 对超期延误车辆在优化指标中添加惩罚项。此外,还应满足车辆运行的先序约束关系。其目标函数定义为:
其中, T0 为从第 1 辆车发出到第 k 辆车返回后的运输车辆的周转时间
; Ti 为第i 辆车完成整个运输任务的运行定额时间, 即起点到终点的运输时间; tsj 、tdj 分别为到达第j 车站的服务时间和规定的服务时间; 为惩罚项加权系数, 根据公交车辆不同的运营时段采取相应的惩罚系数。
假设第 m 辆车的运行作业序列为:OP ( m) ={ Om