Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
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/HeuristicLab.Encodings.LinearLinkageEncoding
Files:
13 edited
2 copied

Legend:

Unmodified
Added
Removed
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding

    • Property svn:mergeinfo set to (toggle deleted branches)
      /branches/crossvalidation-2434/HeuristicLab.Encodings.LinearLinkageEncodingmergedeligible
      /stable/HeuristicLab.Encodings.LinearLinkageEncodingmergedeligible
      /trunk/sources/HeuristicLab.Encodings.LinearLinkageEncodingmergedeligible
      /branches/1721-RandomForestPersistence/HeuristicLab.Encodings.LinearLinkageEncoding10321-10322
      /branches/Algorithms.GradientDescent/HeuristicLab.Encodings.LinearLinkageEncoding5516-5520
      /branches/Benchmarking/sources/HeuristicLab.Encodings.LinearLinkageEncoding6917-7005
      /branches/CloningRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding4656-4721
      /branches/CodeEditor/HeuristicLab.Encodings.LinearLinkageEncoding11700-11806
      /branches/DataAnalysis Refactoring/HeuristicLab.Encodings.LinearLinkageEncoding5471-5808
      /branches/DataAnalysis SolutionEnsembles/HeuristicLab.Encodings.LinearLinkageEncoding5815-6180
      /branches/DataAnalysis/HeuristicLab.Encodings.LinearLinkageEncoding4458-4459,​4462,​4464
      /branches/DataPreprocessing/HeuristicLab.Encodings.LinearLinkageEncoding10085-11101
      /branches/GP.Grammar.Editor/HeuristicLab.Encodings.LinearLinkageEncoding6284-6795
      /branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Encodings.LinearLinkageEncoding5060
      /branches/HLScript/HeuristicLab.Encodings.LinearLinkageEncoding10331-10358
      /branches/HeuristicLab.DatasetRefactor/sources/HeuristicLab.Encodings.LinearLinkageEncoding11570-12508
      /branches/HeuristicLab.Problems.DataAnalysis.Trading/HeuristicLab.Encodings.LinearLinkageEncoding6123-9799
      /branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Encodings.LinearLinkageEncoding11130-12721
      /branches/HiveStatistics/sources/HeuristicLab.Encodings.LinearLinkageEncoding12440-12877
      /branches/LogResidualEvaluator/HeuristicLab.Encodings.LinearLinkageEncoding10202-10483
      /branches/NET40/sources/HeuristicLab.Encodings.LinearLinkageEncoding5138-5162
      /branches/NSGA-II Changes/HeuristicLab.Encodings.LinearLinkageEncoding12033-12122
      /branches/ParallelEngine/HeuristicLab.Encodings.LinearLinkageEncoding5175-5192
      /branches/ProblemInstancesRegressionAndClassification/HeuristicLab.Encodings.LinearLinkageEncoding7568-7810
      /branches/QAPAlgorithms/HeuristicLab.Encodings.LinearLinkageEncoding6350-6627
      /branches/Restructure trunk solution/HeuristicLab.Encodings.LinearLinkageEncoding6828
      /branches/RuntimeOptimizer/HeuristicLab.Encodings.LinearLinkageEncoding8943-9078
      /branches/ScatterSearch (trunk integration)/HeuristicLab.Encodings.LinearLinkageEncoding7787-8333
      /branches/SlaveShutdown/HeuristicLab.Encodings.LinearLinkageEncoding8944-8956
      /branches/SpectralKernelForGaussianProcesses/HeuristicLab.Encodings.LinearLinkageEncoding10204-10479
      /branches/SuccessProgressAnalysis/HeuristicLab.Encodings.LinearLinkageEncoding5370-5682
      /branches/Trunk/HeuristicLab.Encodings.LinearLinkageEncoding6829-6865
      /branches/UnloadJobs/HeuristicLab.Encodings.LinearLinkageEncoding9168-9215
      /branches/VNS/HeuristicLab.Encodings.LinearLinkageEncoding5594-5752
      /branches/histogram/HeuristicLab.Encodings.LinearLinkageEncoding5959-6341
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/ExactGroupsLinearLinkageCreator.cs

    r14185 r14487  
    5656
    5757    public static LinearLinkage Apply(IRandom random, int length, int groups) {
    58       var solution = new LinearLinkage(length);
    5958      var groupNumbers = Enumerable.Range(0, length).Select(x => x % groups).Shuffle(random);
    6059      var grouping = Enumerable.Range(0, groups).Select(x => new List<int>()).ToList();
     
    6362        grouping[g].Add(idx++);
    6463
    65       solution.SetGroups(grouping);
    66       return solution;
     64      return LinearLinkage.FromGroups(length, grouping);
    6765    }
    6866
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/MaxGroupsLinearLinkageCreator.cs

    r14185 r14487  
    5555
    5656    public static LinearLinkage Apply(IRandom random, int length, int maxGroups) {
    57       var solution = new LinearLinkage(length);
    5857      var groups = Enumerable.Range(0, length).Select(x => Tuple.Create(x, random.Next(maxGroups)))
    5958                                              .GroupBy(x => x.Item2)
    6059                                              .Select(x => x.Select(y => y.Item1).ToList());
    61       solution.SetGroups(groups);
    62       return solution;
     60      return LinearLinkage.FromGroups(length, groups);
    6361    }
    6462
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/RandomLinearLinkageCreator.cs

    r14185 r14487  
    4141
    4242    public static LinearLinkage Apply(IRandom random, int length) {
    43       var solution = new LinearLinkage(length);
    4443      var groups = Enumerable.Range(0, length).Select(x => Tuple.Create(x, random.Next(length)))
    4544                                              .GroupBy(x => x.Item2)
    4645                                              .Select(x => x.Select(y => y.Item1).ToList());
    47       solution.SetGroups(groups);
    48       return solution;
     46      return LinearLinkage.FromGroups(length, groups);
    4947    }
    5048
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GreedyPartitionCrossover.cs

    r14185 r14487  
    4444    public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) {
    4545      var len = parents[0].Length;
    46 
    47       var child = new LinearLinkage(len);
    4846      var childGroup = new List<HashSet<int>>();
    4947      var currentParent = random.Next(parents.Length);
     
    6967      } while (remaining);
    7068
    71       child.SetGroups(childGroup);
    72       return child;
     69      return LinearLinkage.FromGroups(len, childGroup);
    7370    }
    7471
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GroupCrossover.cs

    r14185 r14487  
    3939      return new GroupCrossover(this, cloner);
    4040    }
    41 
     41   
    4242    public static LinearLinkage Apply(IRandom random, LinearLinkage p1, LinearLinkage p2) {
    4343      var length = p1.Length;
    44       var child = new LinearLinkage(length);
    45       var endNodes = new HashSet<int>();
    46       for (var i = 0; i < length; i++) {
    47         if ((p1[i] == i && p2[i] == i)
    48           || ((p1[i] == i || p2[i] == i) && random.NextDouble() < 0.5)) {
    49           child[i] = i;
    50           endNodes.Add(i);
     44      var lleeP1 = p1.ToEndLinks();
     45      var lleeP2 = p2.ToEndLinks();
     46      var lleeChild = new int[length];
     47      var isTransfered = new bool[length];
     48
     49      for (var i = p1.Length - 1; i >= 0; i--) {
     50        lleeChild[i] = i;
     51
     52        // Step 1
     53        var isEndP1 = p1[i] == i;
     54        var isEndP2 = p2[i] == i;
     55        if (isEndP1 & isEndP2 || (isEndP1 | isEndP2 && random.NextDouble() < 0.5)) {
     56          isTransfered[i] = true;
     57          continue;
     58        }
     59
     60        // Step 2
     61        var end1 = lleeP1[i];
     62        var end2 = lleeP2[i];
     63
     64        if (isTransfered[end1] & isTransfered[end2]) {
     65          var end = random.NextDouble() < 0.5 ? end1 : end2;
     66          lleeChild[i] = end;
     67        } else if (isTransfered[end1]) {
     68          lleeChild[i] = end1;
     69        } else if (isTransfered[end2]) {
     70          lleeChild[i] = end2;
     71        } else {
     72          var next = random.NextDouble() < 0.5 ? p1[i] : p2[i];
     73          var end = lleeChild[next];
     74          lleeChild[i] = end;
    5175        }
    5276      }
    53       for (var i = 0; i < length; i++) {
    54         if (endNodes.Contains(i)) continue;
    55         var p1End = endNodes.Contains(p1[i]);
    56         var p2End = endNodes.Contains(p2[i]);
    57         if ((p1End && p2End) || (!p1End && !p2End)) {
    58           child[i] = random.NextDouble() < 0.5 ? p1[i] : p2[i];
    59         } else if (p1End) {
    60           child[i] = p1[i];
    61         } else {
    62           child[i] = p2[i];
    63         }
    64       }
    65       child.LinearizeTreeStructures();
    66       return child;
     77      return LinearLinkage.FromEndLinks(lleeChild);
    6778    }
    6879
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexFirstCrossover.cs

    r14185 r14487  
    4343      var len = parents[0].Length;
    4444      var p = random.Next(parents.Length);
    45       var child = new LinearLinkage(len);
     45      var child = LinearLinkage.SingleElementGroups(len);
    4646      var remaining = new SortedSet<int>(Enumerable.Range(0, len));
    4747      do {
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexMaxCrossover.cs

    r14185 r14487  
    4444    public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) {
    4545      var len = parents[0].Length;
    46       var child = new LinearLinkage(len);
     46      var child = LinearLinkage.SingleElementGroups(len);
    4747      var remaining = new SortedSet<int>(Enumerable.Range(0, len));
    4848      do {
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/SinglePointCrossover.cs

    r14185 r14487  
    4141    public static LinearLinkage Apply(IRandom random, LinearLinkage p1, LinearLinkage p2) {
    4242      var length = p1.Length;
    43       var child = new LinearLinkage(length);
     43      var child = LinearLinkage.SingleElementGroups(length);
    4444      var bp = random.Next(length - 1);
    4545      for (var i = 0; i <= bp; i++) child[i] = p1[i];
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj

    r14475 r14487  
    55    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
    66    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
    7     <ProjectGuid>{BE698769-975A-429E-828C-72BB2B6182C8}</ProjectGuid>
     7    <ProjectGuid>{166507C9-EF26-4370-BB80-699742A29D4F}</ProjectGuid>
    88    <OutputType>Library</OutputType>
    99    <AppDesignerFolder>Properties</AppDesignerFolder>
     
    183183    <Compile Include="Moves\Swap\Swap2MoveMaker.cs" />
    184184    <Compile Include="ShakingOperators\LLEShakingOperator.cs" />
     185    <Compile Include="SimilarityCalculators\HammingSimilarityCalculator.cs" />
    185186    <None Include="HeuristicLab.snk" />
    186187    <None Include="Plugin.cs.frame" />
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs

    r14185 r14487  
    3737    private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { }
    3838    public LinearLinkage() { }
    39     public LinearLinkage(int length) : base(length) { }
    40     public LinearLinkage(int[] elements) : base(elements) { }
     39
     40    private LinearLinkage(int length) : base(length) { }
     41    private LinearLinkage(int[] elements) : base(elements) { }
     42
     43    /// <summary>
     44    /// Create a new LinearLinkage object where every element is in a seperate group.
     45    /// </summary>
     46    public static LinearLinkage SingleElementGroups(int length) {
     47      var elements = new int[length];
     48      for (var i = 0; i < length; i++) {
     49        elements[i] = i;
     50      }
     51      return new LinearLinkage(elements);
     52    }
     53
     54    /// <summary>
     55    /// Create a new LinearLinkage object from an int[] in LLE
     56    /// </summary>
     57    /// <remarks>
     58    /// This operation checks if the argument is a well formed LLE
     59    /// and throws an ArgumentException otherwise.
     60    /// </remarks>
     61    /// <param name="lle">The LLE representation</param>
     62    public static LinearLinkage FromForwardLinks(int[] lle) {
     63      if (!Validate(lle)) {
     64        throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
     65      }
     66      return new LinearLinkage(lle);
     67    }
     68
     69    /// <summary>
     70    /// Create a new LinearLinkage object by parsing an LLE-e representation
     71    /// and modifing the underlying array so that it is in LLE representation.
     72    /// </summary>
     73    /// <remarks>
     74    /// This operation runs in O(n) time, but requires additional memory
     75    /// in form of a int[].
     76    /// </remarks>
     77    /// <param name="llee">The LLE-e representation</param>
     78    /// <returns>LinearLinkage</returns>
     79    public static LinearLinkage FromEndLinks(int[] llee) {
     80      var result = new LinearLinkage(llee.Length);
     81      result.SetEndLinks(llee);
     82      return result;
     83    }
     84
     85    /// <summary>
     86    /// Create a new LinearLinkage object by translating
     87    /// an enumeration of groups into the underlying array representation.
     88    /// </summary>
     89    /// <remarks>
     90    /// Throws an ArgumentException when there is an element assigned to
     91    /// multiple groups or elements that are not assigned to any group.
     92    /// </remarks>
     93    /// <param name="grouping">The grouping of the elements, each element must
     94    /// be part of exactly one group.</param>
     95    public static LinearLinkage FromGroups(int length, IEnumerable<IEnumerable<int>> grouping) {
     96      var result = new LinearLinkage(length);
     97      result.SetGroups(grouping);
     98      return result;
     99    }
    41100
    42101    public override IDeepCloneable Clone(Cloner cloner) {
     
    55114    public IEnumerable<List<int>> GetGroups() {
    56115      var len = array.Length;
    57       var remaining = new HashSet<int>(Enumerable.Range(0, len));
     116      var used = new bool[len];
     117      for (var i = 0; i < len; i++) {
     118        if (used[i]) continue;
     119        var curr = i;
     120        var next = array[curr];
     121        var group = new List<int> { curr };
     122        while (next > curr && next < len && !used[next]) {
     123          used[curr] = true;
     124          curr = next;
     125          next = array[next];
     126          group.Add(curr);
     127        }
     128        if (curr != next) throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
     129        used[curr] = true;
     130        yield return group;
     131      }
     132      /*
     133      var len = array.Length;
     134      var used = new bool[len];
    58135      // iterate from lowest to highest index
    59136      for (var i = 0; i < len; i++) {
    60         if (!remaining.Contains(i)) continue;
     137        if (used[i]) continue;
    61138        var group = new List<int> { i };
    62         remaining.Remove(i);
     139        used[i] = true;
    63140        var next = array[i];
    64         if (next != i) {
    65           int prev;
    66           do {
    67             group.Add(next);
    68             if (!remaining.Remove(next))
    69               throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
    70             prev = next;
    71             next = array[next];
    72           } while (next != prev);
     141        if (next < i || next >= len) {
     142          throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
     143        }
     144        while (next != array[next]) {
     145          if (next < 0 || next >= len || used[next]) {
     146            throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
     147          }
     148          group.Add(next);
     149          used[next] = true;
     150          next = array[next];
    73151        }
    74152        yield return group;
    75       }
     153      }*/
    76154    }
    77155
     
    151229    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
    152230      var len = array.Length;
    153       var remaining = new HashSet<int>(Enumerable.Range(0, len));
     231      var used = new bool[len];
    154232      foreach (var group in grouping) {
    155233        var prev = -1;
    156234        foreach (var g in group.OrderBy(x => x)) {
     235          if (g < prev || g >= len) throw new ArgumentException(string.Format("Element {0} is bigger than {1} or smaller than 0.", g, len - 1), "grouping");
    157236          if (prev >= 0) array[prev] = g;
    158237          prev = g;
    159           if (!remaining.Remove(prev))
     238          if (used[prev]) {
    160239            throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
    161         }
    162         if (prev >= 0) array[prev] = prev;
    163       }
    164       if (remaining.Count > 0)
    165         throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
     240          }
     241          used[prev] = true;
     242        }
     243        array[prev] = prev;
     244      }
     245      if (!used.All(x => x))
     246        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))));
    166247    }
    167248
     
    175256    /// <returns>True if the encoding is valid.</returns>
    176257    public bool Validate() {
     258      return Validate(array);
     259    }
     260
     261    private static bool Validate(int[] array) {
    177262      var len = array.Length;
    178       var remaining = new HashSet<int>(Enumerable.Range(0, len));
     263      var used = new bool[len];
    179264      for (var i = 0; i < len; i++) {
    180         if (!remaining.Contains(i)) continue;
    181         remaining.Remove(i);
    182         var next = array[i];
    183         if (next == i) continue;
    184         int prev;
    185         do {
    186           if (!remaining.Remove(next)) return false;
    187           prev = next;
     265        if (used[i]) continue;
     266        var curr = i;
     267        var next = array[curr];
     268        while (next > curr && next < len && !used[next]) {
     269          used[curr] = true;
     270          curr = next;
    188271          next = array[next];
    189         } while (next != prev);
    190       }
    191       return remaining.Count == 0;
     272        }
     273        if (curr!=next) return false;
     274        used[curr] = true;
     275      }
     276      return true;
    192277    }
    193278
     
    216301    public void LinearizeTreeStructures() {
    217302      // Step 1: Convert the array into LLE-e
    218       ToLLEeInplace(array);
     303      ToEndLinksInplace(array);
    219304      // Step 2: For all groups linearize the links
    220       FromLLEe(array);
     305      SetEndLinks(array);
    221306    }
    222307
     
    233318    /// </remarks>
    234319    /// <returns>An integer array in LLE-e representation</returns>
    235     public int[] ToLLEe() {
     320    public int[] ToEndLinks() {
    236321      var result = (int[])array.Clone();
    237       ToLLEeInplace(result);
     322      ToEndLinksInplace(result);
    238323      return result;
    239324    }
    240325
    241     private void ToLLEeInplace(int[] a) {
    242       var length = a.Length;
     326    private static void ToEndLinksInplace(int[] array) {
     327      var length = array.Length;
    243328      for (var i = length - 1; i >= 0; i--) {
    244         if (array[i] == i) a[i] = i;
    245         else a[i] = a[a[i]];
     329        var next = array[i];
     330        if (next > i) {
     331          array[i] = array[next];
     332        } else if (next < i) {
     333          throw new ArgumentException("Array is malformed and does not represent a valid LLE encoding.", "array");
     334        }
    246335      }
    247336    }
     
    253342    /// <remarks>
    254343    /// This operation runs in O(n) time, but requires additional memory
    255     /// in form of a dictionary.
     344    /// in form of a int[].
    256345    /// </remarks>
    257346    /// <param name="llee">The LLE-e representation</param>
    258     public void FromLLEe(int[] llee) {
     347    public void SetEndLinks(int[] llee) {
    259348      var length = array.Length;
    260       var groups = new Dictionary<int, int>();
     349      if (length != llee.Length) {
     350        throw new ArgumentException(string.Format("Expected length {0} but length was {1}", length, llee.Length), "llee");
     351      }
     352      // If we are ok with mutating llee we can avoid this clone
     353      var lookup = (int[])llee.Clone();
    261354      for (var i = length - 1; i >= 0; i--) {
    262         if (llee[i] == i) {
    263           array[i] = i;
    264           groups[i] = i;
     355        var end = llee[i];
     356        if (end == i) {
     357          array[i] = end;
     358        } else if (end > i && end < length) {
     359          array[i] = lookup[end];
     360          lookup[end] = i;
    265361        } else {
    266           var g = llee[i];
    267           array[i] = groups[g];
    268           groups[g] = i;
     362          throw new ArgumentException("Array is malformed and does not represent a valid LLE end encoding.", "llee");
    269363        }
    270364      }
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Moves/StaticAPI/MoveGenerator.cs

    r14477 r14487  
    4545            yield return new MergeMove(i, l.Key);
    4646          }
     47        } else {
     48          // Fourth: extract i into group of its own (exclude first, because of Second)
     49          yield return new ExtractMove(i, pred, next);
    4750        }
    4851      }
    49       if (!isFirst)
    50         // Fourth: extract i into group of its own (exclude first, because of Second)
    51         yield return new ExtractMove(i, pred, next);
     52       
    5253
    5354    }
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Plugin.cs.frame

    r14195 r14487  
    2323
    2424namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    25   [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.3.14.$WCREV$")]
    26   [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.3.dll", PluginFileType.Assembly)]
     25  [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.4.14.$WCREV$")]
     26  [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.4.dll", PluginFileType.Assembly)]
    2727  [PluginDependency("HeuristicLab.Collections", "3.3")]
    2828  [PluginDependency("HeuristicLab.Common", "3.3")]
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Properties/AssemblyInfo.cs.frame

    r14195 r14487  
    5353// by using the '*' as shown below:
    5454// [assembly: AssemblyVersion("1.0.*")]
    55 [assembly: AssemblyVersion("3.3.0.0")]
    56 [assembly: AssemblyFileVersion("3.3.14.$WCREV$")]
     55[assembly: AssemblyVersion("3.4.0.0")]
     56[assembly: AssemblyFileVersion("3.4.14.$WCREV$")]
Note: See TracChangeset for help on using the changeset viewer.