Operators

Author:

Antonio J. Nebro

Date:

2025-07-07

Operators are the building blocks of evolutionary algorithms in jMetal. Each operator is a function typically applied to one or more solutions, producing one or more new solutions. The source and result are typically a solution or a list of solutions, depending on the operator.

Operator Types

jMetal provides four main types of operators:

  1. Crossover: Recombines parent solutions to produce offspring solutions.

  2. Mutation: Modifies a single solution to introduce diversity.

  3. Selection: Chooses solutions from a population based on some criteria.

  4. Local Search: Applies local search techniques to improve solutions.

Crossover Operators

Crossover operators combine genetic information from parent solutions to create new offspring solutions.

For Double Solutions

  • SBXCrossover: Simulated Binary Crossover with polynomial distribution.

  • BLXAlphaCrossover: Blend Crossover with alpha parameter.

  • BLXAlphaBetaCrossover: Extended BLX with separate alpha and beta parameters.

  • DifferentialEvolutionCrossover: Used in Differential Evolution algorithms.

  • ArithmeticCrossover: Weighted arithmetic mean of parent solutions.

  • LaplaceCrossover: Based on Laplace distribution.

  • WholeArithmeticCrossover: Uses all parents in arithmetic recombination.

  • FuzzyRecombinationCrossover: Implements fuzzy recombination.

  • UnimodalNormalDistributionCrossover: Uses unimodal normal distribution.

The SBX (Simulated Binary Crossover) operator generates offspring around the parents following a distribution controlled by the distribution index: a larger index keeps the offspring closer to the parents, a smaller one spreads them out:

_images/sbx_crossover.png

Offspring distribution produced by SBX for two distribution indices.

The BLX-αβ (Blend) crossover draws offspring uniformly from an interval that extends beyond the parents, asymmetrically: by α·d below the smaller parent and β·d above the larger one, where d is the distance between parents:

_images/blx_alpha_beta_crossover.png

Sampling interval and (uniform) offspring distribution of BLX-αβ.

For Integer Solutions

  • IntegerSBXCrossover: Integer version of SBX.

  • IntegerPolynomialCrossover: Polynomial crossover.

For Binary Solutions

  • HUXCrossover: Half Uniform Crossover.

  • SinglePointCrossover: One-point crossover.

  • TwoPointCrossover: Two-point crossover.

  • NPointCrossover: General N-point crossover.

  • UniformCrossover: Random bit selection from parents.

The single-point crossover chooses a crossover point and swaps the bits from that point onwards between the two parents, producing two children:

_images/single_point_crossover.png

Single-point crossover on binary strings.

For Permutation Solutions

  • PMXCrossover: Partially Mapped Crossover.

  • CycleCrossover: Preserves absolute positions.

  • PositionBasedCrossover: Preserves relative ordering.

  • OXDCrossover: Order-based crossover.

  • EdgeRecombinationCrossover: Preserves adjacency information.

The PMX (Partially Mapped Crossover) operator exchanges the segment between two random cut points and then repairs the offspring, following the mapping defined by the exchanged segment, so that each child remains a valid permutation:

_images/pmx_crossover.png

PMX crossover step by step (Goldberg and Lingle, 1985).

Mutation Operators

Mutation operators introduce random changes to solutions to maintain diversity.

For Double Solutions (Mutation)

  • PolynomialMutation: Polynomial mutation.

  • NonUniformMutation: Strength decreases over time.

  • UniformMutation: Random mutation within bounds.

  • LevyFlightMutation: Uses Lévy flights.

  • PowerLawMutation: Based on power law distribution.

  • SimpleRandomMutation: Uniform random mutation.

The polynomial mutation operator perturbs a variable around its current value following a polynomial distribution controlled by the distribution index: a larger index produces smaller perturbations, a smaller one larger ones:

_images/polynomial_mutation.png

Distribution of the mutated value produced by polynomial mutation for two distribution indices.

The Lévy flight mutation perturbs a variable with a heavy-tailed step generated by Mantegna’s algorithm: mostly small steps with occasional large jumps, which helps escape local optima:

_images/levy_flight_mutation.png

A realization of Lévy steps and the resulting heavy-tailed distribution of the mutated value (compared with a Gaussian).

The uniform mutation replaces a variable with a value drawn uniformly from a window of fixed width (the perturbation parameter) centred on the current value:

_images/uniform_mutation.png

Distribution of the mutated value produced by uniform mutation for two perturbation widths.

The power-law mutation perturbs a variable with a power-distributed strength and chooses the direction from the variable’s relative position, so the perturbation stays within the bounds and is symmetric in the interior of the range:

_images/power_law_mutation.png

Distribution of the mutated value produced by power-law mutation for two exponents.

For Integer Solutions (Mutation)

  • IntegerPolynomialMutation: Integer version of polynomial mutation.

  • SimpleRandomMutation: Random perturbation of values.

For Binary Solutions (Mutation)

  • BitFlipMutation: Flips each bit with given probability.

The bit-flip mutation inverts each bit independently with probability p (typically 1 / number_of_bits):

_images/bit_flip_mutation.png

Bit-flip mutation on a binary string.

For Permutation Solutions (Mutation)

  • SwapMutation: Swaps two elements.

  • InsertMutation: Moves element to new position.

  • ScrambleMutation: Reorders subsequence.

  • InversionMutation: Inverts subsequence order.

  • DisplacementMutation: Moves subsequence.

  • SimpleInversionMutation: Inverts two elements.

The swap mutation picks two distinct random positions and exchanges their elements, which always yields a valid permutation:

_images/permutation_swap_mutation.png

Swap mutation on a permutation.

Selection Operators

  • BinaryTournamentSelection: Better of two random solutions.

  • NaryTournamentSelection: Best of N random solutions.

  • RankingAndCrowdingSelection: NSGA-II selection.

  • RandomSelection: Uniform random selection.

  • BestSolutionSelection: Best in population.

  • RouletteWheelSelection: Fitness-proportional.

  • StochasticUniversalSampling: Improved roulette wheel.

Local Search Operators

  • BasicLocalSearch: Improves solutions locally.

Using Operators in jMetal

Example of creating and using a crossover operator:

// Create a SBX crossover operator with probability 0.9 and distribution index 20.0
double crossoverProbability = 0.9;
double distributionIndex = 20.0;
CrossoverOperator<DoubleSolution> crossover = new SBXCrossover(crossoverProbability, distributionIndex);

// Apply crossover to two parent solutions
List<DoubleSolution> parents = new ArrayList<>();
parents.add(parent1);
parents.add(parent2);
List<DoubleSolution> offspring = crossover.execute(parents);

Example of creating and using a mutation operator:

// Create a polynomial mutation operator with probability 0.1 and distribution index 20.0
double mutationProbability = 0.1;
double distributionIndex = 20.0;
MutationOperator<DoubleSolution> mutation = new PolynomialMutation(mutationProbability, distributionIndex);

// Apply mutation to a solution
DoubleSolution mutatedSolution = mutation.execute(solution);

Choosing the Right Operator

The choice of operators depends on several factors:

  1. Solution Encoding: Match the operator to your solution representation.

  2. Problem Characteristics: Some operators work better for certain problems.

  3. Diversity vs. Intensification: Balance exploration and exploitation.

  4. Computational Cost: Consider the complexity of the operator.