Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/05/17 00:32:43 (8 years ago)
Author:
abeham
Message:

#2701:

  • LLE: Added equality comparer
  • MemPR:
    • Added GPR to learn about heuristic performance
    • Changed Breeding to do more exhaustive search on crossover
    • Added Delinking separately to Relinking
    • Rewrote d/relinking for LLE
    • Reduce usage of local search
    • Renamed TabuWalk to AdaptiveWalk
    • Rewrote adaptive walk for binary problems
    • Renamed LLE namespace to Grouping to avoid namespace clashes
Location:
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4
Files:
3 edited
1 copied

Legend:

Unmodified
Added
Removed

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

    r14492 r14544  
    167167    <Compile Include="Interfaces\ILinearLinkageSwap2MoveOperator.cs" />
    168168    <Compile Include="Interfaces\ILinearLinkageCreator.cs" />
     169    <Compile Include="LinearLinkageEqualityComparer.cs" />
    169170    <Compile Include="LinearLinkage.cs" />
    170171    <Compile Include="LinearLinkageCreator.cs" />

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

    r14492 r14544  
    2020#endregion
    2121
    22 using System;
    2322using System.Collections.Generic;
    24 using System.Linq;
    25 using HeuristicLab.Common;
    26 using HeuristicLab.Core;
    27 using HeuristicLab.Data;
    28 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2923
    3024namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    31   [Item("LinearLinkage", "Represents an LLE grouping of items.")]
    32   [StorableClass]
    33   public sealed class LinearLinkage : IntArray {
    34 
    35     [StorableConstructor]
    36     private LinearLinkage(bool deserializing) : base(deserializing) { }
    37     private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { }
    38     public LinearLinkage() { }
    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     /// <exception cref="ArgumentException">If <paramref name="lle"/> does not represent a valid LLE array.</exception>
    62     /// <param name="lle">The LLE representation</param>
    63     /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    64     public static LinearLinkage FromForwardLinks(int[] lle) {
    65       if (!Validate(lle))
    66         throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
    67       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;
    93     }
    94 
    95     /// <summary>
    96     /// Create a new LinearLinkage object by parsing an LLE-e representation
    97     /// and modifing the underlying array so that it is in LLE representation.
    98     /// </summary>
    99     /// <remarks>
    100     /// This operation runs in O(n) time, but requires additional memory
    101     /// in form of a int[].
    102     /// </remarks>
    103     /// <param name="llee">The LLE-e representation</param>
    104     /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    105     public static LinearLinkage FromEndLinks(int[] llee) {
    106       var result = new LinearLinkage(llee.Length);
    107       result.SetEndLinks(llee);
    108       return result;
    109     }
    110 
    111     /// <summary>
    112     /// Create a new LinearLinkage object by translating
    113     /// an enumeration of groups into the underlying array representation.
    114     /// </summary>
    115     /// <remarks>
    116     /// Throws an ArgumentException when there is an element assigned to
    117     /// multiple groups or elements that are not assigned to any group.
    118     /// </remarks>
    119     /// <param name="grouping">The grouping of the elements, each element must
    120     /// be part of exactly one group.</param>
    121     public static LinearLinkage FromGroups(int length, IEnumerable<IEnumerable<int>> grouping) {
    122       var result = new LinearLinkage(length);
    123       result.SetGroups(grouping);
    124       return result;
    125     }
    126 
    127     public override IDeepCloneable Clone(Cloner cloner) {
    128       return new LinearLinkage(this, cloner);
    129     }
    130 
    131     /// <summary>
    132     /// This method parses the encoded array and calculates the membership of
    133     /// each element to the groups. It starts at the lowest element.
    134     /// </summary>
    135     /// <remarks>
    136     /// Runtime complexity of this method is O(n) where n is the length of the
    137     /// array.
    138     /// </remarks>
    139     /// <exception cref="InvalidOperationException">If this object is not vaild LLE.</exception>
    140     /// <returns>An enumeration of all groups.</returns>
    141     public IEnumerable<List<int>> GetGroups() {
    142       var len = array.Length;
    143       var used = new bool[len];
    144       for (var i = 0; i < len; i++) {
    145         if (used[i]) continue;
    146         var curr = i;
    147         var next = array[curr];
    148         var group = new List<int> { curr };
    149         while (next > curr && next < len && !used[next]) {
    150           used[curr] = true;
    151           curr = next;
    152           next = array[next];
    153           group.Add(curr);
    154         }
    155         if (curr != next) throw new InvalidOperationException("Array is malformed and does not represent a valid LLE forward encoding.");
    156         used[curr] = true;
    157         yield return group;
    158       }
    159     }
    160 
    161     /// <summary>
    162     /// This method parses the encoded array and gathers all elements
    163     /// that belong to the same group as element <paramref name="index"/>.
    164     /// </summary>
    165     /// <param name="index">The element whose group should be returned.
    166     /// </param>
    167     /// <returns>The element at <paramref name="index"/> and all other
    168     /// elements in the same group.</returns>
    169     public IEnumerable<int> GetGroup(int index) {
    170       foreach (var n in GetGroupForward(index))
    171         yield return n;
    172       // the element index has already been yielded
    173       foreach (var n in GetGroupBackward(index).Skip(1))
    174         yield return n;
    175     }
    176 
    177     /// <summary>
    178     /// This method parses the encoded array and gathers the element
    179     /// <paramref name="index"/> as well as subsequent elements that
    180     /// belong to the same group.
    181     /// </summary>
    182     /// <param name="index">The element from which subsequent (having a
    183     /// larger number) elements in the group should be returned.
    184     /// </param>
    185     /// <returns>The element <paramref name="index"/> and all subsequent
    186     /// elements in the same group.</returns>
    187     public IEnumerable<int> GetGroupForward(int index) {
    188       yield return index;
    189       var next = array[index];
    190       if (next == index) yield break;
    191       int prev;
    192       do {
    193         yield return next;
    194         prev = next;
    195         next = array[next];
    196       } while (next != prev);
    197     }
    198 
    199     /// <summary>
    200     /// This method parses the encoded array and gathers the element
    201     /// given <paramref name="index"/> as well as preceeding elements that
    202     /// belong to the same group.
    203     /// </summary>
    204     /// <remarks>
    205     /// Warning, this code has performance O(index) as the array has to
    206     /// be fully traversed backwards from the given index.
    207     /// </remarks>
    208     /// <param name="index">The element from which preceeding (having a
    209     /// smaller number) elements in the group should be returned.
    210     /// </param>
    211     /// <returns>The element <paramref name="index"/> and all preceeding
    212     /// elements in the same group.</returns>
    213     public IEnumerable<int> GetGroupBackward(int index) {
    214       yield return index;
    215       var next = array[index];
    216       // return preceding elements in group
    217       for (var prev = index - 1; prev >= 0; prev--) {
    218         if (array[prev] != next) continue;
    219         next = prev;
    220         yield return next;
    221       }
    222     }
    223 
    224     /// <summary>
    225     /// This method translates an enumeration of groups into the underlying
    226     /// array representation.
    227     /// </summary>
    228     /// <remarks>
    229     /// Throws an ArgumentException when there is an element assigned to
    230     /// multiple groups or elements that are not assigned to any group.
    231     /// </remarks>
    232     /// <param name="grouping">The grouping of the elements, each element must
    233     /// 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>
    238     public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
    239       var len = array.Length;
    240       var used = new bool[len];
    241       foreach (var group in grouping) {
    242         var prev = -1;
    243         foreach (var g in group.OrderBy(x => x)) {
    244           if (g < prev || g >= len) throw new ArgumentException(string.Format("Element {0} is bigger than {1} or smaller than 0.", g, len - 1), "grouping");
    245           if (prev >= 0) array[prev] = g;
    246           prev = g;
    247           if (used[prev]) {
    248             throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
    249           }
    250           used[prev] = true;
    251         }
    252         array[prev] = prev;
    253       }
    254       if (!used.All(x => x))
    255         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))));
    256     }
    257 
    258     /// <summary>
    259     /// Performs a check whether the array represents a valid LLE encoding.
    260     /// </summary>
    261     /// <remarks>
    262     /// The runtime complexity of this method is O(n) where n is the length of
    263     /// the array.
    264     /// </remarks>
    265     /// <returns>True if the encoding is valid.</returns>
    266     public bool Validate() {
    267       return Validate(array);
    268     }
    269 
    270     private static bool Validate(int[] array) {
    271       var len = array.Length;
    272       var used = new bool[len];
    273       for (var i = 0; i < len; i++) {
    274         if (used[i]) continue;
    275         var curr = i;
    276         var next = array[curr];
    277         while (next > curr && next < len && !used[next]) {
    278           used[curr] = true;
    279           curr = next;
    280           next = array[next];
    281         }
    282         if (curr!=next) return false;
    283         used[curr] = true;
    284       }
     25  public class LinearLinkageEqualityComparer : EqualityComparer<LinearLinkage> {
     26    public override bool Equals(LinearLinkage x, LinearLinkage y) {
     27      if (x == null && y == null) return true;
     28      if (x == null || y == null) return false;
     29      if (x.Length != y.Length) return false;
     30      for (var i = 0; i < x.Length; i++)
     31        if (x[i] != y[i]) return false;
    28532      return true;
    28633    }
    28734
    288     /// <summary>
    289     /// This method flattens tree structures that may be present in groups.
    290     /// These tree structures may be created by e.g. merging two groups by
    291     /// linking one end node to the end node of another.
    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
    295     ///    /   \
    296     ///   5     6
    297     ///  / \    |
    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.
    301     /// </summary>
    302     /// <remarks>
    303     /// The method first converts the array to LLE-e format and then
    304     /// linearizes the links. This requires two passes of the whole array
    305     /// as well as another copy of the underlying array.
    306     /// The runtime complexity is O(n).
    307     ///
    308     /// The method assumes that there are no back links present.
    309     /// </remarks>
    310     public void LinearizeTreeStructures() {
    311       // Step 1: Convert the array into LLE-e
    312       ToEndLinksInplace(array);
    313       // Step 2: For all groups linearize the links
    314       SetEndLinks(array);
    315     }
    316 
    317     /// <summary>
    318     /// Creates a copy of the underlying array and turns it into LLE-e.
    319     /// </summary>
    320     /// <remarks>
    321     /// LLE-e is a special format where each element points to the
    322     /// ending item of a group.
    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.
    325     ///
    326     /// This operation runs in O(n) time.
    327     /// </remarks>
    328     /// <exception cref="ArgumentException">In case, this object does not
    329     /// represent a valid LLE encoding.
    330     /// </exception>
    331     /// <returns>An integer array in LLE-e representation</returns>
    332     public int[] ToEndLinks() {
    333       var result = (int[])array.Clone();
    334       ToEndLinksInplace(result);
    335       return result;
    336     }
    337 
    338     private static void ToEndLinksInplace(int[] array) {
    339       var length = array.Length;
    340       for (var i = length - 1; i >= 0; i--) {
    341         var next = array[i];
    342         if (next > i) {
    343           array[i] = array[next];
    344         } else if (next < i) {
    345           throw new ArgumentException("Array is malformed and does not represent a valid LLE encoding.", "array");
    346         }
     35    public override int GetHashCode(LinearLinkage obj) {
     36      unchecked {
     37        int hash = 17;
     38        foreach (var o in obj)
     39          hash = hash * 31 + o.GetHashCode();
     40        return hash;
    34741      }
    348     }
    349 
    350     /// <summary>
    351     /// Parses an LLE-e representation and modifies the underlying array
    352     /// so that it is in LLE representation.
    353     /// </summary>
    354     /// <remarks>
    355     /// This operation runs in O(n) time, but requires additional memory
    356     /// in form of a int[].
    357     /// </remarks>
    358     /// <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>
    363     public void SetEndLinks(int[] llee) {
    364       var length = array.Length;
    365       if (length != llee.Length) {
    366         throw new ArgumentException(string.Format("Expected length {0} but length was {1}", length, llee.Length), "llee");
    367       }
    368       // If we are ok with mutating llee we can avoid this clone
    369       var lookup = (int[])llee.Clone();
    370       for (var i = length - 1; i >= 0; i--) {
    371         var end = llee[i];
    372         if (end == i) {
    373           array[i] = end;
    374         } else if (end > i && end < length) {
    375           array[i] = lookup[end];
    376           lookup[end] = i;
    377         } else {
    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;
    40742    }
    40843  }

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

    r14492 r14544  
    2020#endregion
    2121
    22 using HeuristicLab.Collections;
    23 
    2422namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    2523  public abstract class Move {

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

    r14492 r14544  
    2121
    2222using System;
    23 using HeuristicLab.Collections;
    2423
    2524namespace HeuristicLab.Encodings.LinearLinkageEncoding {
Note: See TracChangeset for help on using the changeset viewer.