基于遗传算法的铁路纵断面优化研究

何祥卫

(中铁第四勘察设计院集团有限公司，湖北武汉 430063)

在解决铁路纵断面优化问题时，首先要建立基于优化算法的数学模型，所以优化算法不单单会对模型的质量产生影响，而且也决定了该模型求解的精度和效率。当前国内应用广泛的算法主要有蚁群算法、二次规划法、梯度投影法等。蚁群算法由 M.Dori于1991年提出［1］，它主要应用于离散空间优化问题，之后很多研究人员对该算法进行改进以适于解决连续性的铁路线路优化问题，但它还不是真正意义上的连续空间优化。二次规划法是一种特殊的非线性规划方法，缺点是以二次函数作为目标函数的海森矩阵很难求得。梯度投影法适用于解决具有线性约束的非线性规划问题［2］，它的弊端是当优化过程接近最优解时，“锯齿”现象频繁发生，从而导致收敛速率下降，最优解难以得到。针对上述方法存在的问题，本文引入遗传算法，此方法可在一个可行域中自动搜索一个最优解或较优解［3，4］，且对求解问题限制较少，可适用于解决传统搜索方法难以处理的纵断面优化问题。

1 建立纵断面优化的数学模型

1.1 优化变量

整个纵断面设计线可由变坡点里程、变坡点的设计高程和相应的竖曲线表达，依照遗传算法搜索求解过程的全局性，笔者在此选取变坡点里程和变坡点的设计高程这两个优化变量，采用改进后的遗传算法进行优化研究。

1.2 目标函数

传统的纵断面优化模型是在纵断面线路设计要素满足适当的约束条件下，尽可能地节约人力物力，减少工程造价成本，所以应把线路的总工程费用作为目标函数进行优化。考虑到实际工程包含路基土石方工程、桥隧工程、支挡工程、涵洞工程等分项工程，将它们分别设立不同的目标函数，并作表达式如下

式中，f1(x)为路基土石方工程费用;f2(x)为桥隧工程费用;f3(x)为支挡工程费用;f4(x)为涵洞工程费用;f(x)为纵断面设计线的总工程费用。

1.3 约束条件

纵断面设计的约束条件包括:坡度约束、坡长约束、起终点高程约束、竖缓曲线重叠约束、平纵组合约束等。

2 基于遗传算法的纵断面优化设计

遗传算法是一种模拟自然选择和生物进化机制的优化算法。1975年，美国的John Holland教授首次提出该算法，它的基本思想来源于达尔文的进化论和Mendel的遗传学说［5］。遗传算法中核心的两个算子是交叉和变异，它们被反复利用到由可以代表问题的解的染色体上。遗传算法基于适应度函数选择合适的染色体，并剔除掉适应性较差的染色体，按照适者生存的原则，通过交叉变异的反复迭代过程产生适应环境的新种群［6，7］。下面对基于遗传算法的纵断面优化模型进行分析阐述。

2.1 编码设计

常见的编码方式是Holland教授提出的二进制编码。为了更好地结合纵断面优化的知识建立模型，本文采用实数编码方式。该编码适用于较大空间的搜索，能解决变坡点位置组合需要较大空间搜索的问题，并将编码的基因与变坡点一一对应起来，能有效提高该模型的精度和效率。

实数编码中每个个体ρ可表示为

式中，Mi为变坡点里程，Hi为变坡点设计高程，i=1，2，3，…，n。

2.2 种群初始化

为了使初始种群具有多样性，减少算法陷入局部解的可能性，本文将采用崎岖度的方法对初始个体进行处理，并挑选最优个体放入初始种群，从而得到适合算法的初始种群［8］。这种方法能使模型在预期内得到最优解，并且能缩减搜索时间。

纵断面方案的初始种群是一系列由崎岖度生成的个体的集合，每个个体分别代表一组解，即一条完整的经连续处理后的纵断面曲线。

2.3 适应度函数的构建

遗传算法进化过程以每个个体的适应度值作为选择依据。纵断面优化的目标是减少线路运营维护费用以及增强机车行驶安全性，并且改良与周边环境的协调性(平面线型已经拟定的情况)。但是现阶段研究尚未明确揭示线路运营维护费用与纵断面线形之间的关系，而且线路与周边环境的协调性也不好量化。在此选取土石方工程费用作为适应度函数变量，基于此目标函数求得个体的适应度值。

要选取遗传进化过程中最优的个体，则需根据土石方费用函数建立适应度函数，计算个体的适应度值，然后将个体的适应度值进行排列选择。该适应度函数如下

式中，n为方案中横断面的个数;Vf(i)、Vc(i)分别为i路段的填、挖体积;Cf(i)、Cc(i)分别为i路段的单位填方及挖方费用。

2.4 遗传操作数

标准遗传算法操作数包含选择、交叉和变异。这3个操作数分别模拟了自然界中生物进化的3个不同阶段，同时这3个阶段也是相互结合相互渗透的。因此，选择合适的或者改变每个算子的排列组合和操作方式，都能极大程度地影响该算法的优化计算结果。

2.4.1 选择策略

在保持种群多样性的前提下为使得算法收敛速度加快，本文采用排序轮盘法选择算子。第一步计算每个个体的适应度值 E(ρi)，其中 i=1，2，…，n，然后对种群中的个体按照其适应度值E(ρi)由小到大排列。选择每个个体ρ的概率pi为

计算个体ρ的累积概率qi为

旋转n次轮盘后，获得新的种群。轮盘方法中放回取样的选择策略容易使新种群产生重复的方案，所以在该过程中，要对重复的新方案进行剔除。选择策略设计流程如图1所示。

图1 选择操作流程

2.4.2 交叉操作

交叉算子是遗传算法中最核心的部分，即把2个配对的染色体在同一位置被切断，基因重组后形成2个新个体。通过交叉操作产生的个体具有离散性强的特征，该特征能够大大增强算法的全局寻优能力。本文采用启发式交叉，将适应度较大的个体向着较优的个体增大的方向移动，交叉后得到更优个体。该交叉方法有利于生成较优个体，能在全局范围内搜索变坡点。

2.4.3 变异操作

变异运算是对个体串的某些基因值做等位替换后形成一个新个体。根据已有经验，优化设计中交叉采用多种变异算子。变异概率Pm通常取0.000 1～0.1。通过变异操作，计算种群中的最优的纵断面方案(即最优个体)与当前个体的差异值，将该值乘以变异概率来调整当前纵断面方案。

2.5 约束条件的处理

上文已经介绍了纵断面设计的约束条件，经过每次迭代后产生新的个体，若个体符合约束条件，则保留用于下一次迭代，若不符合，则剔除并重新迭代。

2.6 停止规则

利用遗传算法进行纵断面优化的目标是为了寻得可行解中的最优方案，并且该方案能满足事先设定的所有约束条件。上述过程已经完成了一次完整的迭代，是否继续取决于算法的停止规则。一种是指定一个最大的遗传代数G，当进化迭代次数达到G时即停止;另一种是对各代的最佳解进行监控的方法，动态确定停止规则。即当前的最好解在连续20代没有变化时即停止计算。否则，将继续迭代。在本文中采用后一种方法。

3 算法实现过程

基于遗传算法与动态监测最优解的方法需要通过许多次的迭代才能不断地接近最优解，该过程用人工计算几乎不可能实现。本文为解决该算法繁琐冗长的计算过程，在VS.NET下利用AutoCAD二次开发平台和遗传算法方法编制了纵断面优化程序，以期提高程序的执行效率。纵断面优化程序流程如图2所示。

4 结语

本文引进了模拟生物进化过程和遗传机理的遗传算法，该算法具有全局优化和对问题提供启发式等特点，将遗传算法应用于纵断面优化模型，能更便捷地解决多峰函数优化问题以及无解析表达式的目标函数优化问题，提高优化模型的计算效率，减少设计人员的工作任务量，具有很好的适用价值。但是，遗传算法的应用依然存在一些适应度函数及有效约束处理上的问题，在接下来的研究中，应重点考虑改进遗传算法的构造方式。

图2 纵断面优化程序流程

［1］段海滨.蚁群算法原理及其应用［M］.北京:科学出版社，2005.

［2］詹振炎.梯度投影法及其在铁路纵断面设计中的应用［J］.长沙铁道学院学报，1979，26(4):32-37.

［3］Eungcheol Kim，Manoj K.Jha，Bongsoo Son.Improving the computational efficiency of highway alignment optimization models through a stepwise genetic algorithms approach［J］.Transportation research part B，2005，17(39):339-360.

［4］Goldberg，D.E.Genetic Algorithms in Search，Optimization，and Machine Learning［M］.Massachusetts，Addison-Welsey Publishing Company Inc，1989.

［5］杨献波.基于遗传算法的公路纵断面优化研究［D］.南京:东南大学，2006.

［6］陈国良.遗传算法及其应用［M］.北京:人民邮电出版社，1996.

［7］李敏强.遗传算法的基本理论与应用［M］.北京:科学出版社，2002.

［8］许金良.集成化公路CAD系统研究与开发［D］.西安:长安大学，2002.