第35卷第8期武汉大学学报信息科学版Vol.35No.82010年8月GeomaticsandInformationScienceofWuhanUniversityAug.2010:1671-8860(2010)08-0905-04文献标志码:A基于云遗传算法的公交车辆智能调度张飞舟1耿嘉洲1程鹏1(1北京大学地球与空间科学学院,北京市海淀区颐和园路5号,100871)摘要:综合考虑公交车辆运营调度方案的实时性和有效性要求,引入了云模型理论与遗传算法(GA)相结合的云遗传算法。该混合遗传算法充分利用了云模型云滴的随机性和稳定倾向性特点,在遗传算法的优化操作中,由正态云模型的Y条件云发生器实现交叉操作,由基本云发生器实现变异操作,不仅克服了传统遗传算法搜索速度慢、易陷入局部最优解的缺陷,而且提高了算法的收敛性、优化质量及其鲁棒性。实验表明,将该混合遗传算法引人公交车辆运营调度管理中,可大大提高公交车辆调度的实时性与有效性,而且运行服务质量评测分析验证了该优化调度方法的有效性,具有良好的应用前景。关键词:遗传算法;云模型;云遗传算法;公共交通;调度中图法分类号:P208---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---[11,12]城市公交车辆运营调度的任务就是有效管理和合理分配有限车辆资源,调整供需平衡,以解决供需矛盾,达到所求的目标最佳[1,2],而调度问题本身的组合优化特征存在近似复杂性,实际调度系统所采用的数学模型都对运行环境作了大大简化,因此,仅靠已有的寻优改进还远远不能满足运营调度方案的实时性和有效性要求。文献[3-6]的研究都未能从系统角度考虑公交调度系统的整体优化问题。公交时刻表的生成与车辆调度之间存在着有机联系,因此,虽然按照这些既有的模型算法可以得出上述公交调度问题较好的解决方案,却不能够保证系统的解决方案从总体上讲是最优的。本文将云模型理论与遗传算法(geneticalgorithm,GA)相结合,充分利用云模型云滴的随机性和稳定倾向性特点,在GA中运用云模型理论进行交叉、变异优化操作,不但能够维持GA种群的多样性,而且在寻优能力上也得到提高,改善了GA的优化性能及其鲁棒性,从而可提高公交车辆运营调度的效率与车辆调度的稳定性。1云遗传算法性能分析云模型是我国著名学者、中国工程院院士李德毅教授提出的,并逐步完善形成了云模型理论。云模型理论已成功应用于智能控制、数据挖掘、入侵检测、系统评估与评测等领域[8-10]。云模型是一个遵循正态分布规律并具有稳定倾向的随机数集,其三个数字特征用期望值Ex、熵En和超熵He来表征,反映了定性概念的整体特性[10]。GA是一种求解问题的高效并行全局搜索算法。目前研究发现,在调整交叉概率pc和变异概率pm的过程中存在许多模糊概念和信息,这一特点决定了可以用模糊理论工具来获取和处理这些不确定信息。本文充分利用云模型云滴的随机性和稳定倾向性特点,将云模型的Y条件云生成算法实现交叉操作,基本云生成算法实现变异操作,使概率值既具有传统的趋势性,满足快速寻优能力,又具有随机性,实现pc和pm的自适应调整,从而提高了避免陷入局部最优的能力,构成了全新的云遗传算法(cloudgeneticalgorithm,CGA)。CGA优化算法步骤如下:1)初始化种群。2)计算适合度。3)选择、复制和迁移:复制最佳个体至下一代;选择精英群,并复制;淘汰最差个体,被随机产生的外来个体移民所取代。---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---收稿日期:2010-06-15。项目:国家863计划资助项目(2009AA12Z325)。---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---906武汉大学学报信息科学版2010年8月---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---4)对精英群进行交叉操作:按均匀分布随机生成确定度;Ex由父代按适合度大小加权确定;En=变量搜索范围/c1;He=En/c2;由Y条件云生成算法产生两个子代。其中,c1、c2为控制系数。5)变异:Ex取原个体;En=变量搜索范围/c3;He=En/c4;若确定度小于变异概率,由基本云生成算法便可得到变异后的个体。其中,c3、c4为控制系数。6)转第2)步,直到满足停止条件。1.1CGA性能参数正态云是一种泛正态分布,呈现中间多、两头少的特点,这样,参数Ex和En的变化分别影响云模...