Crossover

Simulated Binary Crossover (‘real_sbx’, ‘int_sbx’)

Details about the crossover can be found in [35]. Real values can be represented by a binary notation and then a the point crossovers can be performed. SBX simulated this operation by using a probability distribution simulating the binary crossover.

A crossover object can be created by

[1]:
from pymoo.factory import get_crossover

crossover = get_crossover("real_sbx", prob=0.9, eta=20)

As arguments, the probability of a crossover and the eta parameter can be provided.

In the example below, we demonstrate a crossover in an optimization problem with only one variable. A crossover is performed between two points, 0.2 and 0.8, and the resulting exponential distribution is visualized. Depending on the eta_cross, the exponential distribution can be fine-tuned.

The probability of SBX follows an exponential distribution. Please note for demonstration purposes, we have set prob_per_variable=1.0, which means every variable participates in the crossover (necessary because there exists only one variable). However, it is suggested to perform a crossover of two variables forms each parent with a probability of 0.5, which is defined by default if not defined otherwise.

[2]:
from pymoo.interface import crossover
import numpy as np
import matplotlib.pyplot as plt

def show(eta_cross):
    a,b = np.full((5000, 1), 0.2), np.full((5000, 1), 0.8)
    off = crossover(get_crossover("real_sbx", prob=1.0, eta=eta_cross, prob_per_variable=1.0), a, b)

    plt.hist(off, range=(0,1), bins=200, density=True, color="red")
    plt.show()

show(1)
../_images/operators_crossover_6_0.png
[3]:
show(30)
../_images/operators_crossover_7_0.png

Also, it can be used for integer variables. The bounds are slightly modified, and after doing the crossover, the variables are rounded.

[4]:
from pymoo.factory import get_crossover
from pymoo.interface import crossover
import numpy as np
import matplotlib.pyplot as plt

def show(eta_cross):
    a,b = np.full((50000, 1), -10), np.full((50000, 1), +10)
    off = crossover(get_crossover("int_sbx", prob=1.0, eta=eta_cross, prob_per_variable=1.0), a, b, xl=-20, xu=+20)
    val, count = np.unique(off, return_counts=True)
    #print(np.column_stack([val, count / count.sum()]))
    plt.hist(off, range=(-20, 20), bins=41, density=True, color="red")
    plt.show()

show(3)
../_images/operators_crossover_9_0.png

Point Crossover (‘real_point’, ‘bin_point’, ‘int_point’ )

The point crossover is mostly applied to binary optimization problems. However, in general, it can be used for other variable representations.

The point crossover can be initiated by

[5]:
crossover = get_crossover("real_k_point", n_points=2)

For any number of points that are desired. Additionally, for convenience the single- or two-point crossover is created by

[6]:
get_crossover("real_one_point")
get_crossover("real_two_point")
[6]:
<pymoo.operators.crossover.pntx.PointCrossover at 0x7f1bb6444970>

directly.

[7]:
from pymoo.interface import crossover
from pymoo.factory import get_crossover
import numpy as np
import matplotlib.pyplot as plt

def example_parents(n_matings, n_var):
    a = np.arange(n_var)[None, :].repeat(n_matings, axis=0)
    b = a + n_var
    return a, b


def show(M):
    plt.figure(figsize=(4,4))
    plt.imshow(M, cmap='Greys',  interpolation='nearest')
    plt.xlabel("Variables")
    plt.ylabel("Individuals")
    plt.show()

n_matings, n_var = 100, 100
a,b = example_parents(n_matings,n_var)

print("One Point Crossover")
off = crossover(get_crossover("bin_one_point"), a, b)
show((off[:n_matings] != a[0]))

print("Two Point Crossover")
off = crossover(get_crossover("bin_two_point"), a, b)
show((off[:n_matings] != a[0]))

print("K Point Crossover (k=4)")
off = crossover(get_crossover("bin_k_point", n_points=4), a, b)
show((off[:n_matings] != a[0]))
One Point Crossover
../_images/operators_crossover_17_1.png
Two Point Crossover
../_images/operators_crossover_17_3.png
K Point Crossover (k=4)
../_images/operators_crossover_17_5.png

Uniform Crossover (‘real_ux’, ‘bin_ux’, ‘int_ux’)

The uniform crossover takes with a probability of 0.5 the values from each parent. In contrast to a point crossover, not a sequence of variables is taken, but random indices.

[8]:
off = crossover(get_crossover("bin_ux"), a, b)
show((off[:n_matings] != a[0]))
../_images/operators_crossover_21_0.png

Half Uniform Crossover (‘bin_hux’, ‘int_hux’)

The half uniform crossover will first determine what indices are different in the first and the second parent. Then, it will take half of the difference to be selected from the other parent.

[9]:
_a = np.full((100,100), False)
_b = np.copy(_a)
_b[:, np.linspace(5, 95, 10).astype(int)] = True

print("Here, a and b are different for indices: ", np.where(_a[0] != _b[0])[0])

off = crossover(get_crossover("bin_hux"), _a, _b)
show((off[:100] != _a[0]))

diff_a_to_b = (_a != _b).sum()
diff_a_to_off = (_a != off[:100]).sum()

print("Difference in bits (a to b): ", diff_a_to_b)
print("Difference in bits (a to off): ", diff_a_to_off)

print("Crossover Rate: ", diff_a_to_off / diff_a_to_b)


Here, a and b are different for indices:  [ 5 15 25 35 45 55 65 75 85 95]
../_images/operators_crossover_25_1.png
Difference in bits (a to b):  1000
Difference in bits (a to off):  450
Crossover Rate:  0.45

Exponential Crossover (‘real_exp’, ‘bin_exp’, ‘int_exp’)

The exponential crossover is mostly a one-point crossover, but occasionally it can be a two-point crossover. First, randomly a starting index is chosen. Then, we add the next variable to be mutated with a specific probability. If we reach the last variable, we continue with the first (wrap around).

[10]:
off = crossover(get_crossover("real_exp", prob=0.95), a, b)
show((off[:n_matings] != a[0]))
../_images/operators_crossover_29_0.png

Differential Crossover (‘real_de’)

The differential crossover is used in the DE. It adds the difference of two individuals to another one.

It can be initiated by

[11]:
crossover = get_crossover("real_de")

In the following, the different creating of donor vectors is shown. The difference between \(x_{\pi_2} - x_{\pi_3}\) is added with different weights \(F \in (0, 1)\) to \(x_{\pi_1}\). The resulting donor solution can be used for further evolutionary recombinations (for example, DE uses it for another crossover).

[12]:
from pymoo.factory import get_crossover
from pymoo.interface import crossover
import numpy as np
import matplotlib.pyplot as plt

c = np.array([[0.8, 0.2]])
a = np.array([[0.4, 0.4]])
b = np.array([[0.6, 0.5]])


X = crossover(get_crossover("real_de", CR=0.5, dither='vector'),
              a.repeat(100, axis=0), b.repeat(100, axis=0), c.repeat(100, axis=0))

plt.scatter(X[:, 0], X[:, 1], s=20,facecolors='none', edgecolors='r', label="v")
plt.scatter(a[:, 0], a[:, 1], label="$x_{\pi_1}$", marker="X", color="blue")
plt.scatter(b[:, 0], b[:, 1], label="$x_{\pi_2}$", marker="X", color="green")
plt.scatter(c[:, 0], c[:, 1], label="$x_{\pi_3}$", marker="X", color="black")

plt.xlim(0, 1)
plt.ylim(0, 1)
plt.legend()
plt.show()
../_images/operators_crossover_35_0.png

API

pymoo.factory.get_crossover(name, kwargs)

A convenience method to get a crossover object just by providing a string.

Parameters
name{ ‘real_sbx’, ‘int_sbx’, ‘real_de’, ‘real_pcx’, ‘(real|bin|int)_ux’, ‘(bin|int)_hux’, ‘(real|bin|int)_exp’, ‘(real|bin|int)_one_point’, ‘(real|bin|int)_two_point’, ‘(real|bin|int)_k_point’, ‘perm_ox’, ‘perm_erx’ }

Name of the crossover.

kwargsdict

Dictionary that should be used to call the method mapped to the crossover factory function.

Returns
classCrossover

An crossover object based on the string. None if the crossover was not found.

pymoo.core.crossover.Crossover(n_parents, n_offsprings, prob=0.9)

The crossover combines parents to offsprings. Some crossover are problem specific and use additional information. This class must be inherited from to provide a crossover method to an algorithm.