Changeset 14475 for trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding

Timestamp:

12/12/16 13:53:16 (8 years ago)

Author:

sraggl

Message:

#2666
Updated LinearLinkageEncoding by:

• Speeding up GroupCrossover and SetGroups and GetGroups
• making Constructor private adding static initializer Methods

Location:

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3

Files:

• Creators/ExactGroupsLinearLinkageCreator.cs (modified) (2 diffs)
• Creators/MaxGroupsLinearLinkageCreator.cs (modified) (1 diff)
• Creators/RandomLinearLinkageCreator.cs (modified) (1 diff)
• Crossovers/GreedyPartitionCrossover.cs (modified) (2 diffs)
• Crossovers/GroupCrossover.cs (modified) (1 diff)
• Crossovers/LowestIndexFirstCrossover.cs (modified) (1 diff)
• Crossovers/LowestIndexMaxCrossover.cs (modified) (1 diff)
• Crossovers/SinglePointCrossover.cs (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj (moved) (moved from trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj) (2 diffs)
• LinearLinkage.cs (modified) (7 diffs)
• Plugin.cs.frame (modified) (1 diff)
• Properties/AssemblyInfo.cs.frame (modified) (1 diff)

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/ExactGroupsLinearLinkageCreator.cs ¶

@@ -56 +56 @@
 
     public static LinearLinkage Apply(IRandom random, int length, int groups) {
-      var solution = new LinearLinkage(length);
       var groupNumbers = Enumerable.Range(0, length).Select(x => x % groups).Shuffle(random);
       var grouping = Enumerable.Range(0, groups).Select(x => new List<int>()).ToList();
@@ -63 +62 @@
         grouping[g].Add(idx++);
 
-      solution.SetGroups(grouping);
-      return solution;
+      return LinearLinkage.FromGroups(length, grouping);
     }
 

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/MaxGroupsLinearLinkageCreator.cs ¶

@@ -55 +55 @@
 
     public static LinearLinkage Apply(IRandom random, int length, int maxGroups) {
-      var solution = new LinearLinkage(length);
       var groups = Enumerable.Range(0, length).Select(x => Tuple.Create(x, random.Next(maxGroups)))
                                               .GroupBy(x => x.Item2)
                                               .Select(x => x.Select(y => y.Item1).ToList());
-      solution.SetGroups(groups);
-      return solution;
+      return LinearLinkage.FromGroups(length, groups);
     }
 

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/RandomLinearLinkageCreator.cs ¶

@@ -41 +41 @@
 
     public static LinearLinkage Apply(IRandom random, int length) {
-      var solution = new LinearLinkage(length);
       var groups = Enumerable.Range(0, length).Select(x => Tuple.Create(x, random.Next(length)))
                                               .GroupBy(x => x.Item2)
                                               .Select(x => x.Select(y => y.Item1).ToList());
-      solution.SetGroups(groups);
-      return solution;
+      return LinearLinkage.FromGroups(length, groups);
     }
 

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GreedyPartitionCrossover.cs ¶

@@ -44 +44 @@
     public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) {
       var len = parents[0].Length;
-
-      var child = new LinearLinkage(len);
       var childGroup = new List<HashSet<int>>();
       var currentParent = random.Next(parents.Length);
@@ -69 +67 @@
       } while (remaining);
 
-      child.SetGroups(childGroup);
-      return child;
+      return LinearLinkage.FromGroups(len, childGroup);
     }
 

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GroupCrossover.cs ¶

@@ -39 +39 @@
       return new GroupCrossover(this, cloner);
     }
-
+    
     public static LinearLinkage Apply(IRandom random, LinearLinkage p1, LinearLinkage p2) {
       var length = p1.Length;
-      var child = new LinearLinkage(length);
-      var endNodes = new HashSet<int>();
-      for (var i = 0; i < length; i++) {
-        if ((p1[i] == i && p2[i] == i)
-          || ((p1[i] == i || p2[i] == i) && random.NextDouble() < 0.5)) {
-          child[i] = i;
-          endNodes.Add(i);
+      var lleeP1 = p1.ToEndLinks();
+      var lleeP2 = p2.ToEndLinks();
+      var lleeChild = new int[length];
+      var isTransfered = new bool[length];
+
+      for (var i = p1.Length - 1; i >= 0; i--) {
+        lleeChild[i] = i;
+
+        // Step 1
+        var isEndP1 = p1[i] == i;
+        var isEndP2 = p2[i] == i;
+        if (isEndP1 & isEndP2 || (isEndP1 | isEndP2 && random.NextDouble() < 0.5)) {
+          isTransfered[i] = true;
+          continue;
+        }
+
+        // Step 2
+        var end1 = lleeP1[i];
+        var end2 = lleeP2[i];
+
+        if (isTransfered[end1] & isTransfered[end2]) {
+          var end = random.NextDouble() < 0.5 ? end1 : end2;
+          lleeChild[i] = end;
+        } else if (isTransfered[end1]) {
+          lleeChild[i] = end1;
+        } else if (isTransfered[end2]) {
+          lleeChild[i] = end2;
+        } else {
+          var next = random.NextDouble() < 0.5 ? p1[i] : p2[i];
+          var end = lleeChild[next];
+          lleeChild[i] = end;
         }
       }
-      for (var i = 0; i < length; i++) {
-        if (endNodes.Contains(i)) continue;
-        var p1End = endNodes.Contains(p1[i]);
-        var p2End = endNodes.Contains(p2[i]);
-        if ((p1End && p2End) || (!p1End && !p2End)) {
-          child[i] = random.NextDouble() < 0.5 ? p1[i] : p2[i];
-        } else if (p1End) {
-          child[i] = p1[i];
-        } else {
-          child[i] = p2[i];
-        }
-      }
-      child.LinearizeTreeStructures();
-      return child;
+      return LinearLinkage.FromEndLinks(lleeChild);
     }
 

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexFirstCrossover.cs ¶

@@ -43 +43 @@
       var len = parents[0].Length;
       var p = random.Next(parents.Length);
-      var child = new LinearLinkage(len);
+      var child = LinearLinkage.SingleElementGroups(len);
       var remaining = new SortedSet<int>(Enumerable.Range(0, len));
       do {

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexMaxCrossover.cs ¶

@@ -44 +44 @@
     public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) {
       var len = parents[0].Length;
-      var child = new LinearLinkage(len);
+      var child = LinearLinkage.SingleElementGroups(len);
       var remaining = new SortedSet<int>(Enumerable.Range(0, len));
       do {

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/SinglePointCrossover.cs ¶

@@ -41 +41 @@
     public static LinearLinkage Apply(IRandom random, LinearLinkage p1, LinearLinkage p2) {
       var length = p1.Length;
-      var child = new LinearLinkage(length);
+      var child = LinearLinkage.SingleElementGroups(length);
       var bp = random.Next(length - 1);
       for (var i = 0; i <= bp; i++) child[i] = p1[i];

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj ¶

@@ -9 +9 @@
     <AppDesignerFolder>Properties</AppDesignerFolder>
     <RootNamespace>HeuristicLab.Encodings.LinearLinkageEncoding</RootNamespace>
-    <AssemblyName>HeuristicLab.Encodings.LinearLinkageEncoding-3.3</AssemblyName>
+    <AssemblyName>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</AssemblyName>
     <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
     <FileAlignment>512</FileAlignment>
@@ -156 +156 @@
   <ItemGroup>
     <Compile Include="Creators\ExactGroupsLinearLinkageCreator.cs" />
+    <Compile Include="Creators\MaxGroupSizeLinearLinkageCreator.cs" />
     <Compile Include="Creators\MaxGroupsLinearLinkageCreator.cs" />
     <Compile Include="Creators\RandomLinearLinkageCreator.cs" />

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs ¶

@@ -37 +37 @@
     private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { }
     public LinearLinkage() { }
-    public LinearLinkage(int length) : base(length) { }
-    public LinearLinkage(int[] elements) : base(elements) { }
+
+    private LinearLinkage(int length) : base(length) { }
+    private LinearLinkage(int[] elements) : base(elements) { }
+
+    /// <summary>
+    /// Create a new LinearLinkage object where every element is in a seperate group.
+    /// </summary>
+    public static LinearLinkage SingleElementGroups(int length) {
+      var elements = new int[length];
+      for (var i = 0; i < length; i++) {
+        elements[i] = i;
+      }
+      return new LinearLinkage(elements);
+    }
+
+    /// <summary>
+    /// Create a new LinearLinkage object from an int[] in LLE
+    /// </summary>
+    /// <remarks>
+    /// This operation checks if the argument is a well formed LLE
+    /// and throws an ArgumentException otherwise.
+    /// </remarks>
+    /// <param name="lle">The LLE representation</param>
+    public static LinearLinkage FromForwardLinks(int[] lle) {
+      if (!Validate(lle)) {
+        throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
+      }
+      return new LinearLinkage(lle);
+    }
+
+    /// <summary>
+    /// Create a new LinearLinkage object by parsing an LLE-e representation
+    /// and modifing 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 int[].
+    /// </remarks>
+    /// <param name="llee">The LLE-e representation</param>
+    /// <returns>LinearLinkage</returns>
+    public static LinearLinkage FromEndLinks(int[] llee) {
+      var result = new LinearLinkage(llee.Length);
+      result.SetEndLinks(llee);
+      return result;
+    }
+
+    /// <summary>
+    /// Create a new LinearLinkage object by translating
+    /// an enumeration of groups into the underlying array representation.
+    /// </summary>
+    /// <remarks>
+    /// Throws an ArgumentException when there is an element assigned to
+    /// multiple groups or elements that are not assigned to any group.
+    /// </remarks>
+    /// <param name="grouping">The grouping of the elements, each element must
+    /// be part of exactly one group.</param>
+    public static LinearLinkage FromGroups(int length, IEnumerable<IEnumerable<int>> grouping) {
+      var result = new LinearLinkage(length);
+      result.SetGroups(grouping);
+      return result;
+    }
 
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -55 +114 @@
     public IEnumerable<List<int>> GetGroups() {
       var len = array.Length;
-      var remaining = new HashSet<int>(Enumerable.Range(0, len));
+      var used = new bool[len];
+      for (var i = 0; i < len; i++) {
+        if (used[i]) continue;
+        var curr = i;
+        var next = array[curr];
+        var group = new List<int> { curr };
+        while (next > curr && next < len && !used[next]) {
+          used[curr] = true;
+          curr = next;
+          next = array[next];
+          group.Add(curr);
+        }
+        if (curr != next) throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
+        used[curr] = true;
+        yield return group;
+      }
+      /*
+      var len = array.Length;
+      var used = new bool[len];
       // iterate from lowest to highest index
       for (var i = 0; i < len; i++) {
-        if (!remaining.Contains(i)) continue;
+        if (used[i]) continue;
         var group = new List<int> { i };
-        remaining.Remove(i);
+        used[i] = true;
         var next = array[i];
-        if (next != i) {
-          int prev;
-          do {
-            group.Add(next);
-            if (!remaining.Remove(next))
-              throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
-            prev = next;
-            next = array[next];
-          } while (next != prev);
+        if (next < i || next >= len) {
+          throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
+        }
+        while (next != array[next]) {
+          if (next < 0 || next >= len || used[next]) {
+            throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
+          }
+          group.Add(next);
+          used[next] = true;
+          next = array[next];
         }
         yield return group;
-      }
+      }*/
     }
 
@@ -151 +229 @@
     public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
       var len = array.Length;
-      var remaining = new HashSet<int>(Enumerable.Range(0, len));
+      var used = new bool[len];
       foreach (var group in grouping) {
         var prev = -1;
         foreach (var g in group.OrderBy(x => x)) {
+          if (g < prev || g >= len) throw new ArgumentException(string.Format("Element {0} is bigger than {1} or smaller than 0.", g, len - 1), "grouping");
           if (prev >= 0) array[prev] = g;
           prev = g;
-          if (!remaining.Remove(prev))
+          if (used[prev]) {
             throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
-        }
-        if (prev >= 0) array[prev] = prev;
-      }
-      if (remaining.Count > 0)
-        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
+          }
+          used[prev] = true;
+        }
+        array[prev] = prev;
+      }
+      if (!used.All(x => x))
+        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", used.Select((x, i) => new { x, i }).Where(x => !x.x).Select(x => x.i))));
     }
 
@@ -175 +256 @@
     /// <returns>True if the encoding is valid.</returns>
     public bool Validate() {
+      return Validate(array);
+    }
+
+    private static bool Validate(int[] array) {
       var len = array.Length;
-      var remaining = new HashSet<int>(Enumerable.Range(0, len));
+      var used = new bool[len];
       for (var i = 0; i < len; i++) {
-        if (!remaining.Contains(i)) continue;
-        remaining.Remove(i);
-        var next = array[i];
-        if (next == i) continue;
-        int prev;
-        do {
-          if (!remaining.Remove(next)) return false;
-          prev = next;
+        if (used[i]) continue;
+        var curr = i;
+        var next = array[curr];
+        while (next > curr && next < len && !used[next]) {
+          used[curr] = true;
+          curr = next;
           next = array[next];
-        } while (next != prev);
-      }
-      return remaining.Count == 0;
+        }
+        if (curr!=next) return false;
+        used[curr] = true;
+      }
+      return true;
     }
 
@@ -216 +301 @@
     public void LinearizeTreeStructures() {
       // Step 1: Convert the array into LLE-e
-      ToLLEeInplace(array);
+      ToEndLinksInplace(array);
       // Step 2: For all groups linearize the links
-      FromLLEe(array);
+      SetEndLinks(array);
     }
 
@@ -233 +318 @@
     /// </remarks>
     /// <returns>An integer array in LLE-e representation</returns>
-    public int[] ToLLEe() {
+    public int[] ToEndLinks() {
       var result = (int[])array.Clone();
-      ToLLEeInplace(result);
+      ToEndLinksInplace(result);
       return result;
     }
 
-    private void ToLLEeInplace(int[] a) {
-      var length = a.Length;
+    private static void ToEndLinksInplace(int[] array) {
+      var length = array.Length;
       for (var i = length - 1; i >= 0; i--) {
-        if (array[i] == i) a[i] = i;
-        else a[i] = a[a[i]];
+        var next = array[i];
+        if (next > i) {
+          array[i] = array[next];
+        } else if (next < i) {
+          throw new ArgumentException("Array is malformed and does not represent a valid LLE encoding.", "array");
+        }
       }
     }
@@ -253 +342 @@
     /// <remarks>
     /// This operation runs in O(n) time, but requires additional memory
-    /// in form of a dictionary.
+    /// in form of a int[].
     /// </remarks>
     /// <param name="llee">The LLE-e representation</param>
-    public void FromLLEe(int[] llee) {
+    public void SetEndLinks(int[] llee) {
       var length = array.Length;
-      var groups = new Dictionary<int, int>();
+      if (length != llee.Length) {
+        throw new ArgumentException(string.Format("Expected length {0} but length was {1}", length, llee.Length), "llee");
+      }
+      // If we are ok with mutating llee we can avoid this clone
+      var lookup = (int[])llee.Clone();
       for (var i = length - 1; i >= 0; i--) {
-        if (llee[i] == i) {
-          array[i] = i;
-          groups[i] = i;
+        var end = llee[i];
+        if (end == i) {
+          array[i] = end;
+        } else if (end > i && end < length) {
+          array[i] = lookup[end];
+          lookup[end] = i;
         } else {
-          var g = llee[i];
-          array[i] = groups[g];
-          groups[g] = i;
+          throw new ArgumentException("Array is malformed and does not represent a valid LLE end encoding.", "llee");
         }
       }

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Plugin.cs.frame ¶

@@ -23 +23 @@
 
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
-  [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.3.14.$WCREV$")]
-  [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.3.dll", PluginFileType.Assembly)]
+  [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.4.14.$WCREV$")]
+  [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.4.dll", PluginFileType.Assembly)]
   [PluginDependency("HeuristicLab.Collections", "3.3")]
   [PluginDependency("HeuristicLab.Common", "3.3")]

trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Properties/AssemblyInfo.cs.frame ¶

@@ -53 +53 @@
 // by using the '*' as shown below:
 // [assembly: AssemblyVersion("1.0.*")]
-[assembly: AssemblyVersion("3.3.0.0")]
-[assembly: AssemblyFileVersion("3.3.14.$WCREV$")]
+[assembly: AssemblyVersion("3.4.0.0")]
+[assembly: AssemblyFileVersion("3.4.14.$WCREV$")]