Application single-kid genetic algorithm for tree pipe network optimization arrangement
Zhou Rongmin 1, Lin Zi 2 (1. Zhengzhou University Water Ring College 2. Northwest Agricultural Science and Technology University)
Abstract: Tree pipe network layout optimization is a typical combination optimization problem. In this paper, the characteristics of the tree pipe network are theoretically based on the theoretical basis of the map and the genetic algorithm. It is applied to improve the genetic algorithm single-pro-genetic algorithm for the tree management network to optimize the arrangement, and the corresponding adaptive function, single-minded operator and Reverse operator. Compared with the Dijkstra algorithm and the Kruskal algorithm, the single-child borus is directly invested by the pipe network to the optimization goal, and the minimum arrangement scheme for the investment of pipe network is available, and the optimization efficiency of the algorithm is high, the convergence and stability are better. .
Keywords: single-pro-genetic algorithm; tree pipe network; optimized arrangement
Request Date: 2000 05 17 Author Summary: Zhou Rongmin (1971-), female, Henan Xinye, Ph.D., lecturer, mainly engaged in water-saving irrigation.
1 The basic principle of the tree-shaped pipe network generating optimization arrangement has the properties of the tree in the tree, and the tree tube network with ND nodes corresponds to a tree having an ND node, there is a tree of ND-1. The goal of the tree-shaped pipe network optimization arrangement is to find the form of tree pipe network in the pipe network investment. It is essentially based on the preliminary connection map of the pipe network. The pipeline cost is values, and the minimum tree investment in the pipe network. A preliminary connection map with ND nodes and NPs to be selected by ND nodes, there are many feasible tree pipeline layouts, due to different flow distribution patterns in the pipe network, the difference in hydraulic performance is large. If you use an enumeration method, you seek all spanning trees, the amount of calculation is large, and the solution is low. If the Dijkstra algorithm and the Kruskal algorithm are used in the map, only a total length of the total length of the pipe network and the shortest route can be obtained, but its pipe network investment may not be minimal. Genetic Algorithms GA is an emerging global optimization algorithm that is only based on the target function value, and the basic genetic computing is achieved by group optimization search and randomly performing basic genetic computing. It is suitable for solving discrete combined optimization problems. And complex nonlinear issues [2]. Tree-like pipe network layout optimization is a typical combination optimization problem, can apply a genetic algorithm to optimize arrangement: first select a suitable encoding method to represent a tree-shaped pipeline arrangement, then in the NP strip from NP Select the ND-1 strip to form a pipe network connection subgram, and use the depth priority search algorithm (DFS) to determine its connectivity. If a search can find ND nodes, the connection subgraph is a communication map. After the ND top point and the communication map of ND-1 is a certain support tree, that is, the selected ND-1 strip is constituted a tree pipe network. It is known that the tree is arranged in the form of the tree and the required water (if the outflow pipe network is positive, the flow pipe network is negative), according to the pipe network node continuity equation [3], the treadmone network is obtained from the formula (1) Different flow rates:
BT QT Qt = 0 (1)
{1 indicates that the tube section K and the node i are connected, and the inner water flow flow from the node BIK = 0 indicates that the tube segment does not connect to the node K and the node I, and the water flow flows into the node.
Where: Bt = (bik) n × m (i = 1, 2, ..., n; k = 1, 2, ..., m) is a tree-shaped pipe network association matrix; n is a tree pipe network node number; Tarnate network edge, m = N-1; Qt = (Q1, Q2, Q3, ..., QM) T pipeline traffic column vector; Qt = (Q1, Q2, Q3, ..., Qn) T is node traffic Column vector. Assume that traffic QK is passed by minimum allowing flow rate vmin, calculated by Qk = π / 4D2VMIN DK:
(2)
Equivalent formula G = ADB estimated tree pipe network static investment:
(3)
Where: WC is the static investment in the pipe network, Yuan; A, B is the parameters of the pipe-cost experience formula; LK is the length of the kth pipe in the tree pipe network, m; DK is the knop pipe in the tree pipe network The diameter, m. When using the genetic algorithm to optimize the tree-shaped pipe network, directly use the pipe network investment to the optimization goal, from a set of randomized initial pipe network layout, the genetic algorithm is controlled to optimize the search process, for each feasible tree The pipeline arrangement scheme (1), the formula (2) and the formula (3) calculation pipe network investment size, by continuous searching and evaluating the tree pipe network, gradually evolving to a group of investment minimal arrangement, realizing tree Genetic optimization arrangement of pipe network. 2 The key to the use of genetic algorithm to apply genetic algorithm to optimize the arrangement of coding mode, design adaptation function, genetic operator and genetic control strategy [4]. 2.1 Binary Coding Scheme Apply Genetic Algorithm for Tree Pipe Network Optimization Arrangement, using a simple binary coding method to fully describe the problem required.
Figure 1 Pipe network preliminary connection Figure G Figure 2 tree a
It is assumed that the pipe network is initially connected to the ND nodes and NP strips, and the nodes in the figure are numbered. All coding variables are coded in Figure G, each encoding variation is 0 or 1. According to the number of numbered sequences, the binary string of length NP can represent a sub-figure of the diagram G, when the character value on a certain bit is 1, indicating that the edge of the corresponding sub-map is formed; When the character value is 0, the edge indicating that it corresponds to the side of the composition. According to the code scheme, the binary string of length NP can represent all of the submaps of the graph G, each sub-map corresponds to a possible pipe network connection scheme, and then determines whether the sub-map is a feasible Tree pipe network arrangement scheme. For example, there is a pipe network preliminary connection FIG. G (Fig. 1), there are 5 nodes and 10 sides, nodes, and edge numbers are shown in Figure 1, and all of the sub-graphs of Figure G can be represented by a 10-bit binary string. . Fig. 2 is a support tree of FIG. G, corresponding to a tree tube web, composed of edges 4, 5, 7, and 10, with binary coding, the tree A can be represented as: {0001101001} 2.2 Adaptive function design genetic algorithm During the evolutionary search process, it is required to reflect the survivability of the individual in a non-negative maximum form. In order to adapt to the characteristics of the genetic algorithm, the binary coding method and the target function of the tree pipe network are defined, the adaptivity function is:
F = {and is a hub (4) to 000, other
Among them, f0 = (ND-1) · AdbmaxLmax ,.
Where: F0 is a normal number, its value varies with the size of the optimization problem, ensuring that individual fitness f is always non-negative; LMAX = max (L1, L2, ..., LNP) is in the preliminary connection of the pipe network. The longest tube segment, m; DMAX is the maximum tube diameter at the time of Vmin through the total flow of the pipe network, M; Qi is the flow rate of the i-th segment, determined by the formula (1), M3 / S; DI is vmin The tube diameter, M; Li is the length of the first tube segment, m; Zi is the character value on the i-bit in the individual coded string, which corresponds to the No. I pipe segment in the pipe network, 0 or 0 or 1; NP is the number of tube sections in the pipe network; ND is the number of nodes in the pipe network; other symbols are the same. During the genetic evolution of the tree pipe network, each individual produced is first tested, and it is determined whether it is a tree pipe network. If it is a tree pipe network, the pipeline flow and the tube diameter are calculated using the formula (1) and equation (2), and then the individual adaptation degree F is calculated by the formula (4). The size of the individual adaptation f value is the standard of measuring the advantages and disadvantage of the corresponding arrangement. The larger the f value indicates that the small investment corresponding to the individual is smaller, the higher the viability of the evolution, and the higher the probability of producing offspring. If the individual corresponds to a non-tree-shaped pipe network, the individual adaptation degree f value is zero, the living capacity is the lowest, and it is gradually eliminated during the evolution. 2.3 Single doctrine operator and reverse operator Since there is a ND-1 side of the tree pipe network and satisfy the connectivity, there is less than or greater than the ND-1 character value 1 must not be a tree pipe network. Therefore, in the evolutionary search process, the individual individuals must be controlled to satisfy the necessary conditions that become a feasible scheme, that is, each individual has an ND-1 character value 1. Basic generator algorithm mainly generates a new individual by crossover operator, that is, passed random From the selection of two individuals from the parent population, randomly exchanged some genetic segments of the two parent individuals to form new sub-generation individuals. For tree pipe network layout, cross-operators are easily destroyed into basic conditions that become a feasible solution, and the probability of feasible individual is small. Therefore, this paper is based on the characteristics of the tree pipe network, abandoned the traditional parental crosslinking operator, design a new single-pivotive operator and reverse operator, and called this improved genetic algorithm for "single-kid binary algorithm" ( Single Parent Genetic Algorithm SPGA). Figure 3 Tree B Figure 4 Tree C
The single-donated operator exchanges generates new individuals by exchanging any pair of genes in the maternal gene chain, and the gene is determined randomly with the number of exchanges and the exchanged genetics. For example, the parent A corresponds to the tree A (Fig. 2), producing a new primitive B after random exchange of primary gene, which corresponds to the tree B (Fig. 3), composed of edges 2, 4, 5, and 10.
Master a substrate B.
The single-kind-reverse operator produces a new type C by retrograde a single-parent reverse operator by any of the genetic chains, corresponding to Tree C (Fig. 4), composed of edges 4, 6, 7, and 10.
Mothermium C.
Compared to the basic generator algorithm, SPGA has a protruding feature of SPGA: there is only one parent in the generating process of the sub-community, and a new individual having different traits is produced by randomly performing a transposition operator or a reverse operator. Single-related operators and reverse operators can guarantee the new generation of individuals with the basic characteristics of feasibility, and improve search capabilities for solutions. The single-minded competent operator can cause any parent to generate another new individual through a limited genotylet. Single-priest reversal operators have faster performance, which helps to directly gene in the maid into the substrate. 2.4 Evolutionary Policy Design In the evolution of SPGA, integrated application equality selection and priority selection combined with a mixed selection mechanism, a generation of survival mechanisms combined with group monolithic strategies, single-pivotive operator and reverse operator randomly Evolutionary strategies such as genetic mechanisms, coordinate control of the evolutionary process to advance toward the ideal optimization direction, enhance the optimization efficiency of the algorithm, convergence, and stability. 3 Application Figure 5 Pipe Network initial connection
3.1 Example Description A pipe network preliminary connection diagram (Figure 5) has a total of 10 nodes, 23 possible pipeline connection routes. Each node in the pipe network is 10m3 / h, and the minimum allowed flow rate is 0.5m / s. The pipeline unit price formula is g = 0.0047d1.6347, and the unit of the pipe diameter D is mm. 3.2 SPGA Optimization Arrangement Results The SPGA is used to optimize the reservoir. Set the mass size of 20, the genetic algebra is 400 generation, optimized with different selectivity and commission rate combination mode, and obtain 20 optimal tree pipe network arrangement scheme, wherein the top 10 regimen of the total investment of pipe network is shown in Table 1, SA1 program pipe network investment minimal (Figure 6). Application of SPGA for 400 generations, when the combined mode of the selectivity and the transfer rate change between [0, 0] ~ [0.5, 0.5], corresponding The program running time is 120 ~ 600s, and the program has a total search and evaluated 20 × 400 = 8,000 scenarios, and the calculation time of each scheme is 0.015 ~ 0.075s. At the same time, the ability to obtain the optimal arrangement scheme is obtained in comparison of different optimization methods, and the Dijkstra algorithm in the map is used to optimize the tree-like pipe network. The DA scheme (Fig. 7) is obtained from the water source point 1 to each need for the water node path with the Dijkstra algorithm (Fig. 7), the program running time is 0.06 s; the KRuskal algorithm is used to obtain the shorter length of the total length of the pipe network (Figure 8), the program run time 0.05s. The total length and investment changes of the pipe network of the KA scheme and the SA1 scheme are shown in Table 2.
Table 1 Tree pipe network optimization arrangement scheme for pipe network investment obtained by SPGA
No. Source point pipe network investment / yuan total length / M pipeline number
SA11684.236412351011131920SA21684.296712391011131920SA31692.76312351011151920SA41692.766612391011151920SA51699.556812391011181920SA61700.236512351011181920SA71701.1165123101113161920SA81702.48731238910131920SA91703.16701235810131920SA101704.586412351011131922
Table 2 Tube network length and investment in Ka, DA and SA1 scheme (with node 1 is water source)
Solution Optimization Method Pipe Network Total Length / M Pipe Network Length Change Rate (%) Pipe Network Investment / Yuan Investment Change Rate (%)
KA Program Kruskal Algorithm 60 - 743.2 - DA Program Dijkstral Algorithm 6711.67684.29-7.93SA1 Scenary SPGA Algorithm 646.67684.23--7.94
Figure 6 SA1 scenario Figure 7 DA scheme Figure 8 kA scheme
