Changeset 2823

Timestamp:

02/17/10 20:24:23 (15 years ago)

Author:

abeham

Message:

updated MPX (documentation) and PMX (documentation + implementation) (#889)
previously commited implementation of PMX was faulty

Location:

trunk/sources/HeuristicLab.Permutation/3.3

Files:

• MaximalPreservativeCrossover.cs (modified) (1 diff)
• PartiallyMatchedCrossover.cs (modified) (2 diffs)

trunk/sources/HeuristicLab.Permutation/3.3/MaximalPreservativeCrossover.cs

@@ -41 +41 @@
     /// </summary>
     /// <exception cref="InvalidOperationException">Thrown if the numbers in the permutation array are not in the range [0,N) with N = length of the permutation.</exception>
+    /// <exception cref="ArgumentException">Thrown when <paramref name="parent1"/> and <paramref name="parent2"/> are not of equal length or when the permutations are shorter than 4 elements.</exception>
     /// <remarks>
     /// First one segment is copied from the first parent to the offspring in the same position.

trunk/sources/HeuristicLab.Permutation/3.3/PartiallyMatchedCrossover.cs

@@ -40 +40 @@
     /// Performs the partially matched crossover on <paramref name="parent1"/> and <paramref name="parent2"/>.
     /// </summary>
+    /// <exception cref="ArgumentException">Thrown when <paramref name="parent1"/> and <paramref name="parent2"/> are not of equal length or when the permutations are shorter than 4 elements.</exception>
     /// <remarks>
     /// First a segment from the first parent is copied to the offspring.
@@ -51 +52 @@
     /// <returns>The new permutation resulting from the crossover.</returns>
     public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
+      if (parent1.Length != parent2.Length) throw new ArgumentException("PartiallyMatchedCrossover: The parent permutations are of unequal length");
+      if (parent1.Length < 4) throw new ArgumentException("PartiallyMatchedCrossover: The parent permutation must be at least of size 4");
       int length = parent1.Length;
-      Permutation result = new Permutation(length);
-      bool[] numbersCopied = new bool[length];
+      Permutation result = new Permutation(length); ;
+      int[] invResult = new int[length];
 
-      int breakPoint1 = random.Next(length - 1);
-      int breakPoint2 = random.Next(breakPoint1 + 1, length);
+      int breakPoint1, breakPoint2;
+      do {
+        breakPoint1 = random.Next(length - 1);
+        breakPoint2 = random.Next(breakPoint1 + 1, length);
+      } while (breakPoint2 - breakPoint1 >= length - 2); // prevent the case [0,length-1) -> clone of parent1
 
-      for (int j = breakPoint1; j <= breakPoint2; j++) {  // copy part of first permutation
-        result[j] = parent1[j];
-        numbersCopied[result[j]] = true;
+      // clone parent2 and calculate inverse permutation (number -> index)
+      for (int j = 0; j < length; j++) {
+        result[j] = parent2[j];
+        invResult[result[j]] = j;
       }
 
-      // calculate the inverse permutation (number -> index) of parent1
-      int[] invParent1 = new int[length];
-      for (int j = 0; j < length; j++) {
-        invParent1[parent1[j]] = j;
+      for (int j = breakPoint1; j <= breakPoint2; j++) {
+        int orig = result[j]; // save the former value
+        result[j] = parent1[j]; // overwrite the former value with the new value
+        int index = invResult[result[j]]; // look where the new value is in the child
+        result[index] = orig; // write the former value to this position
+        invResult[orig] = index; // update the inverse mapping
+        // it's not necessary to do 'invResult[result[j]] = j' as this will not be needed again
       }
 
-      int i = ((breakPoint1 == 0) ? (breakPoint2 + 1) : (0));
-      while (i < length) {  // copy rest from second permutation
-        if (!numbersCopied[parent2[i]]) {  // copy directly
-          result[i] = parent2[i];
-        } else {  // copy from area between breakpoints
-          int index = invParent1[parent2[i]]; // find the index of the corresponding occupied number in parent1
-          result[i] = parent2[index]; // use that index to take the number from parent2
-        }
-
-        i++;
-        if (i == breakPoint1) {  // skip area between breakpoints
-          i = breakPoint2 + 1;
-        }
-      }
       return result;
     }