Changeset 14442


Ignore:
Timestamp:
12/02/16 14:03:55 (4 years ago)
Author:
jzenisek
Message:

#2707 fixed min variance bug in time window based k-means clustering

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

    r14431 r14442  
    99  public class ClusterAlgorithm<C,CO> where C : Cluster<CO> where CO : ClusterElement {
    1010
    11     public static List<C> KMeans(IRandom random, List<CO> clusterElements, int k, double changeThreshold, bool minimizeImpact) {
     11    public static List<C> KMeans(IRandom random, List<CO> clusterElements, int k, double changeThreshold) {
    1212      HashSet<int> initMeans = new HashSet<int>();
    1313      int nextMean = -1;
     
    3232
    3333      do {
    34         int changes = KMeansRun(clusters, clusterElements, minimizeImpact);
     34        int changes = KMeansRun(clusters, clusterElements);
    3535        changeRate = (double)changes / clusterElements.Count;
    3636      } while (changeRate > changeThreshold);
     
    4343    }
    4444
    45     private static int KMeansRun(List<C> clusters, List<CO> clusterElements, bool minimizeImpact) {
     45    private static int KMeansRun(List<C> clusters, List<CO> clusterElements) {
    4646      int changes = 0;
    4747
     
    5757        for (int i = 1; i < clusters.Count; i++) {
    5858          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 
     59          if (impact < optImpact) {
    6760            optImpact = impact;
    6861            optClusterIdx = i;
     
    206199    public override double CalculateDistance(TemporalDistanceClusterElement e1, TemporalDistanceClusterElement e2) {
    207200      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);
     201
     202      distance += Math.Pow(e1.ReadyTime - e2.ReadyTime, 2);
     203      distance += Math.Pow(e1.DueTime - e2.DueTime, 2);
    218204
    219205      return Math.Sqrt(distance);
  • branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs

    r14431 r14442  
    7575      int k = random.Next(minK, maxK);
    7676      List<SpatialDistanceCluster> clusters = ClusterAlgorithm<SpatialDistanceCluster, SpatialDistanceClusterElement>
    77         .KMeans(random, clusterElements, k, clusterChangeThreshold, true);
     77        .KMeans(random, clusterElements, k, clusterChangeThreshold);
    7878     
    7979      // (3) build tours with a (a) shuffling (b) greedy tour creation routine
  • branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/TemporalDistanceClusterCreator.cs

    r14431 r14442  
    7676      int k = random.Next(minK, maxK);
    7777      List<TemporalDistanceCluster> clusters = ClusterAlgorithm<TemporalDistanceCluster, TemporalDistanceClusterElement>
    78         .KMeans(random, clusterElements, k, clusterChangeThreshold, false);
     78        .KMeans(random, clusterElements, k, clusterChangeThreshold);
    7979
    8080      // (3) build tours with a (a) shuffling (b) greedy tour creation routine
Note: See TracChangeset for help on using the changeset viewer.