Two-Dimensional Bin Packing Problem with Multiple Constraints — Code Analysis for Finding the Optimal Layout of Cairo Ramen Shop (IV): Crossover Operator Analysis

Crossover Operators

In common crossover operators, there is often an operation of selecting gene segments; some selections are continuous, and some are discontinuous. For crossover operators that use continuous selection, I always use circular selection. The specific operation is as follows: first given a start point l and an end point m, as well as gene length L, if l<m, then select the gene segment from l to m; if l>m, then select the two segments from 0 to m and from l to L. This ensures that every “base pair” has an equal probability of being selected.

For the crossover operators I mainly referred to: https://blog.csdn.net/u012750702/article/details/54563515

Most of the following content is excerpted from that website, of course with a small portion of my own understanding.

Partial-Mapped Crossover(PMX)

This crossover operator uses continuous selection. The specific process is as follows: Step 1: randomly select the start and end positions of several genes in a pair of chromosomes (the parents) (the selected positions are the same on both chromosomes):

Step 2: exchange the positions of these two groups of genes:

Step 3: perform conflict detection. Based on the two exchanged groups of genes, establish a mapping relationship. As shown in the figure, taking the 1-6-3 mapping relationship as an example, you can see that in the result of step 2, offspring 1 has two gene 1s; at this point transform it into gene 3 through the mapping relationship, and so on until there are no conflicts. In the end, all conflicting genes will go through the mapping, ensuring that the newly formed pair of offspring genes has no conflicts:

Final result:

The most critical part of this crossover operator is the conflict detection in the third step. The method I adopted is to first use a dictionary to store the “base” corresponding to each “base”. For example, in the above example, the dictionary I stored is

For such a mapping table, if I want to find the number corresponding to “1”, I only need nested loop checks: the number corresponding to “1” is “6”, the number corresponding to “6” is “3”, the number corresponding to “3” is “-1”, the loop stops, so I found that the number “1” ultimately corresponds to is “3”. In this way, conflict detection is implemented.

/// <summary>
/// PMX交叉算子
/// </summary>
/// <param name="parent1">父类基因一</param>
/// <param name="parent2">父类基因二</param>
/// <returns>基因片段</returns>
public static List<int[]> PMX(int[] parent1, int[] parent2)
{
    List<int[]> ans = new List<int[]>();
    int[] a = new int[parent1.Length], ans1 = new int[parent1.Length], ans2 = new int[parent1.Length];
    int l, m, num;
    for (int i = 0; i < parent1.Length; i++)
    {
        a[i] = i;
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    l = a[0];
    m = a[1];
    Dictionary<int, int> dict1 = new Dictionary<int, int>(), dict2 = new Dictionary<int, int>();
    for (int i = 1; i <= parent1.Length; i++)
    {
        dict1[i] = -1;
        dict2[i] = -1;
    }

    if (l < m)
    {
        for (int i = l; i < m; i++)
        {
            ans1[i] = parent2[i];
            ans2[i] = parent1[i];
            dict1[parent2[i]] = parent1[i];
            dict2[parent1[i]] = parent2[i];
        }

        for (int i = 0; i < l; i++)
        {
            num = parent1[i];
            while (dict1[num] != -1)
            {
                num = dict1[num];
            }

            ans1[i] = num;

            num = parent2[i];
            while (dict2[num] != -1)
            {
                num = dict2[num];
            }

            ans2[i] = num;
        }

        for (int i = m; i < parent1.Length; i++)
        {
            num = parent1[i];
            while (dict1[num] != -1)
            {
                num = dict1[num];
            }

            ans1[i] = num;

            num = parent2[i];
            while (dict2[num] != -1)
            {
                num = dict2[num];
            }

            ans2[i] = num;
        }
    }
    else
    {
        for (int i = 0; i < m; i++)
        {
            ans1[i] = parent2[i];
            ans2[i] = parent1[i];
            dict1[parent2[i]] = parent1[i];
            dict2[parent1[i]] = parent2[i];
        }

        for (int i = l; i < parent1.Length; i++)
        {
            ans1[i] = parent2[i];
            ans2[i] = parent1[i];
            dict1[parent2[i]] = parent1[i];
            dict2[parent1[i]] = parent2[i];
        }

        for (int i = m; i < l; i++)
        {
            num = parent1[i];
            while (dict1[num] != -1)
            {
                num = dict1[num];
            }

            ans1[i] = num;

            num = parent2[i];
            while (dict2[num] != -1)
            {
                num = dict2[num];
            }

            ans2[i] = num;
        }
    }

    ans.Add(ans1);
    ans.Add(ans2);
    return ans;
}

Order Crossover (OX)

This operator also uses continuous selection. The specific process is as follows:

Step 1: same as PMX, randomly select the start and end positions of several genes in a pair of chromosomes (the parents) (the selected positions are the same on both chromosomes):

Step 2: generate an offspring, and ensure that the positions of the selected genes in the offspring are the same as in the parent:

Step 3 (which can be further divided into two sub-steps): first find the positions of the genes selected in step 1 in the other parent, then place the remaining genes in order into the offspring generated in the previous step:

It should be noted that this algorithm will likewise generate two offspring. The generation process for the other offspring is completely the same; you only need to swap the positions of the two parent chromosomes, with the genotype positions selected in step 1 remaining the same. The other offspring in this example is: 254913678

Unlike PMX, there is no need to perform conflict detection (in fact, only PMX needs to do conflict detection).

/// <summary>
/// OX交叉算子
/// </summary>
/// <param name="parent1">父类基因一</param>
/// <param name="parent2">父类基因二</param>
/// <returns>基因片段</returns>
public static List<int[]> OX(int[] parent1, int[] parent2)
{
    List<int[]> ans = new List<int[]>();
    int[] a = new int[parent1.Length], ans1 = new int[parent1.Length], ans2 = new int[parent1.Length];
    int l, m;
    for (int i = 0; i < parent1.Length; i++)
    {
        a[i] = i;
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    l = a[0];
    m = a[1];

    if (l < m)
    {
        HashSet<int> set1 = new HashSet<int>(), set2 = new HashSet<int>();
        int j = 0, k = 0;
        for (int i = l; i < m; i++)
        {
            ans2[i] = parent2[i];
            set2.Add(parent2[i]);
            ans1[i] = parent1[i];
            set1.Add(parent1[i]);
        }

        for (int i = 0; i < l; i++)
        {
            while (set1.Contains(parent2[j]))
            {
                j++;
            }

            ans1[i] = parent2[j];
            j++;

            while (set2.Contains(parent1[k]))
            {
                k++;
            }

            ans2[i] = parent1[k];
            k++;
        }

        for (int i = m; i < parent1.Length; i++)
        {
            while (set1.Contains(parent2[j]))
            {
                j++;
            }

            ans1[i] = parent2[j];
            j++;

            while (set2.Contains(parent1[k]))
            {
                k++;
            }

            ans2[i] = parent1[k];
            k++;
        }
    }
    else
    {
        HashSet<int> set1 = new HashSet<int>(), set2 = new HashSet<int>();
        int j = 0, k = 0;
        for (int i = 0; i < m; i++)
        {
            ans2[i] = parent2[i];
            set2.Add(parent2[i]);
            ans1[i] = parent1[i];
            set1.Add(parent1[i]);
        }

        for (int i = l; i < parent1.Length; i++)
        {
            ans2[i] = parent2[i];
            set2.Add(parent2[i]);
            ans1[i] = parent1[i];
            set1.Add(parent1[i]);
        }

        for (int i = m; i < l; i++)
        {
            while (set1.Contains(parent2[j]))
            {
                j++;
            }

            ans1[i] = parent2[j];
            j++;

            while (set2.Contains(parent1[k]))
            {
                k++;
            }

            ans2[i] = parent1[k];
            k++;
        }
    }

    ans.Add(ans1);
    ans.Add(ans2);
    return ans;
}

Position-based Crossover (PBX)

This operator uses discontinuous selection. The specific process is as follows:

Step 1: randomly select several genes in a pair of chromosomes (the parents); the positions need not be continuous, but the selected positions on both chromosomes are the same:

Step 2: same as step 2 of OX, generate an offspring, and ensure that the positions of the selected genes in the offspring are the same as in the parent:

Step 3: also the same as step 3 of OX, first find the positions of the genes selected in step 1 in the other parent, then place the remaining genes in order into the offspring generated in the previous step:

Unlike the previous two algorithms, the selected genotype positions can be discontinuous. Apart from this point, it is basically the same as OX. There are likewise two offspring; the other one in this example is: 243519678.

/// <summary>
/// PBX交叉算子
/// </summary>
/// <param name="parent1">父类基因一</param>
/// <param name="parent2">父类基因二</param>
/// <returns>基因片段</returns>
public static List<int[]> PBX(int[] parent1, int[] parent2)
{
    List<int[]> ans = new List<int[]>();
    int[] a = new int[parent1.Length], ans1 = new int[parent1.Length], ans2 = new int[parent1.Length];
    for (int i = 0; i < parent1.Length; i++)
    {
        a[i] = i;
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    int r = rand_int(0, parent1.Length);
    HashSet<int> set = new HashSet<int>(), set1 = new HashSet<int>(), set2 = new HashSet<int>();
    for (int i = 0; i < r; i++)
    {
        set.Add(a[i]);
    }


    foreach (var i in set)
    {
        ans2[i] = parent2[i];
        set2.Add(parent2[i]);
        ans1[i] = parent1[i];
        set1.Add(parent1[i]);
    }

    int j = 0, k = 0;
    for (int i = 0; i < parent1.Length; i++)
    {
        if (set.Contains(i))
        {
            continue;
        }

        while (set1.Contains(parent2[j]))
        {
            j++;
        }

        ans1[i] = parent2[j];
        j++;

        while (set2.Contains(parent1[k]))
        {
            k++;
        }

        ans2[i] = parent1[k];
        k++;
    }

    ans.Add(ans1);
    ans.Add(ans2);
    return ans;
}

Order-Based Crossover (OBX)

This operator uses non-contiguous selection. The specific process is as follows:

Step 1: Randomly select several genes from a pair of chromosomes (parents). The positions need not be contiguous, but the selected positions on both chromosomes are the same:

Step 2 (divided into two sub-steps): First find in parent 2 the positions of the genes selected in parent 1, then use the remaining genes from parent 2 to generate the offspring, ensuring positional correspondence:

Step 3: Place the selected genes from parent 1 into the remaining positions of the offspring in order:

Similarly, swapping parents 1 and 2 yields another offspring (the positions of the selected genes remain unchanged). In this example the result is: 423156798.

Compared with PBX, OBX differs in the source of the “base” genes used to generate offspring: one comes from the selected genes, the other from the remaining ones; otherwise the ideas are essentially similar.

/// <summary>
/// OBX交叉算子
/// </summary>
/// <param name="parent1">父类基因一</param>
/// <param name="parent2">父类基因二</param>
/// <returns>基因片段</returns>
public static List<int[]> OBX(int[] parent1, int[] parent2)
{
    List<int[]> ans = new List<int[]>();
    int[] a = new int[parent1.Length], ans1 = new int[parent1.Length], ans2 = new int[parent1.Length];
    int l, m;
    for (int i = 0; i < parent1.Length; i++)
    {
        a[i] = i;
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    int r = rand_int(0, parent1.Length);
    HashSet<int> set1 = new HashSet<int>(), set2 = new HashSet<int>();
    List<int> set = new List<int>();
    for (int i = 0; i < r; i++)
    {
        set.Add(a[i]);
    }


    foreach (var i in set)
    {
        set1.Add(parent1[i]);
        set2.Add(parent2[i]);
    }

    int j = 0, k = 0;
    for (int i = 0; i < parent2.Length; i++)
    {
        if (!set1.Contains(parent2[i]))
        {
            ans1[i] = parent2[i];
        }
        else
        {
            ans1[i] = parent1[set[j]];
            j++;
        }

        if (!set2.Contains(parent1[i]))
        {
            ans2[i] = parent1[i];
        }
        else
        {
            ans2[i] = parent2[set[k]];
            k++;
        }
    }

    ans.Add(ans1);
    ans.Add(ans2);
    return ans;
}

Cycle Crossover (CX)

The specific process of this operator is as follows:

Step 1: Randomly select 1 gene on one parent, then find the gene number at the corresponding position on the other parent, then go back to the first parent to find the position of the gene with the same number, and repeat the previous work until a cycle is formed. The positions of all genes in the cycle are the finally selected positions:

Step 2: Use the selected genes from parent 1 to generate the offspring, ensuring positional correspondence:

Step 3: Place the remaining genes from parent 2 into the offspring:

Unlike the algorithms above, only one position needs to be randomly selected on one chromosome. In this example the other offspring is: 543926781.

The process of finding the closed cycle here is actually somewhat similar to conflict detection in PMX; it is just nested loop checks.

/// <summary>
/// CX交叉算子
/// </summary>
/// <param name="parent1">父类基因一</param>
/// <param name="parent2">父类基因二</param>
/// <returns>基因片段</returns>
public static List<int[]> CX(int[] parent1, int[] parent2)
{
    int r = rand_int(0, parent1.Length);
    List<int[]> ans = new List<int[]>();
    int[] ans1 = new int[parent1.Length], ans2 = new int[parent1.Length];
    Dictionary<int, int> dict = new Dictionary<int, int>();
    for (int i = 0; i < parent1.Length; i++)
    {
        dict[parent1[i]] = i;
    }

    Dictionary<int, int> a = new Dictionary<int, int>();
    HashSet<int> set = new HashSet<int>();
    a[parent1[r]] = parent2[r];
    int num = parent2[r];
    ans1[r] = parent1[r];
    ans2[r] = parent2[r];
    set.Add(dict[parent1[r]]);
    while (parent2[dict[num]] != parent1[r])
    {
        a[num] = parent2[dict[num]];
        ans1[dict[num]] = num;
        ans2[dict[num]] = parent2[dict[num]];
        set.Add(dict[num]);
        num = a[num];
    }

    set.Add(dict[num]);
    ans1[dict[num]] = num;
    ans2[dict[num]] = parent2[dict[num]];

    for (int i = 0; i < parent1.Length; i++)
    {
        if (!set.Contains(i))
        {
            ans1[i] = parent2[i];
            ans2[i] = parent1[i];
        }
    }

    ans.Add(ans1);
    ans.Add(ans2);
    return ans;
}

Subtour Exchange Crossover(SEC)

This operator uses contiguous selection. The specific process is as follows:

Step 1: Select a group of genes on one parent, and find the positions of these genes on the other parent:

Step 2: Keep the unselected genes unchanged, and according to the order of appearance of the selected genes, swap the gene positions on the two parent chromosomes, generating two offspring at once:

Unlike the algorithms above, gene positions are selected on only one chromosome.

/// <summary>
/// SEC交叉算子
/// </summary>
/// <param name="parent1">父类基因一</param>
/// <param name="parent2">父类基因二</param>
/// <returns>基因片段</returns>
public static List<int[]> SEC(int[] parent1, int[] parent2)
{
    List<int[]> ans = new List<int[]>();
    int[] a = new int[parent1.Length], ans1 = new int[parent1.Length], ans2 = new int[parent1.Length];
    int l, m, t;
    for (int i = 0; i < parent1.Length; i++)
    {
        a[i] = i;
        ans1[i] = parent1[i];
        ans2[i] = parent2[i];
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    l = a[0];
    m = a[1];


    Dictionary<int, int> dict = new Dictionary<int, int>();
    for (int i = 0; i < parent1.Length; i++)
    {
        dict[parent2[i]] = i;
    }

    List<int> index = new List<int>();

    if (l < m)
    {
        for (int i = l; i < m; i++)
        {
            index.Add(dict[parent1[i]]);
        }

        index.Sort();

        for (int i = 0; i < m - l; i++)
        {
            t = ans1[l + i];
            ans1[l + i] = ans2[index[i]];
            ans2[index[i]] = t;
        }
    }
    else
    {
        for (int i = 0; i < m; i++)
        {
            index.Add(dict[parent1[i]]);
        }

        for (int i = l; i < parent1.Length; i++)
        {
            index.Add(dict[parent1[i]]);
        }

        index.Sort();

        for (int i = 0; i < m; i++)
        {
            t = ans1[i];
            ans1[i] = ans2[index[i]];
            ans2[index[i]] = t;
        }

        for (int i = 0; i < parent1.Length - l; i++)
        {
            t = ans1[l + i];
            ans1[l + i] = ans2[index[m + i]];
            ans2[index[m + i]] = t;
        }
    }

    ans.Add(ans1);
    ans.Add(ans2);
    return ans;
}

Other Crossover Operators

The algorithms above all handle genes of int-array type. For genes of bool-array type, processing is much simpler: just select gene segments and swap them. By the same principle, the selection can be either contiguous or non-contiguous.

/// <summary>
/// OX交叉算子
/// </summary>
/// <param name="parent1">父类基因一</param>
/// <param name="parent2">父类基因二</param>
/// <returns>基因片段</returns>
public static List<bool[]> OX(bool[] parent1, bool[] parent2)
{
    List<bool[]> ans = new List<bool[]>();
    int[] a = new int[parent1.Length];
    bool[] ans1 = new bool[parent1.Length], ans2 = new bool[parent2.Length];
    int l, m;
    for (int i = 0; i < parent1.Length; i++)
    {
        a[i] = i;
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    l = a[0];
    m = a[1];

    if (l < m)
    {
        for (int i = l; i < m; i++)
        {
            ans1[i] = parent2[i];
            ans2[i] = parent1[i];
        }

        for (int i = 0; i < l; i++)
        {
            ans1[i] = parent1[i];
            ans2[i] = parent2[i];
        }

        for (int i = m; i < parent1.Length; i++)
        {
            ans1[i] = parent1[i];
            ans2[i] = parent2[i];
        }
    }
    else
    {
        for (int i = 0; i < m; i++)
        {
            ans1[i] = parent2[i];
            ans2[i] = parent1[i];
        }

        for (int i = l; i < parent1.Length; i++)
        {
            ans1[i] = parent2[i];
            ans2[i] = parent1[i];
        }

        for (int i = m; i < l; i++)
        {
            ans1[i] = parent1[i];
            ans2[i] = parent2[i];
        }
    }

    ans.Add(ans1);
    ans.Add(ans2);
    return ans;
}

/// <summary>
/// PBX交叉算子
/// </summary>
/// <param name="parent1">父类基因一</param>
/// <param name="parent2">父类基因二</param>
/// <returns>基因片段</returns>
public static List<bool[]> PBX(bool[] parent1, bool[] parent2)
{
    List<bool[]> ans = new List<bool[]>();
    int[] a = new int[parent1.Length];
    bool[] ans1 = new bool[parent1.Length], ans2 = new bool[parent2.Length];
    for (int i = 0; i < parent1.Length; i++)
    {
        a[i] = i;
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    int r = rand_int(0, parent1.Length);
    HashSet<int> set = new HashSet<int>(), set1 = new HashSet<int>(), set2 = new HashSet<int>();
    for (int i = 0; i < r; i++)
    {
        set.Add(a[i]);
    }

    for (int i = 0; i < parent1.Length; i++)
    {
        if (set.Contains(i))
        {
            ans1[i] = parent2[i];
            ans2[i] = parent1[i];
        }
        else
        {
            ans1[i] = parent1[i];
            ans2[i] = parent2[i];
        }
    }

    ans.Add(ans1);
    ans.Add(ans2);
    return ans;
}

Mutation Operators

Mutation is relatively much simpler. For genes of int-array type, you only need to select a gene segment (contiguous or non-contiguous) and rearrange it; for genes of bool-array type, you only need to select a gene segment (contiguous or non-contiguous) and invert it.

/// <summary>
/// OX变异算子
/// </summary>
/// <param name="gene">基因片段</param>
/// <returns>基因片段</returns>
public static int[] Variation_OX(int[] gene)
{
    int[] a = new int[gene.Length], ans = new int[gene.Length];
    int l, m;
    for (int i = 0; i < gene.Length; i++)
    {
        a[i] = i;
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    l = a[0];
    m = a[1];

    List<int> b = new List<int>();
    if (l < m)
    {
        for (int i = l; i < m; i++)
        {
            b.Add(gene[i]);
        }

        b = b.OrderBy(c => Guid.NewGuid()).ToList();
        for (int i = 0; i < l; i++)
        {
            ans[i] = gene[i];
        }

        for (int i = 0; i < m - l; i++)
        {
            ans[l + i] = b[i];
        }

        for (int i = m; i < gene.Length; i++)
        {
            ans[i] = gene[i];
        }
    }
    else
    {
        for (int i = 0; i < m; i++)
        {
            b.Add(gene[i]);
        }

        for (int i = l; i < gene.Length; i++)
        {
            b.Add(gene[i]);
        }

        b = b.OrderBy(c => Guid.NewGuid()).ToList();
        for (int i = 0; i < m; i++)
        {
            ans[i] = b[i];
        }

        for (int i = m; i < l; i++)
        {
            ans[i] = gene[i];
        }

        for (int i = 0; i < gene.Length - l; i++)
        {
            ans[i + l] = b[m + i];
        }
    }

    return ans;
}

/// <summary>
/// OX变异算子
/// </summary>
/// <param name="gene">基因片段</param>
/// <returns>基因片段</returns>
public static bool[] Variation_OX(bool[] gene)
{
    int[] a = new int[gene.Length];
    int l, m;
    bool[] ans = new bool[gene.Length];
    for (int i = 0; i < gene.Length; i++)
    {
        a[i] = i;
        ans[i] = gene[i];
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    l = a[0];
    m = a[1];

    if (l < m)
    {
        for (int i = l; i < m; i++)
        {
            ans[i] = !ans[i];
        }
    }
    else
    {
        for (int i = 0; i < m; i++)
        {
            ans[i] = !ans[i];
        }

        for (int i = l; i < gene.Length; i++)
        {
            ans[i] = !ans[i];
        }
    }

    return ans;
}

/// <summary>
/// PBX变异算子
/// </summary>
/// <param name="gene">基因片段</param>
/// <returns>基因片段</returns>
public static int[] Variation_PBX(int[] gene)
{
    int[] a = new int[gene.Length], ans = new int[gene.Length];
    for (int i = 0; i < gene.Length; i++)
    {
        a[i] = i;
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    int r = rand_int(0, gene.Length);
    HashSet<int> set = new HashSet<int>();
    for (int i = 0; i < r; i++)
    {
        set.Add(a[i]);
    }

    List<int> b = new List<int>();
    for (int i = 0; i < gene.Length; i++)
    {
        if (set.Contains(i))
        {
            b.Add(gene[i]);
        }
    }

    b = b.OrderBy(c => Guid.NewGuid()).ToList();
    int num = 0;
    for (int i = 0; i < gene.Length; i++)
    {
        if (set.Contains(i))
        {
            ans[i] = b[num];
            num++;
        }
        else
        {
            ans[i] = gene[i];
        }
    }

    return ans;
}

/// <summary>
/// PBX变异算子
/// </summary>
/// <param name="gene">基因片段</param>
/// <returns>基因片段</returns>
public static bool[] Variation_PBX(bool[] gene)
{
    int[] a = new int[gene.Length];
    bool[] ans = new bool[gene.Length];
    for (int i = 0; i < gene.Length; i++)
    {
        a[i] = i;
    }

    a = a.OrderBy(c => Guid.NewGuid()).ToArray();
    int r = rand_int(0, gene.Length);
    HashSet<int> set = new HashSet<int>();
    for (int i = 0; i < r; i++)
    {
        set.Add(a[i]);
    }

    for (int i = 0; i < gene.Length; i++)
    {
        if (set.Contains(i))
        {
            ans[i] = !gene[i];
        }
        else
        {
            ans[i] = gene[i];
        }
    }


    return ans;
}

That's all for the population class code! Next up is the brief yet core genetic algorithm!