2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I have edited this post to leave the question that I think was your original question. Please, make sure that this is really the case. If not, feel free to edit your post again and clarify what your question really is. $\endgroup$ – nbro Dec 8 '20 at 15:40
1
$\begingroup$

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.

enter image description here

    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

enter image description here

 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.

$\endgroup$
1
  • $\begingroup$ I edited the original post to clarify it even further. The current version of the question is an attempt to be the question to your answer, which seems valuable (that's why I tried to save this post by reformulating the question, in the first place). Please, make sure that the current version of the question is really the question that you're addressing in this answer. $\endgroup$ – nbro Dec 8 '20 at 15:36
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.