Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/26/10 17:43:21 (15 years ago)
Author:
abeham
Message:

Updated CosaCrossover #889

Location:
trunk/sources/HeuristicLab.Permutation/3.3
Files:
2 edited

Legend:

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

    r2871 r2879  
    2626namespace HeuristicLab.Permutation {
    2727  /// <summary>
    28   /// Performs a crossover operation between two permutation arrays by taking randomly chosen
    29   /// reverse and forward intervals from the first permutation array inserting
    30   /// it in the child on different positions depending on the second permutation array.
     28  /// Performs the crossover described in the COSA optimization method.
    3129  /// </summary>
    32   /// <remarks>It is implemented as described in Wendt, O. 1994. COSA: COoperative Simulated Annealing - Integration von Genetischen Algorithmen und Simulated Annealing am Beispiel der Tourenplanung. Dissertation Thesis. IWI Frankfurt.<br />
     30  /// <remarks>
     31  /// It is implemented as described in Wendt, O. 1994. COSA: COoperative Simulated Annealing - Integration von Genetischen Algorithmen und Simulated Annealing am Beispiel der Tourenplanung. Dissertation Thesis. IWI Frankfurt.<br />
     32  /// The operator actually performs a 2-opt mutation on the first parent, but it uses the second parent to determine which new edge should be inserted.
     33  /// Thus the mutation is not random as the second breakpoint depends on the information that is encoded in other members of the population.
     34  /// The idea is that the child should not sit right inbetween the two parents, but rather go a little bit from one parent in direction to the other.
    3335  /// </remarks>
    34   [Item("CosaCrossover", "An operator which performs a crossover operation between two permutation arrays by taking randomly chosen reverse and forward intervals from the first permutation array inserting it in the child on different positions depending on the second permutation array. It is implemented as described in Wendt, O. 1994. COSA: COoperative Simulated Annealing - Integration von Genetischen Algorithmen und Simulated Annealing am Beispiel der Tourenplanung. Dissertation Thesis. IWI Frankfurt.")]
     36  [Item("CosaCrossover", "An operator which performs the crossover described in the COSA optimization method. It is implemented as described in Wendt, O. 1994. COSA: COoperative Simulated Annealing - Integration von Genetischen Algorithmen und Simulated Annealing am Beispiel der Tourenplanung. Dissertation Thesis. IWI Frankfurt.")]
    3537  [EmptyStorableClass]
    3638  [Creatable("Test")]
    3739  public class CosaCrossover : PermutationCrossover {
    3840    /// <summary>
    39     /// Performs a cross over permutation of <paramref name="parent1"/> and <paramref name="parent2"/>
    40     /// by taking first the reverse elements of a randomly chosen interval of parent1
    41     /// and inserting it in the result at a position specified by the permutation of parent2.
    42     /// The remaining elements to be inserted are taken again from parent1 in the forward direction.
     41    /// The operator actually performs a 2-opt mutation on the first parent, but it uses the second parent to determine which new edge should be inserted.
     42    /// Thus the mutation is not random as the second breakpoint depends on the information that is encoded in other members of the population.
     43    /// The idea is that the child should not sit right inbetween the two parents, but rather go a little bit from one parent in direction to the other.
    4344    /// </summary>
    4445    /// <exception cref="ArgumentException">Thrown when <paramref name="parent1"/> and <paramref name="parent2"/> are not of equal length.</exception>
     
    5758
    5859      int i = 0;
    59       while ((i < parent2.Length) && (parent2[i] != parent1[startIndex])) {  // find index of start value in second permutation
     60      while ((i < parent2.Length) && (parent2[i] != parent1[crossPoint])) {  // find index of cross point in second permutation
    6061        i++;
    6162      }
    62       i = (i + 1) % length;
    63       int j = 0;
    64       while ((j < parent1.Length) && (parent1[j] != parent2[i])) {  // find index of parent2[i] in first permutation
    65         j++;
     63      int newEdge = parent2[(i + 1) % length]; // the number that follows the cross point number in parent2 is the new edge that we want to insert
     64      endIndex = 0;
     65      while ((endIndex < parent1.Length) && (parent1[endIndex] != newEdge)) {  // find index of the new edge in the first permutation
     66        endIndex++;
    6667      }
    67       endIndex = (j - 1 + length) % length;
    6868
    69       i = endIndex;
    70       j = 0;
    71       do {  // permutation from end to crosspoint (backwards)
    72         result[j] = parent1[i];
    73         i = (i - 1 + length) % length;
    74         j++;
    75       } while (i != crossPoint);
    76 
    77       i = (endIndex + 1) % length;
    78       while (i != crossPoint) {  // permutation from end to crosspoint (forwards)
    79         result[j] = parent1[i];
    80         i = (i + 1) % length;
    81         j++;
     69      if (startIndex <= endIndex) {
     70        // copy parent1 to child and reverse the order in between startIndex and endIndex
     71        for (i = 0; i < parent1.Length; i++) {
     72          if (i >= startIndex && i <= endIndex) {
     73            result[i] = parent1[endIndex - i + startIndex];
     74          } else {
     75            result[i] = parent1[i];
     76          }
     77        }
     78      } else { // startIndex > endIndex
     79        for (i = 0; i < parent1.Length; i++) {
     80          if (i >= startIndex || i <= endIndex) {
     81            result[i] = parent1[(endIndex - i + startIndex + length) % length]; // add length to wrap around when dropping below index 0
     82          } else {
     83            result[i] = parent1[i];
     84          }
     85        }
    8286      }
    83       result[j] = parent1[crossPoint];  // last station: crosspoint
    8487      return new Permutation(result);
    8588    }
  • trunk/sources/HeuristicLab.Permutation/3.3/Tests/CosaCrossoverTest.cs

    r2854 r2879  
    110110      TestRandom random = new TestRandom();
    111111      Permutation parent1, parent2, expected, actual;
     112      // The following test is based on an example from Wendt, O. 1994. COSA: COoperative Simulated Annealing - Integration von Genetischen Algorithmen und Simulated Annealing am Beispiel der Tourenplanung. Dissertation Thesis. IWI Frankfurt.
     113      random.Reset();
     114      random.IntNumbers = new int[] { 1 };
     115      parent1 = new Permutation(new int[] { 0, 1, 5, 2, 4, 3 });
     116      Assert.IsTrue(parent1.Validate());
     117      parent2 = new Permutation(new int[] { 3, 0, 2, 1, 4, 5 });
     118      Assert.IsTrue(parent2.Validate());
     119      expected = new Permutation(new int[] { 0, 1, 4, 2, 5, 3 });
     120      Assert.IsTrue(expected.Validate());
     121      actual = CosaCrossover.Apply(random, parent1, parent2);
     122      Assert.IsTrue(actual.Validate());
     123      Assert.IsTrue(Auxiliary.PermutationIsEqualByPosition(expected, actual));
     124      // The following test is not based on published examples
    112125      random.Reset();
    113126      random.IntNumbers = new int[] { 4 };
     
    116129      parent2 = new Permutation(new int[] { 1, 3, 5, 7, 6, 4, 2, 0 });
    117130      Assert.IsTrue(parent2.Validate());
    118       expected = new Permutation(new int[] { 6, 5, 7, 0, 1, 2, 3, 4 });
     131      expected = new Permutation(new int[] { 7, 6, 5, 3, 4, 2, 1, 0 });
    119132      Assert.IsTrue(expected.Validate());
    120133      actual = CosaCrossover.Apply(random, parent1, parent2);
    121134      Assert.IsTrue(actual.Validate());
    122135      Assert.IsTrue(Auxiliary.PermutationIsEqualByPosition(expected, actual));
    123 
     136      // The following test is not based on published examples
     137      random.Reset();
     138      random.IntNumbers = new int[] { 5 };
     139      parent1 = new Permutation(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 });
     140      Assert.IsTrue(parent1.Validate());
     141      parent2 = new Permutation(new int[] { 4, 3, 5, 1, 0, 9, 7, 2, 8, 6 });
     142      Assert.IsTrue(parent2.Validate());
     143      expected = new Permutation(new int[] { 7, 6, 2, 3, 4, 5, 1, 0, 9, 8 });
     144      Assert.IsTrue(expected.Validate());
     145      actual = CosaCrossover.Apply(random, parent1, parent2);
     146      Assert.IsTrue(actual.Validate());
     147      Assert.IsTrue(Auxiliary.PermutationIsEqualByPosition(expected, actual));
     148     
    124149      // perform a test when the two permutations are of unequal length
    125150      random.Reset();
Note: See TracChangeset for help on using the changeset viewer.