Construction of Optimal Tubular Networks in Arbitrary Regions in R^3

Tubular network;Circle packing;Matching;Genetic algorithm;Applied Mathematics

Jiang, Wenzhe

University of Waterloo

关键词: Tubular network;    Circle packing;    Matching;    Genetic algorithm;    Applied Mathematics;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/9510/1/Jiang_Wenzhe.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In this thesis, we describe various algorithms for the construction of tubular networks in an arbitrary three-dimensional region that possesses a principal direction along which the cross-section varies. The region can be digitized into a series of blocks B_i, each of which exhibits no variation in the principle direction. Tubular networks with one inlet and one outlet are constructed by connecting the series of blocks packed with parallel cylindrical tubes.Packing tubes into a block B_i can be simplified to packing circles into its cross section C_i which is approximated by a polygon. A set of novel circle-packing algorithms are developed to possess the following desirable features. Firstly, circles are first packed into an interior region which is common to several or all blocks and the remainder of the unpacked region are packed afterwards. Secondly, larger circles are placed primarily in the central part of the region. Lastly, at a certain stage of circle-packing, all the packed circles are moved towards the center of mass by a fictitious force so that as much as possible empty space is left along the boundary.Three fundamental connections are used to construct a tubular network with one inlet and one outlet: (i) endcap connection--two 90-degree bends that connect two adjacent tubes at their ends, (ii) a ;;merge” operation in which a tube flows into an adjacent tube, and (iii) a ;;shift” operation in which a tube is shifted into an adjacent position. Tubes at the extreme ends of a network must be connected by endcaps and the other tubes could be connected via any one of the above connections. A set of algorithms are developed to generate all the possible solutions of constructing tubular networks and to check the feasibility of solutions to make sure there is no ;;dead end” or ;;isolated loop”.Among all the feasible networks, an optimal network should be chosen with respect to a certain measure. Obviously, enumerating all the possible solutions of constructing feasible networks is extremely time-consuming and sometimes it can take millions of years. Therefore, genetic algorithm with only mutation is applied here to randomly search for the best network. In this genetic algorithm, every fundamental connection could mutate to any other fundamental connection. Thus every network could mutate to any other one and genetic algorithm could find the globally best network.