Changeset 12286


Ignore:
Timestamp:
04/04/15 23:58:27 (4 years ago)
Author:
abeham
Message:

#2319:

  • Removed LargestGroupFirstCrossover (slow and not mentioned in the literature)
  • Added manipulators
  • Added multi-operators
Location:
branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3
Files:
4 added
2 deleted
2 edited
2 moved

Legend:

Unmodified
Added
Removed
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj

    r12285 r12286  
    106106    <Compile Include="Crossovers\GroupCrossover.cs" />
    107107    <Compile Include="Crossovers\LowestIndexMaxCrossover.cs" />
     108    <Compile Include="Crossovers\MultiLLECrossover.cs" />
    108109    <Compile Include="Interfaces\ILinearLinkageCreator.cs" />
    109110    <Compile Include="LinearLinkage.cs" />
     
    112113    <Compile Include="LinearLinkageManipulator.cs" />
    113114    <Compile Include="LinearLinkageCrossover.cs" />
    114     <Compile Include="ShakingOperators\SplitGroupShakingOperator.cs" />
    115     <Compile Include="ShakingOperators\SwapNShakingOperator.cs" />
     115    <Compile Include="Manipulators\MoveItemManipulator.cs" />
     116    <Compile Include="Manipulators\MergeGroupManipulator.cs" />
     117    <Compile Include="Manipulators\MultiLLEManipulator.cs" />
     118    <Compile Include="ShakingOperators\LLEShakingOperator.cs" />
    116119    <None Include="HeuristicLab.snk" />
    117120    <None Include="Plugin.cs.frame" />
     
    123126    <Compile Include="Interfaces\ILinearLinkageShakingOperator.cs" />
    124127    <Compile Include="Manipulators\SplitGroupManipulator.cs" />
    125     <Compile Include="Manipulators\SwapNManipulator.cs" />
     128    <Compile Include="Manipulators\SwapItemManipulator.cs" />
    126129    <Compile Include="Plugin.cs" />
    127130    <None Include="Properties\AssemblyInfo.cs.frame" />
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/SplitGroupManipulator.cs

    r12285 r12286  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
     
    5354    }
    5455
     56    public static void Apply(IRandom random, LinearLinkage lle, int n) {
     57      var grouping = lle.GetGroups().ToList();
     58      var groupsLargerOne = grouping.Select((v, i) => Tuple.Create(i, v))
     59                                    .Where(x => x.Item2.Count > 1)
     60                                    .ToDictionary(x => x.Item1, x => x.Item2);
     61      if (groupsLargerOne.Count == 0) return;
     62      var toRemove = new List<int>();
     63
     64      for (var i = 0; i < n; i++) {
     65        var g = groupsLargerOne.Keys.SampleRandom(random);
     66        var idx = random.Next(1, groupsLargerOne[g].Count);
     67        // shuffle here to avoid a potential bias of grouping smaller and larger numbers together
     68        var tmp = groupsLargerOne[g].Shuffle(random);
     69        var before = new List<int>();
     70        var after = new List<int>();
     71        foreach (var t in tmp) {
     72          if (idx > 0) before.Add(t);
     73          else after.Add(t);
     74          idx--;
     75        }
     76        if (before.Count > 1) groupsLargerOne[grouping.Count] = before;
     77        grouping.Add(before);
     78        if (after.Count > 1) groupsLargerOne[grouping.Count] = after;
     79        grouping.Add(after);
     80        toRemove.Add(g);
     81        groupsLargerOne.Remove(g);
     82        if (groupsLargerOne.Count == 0) break;
     83      }
     84      foreach (var r in toRemove.OrderByDescending(x => x))
     85        grouping.RemoveAt(r);
     86
     87      lle.SetGroups(grouping);
     88    }
     89
    5590    protected override void Manipulate(IRandom random, LinearLinkage lle) {
    5691      var N = NParameter.ActualValue.Value;
    57 
    58       // shuffle here to avoid bias due to lowest-index-first encoding
    59       var grouping = lle.GetGroups().Select(x => x.ToList()).Shuffle(random).ToList();
    60       var groupsLargerOne = grouping.Count(x => x.Count > 1);
    61       if (groupsLargerOne == 0) return;
    62 
    63       var i = -1;
    64       while (N > 0) {
    65         i = (i + 1) % grouping.Count;
    66         if (grouping[i].Count <= 1) continue;
    67         if (random.NextDouble() < N / (double)groupsLargerOne) {
    68           var idx = random.Next(1, grouping[i].Count);
    69           // shuffle here to avoid a potential bias of grouping smaller and larger numbers together
    70           var tmp = grouping[i].Shuffle(random);
    71           var before = new List<int>();
    72           var after = new List<int>();
    73           foreach (var t in tmp) {
    74             if (idx > 0) before.Add(t);
    75             else after.Add(t);
    76             idx--;
    77           }
    78           grouping.Add(before);
    79           grouping.Add(after);
    80           grouping.RemoveAt(i);
    81           i--;
    82           N--;
    83           if (before.Count > 1 && after.Count > 1) groupsLargerOne++;
    84           else if (before.Count == 1 && after.Count == 1) groupsLargerOne--;
    85         }
    86         if (groupsLargerOne == 0) break;
    87       }
    88       lle.SetGroups(grouping);
     92      Apply(random, lle, N);
    8993    }
    9094  }
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/SwapItemManipulator.cs

    r12285 r12286  
    2020#endregion
    2121
    22 using System.Collections.Generic;
    2322using System.Linq;
    2423using HeuristicLab.Common;
    2524using HeuristicLab.Core;
    2625using HeuristicLab.Data;
    27 using HeuristicLab.Operators;
    28 using HeuristicLab.Optimization;
    2926using HeuristicLab.Parameters;
    3027using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3128
    3229namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    33   [Item("Swap-n Manipulator", "")]
     30  [Item("Swap Item Manipulator", "Swaps items between groups. Items may be swapped multiple times.")]
    3431  [StorableClass]
    35   public sealed class SwapNManipulator : InstrumentedOperator, ILinearLinkageManipulator, IStochasticOperator {
    36     public ILookupParameter<IRandom> RandomParameter {
    37       get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    38     }
    39 
    40     public ILookupParameter<LinearLinkage> LLEParameter {
    41       get { return (ILookupParameter<LinearLinkage>)Parameters["LLE"]; }
    42     }
     32  public sealed class SwapItemManipulator : LinearLinkageManipulator {
    4333
    4434    public IValueLookupParameter<IntValue> NParameter {
     
    4737
    4838    [StorableConstructor]
    49     private SwapNManipulator(bool deserializing) : base(deserializing) { }
    50     private SwapNManipulator(SwapNManipulator original, Cloner cloner) : base(original, cloner) { }
    51     public SwapNManipulator() {
    52       Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
    53       Parameters.Add(new LookupParameter<LinearLinkage>("LLE", "The encoding vector that is to be manipulated."));
    54       Parameters.Add(new ValueLookupParameter<IntValue>("N", "The number of swaps to perform.", new IntValue(2)));
     39    private SwapItemManipulator(bool deserializing) : base(deserializing) { }
     40    private SwapItemManipulator(SwapItemManipulator original, Cloner cloner) : base(original, cloner) { }
     41    public SwapItemManipulator() {
     42      Parameters.Add(new ValueLookupParameter<IntValue>("N", "The number of swaps to perform.", new IntValue(1)));
    5543    }
    56     public SwapNManipulator(int n)
     44    public SwapItemManipulator(int n)
    5745      : this() {
    5846      NParameter.Value = new IntValue(n);
     
    6048
    6149    public override IDeepCloneable Clone(Cloner cloner) {
    62       return new SwapNManipulator(this, cloner);
     50      return new SwapItemManipulator(this, cloner);
    6351    }
    6452
    65     public override IOperation InstrumentedApply() {
    66       var random = RandomParameter.ActualValue;
    67       var vector = LLEParameter.ActualValue;
    68       var N = NParameter.ActualValue.Value;
     53    public static void Apply(IRandom random, LinearLinkage lle, int n) {
     54      var grouping = lle.GetGroups().Select(x => x.ToList()).ToList();
     55      if (grouping.Count == 1) return; // nothing can be changed
    6956
    70       var grouping = vector.GetGroups().Select(x => x.ToList()).ToList();
    71       if (grouping.Count == 1) return base.InstrumentedApply(); // nothing can be changed
    72       var touched = new HashSet<int>();
    7357      var prevGroup = random.Next(grouping.Count);
    7458      var prevItem = random.Next(grouping[prevGroup].Count);
    75       touched.Add(grouping[prevGroup][prevItem]);
    76       for (var i = 0; i < N; i++) {
    77         int nextGroup = -1, nextItem = -1, tries = 0;
     59      for (var i = 0; i < n; i++) {
     60        int nextGroup, nextItem;
    7861        do {
    79           if (tries >= 100) break;
    8062          nextGroup = random.Next(grouping.Count);
    8163          nextItem = random.Next(grouping[nextGroup].Count);
    82           tries++;
    83         } while (nextGroup == prevGroup || touched.Contains(grouping[nextGroup][nextItem]));
    84         if (tries >= 100) break;
     64        } while (nextGroup == prevGroup);
    8565        var h = grouping[nextGroup][nextItem];
    8666        grouping[nextGroup][nextItem] = grouping[prevGroup][prevItem];
    8767        grouping[prevGroup][prevItem] = h;
    88         touched.Add(h);
    8968        prevGroup = nextGroup;
    9069        prevItem = nextItem;
    9170      }
    92       vector.SetGroups(grouping);
    93       return base.InstrumentedApply();
     71
     72      lle.SetGroups(grouping);
     73    }
     74
     75    protected override void Manipulate(IRandom random, LinearLinkage lle) {
     76      var N = NParameter.ActualValue.Value;
     77      Apply(random, lle, N);
    9478    }
    9579  }
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/ShakingOperators/LLEShakingOperator.cs

    r12285 r12286  
    3434  /// A shaking operator for VNS.
    3535  /// </summary>
    36   [Item("Split Group Shaking Operator", "A shaking operator for VNS which uses split group manipulators to perform the shaking.")]
     36  [Item("LLE Shaking Operator", "A shaking operator for VNS which LLE manipulators to perform the shaking.")]
    3737  [StorableClass]
    38   public class SplitGroupShakingOperator : ShakingOperator<ILinearLinkageManipulator>, IStochasticOperator, ILinearLinkageShakingOperator {
     38  public class LLEShakingOperator : ShakingOperator<ILinearLinkageManipulator>, IStochasticOperator, ILinearLinkageShakingOperator {
    3939
    4040    public ILookupParameter<IRandom> RandomParameter {
     
    5151
    5252    [StorableConstructor]
    53     protected SplitGroupShakingOperator(bool deserializing) : base(deserializing) { }
    54     protected SplitGroupShakingOperator(SplitGroupShakingOperator original, Cloner cloner) : base(original, cloner) { }
    55     public SplitGroupShakingOperator()
     53    protected LLEShakingOperator(bool deserializing) : base(deserializing) { }
     54    protected LLEShakingOperator(LLEShakingOperator original, Cloner cloner) : base(original, cloner) { }
     55    public LLEShakingOperator()
    5656      : base() {
    5757      Parameters.Add(new LookupParameter<LinearLinkage>("LLE", "The encoding to shake."));
    5858      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used for stochastic shaking operators."));
    59       for (var i = 1; i < 6; i++) Operators.Add(new SplitGroupManipulator(i));
     59      for (var i = 1; i < 4; i++) {
     60        Operators.Add(new MoveItemManipulator(i * 2));
     61        Operators.Add(new SwapItemManipulator(i * 2));
     62        Operators.Add(new SplitGroupManipulator(i * 2));
     63        Operators.Add(new MergeGroupManipulator(i * 2));
     64      }
    6065    }
    6166
    6267    public override IDeepCloneable Clone(Cloner cloner) {
    63       return new SplitGroupShakingOperator(this, cloner);
     68      return new LLEShakingOperator(this, cloner);
    6469    }
    6570
Note: See TracChangeset for help on using the changeset viewer.