遗传算法在道路纵断面设计优化中的应用探索

张明亮

（中铁第五勘察设计院集团有限公司郑州分院 河南郑州 450001）

1 引言

道路纵断面设计优化是一个复杂的过程。需要综合考虑道路性质（等级、车道数、设计速度、服务对象）、建设条件（地物、地形、地质、水文等）、沿线构造物（路基、桥梁、涵洞、隧道等）多方面因素，得到平纵组合合理、平顺、流畅的线形，并达到费用省、行车安全、养护简单的目的。

在纵断面设计过程中，传统人工拉坡方式具有较强的主观性，受经验、精力、时间所限，即使反复的试坡、调整、核对，也无法保证结果最优。设计成果的优劣，与设计人员的技术水平和经验关系甚大[1]。

为了消除人的主观因素影响，国内多人尝试采用如遗传算法[2]、动态规划法[3]、蚁群算法[4]、自由落体法[5]等诸多计算方法，通过建立数学模型，进行纵断面优化任务的自动化尝试。然而当路线长度较长时，解算规模爆炸式增长，存在对计算机性能要求苛刻、运算时间过长等问题，难以满足一般设计工作的需求。

经实践探索，运用遗传算法，通过精细化参数控制、优化进化策略，能够有效减小解算规模，实现纵断面设计优化的目的。

2 遗传算法简介

遗传算法是计算机科学人工智能领域中用于解决最优化问题的一种启发式搜索算法[6]。其基本思想是模拟自然进化过程，通过对群体中具有某种特性的个体进行量化识别，通过“优胜劣汰”的筛选机制，经自然选择、遗传、杂交、突变等操作，生成下一代新的群体，使群体内的个体对所处环境的适应性相对上一代不断提高。如此经过若干代的循环，逐渐接近更优的解。

遗传算法的基本流程如图1所示。

图1 遗传算法 基本流程

3 算法实现

遗传算法的术语描述，以及其在纵断面优化设计应用的实际意义，列表对照见表1。

表1 算法概念对照

3.1 优化变量的选取

路线纵断面设计成果有:纵断面图、纵坡竖曲线表，实质核心内容为路线中多个变坡点信息的集合。单个变坡点可归结为3项基本信息:变坡点桩号（L）、变坡点高程（H）和竖曲线半径（R）。而其他要素诸如坡长、坡度、竖曲线长、改正值等内容，均可由前述3项基本信息通过变换计算得到。

根据经验，在多数实际项目中，竖曲线半径的调整对优化结果表现不明显[7]。故仅把变坡点桩号（L）、变坡点高程（H）作为设计优化变量。

3.2 编码解码方案

遗传算法编码中，目前常用有二进制编码、字符编码、浮点数编码等编码技术。本次探索采用最简单、最易用的二进制编码方案。

假设优化区段起点桩号为L0，终点桩号为L1，高程取值范围为h0～h1。

（1）桩号编码、解码

考虑到变坡点桩号在小范围微调对整体方案的影响有限，为了控制解算规模、提高效率，桩号编码的精度采用10 m。

则桩号编码的二进制位长的计算公式如下:

式中，n1为桩号编码的二进制位长度；L0为区段起始桩号（m）；L1为区段终止桩号（m）。

每一个变坡点桩号的二进制编码采用n1位长的{0，1}字符串表达，其转换为十进制的正整数，记作Xi。则对应的桩号解码公式为:

式中，Li为解码后的桩号值（m）。

（2）高程编码、解码

高程编码的精度采用0.05 m。

则高程编码的二进制位长的计算公式为:

式中，n2为高程编码的二进制位长度；h0为高程范围最小值（m）；h1为高程范围最大值（m）。

每一个变坡点高程的二进制编码采用n2位长的{0，1}字符串表达，其转换为十进制的正整数，记作Yi。则对应的高程解码公式为:

式中，Hi为解码后的高程值（m）。

3.3 边界条件的表达

在纵断面设计优化过程中，边界条件主要是指某些位置的高程控制条件[8]。主要可分为三类，即:上限点、下限点、必经点。

为了后续操作方便，对三类高程控制条件进行归一化处理，形成统一格式:桩号、下限高程、上限高程。详见表2。

表2 边界条件的数据描述

3.4 初始群体的产生

若群体规模过小，多样性不足会导致寻优失败。而群体规模过大，又会出现解算规模大、运算效率低的现象。经测试，初始群体取10～20是较为合理的规模。

初始群体中个体的变坡点个数，可按照道路等级、道路长度进行估算。平均坡长可按照当前道路设计速度对应最小坡长[9]的2～5倍进行估算。当地形复杂、道路等级低时，变坡点个数可取大值；当地形平坦、道路等级较高时，变坡点个数宜取小值。

需要特别指出的是，该处变坡点个数的初值确定，并不会对优化最终结果的变坡点个数造成影响。

通过随机生成二进制字符串的方法，逐变坡点、逐条纵断进行填充，形成第一代初始群体。

3.5 适应度函数构建

遗传算法中，所谓适应度函数是判断群体中每个个体优劣的标准。适应度函数构建的优劣，对遗传算法的性能影响甚大，若适应度函数构建不当，则有可能达不到整体最优效果。

考虑到不同的纵断面方案，有着不同的路、桥、隧比例，同时对应不同的费用。在纵断面设计优化的应用中，可将一条纵断面方案的工程数量、估算费用[10-11]作为评价适应度的基本指标。

（1）工程数量

为了将工程规模自动随着纵断面方案进行联动，采用的方法是:首先按照一定桩号间隔（一般取值2～20 m），逐桩号计算填挖高度，然后根据预设的起桥高度值、设隧深度值对全线进行桥梁、隧道桩号段落进行初步分划，最后对桥隧段落进行检查整合处理（例如:取消过短的桥梁、合并间隔较小的桥梁、合并间隔较小的隧道等）后，形成最终的路基、桥梁、隧道段落。

逐段估算工程数量。桥梁、隧道工程数量估算仅逐段计算延米长度；路基内容相对略为复杂，由于是估算，为控制资源开销，可暂假定横断面地面线为水平、假定无超高无加宽，路基土方数量、边坡面积、路面面积等工程数量仅为路基宽度、边坡坡度、填挖高度的函数，逐段落、逐桩号计算即可获得。

（2）估算费用

不同的纵断面方案，有着不同的路、桥、隧比例，同时对应不同的费用。根据预设单价指标、前述工程数量进行费用估算。即实现工程费用自动

随着纵断面方案进行联动。估算费用公式为:

式中，Fi为个体对应的估算费用合计值（万元）；FL为路基工程费用（万元）；FQ为桥梁工程费用（万元）；FS为隧道工程费用（万元）；FD为用地及其它工程费用（万元）。

（3）适应度计算

根据遗传算法后续选择操作的要求，适应度应为正数。而工程费用虽然为正，但优化的目标是要费用最省，故可根据工程费用进一步变换计算得到适应度。

适应度计算公式为:

式中，fi为个体的适应度值（万元）；Fmax为当代群体中估算费用的最大值（万元）。

3.6 遗传操作

以群体中的所有个体为对象，依次进行选择、杂交和变异三项基本操作。

（1）选择

选择操作的前提，应先对每个个体进行适应度评价。在纵断面设计优化应用中，采取最优保存策略[12]，即适应度最高的个体不参与后续杂交和变异，而是用它来替换掉当代群体中适应度最低的个体。

其实际意义在于:当前最好的纵断面方案，直接进入下一轮计算，可以保证寻优过程不会倒退。具体操作策略见表3。

表3 选择策略描述

（2）杂交

杂交操作是将配对后的两个个体通过交换部分基因编码的形式，形成两个新的个体。具体操作为:将群体内适应度排序在0%～90%的个体进行随机配对，以随机桩号为交叉点，逐对进行单点交换，从而形成两个新的下一代个体。

在纵断面设计优化应用中，交叉点的概念具有特殊性，并非是二进制编码的序号位置，而是桩号位置。

（3）变异

变异操作是将随机位置处的编码进行改变，从而改变个体编码串的内容，变异是遗传算法具有局部搜索能力的关键。在纵断面设计优化应用中，由于采用的是二进制编码方案，故这里采用基本位变异的方法。

具体操作为:针对群体内的每一个个体，以指定的变异概率随机选择，在随机变异点位置进行取反运算（即把1替换为0、把0替换为1），从而形成新的个体。

3.7 终止条件

纵断面设计优化计算，在满足下列条件之一时终止:

（1）达到预定代数时。预定代数可设为100～500代。

（2）连续10代中，最优纵断面方案的估算费用、适应度值无变化时。

（3）累计运算时间达到600 min。

4 程序实现

在通用CAD软件平台采用Visual LISP语言进行二次开发，编制纵断面优化设计软件工具，验证前述算法的有效性。

考虑到在适应度函数中关于工程数量的计算，需调用路线软件中的相应功能模块、计算负荷较大，为了避免多次重复计算引起的时间消耗，在软件内维护一个全局表，用于存放不同填挖高度所对应的工程数量。

在运用时，根据当前填挖高度数值查询该全局表，若有记录则直接取用；若无记录，则先调用外部函数计算当前填挖高度数值对应的工程数量，然后将工程数量写入全局表中，供后续查询使用。如此可极大地节约运算时间。

5 算例

以山西省某一级公路新建工程为例，双向四车道，路基宽度24.5 m，设计速度80 km/h。拟优化路段桩号范围为K15+400～K18+580，高程范围为680～720 m。

参数取值计算如下:

式中，n1为桩号编码的二进制位长度。

式中，n2为高程编码的二进制位长度。群体规模取20。

初始群体变坡点间距取2.5倍的最小坡长规范值，即为500 m，则变坡点个数估算为5个（不含起终点）。

初始群体中，个体的编码长度为95位。

预定代数取100代，杂交概率取0.4，变异概率取0.05。

在个人计算机上运行前述算法，在达到预定代数后，取出最后一代的最优个体，经解码后形成道路纵断面设计成果。

6 结束语

（1）运用遗传算法，通过精细化参数控制、优化进化策略，可有效减小解算规模，能够实现道路纵断面设计优化的目的，经实践验证该方法可行。

（2）在本次应用探索中，由于仅对变坡点桩号及高程进行编码求解，故初始方案中竖曲线半径的预估设定对优化结果尚有一定的影响。后续研究可尝试对桩号、高程、半径三者进行综合编码，以期得到更佳的寻优效果。

（3）适应度评价函数的定义，是遗传算法的关键环节。为了实现更全面、更细致的评价纵断面方案的合理性，下一步可考虑加入更多影响因素（如:坡长限制、平纵组合条件等约束），并引入惩罚函数对评价结论予以修正。