Simulated Binary Crossover Always Exchanges Variables in Certain Case

[electronsandstuff]

Thanks for putting together a nice optimization package in python! I have been using it in my research for a little while now.

This issues concerns an observation I made while making plots of pymoo's simulated binary crossover implementation. I noticed that in the specific case where the decision variable of parent 1 is greater than the decision variable of parent 2, the two variables will show up exchanged in the children even when the exchange probability (prob_bin) is set to zero (if they also experience crossover).

I believe this comes from the following implementation detail in pymoo/operators/crossover/sbx.py where decision variables are broken up into the smaller and larger value.

# assign y1 the smaller and y2 the larger value
y1 = np.min(X, axis=0)[cross]
y2 = np.max(X, axis=0)[cross]

If I understand the code which follows, each decision variable in the first child (masked by cross) will be closest to the smaller of the two values in parent 1 and parent 2. This means that the decision variables are always exchanged in the case that cross is true and the value of parent 1's variable is larger than that of parent 2.

I noticed this while making some figures of the distribution of the crossover operator's output for two fixed decision variables. Here are the results when parent 2 has the larger value. It is as you would expect.

Here it is with parent 1 having the larger value for the decision variable.

With a 50% crossover rate and 0% exchange rate, you can see the non-crossed over individuals and that the crossed over individuals are also always swapped.

Here is the code I used to generate these plots.

import numpy as np
import matplotlib.pyplot as plt
from pymoo.operators.crossover.sbx import cross_sbx
from pymoo.core.variable import get

# Experiment settings
num_vars = 512
num_individuals = 10240
loc1 = 0.5
loc2 = -0.5
eta = 20
prob_var = 0.5
prob_bin = 0
        
# Create subplots for visualization
fig, axs = plt.subplots(1, 1)
fig.suptitle(f'Simulated Binary Crossover, loc=({loc1}, {loc2})', fontsize=16)

# Define bounds (all variables between -1 and 1)
bounds = np.array([[-1.0] * num_vars, [1.0] * num_vars])

# Generate initial population
population1 = np.full((num_individuals, num_vars), loc1)
population2 = np.full((num_individuals, num_vars), loc2)

# Perform crossover
eta, prob_var, prob_exch, prob_bin = get(eta, prob_var, prob_bin, prob_bin,
                                            size=(1, 1))
poly_mutated_pymoo = np.array([cross_sbx(
    np.vstack((ind1, ind2))[:, None, :], 
    bounds[0], 
    bounds[1], 
    eta, 
    prob_var, 
    prob_exch) for ind1, ind2 in zip(population1, population2)])

# Original distribution
plt.hist(poly_mutated_pymoo[:, 0].ravel(), bins=128, alpha=0.5, label="Child 1")
plt.hist(poly_mutated_pymoo[:, 1].ravel(), bins=128, alpha=0.5, label="Child 2")
plt.axvline(loc1, c='k', ls=':')
plt.axvline(loc2, c='k', ls=':')

plt.axvline(-1, c='r')
plt.axvline(1, c='r')

plt.xlabel('Value')
plt.ylabel('Frequency')
plt.legend()

I thought it would be a good idea to bring this to your attention. A simple fix would be to exchange the decision vars in c1 and c2 according to the array X[cross, 0] > X[cross, 1] around line 62 in pymoo/operators/crossover/sbx.py.

[blankjul]

Thanks for looking into to this!

Can you benchmark against the origal implementation? It is available here: https://www.egr.msu.edu/~kdeb/codes.shtml

This is what the implementation in pymoo is also based on (but vectorized). Let us double check both implementation and see if your concern remain.

You want to check the crossover.c file. The code segment you are referring to is this:

if (parent1->xreal[i] < parent2->xreal[i])
{
    y1 = parent1->xreal[i];
    y2 = parent2->xreal[i];
}
else
{
    y1 = parent2->xreal[i];
    y2 = parent1->xreal[i];
}

[blankjul]

Do you still have any concern about the implementation of SBX in pymoo?

[electronsandstuff]

I checked out the c implementation and it looks like the pymoo version is a nice translation of it to python!

The only detail I noticed was that the exchange probability is hard-coded at 50% in the c version. This means the case I saw (parents are exchanged when exchange probability is set to zero) will never show up. It's a tiny detail that likely does not matter.

If you are interested in changing it, however, I can suggest a one line fix which I just posted as a draft PR in #730. When the exchanges happen at the end, this code checks what was original swapped due to the values of the individuals and adds the operation to unswap them. Here is the same figure as above for the modified code.

The crossed over individuals now do not swap by default.