资源描述：
《基于遗传算法的公园道路设计_信息与通信_工程科技_专业资料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于遗传算法的城市道路设计［摘要］对城市道路的规划特定的两个问题给出了设计方案。该方案基于遗传算法的思想并对其改进优化，以市内道路总长为目标函数，合理地选择迭代次数和变异概率，在不同的限定条件下，分别得出了两个问题的解决方案并大幅降低了问题的复杂度和计算量，有效地处理传统算法难以解决的复杂问题。最后给出了算法的改进方案，并对该算法应用做了进一步的推广。［关键词］道路设计；路程最短；遗传算法引言城市中的道路是城市中的重要组成部分，城市中的道路的规划，直接影响到城市屮各功能空间划分的合理性，人流交通是否通畅，绿化组
2、织是否合理，对城市的整体规划的合理性起着举足轻重的作用。传统的城市道路设计主要凭借经验，近年来随着计算机的普及以及软硬件性能的提高，人们开始借助计算机模拟并规划道路，以寻求较好的解决方案。大部分设计方案按照规定的要求，借助计算机，穷举出所有可能的路线，从中选出最佳的。城市布局可以看成图，每个入口、交叉点和顶点看作图的顶点，它们Z间的连线看作图的边。任意两点之间的连线都可能是最终设计结果的一条边，这些可能边构成的边集的数量是O(n2),这里n指顶点数量。当n的值大到一定程度时，利用穷举法寻求精确最优解的代价是巨大
3、的。而遗传计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法，具有口组织、口适应、□学习的特性，能够不受问题性质的限制，适应不同的环境下的不同问题，而冃在大多数情况下都能得到比较满意的有效解。有效地处理传统优化算法难以解决的复杂问题。1模型描述与假定1.1模型描述城市平面模型如图1所示，长200km,宽100km,有若干个入口，1〜8各入口的坐标分别为：Pi(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,100),P7(10,100),P8(0,
4、25)o设计道路使任意两个入口相连,使总道路长度之和最小，并且任意两个入口间的最短道路长不大于两点连线的1.4倍。求解以下问题：(1)假定城市内确定要使用4个道路交叉点为：A(50,75),B(40,40),C(120,40),D(I15,70)。设计道路使城市内道路的总路程最短。(2)现在城市内可以任意修建道路，只考虑在满足条件下使总路程最少。1・2模型假设为方便清晰地分析问题，根据题目条件和要求，对模型做如下假设：(1)忽略各定点Z间的可能的障碍，即任意两顶点Z间可以直线和连。(2)城市四周的边即矩形四条边
5、上存在建好的道路，但此道路不计入总长。(3)城市内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其他点。908070宽60/50k皿4°m3020100♦♦P6(35,100)P7(10,100)P/0,25)♦P5(120,100)P4(200,50)P/20,0)P2(50,0)P3(160,0)I~IIIii~n020406080100120140160180200长/km图1城市及入口示意图2准备工作2.1符号定义与说明用到的符号说明如表1所示。表1符号说明符号符号所代表的意义顶点i的坐标，
6、横坐标a：,纵坐标6Vi顶点iViQib)lij顶点i到顶点j的长度Pnice当得到的矩阵较好时，选择它作为变异概率Pbad当得到的矩阵较好时，选择它作为变异概率迭代次数Pmutaion变异概率T2.2邻接矩阵邻接矩阵(AdjacencyMatrix)的表示法，就是用一维数组存储图屮顶点的信息,用矩阵表示图中各顶点Z间的邻接关系。假设图G=(V,E)有n个确定的顶点，V是顶点集，E是边集。令绚等于G屮顶点M和Vj之间的边数，贝IJ
7、V
8、阶方阵A(G)=(aij)称为G的邻接矩阵。2.3Floyd算法Floyd算
9、法的基本思想是：假设求从节点M到Vj的最短路径。如果从Vj到Vj有弧，则从M到Vj存在一条长度为A”的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径Wp%,Vj>是否存在，如果存在，则比较vVpVj>和的路径长度，取长度较短者为从Vi到Vj的屮间节点的序号W1的最短路径。假如在路径上再增加一个节点V2,即如果Wi，…，V2>和VV2，…，Vj>分别是当前找到的屮间节点的序号W1的最短路径，那么就有可能是Vi〜Vj的中间节点的序号W2的最短路径。将它和已
10、经得到的Vi〜Vj中间节点序号W1的最短路径相比较，从中选出中间节点的序号W2的最短路径Z后，再增加一个V3,继续进行试探。依次类推，经过n次比较后，求得Vj〜Vj的最短路径。3模型建立与求解3.1模型的建立设顶点M的坐标为Vi（ai，bi）,当顶点VpVj之间有路相连时，顶点*〜％的距离hj二
11、〒.-I二J（兔—ay+（bj—by,当顶点VpVj之间没冇路相连时，ljj=Oo根据题意
