遗传算法城市多模式公共交通运行

所构建的随机混合整数线性规划模型可采用与6.2节相同的求解方法，即先将随机问题转化为样本均值近似问题，后利用包含分支定界法的优化求解器如CPLEX求解每一个样本均值近似问题。然而，考虑到6.3.2节所构建模型的优化对象为部分或整个公交网络，所涉及的线路与站点规模将使得分支定界法出现计算时间过长或计算内存不足问题，故设计包含蒙特卡罗仿真方法的遗传算法用以求解上述随机混合整数线性规划模型。所谓包含蒙特卡罗仿真方法，即利用伪随机数生成器产生L个不同情景下随机向量取值，进而将转化为此时，公式（6-49）和公式（6-51）可分别转化为

需要指出的是，当样本量趋于无穷时，蒙特卡罗仿真方法的收敛性已经在众多研究文献中得到验证。

1.遗传算法简介

遗传算法（Genetic Algorithm，GA）是一类借鉴生物界进化规律（适者生存、优胜劣汰机制）演化而来的随机化局部搜索算法，最早由Holland于1975年提出[204]。Goldberg（1989）[205]、Michalewicz（1992）[206]和Chambers（1995）[207]探讨了遗传算法在优化问题中的应用。它是一种基于种群迭代过程的局部搜索算法，每一代种群代表了问题可能的解集。种群由经过基因编码的一定数量的个体组成，而每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的载体，为多个基因的集合，染色体上的每一个位置称为一个基因。由于仿照基因编码的工作过于复杂，通常采用二进制编码。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生越来越好的近似解，在每一代中，根据个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行再生、组合交叉和变异，产生出代表新的解集的种群，该种群在下一次迭代中成为当前种群。这个过程使得新产生的种群比上一代更加适应环境。图6-11描述了遗传算法的基本流程。遗传算法终止条件一般包括：（1）达到最大迭代次数；（2）耗费最大计算资源（如计算时间、计算内存等）；（3）找到最优解；（4）适应度达到饱和。

图6-11　遗传算法的基本流程

与其他局部搜索方法相比，遗传算法具有以下特点：处理的是参数集的编码，而不是直接处理参数本身；搜索一个种群，而非种群中的一个单点；采用目标函数信息，而不是其他辅助知识或信息。这些特点使得遗传算法的应用更加广泛，只需要影响搜索方向的目标函数和相应的适应度函数，而且可以同时对搜索空间中的多个解进行评估，减小了陷入局部最优解的风险。

下面具体介绍遗传算法的三个算子：选择、交叉和变异。

选择算子又称为再生算子。它是一个依据适应度值复制个体的过程[208]，目的是把优化的个体（或解）直接遗传到下一代或者通过配对交叉产生新的个体再遗传到下一代。最简单最常用的方法是轮盘赌选择法，各个个体被选中的概率与其适应度值成正比。假设一个含有n个个体的种群，个体i的适应度值为fi，则i被选中的概率为

交叉算子指按照给定的交叉概率将两个个体的部分结构加以替换重新组合生成新个体的过程[208]。最常用的交叉算子为单点交叉，即在个体的基因串中随机设定一个交叉点，实施交叉时，该点前或后的两个个体的部分结构进行互换，生成两个新的个体的过程，如图6-12所示。

图6-12　单点交叉算子示例(www.xing528.com)

与选择算子和交叉算子相比，变异算子主要起辅助作用[208]。它是按照给定的变异概率调整个体内某些基因值的过程。图6-13示例中下方标注“△”符号的基因其值即发生了变异。引入变异主要是为了：（1）使遗传算法具有局部的随机搜索能力；（2）使遗传算法维持种群的多样性，防止出现早熟收敛现象。变异率的选取一般受种群规模、染色体长度等因素的影响，通常取较小的值。

图6-13　变异算子示例

2.遗传算法求解时刻表协调优化问题

求解公交网络时刻表协调优化问题的遗传算法的第一步是对时刻表调整方案进行基因表达，即在问题的实际表现形式和遗传算法的染色体位串结构之间建立联系，确定编码和解码运算。由于时刻表协调优化问题的决策变量为时刻表整体偏移量xr，它本身是一个属于对称区间范围的整数变量，直接采用基于0和1的二值编码形式并辅以一定的解码运算即可。例如，当用一个10位的二值数b表示xr的值时相当于将xr的变量域离散化为二值域[0　，1023]，此时若xr实际的变量范围为[-　6，6]时，仅需辅以令xr等于（6-b·12/1023）取整结果的解码运算。图6-14给出了染色体基因表达范例。

图6-14　染色体基因排列示意图

编码确定之后，便是初始种群的选择。选择规模较大的初始种群可以同时处理更多的解，因而容易得到全局最优解，其缺点是增加了每次迭代的时间，种群规模一般取30～100[205]。

遗传算法的适应度函数被用于判断种群中个体的优劣程度，是根据所求问题的目标函数来进行评估的。然而根据适应度选择可以进入下一代的个体时容易导致一些较差的个体依然被选中，而丢失部分优秀个体，故直接选择最优的前N个个体进入下一代。例如，某一代开始时有100个个体，通过交叉、变异产生了另外新的47个个体，则选择这147个体中目标函数值最小（本节时刻表协调优化问题为最小化问题）的前100个进入下一代，可保障始终不会遗漏优秀个体。

交叉率和变异率的取值采用试算，即通过分析各比率值的变化对目标函数以及收敛速度的影响进行确定。

终止条件为给定最大的迭代数，算法的遗传迭代数达到最大预设值时，算法终止。

3.包含蒙特卡罗仿真的遗传算法求解步骤

包含蒙特卡罗仿真方法的遗传算法具体流程见图6-15。遗传算法主要用于生成不同的时刻表调整方案。基于给定的时刻表调整方案，蒙特卡罗仿真方法主要用于计算相应的目标函数值。