浅谈遗传算法基于公交智能调度的应用研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇浅谈遗传算法基于公交智能调度的应用研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：本文利用遗传算法与免疫算法各自的特点以及二者的共性提出了一种新的优化方法——免疫遗传算法，将免疫算法融入到遗传算法当中，构成一种改进的遗传算法，并应用于解决公交调度管理中的优化中，与利用简单遗传算法的计算过程进行了仿真和对比。

关键词：静态调度；公共交通系统；免疫遗传算法

中图分类号：G650 文献标识码：A 文章编号：1003-2851（2012）-09-0180-01

遗传算法[（genetic algorithm，GA）是一种自适应大规模并行搜索优化算法，较以往传统的搜索算法具有使用方便、鲁棒性强、便于并行处理等特点，因而广泛应用于解决搜索和优化的问题。但由于遗传算法不能很好地维持解种群中个体的多样性，易趋于“早熟”收敛而陷入局部最优解。因此，遗传算法不能保证一定能找到问题的全局最优解，目前公交公司各车队的排班主要依靠工作人员的经验手工进行，虽然它具有一定的实用性，但它存在着明显的不足，很难保证排班的结果在运营效率等方面是最优或者接近最优的。为满足实际应用需求，采用智能化算法来求解车辆调度优化问题，在有限的算法步骤内，找出所有满足约束条件的排班方案中的最优方案或接近最优的方案。

一、遗传算法

1.遗传算法简介

遗传算法（Genetic Algorithms，GA）是一种基于自然选择和基因遗传学原理的自适应全局优化概率搜索方法。它的创立有两个研究目的：一是抽象和严谨地解释自然界的适应过程；二是为了将自然生物系统的重要机理运用到工程系统中。GA从许多点开始并行操作，在解空间进行高效启发式搜索，因而可以有效地防止搜索过程收敛于局部最优解；遗传算法在计算机上模拟生物的进化过程和基因的操作，通过目标函数来计算适配值，并不需要对象的特定知识，它具有全局寻优的能力，能解决高度复杂的问题，被广泛应用于自动控制、图形处理、电力调度等方面。

2.建立调度的数学模型

调度系统所采用的数学模型对运行环境做了简化：车的速度恒定，保持匀速行驶，无特殊事件发生；以分钟作为最小的时间单位，这对安排时刻表是合理的；假设客流模型能反映该段线路上的日常客流量（我们假设到站乘客服从均匀分布，在不同时段有不同的分布密度）。

首班车发车时刻为早上6点整，末班车发车时刻为22点整，所有运营车都在整分钟时刻发车，一天之内的总班次为m，总时间为16小时，即960分钟。用xm表示第m辆运营车发车时刻距首发时刻的时间，以分钟为单位。决策变量为X=[x1，x2，…xn]；染色体X是一个完整的发车时刻表，其中的每个基因为一个车辆的发车时刻。

免疫算法效仿生物免疫系统，把外来侵犯的抗原和免疫产生的抗体分别与实际求解问题的目标函数以及问题的解相对应，生成的抗体能有效地排除抗原，也就相当于求得了问题的最优解；对与抗原亲和力高的抗体进行记忆能促进快速求解。

二、IGA应用于公交动态调度

现仍采用上面建立的数学模型，初始规模N仍为200且不随进化代数而发生变化，便于IGA和GA比较。现利用IGA来进行优化的步骤为：

1.在解空间内随机生成初始群体，并计算其适应度，确定最优个体x0best，并给出的取值？滓0，A取为1，？滓0i取为3，？滓？孜取为0。

2.根据式（4.7）进行进化操作，在解空间内生成子代群体，规模为N。

3.计算子代群体的适应度，确定最优个体xt+1best，若f（xt+1best）>f（xtbest），则选定最优个体为xt+1best，否则最优个体为xtbest。

4.重复执行步骤2和3，直至达到终止条件，这里T取为100，选择最后一代的最优个体作为寻优的结果。

本文在遗传算法的基础上采用了一种较新的混合遗传算法——免疫遗传算法对公交静态调度进行了研究，并对二者的应用结果进行了仿真和比较，结果表明IGA有效的克服了简单GA的不足之处，并提高了寻优过程当中目标函数的收敛速度，并得到了合理的发车时刻表，可以提高公交企业的服务水平，对改善城市交通问题和节约市民出行时间有相当的实际意义。

参考文献

[1]倪长健.免疫进化算法研究及其在水问题中的应用[D].四川大学博士论文，2003：50-51.

[2]周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，1999.

[3]史忠植.知识发现[M].北京：清华大学出版社，2002.