Changeset 14431


Ignore:
Timestamp:
11/30/16 14:49:22 (3 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:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/Cluster.cs

    r14430 r14431  
    11using System;
     2using System.Collections;
    23using System.Collections.Generic;
    3 using System.Linq;
    4 using System.Security.Cryptography.X509Certificates;
    5 using System.Text;
    6 using System.Threading.Tasks;
    74using HeuristicLab.Core;
    85using HeuristicLab.Problems.VehicleRouting.Interfaces;
    9 using HeuristicLab.Problems.VehicleRouting.Variants;
    106
    117namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    128
    13 
    149  public class ClusterAlgorithm<C,CO> where C : Cluster<CO> where CO : ClusterElement {
    1510
    16     //public static List<C> KMeans(IVRPProblemInstance instance, IRandom random, List<CO> clusterObjects, int k, double changeThreshold) {
    17     //  HashSet<int> initMeans = new HashSet<int>();
    18     //  int nextMean = -1;
    19 
    20     //  for (int i = 0; i < k && i < clusterObjects.Count; i++) {
    21     //    //C cluster = new C()
    22     //  }
    23 
    24 
    25 
    26 
    27     //}
    28 
    29     //private static int KMeansRun(List<C> clusters, List<CO> clusterObjects) {
    30      
    31     //}
    32 
     11    public static List<C> KMeans(IRandom random, List<CO> clusterElements, int k, double changeThreshold, bool minimizeImpact) {
     12      HashSet<int> initMeans = new HashSet<int>();
     13      int nextMean = -1;
     14
     15      List<C> clusters = CreateCList();
     16
     17      // (1) initialize each cluster with a random element as mean
     18      for (int i = 0; i < k && i < clusterElements.Count; i++) {
     19        C cluster = (C)Activator.CreateInstance(typeof(C));
     20        cluster.Id = i;
     21
     22        do {
     23          nextMean = random.Next(0, clusterElements.Count);
     24        } while (initMeans.Contains(nextMean));
     25        initMeans.Add(nextMean);
     26        cluster.SetMean(clusterElements[nextMean]);
     27        clusters.Add(cluster);
     28      }
     29
     30      // (2) repeat clustering until change rate is below threshold
     31      double changeRate = 0.0;
     32
     33      do {
     34        int changes = KMeansRun(clusters, clusterElements, minimizeImpact);
     35        changeRate = (double)changes / clusterElements.Count;
     36      } while (changeRate > changeThreshold);
     37
     38
     39      // remove empty clusters
     40      clusters.RemoveAll(c => c.Elements.Count.Equals(0));
     41
     42      return clusters;
     43    }
     44
     45    private static int KMeansRun(List<C> clusters, List<CO> clusterElements, bool minimizeImpact) {
     46      int changes = 0;
     47
     48      // clear clusters from previous assigned elements
     49      foreach (var c in clusters) {
     50        c.Elements.Clear();
     51      }
     52
     53      // assign elements to currently most suitable clusters
     54      foreach (var e in clusterElements) {
     55        int optClusterIdx = 0;
     56        double optImpact = clusters[optClusterIdx].CalculateImpact(e);
     57        for (int i = 1; i < clusters.Count; i++) {
     58          double impact = clusters[i].CalculateImpact(e);
     59          if (
     60            // optimal impact: max variance decrease (biggest negative or smallest positive value)
     61            (minimizeImpact && impact < optImpact) ||
     62            // optimal impact: min variance increase, if no increase possible: min decrease (smallest negative or positive value)
     63            //(!minimizeImpact && ((optImpact > 0 && impact < optImpact) || (optImpact < 0 && impact > optImpact)))) {
     64            (!minimizeImpact && impact > optImpact)
     65            ) {
     66
     67            optImpact = impact;
     68            optClusterIdx = i;
     69          }
     70        }
     71        if (clusters[optClusterIdx].AddObject(e)) {
     72          changes++;
     73        }
     74      }
     75
     76      // update mean and variance
     77      foreach (var c in clusters) {
     78        c.CalculateMean();
     79        c.CalculateVariance();
     80      }
     81
     82      return changes;
     83    }
     84
     85    private static List<C> CreateCList() {
     86      var listType = typeof(List<>);
     87      var constructedListType = listType.MakeGenericType(typeof(C));
     88      return (List<C>)Activator.CreateInstance(constructedListType);
     89    }
    3390  }
    3491
    3592  #region Cluster
    36   public interface ICluster<T> where T : IClusterElement {
    37     double CalculateImpact(T o);
    38     void CalculateMean();
     93  public interface ICluster<T> where T : ClusterElement {
    3994    void SetMean(T o);
    4095    bool AddObject(T o);
     96    void CalculateMean();
     97    void CalculateVariance();
     98    double CalculateImpact(T e);
     99    double CalculateDistance(T e1, T e2);
     100
    41101  }
    42102  public abstract class Cluster<T> : ICluster<T> where T : ClusterElement {
    43103    public int Id;
    44     protected readonly IVRPProblemInstance instance;
     104
    45105    public List<T> Elements { get; private set; }
    46106
     
    49109    public double Variance { get; set; }
    50110
    51     public Cluster(IVRPProblemInstance instance, int id) {
    52       this.instance = instance;
     111    protected Cluster() {
     112      Elements = new List<T>();
     113    }
     114
     115    protected Cluster(int id) {
    53116      Id = id;
    54117      Elements = new List<T>();
    55118
    56119    }
    57     public bool AddObject(T o) {
    58       Elements.Add(o);
    59 
    60       bool clusterChanged = o.ClusterId != Id;
    61       o.ClusterId = Id;
     120
     121    public bool AddObject(T e) {
     122      Elements.Add(e);
     123
     124      bool clusterChanged = e.ClusterId != Id;
     125      e.ClusterId = Id;
    62126      return clusterChanged;
    63127    }
    64128
    65     public void SetMean(T o) {
    66       Mean = o;
     129    public void SetMean(T e) {
     130      Mean = e;
    67131      Mean.ClusterId = Id;
    68132    }
     
    70134    public abstract void CalculateMean();
    71135
    72     public abstract void CalculateVariance();
    73 
    74     public abstract double CalculateImpact(T o);
    75 
    76   }
    77   public class SpatialDistanceCluster : Cluster<SpatialDistanceClusterElement> {
    78     public SpatialDistanceCluster(IVRPProblemInstance instance, int id) : base(instance, id) {
    79     }
    80 
    81     public override void CalculateMean() {
    82       int dimensions = instance.Coordinates.Columns;
    83       SpatialDistanceClusterElement mean = new SpatialDistanceClusterElement(-1, dimensions, Id);
    84       foreach (SpatialDistanceClusterElement o in Elements) {
    85         double[] coordinates = instance.GetCoordinates(o.Id);
    86         for (int i = 0; i < coordinates.Length; i++) {
    87           mean.Coordinates[i] += (coordinates[i] / Elements.Count);
    88         }
    89       }
    90       Mean = mean;
    91     }
    92 
    93     public override void CalculateVariance() {
    94       if(Mean == null)
    95         CalculateMean();
    96 
    97       Variance = 0.0;
    98       foreach (SpatialDistanceClusterElement o in Elements) {
    99         Variance += Math.Pow(Mean.GetDistance(o), 2);
    100       }
    101       Variance /= Elements.Count;
    102     }
    103 
    104     public override double CalculateImpact(SpatialDistanceClusterElement o) {
     136    public abstract double CalculateDistance(T e1, T e2);
     137
     138    public virtual void CalculateVariance() {
    105139      if (Mean == null)
    106140        CalculateMean();
    107141
    108       double newVariance = (Variance*Elements.Count + Math.Pow(Mean.GetDistance(o), 2))/(Elements.Count + 1);
     142      Variance = 0.0;
     143      foreach (T e in Elements) {
     144        Variance += Math.Pow(CalculateDistance(Mean, e), 2);
     145      }
     146      Variance /= Elements.Count;
     147    }
     148
     149    public virtual double CalculateImpact(T e) {
     150      if (Mean == null)
     151        CalculateMean();
     152
     153      double newVariance = (Variance * Elements.Count + Math.Pow(CalculateDistance(Mean, e), 2)) / (Elements.Count + 1);
    109154      return newVariance - Variance;
    110155    }
     156
     157  }
     158  public class SpatialDistanceCluster : Cluster<SpatialDistanceClusterElement> {
     159    public SpatialDistanceCluster() : base() {
     160    }
     161
     162    public SpatialDistanceCluster(int id) : base(id) {
     163    }
     164
     165    public override void CalculateMean() {
     166      int dimensions = (Mean != null) ? Mean.Coordinates.Length : (Elements.Count > 0) ? Elements[0].Coordinates.Length : 0;
     167      SpatialDistanceClusterElement mean = new SpatialDistanceClusterElement(-1, dimensions, Id);
     168      foreach (SpatialDistanceClusterElement e in Elements) {
     169        for (int i = 0; i < Mean.Coordinates.Length; i++) {
     170          mean.Coordinates[i] += (e.Coordinates[i] / Elements.Count);
     171        }
     172      }
     173      Mean = mean;
     174    }
     175
     176    public override double CalculateDistance(SpatialDistanceClusterElement e1, SpatialDistanceClusterElement e2) {
     177      if (!e1.Coordinates.Length.Equals(e2.Coordinates.Length)) {
     178        throw new ArgumentException("Distance could not be calculated since number of dimensions is unequal.");
     179      }
     180
     181      double distance = 0.0;
     182      for (int i = 0; i < e1.Coordinates.Length; i++) {
     183        distance += Math.Pow(e1.Coordinates[i] - e2.Coordinates[i], 2);
     184      }
     185
     186      return Math.Sqrt(distance);
     187    }
    111188  }
    112189
    113190  public class TemporalDistanceCluster : Cluster<TemporalDistanceClusterElement> {
    114     public TemporalDistanceCluster(ITimeWindowedProblemInstance instance, int id) : base(instance, id) {
    115     }
    116 
     191    public TemporalDistanceCluster() : base() {
     192    }
     193
     194    public TemporalDistanceCluster(int id) : base(id) {
     195    }
    117196
    118197    public override void CalculateMean() {
     
    125204    }
    126205
    127     public override void CalculateVariance() {
    128       if (Mean == null)
    129         CalculateMean();
    130 
    131       Variance = 0.0;
    132       foreach (TemporalDistanceClusterElement e in Elements) {
    133         Variance += Math.Pow(Math.Abs(Mean.ReadyTime - e.ReadyTime) + Math.Abs(Mean.DueTime - e.DueTime), 2);
    134       }
    135       Variance /= Elements.Count;
    136     }
    137 
    138     public override double CalculateImpact(TemporalDistanceClusterElement o) {
    139       if(Mean == null)
    140         CalculateMean();
    141 
    142       double newVariance = (Variance * Elements.Count + Math.Pow(Math.Abs(Mean.ReadyTime - o.ReadyTime) + Math.Abs(Mean.DueTime - o.DueTime), 2)) / (Elements.Count + 1);
    143       return newVariance - Variance;
    144     }
    145   }
     206    public override double CalculateDistance(TemporalDistanceClusterElement e1, TemporalDistanceClusterElement e2) {
     207      double distance = 0.0;
     208      distance += Math.Abs(e1.ReadyTime - e2.ReadyTime);
     209      distance += Math.Abs(e1.DueTime - e2.DueTime);
     210
     211      return distance;
     212      //return euklid(e1, e2);
     213    }
     214
     215    private double euklid(TemporalDistanceClusterElement e1, TemporalDistanceClusterElement e2) {
     216      double distance = 0.0;
     217      distance += Math.Pow(e1.ReadyTime - e2.ReadyTime + e1.DueTime - e2.DueTime, 2);
     218
     219      return Math.Sqrt(distance);
     220    }
     221  }
     222
    146223  #endregion Cluster
    147224
    148 
    149225  #region ClusterElement
    150   public interface IClusterElement {
    151     double GetDistance(IClusterElement o);
    152   }
    153   public abstract class ClusterElement : IClusterElement {
     226  public abstract class ClusterElement {
    154227    public int Id { get; set; }
    155228    public int ClusterId { get; set; }
    156229
    157     private ClusterElement() { }
     230    protected ClusterElement() {
     231      ClusterId = -1;
     232    }
    158233
    159234    public ClusterElement(int id, int clusterId = -1) {
     
    161236      ClusterId = clusterId;
    162237    }
    163 
    164     public abstract double GetDistance(IClusterElement o);
    165238  }
    166239  public class SpatialDistanceClusterElement : ClusterElement {
    167240
    168241    public double[] Coordinates { get; set; }
     242
     243    public SpatialDistanceClusterElement() : base() {
     244    }
    169245
    170246    public SpatialDistanceClusterElement(int id, int clusterId = -1) : base(id, clusterId) {
     
    179255    }
    180256
    181     public override double GetDistance(IClusterElement o) {
    182       var other = o as SpatialDistanceClusterElement;
    183       if (other == null) {
    184         throw new ArgumentException(string.Format("Distance calculation between {0} and {1} is not possible.",
    185           typeof(SpatialDistanceClusterElement), o.GetType()));
    186       }
    187 
    188       double distance = 0.0;
    189       for (int i = 0; i < other.Coordinates.Length; i++) {
    190         distance += Math.Pow(Coordinates[i] - other.Coordinates[i], 2);
    191       }
    192 
    193       return Math.Sqrt(distance);
    194     }
    195257  }
    196258
     
    199261    public double DueTime { get; set; }
    200262
     263    public TemporalDistanceClusterElement() : base() {
     264    }
     265
    201266    public TemporalDistanceClusterElement(int id, int clusterId = -1) : base(id, clusterId) {
    202267    }
     
    206271      DueTime = dueTime;
    207272    }
    208 
    209     public override double GetDistance(IClusterElement o) {
    210       var other = o as TemporalDistanceClusterElement;
    211       if (other == null) {
    212         throw new ArgumentException(string.Format("Distance calculation between {0} and {1} is not possible.",
    213           typeof(TemporalDistanceClusterElement), o.GetType()));
    214       }
    215 
    216       double distance = 0.0;
    217       distance += Math.Abs(ReadyTime - other.ReadyTime);
    218       distance += Math.Abs(DueTime - other.DueTime);
    219 
    220       return distance;
    221 
    222       //return GetDistanceEuklid(other);
    223     }
    224 
    225     public double GetDistanceEuklid(TemporalDistanceClusterElement other) {
    226       double distance = 0.0;
    227       distance += Math.Pow(ReadyTime - other.ReadyTime, 2);
    228       distance += Math.Pow(DueTime - other.DueTime, 2);
    229 
    230       return Math.Sqrt(distance);
    231     }
    232 
    233273  }
    234274
  • branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs

    r14430 r14431  
    4848    }
    4949
    50     public static List<SpatialDistanceClusterElement> CreateClusterObjects(IVRPProblemInstance instance) {
     50    public static List<SpatialDistanceClusterElement> CreateClusterElements(IVRPProblemInstance instance) {
    5151      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
    5252
     
    5959
    6060      // wrap stops in SpatialDistanceClusterElement
    61       List<SpatialDistanceClusterElement> clusterObjects = new List<SpatialDistanceClusterElement>();
     61      List<SpatialDistanceClusterElement> clusterElements = new List<SpatialDistanceClusterElement>();
    6262      foreach (int customer in customers) {
    63         clusterObjects.Add(new SpatialDistanceClusterElement(customer, instance.GetCoordinates(customer)));
     63        clusterElements.Add(new SpatialDistanceClusterElement(customer, instance.GetCoordinates(customer)));
    6464      }
    65       return clusterObjects;
     65      return clusterElements;
    6666    }
    6767
     
    6969      PotvinEncoding result = new PotvinEncoding(instance);
    7070
    71       List<SpatialDistanceClusterElement> clusterObjects = CreateClusterObjects(instance);
     71      // (1) wrap stops in cluster elements
     72      List<SpatialDistanceClusterElement> clusterElements = CreateClusterElements(instance);
    7273
     74      // (2) create a random number k of clusters
    7375      int k = random.Next(minK, maxK);
    74       List<SpatialDistanceCluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
    75 
    76       // (3) build tours
    77       // (a) shuffle
    78       // (b) greedy
     76      List<SpatialDistanceCluster> clusters = ClusterAlgorithm<SpatialDistanceCluster, SpatialDistanceClusterElement>
     77        .KMeans(random, clusterElements, k, clusterChangeThreshold, true);
     78     
     79      // (3) build tours with a (a) shuffling (b) greedy tour creation routine
    7980      foreach (var c in clusters) {
    8081        Tour newTour = new Tour();
     
    9798
    9899      return result;
    99     }
    100 
    101     private static List<SpatialDistanceCluster> KMeans(IVRPProblemInstance instance, IRandom random, List<SpatialDistanceClusterElement> objects, int k, double changeTreshold) {
    102 
    103       List<SpatialDistanceCluster> clusters = new List<SpatialDistanceCluster>();
    104       HashSet<int> initMeans = new HashSet<int>();
    105       int nextMean = -1;
    106 
    107       // (1) initialize each cluster with a random first object (i.e. mean)
    108       for (int i = 0; i < k && i < objects.Count; i++) {
    109         SpatialDistanceCluster cluster = new SpatialDistanceCluster(instance, i);
    110 
    111         do {
    112           nextMean = random.Next(0, objects.Count);
    113         } while (initMeans.Contains(nextMean));
    114         initMeans.Add(nextMean);
    115         cluster.SetMean(objects[nextMean]);
    116         clusters.Add(cluster);
    117       }
    118 
    119       // (2) repeat clustering until change rate is below threshold
    120       int changes = 0;
    121       double changeRate = 1.0;
    122 
    123       do {
    124         changes = KMeansRun(clusters, objects);
    125         changeRate = changes / objects.Count;
    126 
    127       } while (changeRate > changeTreshold);
    128 
    129       // remove empty clusters
    130       clusters.RemoveAll(c => c.Elements.Count.Equals(0));
    131 
    132       return clusters;
    133     }
    134 
    135     private static int KMeansRun(List<SpatialDistanceCluster> clusters, List<SpatialDistanceClusterElement> objects) {
    136       int changes = 0;
    137 
    138       foreach (var c in clusters) {
    139         c.Elements.Clear();
    140       }
    141 
    142       foreach (var o in objects) {
    143         int bestClusterIdx = 0;
    144         double minImpact = clusters[0].CalculateImpact(o);
    145         for (int i = 1; i < clusters.Count; i++) {
    146           double impact = clusters[i].CalculateImpact(o);
    147           if (impact < minImpact) {
    148             minImpact = impact;
    149             bestClusterIdx = i;
    150           }
    151         }
    152         if (clusters[bestClusterIdx].AddObject(o))
    153           changes++;
    154       }
    155 
    156       foreach (var c in clusters) {
    157         c.CalculateMean();
    158         c.CalculateVariance();
    159       }
    160 
    161       return changes;
    162100    }
    163101
  • branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/TemporalDistanceClusterCreator.cs

    r14430 r14431  
    4949    }
    5050
    51     public static List<TemporalDistanceClusterElement> CreateClusterObjects(ITimeWindowedProblemInstance instance) {
     51    public static List<TemporalDistanceClusterElement> CreateClusterElements(ITimeWindowedProblemInstance instance) {
    5252      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
    5353
     
    7070      PotvinEncoding result = new PotvinEncoding(instance);
    7171
    72       List<TemporalDistanceClusterElement> clusterObjects = CreateClusterObjects(instance);
     72      // (1) wrap stops in cluster elements
     73      List<TemporalDistanceClusterElement> clusterElements = CreateClusterElements(instance);
    7374
     75      // (2) create a random number k of clusters
    7476      int k = random.Next(minK, maxK);
    75       List<TemporalDistanceCluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
     77      List<TemporalDistanceCluster> clusters = ClusterAlgorithm<TemporalDistanceCluster, TemporalDistanceClusterElement>
     78        .KMeans(random, clusterElements, k, clusterChangeThreshold, false);
    7679
    77       // (3) build tours
    78       // (a) shuffle
    79       // (b) greedy
     80      // (3) build tours with a (a) shuffling (b) greedy tour creation routine
    8081      foreach (var c in clusters) {
    8182        Tour newTour = new Tour();
     
    9394            newTour.Stops.Add(o.Id);
    9495          }
    95           GreedyTourCreation(instance, result, newTour, false);
     96          GreedyTourCreation(instance, result, newTour, true); // "true" means include costs
    9697        }
    9798      }
    9899
    99100      return result;
    100     }
    101 
    102     private static List<TemporalDistanceCluster> KMeans(ITimeWindowedProblemInstance instance, IRandom random, List<TemporalDistanceClusterElement> objects, int k, double changeTreshold) {
    103 
    104       List<TemporalDistanceCluster> clusters = new List<TemporalDistanceCluster>();
    105       HashSet<int> initMeans = new HashSet<int>();
    106       int nextMean = -1;
    107 
    108       // (1) initialize each cluster with a random first object (i.e. mean)
    109       for (int i = 0; i < k && i < objects.Count; i++) {
    110         TemporalDistanceCluster cluster = new TemporalDistanceCluster(instance, i);
    111 
    112         do {
    113           nextMean = random.Next(0, objects.Count);
    114         } while (initMeans.Contains(nextMean));
    115         initMeans.Add(nextMean);
    116         cluster.SetMean(objects[nextMean]);
    117         clusters.Add(cluster);
    118       }
    119 
    120       // (2) repeat clustering until change rate is below threshold
    121       int changes = 0;
    122       double changeRate = 1.0;
    123 
    124       do {
    125         changes = KMeansRun(clusters, objects);
    126         changeRate = changes / objects.Count;
    127 
    128       } while (changeRate > changeTreshold);
    129 
    130       // remove empty clusters
    131       clusters.RemoveAll(c => c.Elements.Count.Equals(0));
    132 
    133       return clusters;
    134     }
    135 
    136     private static int KMeansRun(List<TemporalDistanceCluster> clusters, List<TemporalDistanceClusterElement> objects) {
    137       int changes = 0;
    138 
    139       foreach (var c in clusters) {
    140         c.Elements.Clear();
    141       }
    142 
    143       foreach (var o in objects) {
    144         int bestClusterIdx = 0;
    145         double minImpact = clusters[0].CalculateImpact(o);
    146         for (int i = 1; i < clusters.Count; i++) {
    147           double impact = clusters[i].CalculateImpact(o);
    148           if ((minImpact > 0 && impact < minImpact) || (minImpact < 0 && impact > minImpact)) { // V1: min positive impact
    149           //if(impact > minImpact) { // V2: max impact
    150             minImpact = impact;
    151             bestClusterIdx = i;
    152           }
    153         }
    154         if (clusters[bestClusterIdx].AddObject(o))
    155           changes++;
    156       }
    157 
    158       foreach (var c in clusters) {
    159         c.CalculateMean();
    160         c.CalculateVariance();
    161       }
    162 
    163       return changes;
    164101    }
    165102
Note: See TracChangeset for help on using the changeset viewer.