Changeset 12286 for branches/LinearLinkage

Timestamp:

04/04/15 23:58:27 (10 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:

• Crossovers/LargestGroupFirstCrossover.cs (deleted)
• Crossovers/MultiLLECrossover.cs (added)
• HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj (modified) (3 diffs)
• Manipulators/MergeGroupManipulator.cs (added)
• Manipulators/MoveItemManipulator.cs (added)
• Manipulators/MultiLLEManipulator.cs (added)
• Manipulators/SplitGroupManipulator.cs (modified) (2 diffs)
• Manipulators/SwapItemManipulator.cs (moved) (moved from branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/SwapNManipulator.cs) (3 diffs)
• ShakingOperators/LLEShakingOperator.cs (moved) (moved from branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/ShakingOperators/SplitGroupShakingOperator.cs) (2 diffs)
• ShakingOperators/SwapNShakingOperator.cs (deleted)

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

@@ -106 +106 @@
     <Compile Include="Crossovers\GroupCrossover.cs" />
     <Compile Include="Crossovers\LowestIndexMaxCrossover.cs" />
+    <Compile Include="Crossovers\MultiLLECrossover.cs" />
     <Compile Include="Interfaces\ILinearLinkageCreator.cs" />
     <Compile Include="LinearLinkage.cs" />
@@ -112 +113 @@
     <Compile Include="LinearLinkageManipulator.cs" />
     <Compile Include="LinearLinkageCrossover.cs" />
-    <Compile Include="ShakingOperators\SplitGroupShakingOperator.cs" />
-    <Compile Include="ShakingOperators\SwapNShakingOperator.cs" />
+    <Compile Include="Manipulators\MoveItemManipulator.cs" />
+    <Compile Include="Manipulators\MergeGroupManipulator.cs" />
+    <Compile Include="Manipulators\MultiLLEManipulator.cs" />
+    <Compile Include="ShakingOperators\LLEShakingOperator.cs" />
     <None Include="HeuristicLab.snk" />
     <None Include="Plugin.cs.frame" />
@@ -123 +126 @@
     <Compile Include="Interfaces\ILinearLinkageShakingOperator.cs" />
     <Compile Include="Manipulators\SplitGroupManipulator.cs" />
-    <Compile Include="Manipulators\SwapNManipulator.cs" />
+    <Compile Include="Manipulators\SwapItemManipulator.cs" />
     <Compile Include="Plugin.cs" />
     <None Include="Properties\AssemblyInfo.cs.frame" />

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/SplitGroupManipulator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -53 +54 @@
     }
 
+    public static void Apply(IRandom random, LinearLinkage lle, int n) {
+      var grouping = lle.GetGroups().ToList();
+      var groupsLargerOne = grouping.Select((v, i) => Tuple.Create(i, v))
+                                    .Where(x => x.Item2.Count > 1)
+                                    .ToDictionary(x => x.Item1, x => x.Item2);
+      if (groupsLargerOne.Count == 0) return;
+      var toRemove = new List<int>();
+
+      for (var i = 0; i < n; i++) {
+        var g = groupsLargerOne.Keys.SampleRandom(random);
+        var idx = random.Next(1, groupsLargerOne[g].Count);
+        // shuffle here to avoid a potential bias of grouping smaller and larger numbers together
+        var tmp = groupsLargerOne[g].Shuffle(random);
+        var before = new List<int>();
+        var after = new List<int>();
+        foreach (var t in tmp) {
+          if (idx > 0) before.Add(t);
+          else after.Add(t);
+          idx--;
+        }
+        if (before.Count > 1) groupsLargerOne[grouping.Count] = before;
+        grouping.Add(before);
+        if (after.Count > 1) groupsLargerOne[grouping.Count] = after;
+        grouping.Add(after);
+        toRemove.Add(g);
+        groupsLargerOne.Remove(g);
+        if (groupsLargerOne.Count == 0) break;
+      }
+      foreach (var r in toRemove.OrderByDescending(x => x))
+        grouping.RemoveAt(r);
+
+      lle.SetGroups(grouping);
+    }
+
     protected override void Manipulate(IRandom random, LinearLinkage lle) {
       var N = NParameter.ActualValue.Value;
-
-      // shuffle here to avoid bias due to lowest-index-first encoding
-      var grouping = lle.GetGroups().Select(x => x.ToList()).Shuffle(random).ToList();
-      var groupsLargerOne = grouping.Count(x => x.Count > 1);
-      if (groupsLargerOne == 0) return;
-
-      var i = -1;
-      while (N > 0) {
-        i = (i + 1) % grouping.Count;
-        if (grouping[i].Count <= 1) continue;
-        if (random.NextDouble() < N / (double)groupsLargerOne) {
-          var idx = random.Next(1, grouping[i].Count);
-          // shuffle here to avoid a potential bias of grouping smaller and larger numbers together
-          var tmp = grouping[i].Shuffle(random);
-          var before = new List<int>();
-          var after = new List<int>();
-          foreach (var t in tmp) {
-            if (idx > 0) before.Add(t);
-            else after.Add(t);
-            idx--;
-          }
-          grouping.Add(before);
-          grouping.Add(after);
-          grouping.RemoveAt(i);
-          i--;
-          N--;
-          if (before.Count > 1 && after.Count > 1) groupsLargerOne++;
-          else if (before.Count == 1 && after.Count == 1) groupsLargerOne--;
-        }
-        if (groupsLargerOne == 0) break;
-      }
-      lle.SetGroups(grouping);
+      Apply(random, lle, N);
     }
   }

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/SwapItemManipulator.cs

@@ -20 +20 @@
 #endregion
 
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
-using HeuristicLab.Operators;
-using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
-  [Item("Swap-n Manipulator", "")]
+  [Item("Swap Item Manipulator", "Swaps items between groups. Items may be swapped multiple times.")]
   [StorableClass]
-  public sealed class SwapNManipulator : InstrumentedOperator, ILinearLinkageManipulator, IStochasticOperator {
-    public ILookupParameter<IRandom> RandomParameter {
-      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
-    }
-
-    public ILookupParameter<LinearLinkage> LLEParameter {
-      get { return (ILookupParameter<LinearLinkage>)Parameters["LLE"]; }
-    }
+  public sealed class SwapItemManipulator : LinearLinkageManipulator {
 
     public IValueLookupParameter<IntValue> NParameter {
@@ -47 +37 @@
 
     [StorableConstructor]
-    private SwapNManipulator(bool deserializing) : base(deserializing) { }
-    private SwapNManipulator(SwapNManipulator original, Cloner cloner) : base(original, cloner) { }
-    public SwapNManipulator() {
-      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
-      Parameters.Add(new LookupParameter<LinearLinkage>("LLE", "The encoding vector that is to be manipulated."));
-      Parameters.Add(new ValueLookupParameter<IntValue>("N", "The number of swaps to perform.", new IntValue(2)));
+    private SwapItemManipulator(bool deserializing) : base(deserializing) { }
+    private SwapItemManipulator(SwapItemManipulator original, Cloner cloner) : base(original, cloner) { }
+    public SwapItemManipulator() {
+      Parameters.Add(new ValueLookupParameter<IntValue>("N", "The number of swaps to perform.", new IntValue(1)));
     }
-    public SwapNManipulator(int n)
+    public SwapItemManipulator(int n)
       : this() {
       NParameter.Value = new IntValue(n);
@@ -60 +48 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new SwapNManipulator(this, cloner);
+      return new SwapItemManipulator(this, cloner);
     }
 
-    public override IOperation InstrumentedApply() {
-      var random = RandomParameter.ActualValue;
-      var vector = LLEParameter.ActualValue;
-      var N = NParameter.ActualValue.Value;
+    public static void Apply(IRandom random, LinearLinkage lle, int n) {
+      var grouping = lle.GetGroups().Select(x => x.ToList()).ToList();
+      if (grouping.Count == 1) return; // nothing can be changed
 
-      var grouping = vector.GetGroups().Select(x => x.ToList()).ToList();
-      if (grouping.Count == 1) return base.InstrumentedApply(); // nothing can be changed
-      var touched = new HashSet<int>();
       var prevGroup = random.Next(grouping.Count);
       var prevItem = random.Next(grouping[prevGroup].Count);
-      touched.Add(grouping[prevGroup][prevItem]);
-      for (var i = 0; i < N; i++) {
-        int nextGroup = -1, nextItem = -1, tries = 0;
+      for (var i = 0; i < n; i++) {
+        int nextGroup, nextItem;
         do {
-          if (tries >= 100) break;
           nextGroup = random.Next(grouping.Count);
           nextItem = random.Next(grouping[nextGroup].Count);
-          tries++;
-        } while (nextGroup == prevGroup || touched.Contains(grouping[nextGroup][nextItem]));
-        if (tries >= 100) break;
+        } while (nextGroup == prevGroup);
         var h = grouping[nextGroup][nextItem];
         grouping[nextGroup][nextItem] = grouping[prevGroup][prevItem];
         grouping[prevGroup][prevItem] = h;
-        touched.Add(h);
         prevGroup = nextGroup;
         prevItem = nextItem;
       }
-      vector.SetGroups(grouping);
-      return base.InstrumentedApply();
+
+      lle.SetGroups(grouping);
+    }
+
+    protected override void Manipulate(IRandom random, LinearLinkage lle) {
+      var N = NParameter.ActualValue.Value;
+      Apply(random, lle, N);
     }
   }

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

@@ -34 +34 @@
   /// A shaking operator for VNS.
   /// </summary>
-  [Item("Split Group Shaking Operator", "A shaking operator for VNS which uses split group manipulators to perform the shaking.")]
+  [Item("LLE Shaking Operator", "A shaking operator for VNS which LLE manipulators to perform the shaking.")]
   [StorableClass]
-  public class SplitGroupShakingOperator : ShakingOperator<ILinearLinkageManipulator>, IStochasticOperator, ILinearLinkageShakingOperator {
+  public class LLEShakingOperator : ShakingOperator<ILinearLinkageManipulator>, IStochasticOperator, ILinearLinkageShakingOperator {
 
     public ILookupParameter<IRandom> RandomParameter {
@@ -51 +51 @@
 
     [StorableConstructor]
-    protected SplitGroupShakingOperator(bool deserializing) : base(deserializing) { }
-    protected SplitGroupShakingOperator(SplitGroupShakingOperator original, Cloner cloner) : base(original, cloner) { }
-    public SplitGroupShakingOperator()
+    protected LLEShakingOperator(bool deserializing) : base(deserializing) { }
+    protected LLEShakingOperator(LLEShakingOperator original, Cloner cloner) : base(original, cloner) { }
+    public LLEShakingOperator()
       : base() {
       Parameters.Add(new LookupParameter<LinearLinkage>("LLE", "The encoding to shake."));
       Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used for stochastic shaking operators."));
-      for (var i = 1; i < 6; i++) Operators.Add(new SplitGroupManipulator(i));
+      for (var i = 1; i < 4; i++) {
+        Operators.Add(new MoveItemManipulator(i * 2));
+        Operators.Add(new SwapItemManipulator(i * 2));
+        Operators.Add(new SplitGroupManipulator(i * 2));
+        Operators.Add(new MergeGroupManipulator(i * 2));
+      }
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new SplitGroupShakingOperator(this, cloner);
+      return new LLEShakingOperator(this, cloner);
     }