Changeset 14487

Timestamp:

12/14/16 10:16:50 (8 years ago)

Author:

sraggl

Message:

#2701 Merged with trunk to get new version of LinearLinkageEncoding
Improved MoveGenerator

Location:

branches/MemPRAlgorithm

Files:

• HeuristicLab 3.3.sln (modified) (5 diffs)
• HeuristicLab.Algorithms.MemPR/3.3/HeuristicLab.Algorithms.MemPR-3.3.csproj (modified) (1 diff)
• HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs (modified) (1 diff)
• HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnivariateSolutionModel.cs (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding (modified) (1 prop)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/ExactGroupsLinearLinkageCreator.cs (modified) (2 diffs)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/MaxGroupSizeLinearLinkageCreator.cs (copied) (copied from trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/MaxGroupSizeLinearLinkageCreator.cs)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/MaxGroupsLinearLinkageCreator.cs (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/RandomLinearLinkageCreator.cs (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GreedyPartitionCrossover.cs (modified) (2 diffs)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GroupCrossover.cs (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexFirstCrossover.cs (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexMaxCrossover.cs (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/SinglePointCrossover.cs (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj (copied) (copied from trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj) (2 diffs)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs (modified) (7 diffs)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Moves/StaticAPI/MoveGenerator.cs (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Plugin.cs.frame (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Properties/AssemblyInfo.cs.frame (modified) (1 diff)
• HeuristicLab.PluginInfrastructure/3.3/Manager/PluginValidator.cs (modified) (2 diffs)
• HeuristicLab.Problems.GraphColoring/3.3/GraphColoringProblem.cs (modified) (2 diffs)
• HeuristicLab.Problems.GraphColoring/3.3/HeuristicLab.Problems.GraphColoring-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.Programmable/3.3/HeuristicLab.Problems.Programmable-3.3.csproj (modified) (1 diff)

branches/MemPRAlgorithm/HeuristicLab 3.3.sln

@@ -80 +80 @@
     {3B90F866-70F8-43EF-A541-51819D255B7B} = {3B90F866-70F8-43EF-A541-51819D255B7B}
     {07486E68-1517-4B9D-A58D-A38E99AE71AB} = {07486E68-1517-4B9D-A58D-A38E99AE71AB}
-    {BE698769-975A-429E-828C-72BB2B6182C8} = {BE698769-975A-429E-828C-72BB2B6182C8}
     {4AE3FC69-C575-42D2-BC46-0FAD5850EFC5} = {4AE3FC69-C575-42D2-BC46-0FAD5850EFC5}
     {56F9106A-079F-4C61-92F6-86A84C2D84B7} = {56F9106A-079F-4C61-92F6-86A84C2D84B7}
@@ -423 +422 @@
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.CMAEvolutionStrategy-3.4", "HeuristicLab.Algorithms.CMAEvolutionStrategy\3.4\HeuristicLab.Algorithms.CMAEvolutionStrategy-3.4.csproj", "{291010E4-2F4E-4D29-A795-753CFF293FDB}"
 EndProject
-Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.LinearLinkageEncoding-3.3", "HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj", "{BE698769-975A-429E-828C-72BB2B6182C8}"
-EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Orienteering-3.3", "HeuristicLab.Problems.Orienteering\3.3\HeuristicLab.Problems.Orienteering-3.3.csproj", "{D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}"
 EndProject
@@ -458 +455 @@
 EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Instances.DIMACS-3.3", "HeuristicLab.Problems.Instances.DIMACS\3.3\HeuristicLab.Problems.Instances.DIMACS-3.3.csproj", "{9943FF23-8619-459C-B84A-E7FBDCBA04E6}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.LinearLinkageEncoding-3.4", "HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj", "{166507C9-EF26-4370-BB80-699742A29D4F}"
 EndProject
 Global
@@ -2017 +2016 @@
     {291010E4-2F4E-4D29-A795-753CFF293FDB}.Release|x86.ActiveCfg = Release|x86
     {291010E4-2F4E-4D29-A795-753CFF293FDB}.Release|x86.Build.0 = Release|x86
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|Any CPU.Build.0 = Debug|Any CPU
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x64.ActiveCfg = Debug|x64
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x64.Build.0 = Debug|x64
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x86.ActiveCfg = Debug|x86
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x86.Build.0 = Debug|x86
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Release|Any CPU.ActiveCfg = Release|Any CPU
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Release|Any CPU.Build.0 = Release|Any CPU
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x64.ActiveCfg = Release|x64
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x64.Build.0 = Release|x64
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x86.ActiveCfg = Release|x86
-    {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x86.Build.0 = Release|x86
     {D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     {D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}.Debug|Any CPU.Build.0 = Debug|Any CPU
@@ -2233 +2220 @@
     {9943FF23-8619-459C-B84A-E7FBDCBA04E6}.Release|x86.ActiveCfg = Release|Any CPU
     {9943FF23-8619-459C-B84A-E7FBDCBA04E6}.Release|x86.Build.0 = Release|Any CPU
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|Any CPU.Build.0 = Debug|Any CPU
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x64.ActiveCfg = Debug|x64
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x64.Build.0 = Debug|x64
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x86.ActiveCfg = Debug|x86
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x86.Build.0 = Debug|x86
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|Any CPU.ActiveCfg = Release|Any CPU
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|Any CPU.Build.0 = Release|Any CPU
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x64.ActiveCfg = Release|x64
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x64.Build.0 = Release|x64
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x86.ActiveCfg = Release|x86
+    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x86.Build.0 = Release|x86
   EndGlobalSection
   GlobalSection(SolutionProperties) = preSolution

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/HeuristicLab.Algorithms.MemPR-3.3.csproj

@@ -162 +162 @@
       <Private>False</Private>
     </ProjectReference>
-    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj">
-      <Project>{BE698769-975A-429E-828C-72BB2B6182C8}</Project>
-      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.3</Name>
-      <Private>False</Private>
+    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
+      <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project>
+      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name>
     </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj">

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs

@@ -250 +250 @@
       var p1 = p1Scope.Solution;
       var p2 = p2Scope.Solution;
-      var transfered = new bool[p1.Length];
-      var subspace = new bool[p1.Length];
-      var lleeChild = new int[p1.Length];
-      var lleep1 = p1.ToLLEe();
-      var lleep2 = p2.ToLLEe();
-      for (var i = p1.Length - 1; i >= 0; i--) {
-        // Step 1
-        subspace[i] = p1[i] != p2[i];
-        var p1IsEnd = p1[i] == i;
-        var p2IsEnd = p2[i] == i;
-        if (p1IsEnd & p2IsEnd) {
-          transfered[i] = true;
-        } else if (p1IsEnd | p2IsEnd) {
-          transfered[i] = Context.Random.NextDouble() < 0.5;
-        }
-        lleeChild[i] = i;
-
-        // Step 2
-        if (transfered[i]) continue;
-        var end1 = lleep1[i];
-        var end2 = lleep2[i];
-        var containsEnd1 = transfered[end1];
-        var containsEnd2 = transfered[end2];
-        if (containsEnd1 & containsEnd2) {
-          if (Context.Random.NextDouble() < 0.5) {
-            lleeChild[i] = end1;
-          } else {
-            lleeChild[i] = end2;
-          }
-        } else if (containsEnd1) {
-          lleeChild[i] = end1;
-        } else if (containsEnd2) {
-          lleeChild[i] = end2;
-        } else {
-          if (Context.Random.NextDouble() < 0.5) {
-            lleeChild[i] = lleeChild[p1[i]];
-          } else {
-            lleeChild[i] = lleeChild[p2[i]];
-          }
-        }
-      }
-      var child = new Encodings.LinearLinkageEncoding.LinearLinkage(lleeChild.Length);
-      child.FromLLEe(lleeChild);
-      
-      return ToScope(child);
+      return ToScope(GroupCrossover.Apply(Context.Random, p1, p2));
     }
 

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnivariateSolutionModel.cs

@@ -63 +63 @@
     public Encodings.LinearLinkageEncoding.LinearLinkage Sample() {
       var N = Frequencies.Rows;
-      var centroid = new Encodings.LinearLinkageEncoding.LinearLinkage(N);
+      var centroid = Encodings.LinearLinkageEncoding.LinearLinkage.SingleElementGroups(N);
       var dict = new Dictionary<int, int>();
       for (var i = N - 1; i >= 0; i--) {

branches/MemPRAlgorithm/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);
     }
 

branches/MemPRAlgorithm/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);
     }
 

branches/MemPRAlgorithm/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);
     }
 

branches/MemPRAlgorithm/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);
     }
 

branches/MemPRAlgorithm/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);
     }
 

branches/MemPRAlgorithm/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 {

branches/MemPRAlgorithm/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 {

branches/MemPRAlgorithm/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];

branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj

@@ -5 +5 @@
     <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
     <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
-    <ProjectGuid>{BE698769-975A-429E-828C-72BB2B6182C8}</ProjectGuid>
+    <ProjectGuid>{166507C9-EF26-4370-BB80-699742A29D4F}</ProjectGuid>
     <OutputType>Library</OutputType>
     <AppDesignerFolder>Properties</AppDesignerFolder>
@@ -183 +183 @@
     <Compile Include="Moves\Swap\Swap2MoveMaker.cs" />
     <Compile Include="ShakingOperators\LLEShakingOperator.cs" />
+    <Compile Include="SimilarityCalculators\HammingSimilarityCalculator.cs" />
     <None Include="HeuristicLab.snk" />
     <None Include="Plugin.cs.frame" />

branches/MemPRAlgorithm/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");
         }
       }

branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Moves/StaticAPI/MoveGenerator.cs

@@ -45 +45 @@
             yield return new MergeMove(i, l.Key);
           }
+        } else {
+          // Fourth: extract i into group of its own (exclude first, because of Second)
+          yield return new ExtractMove(i, pred, next);
         }
       }
-      if (!isFirst)
-        // Fourth: extract i into group of its own (exclude first, because of Second)
-        yield return new ExtractMove(i, pred, next);
+        
 
     }

branches/MemPRAlgorithm/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")]

branches/MemPRAlgorithm/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$")]

branches/MemPRAlgorithm/HeuristicLab.PluginInfrastructure/3.3/Manager/PluginValidator.cs

@@ -260 +260 @@
         }
         // ignore exceptions. Just don't yield a plugin description when an exception is thrown
-        catch (FileNotFoundException) {
+        catch (FileNotFoundException e) {
         }
         catch (FileLoadException) {
@@ -468 +468 @@
         // if the dependency is already disabled we can ignore the cycle detection because we will disable the plugin anyway
         // if following one of the dependencies recursively leads to a cycle then we also return
-        if (dep == plugin || dep.PluginState == PluginState.Disabled || HasCycleInDependencies(plugin, dep.Dependencies)) return true;
+        if (dep == plugin || dep.PluginState == PluginState.Disabled || HasCycleInDependencies(plugin, dep.Dependencies))
+          return true;
       }
       // no cycle found and none of the direct and indirect dependencies is disabled

branches/MemPRAlgorithm/HeuristicLab.Problems.GraphColoring/3.3/GraphColoringProblem.cs

@@ -114 +114 @@
       var fitFun = FitnessFunctionParameter.Value.Value;
       var adjList = adjacencyListParameter.Value;
-      var lle = individual.LinearLinkage(Encoding.Name).ToLLEe(); // LLE-e encoding uses the highest indexed member as group number
+      var lle = individual.LinearLinkage(Encoding.Name).ToEndLinks(); // LLE-e encoding uses the highest indexed member as group number
 
       switch (fitFun) {
@@ -158 +158 @@
 
       var adjList = AdjacencyListParameter.Value;
-      var lle = best.ToLLEe();
+      var lle = best.ToEndLinks();
       var conflicts = 0;
       var colors = lle.Distinct().Count();

branches/MemPRAlgorithm/HeuristicLab.Problems.GraphColoring/3.3/HeuristicLab.Problems.GraphColoring-3.3.csproj

@@ -88 +88 @@
       <Private>False</Private>
     </ProjectReference>
-    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj">
-      <Project>{be698769-975a-429e-828c-72bb2b6182c8}</Project>
-      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.3</Name>
-      <Private>False</Private>
+    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
+      <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project>
+      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name>
     </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Operators\3.3\HeuristicLab.Operators-3.3.csproj">

branches/MemPRAlgorithm/HeuristicLab.Problems.Programmable/3.3/HeuristicLab.Problems.Programmable-3.3.csproj

@@ -149 +149 @@
       <Name>HeuristicLab.Encodings.IntegerVectorEncoding-3.3</Name>
     </ProjectReference>
-    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj">
-      <Project>{be698769-975a-429e-828c-72bb2b6182c8}</Project>
-      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.3</Name>
-      <Private>False</Private>
+    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
+      <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project>
+      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name>
     </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj">