基于遗传算法的线路纵断面初始方案的产生.pdf

基于遗传算法的线路纵断面初始方案的产生 高 华 (中铁第四勘察设计院集团有限公司，湖北武汉 430063) GenerationofPreliminarySchemeonOriginalVerticalSection ofRailwayLinesBasedonDTM andGeneticAlgorithm GaoHua 摘 要 在道路选线设计 中，纵断面初始方案的 自动生成是道路 CAD体系的重要组成部分和关键 问题 。多 目标遗传算法具有处理大的空间问题的能力，在一次进化过程 中可以得到多个可行解，对问题 域的先验知识没有要求，对函数定义域的凸性不敏感，这正是经典算法所不具备的。基于数字地面模 型，在多目标遗传算法的基础上，用VC编制程序，根据已知的给定标准值、纵断面数据和构造物控制高 程等，自动生成纵断面的初始方案，满足最小坡长，最大纵坡和高程约束的要求。 关键词 计算机辅助设计 遗传算法 道路选线 在20世纪60年代末、70年代初，继美国Michigan 大学的Holand所做的开创性工作后，遗传算法产生 了。基本的遗传算法 (或称标准的遗传算法)由初始 化、选择、交叉和变异四个部分组成。遗传算法是从一 组随机产生的初始解 ，称为 “种群 (Population)”，开始 搜索过程。种群中的每个个体是问题 的一个解 ，称为 “染色体 (Chromosome)”。染色体是一串符号，比如一 个二进制字符串。这些染色体在后续迭代中不断进 化，称为遗传。在每一代中用 “适值 (Fitness)”来测量 染色体的好坏。生成的下一代染色体，称为后代 (Off- 图 1 遗传算法的基本流程 spring)。后代是由前一代染色体通过交叉 (Crossover) 出最优方案。本文中，在用遗传算法生成纵断面的初 或者变异 (Mutation)运算形成的。新一代形成后，根 始方案时，采用了对待非法解的拒绝策略，禁止非法染 据适值的大小进行选择。在这个过程中，适值高的染 色体进入下一代种群。要求初始方案种群符合规范要 色体被选中的概率比较高。从而保留部分后代，淘汰 求、满足一定的约束条件。 部分后代，保持种群大小是常数。这样，经过若干代之 首先生成了lO个初始方案，各方案的具体形成过 后，算法收敛于最好的染色体，它很可能就是问题的最 程如下：假设某地面线为图2中AB之间的实线部分， 优解或次优解。遗传算法的基本流程如图1所示。 A、B为线路起终点。显然以AB的直接连线形成的初 1 满足坡度限制的初始方案的生成 始方案可以满足坡度要求，但此方案中变坡点数 目太 少，造成染色体中的基因数 目较少 (本文中染色体中 在纵断面优化设计过程 中，首先需要产生纵断面 的基因即方案中的变坡点，基因数即变坡点个数)。 初始方案种群，然后在此基础上采用遗传算法寻优找 因此本文采用内插法，在AB连线的基础上增加变坡 收稿 日期：2008—09—01 点，同一个方案中的所有坡段，除了最后一个坡段外各 作者简介：高 华 (1981一)，女，2007年毕业中南大学道路与铁道工程 专业 ，工学硕士，助理工程师。