Changeset 14559

Timestamp:

01/12/17 16:42:50 (8 years ago)

Author:

pfleck

Message:

#2707 Simplified k-means clustering for ClusterCreators.

Location:

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

Files:

• Cluster.cs (modified) (2 diffs)
• GeographicDistanceClusterCreator.cs (modified) (4 diffs)
• TemporalDistanceClusterCreator.cs (modified) (4 diffs)

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

@@ -1 @@
-using System;
-using System.Collections;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
 using System.Collections.Generic;
 using HeuristicLab.Core;
-using HeuristicLab.Problems.VehicleRouting.Interfaces;
+using HeuristicLab.Encodings.PermutationEncoding;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
 
-  public class ClusterAlgorithm<TCluster,TClusterElement> 
-    where TCluster : Cluster<TClusterElement>, new() 
-    where TClusterElement : ClusterElement, new() {
+  public class KMeansAlgorithm<TData> where TData : class {
 
-    public static List<TCluster> KMeans(IRandom random, List<TClusterElement> clusterElements, 
-      int k, double changeThreshold) {
-      HashSet<int> initMeans = new HashSet<int>();
-      int nextMean = -1;
-      List<TCluster> clusters = CreateCList();
+    private class ClusterInfo {
+      public TData Mean;
+      public double Variance;
+      public int Size;
+    }
+
+    private readonly Func<List<TData>, TData> meanCalculator;
+    private readonly Func<TData, TData, double> distanceCalculator;
+
+    public KMeansAlgorithm(Func<List<TData>, TData> meanCalculator, Func<TData, TData, double> distanceCalculator) {
+      this.meanCalculator = meanCalculator;
+      this.distanceCalculator = distanceCalculator;
+    }
+
+    public List<List<int>> Run(List<TData> data, int k, double changeThreshold, IRandom random) {
+      int numClusters = Math.Min(k, data.Count);
+
+      var assignments = new int[data.Count];
+      for (int i = 0; i < assignments.Length; i++)
+        assignments[i] = -1; // unassigned
 
       // (1) initialize each cluster with a random element as mean
-      for (int i = 0; i < k && i < clusterElements.Count; i++) {
-        TCluster cluster = new TCluster();
-        cluster.Id = i;
-
-        do {
-          nextMean = random.Next(0, clusterElements.Count);
-        } while (initMeans.Contains(nextMean));
-        initMeans.Add(nextMean);
-        cluster.SetMean(clusterElements[nextMean]);
-        clusters.Add(cluster);
+      var clusters = new ClusterInfo[numClusters];
+      var initIndices = new Permutation(PermutationTypes.Absolute, data.Count, random);
+      for (int c = 0; c < numClusters; c++) {
+        assignments[initIndices[c]] = c;
+        clusters[c] = new ClusterInfo {
+          Mean = data[initIndices[c]],
+          Size = 1
+        };
       }
 
-      // (2) repeat clustering until change rate is below threshold
-      double changeRate = 0.0;
+      // (2) repeat clustering until change rate is below the threshold
+      double changeRate;
       do {
-        int changes = KMeansRun(clusters, clusterElements);
-        changeRate = (double)changes / clusterElements.Count;
+        int changes = Iterate(data, assignments, clusters);
+        changeRate = (double)changes / data.Count;
       } while (changeRate > changeThreshold);
 
-
-      // remove empty clusters
-      clusters.RemoveAll(c => c.Elements.Count.Equals(0));
-      return clusters;
+      // (3) return non-empty clusters
+      var clustersData = new List<List<int>>(numClusters);
+      for (int c = 0; c < numClusters; c++)
+        clustersData.Add(new List<int>());
+      for (int i = 0; i < assignments.Length; i++)
+        clustersData[assignments[i]].Add(i);
+      clustersData.RemoveAll(c => c.Count == 0);
+      return clustersData;
     }
 
-    private static int KMeansRun(List<TCluster> clusters, List<TClusterElement> clusterElements) {
+    private int Iterate(List<TData> data, int[] assignments, ClusterInfo[] clusters) {
       int changes = 0;
 
-      // clear clusters from previous assigned elements
-      foreach (var c in clusters) {
-        c.Elements.Clear();
+      var newAssignments = new int[data.Count];
+      assignments.CopyTo(newAssignments, 0);
+
+      // assign elements to currently most suited cluster
+      for (int i = 0; i < data.Count; i++) {
+        int bestCluster = 0;
+        double bestImpact = CalculateImpact(data[i], clusters[0]);
+        for (int c = 1; c < clusters.Length; c++) {
+          double impact = CalculateImpact(data[i], clusters[c]);
+          if (impact < bestImpact) {
+            bestImpact = impact;
+            bestCluster = c;
+          }
+        }
+        newAssignments[i] = bestCluster;
+        if (newAssignments[i] != assignments[i])
+          changes++;
       }
 
-      // 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 (impact < optImpact) { 
-            optImpact = impact;
-            optClusterIdx = i;
-          }
-        }
-        if (clusters[optClusterIdx].AddElement(e)) {
-          changes++;
-        }
+      // update clusters
+      var clustersData = new List<List<TData>>(clusters.Length);
+      for (int c = 0; c < clusters.Length; c++)
+        clustersData.Add(new List<TData>());
+      for (int i = 0; i < data.Count; i++) {
+        assignments[i] = newAssignments[i];
+        clustersData[assignments[i]].Add(data[i]);
       }
+      for (int c = 0; c < clusters.Length; c++) {
+        var clusterData = clustersData[c];
+        if (clusterData.Count == 0)
+          continue;
 
-      // update mean and variance
-      foreach (var c in clusters) {
-        c.CalculateMean();
-        c.CalculateVariance();
+        clusters[c].Mean = meanCalculator(clusterData);
+
+        clusters[c].Variance = 0;
+        foreach (var e in clusterData)
+          clusters[c].Variance += Math.Pow(distanceCalculator(e, clusters[c].Mean), 2);
+        clusters[c].Variance /= clusterData.Count;
+
+        clusters[c].Size = clusterData.Count;
       }
 
@@ -76 +126 @@
     }
 
-    private static List<TCluster> CreateCList() {
-      var listType = typeof(List<>);
-      var constructedListType = listType.MakeGenericType(typeof(TCluster));
-      return (List<TCluster>)Activator.CreateInstance(constructedListType);
+    private double CalculateImpact(TData datum, ClusterInfo cluster) {
+      double newVariance = (cluster.Variance * cluster.Size + Math.Pow(distanceCalculator(datum, cluster.Mean), 2)) / (cluster.Size + 1);
+      return newVariance - cluster.Variance;
     }
   }
-
-  #region Cluster
-  public interface ICluster<T> where T : ClusterElement {
-    void SetMean(T o);
-    bool AddElement(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, new() {
-    public int Id;
-    public List<T> Elements { get; private set; }
-    public T Mean { get; set; }
-    public double Variance { get; set; }
-    protected Cluster() {
-      Elements = new List<T>();
-    }
-    protected Cluster(int id) {
-      Id = id;
-      Elements = new List<T>();
-    }
-    public bool AddElement(T e) {
-      Elements.Add(e);
-
-      bool clusterChanged = e.ClusterId != Id;
-      e.ClusterId = Id;
-      return clusterChanged;
-    }
-    public void SetMean(T e) {
-      Mean = e;
-      Mean.ClusterId = Id;
-    }
-    public abstract void CalculateMean();
-    public abstract double CalculateDistance(T e1, T e2);
-    public virtual void CalculateVariance() {
-      if (Mean == null)
-        CalculateMean();
-
-      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() : base() {
-    }
-    public TemporalDistanceCluster(int id) : base(id) {
-    }
-    public override void CalculateMean() {
-      TemporalDistanceClusterElement mean = new TemporalDistanceClusterElement(-1, Id);
-      foreach (TemporalDistanceClusterElement e in Elements) {
-        mean.ReadyTime += e.ReadyTime/Elements.Count;
-        mean.DueTime += e.DueTime/Elements.Count;
-      }
-      Mean = mean;
-    }
-    public override double CalculateDistance(TemporalDistanceClusterElement e1, TemporalDistanceClusterElement e2) {
-      double distance = 0.0;
-
-      distance += Math.Pow(e1.ReadyTime - e2.ReadyTime, 2);
-      distance += Math.Pow(e1.DueTime - e2.DueTime, 2);
-
-      return Math.Sqrt(distance);
-    }
-  }
-  #endregion Cluster
-
-  #region ClusterElement
-  public abstract class ClusterElement {
-    public int Id { get; set; }
-    public int ClusterId { get; set; }
-    protected ClusterElement() {
-      ClusterId = -1;
-    }
-    public ClusterElement(int id, int clusterId = -1) {
-      Id = id;
-      ClusterId = clusterId;
-    }
-  }
-  public class SpatialDistanceClusterElement : ClusterElement {
-    public double[] Coordinates { get; set; }
-    public SpatialDistanceClusterElement() : base() {
-    }
-    public SpatialDistanceClusterElement(int id, int clusterId = -1) : base(id, clusterId) {
-    }
-    public SpatialDistanceClusterElement(int id, double[] coordinates, int clusterId = -1) : base(id, clusterId) {
-      Coordinates = coordinates;
-    }
-    public SpatialDistanceClusterElement(int id, int dimensions, int clusterId = -1) : base(id, clusterId) { 
-      Coordinates = new double[dimensions];
-    }
-  }
-  public class TemporalDistanceClusterElement : ClusterElement {
-    public double ReadyTime { get; set; }
-    public double DueTime { get; set; }
-    public TemporalDistanceClusterElement() : base() {
-    }
-    public TemporalDistanceClusterElement(int id, int clusterId = -1) : base(id, clusterId) {
-    }
-    public TemporalDistanceClusterElement(int id, double readyTime, double dueTime, int clusterId = -1) : base(id, clusterId) {
-      ReadyTime = readyTime;
-      DueTime = dueTime;
-    }
-  }
-
-  #endregion ClusterElement
 }

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

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -48 +49 @@
     }
 
-    public static List<SpatialDistanceClusterElement> CreateClusterElements(IVRPProblemInstance instance) {
-      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
-
-      // add all customers
-      List<int> customers = new List<int>();
-      for (int i = 1; i <= instance.Cities.Value; i++) {
-        if (pdp == null || pdp.GetDemand(i) >= 0)
-          customers.Add(i);
-      }
-
-      // wrap stops in SpatialDistanceClusterElement
-      List<SpatialDistanceClusterElement> clusterElements = new List<SpatialDistanceClusterElement>();
-      foreach (int customer in customers) {
-        clusterElements.Add(new SpatialDistanceClusterElement(customer, instance.GetCoordinates(customer)));
-      }
-      return clusterElements;
-    }
 
     public static PotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
       PotvinEncoding result = new PotvinEncoding(instance);
 
-      // (1) wrap stops in cluster elements
-      List<SpatialDistanceClusterElement> clusterElements = CreateClusterElements(instance);
+      // (1) init data
+      var coordinates = new List<double[]>(instance.Cities.Value);
+      var pdp = instance as IPickupAndDeliveryProblemInstance;
+      for (int i = 1; i <= instance.Cities.Value; i++) {
+        if (pdp == null || pdp.GetDemand(i) >= 0)
+          coordinates.Add(instance.GetCoordinates(i));
+      }
 
       // (2) create a random number k of clusters
       int k = random.Next(minK, maxK);
-      List<SpatialDistanceCluster> clusters = ClusterAlgorithm<SpatialDistanceCluster, SpatialDistanceClusterElement>
-        .KMeans(random, clusterElements, k, clusterChangeThreshold);
-      
+      var kMeans = new KMeansAlgorithm<double[]>(CalculateMeanHelper, CalculateDistanceHelper);
+      var clusters = kMeans.Run(coordinates, k, clusterChangeThreshold, random);
+
       // (3) build tours with a (a) shuffling (b) greedy tour creation routine
-      foreach (var c in clusters) {
+      foreach (var cluster in clusters) {
         Tour newTour = new Tour();
         result.Tours.Add(newTour);
@@ -84 +73 @@
         if (creationOption == 0) {
           // (a) shuffle
-          c.Elements.Shuffle(random);
-          foreach (var o in c.Elements) {
-            newTour.Stops.Add(o.Id);
+          cluster.ShuffleInPlace(random);
+          newTour.Stops.AddRange(cluster);
+          foreach (var customer in cluster) {
+            newTour.Stops.Add(customer + 1);
           }
         } else {
           // (b) greedy
-          foreach (var o in c.Elements) {
-            newTour.Stops.Add(o.Id);
+          foreach (var customer in cluster) {
+            newTour.Stops.Add(customer + 1);
           }
           GreedyTourCreation(instance, result, newTour, false);
@@ -98 +88 @@
 
       return result;
+    }
+
+    private static double[] CalculateMeanHelper(List<double[]> coordinates) {
+      var mean = new double[coordinates[0].Length];
+      foreach (double[] coord in coordinates) {
+        for (int i = 0; i < mean.Length; i++) {
+          mean[i] += coord[i] / coordinates.Count;
+        }
+      }
+      return mean;
+    }
+    private static double CalculateDistanceHelper(double[] coord1, double[] coord2) {
+      double distance = 0.0;
+      for (int i = 0; i < coord1.Length; i++) {
+        distance += Math.Pow(coord1[i] - coord2[i], 2);
+      }
+      return Math.Sqrt(distance);
     }
 

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

@@ -26 +26 @@
 using HeuristicLab.Core;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Problems.VehicleRouting.Interfaces;
 using HeuristicLab.Problems.VehicleRouting.Variants;
 using HeuristicLab.Random;
@@ -49 +48 @@
     }
 
-    public static List<TemporalDistanceClusterElement> CreateClusterElements(ITimeWindowedProblemInstance instance) {
-      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
-
-      // add all customers
-      List<int> customers = new List<int>();
-      for (int i = 1; i <= instance.Cities.Value; i++) {
-        if (pdp == null || pdp.GetDemand(i) >= 0)
-          customers.Add(i);
-      }
-
-      // wrap stops in TemporalDistanceClusterElement
-      List<TemporalDistanceClusterElement> clusterObjects = new List<TemporalDistanceClusterElement>();
-      foreach (int customer in customers) {
-        clusterObjects.Add(new TemporalDistanceClusterElement(customer, instance.ReadyTime[customer], instance.DueTime[customer]));
-      }
-      return clusterObjects;
-    }
-
     public static PotvinEncoding CreateSolution(ITimeWindowedProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
       PotvinEncoding result = new PotvinEncoding(instance);
 
-      // (1) wrap stops in cluster elements
-      List<TemporalDistanceClusterElement> clusterElements = CreateClusterElements(instance);
+      // (1) init data
+      var times = new List<Tuple<double, double>>(instance.Cities.Value);
+      var pdp = instance as IPickupAndDeliveryProblemInstance;
+      for (int i = 1; i <= instance.Cities.Value; i++) {
+        if (pdp == null || pdp.GetDemand(i) >= 0)
+          times.Add(Tuple.Create(instance.ReadyTime[i], instance.DueTime[i]));
+      }
 
       // (2) create a random number k of clusters
       int k = random.Next(minK, maxK);
-      List<TemporalDistanceCluster> clusters = ClusterAlgorithm<TemporalDistanceCluster, TemporalDistanceClusterElement>
-        .KMeans(random, clusterElements, k, clusterChangeThreshold);
+      var kMeans = new KMeansAlgorithm<Tuple<double, double>>(CalculateMeanHelper, CalculateDistanceHelper);
+      var clusters = kMeans.Run(times, k, clusterChangeThreshold, random);
+
 
       // (3) build tours with a (a) shuffling (b) greedy tour creation routine
-      foreach (var c in clusters) {
+      foreach (var cluster in clusters) {
         Tour newTour = new Tour();
         result.Tours.Add(newTour);
@@ -85 +72 @@
         if (creationOption == 0) {
           // (a) shuffle
-          c.Elements.Shuffle(random);
-          foreach (var o in c.Elements) {
-            newTour.Stops.Add(o.Id);
+          cluster.ShuffleInPlace(random);
+          newTour.Stops.AddRange(cluster);
+          foreach (var customer in cluster) {
+            newTour.Stops.Add(customer + 1);
           }
         } else {
           // (b) greedy
-          foreach (var o in c.Elements) {
-            newTour.Stops.Add(o.Id);
+          foreach (var customer in cluster) {
+            newTour.Stops.Add(customer + 1);
           }
           GreedyTourCreation(instance, result, newTour, true); // "true" means include costs
@@ -99 +87 @@
 
       return result;
+    }
+
+    private static Tuple<double, double> CalculateMeanHelper(List<Tuple<double, double>> times) {
+      double meanReady = 0, meanDue = 0;
+      foreach (var t in times) {
+        meanReady += t.Item1 / times.Count;
+        meanDue += t.Item2 / times.Count;
+      }
+      return Tuple.Create(meanReady, meanDue);
+    }
+    private static double CalculateDistanceHelper(Tuple<double, double> time1, Tuple<double, double> time2) {
+      double distance = 0.0;
+      distance +=   Math.Pow(time1.Item1 - time2.Item1, 2);
+      distance +=   Math.Pow(time1.Item2 - time2.Item2, 2);
+      return Math.Sqrt(distance);
     }