Parameter Spaces

Parameter spaces in Evolver define the whole set of parameters that can be configured in an automatic way for base-level metaheuristics. Parameters can be categorical, such as the crossover operator in evolutionary algorithms, or numerical, such as the mutation probability (double parameter) or the offspring population size (integer parameter).

This section describes the structure of a parameter space and how they can be defined in YAML files. At the end of this section, we will show an alternartive way to define parameter spaces programatically.

Parameters in Evolver

A parameter is defined by: - A unique name - A type (integer, double, categorical) - A definition of valid values - Relationships with other parameters (conditional parameters and global sub-parameters)

By convention, the name of a parameter should be self-explanatory and defined in camel case such as, for example, offspringPopulationSize or mutationProbability.

Numeric parameter types (integer and double) define a range of valid values using the range attribute, which is an inclusive range:

neighborhoodSize:
  type: integer
  range: [5, 50]  # Inclusive range

laplaceCrossoverScale:
  type: double
  range: [0.1, 1.5] # Inclusive range

Categorical parameters define a set of valid values using the values attribute, and can be defined in two ways:

createInitialSolutions:
  type: categorical
  values:
    default: {}
    latinHypercubeSampling: {}
    scatterSearch: {}

offspringPopulationSize:
  type: categorical
  values: [1, 2, 5, 10, 20, 50, 100, 200, 400]

The first option is useful when the parameter can have conditional parameters. If this is not the case, the second option is more compact and concise.

Conditional Parameters

In the parameter space, a parameter can have conditional parameters. Conditional parameters are parameters that only apply when a parent categorical parameter has a specific value.

Let’s consider the following example to illustrate this concept:

algorithmResult:
  type: categorical
  values:
    population: {}
    externalArchive:
      conditionalParameters:
        populationSizeWithArchive:
          type: integer
          range: [10, 200]
        archiveType:
          type: categorical
          values:
            crowdingDistanceArchive: {}
            unboundedArchive: {}

The algorithmResult parameter is a categorical parameter that can take two values: population or externalArchive. If the value is population, then the populationSizeWithArchive parameter is not considered. If the value is externalArchive, then the populationSizeWithArchive and archiveType parameters are considered. The archiveType parameter is a categorical parameter that can take two values: crowdingDistanceArchive or unboundedArchive.

Global Sub-Parameters

Besides conditional parameters, a categorical parameter can have also global sub-parameters. Global sub-parameters are parameters that always apply, regardless of other parameter values. Let’s take a look to the next example:

crossover:
  type: categorical
  globalSubParameters:
    crossoverProbability:
      type: double
      range: [0.0, 1.0]
    crossoverRepairStrategy:
      type: categorical
      values: [random, round, bounds]
  values:
    SBX:
      conditionalParameters:
        sbxDistributionIndex:
          type: double
          range: [5.0, 400.0]
      conditionalParameters:
    blxAlphaCrossoverAlpha:
          type: double
          range: [0.0, 1.0]
    wholeArithmetic: {}

The crossover parameter is a categorical parameter that can take three values: SBX, blxAlpha, or wholeArithmetic. In contrast to conditional parameters, global sub-parameters always applies. In the example, any crossover has a crossoverProbability and crossoverRepairStrategy parameter. We can see that the SBX``and ``blxAlpha crossovers have a sbxDistributionIndex and blxAlphaCrossoverAlpha parameter, respectively, while the wholeArithmetic crossover does not have these parameters.

First-Level Parameters in a Parameter Space

The first-level parameters in a parameter space are the root nodes of a hierarchy, and they do not have parents. The rest of parameters of the parameter space are children of these first-level parameters, which can be either conditional or global sub-parameters.

If we take a look to the parameter space for NSGA-II for double problems, we can observe that the number of first-level parameters is five:

• algorithmResult

• createInitialSolutions

• offspringPopulationSize

• variation

• selection

However, the first-level parameters of the base-level MOEA/D parameter space are eight:

• neighborhoodSize

• maximumNumberOfReplacedSolutions

• aggregationFunction

• algorithmResult

• createInitialSolutions

• subProblemIdGenerator

• variation

• selection

For more examples, see the parameterSpaces directory in the source code.

Implementation Details

The parameter space functionality in Evolver is implemented through the abstract ParameterSpace class, which provides a framework for managing algorithm parameters in a hierarchical structure. This class is a key component in Evolver’s configuration system.

Here’s the basic structure of the ParameterSpace class with its key method signatures:

public abstract class ParameterSpace {
    // Contains all parameters in the parameter space, stored by parameter name
    // This includes both top-level and nested parameters
    protected final Map<String, Parameter<?>> parameterSpace;

    // Contains only the top-level parameters that serve as entry points
    // These parameters are also included in the parameterSpace map
    protected final List<Parameter<?>> topLevelParameters;

    public ParameterSpace() { ... }

    public void put(Parameter<?> parameter) { ... }

    public Parameter<?> get(String parameterName) { ... }

    public Map<String, Parameter<?>> parameters() { ... }

    public List<Parameter<?>> topLevelParameters() { ... }

    public void addTopLevelParameter(Parameter<?> parameter) { ... }

    public abstract ParameterSpace createInstance();
}

Key Features

• Parameter Storage: Maintains a map of parameters for easy access by name

• Hierarchical Structure: Supports top-level parameters that serve as entry points for configurations

• Type Safety: Uses Java generics to ensure type safety for parameter values

• Immutable Views: Provides unmodifiable views of parameters and top-level parameter lists

Core Components

1. Parameter Storage - Uses a Map<String, Parameter<?>> to store all parameters by name - Contains both top-level and nested parameters in a flattened structure - Provides type-safe access to any parameter through the get() method - Maintains a one-to-one mapping between parameter names and parameter objects

2. Top-Level Parameters - Maintains an ordered list of top-level parameters via topLevelParameters - These parameters serve as the main entry points for algorithm configuration - Each top-level parameter is also included in the main parameterSpace map - Can be accessed via the topLevelParameters() method

3. Parameter Management - put(Parameter<?> parameter): Adds a parameter to the parameter space - get(String parameterName): Retrieves a parameter by name - parameters(): Returns an unmodifiable view of all parameters

4. Abstract Factory Method - createInstance(): Abstract method that subclasses must implement to create and configure the parameter space

Usage Example

// Create a parameter space instance
ParameterSpace parameterSpace = new MyAlgorithmParameterSpace();

// Access a specific parameter
Parameter<?> populationSize = parameterSpace.get("populationSize");

// Get all top-level parameters
List<Parameter<?>> mainParameters = parameterSpace.topLevelParameters();

Encoding-Specific Parameter Spaces: NSGA-II Case Study

Most algorithms are available for several encodings (see Base-Level Metaheuristics), and each encoding needs its own operators: SBX or BLX-alpha make sense for continuous problems, HUX or bit-flip for binary ones, PMX or swap for permutations. Evolver handles this with one YAML file per algorithm and encoding, all sharing the same top-level structure, together with a parameter factory for that encoding.

For NSGA-II, the three parameter spaces are NSGAIIDouble.yaml, NSGAIIBinary.yaml and NSGAIIPermutation.yaml (in src/main/resources/parameterSpaces/). All of them declare the same top-level parameters (algorithmResult, createInitialSolutions, offspringPopulationSize, variation and selection); they differ in the operators the variation parameter can choose from:

Encoding	crossover values	mutation values
Double	SBX, blxAlpha, wholeArithmetic, PCX, …	polynomial, uniform, linkedPolynomial, nonUniform, …
Binary	HUX, uniform, singlePoint	bitFlip
Permutation	PMX, OXD, CX	swap, insert, scramble, inversion, simpleInversion, displacement

The YAML file only states which values a parameter can take. The parameter factory turns each categorical parameter into the class that knows how to build the corresponding jMetal component: DoubleParameterFactory, BinaryParameterFactory and PermutationParameterFactory (in org.uma.evolver.parameter.factory) map, for instance, crossover to DoubleCrossoverParameter, BinaryCrossoverParameter or PermutationCrossoverParameter. The algorithm class for each encoding (DoubleNSGAII, BinaryNSGAII, PermutationNSGAII) then assembles the algorithm from those parameters:

var parameterSpace =
    new YAMLParameterSpace("NSGAIIPermutation.yaml", new PermutationParameterFactory());
var nsgaii = new PermutationNSGAII(problem, 100, 25000, parameterSpace);
nsgaii.parse(configuration);   // e.g. "--crossover PMX --mutation swap ..."
var algorithm = nsgaii.build();

Adding an operator to an existing encoding therefore means adding its value (and any conditional sub-parameters) to the YAML file and, if it is new to Evolver, supporting it in the corresponding *CrossoverParameter or *MutationParameter class. Restricting the search space, e.g. to tune NSGA-II with SBX only, just needs a YAML file with fewer values, as NSGAIIDoubleReduced.yaml does.

Parameter spaces can still be built programmatically by subclassing ParameterSpace (see Implementation Details above), but every parameter space shipped with Evolver is defined in YAML.