(μ+1)-Evolution Strategy

(μ+1)-Evolution Strategy #

Name #

(μ+1)-Evolution Strategy, (μ+1)-ES

Taxonomy #

The (μ+1)-Evolution Strategy is a stochastic optimization algorithm belonging to the field of Evolutionary Computation, a subfield of Computational Intelligence. It is closely related to other Evolution Strategies, such as (1+1)-ES and (μ+λ)-ES.

  • Computational Intelligence
    • Biologically Inspired Computation
      • Evolutionary Computation
        • Evolutionary Algorithms
          • Evolution Strategies
            • (μ+1)-Evolution Strategy

Strategy #

The (μ+1)-Evolution Strategy is a population-based optimization technique that maintains a population of μ individuals, each representing a candidate solution to the problem at hand. The algorithm iteratively generates new offspring by applying mutation to a single parent, selected uniformly at random from the population. The mutation operator perturbs the parent’s decision variables, typically by adding a normally distributed random value to each variable. The resulting offspring is then evaluated using a fitness function, which measures its quality as a solution to the problem.

After the offspring is generated and evaluated, the algorithm performs a selection step to determine which individuals will survive to the next generation. In the (μ+1)-ES, the population for the next generation is selected from the union of the current population and the newly generated offspring. The best μ individuals, as determined by their fitness values, are retained, while the worst individual is discarded. This selection mechanism ensures that the population size remains constant at μ throughout the optimization process.

The (μ+1)-ES continues to iterate, generating new offspring and performing selection, until a termination criterion is met. Common termination criteria include reaching a maximum number of generations, finding a solution of satisfactory quality, or observing convergence in the population.

Procedure #

Data Structures #

  • Individual: A structure representing a candidate solution, which consists of:
    • Object Variables: An array of real-valued object variables.
    • Strategy Parameters: An array of real-valued strategy parameters (mutation step sizes).
    • Fitness: The fitness value of the individual.
  • Population: An array of individuals.
  • Offspring: A single individual generated by mutating a parent.
  • Best Individual: The individual with the best fitness value found so far.

Parameters #

  • μ (mu): The number of parent individuals in the population.
  • Initial Step Size: The initial value for the strategy parameters (mutation step sizes).
  • Termination Criterion: The condition for terminating the algorithm, such as reaching a maximum number of iterations or achieving a satisfactory fitness value.

Steps #

  1. Initialize the population
    1. For each individual in the population (μ individuals):
      1. Randomly initialize the object variables.
      2. Set the strategy parameters to the initial step size.
      3. Evaluate the fitness of the individual.
    2. Update the best individual if necessary.
  2. While the termination criterion is not met:
    1. Select a parent individual
      1. Randomly select one individual from the population.
    2. Create an offspring by mutating the parent
      1. Copy the object variables and strategy parameters from the parent to the offspring.
      2. Mutate the strategy parameters of the offspring.
        1. For each strategy parameter:
          1. Multiply the strategy parameter by a random factor drawn from a lognormal distribution.
      3. Mutate the object variables of the offspring.
        1. For each object variable:
          1. Add a random value drawn from a normal distribution with mean 0 and standard deviation equal to the corresponding mutated strategy parameter.
      4. Evaluate the fitness of the offspring.
    3. Select the survival individual
      1. Compare the fitness of the offspring with the fitness of the parent.
      2. If the offspring has a better (or equal) fitness than the parent:
        1. Replace the parent with the offspring in the population.
      3. Otherwise:
        1. Discard the offspring.
    4. Update the best individual if necessary.
  3. Return the best individual found.

Considerations #

Advantages #

  • Simplicity: The (μ+1)-ES is easy to understand and implement, making it a good choice for practitioners new to Evolutionary Computation.
  • Robustness: The algorithm can handle noisy and multimodal fitness landscapes, as well as problems with non-differentiable or discontinuous objective functions.
  • Parallelization: The fitness evaluations of the population can be easily parallelized, allowing for efficient use of computational resources.

Disadvantages #

  • Limited Exploration: The (μ+1)-ES relies on a single offspring per generation, which may limit its ability to explore the search space effectively, especially in high-dimensional problems.
  • Slow Convergence: The algorithm may converge slowly, particularly in the later stages of the optimization process, as it relies on small, random perturbations to improve the solution quality.
  • Parameter Sensitivity: The performance of the (μ+1)-ES can be sensitive to the choice of the population size (μ) and the mutation operator, requiring careful tuning for each problem.

Heuristics #

Population Size #

  • Start with a moderate population size (e.g., μ = 10) and adjust based on the problem complexity and available computational resources.
  • Larger population sizes can improve exploration but may slow down convergence.
  • Smaller population sizes can lead to faster convergence but may increase the risk of premature convergence to suboptimal solutions.

Mutation Operator #

  • Use a normally distributed random perturbation with zero mean and a problem-dependent standard deviation.
  • Adapt the mutation step size during the optimization process, e.g., by using a self-adaptive strategy or a deterministic schedule.
  • Consider using correlated mutations or other advanced mutation schemes for high-dimensional problems or problems with strong variable interactions.

Termination Criterion #

  • Set a maximum number of generations based on the available computational budget and the problem complexity.
  • Monitor the progress of the best fitness value and stop the algorithm if no significant improvement is observed over a predefined number of generations.
  • Use a convergence criterion based on the diversity of the population, e.g., stop when the variance of the fitness values falls below a threshold.

Hybridization #

  • Consider combining the (μ+1)-ES with local search techniques, such as hill climbing or pattern search, to improve the exploitation of promising regions in the search space.
  • Incorporate domain-specific knowledge or heuristics into the mutation operator or the fitness function to guide the search process more effectively.