Changeset 14431

Timestamp:

11/30/16 14:49:22 (6 years ago)

Author:

jzenisek

Message:

#2707 updated clustering: implemented a quite generic version

Location:

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators

Files:

• Cluster.cs (modified) (8 diffs)
• GeographicDistanceClusterCreator.cs (modified) (4 diffs)
• TemporalDistanceClusterCreator.cs (modified) (3 diffs)

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/Cluster.cs

@@ -1 +1 @@
 using System;
+using System.Collections;
 using System.Collections.Generic;
-using System.Linq;
-using System.Security.Cryptography.X509Certificates;
-using System.Text;
-using System.Threading.Tasks;
 using HeuristicLab.Core;
 using HeuristicLab.Problems.VehicleRouting.Interfaces;
-using HeuristicLab.Problems.VehicleRouting.Variants;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
 
-
   public class ClusterAlgorithm<C,CO> where C : Cluster<CO> where CO : ClusterElement {
 
-    //public static List<C> KMeans(IVRPProblemInstance instance, IRandom random, List<CO> clusterObjects, int k, double changeThreshold) {
-    //  HashSet<int> initMeans = new HashSet<int>();
-    //  int nextMean = -1;
-
-    //  for (int i = 0; i < k && i < clusterObjects.Count; i++) {
-    //    //C cluster = new C()
-    //  }
-
-
-
-
-    //}
-
-    //private static int KMeansRun(List<C> clusters, List<CO> clusterObjects) {
-      
-    //}
-
+    public static List<C> KMeans(IRandom random, List<CO> clusterElements, int k, double changeThreshold, bool minimizeImpact) {
+      HashSet<int> initMeans = new HashSet<int>();
+      int nextMean = -1;
+
+      List<C> clusters = CreateCList();
+
+      // (1) initialize each cluster with a random element as mean
+      for (int i = 0; i < k && i < clusterElements.Count; i++) {
+        C cluster = (C)Activator.CreateInstance(typeof(C));
+        cluster.Id = i;
+
+        do {
+          nextMean = random.Next(0, clusterElements.Count);
+        } while (initMeans.Contains(nextMean));
+        initMeans.Add(nextMean);
+        cluster.SetMean(clusterElements[nextMean]);
+        clusters.Add(cluster);
+      }
+
+      // (2) repeat clustering until change rate is below threshold
+      double changeRate = 0.0;
+
+      do {
+        int changes = KMeansRun(clusters, clusterElements, minimizeImpact);
+        changeRate = (double)changes / clusterElements.Count;
+      } while (changeRate > changeThreshold);
+
+
+      // remove empty clusters
+      clusters.RemoveAll(c => c.Elements.Count.Equals(0));
+
+      return clusters;
+    }
+
+    private static int KMeansRun(List<C> clusters, List<CO> clusterElements, bool minimizeImpact) {
+      int changes = 0;
+
+      // clear clusters from previous assigned elements
+      foreach (var c in clusters) {
+        c.Elements.Clear();
+      }
+
+      // assign elements to currently most suitable clusters
+      foreach (var e in clusterElements) {
+        int optClusterIdx = 0;
+        double optImpact = clusters[optClusterIdx].CalculateImpact(e);
+        for (int i = 1; i < clusters.Count; i++) {
+          double impact = clusters[i].CalculateImpact(e);
+          if (
+            // optimal impact: max variance decrease (biggest negative or smallest positive value)
+            (minimizeImpact && impact < optImpact) ||
+            // optimal impact: min variance increase, if no increase possible: min decrease (smallest negative or positive value)
+            //(!minimizeImpact && ((optImpact > 0 && impact < optImpact) || (optImpact < 0 && impact > optImpact)))) {
+            (!minimizeImpact && impact > optImpact)
+            ) { 
+
+            optImpact = impact;
+            optClusterIdx = i;
+          }
+        }
+        if (clusters[optClusterIdx].AddObject(e)) {
+          changes++;
+        }
+      }
+
+      // update mean and variance
+      foreach (var c in clusters) {
+        c.CalculateMean();
+        c.CalculateVariance();
+      }
+
+      return changes;
+    }
+
+    private static List<C> CreateCList() {
+      var listType = typeof(List<>);
+      var constructedListType = listType.MakeGenericType(typeof(C));
+      return (List<C>)Activator.CreateInstance(constructedListType);
+    }
   }
 
   #region Cluster
-  public interface ICluster<T> where T : IClusterElement {
-    double CalculateImpact(T o);
-    void CalculateMean();
+  public interface ICluster<T> where T : ClusterElement {
     void SetMean(T o);
     bool AddObject(T o);
+    void CalculateMean();
+    void CalculateVariance();
+    double CalculateImpact(T e);
+    double CalculateDistance(T e1, T e2);
+
   }
   public abstract class Cluster<T> : ICluster<T> where T : ClusterElement {
     public int Id;
-    protected readonly IVRPProblemInstance instance;
+
     public List<T> Elements { get; private set; }
 
@@ -49 +109 @@
     public double Variance { get; set; }
 
-    public Cluster(IVRPProblemInstance instance, int id) {
-      this.instance = instance;
+    protected Cluster() {
+      Elements = new List<T>();
+    }
+
+    protected Cluster(int id) {
       Id = id;
       Elements = new List<T>();
 
     }
-    public bool AddObject(T o) {
-      Elements.Add(o);
-
-      bool clusterChanged = o.ClusterId != Id;
-      o.ClusterId = Id;
+
+    public bool AddObject(T e) {
+      Elements.Add(e);
+
+      bool clusterChanged = e.ClusterId != Id;
+      e.ClusterId = Id;
       return clusterChanged;
     }
 
-    public void SetMean(T o) {
-      Mean = o;
+    public void SetMean(T e) {
+      Mean = e;
       Mean.ClusterId = Id;
     }
@@ -70 +134 @@
     public abstract void CalculateMean();
 
-    public abstract void CalculateVariance();
-
-    public abstract double CalculateImpact(T o);
-
-  }
-  public class SpatialDistanceCluster : Cluster<SpatialDistanceClusterElement> {
-    public SpatialDistanceCluster(IVRPProblemInstance instance, int id) : base(instance, id) {
-    }
-
-    public override void CalculateMean() {
-      int dimensions = instance.Coordinates.Columns;
-      SpatialDistanceClusterElement mean = new SpatialDistanceClusterElement(-1, dimensions, Id);
-      foreach (SpatialDistanceClusterElement o in Elements) {
-        double[] coordinates = instance.GetCoordinates(o.Id);
-        for (int i = 0; i < coordinates.Length; i++) {
-          mean.Coordinates[i] += (coordinates[i] / Elements.Count);
-        }
-      }
-      Mean = mean;
-    }
-
-    public override void CalculateVariance() {
-      if(Mean == null)
-        CalculateMean();
-
-      Variance = 0.0;
-      foreach (SpatialDistanceClusterElement o in Elements) {
-        Variance += Math.Pow(Mean.GetDistance(o), 2);
-      }
-      Variance /= Elements.Count;
-    }
-
-    public override double CalculateImpact(SpatialDistanceClusterElement o) {
+    public abstract double CalculateDistance(T e1, T e2);
+
+    public virtual void CalculateVariance() {
       if (Mean == null)
         CalculateMean();
 
-      double newVariance = (Variance*Elements.Count + Math.Pow(Mean.GetDistance(o), 2))/(Elements.Count + 1);
+      Variance = 0.0;
+      foreach (T e in Elements) {
+        Variance += Math.Pow(CalculateDistance(Mean, e), 2);
+      }
+      Variance /= Elements.Count;
+    }
+
+    public virtual double CalculateImpact(T e) {
+      if (Mean == null)
+        CalculateMean();
+
+      double newVariance = (Variance * Elements.Count + Math.Pow(CalculateDistance(Mean, e), 2)) / (Elements.Count + 1);
       return newVariance - Variance;
     }
+
+  }
+  public class SpatialDistanceCluster : Cluster<SpatialDistanceClusterElement> {
+    public SpatialDistanceCluster() : base() {
+    }
+
+    public SpatialDistanceCluster(int id) : base(id) {
+    }
+
+    public override void CalculateMean() {
+      int dimensions = (Mean != null) ? Mean.Coordinates.Length : (Elements.Count > 0) ? Elements[0].Coordinates.Length : 0;
+      SpatialDistanceClusterElement mean = new SpatialDistanceClusterElement(-1, dimensions, Id);
+      foreach (SpatialDistanceClusterElement e in Elements) {
+        for (int i = 0; i < Mean.Coordinates.Length; i++) {
+          mean.Coordinates[i] += (e.Coordinates[i] / Elements.Count);
+        }
+      }
+      Mean = mean;
+    }
+
+    public override double CalculateDistance(SpatialDistanceClusterElement e1, SpatialDistanceClusterElement e2) {
+      if (!e1.Coordinates.Length.Equals(e2.Coordinates.Length)) {
+        throw new ArgumentException("Distance could not be calculated since number of dimensions is unequal.");
+      }
+
+      double distance = 0.0;
+      for (int i = 0; i < e1.Coordinates.Length; i++) {
+        distance += Math.Pow(e1.Coordinates[i] - e2.Coordinates[i], 2);
+      }
+
+      return Math.Sqrt(distance);
+    }
   }
 
   public class TemporalDistanceCluster : Cluster<TemporalDistanceClusterElement> {
-    public TemporalDistanceCluster(ITimeWindowedProblemInstance instance, int id) : base(instance, id) {
-    }
-
+    public TemporalDistanceCluster() : base() {
+    }
+
+    public TemporalDistanceCluster(int id) : base(id) {
+    }
 
     public override void CalculateMean() {
@@ -125 +204 @@
     }
 
-    public override void CalculateVariance() {
-      if (Mean == null)
-        CalculateMean();
-
-      Variance = 0.0;
-      foreach (TemporalDistanceClusterElement e in Elements) {
-        Variance += Math.Pow(Math.Abs(Mean.ReadyTime - e.ReadyTime) + Math.Abs(Mean.DueTime - e.DueTime), 2);
-      }
-      Variance /= Elements.Count;
-    }
-
-    public override double CalculateImpact(TemporalDistanceClusterElement o) {
-      if(Mean == null)
-        CalculateMean();
-
-      double newVariance = (Variance * Elements.Count + Math.Pow(Math.Abs(Mean.ReadyTime - o.ReadyTime) + Math.Abs(Mean.DueTime - o.DueTime), 2)) / (Elements.Count + 1);
-      return newVariance - Variance;
-    }
-  }
+    public override double CalculateDistance(TemporalDistanceClusterElement e1, TemporalDistanceClusterElement e2) {
+      double distance = 0.0;
+      distance += Math.Abs(e1.ReadyTime - e2.ReadyTime);
+      distance += Math.Abs(e1.DueTime - e2.DueTime);
+
+      return distance;
+      //return euklid(e1, e2);
+    }
+
+    private double euklid(TemporalDistanceClusterElement e1, TemporalDistanceClusterElement e2) {
+      double distance = 0.0;
+      distance += Math.Pow(e1.ReadyTime - e2.ReadyTime + e1.DueTime - e2.DueTime, 2);
+
+      return Math.Sqrt(distance);
+    }
+  }
+
   #endregion Cluster
 
-
   #region ClusterElement
-  public interface IClusterElement {
-    double GetDistance(IClusterElement o);
-  }
-  public abstract class ClusterElement : IClusterElement {
+  public abstract class ClusterElement {
     public int Id { get; set; }
     public int ClusterId { get; set; }
 
-    private ClusterElement() { }
+    protected ClusterElement() {
+      ClusterId = -1;
+    }
 
     public ClusterElement(int id, int clusterId = -1) {
@@ -161 +236 @@
       ClusterId = clusterId;
     }
-
-    public abstract double GetDistance(IClusterElement o);
   }
   public class SpatialDistanceClusterElement : ClusterElement {
 
     public double[] Coordinates { get; set; }
+
+    public SpatialDistanceClusterElement() : base() {
+    }
 
     public SpatialDistanceClusterElement(int id, int clusterId = -1) : base(id, clusterId) {
@@ -179 +255 @@
     }
 
-    public override double GetDistance(IClusterElement o) {
-      var other = o as SpatialDistanceClusterElement;
-      if (other == null) {
-        throw new ArgumentException(string.Format("Distance calculation between {0} and {1} is not possible.",
-          typeof(SpatialDistanceClusterElement), o.GetType()));
-      }
-
-      double distance = 0.0;
-      for (int i = 0; i < other.Coordinates.Length; i++) {
-        distance += Math.Pow(Coordinates[i] - other.Coordinates[i], 2);
-      }
-
-      return Math.Sqrt(distance);
-    }
   }
 
@@ -199 +261 @@
     public double DueTime { get; set; }
 
+    public TemporalDistanceClusterElement() : base() {
+    }
+
     public TemporalDistanceClusterElement(int id, int clusterId = -1) : base(id, clusterId) {
     }
@@ -206 +271 @@
       DueTime = dueTime;
     }
-
-    public override double GetDistance(IClusterElement o) {
-      var other = o as TemporalDistanceClusterElement;
-      if (other == null) {
-        throw new ArgumentException(string.Format("Distance calculation between {0} and {1} is not possible.",
-          typeof(TemporalDistanceClusterElement), o.GetType()));
-      }
-
-      double distance = 0.0;
-      distance += Math.Abs(ReadyTime - other.ReadyTime);
-      distance += Math.Abs(DueTime - other.DueTime);
-
-      return distance;
-
-      //return GetDistanceEuklid(other);
-    }
-
-    public double GetDistanceEuklid(TemporalDistanceClusterElement other) {
-      double distance = 0.0;
-      distance += Math.Pow(ReadyTime - other.ReadyTime, 2);
-      distance += Math.Pow(DueTime - other.DueTime, 2);
-
-      return Math.Sqrt(distance);
-    }
-
   }
 

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs

@@ -48 +48 @@
     }
 
-    public static List<SpatialDistanceClusterElement> CreateClusterObjects(IVRPProblemInstance instance) {
+    public static List<SpatialDistanceClusterElement> CreateClusterElements(IVRPProblemInstance instance) {
       IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
 
@@ -59 +59 @@
 
       // wrap stops in SpatialDistanceClusterElement
-      List<SpatialDistanceClusterElement> clusterObjects = new List<SpatialDistanceClusterElement>();
+      List<SpatialDistanceClusterElement> clusterElements = new List<SpatialDistanceClusterElement>();
       foreach (int customer in customers) {
-        clusterObjects.Add(new SpatialDistanceClusterElement(customer, instance.GetCoordinates(customer)));
+        clusterElements.Add(new SpatialDistanceClusterElement(customer, instance.GetCoordinates(customer)));
       }
-      return clusterObjects;
+      return clusterElements;
     }
 
@@ -69 +69 @@
       PotvinEncoding result = new PotvinEncoding(instance);
 
-      List<SpatialDistanceClusterElement> clusterObjects = CreateClusterObjects(instance);
+      // (1) wrap stops in cluster elements
+      List<SpatialDistanceClusterElement> clusterElements = CreateClusterElements(instance);
 
+      // (2) create a random number k of clusters
       int k = random.Next(minK, maxK);
-      List<SpatialDistanceCluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
-
-      // (3) build tours
-      // (a) shuffle
-      // (b) greedy
+      List<SpatialDistanceCluster> clusters = ClusterAlgorithm<SpatialDistanceCluster, SpatialDistanceClusterElement>
+        .KMeans(random, clusterElements, k, clusterChangeThreshold, true);
+      
+      // (3) build tours with a (a) shuffling (b) greedy tour creation routine
       foreach (var c in clusters) {
         Tour newTour = new Tour();
@@ -97 +98 @@
 
       return result;
-    }
-
-    private static List<SpatialDistanceCluster> KMeans(IVRPProblemInstance instance, IRandom random, List<SpatialDistanceClusterElement> objects, int k, double changeTreshold) {
-
-      List<SpatialDistanceCluster> clusters = new List<SpatialDistanceCluster>();
-      HashSet<int> initMeans = new HashSet<int>();
-      int nextMean = -1;
-
-      // (1) initialize each cluster with a random first object (i.e. mean)
-      for (int i = 0; i < k && i < objects.Count; i++) {
-        SpatialDistanceCluster cluster = new SpatialDistanceCluster(instance, i);
-
-        do {
-          nextMean = random.Next(0, objects.Count);
-        } while (initMeans.Contains(nextMean));
-        initMeans.Add(nextMean);
-        cluster.SetMean(objects[nextMean]);
-        clusters.Add(cluster);
-      }
-
-      // (2) repeat clustering until change rate is below threshold
-      int changes = 0;
-      double changeRate = 1.0;
-
-      do {
-        changes = KMeansRun(clusters, objects);
-        changeRate = changes / objects.Count;
-
-      } while (changeRate > changeTreshold);
-
-      // remove empty clusters
-      clusters.RemoveAll(c => c.Elements.Count.Equals(0));
-
-      return clusters;
-    }
-
-    private static int KMeansRun(List<SpatialDistanceCluster> clusters, List<SpatialDistanceClusterElement> objects) {
-      int changes = 0;
-
-      foreach (var c in clusters) {
-        c.Elements.Clear();
-      }
-
-      foreach (var o in objects) {
-        int bestClusterIdx = 0;
-        double minImpact = clusters[0].CalculateImpact(o);
-        for (int i = 1; i < clusters.Count; i++) {
-          double impact = clusters[i].CalculateImpact(o);
-          if (impact < minImpact) {
-            minImpact = impact;
-            bestClusterIdx = i;
-          }
-        }
-        if (clusters[bestClusterIdx].AddObject(o))
-          changes++;
-      }
-
-      foreach (var c in clusters) {
-        c.CalculateMean();
-        c.CalculateVariance();
-      }
-
-      return changes;
     }
 

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/TemporalDistanceClusterCreator.cs

@@ -49 +49 @@
     }
 
-    public static List<TemporalDistanceClusterElement> CreateClusterObjects(ITimeWindowedProblemInstance instance) {
+    public static List<TemporalDistanceClusterElement> CreateClusterElements(ITimeWindowedProblemInstance instance) {
       IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
 
@@ -70 +70 @@
       PotvinEncoding result = new PotvinEncoding(instance);
 
-      List<TemporalDistanceClusterElement> clusterObjects = CreateClusterObjects(instance);
+      // (1) wrap stops in cluster elements
+      List<TemporalDistanceClusterElement> clusterElements = CreateClusterElements(instance);
 
+      // (2) create a random number k of clusters
       int k = random.Next(minK, maxK);
-      List<TemporalDistanceCluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
+      List<TemporalDistanceCluster> clusters = ClusterAlgorithm<TemporalDistanceCluster, TemporalDistanceClusterElement>
+        .KMeans(random, clusterElements, k, clusterChangeThreshold, false);
 
-      // (3) build tours
-      // (a) shuffle
-      // (b) greedy
+      // (3) build tours with a (a) shuffling (b) greedy tour creation routine
       foreach (var c in clusters) {
         Tour newTour = new Tour();
@@ -93 +94 @@
             newTour.Stops.Add(o.Id);
           }
-          GreedyTourCreation(instance, result, newTour, false);
+          GreedyTourCreation(instance, result, newTour, true); // "true" means include costs
         }
       }
 
       return result;
-    }
-
-    private static List<TemporalDistanceCluster> KMeans(ITimeWindowedProblemInstance instance, IRandom random, List<TemporalDistanceClusterElement> objects, int k, double changeTreshold) {
-
-      List<TemporalDistanceCluster> clusters = new List<TemporalDistanceCluster>();
-      HashSet<int> initMeans = new HashSet<int>();
-      int nextMean = -1;
-
-      // (1) initialize each cluster with a random first object (i.e. mean)
-      for (int i = 0; i < k && i < objects.Count; i++) {
-        TemporalDistanceCluster cluster = new TemporalDistanceCluster(instance, i);
-
-        do {
-          nextMean = random.Next(0, objects.Count);
-        } while (initMeans.Contains(nextMean));
-        initMeans.Add(nextMean);
-        cluster.SetMean(objects[nextMean]);
-        clusters.Add(cluster);
-      }
-
-      // (2) repeat clustering until change rate is below threshold
-      int changes = 0;
-      double changeRate = 1.0;
-
-      do {
-        changes = KMeansRun(clusters, objects);
-        changeRate = changes / objects.Count;
-
-      } while (changeRate > changeTreshold);
-
-      // remove empty clusters
-      clusters.RemoveAll(c => c.Elements.Count.Equals(0));
-
-      return clusters;
-    }
-
-    private static int KMeansRun(List<TemporalDistanceCluster> clusters, List<TemporalDistanceClusterElement> objects) {
-      int changes = 0;
-
-      foreach (var c in clusters) {
-        c.Elements.Clear();
-      }
-
-      foreach (var o in objects) {
-        int bestClusterIdx = 0;
-        double minImpact = clusters[0].CalculateImpact(o);
-        for (int i = 1; i < clusters.Count; i++) {
-          double impact = clusters[i].CalculateImpact(o);
-          if ((minImpact > 0 && impact < minImpact) || (minImpact < 0 && impact > minImpact)) { // V1: min positive impact
-          //if(impact > minImpact) { // V2: max impact
-            minImpact = impact;
-            bestClusterIdx = i;
-          }
-        }
-        if (clusters[bestClusterIdx].AddObject(o))
-          changes++;
-      }
-
-      foreach (var c in clusters) {
-        c.CalculateMean();
-        c.CalculateVariance();
-      }
-
-      return changes;
     }