Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14424


Ignore:
Timestamp:
11/28/16 16:41:36 (8 years ago)
Author:
jzenisek
Message:

#2707 adapted clustering leading to more generic usage

Location:
branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4
Files:
2 added
2 edited

Legend:

Unmodified
Added
Removed

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

    r14417 r14424  
    3737  [Item("ClusterCreator", "Creates a VRP solution by clustering customers first with a KMeans-algorithm and building tours afterwards alternatevly in a random or a greedy fashion.")]
    3838  [StorableClass]
    39   public sealed class ClusterCreator : PotvinCreator, IStochasticOperator {
     39  public abstract class ClusterCreator : PotvinCreator, IStochasticOperator {
    4040
    4141    public ILookupParameter<IRandom> RandomParameter {
    … …  
    6969    }
    7070
    71     private ClusterCreator(ClusterCreator original, Cloner cloner)
     71    protected ClusterCreator(ClusterCreator original, Cloner cloner)
    7272      : base(original, cloner) {
    7373    }
    7474
    75     public override IDeepCloneable Clone(Cloner cloner) {
    76       return new ClusterCreator(this, cloner);
    77     }
    78 
    79     public static PotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
    80       PotvinEncoding result = new PotvinEncoding(instance);
    81 
    82       IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
    83 
    84       // add all customers
    85       List<int> customers = new List<int>();
    86       for (int i = 1; i <= instance.Cities.Value; i++) {
    87         if(pdp == null || pdp.GetDemand(i) >= 0)
    88           customers.Add(i);
    89       }
    90 
    91       // cluster by spatial distribution
    92 
    93       // (1) wrap stops in ClusterObject
    94       List<ClusterObject> clusterObjects = new List<ClusterObject>();
    95       foreach (int customer in customers) {
    96         clusterObjects.Add(new ClusterObject(customer, instance.GetCoordinates(customer)));
    97       }
    98 
    99       // (2) cluster
    100       int k = random.Next(minK, maxK);
    101       List<Cluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
    102 
    103       // (3) build tours
    104       // (a) shuffle
    105       // (b) greedy
    106       foreach (Cluster c in clusters) {
    107         Tour newTour = new Tour();
    108         result.Tours.Add(newTour);
    109 
    110         if (creationOption == 0) {
    111           // (a) shuffle
    112           c.Objects.Shuffle(random);
    113           foreach (ClusterObject o in c.Objects) {
    114             newTour.Stops.Add(o.Id);
    115           }
    116         } else {
    117           // (b) greedy
    118           foreach (ClusterObject o in c.Objects) {
    119             newTour.Stops.Add(o.Id);
    120           }
    121           GreedyTourCreation(instance, result, newTour, false);
    122         }
    123       }
    124       return result;
    125     }
    126 
    127     public override IOperation InstrumentedApply() {
    128       IRandom random = RandomParameter.ActualValue;
    129 
    130       int minK = (MinK.Value.Value > 0) ? MinK.Value.Value : 1;
    131       int maxK = (MaxK.Value != null) ? MaxK.Value.Value : ProblemInstance.Vehicles.Value;
    132       double clusterChangeThreshold = (ClusterChangeThreshold.Value.Value >= 0.0 &&
    133                                        ClusterChangeThreshold.Value.Value <= 1.0)
    134         ? ClusterChangeThreshold.Value.Value
    135         : 0.0;
    136 
    137       // normalize probabilities
    138       double max = TourCreationProbabilities.Value.Max();
    139       double[] probabilites = new double[2];
    140       for (int i = 0; i < TourCreationProbabilities.Value.Length; i++) {
    141         probabilites[i] = TourCreationProbabilities.Value[i] / max;
    142       }
    143 
    144       List<int> creationOptions = new List<int>() {0, 1};
    145       int creationOption = creationOptions.SampleProportional(random, 1, probabilites, false, false).First();
    146 
    147       VRPToursParameter.ActualValue = CreateSolution(ProblemInstance, random, minK, maxK, clusterChangeThreshold, creationOption);
    148       return base.InstrumentedApply();
    149     }
    150 
    151     private static List<Cluster> KMeans(IVRPProblemInstance instance, IRandom random, List<ClusterObject> objects, int k, double changeTreshold) {
    152 
    153       List<Cluster> clusters = new List<Cluster>();
    154       HashSet<int> initMeans = new HashSet<int>();
    155       int nextMean = -1;
    156 
    157       // (1) initialize each cluster with a random first object (i.e. mean)
    158       for (int i = 0; i < k && i < objects.Count; i++) {
    159         Cluster cluster = new Cluster(instance, i);
    160 
    161         do {
    162           nextMean = random.Next(0, objects.Count);
    163         } while (initMeans.Contains(nextMean));
    164         initMeans.Add(nextMean);
    165         cluster.SetMean(objects[nextMean]);
    166         clusters.Add(cluster);
    167       }
    168 
    169       // (2) repeat clustering until change rate is below threshold
    170       int changes = 0;
    171       double changeRate = 1.0;
    172 
    173       do {
    174         changes = KMeansRun(clusters, objects);
    175         changeRate = changes / objects.Count;
    176 
    177       } while (changeRate > changeTreshold);
    178 
    179       // remove empty clusters
    180       clusters.RemoveAll(c => c.Objects.Count.Equals(0));
    181 
    182       return clusters;
    183     }
    184 
    185     private static int KMeansRun(List<Cluster> clusters, List<ClusterObject> objects) {
    186       int changes = 0;
    187 
    188       foreach (Cluster c in clusters) {
    189         c.Objects.Clear();
    190       }
    191 
    192       foreach (ClusterObject o in objects) {
    193         int bestClusterIdx = -1;
    194         double minImpact = double.MaxValue;
    195         for(int i = 0; i < clusters.Count; i++) {
    196           double impact = clusters[i].CalculateVarianceIncrease(o);
    197           if (impact < minImpact) {
    198             minImpact = impact;
    199             bestClusterIdx = i;
    200           }
    201         }
    202         clusters[bestClusterIdx].AddObject(o);
    203       }
    204 
    205       foreach (Cluster c in clusters) {
    206         c.CalculateMean();
    207       }
    208 
    209       return changes;
    210     }
    211 
    212     class Cluster {
    213       public int Id;
    214       public List<ClusterObject> Objects { get; private set; }
    215       public double Variance { get; private set; }
    216       public ClusterObject Mean { get; set; }
    217 
    218       private readonly IVRPProblemInstance instance;
    219 
    220       public Cluster(IVRPProblemInstance instance, int id) {
    221         this.instance = instance;
    222         Id = id;
    223         Objects = new List<ClusterObject>();
    224       }
    225 
    226       public bool IsEqual(Cluster cluster) {
    227         bool equal = (cluster != null) && (cluster.Objects.Count == Objects.Count);
    228         int index = 0;
    229 
    230         while (equal && index < Objects.Count) {
    231           equal = cluster.Objects.Contains(Objects[index]);
    232           index++;
    233         }
    234         return equal;
    235       }
    236 
    237       public bool AddObject(ClusterObject o) {
    238         Objects.Add(o);
    239 
    240         bool clusterChanged = o.ClusterId != Id;
    241         o.ClusterId = Id;
    242         return clusterChanged;
    243       }
    244 
    245       public void SetMean(ClusterObject o) {
    246         Mean = o;
    247         Mean.ClusterId = Id;
    248       }
    249 
    250       public ClusterObject CalculateMean() {
    251         int dimensions = instance.Coordinates.Columns;
    252         ClusterObject mean = new ClusterObject(-1, Id, dimensions);
    253         foreach (ClusterObject o in Objects) {
    254           double[] coordinates = instance.GetCoordinates(o.Id);
    255           for (int i = 0; i < coordinates.Length; i++) {
    256             mean.Coordinates[i] += (coordinates[i] / Objects.Count);
    257           }
    258         }
    259         Mean = mean;
    260         return Mean;
    261       }
    262 
    263       public double CalculateVariance() {
    264         Variance = 0.0;
    265 
    266         if (Mean == null)
    267           CalculateMean();
    268 
    269         foreach (ClusterObject o in Objects) {
    270           double[] coordinates = instance.GetCoordinates(o.Id);
    271           Variance += Math.Pow(Mean.GetDistance(o.Coordinates), 2);
    272         }
    273         return Variance /= Objects.Count;
    274       }
    275 
    276       public double CalculateVarianceIncrease(ClusterObject o) {
    277         if(Mean == null)
    278           CalculateMean();
    279 
    280         return Math.Pow(Mean.GetDistance(o.Coordinates), 2) / ((Objects.Count > 0) ? Objects.Count : 1);
    281       }
    282     }
    283 
    284     class ClusterObject {
    285      
    286       public int Id { get; private set; }
    287 
    288       public int ClusterId { get; set; }
    289 
    290       public double[] Coordinates { get; set; }
    291 
    292       public ClusterObject() { }
    293 
    294       public ClusterObject(int id, int clusterId = -1) {
    295         Id = id;
    296         ClusterId = clusterId;
    297       }
    298 
    299       public ClusterObject(int id, double[] coordinates) {
    300         Id = id;
    301         Coordinates = coordinates;
    302       }
    303 
    304       public ClusterObject(int id, int clusterId, int dimensions) {
    305         Id = id;
    306         ClusterId = clusterId;
    307         Coordinates = new double[dimensions];
    308       }
    309 
    310       public double GetDistance(double[] otherCoordinates) {
    311         double distance = 0.0;
    312 
    313         for (int i = 0; i < otherCoordinates.Length; i++) {
    314           distance += Math.Pow(Coordinates[i] - otherCoordinates[i], 2);
    315         }
    316         return Math.Sqrt(distance);
    317       }
    318     }
    319 
    320     private static double CalculateAngleToDepot(IVRPProblemInstance instance, int city) {
     75    protected static double CalculateAngleToDepot(IVRPProblemInstance instance, int city) {
    32176      double dx = instance.GetCoordinates(0)[0];
    32277      double dy = instance.GetCoordinates(0)[1];
    … …  
    33691    }
    33792
    338     private static void GreedyTourCreation(IVRPProblemInstance instance, PotvinEncoding individual, Tour tour, bool includeCosts) {
     93    protected static void GreedyTourCreation(IVRPProblemInstance instance, PotvinEncoding individual, Tour tour, bool includeCosts) {
    33994      Tour unrouted = tour.Clone() as Tour;
    34095      tour.Stops.Clear();

  • branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

    r14417 r14424  
    4848    <CodeAnalysisRuleSet>AllRules.ruleset</CodeAnalysisRuleSet>
    4949    <Prefer32Bit>false</Prefer32Bit>
     50    <LangVersion>5</LangVersion>
    5051  </PropertyGroup>
    5152  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
    … …  
    195196    <Compile Include="Analyzer\ConstraintRelaxation\TimeWindowed\TimeWindowRelaxationVRPAnalyzer.cs" />
    196197    <Compile Include="Analyzer\VRPSolution.cs" />
     198    <Compile Include="Encodings\Potvin\Creators\Cluster.cs" />
    197199    <Compile Include="Encodings\Potvin\Creators\ClusterCreator.cs" />
     200    <Compile Include="Encodings\Potvin\Creators\GeographicDistanceClusterCreator.cs" />
    198201    <Compile Include="Encodings\Potvin\Crossovers\PotvinEdgePreservingSequenceBasedCrossover.cs" />
    199202    <Compile Include="Encodings\Potvin\Manipulators\PotvinGreedyTourCreationManipulator.cs" />
Note: See TracChangeset for help on using the changeset viewer.