Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/06/15 22:41:24 (10 years ago)
Author:
abeham
Message:

#2319:

  • Changed encoding to represent linkages in LLE (as opposed to LLE-e)
  • Added GraftManipulator
  • Added repair procedure
  • Improved performance of some crossovers
Location:
branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3
Files:
12 edited
1 copied

Legend:

Unmodified
Added
Removed

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/RandomLinearLinkageCreator.cs

    r12285 r12288  
    2727
    2828namespace HeuristicLab.Encodings.LinearLinkageEncoding.Creators {
    29   [Item("Random Linear Linkage Creator", "Creates a random linear linkage LLE-e encoded solution.")]
     29  [Item("Random Linear Linkage Creator", "Creates a random linear linkage LLE encoded solution.")]
    3030  [StorableClass]
    3131  public sealed class RandomLinearLinkageCreator : LinearLinkageCreator {

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GroupCrossover.cs

    r12285 r12288  
    2222using System;
    2323using System.Collections.Generic;
     24using System.Linq;
    2425using HeuristicLab.Common;
    2526using HeuristicLab.Core;
    … …  
    5354      for (var i = 0; i < length; i++) {
    5455        if (endNodes.Contains(i)) continue;
    55         if (endNodes.Contains(p1[i]) && endNodes.Contains(p2[i])) {
     56        var p1End = endNodes.Contains(p1[i]);
     57        var p2End = endNodes.Contains(p2[i]);
     58        if ((p1End && p2End) || (!p1End && !p2End)) {
    5659          child[i] = random.NextDouble() < 0.5 ? p1[i] : p2[i];
    57         } else if (endNodes.Contains(p1[i])) {
     60        } else if (p1End) {
    5861          child[i] = p1[i];
    59         } else if (endNodes.Contains(p2[i])) {
     62        } else {
    6063          child[i] = p2[i];
    61         } else {
    62           var a = p1[i];
    63           var b = p2[i];
    64           while (true) {
    65             if (endNodes.Contains(p2[a])) {
    66               child[i] = p2[a];
    67               break;
    68             }
    69             if (endNodes.Contains(p1[b])) {
    70               child[i] = p1[b];
    71               break;
    72             }
    73             var tmp = b;
    74             b = p2[a];
    75             a = p1[tmp];
    76           }
    7764        }
    7865      }
     66      child.LinearizeTreeStructures();
    7967      return child;
    8068    }

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexFirstCrossover.cs

    r12285 r12288  
    4242    public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) {
    4343      var len = parents[0].Length;
     44      var p = random.Next(parents.Length);
    4445      var child = new LinearLinkage(len);
    45       var childGroup = new List<HashSet<int>>();
    46       var currentParent = random.Next(parents.Length);
    47       var remaining = new HashSet<int>(Enumerable.Range(0, len));
     46      var remaining = new SortedSet<int>(Enumerable.Range(0, len));
    4847      do {
    49         var i = remaining.Min();
    50         var group = new HashSet<int>(parents[currentParent].GetGroupForward(i));
    51         group.IntersectWith(remaining);
    52         childGroup.Add(group);
    53         remaining.ExceptWith(group);
    54         currentParent = (currentParent + 1) % parents.Length;
     48        var i = remaining.Min;
     49        foreach (var g in parents[p].GetGroupForward(i)) {
     50          if (!remaining.Contains(g)) continue;
     51          child[i] = g;
     52          i = g;
     53          remaining.Remove(g);
     54        }
     55        child[i] = i;
     56        remaining.Remove(i);
     57
     58        p = (p + 1) % parents.Length;
    5559      } while (remaining.Count > 0);
    5660
    57       child.SetGroups(childGroup);
    5861      return child;
    5962    }

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexMaxCrossover.cs

    r12285 r12288  
    4545      var len = parents[0].Length;
    4646      var child = new LinearLinkage(len);
    47       var childGroup = new List<HashSet<int>>();
    48       var remaining = new HashSet<int>(Enumerable.Range(0, len));
     47      var remaining = new SortedSet<int>(Enumerable.Range(0, len));
    4948      do {
    50         var i = remaining.Min();
    51         var groups = parents.Select(x => new HashSet<int>(x.GetGroupForward(i))).ToList();
    52         for (var k = 0; k < groups.Count; k++)
    53           groups[k].IntersectWith(remaining);
    54 
    55         var maxGroup = groups.Select((v, idx) => Tuple.Create(idx, v)).MaxItems(x => x.Item2.Count).SampleRandom(random).Item1;
    56         childGroup.Add(groups[maxGroup]);
    57         remaining.ExceptWith(groups[maxGroup]);
     49        var groups = parents.Select(x => x.GetGroupForward(remaining.Min).Where(y => remaining.Contains(y)).ToList()).ToList();
     50        var max = groups.Select((v, idx) => Tuple.Create(idx, v.Count)).MaxItems(x => x.Item2).SampleRandom(random).Item1;
     51        var i = groups[max][0];
     52        for (var k = 1; k < groups[max].Count; k++) {
     53          child[i] = groups[max][k];
     54          remaining.Remove(i);
     55          i = child[i];
     56        }
     57        child[i] = i;
     58        remaining.Remove(i);
    5859      } while (remaining.Count > 0);
    5960
    60       child.SetGroups(childGroup);
    6161      return child;
    6262    }

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj

    r12286 r12288  
    113113    <Compile Include="LinearLinkageManipulator.cs" />
    114114    <Compile Include="LinearLinkageCrossover.cs" />
     115    <Compile Include="Manipulators\GraftManipulator.cs" />
    115116    <Compile Include="Manipulators\MoveItemManipulator.cs" />
    116117    <Compile Include="Manipulators\MergeGroupManipulator.cs" />
    … …  
    119120    <None Include="HeuristicLab.snk" />
    120121    <None Include="Plugin.cs.frame" />
    121     <Compile Include="Crossovers\LargestGroupFirstCrossover.cs" />
    122122    <Compile Include="Crossovers\LowestIndexFirstCrossover.cs" />
    123123    <Compile Include="Interfaces\ILinearLinkageCrossover.cs" />

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs

    r12285 r12288  
    2929
    3030namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    31   [Item("LinearLinkage", "Represents an LLE-e grouping of items.")]
     31  [Item("LinearLinkage", "Represents an LLE grouping of items.")]
    3232  [StorableClass]
    3333  public sealed class LinearLinkage : IntArray {
    … …  
    4545
    4646    /// <summary>
    47     /// This method parses the encoded array and calculates the membership of each element to the groups.
    48     /// It starts at the lowest element.
    49     /// </summary>
    50     /// <remarks>
    51     /// Runtime complexity of this method is O(n) where n is the length of the array.
     47    /// This method parses the encoded array and calculates the membership of
     48    /// each element to the groups. It starts at the lowest element.
     49    /// </summary>
     50    /// <remarks>
     51    /// Runtime complexity of this method is O(n) where n is the length of the
     52    /// array.
    5253    /// </remarks>
    5354    /// <returns>An enumeration of all groups.</returns>
    5455    public IEnumerable<List<int>> GetGroups() {
    5556      var len = array.Length;
    56       var dict = new Dictionary<int, List<int>>();
    57       for (var i = 0; i < len; i++) {
    58         var end = array[i];
    59         if (end < i || end >= len || array[end] != end)
    60           throw new ArgumentException("Array is malformed and does not represent a valid LLE-e encoding.");
    61         List<int> list;
    62         if (!dict.TryGetValue(end, out list))
    63           dict.Add(end, new List<int>() { i });
    64         else list.Add(i);
    65       }
    66       return dict.Values;
    67       /* This code implements group extraction from LLE forward encoding
    68        * var len = array.Length;
    6957      var remaining = new HashSet<int>(Enumerable.Range(0, len));
    7058      // iterate from lowest to highest index
    … …  
    8573        }
    8674        yield return group;
    87       }*/
    88     }
    89 
    90     /// <summary>
    91     /// This method parses the encoded array and gathers all items that belong to the same group as element <paramref name="index"/>.
     75      }
     76    }
     77
     78    /// <summary>
     79    /// This method parses the encoded array and gathers all items that
     80    /// belong to the same group as element <paramref name="index"/>.
    9281    /// </summary>
    9382    /// <param name="index">The element whose group should be returned.</param>
    94     /// <returns>The element at <paramref name="index"/> and all other elements in the same group.</returns>
     83    /// <returns>The element at <paramref name="index"/> and all other
     84    /// elements in the same group.</returns>
    9585    public IEnumerable<int> GetGroup(int index) {
    96       yield return index;
    97       var gn = array[index];
    98       for (var i = index + 1; i <= gn; i++) {
    99         if (array[i] == gn) yield return i;
    100       }
    101       for (var i = index - 1; i >= 0; i++) {
    102         if (array[i] == gn) yield return i;
    103       }
    104       /* This code implements group extraction from LLE forward encoding
    10586      // return current element
    10687      yield return index;
    … …  
    120101        next = prev;
    121102        yield return next;
    122       }*/
    123     }
    124 
    125     /// <summary>
    126     /// This method parses the encoded array and gathers the item itself as well as subsequent items that belong to the same group as element <paramref name="index"/>.
    127     /// </summary>
    128     /// <param name="index">The element from which items in the group should be returned.</param>
    129     /// <returns>The element at <paramref name="index"/> and all subsequent elements in the same group.</returns>
     103      }
     104    }
     105
     106    /// <summary>
     107    /// This method parses the encoded array and gathers the item itself as
     108    /// well as subsequent items that belong to the same group as element
     109    /// <paramref name="index"/>.
     110    /// </summary>
     111    /// <param name="index">The element from which items in the group should
     112    /// be returned.</param>
     113    /// <returns>The element at <paramref name="index"/> and all subsequent
     114    /// elements in the same group.</returns>
    130115    public IEnumerable<int> GetGroupForward(int index) {
    131       yield return index;
    132       var gn = array[index];
    133       for (var i = index + 1; i <= gn; i++) {
    134         if (array[i] == gn) yield return i;
    135       }
    136       /* This code implements group extraction from LLE forward encoding
    137116      yield return index;
    138117      var next = array[index];
    … …  
    143122        prev = next;
    144123        next = array[next];
    145       } while (next != prev);*/
    146     }
    147 
    148     /// <summary>
    149     /// This method translates an enumeration of groups into the underlying array representation.
    150     /// </summary>
    151     /// <remarks>
    152     /// Throws an ArgumentException when there is an element assigned to multiple groups or elements that
    153     /// are not assigned to any group.
    154     /// </remarks>
    155     /// <param name="grouping">The grouping of the elements, each element must be part of exactly one group.</param>
     124      } while (next != prev);
     125    }
     126
     127    /// <summary>
     128    /// This method translates an enumeration of groups into the underlying
     129    /// array representation.
     130    /// </summary>
     131    /// <remarks>
     132    /// Throws an ArgumentException when there is an element assigned to
     133    /// multiple groups or elements that  are not assigned to any group.
     134    /// </remarks>
     135    /// <param name="grouping">The grouping of the elements, each element must
     136    /// be part of exactly one group.</param>
    156137    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
    157       var len = array.Length;
    158       var remaining = new HashSet<int>(Enumerable.Range(0, len));
    159       foreach (var group in grouping) {
    160         var max = -1;
    161         foreach (var g in group.OrderByDescending(x => x)) {
    162           if (max < 0) max = g;
    163           array[g] = max;
    164           remaining.Remove(g);
    165         }
    166       }
    167       if (remaining.Count > 0)
    168         throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
    169       /* This code implements group setting for LLE forward encoding
    170138      var len = array.Length;
    171139      var remaining = new HashSet<int>(Enumerable.Range(0, len));
    … …  
    182150      if (remaining.Count > 0)
    183151        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
    184        */
    185     }
    186 
    187     /// <summary>
    188     /// Performs a check whether the array represents a valid LLE-e encoding.
    189     /// </summary>
    190     /// <remarks>
    191     /// The runtime complexity of this method is O(n) where n is the length of the array.
     152    }
     153
     154    /// <summary>
     155    /// Performs a check whether the array represents a valid LLE encoding.
     156    /// </summary>
     157    /// <remarks>
     158    /// The runtime complexity of this method is O(n) where n is the length of
     159    /// the array.
    192160    /// </remarks>
    193161    /// <returns>True if the encoding is valid.</returns>
    194162    public bool Validate() {
    195       var len = array.Length;
    196       for (var i = 0; i < len; i++) {
    197         var end = array[i];
    198         if (end < i || end >= len || array[end] != end)
    199           return false;
    200       }
    201       return true;
    202       /* This code implements group setting for LLE forward encoding
    203163      var len = array.Length;
    204164      var remaining = new HashSet<int>(Enumerable.Range(0, len));
    … …  
    215175        } while (next != prev);
    216176      }
    217       return remaining.Count == 0;*/
     177      return remaining.Count == 0;
     178    }
     179
     180    /// <summary>
     181    /// This method flattens tree structures that may be present in groups.
     182    /// These tree structures may be created by e.g. merging two groups by
     183    /// linking one end node to the end node of another.
     184    /// Consider following example: 6, 6, 7, 5, 5, 8, 8, 8, 9.
     185    /// This results in the following tree structure for group 8:
     186    ///      8
     187    ///    /   \
     188    ///   6     7
     189    ///  / \
     190    /// 1   2
     191    /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
     192    /// </summary>
     193    /// <remarks>
     194    /// The method first converts the array to LLE-e format and then
     195    /// linearizes the links. This requires two passes of the whole array
     196    /// as well as a dictionary to hold the smallest index of each group.
     197    ///
     198    /// The method assumes that there are no back links present.
     199    /// </remarks>
     200    public void LinearizeTreeStructures() {
     201      // Step 1: Convert the array into LLE-e
     202      var length = array.Length;
     203      var groups = new Dictionary<int, int>();
     204      for (var i = length - 1; i >= 0; i--) {
     205        if (array[i] == i) groups[i] = i;
     206        else array[i] = array[array[i]];
     207      }
     208      // Step 2: For all groups linearize the links
     209      for (var i = length - 1; i >= 0; i--) {
     210        if (array[i] == i) continue;
     211        var g = array[i];
     212        array[i] = groups[g];
     213        groups[g] = i;
     214      }
    218215    }
    219216  }

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkageCreator.cs

    r12285 r12288  
    2929
    3030namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    31   [Item("Linear Linkage Creator", "Base class for LLE-e creators.")]
     31  [Item("Linear Linkage Creator", "Base class for linear linkage creators.")]
    3232  [StorableClass]
    3333  public abstract class LinearLinkageCreator : InstrumentedOperator, ILinearLinkageCreator, IStochasticOperator {

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkageEncoding.cs

    r12285 r12288  
    3333
    3434namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    35   [Item("Linear Linkage Encoding", "Describes a linear linkage (LLE-e) encoding.")]
     35  [Item("Linear Linkage Encoding", "Describes a linear linkage (LLE) encoding.")]
    3636  [StorableClass]
    3737  public sealed class LinearLinkageEncoding : Encoding<ILinearLinkageCreator> {

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkageManipulator.cs

    r12285 r12288  
    2828
    2929namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    30   [Item("Linear Linkage Manipulator", "Base class for manipulators of the linear linkage encoding.")]
     30  [Item("Linear Linkage Manipulator", "Base class for linear linkage manipulators.")]
    3131  [StorableClass]
    3232  public abstract class LinearLinkageManipulator : InstrumentedOperator, ILinearLinkageManipulator, IStochasticOperator {

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/GraftManipulator.cs

    r12286 r12288  
    2020#endregion
    2121
     22using System;
    2223using System.Linq;
    2324using HeuristicLab.Common;
    … …  
    2829
    2930namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    30   [Item("Merge Group Manipulator", "Performs a maximum of N merge operations on the groups. Groups may be merged multiple times.")]
     31  [Item("Graft Manipulator", "Performs graft mutation as described in Du, J., Korkmaz, E.E., Alhajj, R., and Barker, K. 2004. Novel Clustering Approach that employs Genetic Algorithm with New Representation Scheme and Multiple Objectives. Data Warehousing and Knowledge Discovery, pp. 219-228. Springer Berlin Heidelberg.")]
    3132  [StorableClass]
    32   public sealed class MergeGroupManipulator : LinearLinkageManipulator {
     33  public sealed class GraftManipulator : LinearLinkageManipulator {
    3334
    34     public IValueLookupParameter<IntValue> NParameter {
    35       get { return (IValueLookupParameter<IntValue>)Parameters["N"]; }
     35    public IValueLookupParameter<IntValue> MaxGroupsParameter {
     36      get { return (IValueLookupParameter<IntValue>)Parameters["MaxGroups"]; }
    3637    }
    3738
    3839    [StorableConstructor]
    39     private MergeGroupManipulator(bool deserializing) : base(deserializing) { }
    40     private MergeGroupManipulator(MergeGroupManipulator original, Cloner cloner) : base(original, cloner) { }
    41     public MergeGroupManipulator() {
    42       Parameters.Add(new ValueLookupParameter<IntValue>("N", "The number of groups to merge.", new IntValue(1)));
     40    private GraftManipulator(bool deserializing) : base(deserializing) { }
     41    private GraftManipulator(GraftManipulator original, Cloner cloner) : base(original, cloner) { }
     42    public GraftManipulator() {
     43      Parameters.Add(new ValueLookupParameter<IntValue>("MaxGroups", "The maximum number of groups. If a value less or equal than 0 is used the number of groups is not limited.", new IntValue(-1)));
    4344    }
    44     public MergeGroupManipulator(int n)
     45    public GraftManipulator(int maxGroups)
    4546      : this() {
    46       NParameter.Value = new IntValue(n);
     47      MaxGroupsParameter.Value = new IntValue(maxGroups);
    4748    }
    4849
    4950    public override IDeepCloneable Clone(Cloner cloner) {
    50       return new MergeGroupManipulator(this, cloner);
     51      return new GraftManipulator(this, cloner);
    5152    }
    5253
    53     public static void Apply(IRandom random, LinearLinkage lle, int n) {
    54       var grouping = lle.GetGroups().ToList();
    55       if (grouping.Count == 1) return; // nothing to merge
     54    public static void Apply(IRandom random, LinearLinkage lle, int maxGroups) {
     55      int tries = lle.Length;
     56      var index = random.Next(lle.Length);
     57      while (tries > 0 && lle[index] == index) {
     58        index = random.Next(lle.Length);
     59        tries--;
     60      }
     61      if (lle[index] != index) Apply(random, lle, maxGroups, index);
     62    }
    5663
    57       for (var i = 0; i < n; i++) {
    58         var g1 = random.Next(grouping.Count);
    59         var g2 = random.Next(grouping.Count);
    60         while (g1 == g2) g2 = random.Next(grouping.Count);
    61         grouping[g1].AddRange(grouping[g2]);
    62         grouping.RemoveAt(g2);
    63         if (grouping.Count == 1) break;
     64    public static void Apply(IRandom random, LinearLinkage lle, int maxGroups, int index) {
     65      var groups = lle.Select((val, idx) => Tuple.Create(idx, val))
     66                      .Where(x => x.Item1 == x.Item2)
     67                      .Select(x => x.Item2).ToList();
     68      var z = groups.Count;
     69
     70      if (random.NextDouble() < 0.5)
     71        lle[index] = index; // divide the cluster into two
     72      else {
     73        var c = random.Next(z);
     74        if (groups[c] > index)
     75          lle[index] = groups[c]; // combine the portion with another class
     76        else {
     77          // combine the other class here
     78          lle[groups[c]] = lle[index];
     79          lle[index] = index;
     80        }
     81        lle.LinearizeTreeStructures();
    6482      }
    65 
    66       lle.SetGroups(grouping);
    6783    }
    6884
    6985    protected override void Manipulate(IRandom random, LinearLinkage lle) {
    70       var N = NParameter.ActualValue.Value;
    71       Apply(random, lle, N);
     86      var maxGroups = MaxGroupsParameter.ActualValue.Value;
     87      Apply(random, lle, maxGroups <= 0 ? int.MaxValue : maxGroups);
    7288    }
    7389  }

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/MultiLLEManipulator.cs

    r12286 r12288  
    5858      }
    5959      Operators.SetItemCheckedState(Operators.OfType<SwapItemManipulator>().First(), false);
     60      Operators.SetItemCheckedState(Operators.OfType<GraftManipulator>().First(), false);
    6061      SelectedOperatorParameter.ActualName = "SelectedManipulatorOperator";
    6162    }

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Plugin.cs.frame

    r12285 r12288  
    2323
    2424namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    25   [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE-e).", "3.3.11.$WCREV$")]
     25  [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.3.11.$WCREV$")]
    2626  [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.3.dll", PluginFileType.Assembly)]
    2727  [PluginDependency("HeuristicLab.Collections", "3.3")]

  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/ShakingOperators/LLEShakingOperator.cs

    r12286 r12288  
    3434  /// A shaking operator for VNS.
    3535  /// </summary>
    36   [Item("LLE Shaking Operator", "A shaking operator for VNS which LLE manipulators to perform the shaking.")]
     36  [Item("LLE Shaking Operator", "A shaking operator for VNS which uses LLE manipulators to perform the shaking.")]
    3737  [StorableClass]
    3838  public class LLEShakingOperator : ShakingOperator<ILinearLinkageManipulator>, IStochasticOperator, ILinearLinkageShakingOperator {
Note: See TracChangeset for help on using the changeset viewer.