Genetic Algorithm

A Discrete Search Method available in the Sizing Method panel. This method is fundamentally discrete and does not use gradients in its search.

The Genetic Algorithm is a type of Evolutionary Algorithm - as the name implies, it selects advantageous traits by emulating biological evolution. An initial "population" of potential solutions is generated and gradually improved.

The starting population is an effectively random selection of "individuals". In the context of ANS, an individual is a proposed selection of pipe sizes for the system in question. At the start of the sizing process, these individuals may have an assortment of good and bad traits. A "bad" trait might be one that violates a Design Constraint or increases the cost of the system.

To improve the Fitness of the population there are three major operations: Selection, Crossover, and Mutation.

Selection occurs by determining the "Fitness" of all individuals in the population. Objective value is not the only concern when determining how acceptable any given individual is, so we need a different function to represent this. This function is a Fitness Function. The Fitness of any given individual is measured based on its Objective value and proximity to, or violation of, Design Requirements. Like Darwin's theory of Survival of the Fittest the goal in this process is to maximize the Fitness of the population as a whole. With the Fitness known for all individuals, a parent population with high Fitness can be selected.

Crossover occurs by "breeding" the parent solutions to generate new solutions. Some of these solutions will, randomly, have inherited good traits from their parents. Others will have inherited bad traits.

Mutation occurs after crossover, introducing a further element of randomness into the system by changing traits with no regard to the parent traits. This allows the algorithm to consider new solutions that were not previously part of the "gene pool." If no new traits can be introduced, the flexibility of the method is limited. If the mutation rate is too high, however, the good traits will not be carried through to new generations as effectively.

The new population is then combined with the parent population, and the process is repeated.

Note: When sizing with a Discrete method, it is possible to start the search with a Continuous Method. This limits the search space which should reduce the run time. When this option is enabled, the user has control over both the Continuous and Discrete methods.

Sizing Control Parameters

Genetic Algorithm Population Size

Number of Discrete Sizes Around Continuous Solution - If Start with Continuous Method is selected, this option limits the search space of the genetic algorithm by only considering discrete sizes close to the continuous solution. For example, a Candidate Set may contain 20 unique sizes. Including all of these sizes makes the problem extremely complex, as indicated in Brute Force Method. It is likely that the best discrete solution is near the best continuous solution, so only searching 4 unique sizes (+/- 2) around the continuous solution can dramatically reduce runtime.
Automatic - Set the User Specified Multiplier to 2 to determine the size of the population to use.
User Specified Multiplier - Every independently sized pipe in the model has a certain number of possible sizes that it may be, as determined by its particular Candidate Set. Because every independently sized pipe in the model can have a unique Candidate Set, it can also have a unique count of possible sizes. This multiplier is based on the sum of all of these counts across the model. For example, if there are 2 independently sized pipes with Candidate Sets P1: (4", 6") and P2 (3", 4", 6", 8"), the total count will be 6, and a multiplier of 3 would give a population size of 18.
User Specified Population - The size of the population can also be directly specified. It is important the population size is not too small as this will artificially limit the capability of finding a good solution. However, population sizes too large will not solve in a reasonable time frame.

Caution: The Advanced Control Parameters below should not be changed under normal circumstances without the direction of AFT Support.

Genetic Algorithm Seed - This number is used to generate a "random" population. The same number will always generate the same initial population.
Genetic Algorithm Parameters

Crossover Probability - The average fraction of the population obtained from crossover. As a probability this does not mean exactly this fraction will be obtained. This value is typically close to 1, meaning that the majority of the population each generation is obtained as children of the parent generation. It is generally less than 1 to avoid losing very good solutions from the parent generation due to poor crossover.
Crossover Distribution Index - This value is inversely proportional to allowed perturbations caused by crossover. That is, a large value will limit the amount of perturbation generated from crossover, whereas a small value will allow significant perturbation.
Mutation Probability - The average fraction of the population subjected to mutation. As a probability this does not mean exactly this fraction will be obtained. This value is typically the inverse of the number of independently sized pipes. As the system (and usually, population) gets very large, the need for "additional" randomness decreases. However, for small systems this randomness is important to introduce to prevent a premature solution.
Mutation Distribution Index - This value is inversely proportional to allowed perturbations caused by mutation. That is, a large value will limit the amount of perturbation generated from mutation, whereas a small value will allow significant perturbation.

Genetic Algorithm Convergence

Consecutive Unimproved Generations - When no improvements in the Objective occur over this number of generations, the sizing process will be stopped and the results are presented. It is assumed from the lack of progress that the ideal solution has been found. It is impossible to tell in advance how many total iterations this condition may require.
Fixed Number of Generations - To limit the runtime to a length that can be estimated, the algorithm can be set to a specific count of generations. This should be used with caution as it is possible to end before the best solution has been found, or to continue long after the best solution has been found.