DEA (Differential Evolution Algorithm)

This is an implementation of the Differential Evolution Algorithm algorithm, as published in Storn1997.

DEA optimizes a problem by updating a population of candidate solutions through mutation and recombination. The update rules are simple and the objective function must not be differentiable. Our implementation includes various adaption and updating strategies Brest2006.

Usage

e["Solver"]["Type"] = "Optimizer/DEA"

Results

These are the results produced by this solver:

Best F(x)

  • Usage: e[“Results”][“Best F(x)”] = real number

  • Description: Optimal value of F(x) found so far.

Best Parameters

  • Usage: e[“Results”][“Best Parameters”] = List of real number

  • Description: Value for the x parameters that produced the best F(x).

Variable-Specific Settings

These are settings required by this module that are added to each of the experiment’s variables when this module is selected.

Lower Bound

  • Usage: e[“Variables”][index][“Lower Bound”] = real number

  • Description: [Hint] Lower bound for the variable’s value.

Upper Bound

  • Usage: e[“Variables”][index][“Upper Bound”] = real number

  • Description: [Hint] Upper bound for the variable’s value.

Initial Value

  • Usage: e[“Variables”][index][“Initial Value”] = real number

  • Description: [Hint] Initial value at or around which the algorithm shall start looking for an optimum.

Initial Mean

  • Usage: e[“Variables”][index][“Initial Mean”] = real number

  • Description: [Hint] Initial mean for the proposal distribution. This value must be defined between the variable’s Mininum and Maximum settings (by default, this value is given by the center of the variable domain).

Initial Standard Deviation

  • Usage: e[“Variables”][index][“Initial Standard Deviation”] = real number

  • Description: [Hint] Initial standard deviation of the proposal distribution for a variable (by default, this value is given by 30% of the variable domain width).

Minimum Standard Deviation Update

  • Usage: e[“Variables”][index][“Minimum Standard Deviation Update”] = real number

  • Description: [Hint] Lower bound for the standard deviation updates of the proposal distribution for a variable. Korali increases the scaling factor sigma if this value is undershot.

Values

  • Usage: e[“Variables”][index][“Values”] = List of real number

  • Description: [Hint] Locations to evaluate the Objective Function.

Configuration

These are settings required by this module.

Population Size

  • Usage: e[“Solver”][“Population Size”] = unsigned integer

  • Description: Specifies the number of samples to evaluate per generation (preferably 5-10x the number of variables).

Crossover Rate

  • Usage: e[“Solver”][“Crossover Rate”] = real number

  • Description: Controls the rate at which dimensions of the samples are mixed (must be in [0,1]).

Mutation Rate

  • Usage: e[“Solver”][“Mutation Rate”] = real number

  • Description: Controls the scaling of the vector differentials (must be in [0,2], preferably < 1).

Mutation Rule

  • Usage: e[“Solver”][“Mutation Rule”] = string

  • Description: Controls the Mutation Rate.

  • Options:

    • “Fixed”: Fixed mutation rate.

    • “Self Adaptive”: Varying Crossover Rate and Mutation Rate, according to [Brest2006].

Parent Selection Rule

  • Usage: e[“Solver”][“Parent Selection Rule”] = string

  • Description: Defines the selection rule of the parent vector.

  • Options:

    • “Random”: Select parent randomly.

    • “Best”: Mutate only best variables.

Accept Rule

  • Usage: e[“Solver”][“Accept Rule”] = string

  • Description: Sets the accept rule after sample mutation and evaluation.

  • Options:

    • “Best”: Update best sample if better than Best Ever Sample.

    • “Greedy”: Accept all candiates better than parent.

    • “Iterative”: Iterate through candidates and accept if Best Ever Value improved.

    • “Improved”: Accept all candidates better than Best Ever Sample.

Fix Infeasible

  • Usage: e[“Solver”][“Fix Infeasible”] = True/False

  • Description: If set true, Korali samples a random sample between Parent and the voiolated boundary. If set false, infeasible samples are mutated again until feasible.

Termination Criteria

These are the customizable criteria that indicates whether the solver should continue or finish execution. Korali will stop when at least one of these conditions are met. The criteria is expressed in C++ since it is compiled and evaluated as seen here in the engine.

Max Infeasible Resamplings

  • Usage: e[“Solver”][“Max Infeasible Resamplings”] = unsigned integer

  • Description: Max number of mutations per sample per generation if infeasible (only relevant if Fix Infeasible is set False).

  • Criteria: _infeasibleSampleCount > _maxInfeasibleResamplings

Min Value

  • Usage: e[“Solver”][“Min Value”] = real number

  • Description: Specifies the target fitness to stop minimization.

  • Criteria: (_k->_currentGeneration > 1) && (-_bestEverValue < _minValue)

Min Step Size

  • Usage: e[“Solver”][“Min Step Size”] = real number

  • Description: Specifies the minimal step size of the population mean from one gneration to another.

  • Criteria: _currentMinimumStepSize < _minStepSize

Max Value

  • Usage: e[“Solver”][“Max Value”] = real number

  • Description: Specifies the maximum target fitness to stop maximization.

  • Criteria: _k->_currentGeneration > 1 && (+_bestEverValue > _maxValue)

Min Value Difference Threshold

  • Usage: e[“Solver”][“Min Value Difference Threshold”] = real number

  • Description: Specifies the minimum fitness differential between two consecutive generations before stopping execution.

  • Criteria: _k->_currentGeneration > 1 && (fabs(_currentBestValue - _previousBestValue) < _minValueDifferenceThreshold)

Max Model Evaluations

  • Usage: e[“Solver”][“Max Model Evaluations”] = unsigned integer

  • Description: Specifies the maximum allowed evaluations of the computational model.

  • Criteria: _maxModelEvaluations <= _modelEvaluationCount

Max Generations

  • Usage: e[“Solver”][“Max Generations”] = unsigned integer

  • Description: Determines how many solver generations to run before stopping execution. Execution can be resumed at a later moment.

  • Criteria: _k->_currentGeneration > _maxGenerations

Default Configuration

These following configuration will be assigned by default. Any settings defined by the user will override the given settings specified in these defaults.

{
"Accept Rule": "Greedy",
"Best Ever Value": -Infinity,
"Best Sample Index": 0,
"Candidate Population": [
    []
],
"Crossover Rate": 0.9,
"Current Best Variables": [],
"Current Mean": [],
"Current Minimum Step Size": 0.0,
"Fix Infeasible": true,
"Infeasible Sample Count": 0,
"Max Distances": [],
"Model Evaluation Count": 0,
"Mutation Rate": 0.5,
"Mutation Rule": "Fixed",
"Normal Generator": {
    "Mean": 0.0,
    "Standard Deviation": 1.0,
    "Type": "Univariate/Normal"
    },
"Parent Selection Rule": "Random",
"Population Size": 200,
"Previous Best Ever Value": -Infinity,
"Previous Mean": [],
"Previous Value Vector": [],
"Sample Population": [
    []
],
"Termination Criteria": {
    "Max Generations": 10000000000,
    "Max Infeasible Resamplings": 10000000,
    "Max Model Evaluations": 1000000000,
    "Max Value": Infinity,
    "Min Step Size": -Infinity,
    "Min Value": -Infinity,
    "Min Value Difference Threshold": -Infinity
    },
"Uniform Generator": {
    "Maximum": 1.0,
    "Minimum": 0.0,
    "Type": "Univariate/Uniform"
    },
"Value Vector": [],
"Variable Count": 0
}

Variable Defaults

These following configuration will be assigned to each of the experiment variables by default. Any settings defined by the user will override the given settings specified in these defaults.

{
"Initial Mean": NaN,
"Initial Standard Deviation": NaN,
"Initial Value": NaN,
"Lower Bound": -Infinity,
"Minimum Standard Deviation Update": 0.0,
"Upper Bound": Infinity,
"Values": []
}