The problem of obtaining optimal designs of water distribution systems using diameters selected from a discrete set is NP-hard . This paper presents the initial results of exploratory research on a maximum entropy-constrained approach to the design optimization of water distribution networks using discrete pipe diameters based on a simple genetic algorithm (GA). The formulation uses Shannon's informational entropy [2,3] as a surrogate measure for the reliability of the water distribution system. Some of the advantages of the entropy measure for water distribution networks are its minimal data requirements, ease of computation and incorporation into design optimization procedures, and evidence of good correlation between entropy and hydraulic reliability. It is a function of the pipe flow rates only and reflects the uniformity of the pipe flow rates and the numbers of supply paths to the various demand nodes. It increases with both the numbers of alternative supply paths and the uniformity of the pipe flows. The novelty of this research is that it combines informational entropy, discrete pipe diameters and evolutionary computing.
A simple GA was used in a FORTRAN 95 program in which a maximum entropy constraint was added to the standard set of design constraints for water distribution networks. The program included routines for the hydraulic analysis of water distribution networks and informational entropy. Although different maximum entropy values are associated with different sets of feasible flow directions in a water distribution system, there is a unique maximum entropy value for any feasible set of flow directions. Hypothetical networks from the literature whose maximum entropy minimum-cost solutions for continuous pipe diameters are known were used to verify the results obtained from the GA program. The GA performed well and found the global optimum solutions.
The GA seeks out the most cost-effective design-flow directions using the available set of discrete pipe diameters. The informational entropy routine yields the entropy value for the actual pipe flow rates and the maximum entropy value, for every candidate solution. The entropy calculations are not time consuming and require the flow directions to be known. The hydraulic network solver yields the pipe flow rates and directions which are then used to calculate the actual and maximum entropy values. In turn, these values are used to evaluate the magnitude of the constraint violation for the maximum entropy constraint, for each candidate solution. This research is still in progress and the main conclusion so far is that the GA appears capable of identifying the least-cost maximum entropy solution with discrete pipe diameters.
- water distribution
- informational entropy
- genetic algorithms
- design optimization
- evolutionary computing