Free cookie consent management tool by TermsFeed Policy Generator

source: branches/FitnessLandscapeAnalysis/VRPProblemAnalyzer/Program.cs @ 12833

Last change on this file since 12833 was 7316, checked in by svonolfe, 13 years ago

Added Picture generator (#1696)

File size: 8.0 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using System.Text;
6using System.IO;
7using System.Drawing;
8
9namespace VRPProblemAnalyzer {
10 
11  public class Program {
12
13    private static double[] GetDistances(double[,] vertices) {
14      List<double> result = new List<double>();
15
16      int cities = vertices.Length / 2;
17      for (int i = 0; i < cities; i++) {
18        for (int j = 0; j < cities; j++) {
19          if (i != j) {
20            result.Add(Utils.GetDistance(vertices, i, j));
21          }
22        }
23      }
24
25      return result.ToArray();
26    }
27
28    private static double[] GetAverageDistances(double[,] vertices) {
29      int cities = vertices.Length / 2;
30      double[] result = new double[cities];
31     
32      for (int i = 0; i < cities; i++) {
33        double distance = 0;
34        for (int j = 0; j < cities; j++) {
35          if (i != j) {
36            distance += Utils.GetDistance(vertices, i, j);
37          }
38        }
39        result[i] = distance / (cities - 1);
40      }
41
42      return result;
43    }
44
45    private static double GetAverageDistance(TSPLIBParser instance) {
46      double result = 0;
47
48      double[] distances = GetDistances(instance.Vertices);
49      result = distances.Average();
50
51      return result;
52    }
53
54    private static double GetDistanceHeterogenity(TSPLIBParser instance) {
55      double result = 0;
56
57      result = GetAverageDistances(instance.Vertices).StandardDeviation();
58
59      return result;
60    }
61
62    private static double GetDistance(double[] cust1, double[] cust2) {
63      return Math.Sqrt(
64                 Math.Pow((cust1[0] - cust2[0]), 2) +
65                 Math.Pow((cust1[1] - cust2[1]), 2));
66    }
67
68    private static double GetDistance(Cluster cluster1, Cluster cluster2) {
69      List<double> distances = new List<double>();
70      foreach (double[] cust1 in cluster1.Items) {
71        foreach (double[] cust2 in cluster2.Items) {
72          distances.Add(GetDistance(cust1, cust2));
73        }
74      }
75
76      return distances.Min();
77
78      //return GetDistance(cluster1.Center, cluster2.Center);
79    }
80
81    private static double GetDistance(List<Cluster> clusters, Cluster cluster) {
82      List<double> distances = new List<double>();
83      foreach (Cluster other in clusters) {
84        if (other != cluster) {
85          distances.Add(GetDistance(cluster, other));
86        }
87      }
88
89      if (distances.Count > 0)
90        return distances.Min();
91      else
92        return 0;
93    }
94
95    private static double GetCohesion(Cluster cluster) {
96      double cohesion = 0;
97
98      List<double> distances = new List<double>();
99      foreach (double[] cust1 in cluster.Items) {
100        //option 1
101        foreach (double[] cust2 in cluster.Items) {
102          if (cust1 != cust2) {
103            distances.Add(GetDistance(cust1, cust2));           
104          }
105        }
106
107        //option2
108        //distances.Add(GetDistance(cluster.Center, cust1));
109      }
110
111      if (distances.Count > 0)
112        cohesion = distances.Average();
113
114      return cohesion;
115    }
116
117    private static double GetClustering(TSPLIBParser instance) {
118      double result = 0;
119
120      int cities = instance.Vertices.Length / 2 - 1;
121      double[,] coordinates = new double[cities, 2];
122      for (int i = 1; i <= cities; i++) {
123        coordinates[i - 1, 0] = instance.Vertices[i, 0];
124        coordinates[i - 1, 1] = instance.Vertices[i, 1];
125      }
126
127      double clusterFactor = 0;
128      double couplingFactor = 1;
129      double cohesionFactor = 1;
130
131      double maxQuality = double.MinValue;
132
133      int clusters = -1;
134      for (int i = 1; i <= cities; i++) {
135        List<Cluster> collection = KMeansClustering.Cluster(coordinates, i, 9);
136
137        if (collection.Count > 0) {
138          List<double> distances = new List<double>();
139          List<double> cohesions = new List<double>();
140          foreach (Cluster cluster in collection) {
141            distances.Add(GetDistance(collection, cluster));
142            cohesions.Add(GetCohesion(cluster));
143          }
144
145          double distance = distances.Average();
146          double cohesion = cohesions.Average();
147
148          double quality = clusterFactor * (distances.Count / (double)cities) + couplingFactor * distance - cohesionFactor * cohesion;
149          if (quality > maxQuality) {
150            maxQuality = quality;
151            clusters = distances.Count;
152          }
153        }
154      }
155
156      if (clusters != 0)
157        result = (cities / (double)clusters) / cities;
158
159      return result;
160    }
161
162    private static double GetDemandSize(TSPLIBParser instance) {
163      double result = 0;
164
165      result = instance.Demands.Average();
166
167      return result;
168    }
169
170    private static double GetDemandHeterogenity(TSPLIBParser instance) {
171      double result = 0;
172
173      result = instance.Demands.StandardDeviation();
174
175      return result;
176    }
177
178
179    private static void Normalize(TSPLIBParser instance) {
180      //normalize demands
181      for (int i = 0; i < instance.Demands.Length; i++) {
182          instance.Demands[i] = instance.Demands[i] / instance.Capacity;
183      }
184      instance.Capacity = 1.0;
185
186      //normalize coordinates
187      //-find bounds
188      var cities = Utils.MatrixToPointList(instance.Vertices);
189      var minX = cities.Min(c => c.X);
190      var minY = cities.Min(c => c.Y);
191      var maxX = cities.Max(c => c.X);
192      var maxY = cities.Max(c => c.Y);
193      var rangeX = maxX - minX;
194      var rangeY = maxY - minY;
195      var factor = Math.Sqrt(0.5)/Math.Max(rangeX, rangeY);
196
197      for (int i = 0; i < instance.Vertices.GetLength(0); i++) {
198        instance.Vertices[i, 0] = (cities[i].X-minX)*factor;
199        instance.Vertices[i, 1] = (cities[i].Y-minY)*factor;
200      }
201    }
202
203    static void Main(string[] args) {
204      if (args.Length < 1) {
205        Console.Error.WriteLine("Not enough arguments, please specify directory with VRP instances.");
206        Environment.Exit(-1);
207      }
208      var path = args[0];
209      using (StreamWriter sw = new StreamWriter(Path.Combine(path, "analysis.csv"))) {
210        sw.WriteLine("Instance;Customers;Clustering;DistanceAvg;DistanceStdev;DemandAvg;DemandStdev;GeographicExcentricity;DistanceExcentricity;DistanceDemandExcenetricity");
211       
212        string[] instances = Directory.GetFiles(path, "*.vrp", SearchOption.AllDirectories);
213        foreach (string instance in instances) {
214          TSPLIBParser parser = new TSPLIBParser(instance);
215          parser.Parse();
216          Normalize(parser);
217
218          string instanceName = Path.GetFileNameWithoutExtension(instance);
219
220          string solutionName = Path.Combine(Path.GetDirectoryName(instance), Path.GetFileNameWithoutExtension(instance) + ".opt");
221          SolutionParser solution = new SolutionParser(solutionName);
222          solution.Parse();
223
224          sw.Write(instanceName);
225          sw.Write(';');
226          sw.Write(parser.Vertices.Length / 2 - 1);
227          sw.Write(';');
228          sw.Write(GetClustering(parser));
229          sw.Write(';');
230          sw.Write(GetAverageDistance(parser));
231          sw.Write(';');
232          sw.Write(GetDistanceHeterogenity(parser));
233          sw.Write(';');
234          sw.Write(GetDemandSize(parser));
235          sw.Write(';');
236          sw.Write(GetDemandHeterogenity(parser));
237          sw.Write(';');
238          sw.Write(DepotExcentricityCalculator.Geographic(parser.Vertices));
239          sw.Write(';');
240          sw.Write(DepotExcentricityCalculator.DistanceCentroid(parser.Vertices));
241          sw.Write(';');
242          sw.Write(DepotExcentricityCalculator.DemandDistanceCentroid(parser.Vertices, parser.Demands));
243          sw.Write(';');
244          sw.WriteLine();
245
246
247          Image picture = PictureGenerator.GeneratePicture(parser, solution);
248          picture.Save(Path.Combine(path, instanceName + ".png"));
249        }
250      }
251      //Console.WriteLine("Done. Press Enter...");
252      //Console.ReadLine();
253    }
254  }
255}
Note: See TracBrowser for help on using the repository browser.