|
|
|
| Ship pipe route planning method based on maze algorithm and genetic algorithm |
| SUI Hai-teng, NIU Wen-tie |
| Key Laboratory of Mechanism Theory and Equipment Design of Ministry of Education, Tianjin University, Tianjin 300072, China |
|
|
|
Abstract The diversity of piping systems and complexity of constrains in layout space lead to the low efficiency of ship pipe design. A new pipe route planning method was proposed to improve the design efficiency and reduce human errors. Based on the simplified layout space, the mathematical model was firstly built by the discretization of the layout space and the specific energy value which was given to the spatial network. Based on the constructed mathematical model, the improved maze algorithm and genetic algorithm were then combined together to conduct pipe route planning. The concept of auxiliary point was introduced to improve the maze searching performance, which guaranteed the diversity of initial population and enhanced the global search ability of genetic algorithm. A fixed-length coding method was also proposed to simplify the difficulty in handling the pipe chromosomes and improve the performance of algorithm. The direction oriented strategy was applied in maze retracing process to design the genetic operators with fixed-length chromosomes, which not only guaranteed the quality of children chromosomes but also improved the convergence speed of the algorithm. The simulation results verify the feasibility and effectiveness of this approach, and prove the guiding significance of the approach to actual ship pipe route planning.
|
|
Received: 08 May 2015
Published: 28 April 2016
|
|
|
基于迷宫算法和遗传算法的船舶管路路径规划
船舶管路的多样性和布局环境中约束的复杂性导致管路设计效率低下.为辅助设计人员提高管路设计效率并减少人为错误,提出了一种新的管路设计方法.首先,基于轴平行包围盒简化管路布局空间,利用栅格法对其进行离散化,并赋予空间网格特定的能量值,构建管路布局优化问题的数学模型.其次,基于遗传算法的框架,引入改进迷宫算法,提出管路路径规划方法,其中:迷宫搜索中引入辅助点的概念,增加了遗传算法中初始种群的多样性,有利于提高遗传算法的全局搜索能力;提出了定长度的编码方法,简化了管路染色体处理难度,提高了算法性能;基于引入方向优先搜索策略的迷宫算法,设计定长度编码遗传算子,保证了子代个体的质量,提高算法的收敛速度.最后,基于仿真试验,验证算法的性能.试验结果表明了该方法的可行性和高效率,以及其对实际管路布局工作具有指导意义.
关键词：
管路布局,
迷宫算法,
遗传算法,
定长度编码
|
|
| [1] PARK J H,STORCH R L.Pipe-routing algorithm development:case study of a ship engine room design[J].Expert Systems with Applications,2002,23(3):299-309.[2] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269-271.[3] LEE C Y.An algorithm for path connections and its applications[J].Ire Transactions on Electronic Computers,1961,10(3):346-365.[4] 樊江,马枚,杨晓光.航空发动机外部管路自动敷设研究[J].机械设计,2003,20(7):21-23. FAN Jiang,MA Mei,YANG Xiao-guang.Research on automatic laying out for external pipeline of aero-engine[J].Journal of Machine Design,2003,20(7):21-23.[5] HIGHTOWER D W.A solution to line routing problems on the continuous plane[C]//Proceedings of 6th Design Automation Workshop.IEEE,1969:1-24.[6] ITO T.A genetic algorithm approach to piping route path planning[J].Journal of Intelligent Manufacturing,1999,10(1):103-114.[7] ITO T.Developments in applied artificial intelligence[C].Berlin:Springer,2002:547-556.[8] 范小宁,林焰,纪卓尚.船舶管路三维布局优化的变长度编码遗传算法[J].中国造船,2007,48(1):82-90. FAN Xiao-ning,LIN Yan,JI Zhuo-shang.A variable length coding genetic algorithm to ship pipe path routing optimization in 3D space[J].Shipbuilding of China,2007,48(1):82-90.[9] SANDURKAR Sunand,WEI Chen.GAPRUS—genetic algorithms based pipe routing using tessellated objects[J].Computers in Industry,1999,38(3):209-223.[10] REN Tao,ZHU Zhi-liang,DIMIROVSKI G M,et al.A new pipe routing method for aero-engines based on genetic algorithm[J].Proceedings of the Institution of Mechanical Engineers,Part G:Journal of Aerospace Engineering,2014,228(3):424-434.[11] JIANG Wen-ying,LIN Yan,CHEN Ming,et al.An ant colony optimization-genetic algorithm approach for ship pipe route design[J].International Shipbuilding Progress,2014,61(3):163-183.[12] 范小宁,林焰,纪卓尚.多蚁群协进化的船舶多管路并行布局优化[J].上海交通大学学报,2009,43(2):193-197. FAN Xiao-ning,LIN Yan,JI Zhuo-shang.Multi ant colony cooperative co-evolution for optimization of ship muti pipe parallel routing[J].Journal of Shanghai Jiaotong University,2009,43(2):193-197.[13] LIU Qiang,WANG Chen-gen.A discrete particle swarm optimization algorithm for rectilinear branch pipe routing[J].Assembly Automation,2011,31(4):363-368.[14] LIU Qiang,WANG Chen-gen.Pipe-assembly approach for aero-engines by modified particle swarm optimization[J].Assembly Automation,2010,30(4):365-377.[15] LIU Qiang,WANG Chen-gen.Multi-terminal pipe routing by Steiner minimal tree and particle swarm optimization[J].Enterprise Information Systems,2012,6 (3):315-327.[16] KIM S H,RUY W,JANG B S.The development of a practical pipe auto-routing system in a shipbuilding CAD environment using network optimization[J].International Journal of Naval Architecture and Ocean Engineering,2013,5(3):468-477. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
