公路路线自动寻优的遗传算法实现

梁昌征, 张贵阳, 张志清

(1.中国城市规划设计研究院， 北京 100037； 2.中国电建市政建设集团有限公司， 天津 300384；3.北京工业大学交通工程北京市重点实验室， 北京 100124)

0 引言

遗传算法在公路工程中的应用发展到今天，已经有20多年历史. 最先将遗传算法用于公路工程的是美国马里兰大学的Jong博士[1]，他在其博士论文中进行了遗传算法在平面线形优化的尝试，该优化模型的主要特点是以起讫点连线为基础，在选线区域等距离作起讫点的垂线，假设公路平面交点在这些垂线上移动. Jong等[2-3]又提出了一种水平和垂直线形同时优化的路线优化模型. 近年来，国内外已经有很多学者进行自动选线研究，从平面线形优化、纵断面线性优化到平纵线形组合优化，以及三维空间线性优化，且取得了相应的研究成果[4-9]. 但是，公路自动选线表现出的主要局限性是，在选定公路平面交点时，不能在选线区域随机分布. 本文将主要针对这个问题，基于改进的遗传算法，构建新的公路路线优化模型，以实现公路智能选线，研究成果具有一定的实际意义.

1 遗传算法在公路自动选线中的应用优势

1.1 自动选线方法介绍

最初的自动选线方法是指计算机辅助设计，由于只能是进行一些单一的计算、输入输出数据的工作，在详细优化工作方面仍有待改进.

自动选线方法的核心是智能运算方法，智能运算是指一系列学习和模拟自然界中生物结构和行为，和自然现象、过程及其原理的各种方法[10]，自动选线是指在人工确定公路起讫点和控制点的基础上，借助计算机技术实现公路路线的自动选择和优化.

1.2 遗传算法的应用优势

遗传算法是模拟物种进化论发展而来的智能优化算法[10]. 遗传算法不依赖精密的数学模型，依靠社会群体的内在准则实现方案个体的优化，特别适用于复杂问题的优化求解. 主要解决设计变量选择、编码方法确定、遗传算子及终止准则设计.

遗传算法主要优势有3点：操作简单，算法实现比较容易；更符合公路选线的特点，公路自动选线的实现比较容易；属于随机搜索算法，结合交叉和变异操作更能实现全局寻优的目的.

1.3 遗传算法步骤

通常情况下，使用遗传算法进行优化运算的过程可分为5个步骤：

步骤1编码：把公路路线表示方式进行编码，每1个指标就表示为1个基因，每1组基因串就代表1个路线方案.

步骤2初始种群：随机生成n个基因型，即生成了n个路线方案，就构成了初始种群.

步骤3适应度值计算：计算新个体的适应能力，以体现个体在种群中的优劣程度，也是进行选择、交叉及变异操作的依据.

步骤4遗传操作：主要包括选择、交叉和变异3种，选择种群中适应能力较好的个体，进行交叉和变异操作，以产生具有新的基因型的个体，进一步提高个体的适应能力.

步骤5终止：遗传算法的优化寻优是有尽头的，为了防止优化一直进行下去，需要设定一定的终止条件，当优化迭代一定的次数或当问题不能进一步优化时，就可终止程序的运行. 遗传算法的终止准则应该采用多种终止方式相结合的模式，以避免遗传迭代过早结束或者无休止进行下去.

2 公路路线优化目标函数模型

公路的自动选线可认为是：在选线区域内，搜索满足各种公路约束条件的路线方案，基于优化数学模型，搜索确定工程费用最低、安全条件高的公路路线方案. 想要实现公路自动选线，处理好设计变量的选择、约束条件及目标函数是关键，公路路线方案的优化需要综合考虑多种影响因素，构造一个完善、有效的目标函数模型，避免遗漏优秀公路路线方案. 通过对路线方案安全性评价、经济性评价及规范性约束3个方面建立路线优化目标函数模型，以比较公路路线方案的优劣，确定各路线个体的适应度值.

2.1 安全性评价

公路路线是公路建设的骨架，在选线过程中，不仅要满足基本的规范要求，也要确保公路路线设计的安全性能，以保障人们生命安全. 设计速度是公路设计中的重要指标，对于公路实现其安全迅捷、舒适的使用目的具有重要意义. 以公路线形速度一致性作为公路自动选线安全性评价指标. 车辆的运行速度是公路线形安全评价的一项重要指标，是评价路线的速度协调性、平纵横等技术指标的重要标准，国外诸多学者都进行了考虑运行速度的公路安全性评价研究[11-13].

参考《公路项目安全性评价指南》的评价方法，评价指标采用相邻路段运行速度的差值Δv85，评价标准见表1.

表1 运行速度的差值标准

2.2 经济性评价

目标函数的经济性是指公路建设总费用[14]. 详细数学表达见式(1)：

C=C1+C2+C3+C4+C5

(1)

式中，C为建设工程费用；C1为征地费用；C2为路基土石方工程费用；C3为桥梁、涵洞及隧道建设工程费用；C4为房屋拆迁费用；C5为路面材料费用.

2.3 规范约束

路线基本规范约束模型是公路选线过程中首先需要考虑的模型，是公路选线的基础，即要求公路路线方案要满足基本规范要求. 本文以《公路路线设计规范》(JTG D20—2017)作为基本要求，主要考虑公路平面约束、纵断面约束及平纵组合约束.

3 遗传算法在公路自动选线中的应用

3.1 设计变量选择

设计变量是公路路线优化过程中需要控制的变量. 在公路平纵线形设计中，需要确定平面交点位置、圆曲线半径、竖曲线半径、变坡点位置及变坡点高程5个指标. 为了便于研究，假设变坡点位置与平面交点位置重合，通过改变平面交点位置、圆曲线半径、竖曲线半径和变坡点高程来实现公路路线的自动搜索与优化.

3.2 遗传编码

根据公路自动选线的问题和特点，选择实数编码方法. 对线路三维空间基因编码进行改进，平面交点采取随机分布，先生成平、纵断面基因片段，再组合形成整体公路路线表达基因，以完成公路路线基因编码的全过程.

图1 遗传编码程序示意图

3.3 生成初始种群

路线方案初始种群是指一系列满足规范要求和安全要求的路线方案组合，是路线优化的初始状态. 首先根据基因编码方法生成一串基因序列构成一个路线方案个体；再生成一定数量的方案个体构成初始种群. 生成流程见图2：

图2 初始种群生成流程图

3.4 适应度函数

遗传算法的适应度值是表示某一个体对环境的适应能力，也表示该个体优秀性能被选择的能力. 由于公路路线方案之间的目标函数值差异有限，适应度值计算采用公式f(x)=cmax-g(x)计算，公路路线方案的适应度值越大，则该方案被选择的概率就越大. 适应度值计算程序示意如图3：

图3 适应度值计算

3.5 遗传操作

遗传操作主要包括选择、交叉和变异3种操作，是实现寻优的主要手段. 选择的目的是把父代的优秀基因传递给子代个体，可通过轮盘赌模型实现选择操作. 基于遗传算法的交叉运算，交换2个父代个体的部分基因片段，在整个选线区域内，不断产生新的路线方案. 变异是一种基本的遗传操作，通过随机改变父代个体的某一基因片段，以产生新的路线方案，可提高遗传算法对整个空间的搜索能力.

图4 遗传操作流程图

在遗传操作的过程中，需要特别注意的是遗传操作点位的选取，虽然理论上讲，遗传算法的操作点位是可在任意位置的，结合公路选线的实际情况，在公路自动选线过程中，路线的起讫点是已定的，要求在优化的时候不能改变起讫点位置，因此在交叉操作是需要把起讫点的位置基因片段及高程基因片段除外. 本文采用的方法是把所有的基因片段进行排序，在进行遗传操作点位选择的时候，首先判断选择的是否为起讫点相关基因片段，只有选择非起讫点相关基因片段才可进行交叉、变异操作.

4 算例分析

通过公路选线方法与遗传算法相结合，实现公路自动选线，为了提高研究成果的可信度，更好地为我国公路自动选线工程服务，本文进行实际工程案例分析，实现基于遗传算法的公路自动选线. 选线区域等高线图如图5所示，路线起讫点坐标分别为：(477 772.985，320 625.085 6)、(478 204.230 4，321 791.855 7).

图5 选线区域等高线图

4.1 参数设定

基础参数是与公路等级要求、程序运行状态直接相关的公路选线技术指标，需要在公路自动选线程序运行之前就确定. 根据公路等级不同，参考公路设计相关标准，路线平纵横断面设计参数见表2.

表2 公路基本参数表

4.2 选线结果分析

通过基于遗传算法的公路自动选线程序的运行，实现了公路路线方案的搜索与优化. 主要体现在路线长度变化和工程总费用变化上. 公路自动选线过程中的每一代最优路线方案相关技术指标输出见表3.

表3 公路逐代优化技术指标表

通过运行程序，输出路线优化图见图6，路线长度变化图见图7，工程总费用图见图8.

图8 建设总费用迭代图

从图6可看出：经过100代的迭代优化，公路路线方案有了明显的优化. 从图7可看出，公路路线长度呈逐代下降趋势，说明遗传算法在公路自动选线中的应用是基本成功的. 公路路线优化过程可分为3个阶段：快速优化期(1～20代)，缓慢优化期(20～60代)，稳定优化期(60代以后). 说明迭代

图6 路线优化示意图

图7 路线长度迭代图

初期公路路线迅速优化，迭代中期优化速度减缓，迭代末期优化速度趋于平缓，最后保持不变，实现路线最优化选择. 从图8可看出，公路路线的工程总费用变化趋势与路线长度变化基本相似，工程总费用的变化更能体现遗传算法应用于公路自动选线中的优势.

5 结束语

在分析国内外遗传算法在公路自动选线应用理论方法的基础上，重点改进了交点在整个选线区域的自动寻优，并且增加了安全性指标的约束条件，提出了一种基于遗传算法的公路自动选线新方法. 以MATLAB为实验平台，模拟公路路线自动寻优，可优化选出公路路线方案，说明该方法可行. 论文提出的自动选线方法较以往研究成果具有3个方面的优势：

1)基于遗传算法的公路自动选线方法，克服了以往公路自动选线过程中平面交点只能在某一剖切面上变化的局限，实现了对整个选线区域内的公路路线方案的自动寻优.

2)在满足基本公路路线设计规范的基础上，将公路线形一致性的安全性评价指标，引入公路自动选线过程中，提高了公路自动选线的安全性.

3)以公路工程造价作为评价标准，把公路路线优化问题转化为以公路工程造价为导向的优化问题. 建立了以经济评价指标为基础的公路自动选线优化模型，保证了自动选择方案的经济性.