Changeset 12396

Timestamp:

05/21/15 16:30:14 (10 years ago)

Author:

abeham

Message:

#2319: Added SinglePointCrossover

Location:

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3

Files:

• Crossovers/SinglePointCrossover.cs (added)
• HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj (modified) (1 diff)
• LinearLinkage.cs (modified) (3 diffs)
• Manipulators/GraftManipulator.cs (modified) (5 diffs)
• Manipulators/MergeGroupManipulator.cs (modified) (1 diff)
• Manipulators/MoveItemManipulator.cs (modified) (1 diff)
• Manipulators/SplitGroupManipulator.cs (modified) (1 diff)
• Manipulators/SwapItemManipulator.cs (modified) (1 diff)

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj

@@ -107 +107 @@
     <Compile Include="Crossovers\LowestIndexMaxCrossover.cs" />
     <Compile Include="Crossovers\MultiLLECrossover.cs" />
+    <Compile Include="Crossovers\SinglePointCrossover.cs" />
     <Compile Include="Interfaces\ILinearLinkageCreator.cs" />
     <Compile Include="LinearLinkage.cs" />

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs

@@ -182 +182 @@
     /// These tree structures may be created by e.g. merging two groups by
     /// linking one end node to the end node of another.
-    /// Consider following example: 6, 6, 7, 5, 5, 8, 8, 8, 9.
+    /// Consider following 1-based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9.
     /// This results in the following tree structure for group 8:
     ///      8
     ///    /   \
     ///   6     7
-    ///  / \
-    /// 1   2
+    ///  / \    |
+    /// 1   2   3
     /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
+    /// Representing a tree with one branch: 1 -> 2 -> 3 -> 6 -> 7 -> 8
     /// </summary>
     /// <remarks>
@@ -195 +196 @@
     /// linearizes the links. This requires two passes of the whole array
     /// as well as a dictionary to hold the smallest index of each group.
+    /// The runtime complexity is O(n).
     /// 
     /// The method assumes that there are no back links present.
@@ -200 +202 @@
     public void LinearizeTreeStructures() {
       // Step 1: Convert the array into LLE-e
+      ToLLEeInplace(array);
+      // Step 2: For all groups linearize the links
+      FromLLEe(array);
+    }
+
+    /// <summary>
+    /// Creates a copy of the underlying array and turns it into LLE-e.
+    /// </summary>
+    /// <remarks>
+    /// LLE-e is a special format where each element points to the
+    /// ending item of a group.
+    /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become 
+    /// 5, 5, 5, 8, 5, 8, 8, 8 in LLE-e.
+    /// 
+    /// This operation runs in O(n) time.
+    /// </remarks>
+    /// <returns>An integer array in LLE-e representation</returns>
+    public int[] ToLLEe() {
+      var result = (int[])array.Clone();
+      ToLLEeInplace(result);
+      return result;
+    }
+
+    private void ToLLEeInplace(int[] a) {
+      var length = a.Length;
+      for (var i = length - 1; i >= 0; i--) {
+        if (array[i] == i) a[i] = i;
+        else a[i] = a[a[i]];
+      }
+    }
+
+    /// <summary>
+    /// Parses an LLE-e representation and modifies the underlying array
+    /// so that it is in LLE representation.
+    /// </summary>
+    /// <remarks>
+    /// This operation runs in O(n) time, but requires additional memory
+    /// in form of a dictionary.
+    /// </remarks>
+    /// <param name="llee">The LLE-e representation</param>
+    public void FromLLEe(int[] llee) {
       var length = array.Length;
       var groups = new Dictionary<int, int>();
       for (var i = length - 1; i >= 0; i--) {
-        if (array[i] == i) groups[i] = i;
-        else array[i] = array[array[i]];
-      }
-      // Step 2: For all groups linearize the links
-      for (var i = length - 1; i >= 0; i--) {
-        if (array[i] == i) continue;
-        var g = array[i];
-        array[i] = groups[g];
-        groups[g] = i;
+        if (llee[i] == i) {
+          array[i] = i;
+          groups[i] = i;
+        } else {
+          var g = llee[i];
+          array[i] = groups[g];
+          groups[g] = i;
+        }
       }
     }

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/GraftManipulator.cs

@@ -24 +24 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
-using HeuristicLab.Data;
-using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
@@ -33 +31 @@
   public sealed class GraftManipulator : LinearLinkageManipulator {
 
-    public IValueLookupParameter<IntValue> MaxGroupsParameter {
-      get { return (IValueLookupParameter<IntValue>)Parameters["MaxGroups"]; }
-    }
-
     [StorableConstructor]
     private GraftManipulator(bool deserializing) : base(deserializing) { }
     private GraftManipulator(GraftManipulator original, Cloner cloner) : base(original, cloner) { }
-    public GraftManipulator() {
-      Parameters.Add(new ValueLookupParameter<IntValue>("MaxGroups", "The maximum number of groups. If a value less or equal than 0 is used the number of groups is not limited.", new IntValue(-1)));
-    }
-    public GraftManipulator(int maxGroups)
-      : this() {
-      MaxGroupsParameter.Value = new IntValue(maxGroups);
-    }
+    public GraftManipulator() { }
 
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -52 +40 @@
     }
 
-    public static void Apply(IRandom random, LinearLinkage lle, int maxGroups) {
+    public static void Apply(IRandom random, LinearLinkage lle) {
       int tries = lle.Length;
       var index = random.Next(lle.Length);
@@ -59 +47 @@
         tries--;
       }
-      if (lle[index] != index) Apply(random, lle, maxGroups, index);
+      if (lle[index] != index) Apply(random, lle, index);
     }
 
-    public static void Apply(IRandom random, LinearLinkage lle, int maxGroups, int index) {
+    public static void Apply(IRandom random, LinearLinkage lle, int index) {
       var groups = lle.Select((val, idx) => Tuple.Create(idx, val))
                       .Where(x => x.Item1 == x.Item2)
@@ -84 +72 @@
 
     protected override void Manipulate(IRandom random, LinearLinkage lle) {
-      var maxGroups = MaxGroupsParameter.ActualValue.Value;
-      Apply(random, lle, maxGroups <= 0 ? int.MaxValue : maxGroups);
+      Apply(random, lle);
     }
   }

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/MergeGroupManipulator.cs

@@ -28 +28 @@
 
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
-  [Item("Merge Group Manipulator", "Performs a maximum of N merge operations on the groups. Groups may be merged multiple times.")]
+  [Item("Merge Group Manipulator", "Performs a maximum of N merge operations on the groups. An already merged group may be merged again.")]
   [StorableClass]
   public sealed class MergeGroupManipulator : LinearLinkageManipulator {

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/MoveItemManipulator.cs

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
-  [Item("Move Item Manipulator", "Performs a maximum of N move operations between groups or to new groups. Items may be moved multiple times.")]
+  [Item("Move Item Manipulator", "Performs a maximum of N move operations between groups or to new groups. An already moved item may be moved again.")]
   [StorableClass]
   public sealed class MoveItemManipulator : LinearLinkageManipulator {

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/SplitGroupManipulator.cs

@@ -31 +31 @@
 
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
-  [Item("Split Group Manipulator", "Performs a maximum of N split operations on the groups. Groups may be split multiple times.")]
+  [Item("Split Group Manipulator", "Performs a maximum of N split operations on the groups. An already split group may be split again.")]
   [StorableClass]
   public sealed class SplitGroupManipulator : LinearLinkageManipulator {

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/SwapItemManipulator.cs

@@ -28 +28 @@
 
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
-  [Item("Swap Item Manipulator", "Swaps items between groups. Items may be swapped multiple times.")]
+  [Item("Swap Item Manipulator", "Performs N swaps operations of two items each. The same items may be swapped multiple times, at least two groups need to be present.")]
   [StorableClass]
   public sealed class SwapItemManipulator : LinearLinkageManipulator {