A genetic algorithm (GA) is a search method that emulates the principles of genetic reproduction operations such as crossover and mutation. It is a branch of evolutionary computation and formally introduced by Holland in 1975 (Holland 1975). Since then, genetic algorithm has been one of the most active research fields in artificial intelligence. Many successful applications have been made in engineering, science, economy, finance, business and management. There are many variations of GA, but basic idea is as follows.
Simple Genetic Algorithms
GA represents a solution as a string, for instance a binary string as shown in Figure 1. It can be any other type of strings. The string is referred to as phenotype or chromosome. One segment of string is assigned to represent one decision variable (e.g. one leak) and thus one completed solution (e.g. a number of leaks for a water distribution system) is encoded onto one string as shown in Figure 1.
Figure 1 An example of genetic algorithm solution representation
Initially, a population of strings or solutions is randomly created. Each of the solutions is evaluated by performing the corresponding hydraulic simulation (either steady state or transient analysis). A fitness value can be calculated by the objective function and assigned to the solution or string. By emulating the principle of Darwin’s survival-of-fittest, the better solution is selected as parent to reproduce next generation of solution. Figure 2 illustrates operation of selecting two parents.
Figure 2 Example GA population solutions and selection operation
The selected parent strings are to reproduce offspring namely the child solutions. Two operations of crossover and mutation are mimicked for the reproduction. As shown in Figure 3, crossover is to first cut two strings at a randomly selected crossover point and then exchanges partial chromosomes to form two new child solutions.
Figure 3 Genetic algorithm crossover operations
Figure 4 Genetic algorithm mutation operations
After crossover, a new solution may be mutated by changing the bit value. As illustrated in Figure 4, a bit may be selected as highlights and its value is flipped from 0 to 1 (or1 to 0). Both crossover and mutation are applied by performing a probabilistic test and when its probability is greater than the prescribed probability. Repetitively applying selection, crossover and mutation, a new population of solutions can be reproduced, and each of them is evaluated with a fitness value. This far, one generation is completed. Generation after generation, the population of strings are expected to evolve to optimal or near-optimal solution.
This is the basic procedure of simple GA. There are different variations based on the principles of the simple genetic algorithm. The improvement of the existing GA methods and new GAs have been constantly developed and reported in literature every year. Overall, many advantages are identified for GA search for good solutions (Goldberg 1989). The primary merit is its capability of solving nonlinear optimization problems. Model-based leakage detection is a typical implicit nonlinear optimization problem.
Fast Messy Genetic Algorithm Key Features
Similar to simple GA, but fast messy GA (fmGA) is different with the key features including flexible string length, gene filtering and multi-era search process. It is originally developed as one of the competent genetic algorithms (Goldberg 2001) for solving the hard-problems more efficiently and effectively.
With fmGA, a flexible scheme is employed to represent a calibration solution with strings (chromosomes) of variable lengths. The length of strings changes from one string to another. Short strings namely partial solutions are generated and evaluated during the early stage of GA optimization. The short strings with better fitness value above the average are considered to retain “building blocks” that form the good solutions. The fmGA starts with an initial population of full-length strings and follows by a building block filtering process. It identifies the better fit short strings by randomly deleting genes from the initial strings. The identified short strings are used to generate new solutions. A solution is formed by “cut” and “splice” operations instead of standard GA crossover. “Cut” divides one string into two strings while “splice” link two strings to create one individual string. Both genetic operations are purposely designed to effectively exchange the building blocks for generating good solutions.
The fmGA combines building block identification and solution reproduction phases into one artificial evolution process and proceeds over a number of outer iterations or so-called eras. Each era consists of solution initialization, building block filtering and reproduction. The eras continue until good solutions are found or computation resources reach the maximum limit. The fmGA is employed as a competent optimizer for evolving effective water distribution models and embedded into a multi-tier modeling software System (Bentley 2006 and Haestad 2002).