 |
|
Evolution Strategies are variants of Evolutionary Algorithms that have been originated by Schwefel and Rechenberg in the early 60ties. Recent variants of Evolution Strategies are very powerful global and robust local optimization strategies. They have been successfully applied for various applications in engineering and economics since then.
The main search procedure in Evolution Strategies is the mutation operator, that generates random samples around search points (solution candidates) selected from a population of different search points. This is done by adding random values to the vector components of the search point, thereby sampling with continuous Gaussian and/or discrete geometric multivariate distributions. The shape of this multivariate distributions is adapted to the local topology of the objective function, by a mechanism that is termed self adaptation. In particular, this is done by the adaptation of the average step-sizes for the perturbation of input variables.
In modeFRONTIERTM three important variants of Evolution Strategies have been implemented:
The first variant implements the classical (1+1)-Evolution strategy with the 1/5-th success rule for deterministic control of step-sizes. It can be used for fast and robust local optimization (single-objective, continuous). This algorithm is easy to be applied, because of its automatic step-size parameter control and is considered to be fast compared to other ES optimization algorithms, if parallelism cannot be exploited.
The second variant is an elitist version of the Derandomized Evolution Strategy (DES). The DES is a robust local search procedure that works with a fast deterministic (derandomized) adaptation of the multivariate mutation distribution. As the (1+1)-Evolution strategy it can be used for fast single-criterion optimization in continuous search spaces. Unlike the first strategy it can also be parallelized.
The third variant implements a family of population-based global optimization Evolution Strategies the Multimembered Multicriterial Evolution Strategies (MMES). These sophisticated methods allow to exploit the full power of global optimization using Evolution Strategies. They can deal with integer (discrete) as well as with continuous variables. Moreover they are capable of approximating the Pareto Set in multi-criteria optimization.
A better description of these algorithms is available in the paper Evolution Strategies Module R1.1 for modeFRONTIER.
The (1+1)-Evolution Strategy is the "classical" variant of evolution strategies. It employees the 1/5-th success step size control rule in order to control the variance of the mutation steps automatically. It has been proved by Schwefel and Rechenberg that this rule leads to a optimal local convergence velocity in situations where the optimum is far away from the desired optimum (only one direction in the search space leads to an improvement) and also in situations where the search point is located near the optimum of an differentiable function. The rule has been adopted in a way that it yields the optimal convergence velocity independently of the number of design variables.
The (1+1)-Evolution Strategy is a very fast evolutionary algorithm. Compared to population-based algorithms it might easier converge prematurely. However, its rank-based selection mechanism and the gradual success-based refinement of the step-sizes, starting from high step-sizes, makes it robust for slightly noisy functions and in the presence of discontinuities.
The (1+1)-Evolution strategy works in a sequential way and uses a single step size variance. Thus, this algorithm should be used if parallelism cannot be exploited to speed-up search and the significance of parameters is similar, so that it is not required to learn an individual step-size for each design variable. Furthermore its application is by now restricted to single-objective continuous problems.
The following strategy parameter have to be specified when using the (1+1)-ES:
Number of Generations: This determines the maximal number of iterations the algorithm will run. Note that number of evaluations is λ times higher than this number (λ denotes the number of offspring individuals).
Initial Stepsize: This value determines the standard deviation of the initial mutation distribution in percentage of range.
Random Generator Seed: the modification of this value allows the execution of different runs starting from the same initial population. The Seed is an integer number used for sequence repeatability. If two DES Sequences are evaluated with the same seed and the same start points are used, they will generate and return identical sequences of numbers and a run can be exactly reproduced. If the seed value is 0, the sequence is automatically seeded to a value based on the machine clock.
Derandomized Evolution Strategies are very robust local optimization procedures that can be used for single-criterion optimization with high-dimensional continuous functions. Their small population sizes and their accelerated step-size adaptation makes them suitable for optimization with time expensive target functions, like they typically occur in engineering design.
In modeFRONTIERTM an improved variant of the DES has been implemented combining the success based step-size adaptation that have been suggested by I. Rechenberg and H. P. Schwefel with the direct adaptation of the mutation distribution suggested by A. Ostermeier and N. Hansen. The resulting procedure has an increased convergence reliability for difficult search spaces, especially when dealing with small population sizes. Furthermore, a constraint treatment with a penalty approach for implicit constraints and an interval reflection method for explicit bound constraint treatment have been introduced.
Note:
the derandomized ES deals "only with continuous" parameters, i.e. the base within modeFRONTIERTM should be set to 0 for all input variables (any other base is ignored).
The following strategy parameters have to be specified when using the DES:
Number of Generations: This determines the maximal number of iterations the algorithm will run. Note that number of evaluations is λ times higher than this number (λ denotes the number of offspring individuals).
Offspring-Population Size: This parameter determines the number of variants that are generated by Monte Carlo Sampling in one iteration using the adapted mutation distribution. As a default value the approximate formula int(3+3 ln(n)) is recommended. Here n denotes the number of input variables. For difficult multimodal functions the value should be increased and for simple but time expensive functions the value can be slightly decreased.
Initial Stepsize: This value determines the standard deviation of the initial mutation distribution in percentage of range.
Random Generator Seed: the modification of this value allows the execution of different runs starting from the same initial population. The Seed is an integer number used for sequence repeatability. If two DES Sequences are evaluated with the same seed and the same start points are used, they will generate and return identical sequences of numbers and a run can be exactly reproduced. If the seed value is 0, the sequence is automatically seeded to a value based on the machine clock.
Note:
λ is the number of individuals of an offspring population can be evaluated simultaneously on different processors. Therefore, the number of concurrent design evaluations can be chosen in the Run Project Dialog as a value between 1 and λ, determining how many parallel evaluation threads are launched at a time.
The multi-membered ES scheduler implements a family of population-based (or: multi-membered) Evolution Strategies with mutative self-adaptation of step-size variances. It includes an multiobjective extension of Evolution Strategies using the Non-dominated/Crowding distance sorting technique as it is used in NSGA-II. Furthermore it is capable of dealing with mixed integer problems by employing specialized variation operators for different parameter types.
The main difference of MMES to DES is that it works typically with a population of search points and not with a single search point. There are many advantages for using populations of search points rather than using a single search point. First of all it is possible maintain multiple high performance regions at the same time, thereby increasing the chance to hit the global optimum. Furthermore, a good coverage of the Pareto-set in multiobjective optimization can be achieved by working with a population.
The family of Evolution Strategies implemented in modeFRONTIERTM is termed (μ,κ,λ)-ES. Here μ denotes the number of parents, λ denotes the number of offspring and κ the maximal number of iterations that an individual can survive in a parent population. In case of κ=1 the strategy is termed (μ,λ)-ES and in case of κ=∞ the strategy is termed (μ+λ)-ES.
The treatment of multiple objectives is done in a similar way than in the NSGA-II selection procedure. First the offspring population is sorted by means of non-dominated sorting. Then crowding-distance sorting is used, to decide which of the uncomparable solutions are favored. While the non-dominated sorting allows a quick convergence to the Pareto optimal front, the crowding-distance sorting allows to diversify the population in a later stage of the optimization in order to achieve a good coverage. The variation operators of the multiobjective ES remain the same as in the single objective ES. Thus, after a while a refinement of search on the Pareto front takes place, caused by the automatic decrease of mutation step-size variances.
The MMES treats continuous variables as well as discrete variables. For both types of variables scalable isotropic random distributions have been chosen deciding upon the mutation variances. These are the normal distribution for the continuous object variables and a geometric distribution for the integer variables. Furthermore a bound constrained treatment with an interval reflection method has been introduced.
Constraints are treated by a penalty function using a boolean comparison between feasible and unfeasible individuals and then deciding on the rank of two feasible solutions or two unfeasible solutions by comparing their objective function values or the severity of constraint violations, respectively.
The following parameters need to be set for the MMES:
Number of Generations (T): This determines the number of iterations for the algorithm. The number of evaluations is equal to N=λ*T+μ.
Minimal step-size: Minimal Standard deviation for the stochastic distribution that is used to generate offspring individuals.
Offspring-Population Size (λ): This parameter determines the number of variants generated from the parent population in one iteration. If self-adaptation should be employed it is recommended to work with a surplus of offspring individuals (μ/λ=1/7). If a lower ratio μ/λ is chosen, the ability to find the global optima on multimodal surfaces increases while the convergence speed decreases. Anyway, the restriction μ*κ<λ should never be violated, in order to avoid the strategy producing a random walk through the search space.
Initial step-size: This value determines the standard deviation of the initial mutation distribution in percentage of range.
Single Step: Setting single step to true means to maintain only a single step-size variance for the design variables. This typically makes the self-adaptation more fast and robust. However, the local convergence velocity will decrease in narrow valleys of the search landscape. If single step is set to false individual step-size variances are maintained for each design variable.
Recombination / Recombination of Step-Sizes: The Recombination of object variables and step-sizes are operators that allow to stabilize the search process by decreasing the radius of a population and exchange information between individuals. The Recombination operator chooses two individuals from the parental population and then generates an offspring by combining their genetic information. This can be done by an arithmetic mean calculation(intermediate recombination) or by selecting each vector component randomly from one of the solutions (discrete recombination). It is recommended to keep the default settings, for single criterion optimization on continuous variables. If discrete variables are used, a discrete recombination can be advantageous. For multi-criteria optimization the recombination of object variables should be turned off, in order to increase diversity of solutions on the Pareto-front(s).
Maximal Life Span (κ): The maximal life span is the maximal number of iterations that an individual can survive in the parent population. For highly restricted and/or discontinuous problems a value of approximately 5 is recommended. If μ/κ is high (=1/7) lower values should be chosen. If μ/κ is very low then a very high κ is recommended, in order to preserve the algorithm to execute a random walk.
Note:
the constraint μ*κ<λ should always hold.
Adaptation Speed: This parameter determines the speed of adaptation for the step-sizes. It should be set to its default value, which is usually very robust. If it is desired to turn off step-size adaptation, choose a value of 1.0. For a fast step size adaptation the parameter should be increased.
Note:
in the latter case, a very fast step-size adaptation might lead to premature convergence or even divergence of the strategies.
Random Generator Seed: The modification of this value allows the execution of different runs starting from the same initial population. The Seed is an integer number used for sequence repeatability. If two MMES Sequences are evaluated with the same seed and the same start points are used, they will generate and return identical sequences of numbers and a run can be exactly reproduced. If the seed value is 0, the sequence is automatically seeded to a value based on the machine clock.
Note:
λ is the number of individuals of an offspring population can be evaluated simultaneously on different processors. Therefore, the number of concurrent design evaluations can be chosen in the Run Project Dialog as a value between 1 and λ, determining how many parallel evaluation threads are launched at a time.
