Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14492


Ignore:
Timestamp:
12/14/16 20:45:46 (8 years ago)
Author:
abeham
Message:

#2701:

  • Updated LLE encoding
    • Made folder for version 3.4
    • Added conversion from and to LLE-b representation (back-links)
    • Updated moves and movegenerator to replace bidirectionaldictionary with LLE-b representation
  • Updated MemPR (linear linkage)
    • Updated tabu walk
  • Added test for conversion between LLE-e and LLE and LLE-b and LLE
  • Updated test for move apply/undo and added test for applying in sequence
Location:
branches/MemPRAlgorithm
Files:
1 added
1 deleted
17 edited
1 moved

Legend:

Unmodified
Added
Removed

  • branches/MemPRAlgorithm/HeuristicLab 3.3.sln

    r14487 r14492  
    131131    {79271BC8-4446-40E2-BB89-9BE4E17174FE} = {79271BC8-4446-40E2-BB89-9BE4E17174FE}
    132132    {BBF2CCC8-4D87-4297-8E18-8241FF93F966} = {BBF2CCC8-4D87-4297-8E18-8241FF93F966}
     133    {166507C9-EF26-4370-BB80-699742A29D4F} = {166507C9-EF26-4370-BB80-699742A29D4F}
    133134    {59F354CB-FE13-4253-AED2-AD86372BEC27} = {59F354CB-FE13-4253-AED2-AD86372BEC27}
    134135    {4B76E2CB-A990-4959-B080-1D81D418D325} = {4B76E2CB-A990-4959-B080-1D81D418D325}
    … …  
    456457Project("{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}"
    457458EndProject
    458 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}"
     459Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.LinearLinkageEncoding-3.4", "HeuristicLab.Encodings.LinearLinkageEncoding\3.4\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj", "{166507C9-EF26-4370-BB80-699742A29D4F}"
    459460EndProject
    460461Global

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

    r14487 r14492  
    162162      <Private>False</Private>
    163163    </ProjectReference>
    164     <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
     164    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.4\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
    165165      <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project>
    166166      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name>
     167      <Private>False</Private>
    167168    </ProjectReference>
    168169    <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj">

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

    r14487 r14492  
    120120        tabu[i, current[i]] = quality;
    121121      }
    122      
     122
    123123      // this dictionary holds the last relevant links
    124       var links = new BidirectionalDictionary<int, int>();
     124      var groupItems = new List<int>();
     125      var lleb = current.ToBackLinks();
    125126      Move bestOfTheRest = null;
    126127      var bestOfTheRestF = double.NaN;
    … …  
    128129      for (var iter = 0; iter < int.MaxValue; iter++) {
    129130        // clear the dictionary before a new pass through the array is made
    130         links.Clear();
     131        groupItems.Clear();
    131132        for (var i = 0; i < current.Length; i++) {
    132133          if (subspace != null && !subspace[i]) {
    133             links.RemoveBySecond(i);
    134             links.Add(i, current[i]);
     134            if (lleb[i] != i)
     135              groupItems.Remove(lleb[i]);
     136            groupItems.Add(i);
    135137            continue;
    136138          }
    … …  
    141143            if (bestOfTheRest != null) {
    142144              bestOfTheRest.Apply(current);
     145              bestOfTheRest.ApplyToLLEb(lleb);
    143146              currentScope.Fitness = bestOfTheRestF;
    144147              quality = bestOfTheRestF;
    … …  
    162165            break;
    163166          } else {
    164             foreach (var move in MoveGenerator.GenerateForItem(i, next, links)) {
     167            foreach (var move in MoveGenerator.GenerateForItem(i, groupItems, current, lleb)) {
    165168              // we intend to break link i -> next
    166169              var qualityToBreak = tabu[i, next];
    … …  
    185188                if (isAspired) bestQuality = quality;
    186189
    187                 move.UpdateLinks(links);
     190                move.ApplyToLLEb(lleb);
    188191
    189192                if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheWalkF)) {
    … …  
    209212            }
    210213          }
    211           links.RemoveBySecond(i);
    212           links.Add(i, current[i]);
     214          if (lleb[i] != i)
     215            groupItems.Remove(lleb[i]);
     216          groupItems.Add(i);
    213217          if (evaluations >= maxEvals) break;
    214218          if (token.IsCancellationRequested) break;

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Plugin.cs

    r14420 r14492  
    3333  [PluginDependency("HeuristicLab.Data", "3.3")]
    3434  [PluginDependency("HeuristicLab.Encodings.BinaryVectorEncoding", "3.3")]
     35  [PluginDependency("HeuristicLab.Encodings.LinearLinkageEncoding", "3.4")]
     36  [PluginDependency("HeuristicLab.Encodings.PermutationEncoding", "3.3")]
    3537  [PluginDependency("HeuristicLab.Operators", "3.3")]
    3638  [PluginDependency("HeuristicLab.Optimization", "3.3")]

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

    r14487 r14492  
    176176    <Compile Include="Manipulators\MergeGroupManipulator.cs" />
    177177    <Compile Include="Manipulators\MultiLLEManipulator.cs" />
     178    <Compile Include="Moves\ExtractMove.cs" />
     179    <Compile Include="Moves\MergeMove.cs" />
     180    <Compile Include="Moves\Move.cs" />
     181    <Compile Include="Moves\ShiftMove.cs" />
     182    <Compile Include="Moves\SplitMove.cs" />
     183    <Compile Include="Moves\StaticAPI\MoveGenerator.cs" />
    178184    <Compile Include="Moves\Swap\ExhaustiveSwap2MoveGenerator.cs" />
    179185    <Compile Include="Moves\Swap\StochasticSwap2MultiMoveGenerator.cs" />

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkage.cs

    r14487 r14492  
    5959    /// and throws an ArgumentException otherwise.
    6060    /// </remarks>
     61    /// <exception cref="ArgumentException">If <paramref name="lle"/> does not represent a valid LLE array.</exception>
    6162    /// <param name="lle">The LLE representation</param>
     63    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    6264    public static LinearLinkage FromForwardLinks(int[] lle) {
    63       if (!Validate(lle)) {
     65      if (!Validate(lle))
    6466        throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
    65       }
    6667      return new LinearLinkage(lle);
     68    }
     69
     70    /// <summary>
     71    /// Create a new LinearLinkage object by parsing a LLE-b representation
     72    /// and modifing the underlying array so that it is in LLE representation.
     73    /// </summary>
     74    /// <remarks>
     75    /// This operation runs in O(n) time, the parameter <paramref name="lleb"/> is not modified.
     76    /// </remarks>
     77    /// <exception cref="ArgumentException">If <paramref name="lleb"/> does not represent a valid LLE-b array.</exception>
     78    /// <param name="lleb">The LLE-b representation (LLE with back-links)</param>
     79    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
     80    public static LinearLinkage FromBackLinks(int[] lleb) {
     81      var result = new LinearLinkage(lleb.Length);
     82      for (var i = lleb.Length - 1; i > 0; i--) {
     83        if (lleb[i] == i) {
     84          if (result[i] == 0) result[i] = i;
     85          continue;
     86        }
     87        result[lleb[i]] = i;
     88        if (result[i] == 0) result[i] = i;
     89      }
     90      if (!Validate(result.array))
     91        throw new ArgumentException("Array is malformed and does not represent a valid LLE-b encoding (with back-links).", "lleb");
     92      return result;
    6793    }
    6894
    … …  
    76102    /// </remarks>
    77103    /// <param name="llee">The LLE-e representation</param>
    78     /// <returns>LinearLinkage</returns>
     104    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    79105    public static LinearLinkage FromEndLinks(int[] llee) {
    80106      var result = new LinearLinkage(llee.Length);
    … …  
    111137    /// array.
    112138    /// </remarks>
     139    /// <exception cref="InvalidOperationException">If this object is not vaild LLE.</exception>
    113140    /// <returns>An enumeration of all groups.</returns>
    114141    public IEnumerable<List<int>> GetGroups() {
    … …  
    126153          group.Add(curr);
    127154        }
    128         if (curr != next) throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
     155        if (curr != next) throw new InvalidOperationException("Array is malformed and does not represent a valid LLE forward encoding.");
    129156        used[curr] = true;
    130157        yield return group;
    131158      }
    132       /*
    133       var len = array.Length;
    134       var used = new bool[len];
    135       // iterate from lowest to highest index
    136       for (var i = 0; i < len; i++) {
    137         if (used[i]) continue;
    138         var group = new List<int> { i };
    139         used[i] = true;
    140         var next = array[i];
    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];
    151         }
    152         yield return group;
    153       }*/
    154159    }
    155160
    … …  
    227232    /// <param name="grouping">The grouping of the elements, each element must
    228233    /// be part of exactly one group.</param>
     234    /// <exception cref="ArgumentException">If <paramref name="grouping"/> cannot be converted
     235    /// to a valid LLE representation. For instance, because elements are too big or too small,
     236    /// or they're contained in multiple groups, or there are elements not assigned to any group.
     237    /// </exception>
    229238    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
    230239      var len = array.Length;
    … …  
    281290    /// These tree structures may be created by e.g. merging two groups by
    282291    /// linking one end node to the end node of another.
    283     /// Consider following 1-based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9.
    284     /// This results in the following tree structure for group 8:
    285     ///      8
     292    /// Consider following array: 5, 5, 6, 4, 4, 7, 7, 7, 8.
     293    /// This results in the following tree structure for group 7:
     294    ///      7
    286295    ///    /   \
    287     ///   6     7
     296    ///   5     6
    288297    ///  / \    |
    289     /// 1   2   3
    290     /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
    291     /// Representing a tree with one branch: 1 -> 2 -> 3 -> 6 -> 7 -> 8
     298    /// 0   1   2
     299    /// After this operation the array will be 1, 2, 5, 4, 4, 6, 7, 7, 8.
     300    /// Representing a tree with one branch: 0 -> 1 -> 2 -> 5 -> 6 -> 7.
    292301    /// </summary>
    293302    /// <remarks>
    294303    /// The method first converts the array to LLE-e format and then
    295304    /// linearizes the links. This requires two passes of the whole array
    296     /// as well as a dictionary to hold the smallest index of each group.
     305    /// as well as another copy of the underlying array.
    297306    /// The runtime complexity is O(n).
    298307    ///
    … …  
    312321    /// LLE-e is a special format where each element points to the
    313322    /// ending item of a group.
    314     /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become
    315     /// 5, 5, 5, 8, 5, 8, 8, 8 in LLE-e.
     323    /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7 would become
     324    /// 4, 4, 4, 7, 4, 7, 7, 7 in LLE-e.
    316325    ///
    317326    /// This operation runs in O(n) time.
    318327    /// </remarks>
     328    /// <exception cref="ArgumentException">In case, this object does not
     329    /// represent a valid LLE encoding.
     330    /// </exception>
    319331    /// <returns>An integer array in LLE-e representation</returns>
    320332    public int[] ToEndLinks() {
    … …  
    345357    /// </remarks>
    346358    /// <param name="llee">The LLE-e representation</param>
     359    /// <exception cref="ArgumentException">
     360    /// If <paramref name="llee"/> does not contain a valid LLE-e representation or
     361    /// has a different length to the given instance.
     362    /// </exception>
    347363    public void SetEndLinks(int[] llee) {
    348364      var length = array.Length;
    … …  
    360376          lookup[end] = i;
    361377        } else {
    362           throw new ArgumentException("Array is malformed and does not represent a valid LLE end encoding.", "llee");
    363         }
    364       }
     378          throw new ArgumentException("Array is malformed and does not represent a valid LLE-e end encoding.", "llee");
     379        }
     380      }
     381    }
     382
     383    /// <summary>
     384    /// Creates a copy of the underlying array and turns it into LLE-b.
     385    /// </summary>
     386    /// <remarks>
     387    /// LLE-b is a special format where each element points to the
     388    /// predecessor instead of the successor.
     389    /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7
     390    /// would become           0, 0, 1, 3, 2, 3, 5, 6 in LLE-b.
     391    ///
     392    /// This operation runs in O(n) time.
     393    /// </remarks>
     394    /// <returns>An integer array in LLE-b representation</returns>
     395    public int[] ToBackLinks() {
     396      var result = new int[array.Length];
     397      var zeroLink = array[0];
     398      for (var i = 0; i < array.Length; i++) {
     399        if (array[i] == i) {
     400          if (result[i] == 0 && i != zeroLink) result[i] = i;
     401          continue;
     402        }
     403        result[array[i]] = i;
     404        if (result[i] == 0 && i != zeroLink) result[i] = i;
     405      }
     406      return result;
    365407    }
    366408  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/ExtractMove.cs

    r14477 r14492  
    2121
    2222using System;
    23 using HeuristicLab.Collections;
    2423
    2524namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    … …  
    4140        || lle[Item] != NextItem)
    4241        throw new ArgumentException("Move conditions have changed!");
    43       if (!IsFirst)
    44         lle[PreviousItem] = IsLast ? PreviousItem : NextItem;
     42      if (!IsFirst) lle[PreviousItem] = IsLast ? PreviousItem : NextItem;
    4543      lle[Item] = Item;
    4644    }
    … …  
    5149        throw new ArgumentException("Move conditions have changed, cannot undo move.");
    5250
    53       if (!IsFirst)
    54         lle[PreviousItem] = Item;
     51      if (!IsFirst) lle[PreviousItem] = Item;
    5552      lle[Item] = NextItem;
    5653    }
    5754
    58     public override void UpdateLinks(BidirectionalDictionary<int, int> links) {
    59       if (!IsFirst) {
    60         links.RemoveBySecond(Item);
    61         links.SetByFirst(PreviousItem, IsLast ? PreviousItem : NextItem);
    62       }
     55    public override void ApplyToLLEb(int[] lleb) {
     56      if (!IsLast) lleb[NextItem] = IsFirst ? NextItem : PreviousItem;
     57      lleb[Item] = Item;
    6358    }
    6459  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/MergeMove.cs

    r14477 r14492  
    2121
    2222using System;
    23 using HeuristicLab.Collections;
    2423
    2524namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    … …  
    2726
    2827    public int LastItemOfOtherGroup { get; private set; }
    29     private int nextItemOfOtherGroup; // undo information
    3028
    3129    public MergeMove(int item, int lastOfOther) {
    3230      Item = item;
    3331      LastItemOfOtherGroup = lastOfOther;
    34       nextItemOfOtherGroup = -1;
    3532    }
    3633
    3734    public override void Apply(LinearLinkage lle) {
    3835      if (lle[LastItemOfOtherGroup] != LastItemOfOtherGroup) throw new ArgumentException("Move conditions have changed, group does not terminate at " + LastItemOfOtherGroup);
    39       nextItemOfOtherGroup = lle[LastItemOfOtherGroup];
    4036      lle[LastItemOfOtherGroup] = Item;
    4137    }
    … …  
    4339    public override void Undo(LinearLinkage lle) {
    4440      if (lle[LastItemOfOtherGroup] != Item) throw new ArgumentException("Move conditions have changed, groups are no longer linked between " + LastItemOfOtherGroup + " and " + Item);
    45       if (nextItemOfOtherGroup < 0) throw new InvalidOperationException("Cannot undo move that has not been applied first.");
    46       lle[LastItemOfOtherGroup] = nextItemOfOtherGroup;
     41      lle[LastItemOfOtherGroup] = LastItemOfOtherGroup;
    4742    }
    4843
    49     public override void UpdateLinks(BidirectionalDictionary<int, int> links) {
    50       if (nextItemOfOtherGroup < 0) throw new InvalidOperationException("Cannot update links for move that has not been applied first.");
    51       links.RemoveBySecond(nextItemOfOtherGroup);
     44    public override void ApplyToLLEb(int[] lleb) {
     45      lleb[Item] = LastItemOfOtherGroup;
    5246    }
    5347  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/Move.cs

    r14477 r14492  
    2929    public abstract void Undo(LinearLinkage lle);
    3030
    31     public abstract void UpdateLinks(BidirectionalDictionary<int, int> links);
     31    public abstract void ApplyToLLEb(int[] lleb);
    3232  }
    3333}

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/ShiftMove.cs

    r14477 r14492  
    6565    }
    6666
    67     public override void UpdateLinks(BidirectionalDictionary<int, int> links) {
    68       links.RemoveBySecond(Item);
    69       links.SetByFirst(PreviousItemOfNewGroup, Item);
    70       if (!IsFirst) links.SetByFirst(PreviousItemOfOldGroup, IsLast ? PreviousItemOfOldGroup : NextItemOfOldGroup);
     67    public override void ApplyToLLEb(int[] lleb) {
     68      if (!IsLast)
     69        lleb[NextItemOfOldGroup] = IsFirst ? NextItemOfOldGroup : PreviousItemOfOldGroup;
     70      lleb[Item] = PreviousItemOfNewGroup;
     71      if (!NewGroupClosed)
     72        lleb[NextItemOfNewGroup] = Item;
    7173    }
    7274  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/SplitMove.cs

    r14477 r14492  
    2121
    2222using System;
    23 using HeuristicLab.Collections;
    2423
    2524namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    … …  
    4544    }
    4645
    47     public override void UpdateLinks(BidirectionalDictionary<int, int> links) {
    48       // nothing has to be done
     46    public override void ApplyToLLEb(int[] lleb) {
     47      if (nextItem < 0) throw new InvalidOperationException("Cannot undo move that has not been applied first to LLE.");
     48      lleb[nextItem] = nextItem;
    4949    }
    5050  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/StaticAPI/MoveGenerator.cs

    r14487 r14492  
    2626namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    2727  public static class MoveGenerator {
    28     public static IEnumerable<Move> GenerateForItem(int i, int next, BidirectionalDictionary<int, int> links) {
    29       var pred = -1;
    30       var isFirst = !links.TryGetBySecond(i, out pred);
     28    public static IEnumerable<Move> GenerateForItem(int i, List<int> groupItems, LinearLinkage lle, int[] lleb) {
     29      var pred = lleb[i];
     30      var next = lle[i];
     31      var isFirst = pred == i;
    3132      var isLast = next == i;
    3233
    3334      // First: shift i into each previous group
    34       foreach (var l in links.Where(x => x.Value != i)) {
    35         yield return new ShiftMove(i, isFirst ? i : pred, l.Key, next, l.Value);
     35      foreach (var m in groupItems.Where(x => lle[x] != i)) {
     36        yield return new ShiftMove(i, pred, m, next, lle[m]);
    3637      }
    3738
    … …  
    4243        if (isFirst) {
    4344          // Third: merge with closed groups
    44           foreach (var l in links.Where(x => x.Key == x.Value)) {
    45             yield return new MergeMove(i, l.Key);
     45          foreach (var m in groupItems.Where(x => lle[x] == x)) {
     46            yield return new MergeMove(i, m);
    4647          }
    4748        } else {
    48           // Fourth: extract i into group of its own (exclude first, because of Second)
     49          // Fourth: extract i into group of its own (exclude first and last, because of SplitMove)
    4950          yield return new ExtractMove(i, pred, next);
    5051        }
    … …  
    5556
    5657    public static IEnumerable<Move> Generate(LinearLinkage lle) {
    57       var links = new BidirectionalDictionary<int, int>();
     58      var groupItems = new List<int>();
     59      var lleb = lle.ToBackLinks();
    5860      for (var i = 0; i < lle.Length; i++) {
    59         foreach (var move in GenerateForItem(i, lle[i], links))
     61        foreach (var move in GenerateForItem(i, groupItems, lle, lleb))
    6062          yield return move;
    61         links.RemoveBySecond(i);
    62         links.Add(i, lle[i]);
     63        if (lleb[i] != i)
     64          groupItems.Remove(lleb[i]);
     65        groupItems.Add(i);
    6366      }
    6467    }

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

    r14487 r14492  
    8888      <Private>False</Private>
    8989    </ProjectReference>
    90     <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
     90    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.4\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
    9191      <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project>
    9292      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name>

  • branches/MemPRAlgorithm/HeuristicLab.Problems.GraphColoring/3.3/Plugin.cs.frame

    r14471 r14492  
    3131  [PluginDependency("HeuristicLab.Core", "3.3")]
    3232  [PluginDependency("HeuristicLab.Data", "3.3")]
    33   [PluginDependency("HeuristicLab.Encodings.LinearLinkageEncoding", "3.3")]
     33  [PluginDependency("HeuristicLab.Encodings.LinearLinkageEncoding", "3.4")]
    3434  [PluginDependency("HeuristicLab.Operators", "3.3")]
    3535  [PluginDependency("HeuristicLab.Optimization", "3.3")]

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

    r14487 r14492  
    149149      <Name>HeuristicLab.Encodings.IntegerVectorEncoding-3.3</Name>
    150150    </ProjectReference>
    151     <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
     151    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.4\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
    152152      <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project>
    153153      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name>

  • branches/MemPRAlgorithm/HeuristicLab.Tests/HeuristicLab.Encodings.LinearLinkageEncoding-3.3/MoveTests.cs

    r14477 r14492  
    11using System;
     2using System.Collections.Generic;
    23using System.Linq;
    34using HeuristicLab.Encodings.LinearLinkageEncoding;
    … …  
    1112    public void TestApplyUndo() {
    1213      var random = new MersenneTwister(42);
    13       var lle = MaxGroupsLinearLinkageCreator.Apply(random, 32, 8);
    14       var before = (LinearLinkage)lle.Clone();
    15       var moves = 0;
    16       foreach (var move in MoveGenerator.Generate(lle)) {
    17         move.Apply(lle);
    18         Assert.IsFalse(before.SequenceEqual(lle));
    19         move.Undo(lle);
    20         Assert.IsTrue(before.SequenceEqual(lle));
    21         moves++;
     14      for (var p = 0; p < 7; p++) {
     15        var lle = ExactGroupsLinearLinkageCreator.Apply(random, 64, (int)Math.Pow(2, p));
     16        var before = (LinearLinkage)lle.Clone();
     17        var beforeb = before.ToBackLinks();
     18        var moves = 0;
     19        foreach (var move in MoveGenerator.Generate(lle)) {
     20          var lleb = lle.ToBackLinks();
     21          move.Apply(lle);
     22          move.ApplyToLLEb(lleb);
     23          Assert.IsFalse(before.SequenceEqual(lle));
     24          Assert.IsFalse(lleb.SequenceEqual(beforeb));
     25          Assert.IsTrue(lleb.SequenceEqual(lle.ToBackLinks()));
     26          Assert.IsTrue(lle.SequenceEqual(LinearLinkage.FromBackLinks(lleb)));
     27          move.Undo(lle);
     28          Assert.IsTrue(before.SequenceEqual(lle));
     29          moves++;
     30        }
     31        Assert.IsTrue(moves > 0);
    2232      }
    23       Assert.IsTrue(moves > 0);
     33    }
     34
     35    [TestMethod]
     36    public void TestApply() {
     37      var random = new MersenneTwister(42);
     38      for (var p = 0; p < 7; p++) {
     39        var lle = ExactGroupsLinearLinkageCreator.Apply(random, 64, (int)Math.Pow(2, p));
     40        var lleb = lle.ToBackLinks();
     41        var groupItems = new List<int>() { 0 };
     42        var moves = 0;
     43        for (var i = 1; i < lle.Length; i++) {
     44          var move = MoveGenerator.GenerateForItem(i, groupItems, lle, lleb).SampleRandom(random);
     45          move.Apply(lle);
     46          move.ApplyToLLEb(lleb);
     47          Assert.IsTrue(lleb.SequenceEqual(lle.ToBackLinks()));
     48          Assert.IsTrue(lle.SequenceEqual(LinearLinkage.FromBackLinks(lleb)));
     49
     50          if (lleb[i] != i)
     51            groupItems.Remove(lleb[i]);
     52          groupItems.Add(i);
     53
     54          moves++;
     55        }
     56        Assert.IsTrue(moves == lle.Length - 1);
     57      }
    2458    }
    2559  }

  • branches/MemPRAlgorithm/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r14477 r14492  
    198198      <HintPath>..\bin\HeuristicLab.Encodings.IntegerVectorEncoding-3.3.dll</HintPath>
    199199    </Reference>
    200     <Reference Include="HeuristicLab.Encodings.LinearLinkageEncoding-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    201       <SpecificVersion>False</SpecificVersion>
    202       <HintPath>..\bin\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.dll</HintPath>
     200    <Reference Include="HeuristicLab.Encodings.LinearLinkageEncoding-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     201      <SpecificVersion>False</SpecificVersion>
     202      <HintPath>..\bin\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.dll</HintPath>
    203203      <Private>False</Private>
    204204    </Reference>
    … …  
    511511    <Compile Include="HeuristicLab.Encodings.IntegerVectorEncoding-3.3\UniformOnePositionManipulatorTest.cs" />
    512512    <Compile Include="HeuristicLab.Encodings.LinearLinkageEncoding-3.3\MoveTests.cs" />
     513    <Compile Include="HeuristicLab.Encodings.LinearLinkageEncoding-3.3\ConversionTests.cs" />
    513514    <Compile Include="HeuristicLab.Encodings.PermutationEncoding-3.3\Auxiliary.cs" />
    514515    <Compile Include="HeuristicLab.Encodings.PermutationEncoding-3.3\CosaCrossoverTest.cs" />
Note: See TracChangeset for help on using the changeset viewer.