Answers.Body: <p>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.  </p>
  
  <p>In few words, you're trying to solve the salesman problem.</p>
  
  <hr>
  
  <p>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.   </p>
  
  <p>For simplicity I'll represent the ordered genome like an array of integers: <code>int[] genome = {1, 2, 3, 4, 5};</code></p>
  
  <p><strong>Interchange mutation</strong>  </p>
  
  <p>The concept is pretty basic: to mutate an ordered genome you just swap two elements. Easy.    </p>
  
  <p><a href="https://i.sstatic.net/35qDd.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/35qDd.png" alt="enter image description here"></a></p>
  
  
  
  <pre><code>    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;
      }
  </code></pre>
  
  <p><strong>PMX Variation Crossover</strong>  </p>
  
  <p>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.</p>
  
  <ol>
  <li>Start by selecting two parents to use for the crossover.  </li>
  <li>From the first parent (P1) select a random section that will be passed over.</li>
  <li>For the remaining values:<br>
  3A. If they are not in the copied section, take them from P2<br>
  3B. If they are in the copied section, take them from P1<br>
  3C. End up filling the gaps with the missing values in the order they are in P1  </li>
  </ol>
  
  <p><a href="https://i.sstatic.net/9AUeX.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/9AUeX.png" alt="enter image description here"></a></p>
  
  
  
  <pre><code> public int[] PMX2Crossover(int[] P1, int[] P2)
      {
          //Initializing child genome
          int[] child = new int[P1.Length];
          for (int i = 0; i &lt; 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 &lt; Math.Max(i1, i2); i++) child[i] = P1[i];
  
          //Step 3A: Copying values from P2
          for (int i = 0; i &lt; P2.Length; i++) if (child[i] ==-1 &amp;&amp; !child.Contains(P2[i])) child[i] = P2[i];
  
          //Step 3B: Copying values from P1
          for (int i = 0; i &lt; P2.Length; i++) if (child[i] == -1 &amp;&amp; !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
      }
  </code></pre>
  
  <p>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.   </p>
  
  <p>To get the first child call <code>PMX2Crossover(P1, P2);</code> and for the second just swap the parents <code>PMX2Crossover(P2, P1);</code>   </p>
  
  <p>Hope this helps you.  </p>
  
  <p>Source: I have been a bachelor professor of AI for a period.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-08T15:36:42.373Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-21T12:05:51.073Z
Answers.LastActivityDate: 2019-12-21T12:11:11.773Z
Answers.LastEditDate: 2019-12-21T12:11:11.773Z
Answers.UserDisplayName: Alvin Sartor
Answers.Body: <p>You could use <code>np.random.choice</code> to shuffle the arrays. You could use a distance metric to find new arrays that are mutants of the the current good set. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-16T17:54:19.460Z
Answers.LastActivityDate: 2020-02-16T17:54:19.460Z
Answers.UserDisplayName: Dirk N
Body: <p>Consider an optimization problem that involves a set of tasks <span class="math-container">$T = \{1,2,3,4,5\}$</span>, where the goal is to find a certain order of these tasks.</p>
  <p>I would like to solve this problem with a genetic algorithm, where each chromosome <span class="math-container">$C = [i, j, k, l, m]$</span> corresponds to a specific order of these five tasks, so each gene in <span class="math-container">$C$</span> corresponds to a task in <span class="math-container">$T$</span>.</p>
  <p>So, for example, <span class="math-container">$C = [1,3,5,4,2]$</span> and <span class="math-container">$C' = [1,5,4,2,3]$</span> would be two chromosomes that correspond to two different orders of the tasks.</p>
  <p>In this case, how could we design the mutation and cross-over operations so that these constraints are maintained during evolution?</p>
  <p>The genetic algorithm should produce the three best chromosomes or order of tasks.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-08T15:40:56.987Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Tags: <genetic-algorithms><crossover-operators><mutation-operators><constrained-optimization><chromosomes>
Title: How can we design the mutation and crossover operations when the order of the genes in the chromosomes matters?
UserDisplayName: Tariq Kavish Arain
ThreadText: # How can we design the mutation and crossover operations when the order of the genes in the chromosomes matters?
  
  (Asked by: username_0 on 2019-12-18)
  
  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.
  
  **Tags:** genetic-algorithms, crossover-operators, mutation-operators, constrained-optimization, chromosomes
  > **Comments:**
  > **username_1**: 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.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2019-12-21. Score: 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.
  
  Start by selecting two parents to use for the crossover.  
  From the first parent (P1) select a random section that will be passed over.
  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.
  
  > **Comments:**
  > **username_1**: 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.  
  
  ---
  
  ### Answer by username_3 on 2020-02-16. Score: 0
  
  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.
  
  
  ---
  
  