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

Last change on this file since 7231 was 7231, checked in by svonolfe, 11 years ago

Added VRP problem analyzer (#1696)

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