当前位置: 硕士论文网 >> 硕士毕业论文 >> 工程硕士毕业论文 >> 基于蚁群算法的三维管路路径规划
基于蚁群算法的三维管路路径规划
来源:
摘 要
三维管路路径规划问题是在具有约束的环境中，按照某个评价标准（如最短路径长度、最少弯道等），规划一条从起点位置到终点位置满足约束条件的最优（或较优）的路径。在大楼管路敷设、石油运输管路、电站辅机管路设计、航空发动机外部管路设计等领域有着广泛的应用，其主要内容涉及环境表达、规划方法、路径搜索等多个学科。关于三维管路路径规划问题的研究，人们从多方面进行了探索和研究，虽取得了一些成果，但仍存在许多问题有待深入研究。
本文研究了蚁群算法在三维管路路径规划问题的中的应用及改进。首先，分析了三维管路路径规划研究现状及当前研究存在的问题，从众多方法中选择蚁群算法对三维管路路径规划问题进行研究应用；其次，详细论述了基本蚁群系统在三维管路路径规划中的应用及算法实现，并对基本蚁群系统中存在的问题进行了分析，提出了改进型蚁群系统，并将其与基本蚁群系统以及基本蚁群算法进行比较，并对比较结果进行分析；再次，结合协同进化算法，将多种群协同进化算法应用到三维多管路路径规划问题中，并对其进行仿真实验；最后，综合改进型蚁群系统、多种群协同进化算法及UG 强大三维造型功能设计简单三维管路系统软件，便于管路设计人员使用。具体来说，本文主要成果包括以下几个方面：
在将蚁群系统应用于三维管路路径规划过程中，对算法数据结构具体实施细节上进行了改进，将蚂蚁的信息素释放在节点上而不是在节点边上，减少了庞大的距离矩阵，节省存储空间，降低运算量。
提出基于半迭代的全局信息素更新机制，该迭代方式综合了完全迭代更新方式和最优解更新方式的特点，对当代种群进行排序，排在前面Rank 位的蚂蚁释放信息素，而排在Rank 位后的蚂蚁不释放信息素，使得算法既有最优解更新方式的少计算量的特点，又有完全迭代更新方式多样性的特点，在三维环境和平面路径规划中进行了仿真实验，验证了该迭代方式在减少计算量，提高算法多样性上的性能。
利用UG 二次开发功能，设计三维管路系统软件，使得开发具有智能化和可视化，既利用了算法快速求得较优解的优点，又能使设计人员根据经验对设计方案进行修正寻优。将三维管路系统应用于凝汽器接颈部分抽汽管路的设计当中，取得了不错的指导效果，具有一定的工程应用价值。
关键字：三维管路，路径规划，蚁群系统，多种群协同算法，UG 二次开发
绪论
三维管路路径规划是许多工程设备设施设计的关键问题之一，从住房供水管路的敷设到凝汽器抽汽管路的设计，再到航空发动机外部管路的构建以及油汽输送管道的布局等都属于三维管路路径规划问题，三维管路路径规划在这些设备的整个设计中起着至关重要的作用。因此，如何应用当前技术理论，设计出高质量的满足约束条件的三维管路路径成为许多发动机厂家和电站辅机厂家关注的问题之一。
1.1 三维管路路径规划概述
三维管路路径规划从定义上讲，是从二维管路路径规划问题到三维空间的一个延伸，它的主要任务是在三维空间中获得给定的起始点（源点）到终点（目标点）的一条满足约束条件的管路路径。
三维管路路径规划的主要特点是(1)敷管空间是三维空间，增加了空间复杂性。(2)管路的数量多，有的设备上的管路多达 100～200 根，如航空发动机外部管路。(3)管路的约束很多。在质量最轻(即中心线长度最短)的基础上，还要考虑管路的可加工性(如管路的最小弯曲半径)、工作特性 (如基于管内流阻考虑的最小直线段长度)、管路的振动问题(如要求管路能够方便地添加卡箍以增加管路的刚性 )，以及可装配性和可维修性等问题。
基于上述特点，我国三维管路路径规划基本处于人机交互阶段，技术人员和工人依靠长期积累的经验，来满足管路的种种要求。
随着社会的发展，工程设备的要求越来越高，重量要求越来越轻，质量要求越来越高，精度要求越来越高，复杂性也越来越高，同样，作为设备关键问题的三维管路路径规划的难度也越来越大，依靠人的经验和人机交互进行的三维管路路径规划已经不能满足工程需要，大大降低了三维管路路径规划的效率。如果能够做到自动生成满足一定约束条件的三维管路，将大大提高三维管路路径规划的效率。
1.2 三维管路路径规划的离散模型
1.2.1 三维管路模型
三维管路设计就是要从起点（源点）到终点（目标点）找到一条满足条件和约束的最优的路径。如图1-1 所示，管路入口Inlet 在平面H1 上，管路出口在平面H2 上，在空间中要找到一条合适的连接入口Inlet 和出口Outlet 的最优路径。此路径要满足的约束条件：
入口和出口方向分别要垂直平面H1 和H2；所有管路都是垂直正交的，也就是说每个管路的转弯处都是直角；管路转弯处尽可能少；路径总长度最短；避开障碍物；管路直径为pr，障碍物直径为or，对于方形障碍物长宽高为。
1.2.2 三维空间模型
由于数字电子计算机本身是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，对三维连续空间进行适当的离散处理，计算机才能对问题处理求解。为方便问题研究，假设研究范围限定在一个矩形内，所有管路和障碍物都被限定在此矩形内，将矩形的长（Length）、宽（Width）、高（Height）等分，得到（长（Length）+１） （宽（Width）+１） （高（Height）+１）个节点，如图4-2 所示。
1.3 三维管路路径规划的难点
1.3.1 搜索空间的规模
三 维 管 路 路 径 规 划 问 题 是 要 从 图 1-2 所示( 长(Length)+1) ( 宽高(Height)+1)个节点中找到一条最优路径，如果用穷举法那么它的解空间将达到((Length+1) (Width+1) (Height+1))! ， 假设那么解空间将达到100!，而，假设计算机每秒计算10000 万亿次，也需要年才能完成这样规模空间的探索，实际上目前最快的超级计算机IBM Roadrunner 也不过突破每秒一千万亿运算的速度，而且三维空间的规模也远大于此，确定性算法
