Optimisation Technical Background

How It Works

DesignBuilder uses a Genetic Algorithm (GA) (aka Evolutionary Algorithm or EA) based on the NSGA2 method (aka NSGA-II) Deb et al. 2002. This is widely used as a "fast and elitist multi-objective" method providing a good trade off between a well converged and a well distributed solution set. NSGA2 uses the non-dominated sorting method, which is proven to be highly effective in ranking competing objectives. One deficiency of the original NSGA2 is that it does not provide a way for handling constraints efficiently. This is addressed in JEA using the stochastic ranking method. It works as follows:

 

  1. First, the population is randomly initialised.
  2. Chromosomes (design variants) are sorted and put into fronts based on Pareto non-dominated sets. Within a Pareto front, the chromosomes are ranked based on Euclidean distances between solutions or I-dist (the term used in NSGA2). Generally, solutions which are far away (not crowded) from other solutions are given a higher preference in the selection process to help create a diverse solution set and avoid crowding.
  3. The best designs are picked from the current population and put into a mating pool.
  4. In the mating pool, tournament selection, crossover and mating is carried out.
  5. The mating pool and current population is combined. The resulting set is sorted, and the best chromosomes are passed into the new population.
  6. Go to step 2, unless convergence has been reached.
  7. The solution set is the highest ranked Pareto non-dominated set from all populations.

Constraints

Constraint implementation in JEA

Constraint handling is a topic that attracts lots of attention from algorithm designers. The efficiency of constraint handling is measured by not only how quickly feasible solutions are found, but also the quality of those feasible solutions. If a strategy pushes too hard for meeting the constraints, it may hamper exploration for better objective values. On the other hand, if it is too lenient, too much time may be wasted on infeasible solutions. The balance depends on the nature of the problem, so a perfect strategy may not exist. JEA uses one of the best strategies in terms of robustness of adaptability to different problems called Stochastic Ranking (Runarsson and Yao, 2000).

 

Stochastic Ranking is a probabilistic strategy to rank solutions with the different objective and constraint values. Its original form is designed for one objective against one constraint. In order to make it work with NSGA-II, the following steps are taken:

 

  1. All constraints are scaled (normalized) and then aggregated so that the infeasibility (constraint violations) is measured as a value in [0, 1].
  2. Infeasibility is used as an additional objective and sorted with Non-dominated Sorting with all other objectives. This produces an initial ranking order of all solutions.
  3. Stochastic Ranking is then applied to the initial rank of each solution (treated as its objective value) and its aggregated infeasibility value. This produces the final ranking of the solutions.

 

The benefit of this slightly complex arrangement is that it works well with problems with any number of objectives (including single objective) and constraints, and unconstrained problems. The user can use a single Objective bias parameter to control the level of the push for feasibility.

 

Two configuration parameters directly affect the behaviour of NSGA2 with Stochastic Ranking. Objective bias controls the ranking bias between Pareto ranking and infeasibility scores. A value of zero means solutions with lower infeasibility score is better, regardless of the Pareto ranking result. Elitism tolerance controls if infeasible solutions can be selected as elites (see below) or not. If a positive value is assigned, e.g. 0.1, it means solutions with infeasibility scores up to 0.1 may be selected as elites.

Constraint implementation in Open Beagle

The lower and upper constraint margins are used as part of the constraint handling method used by DesignBuilder, which is based on a generic penalty function approach. During a constrained optimisation each design alternative is tested against any constraints applied and a penalty is generated based on whether the design is feasible or not, i.e. whether it meets constraint requirements. If the function value is within the feasible range then no penalty is applied and conversely if it is outside the feasible range then a penalty is applied. There is a margin between the feasible and the infeasible regions where a linearly ramped penalty is applied. The upper and lower margins set on the Calculation options dialog are used to define these regions as shown on the graph below.

 

Pareto Archived Elitism

Evolutionary algorithms are stochastic in nature. The user has little control over which direction or what solutions to explore next. Quite often promising solutions may appear in one generation and then disappear for good in subsequent ones. Elitism is a method for preserving good solutions by selecting cases from a pool of known optimum solutions and inserting them back into the working population.

 

In Pareto Archived elitism, all known solutions on the global Pareto front are stored. They form the pool from which the elitism operator picks “elites”. In JEA, the maximum number of elites and whether they can include infeasible solutions can be controlled. Global elitism controls the pool from which the elite solutions are selected. If set to true (default), selection will be made in the global archive; otherwise it is limited to the current population. Elitism tolerance (explained above) also affects how elitism works.

Bibliography

  1. Introduction to Genetic Algorithms:

     

  2. Sean Luke, 2009, Essentials of Metaheuristics, Lulu, available for free at https://cs.gmu.edu/~sean/book/metaheuristics/
  3. A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, Natural Computing Series, Corr. 2nd printing, 2007, ISBN: 978-3-540-40184-1 https://www.cs.vu.nl/~gusz/ecbook/Eiben-Smith-Intro2EC-Ch2.pdf
  4. Deb, K., Pratap. A, Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transaction on Evolutionary Computation, 6(2), 181-197.