1
$\begingroup$

How can I structure my genetic algorithm to output ordered arrays?

I have some tasks, let's call them $\{1,2,3,4,5\}$ and I would like to create genes representing these tasks in different orders.

i.e.
$\text{gene1}=[1,3,5,4,2];$
$\text{gene2}=[1,5,4,2,3];$
$\text{gene3}=[5,2,3,4,1]$.

Is there any example of genetic algorithms's pseudo code?

$\endgroup$
  • 1
    $\begingroup$ Hi. It's not very clear what you're asking. It's not clear the relationship between tasks and genes and it is not clear your problem. What is a "input task set" and what is a "oder of a task"? $\endgroup$ – nbro Dec 18 '19 at 13:58
  • 1
    $\begingroup$ for example we have five tasks in the population and then with five tasks differents orders like gene 1 gene 2 gene3 $\endgroup$ – Tariq Kavish Arain Dec 18 '19 at 14:31
  • 1
    $\begingroup$ So is this like a Travelling Salesman Problem, where you are searching for the best permutation of the set? And you want to use a GA, but not sure how to express the permutations as genes? $\endgroup$ – Neil Slater Dec 18 '19 at 14:36
  • 1
    $\begingroup$ Unfortunately that doesn't clarify what you are looking for, and I cannot understand the question. If you only want 3 random orders applied to a list of 5 things, use shuffle, there is no need for a GA at all. $\endgroup$ – Neil Slater Dec 19 '19 at 7:32
  • 1
    $\begingroup$ @DukeZhou thanks for reopening the question. I understand your confusion now, but I hope that my answer clarifies it :). $\endgroup$ – Alvin Sartor Dec 21 '19 at 12:09
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.

| improve this answer | |
$\endgroup$
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.

| improve this answer | |
$\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.