Changeset 12288 for branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/GraftManipulator.cs

Timestamp:

04/06/15 22:41:24 (9 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

File:

• branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/GraftManipulator.cs (copied) (copied from branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/MergeGroupManipulator.cs) (2 diffs)

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

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Linq;
 using HeuristicLab.Common;
@@ -28 +29 @@
 
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
-  [Item("Merge Group Manipulator", "Performs a maximum of N merge operations on the groups. Groups may be merged multiple times.")]
+  [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.")]
   [StorableClass]
-  public sealed class MergeGroupManipulator : LinearLinkageManipulator {
+  public sealed class GraftManipulator : LinearLinkageManipulator {
 
-    public IValueLookupParameter<IntValue> NParameter {
-      get { return (IValueLookupParameter<IntValue>)Parameters["N"]; }
+    public IValueLookupParameter<IntValue> MaxGroupsParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["MaxGroups"]; }
     }
 
     [StorableConstructor]
-    private MergeGroupManipulator(bool deserializing) : base(deserializing) { }
-    private MergeGroupManipulator(MergeGroupManipulator original, Cloner cloner) : base(original, cloner) { }
-    public MergeGroupManipulator() {
-      Parameters.Add(new ValueLookupParameter<IntValue>("N", "The number of groups to merge.", new IntValue(1)));
+    private GraftManipulator(bool deserializing) : base(deserializing) { }
+    private GraftManipulator(GraftManipulator original, Cloner cloner) : base(original, cloner) { }
+    public GraftManipulator() {
+      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)));
     }
-    public MergeGroupManipulator(int n)
+    public GraftManipulator(int maxGroups)
       : this() {
-      NParameter.Value = new IntValue(n);
+      MaxGroupsParameter.Value = new IntValue(maxGroups);
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new MergeGroupManipulator(this, cloner);
+      return new GraftManipulator(this, cloner);
     }
 
-    public static void Apply(IRandom random, LinearLinkage lle, int n) {
-      var grouping = lle.GetGroups().ToList();
-      if (grouping.Count == 1) return; // nothing to merge
+    public static void Apply(IRandom random, LinearLinkage lle, int maxGroups) {
+      int tries = lle.Length;
+      var index = random.Next(lle.Length);
+      while (tries > 0 && lle[index] == index) {
+        index = random.Next(lle.Length);
+        tries--;
+      }
+      if (lle[index] != index) Apply(random, lle, maxGroups, index);
+    }
 
-      for (var i = 0; i < n; i++) {
-        var g1 = random.Next(grouping.Count);
-        var g2 = random.Next(grouping.Count);
-        while (g1 == g2) g2 = random.Next(grouping.Count);
-        grouping[g1].AddRange(grouping[g2]);
-        grouping.RemoveAt(g2);
-        if (grouping.Count == 1) break;
+    public static void Apply(IRandom random, LinearLinkage lle, int maxGroups, int index) {
+      var groups = lle.Select((val, idx) => Tuple.Create(idx, val))
+                      .Where(x => x.Item1 == x.Item2)
+                      .Select(x => x.Item2).ToList();
+      var z = groups.Count;
+
+      if (random.NextDouble() < 0.5)
+        lle[index] = index; // divide the cluster into two
+      else {
+        var c = random.Next(z);
+        if (groups[c] > index)
+          lle[index] = groups[c]; // combine the portion with another class
+        else {
+          // combine the other class here
+          lle[groups[c]] = lle[index];
+          lle[index] = index;
+        }
+        lle.LinearizeTreeStructures();
       }
-
-      lle.SetGroups(grouping);
     }
 
     protected override void Manipulate(IRandom random, LinearLinkage lle) {
-      var N = NParameter.ActualValue.Value;
-      Apply(random, lle, N);
+      var maxGroups = MaxGroupsParameter.ActualValue.Value;
+      Apply(random, lle, maxGroups <= 0 ? int.MaxValue : maxGroups);
     }
   }