Genetic Algorithm

Genetic algorithms (GA) are modeled after the evolutionary process theory. GA starts with the creation of a population of designs (a generation). These designs are then ranked with respect to their fitness. Fitness is a measure of how good a design is and it is calculated as a function of constraint violation and objective function values. Selected designs are then reproduced through the application of genetic operators, typically crossover and mutation. The individuals that result from this process (the children) become members of the next generation. This process is repeated for many generations until the evolution of a population converges to the optimal solution.

Usability Characteristics

•	Genetic algorithms differ from conventional optimization techniques in the following ways:

-	They are classified as exploratory methods.

-	They work on a population of designs at once.

-	The design population can be run in parallel.

-	They do not show the typical convergence of other optimization algorithms. You will typically select the maximum number of iterations (generations) to be evaluated. A number of solver runs is executed in each generation, with each run representing a member of the population.

•	Genetic algorithms do a global search.

•	They are well suited for discrete problems.

•	Genetic algorithms are computationally expensive as they require a large number of runs. In HyperStudy, a local search algorithm (Hooke-Jeeves or a response surface method) is utilized to improve the efficiency of GA.

•	In HyperStudy, population size is calculated automatically according to the optimization problem that you defined. It can also be modified manually.

•	In HyperStudy, both a binary and a real coded GA exists. Default is the real coded GA as it is more efficient than the binary coded GA.

•	GA terminates if one of the conditions below are met:

-	The convergence criteria is satisfied. This occurs when the minimum number of allowable iterations (MINDES) are run, the current design is feasible (GMAX), and the change of objective during m successive iterations is small (less than 0.001).

-	The maximum number of allowable iterations (MAXDES) is reached.

-	An analysis fails and the “Terminate Optimization” option is the default (IGFAIL).

The flowchart below illustrates the different phases of the GA process.

GA_flowchart

Settings

In the Specifications step, you can change the settings of GA from the following tabs:

In the Settings tab, you can access the settings listed below. Please note that for most applications the default settings work optimally, and you may only need to change the Maximum Iterations and On Failed Analysis.

Setting

Default

Range

Description

Maximum Iterations

(MAXDES)

200

> 0

Maximum number of iterations allowed.

Minimum Iterations

(MINDES)

> 0,

<= MAXDES

GA process at least MINDES iteration steps.

This can be used to prevent pre-mature convergence.

By setting MINDES to be the same as MAXDES, GA will run the defined number of iteration steps.

Population size

(GAPOPS)

Integer > 1

If GAPOPS is 0, then population size is calculated according to the following function, where N is the number of input variables.

ga1

If GAPOPS is greater than 0, then population size uses the user defined value.

If the allowable computational effort is limited, please set your own value. In general, it is better to allow GA to process at least 25 iteration steps.

Global search

(GAGLOB)

Integer

1, 2, 3

Controls the global search ability. The larger value of GAGLOB, the larger probability that the global optimal solution can be reached, but more calculating time is needed.

Constraint violation tol.

(GMAX)

0.1

>0.0

Global maximum allowable percentage constraint violation. Constraints must not be violated by more than this value in the converged design.

GA is converged: minimum number of allowable iterations (MINDES) are run and current design is feasible (GMAX) and the change of objective during m successive iterations is small (less than 0.001).

This can be formulated as:

ga2

Where, is the objective value; is the current iteration number; is proportional to the global search parameter; is the maximum constraint violation; is the allowable constraint violation.

Type

(GATYPE)

0 or 1

Real coded GA is used.

Note:

When GATYPE is 0, GADISC, GATOUR, GAPMUL and GAPPOW are grayed out.

Binary coded GA is used.

Note:

When GATYPE is 1, then GAINDX is grayed out.

In general, real coded GA performs better than binary coded GA. For discrete optimization problem, binary coded GA could be better.

On failed analysis

(IGFAIL)

Termination

Termination or Ignore Failed Analysis

Termination

GA terminates with an error message when an analysis run fails (default).

Ignore Failed Analysis

GA ignores the failed analysis run.

In the More tab, you can access the setting listed below. Please note that for most applications, the default settings work optimally.

Setting

Default

Range

Description

Discrete states

(GADISC)

1024

Integer > 1

Number of discrete values uniformly covering the range of continuous variables including upper and lower bound. Recommendation: select as a power of 2, e.g. 64 = 2^6, 1024 =2^10, etc.

Larger value allows higher solution precision, but more computational effort is needed to find the optima.

Mutation rate

(GAMUTR)

0.01

0.0 – 1.0

Mutation rate (probability)

Recommended range: 0.001 – 0.05

Larger values introduce a more random effect. As a result, GA can explore more globally but the convergence could be more slowly.

Elite population %

(GAELIT)

1.0 – 50.0

Percentage of population that belongs to elite.

The one with high fitness value is directly passed to the next generation. This is a very important strategy in GA to ensure the quality of solutions be non-decreasing. Larger value means that more individuals will be directly passed to the next generation. So new gene has less chance to be introduced. The convergence speed could be increased. The drawback is that too large value could cause premature convergence.

Recommended range: 1.0 – 20.0.

Random Seed

(GAREPT)

Integer

0 to 10000

Controlling repeatability of runs depending on the way the sequence of random numbers is generated.

Random (non-repeatable).

> 0

Triggers a new sequence of pseudo-random numbers, repeatable if the same number is specified.

Number of contenders

(GATOUR)

Integer

2 to 5

Number of contenders in a tournament selection.

For larger value, individuals with lower fitness value have less chance to be selected. Thus, the good individuals have more chance to produce offspring. The bad effect is that, diversity of the population is reduced. GA could converge prematurely.

Penalty multiplier

(GAPMUL)

2.0

> 0.0

Initial penalty multiplier in the formulation of the fitness function as exterior penalty function. Penalty multiplier will be increased gradually with iterating steps going on.

In general, larger value allows the solution to become feasible with less iteration steps; but too large value could result in a worse solution.

Recommended range: 1.0 – 5.0.

Penalty power

(GAPPOW)

> 0.0,

< 10.0

Penalty power in the formulation of the fitness function as exterior penalty function.

Recommended range: 1.0 – 2.0.

Distribution Index

(GAINDX)

Integer

1 to 100

Distribution index used by real coded GA.

This parameter is to control offspring individuals to be close to or far away from the parent individuals. Increasing the value will result in offspring individuals being closer to the parents.

Recommended range: 3 – 10.

Hybrid Algorithm

(GALOCAL)

0, 1 or 2

The hybrid algorithm used in GA.

0 hybrid1 (Hooke-Jeeves method)

1 hybrid2 (Meta-model based method)

2 no hybrid

Note: This parameter is used in Genetic Algorithm real type. It is not available for binary type.

Constraint threshold

(EPSCON)

1.0e-4

> 0.0

This parameter is used for constraint value calculation. In general, constraint value is normalized to its bound value. One exception is that, constraint value is not normalized if its absolute bound value is less than this parameter. Recommended range is 1.0e-6 ~ 1.0.

Use Inclusion Matrix

(INCLUSI)

No, With Initial

•	No ignores the Inclusion matrix

•	With Initial combines Inclusion matrix with the initial population sample.