2021年1月第1期（总268)
铁道工程学报
JOURNAL OF RAILWAY ENGINEERING SOCIETY
Jan2021
NO.l(Ser.268)
文章编号：l〇〇6 -2106(2021)01 -0019 -06
基于GA- MADS混合算法的既有铁路
平面线形自动重构*
李伟^张振亚1赵璐■蒲浩2彭先宝3
王杰4王建西5
(1.中南大学，长沙410075; 2.高速铁路建造技术国家工程实验室，长沙410075;
3.中铁第四勘察设计院集团有限公司，武汉430063;
4.中铁第一勘察设计院集团
有限公司，西安710043; 5•道路与铁道工程安全保障省部共建教育部重点实验室
(石家庄铁道大学），石家庄050〇43)
摘要：研究目的：既有铁路平面线形重构是铁路养护维修与增改建设计的重要基础，重构结果对列车运行安
全、养护改建工程量将产生重要影响。既有方法通常先识别确定交点坐标，再逐交点优化半径缓长，属局部重
构，难以实现全局优化；同时对约束的处理还不全面，重构的线形需要经过大量人工调整方可应用。对此，本
文提出一种遗传算法混合网格自适应直接搜索（GA-MADS)的既有线路平面重构方法，实现线路平面整体
自动优化重构。
研究结论:（1)在遗传算法中融人M ADS，有效克服了遗传算法在优化中随机性大、早熟收敛的缺点，实现 平面线形整体重构；（2)各类约束在优化过程中被自动处理，无需人工后续调整；（3)研究成果已在各大铁路
设计院6 000余公里的既有线增改建设计中成功应用，结果表明该方法可以自动产生满足工程约束的优化重
构线形，大幅提高效率和质量。
关键词：铁路；既有线；重构；优化计算；网格自适应直接搜索（M ADS)
中图分类号:U212.33 文献标识码:A
Automatically Recreating a Horizontal Alignment Geometry of Existing Railways Bad on a GA - MADS Hybrid Algorithm
LI Wei1, ZHANG Zhenya1, ZHAO L u', PU Hao2, PENG Xianbao3, WANG Jie4, WANG Jianxi5
什么是一见钟情(1. Central South University, Changsha, Hunan 410075, China；2. National Engineering Laboratory for High Speed Railway Construction, Changsha, Hunan 410075, China；3. China Railway Siyuan S
urvey and Design Group Co. Ltd, Wuhan, Hubei 430063, China；4. China Railway First Survey and Design Institute Group Co. Ltd, Xi’a n，Shaanxi 710043，China ；5. Key Laboratory of Roads and Railway Engineering Safety Control of Ministry of Education, Shijiazhuang Tiedao University, Shijiazhuang, Hebei 050043, China)
Abstract ：Rearch purpos ：Horizontal alignment recreation of exiting railway is an important basis for the railway maintenance and reconstruction. The recreation results greatly affect the train operation safety and the amount of maintenance and reconstruction works. Existing methods usually first identify the point of interction ( P I) and determine its coordinates. And then, the radius and transition curve length of each PI are optimized successively. However, through this recreation method, each PI can only be optimized locally. It is difficult to achieve global
*收稿日期：2020 -07 -30
基金项目：国家重点研发计划（2017Y F B1201102)；国家自然科学基金（51608543,52078497)；道路与铁道工程安全保障省部共建教育部重点实验室（石家庄铁道大学）开放课题（S T K F201901)
##作者简介：李伟，1984年出生，男，副教授。
北伐20铁道工程学报2021年1月
optimization. Moreover, constraints are not handled comprehensively, a lot of manual adjustments are needed before the recreation alignment can be applicable. In this regard, this paper propos a horizontal alignment recreation method of existing railway bad on genetic algorithm and mesh adaptive direct arch algorithm (GA - MADS) , which can realize the automatic optimization and recreation of the overall railway horizontal alignment.
Rearch conclusions:( 1) The integration of MADS into genetic algorithm effectively overcomes the shortcomings of genetic algorithm of large randomness and premature convergence in optimization, which realizes the global recreation of the railway horizontal alignment. (2)Multiple constraints can be handled automatically in the optimization process without manual subquent adjustment. (3) The rearch results have been successfully applied to the extension and reconstruction design of more than 6, 000 km existing railway. The results show that the propod method can automatically generate optimized recreation railway horizontal alignment which satisfies multiply engineering constraints, and improves design efficiency and quality greatly.
Key words：railway；existing railway；recreation；optimized calculation；mesh adaptive direct arch ( MADS)
为保证列车平稳安全运行，铁路部门需定期对既 有轨道线形进行重构与整正。重构结果对列车运行安 全、养护改建工程量具有重要影响1为生成拨道 量最优的重构线形，大量学者进行了相关研究。例如：姚连壁m、郭良浩[2]等对既有铁路线元进行特征分 段，基于分段结果进行拟合并得到重构线形；孙晓丽 等[3]以拟合后的线形为初始解，引人遗传算法对曲线 半径和缓长进行优化，进一步提升了重构效果，但这些 方法的线路交点固定，只能实现逐交点的局部优化重 构；李伟等4提出基于点线一致思想进行线元分段拟 合，将交点坐标加人迭代调整，显著提高了重构效果，但是该方法为逐交点的线形重构，夹直线缺乏调整机 制导致重构线形仍不是整体最优。既有重构方法本质 上是逐交点局部优化，对约束的处理不全面，重构结果 需要经过大量人工调整方可应用。因此，亟需开展顾 及各类约束的线路平面整体重构方法研究。
近年来，遗传算法（GA)在用于新建线路方案的全 局寻优方面取得了一系列进展[5_6]，主要是通过编码 全线线元参数进行迭代运算，且能处理多种约束，对既 有铁路线形全局寻优具有借鉴意义。但该方法搜索随 机性较大，可能需要经过令人无法接受的进化代数才 能生成最优解，且既有铁路约束处理与新建铁路不同。网格自适应直接搜索算法（MADS)能够在迭代中不断 向最小目标函数方向逼近+ 7，具有全局收敛性质，不 依赖于目标函数导数，并可以同时处理多个约束，但自 变量的个数不宜过多，适宜线路局部加速优化。因此，本文将MADS算法融入遗传算法，在遗传运算中采用 MADS对曲线半径和缓长进行优化，避免遗传算法过 大的随机性，并在迭代中处理各类复杂约束，实现既有 铁路平面线形整体自动优化重构。
1优化模型
平面线形重构本质上是在满足各类约束条件下，寻找最优线形参数使线路整体拨道量最小的最优化问 题。本文首先建立了线路平面重构优化模型。
铁路平面线形通常由一组交点描述，单个交点/ 的参数包括交点坐标（U)，前后缓和曲线长/P乂，以及圆曲线半径K。平面线形参数可以描述为如下矩阵：
「芩
乙p i R' K\札=[/^.价代]7=
乂L p n R n L n-
(1)式中P/,—第；个交点的参数;
n----交点总数。
设测点集为P…:
尸W =丨6(〜.，：)〇+)，| 1,2,…，m|I(2)式中'—第_/个测点的横坐标；
r；—第_/个测点的纵坐标；
m----测点总数。
则优化问题的目标函数为
F - min ^- min {M R,Pj)(3)
j e l j e l
式中d】—测点&到重构后平面线形上投影点的
距离，即拨量；
L—计算测点拨量的函数。
其中，直线、圆曲线、缓和曲线线元上测点拨量的 计算方式各不相同，且在既有铁路平面线形重构优化 的过程中还存在大量约束条件。
约束1：最小曲线半径
矣0 i = l，2,3 …，n (4)约束2：最小曲线长i C r n i…
^C m in-a； x^,^° i= 1(5)
约束3：最小缓和曲线长L,…
L…-~，彡〇K，矣0 i= 1，2,3,…，n(6)约束4：最小夹直线长
第1期李伟张振亚赵璐等：基于G A-MADS混合算法的既有铁路平面线形自动重构21
^+ (Yi-Y l_l)2 -r, - r,M z= l，2,3〜，n
l2.I
=(尺，+A.) xtan(a,/2) ■，爪
(7)
T,_t =(/?,_, +p,.t) xtan(a,_,/2) H-m,，!,p,_,
式中T,—第；个交点的切线长；
P,—第i个交点的内移量；
m,----第；个交点的切垂距。
约束5：最大容许拨量
当测点位于桥梁、隧道等重大结构物地段或指定 控制点处，测点的拨量需要控制在一定范围之内。设 所有存在限制测点组成的测点集为E P,,，以线路前 进方向左侧为负，右侧为正，<11V，七^分别为限制测点 G的最小、最大拨量容许值，则有
河虾怎么养彡L(M R'p m y(8)综上，铁路线路平面重构具有以下特点：目标函数 分段、不连续甚至没有显函数解析式，不可微，不可导；约束种类多且最大容许拨量亦无解析式；自变量数量 庞大，为交点数量的5倍，长大线路可达到上百个，搜 索空间巨大。因此，亟需研究对目标函数和约束条件 无可微、可导性要求，且能处理超多设计变量，适用于 海量搜索空间的全局优化方法。
2基于G A-M ADS混合算法的平面线 形重构
2.1 GA - MADS混合算法描述
遗传算法（Genetic Algorithm,GA)通过模拟自然 进化过程进行全局最优搜索，对自变量个数没有限制，不要求目标函数和约束条件可微、连续，其搜索方式具 有全局性和随机性，搜索范围遍及整个解空间，能找到 近乎全局最优解[5<。因此遗传算法较适用于线形参 数优化重构问题，但该方法随机性
偏大，可能需要经过 令人无法接受的进化代数才能生成最优解。网格自适 应直接搜索（Mesh Adaptive Direct Search,MADS)丨7是广义模式搜索 GPS(Generalized Pattern Search)算法 的拓展，它通过不断迭代搜索下降方向和步长求得近 似最优解，具有全局收敛性且不依赖于目标函数的 导数，可同时处理各类复杂约束，但自变量不宜过多，较适宜对线路局部进行加速优化。因此，本文将 MADS融人GA，进行曲线参数的优化，从而充分利用 两者优势，克服GA随机性强、MADS自变量不宜过多 的不足。
2.2初始平面方案
在铁路平面线形中，各线元的方位角变化率特征存在明显差异。因此本文采取测点方位角变化率图初 步识别直线段与曲线段。通过判断测点的方位角变化率与直曲分界阈值/的大小关系可进行曲线识 别，1^1 >/时为曲线测点，反之为直线测点[4]。分 段完成后，拟合线元确定全线的交点坐标、半径、缓和 曲线长度，生成初始平面线形，但其曲线参数并不是最 优解，且部分约束条件可能尚未满足。因此，在此初始 方案的基础上进行顾及各类约束的优化。
2.3 G A-M A D S优化运算
2.3.1编码设计
本文以优化模型中的设计变量夂F,Z p，/?乂作为既有线路染色体的基因进行编码，y l为染色体，A表示 基因，线路平面染色体可表示为
A=[入1，入2，入3，入4，入5，...，八5…_4，入5…-3，入511-2,
入5»-丨，入5；1 ]=[尤丨，K，’p i，尺丨，之1，…，U n，Zpn，尺n，,sn ] = [U2，…s…]
(9)式中5,—
—第；个交点的基因片段，S，表示式为5,=
(m m
2.3.2种群初始化
全局最优方案可在初始方案的一定宽度走廊带 范围内搜索。以初始方案中两交点间夹直线为中心，以夹直线上测点的最大拨道量确定可行搜索范围[形成线路搜索走廊带，如图1所示，搜 索带宽w为
w= 2d m a%(10)设初始种群中交点坐标满足正态分布，以初始方 案交点坐标U,，F,)为期望值(，Uy):
成人高考考试技巧m.v = x i= y：(i i)
根据3〇•原则确定标准差(J为
a- 〇)/6(12)
基于正态分布确定全线交点坐标，同时以交点范 围内测点拨量平方和最小为目标，引人MADS算法优 化半径缓长，并处理各个约束。在生成每个种群方案 时，检查约束条件使生成的方案符合约束要求，不断重 复这个过程，直至产生满足所有条件的种群方案。
2.3.3构建适应度函数
遗传算法进化过程中，适应度函数是每个可行解 质量的评价函数。平面重构拨道量平方和越小，
适应
22铁道工程学报2021年1月度则越大。本文构建如下适应度函数
式中—种群中拨道量平方和最大值；
Fm t…—种群中拨道量平方和最小值；
心—
—第&个线路方案拨道量平方和。
2.3.4遗传算子设计
为提高算法的收敛性，并避免群体早熟，本文采用 排序轮盘法作为选择算子。根据个体适应度值计算 个体选择概率，性能较好的个体遗传到下一代的概率 更大。
本文重新设计了简单交叉、两点交叉、算术交叉和 基于适应度的改进启发式交叉4类交叉算子，如图2 所示。单点变异、多点变异2类变异算子如图3所示。
简单交叉是在两双亲染色体中随机选择某交点, 直接交换该交点之后的双亲染色体基因，形成两个新 的线路方案。两点交叉则是随机选取两个不连续的交 点，双亲染色体交换两点之间的基因片段，设Aa,Ab 为拟进行交叉的双亲染色体，单点交叉与两点交叉流 程如下：
人=[Sa l，…，U a,,".，5m]= [5a l,5b;，...，5b J
.^b = [5m l x = [5bl，…入，5a;，…，
(14)
式中i----[1，n]之间的随机交点号。
j A a= [5a l，5a;，…，\而+1,=[5al，…人.^，5b,，…，Sb”5a;+1，...，5a…]
l/lb = [5bl，•..A,、,5b…] = [5bl，...A w，5a;,•••，〜.為“，…，5b…]
式中D—[1 ,n]之间的随机交点号，且）>i + l。
算术交叉是通过采用一定的比例系数对所有的基 因进行线性组合来完成交叉过程，从而生成两个新的 子代个体。设A,,A2为交叉后的子染色体，则 rA,=(pAa + (l -c p)A h
情人节句子浪漫语录1a2=(pAk+(1 -q>)A,
式中《P—[〇，l]之间的随机数。
传统的启发式交叉是增大适应度高的染色体参与 线形组合交叉的比例，但是会存在优选方案整体最优 但局部可能次选方案更优的情况；本文设计基于自适应度的启发式交叉算子，以平面交点为基本单元，计算 每个交点的适应度值，以此确定基因进化方向，而不是 采用统一的进化方向。对于染色体中随机第i个交 点，有
屮(H.,+)+sa.，对应交点范围内4更优
P(s b,, -S a,,〇 +Sh,，对应交点范围内A b更优
(17)式中—第Z个染色体的i交点的基因;
i----[1,〃]之间的随机交点号。
(C)算术交叉
图2交叉算子示意图(d)
启发式交叉
第1期李伟张振亚赵璐等：基于G A-MADS混合算法的既有铁路平面线形自动重构23
单点变异首先在线路上随机选择平面任意交点 行变异操作：
I在满足搜索带宽及规范约束下，对当前交点基因进
梅州游
A= [5,，…，5,、,，5t，“.，5…]=^V = [5,,…，8:，“.，5…] (18)多点变异是对连续的多交点对应的基因片段进行 因片段进行变异操作。
变异操作，随机选取不相邻的交点i-7'，再对；的基
A= [5,，…，5,—,，5,.，…，5”5川，…，5…]=>A’ = [5丨，…，L，5,’，…，，…，5…] (19)
活板文言文翻译
图3变异算子示意图
2.3.S终止准则
遗传算法通常设置的终止条件分两种：一是遗传 到指定代数71终止，二是前后两代进化甚微时终止。
第一种终止条件容易在种群处于高速进化状态 时，进化被强行终止；第二种终止条件容易使进化在陷 入局部最优时终止。为此，本文设计二者结合的终止 准则以避免以上两种情况。首先，设定终止遗传
代数 当遗传代数达到r之前出现进化甚微即相邻两代
目标函数差值小于给定阈值f时，加大变异操作的比 例，继续进化，如果再连续20代进化依然较慢时则终 止；如果遗传代数达到71时种群处于明显进化阶段，
则增加迭代次数，直到进化程度不大时停止。
2.3.6基于MADS算法的曲线参数优化
为避免GA搜索中随机性过大，需要经过令人难
以接受的进化代数方可生成最优化解，在每次种群初 始化与进化运算中，采用MADS算法进行圆曲线半 径、前后缓长的局部加速优化，同时处理各类约束。考 虑圆曲线半径的变化范围与缓和曲线长度的变化范 围不同，为避免搜索出现局部最优，本文设置初始点 h= e的初始网格尺寸为100 m，/p〇，L的初始网格尺寸为10 m，同时最小曲线半径等 规范约束以及曲线段的控制点约束在优化过程中被处 理。如图4中MADS优化部分所示，主要流程如下：第一，初始化：正跨越集网格尺寸更新参数r，网格尺寸AQ m以及轮询尺寸A P。，迭代次数设置为/c—0。
第二，搜索：在第/c次迭代中，更新网格集自制热气球
Mk= + Ar D z-.z b N"0](20)
其中h为第&次迭代前所有评估过目标函数/的点集。在中选择未评估的点作为试验点计算目
标函数。当新的试验点/(七+1) </(\)出现时，搜索
步骤成功，更新最优解此时可以选择增大A r或 保持¥不变，设a +1，继续执行搜索步骤。无新的试验点使/(%+,) </(心）时，转向轮询步骤3
第三，轮询：当搜索步失败后，生成一个MADS架
构h
Pk^\x k+A：d：d e D k\eM, (21)
其中A是一个正跨越集，且从框架中心^到任意框架点七+Ar ^ e的距离被限制为父的一定倍 数，也就是A r i丨心丨矣A S max|丨丨v e Z)丨。将架 构^上的点用于目标函数评价，如果找到了更优解，那么令+ 1，更新最优解％，转向搜索步。如果轮 询步寻找更优解失败，那么进一步减小网格尺寸以细 化网格，然后转向搜索步。
第四，迭代终止：当两次优化后目标函数值的差小
于设定的阈值，或网格尺寸达到最小网格精度后，迭代 终止。
2.4约束处理
MADS具有强大的约束处理能力，可以处理各类 复杂的线性、非线性约束，甚至不需要解析表达式。NOMAD是基于MADS算法编制的开源软件[8]，平面 重构中的最小曲线半径、最小圆曲线长、最小缓长、最 小夹直线长、曲线段容许拨量约束，可直接编写约束计 算的函数，建立与NOMAD软件的接口，即可在MADS 搜索过程中自动处理。而直线部分的最大容许拨量约 束，已在2. 3. 2节中生成线路走廊带过程中进行了处 理。通过上述方法，可保证既有线平面重构中式(4)〜式(8)的各类约束得到满足。
2.5总体流程
基于GA - MADS混合算法的平面整体线形重构流程如图4所示。
3实例分析
基于上述理论与方法，课题组研发了铁路既有线 平面整体自动重构模块，
目前已在国内众多铁路设计
