Changeset 2820

Timestamp:

02/17/10 18:32:57 (15 years ago)

Author:

abeham

Message:

Added MPX and PMX together with reference (#889)

Location:

trunk/sources/HeuristicLab.Permutation/3.3

Files:

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

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

@@ -85 +85 @@
       <SubType>Code</SubType>
     </Compile>
+    <Compile Include="MaximalPreservativeCrossover.cs" />
+    <Compile Include="PartiallyMatchedCrossover.cs" />
     <Compile Include="PermutationManipulator.cs" />
     <Compile Include="HeuristicLabPermutationPlugin.cs" />

trunk/sources/HeuristicLab.Permutation/3.3/MaximalPreservativeCrossover.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 permuation arrays by preserving a preferably big
-  /// region from one permutation array.
-  /// </summary>
-  public class MaximalPreservativeCrossover : PermutationCrossoverBase {
-    /// <inheritdoc select="summary"/>
-    public override string Description {
-      get { return @"TODO\r\nOperator description still missing ..."; }
+  /// <summary>An operator which performs the maximal preservative crossover on two permutations.</summary>
+  /// <remarks>
+  /// 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.
+  /// 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.
+  /// </remarks>
+  [Item("MaximalPreservativeCrossover", "An operator which performs the maximal preservative crossover on two permutations.")]
+  [EmptyStorableClass]
+  [Creatable("Test")]
+  public class MaximalPreservativeCrossover : PermutationCrossover {
+    /// <summary>
+    /// Performs the maximal preservative crossover on <paramref name="parent1"/> and <paramref name="parent2"/>
+    /// 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>
+    /// <remarks>
+    /// First one segment is copied from the first parent to the offspring in the same position.
+    /// Then the tour is completed by adding the next number from the second parent if such an edge exists,
+    /// or from the first parent, or from the next number of the second parent.
+    /// The last case results in an unwanted mutation.
+    /// </remarks>
+    /// <param name="random">A random number generator.</param>
+    /// <param name="parent1">The first parent permutation to cross.</param>
+    /// <param name="parent2">The second parent permutation to cross.</param>
+    /// <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("MaximalPreservativeCrossover: The parent permutations are of unequal length");
+      if (parent1.Length < 4) throw new ArgumentException("MaximalPreservativeCrossover: The parent permutation must be at least of size 4");
+      int length = parent1.Length;
+      Permutation result = new Permutation(length);
+      bool[] numberCopied = new bool[length];
+      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.
+      breakPoint1 = random.Next(length);
+      breakPoint2 = breakPoint1 + subsegmentLength;
+      if (breakPoint2 >= length) breakPoint2 -= length;
+
+      // copy string between position [breakPoint1, breakPoint2) from parent1 to the offspring
+      index = breakPoint1;
+      do {
+        result[index] = parent1[index];
+        numberCopied[result[index]] = true;
+        index++;
+        if (index >= length) index -= length;
+      } while (index != breakPoint2);
+
+      // calculate inverse permutation (number -> index) to help finding the follower of a given number
+      int[] invParent1 = new int[length];
+      int[] invParent2 = new int[length];
+      try {
+        for (int i = 0; i < length; i++) {
+          invParent1[parent1[i]] = i;
+          invParent2[parent2[i]] = i;
+        }
+      } catch (IndexOutOfRangeException) {
+        throw new InvalidOperationException("MaximalPreservativeCrossover: The permutation must consist of consecutive numbers from 0 to N-1 with N = length of the permutation");
+      }
+
+      int prevIndex = ((index > 0) ? (index - 1) : (length - 1));
+      do {
+        // look for the follower of the last number in parent2
+        int p2Follower = GetFollower(parent2, invParent2[result[prevIndex]]);
+        if (!numberCopied[p2Follower]) {
+          result[index] = p2Follower;
+        } else {
+          // if that follower has already been added, look for the follower of the last number in parent1
+          int p1Follower = GetFollower(parent1, invParent1[result[prevIndex]]);
+          if (!numberCopied[p1Follower]) {
+            result[index] = p1Follower;
+          } else {
+            // if that has also been added, look for the next not already added number in parent2
+            int tempIndex = index;
+            for (int i = 0; i < parent2.Length; i++) {
+              if (!numberCopied[parent2[tempIndex]]) {
+                result[index] = parent2[tempIndex];
+                break;
+              }
+              tempIndex++;
+              if (tempIndex >= parent2.Length) tempIndex = 0;
+            }
+          }
+        }
+        numberCopied[result[index]] = true;
+        prevIndex = index;
+        index++;
+        if (index >= length) index -= length;
+      } while (index != breakPoint1);
+
+      return result;
+    }
+
+    private static int GetFollower(Permutation parent, int index) {
+      if (index + 1 == parent.Length)
+        return parent[0];
+      return parent[index + 1];
     }
 
     /// <summary>
-    /// Performs a cross over permutation of <paramref name="parent1"/> and <paramref name="parent2"/>
-    /// by preserving a preferably big randomly chosen region of one permutation and taking 
-    /// the missing ones from the other permuation array.
+    /// Checks number of parents and calls <see cref="Apply"/>.
     /// </summary>
-    /// <param name="random">The random number generator.</param>
-    /// <param name="parent1">The permutation array of parent 1.</param>
-    /// <param name="parent2">The permutation array of parent 2.</param>
-    /// <returns>The created cross over permutation as int array.</returns>
-    public static int[] Apply(IRandom random, int[] parent1, int[] parent2) {
-      int length = parent1.Length;
-      int[] result = new int[length];
-      bool[] numberCopied = new bool[length];
-      int breakPoint1, breakPoint2, subsegmentLength, index;
-
-      if (length >= 20) {  // length of subsegment must be >= 10 and <= length / 2
-        breakPoint1 = random.Next(length - 9);
-        subsegmentLength = random.Next(10, Math.Min((int)(length / 2), length - breakPoint1) + 1);
-        breakPoint2 = breakPoint1 + subsegmentLength - 1;
-      } else {
-        breakPoint1 = random.Next(length - 1);
-        breakPoint2 = random.Next(breakPoint1 + 1, length);
-      }
-
-      index = 0;
-      for (int i = breakPoint1; i <= breakPoint2; i++) {  // copy part of first permutation
-        result[index] = parent1[i];
-        numberCopied[result[index]] = true;
-        index++;
-      }
-
-      for (int i = 0; i < parent2.Length; i++) {  // copy remaining part of second permutation
-        if (!numberCopied[parent2[i]]) {
-          result[index] = parent2[i];
-          index++;
-        }
-      }
-      return result;
-    }
-
-    /// <summary>
-    /// Performs a maximal preservative crossover operation for two given parent permutations.
-    /// </summary>
-    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two parents.</exception>
+    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
     /// <param name="scope">The current scope.</param>
     /// <param name="random">A random number generator.</param>
     /// <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 MaximalPreservativeCrossover: 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("MaximalPreservativeCrossover: Number of parents is not equal to 2.");
       return Apply(random, parents[0], parents[1]);
     }

trunk/sources/HeuristicLab.Permutation/3.3/PartiallyMatchedCrossover.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 permuation arrays
-  /// by taking a randomly chosen interval from the first, keeping the position, 
-  /// then all positions from the second permutation which are still free in the child 
-  /// (the position is free and the value is "free")
-  /// and then missing ones from the second array in the order they occur in the second array.
-  /// </summary>
-  public class PartiallyMatchedCrossover : PermutationCrossoverBase {
-    /// <inheritdoc select="summary"/>
-    public override string Description {
-      get { return @"TODO\r\nOperator description still missing ..."; }
-    }
-
+  /// An operator which performs the partially matched crossover on two permutations.
+  /// </summar>
+  /// <remarks>
+  /// Implemented as described in Fogel, D.B. 1988. An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics, 60, pp. 139-144, Springer-Verlag.
+  /// which references Goldberg, D.E., and Lingle, R. 1985. Alleles, loci, and the traveling salesman problem. Proceedings of an International Conference on Genetic Algorithms and their Applications. Carnegie-Mellon University, pp. 154-159.
+  /// as the original source of the operator.
+  /// </remarks>
+  [Item("PartiallyMatchedCrossover", "An operator which performs the partially matched crossover on two permutations.")]
+  [EmptyStorableClass]
+  [Creatable("Test")]
+  public class PartiallyMatchedCrossover : PermutationCrossover {
     /// <summary>
-    /// Performs a cross over permuation of <paramref name="parent1"/> and <paramref name="parent2"/>
-    /// by taking a randomly chosen interval from <paramref name="parent1"/>, preserving the position, 
-    /// then all positions from <paramref name="parent2"/> which are still free in the child 
-    /// (the position is free and the value is "free")
-    /// and then missing ones from <paramref name="parent2"/> in the order they occur 
-    /// in <paramref name="parent2"/>.
+    /// Performs the partially matched crossover on <paramref name="parent1"/> and <paramref name="parent2"/>.
     /// </summary>
-    /// <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) {
+    /// <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.
+    /// </remarks>
+    /// <param name="random">A random number generator.</param>
+    /// <param name="parent1">The first parent permutation to cross.</param>
+    /// <param name="parent2">The second parent permutation to cross.</param>
+    /// <returns>The new permutation resulting from the crossover.</returns>
+    public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
       int length = parent1.Length;
-      int[] result = new int[length];
+      Permutation result = new Permutation(length);
       bool[] numbersCopied = new bool[length];
 
@@ -65 +63 @@
       }
 
-      int index = breakPoint1;
-      int i = (breakPoint1 == 0 ? (breakPoint2 + 1) : 0);
+      // calculate the inverse permutation (number -> index) of parent1
+      int[] invParent1 = new int[length];
+      for (int j = 0; j < length; j++) {
+        invParent1[parent1[j]] = j;
+      }
+
+      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
-          while (numbersCopied[parent2[index]]) {  // find next valid index
-            index++;
-          }
-          result[i] = parent2[index];
-          index++;
+          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
         }
 
@@ -87 +87 @@
 
     /// <summary>
-    /// Performs a partially matched crossover operation for two given parent permutations.
+    /// Checks number of parents and calls <see cref="Apply"/>.
     /// </summary>
-    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two parents.</exception>
+    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
     /// <param name="scope">The current scope.</param>
     /// <param name="random">A random number generator.</param>
     /// <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 PartiallyMatchedCrossover: 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("PartiallyMatchedCrossover: The number of parents is not equal to 2");
       return Apply(random, parents[0], parents[1]);
     }