Genetic Algorithms (GA)

Introduction

xlOptimizer implements many variants of Genetic Algorithms (GA). These algorithms are inspired by natural selection and survival of the fittest and they are considered to be amongst the most reliable and efficient methods for global optimization. They were introduced by John Holland as a means to study adaptive behavior [1]. Nevertheless, they have been largely considered to be function optimizers, able to provide near-optimum results by evolving a small population of candidate solutions. Since then, they have been applied to virtually any kind of optimization problem conceivable.

In particular, GA (in fact, almost all Evolutionary Algorithms) are attractive for two main reasons: first, they rely on “payoff” data, i.e. not derivative data, which is very important for highly non-linear or combinatorial problems; secondly, they possess an inherent capability for massive parallel computing. It is noted, however, that their performance in discovering the actual local or global optimum is limited due to the so-called anytime behavior; the development of the population’s best individual shows rapid progress in the beginning, followed by gradual degradation until the point when evolution practically stops [2]. For this reason, GA are often coupled with a local optimizer which takes over when the progress of the GA degrades. In xlOptimizer, the user can introduce Greedy Ascent (or Descent) Hill Climber (GAHC), as a local optimizer, simply by selecting the appropriate option in the configuration form. 

How does it work?

The algorithm mimics the process of natural selection. A population of candidate solutions is evolved, generation by generation, using techniques inspired by natural evolution such as selection, mutation and crossover

The evolution starts from a population of randomly generated individuals. In each generation, the fitness of every individual in the population is evaluated. This is a measure of the quality of the solution, and it is depended on the objective function value corresponding to the solution. Next, multiple individuals are stochastically selected from the current population (according to their fitness) to become parents. Their genetic material is recombined, and possibly randomly mutated, to produce offspring and form a new population. The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the elite (best) member of the population.

Mathematical formulation

Pseudo-code

The so-called Standard Genetic Algorithm (SGA) can be described by the following pseudo-code:

  1. Initialize randomly the population of individuals (chromosomes).
  2. Calculate the fitness of each individual in the population.
  3. Select individuals to form a new population according to each one’s fitness.
  4. Perform crossover and mutation to form a new population.
  5. Copy the best (elite) individual to the new population.
  6. Repeat steps (2–5) until some condition is satisfied.

Note that there is not a universally accepted "standard" variant of the GA. For example, step (5) is included in our definition since it dramatically increases the performance of the GA in practically all problems. 

Encoding

The SGA uses binary representation; each design variable is encoded in a series of bits of appropriate length. This string of 0’s and 1’s, called gene, uniquely maps this design variable to a certain value in the real problem. Arranging all genes in a single string produces a chromosome, or a candidate solution of the real problem. The evolution takes place using the binary representation, i.e. using genotype. 

Fitness

The fitness of each chromosome is determined by the corresponding objective function value. This objective function is determined by the user. Usually it returns the cost of the candidate solution, and thus it is referred to as the cost function (to be minimized). 

Initialization

Initially, solutions are randomly generated to form an initial population. The population size depends on the nature of the problem.

Selection

During each successive generation, a proportion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods rate the fitness of each solution and preferentially select the best solutions.

Reproduction: Crossover and mutation

The next step is to generate a new population of solutions using genetic operators: crossover (also called recombination), and/or mutation.

For each new solution to be produced, a pair of "parent" solutions is selected for breeding. Mutation is also stochastically applied to the offspring, which allows the GA to avoid entrapment into local optima and explore new regions of the search space. New parents are selected for each new child, and the process continues until a new population of solutions of appropriate size is generated.

Elitism

Elitism is used in order to ensure that (at least) the best individual of the current generation survives to the next one. Typically one individual, i.e. the best, is transferred as-is to the next generation.

Termination

This generational process is repeated until a termination condition has been reached. Common terminating conditions are:

  • A solution is found that satisfies some criteria
  • An allocated computation budget is reached
  • The highest ranking solution's fitness is reaching or has reached a plateau such that successive iterations no longer produce better results
  • Combinations of the above

Options in xlOptimizer

The following options are available in xlOptimizer:

Step 1

genetic algorithms xloptimizer options step 1

Enter a short title for the scenario. The log files will be saved to a subfolder with this name.

Step 2

genetic algorithms xloptimizer options step 2

Enter the population size for the GA. Usually the optimum value depends on the complexity and the nature of the problem. A mathematical expression may also be used.

  • Example 1: entering '50' sets the population size to 50 individuals.
  • Example 2: entering 'IF(CHROMO_LENGTH_BITS / 2 < 100, CHROMO_LENGTH_BITS / 2, 100)' sets the population size to the chromosome length divided by two if the result is less than 100, or 100 otherwise.

The variables that may be used in the expression are:

  • CHROMO_LENGTH_BITS: the chromosome length in bits.
  • CHROMO_LENGTH_GENES: the chromosome length in genes. This equals the number of design variables.

Step 3

genetic algorithms xloptimizer options step 3

Choose the selection method. The method can be either tournament selection or biased roulette wheel. Usually, tournament selection with pool size equal to 2 and probability equal to 1 is adequate. The roulette wheel method requires the definition of a fitness function, based on the objective function. The evaluation of the fitness can be performed automatically, or based on custom code. In the latter case, the variables that can be used are the following:

  • MIN_OV: the minimum objective value within the members of the population.
  • MAX_OV: the maximum objective value within the members of the population.
  • AVER_OV: the average objective value within the members of the population.
  • BEST_OV: the best objective value within the members of the population.
  • WORST_OV: the worst objective value within the members of the population.
  • OV: the objective value of the current individual for which the fitness is being evaluated.
  • TARGET: the target objective value for target - problems.

The automatic evaluation is based on the following code:

  • '(OV - MIN_OV) / AVER_OV' for maximization problems,
  • '(MAX_OV + MIN_OV - OV) / AVER_OV' for minimization problems,
  • '(ABS(MAX_OV - TARGET) + ABS(MIN_OV - TARGET) - ABS(OV - TARGET) / ABS(AVER_OV - TARGET)' for target-value problems.

Based on the above, a first level of normalization is achieved with the division by the average objective value.

Step 4

genetic algorithms xloptimizer options step 4

Select the crossover method. Usually single crossover with probability 0.7 or uniform crossover with probability 0.5 is selected. Also, choose whether the selected pair of chromosomes will produce one or two offspring.

Step 5

genetic algorithms xloptimizer options step 5

Select the probability for jump and creep mutation.

  • Common setting for jump mutation code is '1 / NEXT_POP_SIZE'. In this case the random number generator is invoked NEXT_POP_SIZE * CHROMO_LENGTH_BITS times.
  • Common setting for creep mutation code is 'CHROMO_LENGTH_BITS / CHROMO_LENGTH_GENES / NEXT_POP_SIZE'. In this case the random number generator is invoked NEXT_POP_SIZE * CHROMO_LENGTH_GENES times.

Step 6

genetic algorithms xloptimizer options step 6

Select the number of elite chromosomes that will pass to the next generation. Common setting for elitism code is '1', the single best individual is transferred to the next generation.

Step 7

genetic algorithms xloptimizer options step 7

Select other algorithm settings. The options are the following:

  • Gray code: Choose whether the chromosome is encoded using Gray code or not.
  • Niching: Select the alpha coefficient (power law exponent for sharing function; typically = 1.0) and the normalized distance ( 1/normalized distance can be viewed as the number of regions over which the sharing function should focus). This affects the design variables that have been set to participate in a niching strategy.
  • Hill climber: Choose whether after the termination of the GA a local optimizer, namely Greedy Ascent Hill Climber, is invoked. Also select the maximum number of function evaluations for the local optimizer.

Step 8

genetic algorithms xloptimizer options step 8

Choose whether to use the Registrar operator with the algorithm. This is recommended only for expensive objective functions.

Step 9

genetic algorithms xloptimizer options step 9

Select the termination criteria. At least one termination criterion must be active. Usually one selects a maximum number of function evaluations and/or a time limit.

Step 10

genetic algorithms xloptimizer options step 10

Select the action when the analysis is finished:

  • Nothing: The last individual analysed remains.
  • Restore previous solution: The solution that was visible before the analysis is restored.
  • Use best: The best solution that was discovered during the analysis is applied.
  • Use best if better than the previous version (recommended): The best solution that was discovered during the analysis is applied only if it is better than the previous solution. In the opposite case the previous solution is restored.

Step 11

genetic algorithms xloptimizer options step 11

Select whether you want to use random or specific seeds for the random number generator. The seeds must be large negative numbers e.g. -100000. Usually a number of analyses with random seeds is performed. The filename of the log is the seed used in the specific analysis.

Step 12

genetic algorithms xloptimizer options step 12

Select the output path. A subfolder with the name of the scenario will be used. Usually a relative path is used i.e. the absolute path check box is not checked. This results in the output logs being saved in the same path as the project file. 

References

[1] Holland, J.H., 1975. Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor.
[2] Eiben, A.E., Smith, J.E., 2003. Introduction to Evolutionary Computing. Springer, New York.