Algorithms - Shuffled Complex Evolution (SCE)

The OSTRICH shuffled complex evolution optimization algorithm

Initial Publication:

Modified:

The following optional group will configure the shuffled complex evolution (SCE) algorithm and will be processed if [ProgramType] is set to “ShuffledComplexEvolution”.

BeginSCEUA
Budget                  [MAXN]
LoopStagnationCriteria  [KSTOP]
PctChangeCriteria       [PCENTO]
PopConvCriteria         [PEPS]              
NumComplexes            [NGS]
NumPointsPerComplex     [NPG]
NumPointsPerSubComplex  [NPS]
NumEvolutionSteps       [NSPL]
MinNumberOfCOmplexes    [MINGS]
UseInitialPoint         [INIFLG]
EndSCEUA
BeginSCEUA
Budget                  10000
LoopStagnationCriteria  5
PctChangeCriteria       0.01
PopConvCriteria         0.001
NumComplexes            3
NumPointsPerComplex     19
NumPointsPerSubComplex  10
NumEvolutionSteps       19
MinNumberOfCOmplexes    3
UseInitialPoint         no
EndSCEUA

Figure 1: General Format (left) and Example (right) of the SCE Group

Where BeginSCEUA and EndSCEUA are parsing tags that wrap a set of algorithm configuration variables. These variables are described below and descriptions are based on comments within the FORTRAN implementation provided by Duan et al. (1993). The corresponding variable names used in the FORTRAN implementation are provided in brackets (‘[’ and ‘]’) in the general format of Figure 1.

  • LoopStagnationCriteria (KSTOP): Number of shuffling loops in which the optimization criterion must improve by the specified percentage or else optimization will be restarted.
  • PctChangeCriteria (PCENTO): Percentage by which the optimization criterion value must change in the specified number of shuffling loops or else optimization is restarted. Use decimal equivalent: Percentage/100. Recommended value: 0.01.
  • PopConvCriteria (PEPS): The optimization will be restarted if the shuffling and/or evolution process results in a population that is entirely within PEPS×100 percent of the feasible space. The default value is 0.001.
  • NumComplexes (NGS): Number of complexes used for optimization search. Minimum value is 1. Recommended value is between 2 and 20 depending on the number of parameters to be optimized and on the degree of difficulty of the problem. If not specified OSTRICH will use the following calculation: NGS = sqrt(np) , where np is the number of parameters.
  • NumPointsPerComplex (NPG): The number of points in each complex. NPG should be greater than or equal to 2. The default value is: NPG = 2 × np + 1.
  • NumPointsPerSubComplex (NPS): The number of points in each sub-complex. NPS should be greater than or equal to 2 and less than NPG. The default value is: NPS = np + 1.
  • NumEvolutionSteps (NSPL): The number of evolution steps taken by each complex before next shuffling. The default value is: NSPL = 2 × np +1.
  • MinNumberOfComplexes (MINGS): Minimum number of complexes required for optimization search, if the number of complexes is allowed to reduce as the optimization search proceeds. The default value is: MINGS = sqrt(np).
  • UseInitialPoint (INIFLG): Flag on whether to include an initial point in the starting population. Enter “yes” if the initial point is to be included. The default value is “no”.

References

Deb, K. 2001. Multi-objective optimization using evolutionary algorithms. John Wiley & Sons, Chichester, UK.

Duan, Q., Sorooshian, S.,Gupta, V. K. 1992. Effective and efficient global optimization for conceptual rainfall-runoff models. Water Resources Research 28, 1015– 1031.

Duan, Q., Gupta, V. K.,Sorooshian, S. 1993. A shuffled complex evolution approach for effective and efficient global minimization. Journal of Optimization Theory and Applications 76, 501– 521.