论文部分内容阅读
摘要: 针对传统道路纵断面优化大多采用局部优化的方法,把遗传算法用于道路纵断面优化设计当中,更好地解决传统算法难于解决的一些问题。
关键词: 道路工程;纵断面;遗传算法;优化设计
中图分类号:U412.33 文献标识码:A 文章编号:1671-7597(2011)0920112-01
0 引言
随着中国现代化建设的全面推进,现代道路的最佳设计已不仅仅是要求工程投资最少或运营费用最低,而且要求道路能有效地和社会环境相协调,投资能获得最大的效益。道路选线在整个道路设计的工作中占有及其重要的地位。目前应用较多的算法[1]有简约梯度法、二次规划法、复合形法等,这些算法都有各自的缺点。针对上述方法存在的问题和不足,基于遗传算法的纵断面优化方法可以在一个可行域中搜索到一个最优或者较优解。
1 纵断面优化数学模型
1.1 设计变量。确定变坡点的位置和变坡点的设计高程是纵断面设计所要解决的两个关键问题。纵断面中边坡点的里程和高程即为纵断面设计优化中的设计变量。
1.2 目标函数。目标函数包括道路自身建设费用、道路使用者费用和惩罚费用[2]等。即
其中: 为道路自身建设费用;为道路使用者费用;为惩罚费用。
为占地拆迁费;为土方工程费用;为单位长度的基本建设费用和道路长度的乘积;为桥梁隧道建设费用;为道路使用阶段养护费用。
为燃油消耗费;为时间消耗费;为交通事故费。
是违反最大纵坡度的惩罚费;
是违反最小曲线长度的惩罚费用;是违反最小平曲线半径的惩罚费用; 是破坏耕地的惩罚费用; 是破坏湿地的惩罚费用。
1.3 约束条件。1)变坡点取值范围。2)最小坡长限制。3)最大纵坡坡度限制。
1.4 数学模型。纵断面优化设计模型[3]可表示为:
N为边坡点的个数;是变坡点里程的最小和最大取值;
变坡点高程的最小和最大取值;是最小坡长限制;最大纵坡坡度限制。
1.5 初始纵断面方案的生成。为了节约搜索时间,尽快达到预期方案的目标,需要预先给定满足纵断面优化所有约束条件的一个初始解。本文采用在地面线连续处理的基础上,借助崎岖度计算得到初始解。
2 遗传算法
遗传算法[4]是基于适者生存的一种并行、随机和自适应的优化算法适合大空间的搜索问题,是一种模拟自然进化过程搜索最优解的方法。仿照基因编码的工作很复杂,我们往往进行简化,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。
3 基于遗传算法的纵断面优化
3.1 编码
编码就是将所求问题的解转化为遗传算法中的染色体,本文用实数编码以便于进行大空间的搜索。公路纵断面优化参数本身就是用实数表示的,可以在整个空间寻求到最优解。
3.2 初始种群的产生
在地面线连续处理的基础上,借助崎岖度计算得到初始解,在此基础上重复这个过程,直到产生的个体数达到所设定的种群规模。
3.3 适应度函数的选择
纵断面优化的问题可以转化为求最小值的问题。适应度越小即说明方案越好,而遗传算法的选择机制是适应度越大被选择的概率越大,因此需要对函数进行适当变形。笔者采用的适应度函数是
其中为某一代中适应度的最大值;为原目标函数。用计算出来的新适应度替代原来的适应度然后进行选择。轮转法选择的过程如下所示:
Step 3:在[0,1]区间产生一个均匀分布的随机数a;
Step 4:若a≤q1,选择第一个染色体,否则与q2,q3…比较,直到选到第k个染色体使得;
Step 5:重复步骤3和4,直到选出新种群。
3.4 交叉
从已经进行了选择操作的群体中随机选取两条染色体作为父代染色体,再随机交换父代串中的某些对应数据从而产生新的染色体。父代染色体通过交叉概率选定,被选到的染色体随机配对,按一点交叉的方法对配对染色体进行交叉操作。在两个父代染色体中随机设定一个交叉点,该点部分两个个体结构互换,生成两个新个体。
3.5 变异
选择和交叉基本上完成了遗传算法的大部分搜索功能,变异则更增加了遗传算法找到最优解的能力,实数编码[5]的过程可采用如下过程实现:对于给定的父代解Vk,若它的元素Xi被选来变异,则生成的后代为,按下式计算
设 是一个父解,分量vk被选来变异,定义区间为[ak,bk],则变异后的解为。
其中,若rand()=0,则;若rand()=1,则
。
上式中的rand()为产生均匀分布随机数函数。
函数△(t,y)的具体表达式可以取为△(t,y)=y[1-r(1-1/T)λ],r是[0,1]上的随机数,T是最大代数,λ是非一致性成都的参数。
4 结语
本文研究表明把遗传算法应用在道路纵断面优化设计中可以产生良好的效果,从而可以缩短道路的设计周期,减少工程量和工程造价,减低道路的建设成本,提高行车舒适度,降低交通事故率方面具有很好的应用价值。遗传算法的难点在于算法的设计和处理上,如何更好的构造适应度函数并有效地处理约束条件从而得到更好的优化结果,还需要进一步地研究。
参考文献:
[1]杨名,基于蚁群算法的道路纵断面优化设计[D].长沙:中南大学.2008.
[2]许金良、王海君、杨少伟,基于遗传算法的公路纵断面优化[J].交通运输工程学报,2003,3(2):48-52.
关键词: 道路工程;纵断面;遗传算法;优化设计
中图分类号:U412.33 文献标识码:A 文章编号:1671-7597(2011)0920112-01
0 引言
随着中国现代化建设的全面推进,现代道路的最佳设计已不仅仅是要求工程投资最少或运营费用最低,而且要求道路能有效地和社会环境相协调,投资能获得最大的效益。道路选线在整个道路设计的工作中占有及其重要的地位。目前应用较多的算法[1]有简约梯度法、二次规划法、复合形法等,这些算法都有各自的缺点。针对上述方法存在的问题和不足,基于遗传算法的纵断面优化方法可以在一个可行域中搜索到一个最优或者较优解。
1 纵断面优化数学模型
1.1 设计变量。确定变坡点的位置和变坡点的设计高程是纵断面设计所要解决的两个关键问题。纵断面中边坡点的里程和高程即为纵断面设计优化中的设计变量。
1.2 目标函数。目标函数包括道路自身建设费用、道路使用者费用和惩罚费用[2]等。即
其中: 为道路自身建设费用;为道路使用者费用;为惩罚费用。
为占地拆迁费;为土方工程费用;为单位长度的基本建设费用和道路长度的乘积;为桥梁隧道建设费用;为道路使用阶段养护费用。
为燃油消耗费;为时间消耗费;为交通事故费。
是违反最大纵坡度的惩罚费;
是违反最小曲线长度的惩罚费用;是违反最小平曲线半径的惩罚费用; 是破坏耕地的惩罚费用; 是破坏湿地的惩罚费用。
1.3 约束条件。1)变坡点取值范围。2)最小坡长限制。3)最大纵坡坡度限制。
1.4 数学模型。纵断面优化设计模型[3]可表示为:
N为边坡点的个数;是变坡点里程的最小和最大取值;
变坡点高程的最小和最大取值;是最小坡长限制;最大纵坡坡度限制。
1.5 初始纵断面方案的生成。为了节约搜索时间,尽快达到预期方案的目标,需要预先给定满足纵断面优化所有约束条件的一个初始解。本文采用在地面线连续处理的基础上,借助崎岖度计算得到初始解。
2 遗传算法
遗传算法[4]是基于适者生存的一种并行、随机和自适应的优化算法适合大空间的搜索问题,是一种模拟自然进化过程搜索最优解的方法。仿照基因编码的工作很复杂,我们往往进行简化,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。
3 基于遗传算法的纵断面优化
3.1 编码
编码就是将所求问题的解转化为遗传算法中的染色体,本文用实数编码以便于进行大空间的搜索。公路纵断面优化参数本身就是用实数表示的,可以在整个空间寻求到最优解。
3.2 初始种群的产生
在地面线连续处理的基础上,借助崎岖度计算得到初始解,在此基础上重复这个过程,直到产生的个体数达到所设定的种群规模。
3.3 适应度函数的选择
纵断面优化的问题可以转化为求最小值的问题。适应度越小即说明方案越好,而遗传算法的选择机制是适应度越大被选择的概率越大,因此需要对函数进行适当变形。笔者采用的适应度函数是
其中为某一代中适应度的最大值;为原目标函数。用计算出来的新适应度替代原来的适应度然后进行选择。轮转法选择的过程如下所示:
Step 3:在[0,1]区间产生一个均匀分布的随机数a;
Step 4:若a≤q1,选择第一个染色体,否则与q2,q3…比较,直到选到第k个染色体使得;
Step 5:重复步骤3和4,直到选出新种群。
3.4 交叉
从已经进行了选择操作的群体中随机选取两条染色体作为父代染色体,再随机交换父代串中的某些对应数据从而产生新的染色体。父代染色体通过交叉概率选定,被选到的染色体随机配对,按一点交叉的方法对配对染色体进行交叉操作。在两个父代染色体中随机设定一个交叉点,该点部分两个个体结构互换,生成两个新个体。
3.5 变异
选择和交叉基本上完成了遗传算法的大部分搜索功能,变异则更增加了遗传算法找到最优解的能力,实数编码[5]的过程可采用如下过程实现:对于给定的父代解Vk,若它的元素Xi被选来变异,则生成的后代为,按下式计算
设 是一个父解,分量vk被选来变异,定义区间为[ak,bk],则变异后的解为。
其中,若rand()=0,则;若rand()=1,则
。
上式中的rand()为产生均匀分布随机数函数。
函数△(t,y)的具体表达式可以取为△(t,y)=y[1-r(1-1/T)λ],r是[0,1]上的随机数,T是最大代数,λ是非一致性成都的参数。
4 结语
本文研究表明把遗传算法应用在道路纵断面优化设计中可以产生良好的效果,从而可以缩短道路的设计周期,减少工程量和工程造价,减低道路的建设成本,提高行车舒适度,降低交通事故率方面具有很好的应用价值。遗传算法的难点在于算法的设计和处理上,如何更好的构造适应度函数并有效地处理约束条件从而得到更好的优化结果,还需要进一步地研究。
参考文献:
[1]杨名,基于蚁群算法的道路纵断面优化设计[D].长沙:中南大学.2008.
[2]许金良、王海君、杨少伟,基于遗传算法的公路纵断面优化[J].交通运输工程学报,2003,3(2):48-52.