城市公交方法：包含蒙特卡罗仿真的遗传算法

越站控制问题实际上是一个非线性0-1规划问题，若公交线路上站点个数N=20，则越站形式有218=262 144种，采用枚举算法较为繁琐，故设计遗传算法进行求解。

设计求解越站控制问题的遗传算法的第一步是对越站形式进行基因表达，即在问题的实际表现形式和遗传算法的染色体位串结构之间建立联系，确定编码和解码运算。由于越站问题的决策变量为yi，j，它本身是一个0-1变量，当yi，j=0时，车辆i越过站点j，当yi，j=1时，车辆i在站点j处停靠。因此，可以直接采用二值编码形式，如图10-2所示。

图10-2　越站问题染色体编码示意图

编码确定之后，便是初始种群的选择。选择规模较大的初始种群可以同时处理更多的解，容易得到全局最优解，但其缺点是增加了每次迭代的时间。初始种群中的个体是随机产生的，先随机生成一定数目的个体，看是否满足约束条件（10-4），然后从中挑出最好的个体加到初始群体中。这个过程不断迭代，直到初始群体中个体数达到了预先确定的规模。

遗传算法的适应度是用来判断群体中个体优劣程度的指标，可根据所求问题的目标函数值来进行评估。然而适应度的方法容易导致一些较差的个体依然被选中，从而丢失好的个体。因此，设计求解越站问题的遗传算法时直接选择最优的前个个体进入下一代。例如，一代开始时，有50个个体，通过交叉和突变，又有了26个个体，那么就选择这76个个体中，目标函数值最小的前50个进入下一代。这样可保证好的个体始终不会丢失。

关于交叉率ρc和变异率ρm的选取。交叉算子采用单点交叉法，交叉率ρc和变异率ρm则采用试算，即通过分析交叉率ρc和变异率ρm值的变化对目标函数值以及收敛速度的影响，最终确定比率值。

终止条件为给定最大迭代数，即当算法遗传代数达到给定最大迭代数时，算法终止。

考虑到行驶时间为随机变量，增加了模型求解难度，故最终设计包含蒙特卡罗仿真的遗传算法获取模型（近似）最优解。基于给定的车辆1的越站形式，蒙特卡罗主要用于计算各参数值和目标函数值。遗传算法主要用于生成车辆1的不同的越站形式。

1.蒙特卡罗过程

Step 1：初始化。令抽样次数表示目标函数值的估计值。惩罚参数M为一个足够大的已知正数。

Step 2：取样。对于公交车辆i，基于站点j-1和站点j之间的行驶时间服从的分布函数，产生一组站点间行驶时间样本(www.xing528.com)

Step 3：参数计算。利用样本行驶时间值，计算各参数值。

Step 4：目标函数值计算。计算目标函数值，记为检查约束条件（10-1）是否满足，若不满足，令目标函数值

Step 5：检查是否停止算法。mmax为设定的样本规模，若m＞mmax，则算法停止并输出目标函数估计值否则，令m=m+1，并跳转至Step2。

Step 6：更新并计算

2.含蒙特卡罗仿真的遗传算法

Step 1：初代种群。设种群规模为n，交叉率为ρc，变异率为ρm，采用伪随机数产生器生成初代种群中的染色体，令种群代数k=1。染色体的第一个基因和最后一个基因均为1，以满足约束条件（10-4）。

Step 2：交叉。对每一个染色体，设一个附加的γ（k）值，γ（k）为服从[0，1]均匀分布的随机数。将γ（k）＜ρc的染色体集中起来，并进行配对。然后，对选中的每一对染色体，在1至N间取一个整数交换染色体中的前个基因，即可形成两个新的染色体。

Step3：变异。对所有的染色体上的每一个基因（除第1个和第N个基因外），设一个附加的值为服从[0，1]均匀分布的随机数。若则改变该基因的值（从0变为1，或者从1变为0），从而生成新的染色体。

Step4：计算。每一个染色体代表了一种中途站越站控制形式。采用蒙特卡罗过程计算每一个新生成的染色体的目标函数值

Step5：选择。将所有染色体的目标函数值z-按从小到大进行排序，选择前个染色体作为优选出的染色体。

Step6：检验是否停止算法。kmax为设定的最大迭代次数（即种群代数），若k＞kmax，算法停止并输出优选出的染色体的目标函数值中的最小值以及对应的染色体；否则，令k=k+1，并跳转至Step2。