Changeset 2823


Ignore:
Timestamp:
02/17/10 20:24:23 (11 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:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Permutation/3.3/MaximalPreservativeCrossover.cs

    r2820 r2823  
    4141    /// </summary>
    4242    /// <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>
     43    /// <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>
    4344    /// <remarks>
    4445    /// First one segment is copied from the first parent to the offspring in the same position.
  • trunk/sources/HeuristicLab.Permutation/3.3/PartiallyMatchedCrossover.cs

    r2820 r2823  
    4040    /// Performs the partially matched crossover on <paramref name="parent1"/> and <paramref name="parent2"/>.
    4141    /// </summary>
     42    /// <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>
    4243    /// <remarks>
    4344    /// First a segment from the first parent is copied to the offspring.
     
    5152    /// <returns>The new permutation resulting from the crossover.</returns>
    5253    public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
     54      if (parent1.Length != parent2.Length) throw new ArgumentException("PartiallyMatchedCrossover: The parent permutations are of unequal length");
     55      if (parent1.Length < 4) throw new ArgumentException("PartiallyMatchedCrossover: The parent permutation must be at least of size 4");
    5356      int length = parent1.Length;
    54       Permutation result = new Permutation(length);
    55       bool[] numbersCopied = new bool[length];
     57      Permutation result = new Permutation(length); ;
     58      int[] invResult = new int[length];
    5659
    57       int breakPoint1 = random.Next(length - 1);
    58       int breakPoint2 = random.Next(breakPoint1 + 1, length);
     60      int breakPoint1, breakPoint2;
     61      do {
     62        breakPoint1 = random.Next(length - 1);
     63        breakPoint2 = random.Next(breakPoint1 + 1, length);
     64      } while (breakPoint2 - breakPoint1 >= length - 2); // prevent the case [0,length-1) -> clone of parent1
    5965
    60       for (int j = breakPoint1; j <= breakPoint2; j++) {  // copy part of first permutation
    61         result[j] = parent1[j];
    62         numbersCopied[result[j]] = true;
     66      // clone parent2 and calculate inverse permutation (number -> index)
     67      for (int j = 0; j < length; j++) {
     68        result[j] = parent2[j];
     69        invResult[result[j]] = j;
    6370      }
    6471
    65       // calculate the inverse permutation (number -> index) of parent1
    66       int[] invParent1 = new int[length];
    67       for (int j = 0; j < length; j++) {
    68         invParent1[parent1[j]] = j;
     72      for (int j = breakPoint1; j <= breakPoint2; j++) {
     73        int orig = result[j]; // save the former value
     74        result[j] = parent1[j]; // overwrite the former value with the new value
     75        int index = invResult[result[j]]; // look where the new value is in the child
     76        result[index] = orig; // write the former value to this position
     77        invResult[orig] = index; // update the inverse mapping
     78        // it's not necessary to do 'invResult[result[j]] = j' as this will not be needed again
    6979      }
    7080
    71       int i = ((breakPoint1 == 0) ? (breakPoint2 + 1) : (0));
    72       while (i < length) {  // copy rest from second permutation
    73         if (!numbersCopied[parent2[i]]) {  // copy directly
    74           result[i] = parent2[i];
    75         } else {  // copy from area between breakpoints
    76           int index = invParent1[parent2[i]]; // find the index of the corresponding occupied number in parent1
    77           result[i] = parent2[index]; // use that index to take the number from parent2
    78         }
    79 
    80         i++;
    81         if (i == breakPoint1) {  // skip area between breakpoints
    82           i = breakPoint2 + 1;
    83         }
    84       }
    8581      return result;
    8682    }
Note: See TracChangeset for help on using the changeset viewer.