Coevolutionary Optimization Algorithm For Ship Branch Pipe Routing

The main purpose of ship pipe routing design is to find a rapid and effective method for solving pipe routing optimization automatically. The research on three dimensional pipe routing optimization has important significance for reducing the designer's burden, improving the design efficiency and quality and reducing the shipbuilding cost. At present, the ship pipe routing design mainly relies on human experts and their related experience in practice because the number of ship pipe is very large, the constraint is miscellaneous and the layout space is large. There is a striking contract between the research on ship pipe routing design and the level of ship CAD. Such situation becomes a bottleneck in the process of ship design and it restricts to improve the ship design velocity and quality. The solving of the automatic and optimization of ship pipe routing design not only has theoretical pioneering and difficulty, but also has complexity in the engineering practice for the sake of the difficulty of pipe routing and the complexity of ship design.The three-dimensional pipe routing optimization problem can be divided into single pipe routing, multiple pipe routing and branch pipe routing. The branched pipe is ubiquity, and it is a one-to-many problem, namely, it has one starting point and many end points, so its routing is very complex. The branch pipe system includes main pipe, branch pipe and nested branch pipe. The optimum path search of the branch pipe belongs to NP hard problem. Some scholars at home and abroad studied and discussed this problem in recent years. Although they used different optimization methods, they must choose the routing sequence of branch pipe firstly and then determine the branch point, finally the branch point as starting point was joined by other end points to find route. Because of the uncertainty of the branch pipe routing sequence and the branch point's position, all above methods have many problems, such as large space, many obstacles, many branches and when it includes nested branches it needs very large storage space, which leads to low time efficiency and even combination explosion. Coevolutionary algorithm is to introduce the concept of ecosystem on the basis of traditional coevolutionary algorithm, the application domain problem is mapped into the evolving ecosystem constituted by various species, so the problem can be resolved by the ecosystem evolvement. In this paper a new method is put forward to solve the problem of branch pipe routing optimization based on the idea of coevolutionary algorithm. This method breaks the traditional methods needed to determine the pipe routing sequence and the branch point's position. In the method, the branch pipe system is divided into many single pipes, and each pipe is an individual and is optimized with a kind of population, the fitness of individual is determined by the distance from the optimal individuals in other population. In addition, this paper discusses genetic algorithm and ant colony algorithm applied to optimized single pipe routing, and these two algorithms could be embedded to branch pipe routing optimization method. Through the simulation experimental verification, the idea and method put forward in this paper are not limited one single pipe routing optimization method and can be applied widely and easily.