How can we design the mutation and crossover operations when the order of the genes in the chromosomes matters?

Question

Consider an optimization problem that involves a set of tasks $T = \{1,2,3,4,5\}$, where the goal is to find a certain order of these tasks.

I would like to solve this problem with a genetic algorithm, where each chromosome $C = [i, j, k, l, m]$ corresponds to a specific order of these five tasks, so each gene in $C$ corresponds to a task in $T$.

So, for example, $C = [1,3,5,4,2]$ and $C' = [1,5,4,2,3]$ would be two chromosomes that correspond to two different orders of the tasks.

In this case, how could we design the mutation and cross-over operations so that these constraints are maintained during evolution?

The genetic algorithm should produce the three best chromosomes or order of tasks.

Answer 1

If I understood correctly, your problem is about finding the optimal way to execute a series of tasks in order to maximize the results, using Genetic Algorithms.

In few words, you're trying to solve the salesman problem.

---

If I am correct, you're looking for Crossover and Mutation algorithms that allow you to work with ordered sets of elements. For these scenarios you usually go for the classic PMX (Partially Mapped Crossover) and Interchange Mutation. But, there are plenty of other crossover algorithms you can use OX1, OX2 (both variants of the Order Based Crossover), Shuffle Crossover, Ring Crossover, etc. Let's start from the mutation, that is easier.

For simplicity I'll represent the ordered genome like an array of integers: int[] genome = {1, 2, 3, 4, 5};

Interchange mutation

The concept is pretty basic: to mutate an ordered genome you just swap two elements. Easy.

    public int[] InterchangeMutation(int[] genome)
    {
        int i1 = random.Next(0, genome.Length);
        int i2 = random.Next(0, genome.Length);

        var copy = genome.ToArray(); //just making a copy here
        copy[i1] = genome[i2];
        copy[i2] = genome[i1];

        return copy;
    }

PMX Variation Crossover

This is a bit more complicated as we have to take repetitions into account. From experience, I like to use this variation of the Partially Mapped Crossover. It is way easier to implement than the original one (you can find the paper online) but it will cost some more computational complexity. Longer the genome, higher the price you will pay.

1. Start by selecting two parents to use for the crossover.
2. From the first parent (P1) select a random section that will be passed over.
3. For the remaining values:
   3A. If they are not in the copied section, take them from P2
   3B. If they are in the copied section, take them from P1
   3C. End up filling the gaps with the missing values in the order they are in P1

 public int[] PMX2Crossover(int[] P1, int[] P2)
    {
        //Initializing child genome
        int[] child = new int[P1.Length];
        for (int i = 0; i < P2.Length; i++) child[i] = -1;

        //Step1: getting random section to copy over
        int i1 = random.Next(0, P1.Length);
        int i2 = random.Next(0, P1.Length);

        //Step 2: Copying over section from P1
        for (int i = Math.Min(i1, i2); i < Math.Max(i1, i2); i++) child[i] = P1[i];

        //Step 3A: Copying values from P2
        for (int i = 0; i < P2.Length; i++) if (child[i] ==-1 && !child.Contains(P2[i])) child[i] = P2[i];

        //Step 3B: Copying values from P1
        for (int i = 0; i < P2.Length; i++) if (child[i] == -1 && !child.Contains(P1[i])) child[i] = P1[i];

        //Step 3C: Copying remaining values from P1
        int emptyGene = child.IndexOfFirst(-1);
        while (emptyGene != -1)
        {
            child[emptyGene] = FirstMissingGene(P1, child); 
            emptyGene = child.IndexOfFirst(-1);
        }

        return child;
    }

    private int FirstMissingGene(int[] parent, int[] child)
    {
        foreach (var gene in parent) if (!child.Contains(gene)) return gene;
        return -1; // should never get here
    }

You can lower down the complexity of the crossover to O(n) (from O(n*n)) simply using a hashmap that keeps track of the genes already added to child.

To get the first child call PMX2Crossover(P1, P2); and for the second just swap the parents PMX2Crossover(P2, P1);

Hope this helps you.

Source: I have been a bachelor professor of AI for a period.

Answer 2

You could use np.random.choice to shuffle the arrays. You could use a distance metric to find new arrays that are mutants of the the current good set.