Changeset 2829 for trunk/sources

Timestamp:

02/18/10 20:42:37 (15 years ago)

Author:

abeham

Message:

Implemented CyclicCrossover, updated documentation in MaximalPreservativeCrossover and PartiallyMatchedCrossover #889

Location:

trunk/sources/HeuristicLab.Permutation/3.3

Files:

• CyclicCrossover.cs (modified) (3 diffs)
• HeuristicLab.Permutation-3.3.csproj (modified) (1 diff)
• MaximalPreservativeCrossover.cs (modified) (4 diffs)
• PartiallyMatchedCrossover.cs (modified) (5 diffs)

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

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -21 +21 @@
 
 using System;
-using System.Collections.Generic;
-using System.Text;
 using HeuristicLab.Core;
-using HeuristicLab.Data;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Permutation {
   /// <summary>
-  /// Performs a cross over permutation between two int arrays by taking first a whole cycle and then the
-  /// missing ones from the second parent.
+  /// An operator which performs the cyclic crossover on two permutations.
   /// </summary>
-  /// <remarks>A whole cycle means: <br/>
-  /// Start at a randomly chosen position x in parent1 and transfer it to the child at the same position.
-  /// Now this position x is no longer available for the node on position x in parent2, so
-  /// the value of the node at position x in parent2 is searched in parent1 and is then transferred
-  /// to the child preserving the position. Now this new position y is no longer available for the node in parent2 ....<br/>
-  /// This procedure is repeated till it is again at position x, then the cycle is over.
+  /// <remarks>It is implemented as described in Eiben, A.E. and Smith, J.E. 2003. Introduction to Evolutionary Computation. Natural Computing Series, Springer-Verlag Berlin Heidelberg.<br />
+  /// The operator first determines all cycles in the permutation and then composes the offspring by alternating between the cycles of the two parents.
   /// </remarks>
-  public class CyclicCrossover : PermutationCrossoverBase {
-    /// <inheritdoc select="summary"/>
-    public override string Description {
-      get { return @"TODO\r\nOperator description still missing ..."; }
-    }
-
+  [Item("CyclicCrossover", "An operator which performs the cyclic crossover on two permutations as described in Eiben, A.E. and Smith, J.E. 2003. Introduction to Evolutionary Computation. Natural Computing Series, Springer-Verlag Berlin Heidelberg.")]
+  [EmptyStorableClass]
+  [Creatable("Test")]
+  public class CyclicCrossover : PermutationCrossover {
     /// <summary>
-    /// Performs a cross over permutation of <paramref name="parent1"/> and <paramref name="parent2"/>
-    /// by copying a whole cycle starting at a randomly chosen position in parent1 and taking the rest
-    /// from parent2.
+    /// Performs the cyclic 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.</exception>
+    /// <exception cref="InvalidOperationException">Thrown if the numbers in the permutation elements are not in the range [0,N) with N = length of the permutation.</exception>
+    /// <remarks>
+    /// First this method randomly determines from which parent to start with equal probability.
+    /// Then it copies the first cycle from the chosen parent starting from index 0 in the permutation.
+    /// After the cycle is complete it copies the next cycle starting from the index closest to 0 which was not yet copied from the other parent.
+    /// It continues to switch between parents for each completed cycle until no new cycle is found anymore.<br /><br />
+    /// The stochasticity of this operator is rather low. There are only two possible outcomes for a given pair of parents.
+    /// </remarks>
     /// <param name="random">The random number generator.</param>
     /// <param name="parent1">The parent scope 1 to cross over.</param>
     /// <param name="parent2">The parent scope 2 to cross over.</param>
     /// <returns>The created cross over permutation as int array.</returns>
-    public static int[] Apply(IRandom random, int[] parent1, int[] parent2) {
+    public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
+      if (parent1.Length != parent2.Length) throw new ArgumentException("CyclicCrossover: The parent permutations are of unequal length");
       int length = parent1.Length;
-      int[] result = new int[length];
+      Permutation result = new Permutation(length);
       bool[] indexCopied = new bool[length];
-      int j, number;
+      int[] invParent1 = new int[length];
+      int[] invParent2 = new int[length];
 
-      j = random.Next(length);  // get number to start cycle
-      while (!indexCopied[j]) {  // copy whole cycle to new permutation
-        result[j] = parent1[j];
-        number = parent2[j];
-        indexCopied[j] = true;
-
-        j = 0;
-        while ((j < length) && (parent1[j] != number)) {  // search copied number in second permutation
-          j++;
+      // calculate inverse mappings (number -> index) for parent1 and parent2
+      try {
+        for (int i = 0; i < length; i++) {
+          invParent1[parent1[i]] = i;
+          invParent2[parent2[i]] = i;
         }
+      } catch (IndexOutOfRangeException) {
+        throw new InvalidOperationException("CyclicCrossover: The permutation must consist of consecutive numbers from 0 to N-1 with N = length of the permutation");
       }
 
-      for (int i = 0; i < length; i++) {  // copy rest of secound permutation to new permutation
-        if (!indexCopied[i]) {
-          result[i] = parent2[i];
-        }
-      }
+      // randomly choose whether to start copying from parent1 or parent2
+      bool copyFromParent1 = ((random.NextDouble() < 0.5) ? (false) : (true));
+
+      int j = 0;
+      do {
+        do {
+          if (copyFromParent1) {
+            result[j] = parent1[j]; // copy number at position j from parent1
+            j = invParent2[result[j]]; // set position j to the position of the copied number in parent2
+          } else {
+            result[j] = parent2[j]; // copy number at position j from parent2
+            j = invParent1[result[j]]; // set position j to the position of the copied number in parent1
+          }
+          indexCopied[j] = true;
+        } while (!indexCopied[j]);
+        copyFromParent1 = !copyFromParent1;
+        j = 0;
+        while (j < length && indexCopied[j]) j++;
+      } while (j < length);
+
       return result;
     }
 
     /// <summary>
-    /// Performs a cyclic crossover operation for two given parent permutations.
+    /// Checks number of parents and calls <see cref="Apply(IRandom, Permutation, Permutation)"/>.
     /// </summary>
     /// <exception cref="InvalidOperationException">Thrown if there are not exactly two parents.</exception>
@@ -87 +100 @@
     /// <param name="parents">An array containing the two permutations that should be crossed.</param>
     /// <returns>The newly created permutation, resulting from the crossover operation.</returns>
-    protected override int[] Cross(IScope scope, IRandom random, int[][] parents) {
-      if (parents.Length != 2) throw new InvalidOperationException("ERROR in CyclicCrossover: The number of parents is not equal to 2");
+    protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) {
+      if (parents.Length != 2) throw new InvalidOperationException("CyclicCrossover: The number of parents is not equal to 2");
       return Apply(random, parents[0], parents[1]);
     }

trunk/sources/HeuristicLab.Permutation/3.3/HeuristicLab.Permutation-3.3.csproj

@@ -82 +82 @@
   <ItemGroup>
     <None Include="HeuristicLabPermutationPlugin.cs.frame" />
+    <Compile Include="CyclicCrossover.cs" />
     <Compile Include="InversionManipulator.cs">
       <SubType>Code</SubType>

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

@@ -29 +29 @@
   /// Performs a crossover between two permuation arrays by preserving a large number of edges in both parents.
   /// The operator also maintains the position in the arrays to some extent.
-  /// It is implemented as described in Mühlenbein, H. Evolution in time and space - the parallel genetic algorithm. FOUNDATIONS OF GENETIC ALGORITHMS, Morgan Kaufmann, 1991, 316-337.
+  /// It is implemented as described in Mühlenbein, H. 1991. Evolution in time and space - the parallel genetic algorithm. FOUNDATIONS OF GENETIC ALGORITHMS, pp. 316-337. Morgan Kaufmann.
+  /// 
   /// The length of the segment copied from the first parent to the offspring is uniformly distributed in the interval [3, N/3) with N = length of the permutation.
+  /// This recommendation is mentioned in Pohlheim, H. 1999. Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis, p. 44, Springer.
+  /// If the length of the permutation is smaller than 15, the size of the segment is always equal to 3.
   /// </remarks>
-  [Item("MaximalPreservativeCrossover", "An operator which performs the maximal preservative crossover on two permutations.")]
+  [Item("MaximalPreservativeCrossover", "An operator which performs the maximal preservative crossover on two permutations as described in Mühlenbein, H. 1991. Evolution in time and space - the parallel genetic algorithm. FOUNDATIONS OF GENETIC ALGORITHMS, pp. 316-337. Morgan Kaufmann.")]
   [EmptyStorableClass]
   [Creatable("Test")]
@@ -40 +43 @@
     /// by preserving a large number of edges in both parents.
     /// </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>
+    /// <exception cref="InvalidOperationException">Thrown if the numbers in the permutation elements are not in the range [0,N) with N = length of the permutation.</exception>
     /// <remarks>
     /// First one segment is copied from the first parent to the offspring in the same position.
@@ -60 +63 @@
       int breakPoint1, breakPoint2, subsegmentLength, index;
 
-      subsegmentLength = random.Next(3, Math.Max(length / 3, 4)); // as mentioned in "Pohlheim, H. Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis, 1999, p.44, Springer.
+      subsegmentLength = random.Next(3, Math.Max(length / 3, 4)); // as mentioned in Pohlheim, H. Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis, 1999, p.44, Springer.
       breakPoint1 = random.Next(length);
       breakPoint2 = breakPoint1 + subsegmentLength;
@@ -126 +129 @@
 
     /// <summary>
-    /// Checks number of parents and calls <see cref="Apply"/>.
+    /// Checks number of parents and calls <see cref="Apply(IRandom, Permutation, Permutation)"/>.
     /// </summary>
     /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>

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

@@ -33 +33 @@
   /// as the original source of the operator.
   /// </remarks>
-  [Item("PartiallyMatchedCrossover", "An operator which performs the partially matched crossover on two permutations.")]
+  [Item("PartiallyMatchedCrossover", "An operator which performs the partially matched crossover on two permutations as described in Fogel, D.B. 1988. An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics, 60, pp. 139-144, Springer-Verlag.")]
   [EmptyStorableClass]
   [Creatable("Test")]
@@ -41 +41 @@
     /// </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>
+    /// <exception cref="InvalidOperationException">Thrown if the numbers in the permutation elements are not in the range [0,N) with N = length of the permutation.</exception>
     /// <remarks>
-    /// First a segment from the first parent is copied to the offspring.
-    /// Then the rest of the offspring is filled with the numbers from parent2.
-    /// When a number is encountered in parent2 that is included in the segment which came from the first parent,
-    /// the number in parent2 is used that was replaced by the corresponding number from parent1.
+    /// Initially the new offspring is a clone of <paramref name="parent2"/>.
+    /// Then a segment is extracted from <paramref name="parent1"/> and copied to the offspring position by position.
+    /// Whenever a position is copied, the number at that position currently in the offspring is transfered to the position where the copied number has been.
+    /// E.g.: Position 15 is selected to be copied from <paramref name="parent1"/> to <paramref name="parent2"/>. At position 15 there is a '3' in <paramref name="parent1"/> and a '5' in the new offspring.
+    /// The '5' in the offspring is then moved to replace the '3' in the offspring and '3' is written at position 15.
     /// </remarks>
     /// <param name="random">A random number generator.</param>
@@ -65 +67 @@
 
       // clone parent2 and calculate inverse permutation (number -> index)
-      for (int j = 0; j < length; j++) {
-        result[j] = parent2[j];
-        invResult[result[j]] = j;
+      try {
+        for (int j = 0; j < length; j++) {
+          result[j] = parent2[j];
+          invResult[result[j]] = j;
+        }
+      } catch (IndexOutOfRangeException) {
+        throw new InvalidOperationException("PartiallyMatchedCrossover: The permutation must consist of consecutive numbers from 0 to N-1 with N = length of the permutation");
       }
 
@@ -73 +79 @@
         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
+        int index = invResult[result[j]]; // look where the new value is in the offspring
         result[index] = orig; // write the former value to this position
         invResult[orig] = index; // update the inverse mapping
@@ -83 +89 @@
 
     /// <summary>
-    /// Checks number of parents and calls <see cref="Apply"/>.
+    /// Checks number of parents and calls <see cref="Apply(Apply(IRandom, Permutation, Permutation)"/>.
     /// </summary>
     /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>