Changeset 4432

Timestamp:

09/19/10 01:38:09 (14 years ago)

Author:

swinkler

Message:

Worked on population diversity analyzer for TSP. (#1188)

File:

• branches/HeuristicLab.DiversityAnalysis/HeuristicLab.Problems.TravelingSalesman/3.3/Analyzers/TSPPopulationDiversityAnalyzer.cs (modified) (6 diffs)

branches/HeuristicLab.DiversityAnalysis/HeuristicLab.Problems.TravelingSalesman/3.3/Analyzers/TSPPopulationDiversityAnalyzer.cs

@@ -40 +40 @@
     // TODO:
     // - iterations sampling
-    // - decide whether old results shall be stored or disposed
     // - view
-    // - check results for identical solutions
 
     public ScopeTreeLookupParameter<Permutation> PermutationParameter {
@@ -50 +48 @@
       get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
     }
-    public LookupParameter<ItemList<DoubleMatrix>> SimilaritiesParameter {
-      get { return (LookupParameter<ItemList<DoubleMatrix>>)Parameters["Similarities"]; }
+    public ValueParameter<BoolValue> StoreCompleteHistoryParameter {
+      get { return (ValueParameter<BoolValue>)Parameters["StoreCompleteHistory"]; }
     }
-    public LookupParameter<ItemList<DoubleArray>> MaximumSimilaritiesParameter {
-      get { return (LookupParameter<ItemList<DoubleArray>>)Parameters["MaximumSimilarities"]; }
+    public ValueParameter<ItemList<DoubleMatrix>> SimilaritiesParameter {
+      get { return (ValueParameter<ItemList<DoubleMatrix>>)Parameters["Similarities"]; }
     }
-    public LookupParameter<ItemList<DoubleValue>> AverageMaximumSimilaritiesParameter {
-      get { return (LookupParameter<ItemList<DoubleValue>>)Parameters["AverageMaximumSimilarities"]; }
+    public ValueParameter<ItemList<DoubleArray>> MaximumSimilaritiesParameter {
+      get { return (ValueParameter<ItemList<DoubleArray>>)Parameters["MaximumSimilarities"]; }
     }
-    public LookupParameter<ItemList<DoubleValue>> AverageSimilaritiesParameter {
-      get { return (LookupParameter<ItemList<DoubleValue>>)Parameters["AverageSimilarities"]; }
+    public ValueParameter<ItemList<DoubleValue>> AverageMaximumSimilaritiesParameter {
+      get { return (ValueParameter<ItemList<DoubleValue>>)Parameters["AverageMaximumSimilarities"]; }
     }
-
-    [NonSerialized]
-    private int[] rxData, ryData;
-    [NonSerialized]
-    private Permutation lastX, lastY;
+    public ValueParameter<ItemList<DoubleValue>> AverageSimilaritiesParameter {
+      get { return (ValueParameter<ItemList<DoubleValue>>)Parameters["AverageSimilarities"]; }
+    }
 
     public TSPPopulationDiversityAnalyzer()
@@ -72 +68 @@
       Parameters.Add(new ScopeTreeLookupParameter<Permutation>("Permutation", "The TSP solutions given in path representation from which the best solution should be analyzed."));
       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the TSP solutions which should be analyzed."));
-      Parameters.Add(new LookupParameter<ItemList<DoubleMatrix>>("Similarities", "The similarities of the TSP solutions which should be analyzed."));
-      Parameters.Add(new LookupParameter<ItemList<DoubleArray>>("MaximumSimilarities", "The maximum similarities of the TSP solutions which should be analyzed."));
-      Parameters.Add(new LookupParameter<ItemList<DoubleValue>>("AverageMaximumSimilarities", "The average maximum similarities of the TSP solutions which should be analyzed."));
-      Parameters.Add(new LookupParameter<ItemList<DoubleValue>>("AverageSimilarities", "The average similarities of the TSP solutions which should be analyzed."));
-      rxData = null;
-      ryData = null;
-      lastX = null;
-      lastY = null;
+      Parameters.Add(new ValueParameter<BoolValue>("StoreCompleteHistory", "Flag that denotes whether the complete history of similarity values shall be stored.", new BoolValue(true)));
+      Parameters.Add(new ValueParameter<ItemList<DoubleMatrix>>("Similarities", "The similarities of the TSP solutions which should be analyzed."));
+      Parameters.Add(new ValueParameter<ItemList<DoubleArray>>("MaximumSimilarities", "The maximum similarities of the TSP solutions which should be analyzed."));
+      Parameters.Add(new ValueParameter<ItemList<DoubleValue>>("AverageMaximumSimilarities", "The average maximum similarities of the TSP solutions which should be analyzed."));
+      Parameters.Add(new ValueParameter<ItemList<DoubleValue>>("AverageSimilarities", "The average similarities of the TSP solutions which should be analyzed."));
     }
 
     public override IOperation Apply() {
+
+      #region testing
+      /*
+      Permutation permutationA = new Permutation(PermutationTypes.Absolute, new int[] { 0, 5, 4, 3, 2, 1 });
+      Permutation permutationB = new Permutation(PermutationTypes.Absolute, new int[] { 0, 3, 2, 4, 5, 1 });
+      Permutation permutationC = new Permutation(PermutationTypes.Absolute, new int[] { 3, 2, 4, 5, 1, 0 });
+      Permutation permutationD = new Permutation(PermutationTypes.Absolute, new int[] { 3, 2, 4, 5, 0, 1 });
+      int[] edgesA = CalculateEdgesVector(permutationA);
+      int[] edgesB = CalculateEdgesVector(permutationB);
+      int[] edgesC = CalculateEdgesVector(permutationC);
+      int[] edgesD = CalculateEdgesVector(permutationD);
+      double s = CalculateSimilarity(edgesA, edgesB);
+      s = CalculateSimilarity(edgesA, edgesA);
+      s = CalculateSimilarity(edgesB, edgesB);
+      s = CalculateSimilarity(edgesC, edgesC);
+      s = CalculateSimilarity(edgesD, edgesD);
+      s = CalculateSimilarity(edgesB, edgesC);
+      s = CalculateSimilarity(edgesC, edgesD);
+      */
+      #endregion
 
       ItemArray<Permutation> permutations = PermutationParameter.ActualValue;
@@ -107 +120 @@
       #endregion
 
+      int[][] edges = new int[cities][];
+      for (int i = 0; i < cities; i++)
+        edges[i] = CalculateEdgesVector(permutationsArray[i]);
+
       DoubleMatrix similarities = new DoubleMatrix(cities, cities);
       DoubleArray maxSimilarities = new DoubleArray(cities);
@@ -113 +130 @@
       for (int i = 0; i < cities; i++) {
         similarities[i, i] = 1;
-        // for (int j = (i + 1); j < cities; j++) {
-        for (int j = (i); j < cities; j++) {
-          double similarity = CalculateSimilarity(permutationsArray[i], permutationsArray[j]);
+        for (int j = (i + 1); j < cities; j++) {
+          double similarity = CalculateSimilarity(edges[i], edges[j]);
           avgSimilarity += similarity;
           n++;
@@ -129 +145 @@
       DoubleValue averageSimilarity = new DoubleValue(avgSimilarity / n);
 
-      if (SimilaritiesParameter.ActualValue == null) {
-        SimilaritiesParameter.ActualValue = new ItemList<DoubleMatrix>();
-        MaximumSimilaritiesParameter.ActualValue = new ItemList<DoubleArray>();
-        AverageMaximumSimilaritiesParameter.ActualValue = new ItemList<DoubleValue>();
-        AverageSimilaritiesParameter.ActualValue = new ItemList<DoubleValue>();
+      if (SimilaritiesParameter.Value == null) {
+        SimilaritiesParameter.Value = new ItemList<DoubleMatrix>();
+        MaximumSimilaritiesParameter.Value = new ItemList<DoubleArray>();
+        AverageMaximumSimilaritiesParameter.Value = new ItemList<DoubleValue>();
+        AverageSimilaritiesParameter.Value = new ItemList<DoubleValue>();
       }
-      SimilaritiesParameter.ActualValue.Add(similarities);
-      MaximumSimilaritiesParameter.ActualValue.Add(maxSimilarities);
-      AverageMaximumSimilaritiesParameter.ActualValue.Add(averageMaximumSimilarity);
-      AverageSimilaritiesParameter.ActualValue.Add(averageSimilarity);
+      if (!StoreCompleteHistoryParameter.Value.Value && SimilaritiesParameter.Value.Count > 0) {
+        SimilaritiesParameter.Value[SimilaritiesParameter.Value.Count - 1] = null;
+        MaximumSimilaritiesParameter.Value[MaximumSimilaritiesParameter.Value.Count - 1] = null;
+      }
+      SimilaritiesParameter.Value.Add(similarities);
+      MaximumSimilaritiesParameter.Value.Add(maxSimilarities);
+      AverageMaximumSimilaritiesParameter.Value.Add(averageMaximumSimilarity);
+      AverageSimilaritiesParameter.Value.Add(averageSimilarity);
 
       return base.Apply();
     }
 
-    private double CalculateSimilarity(Permutation x, Permutation y) {
+    private static int[] CalculateEdgesVector(Permutation permutation) {
+      int cities = permutation.Length;
+      int[] edgesVector = new int[cities];
+      for (int i = 0; i < (cities - 1); i++)
+        edgesVector[permutation[i]] = permutation[i + 1];
+      edgesVector[permutation[cities - 1]] = permutation[0];
+      return edgesVector;
+    }
 
-      int cities = x.Length;
-      if (rxData == null || rxData.Length != cities) {
-        rxData = new int[cities];
-        ryData = new int[cities];
-      }
-
-      if (x.Length != y.Length) throw new InvalidOperationException("ERROR in " + Name + ": Similarity can only be calculated between instances of an equal number of cities");
-      #region Performance savings when calling the function with at least one parameter identical to the last call
-      if (x == lastX) { // if Solution1 stayed the same
-        if (y != lastY) { // and Solution2 changed
-          for (int i = 0; i < y.Length; i++)
-            ryData[y[i]] = i;
-        }
-      } else {
-        if (y == lastX && x == lastY) { // if Solution1 and Solution2 were reversed the call before
-          int[] h = ryData;
-          ryData = rxData;
-          rxData = h;
-        } else if (y == lastX) { // or if just Solution1 is different now
-          ryData = rxData;
-          rxData = new int[x.Length];
-          for (int i = 0; i < x.Length; i++)
-            rxData[x[i]] = i;
-        } else if (x == lastY) { // or just Solution2 is different now
-          rxData = ryData;
-          ryData = new int[y.Length];
-          for (int i = 0; i < y.Length; i++)
-            ryData[y[i]] = i;
-        } else if (y != lastY) { // or none are the same
-          for (int i = 0; i < x.Length; i++) {
-            rxData[x[i]] = i;
-            ryData[y[i]] = i;
-          }
-        } else { // or just Solution2 is the same
-          for (int i = 0; i < x.Length; i++)
-            rxData[x[i]] = i;
-        }
-      }
-      lastX = x;
-      lastY = y;
-      #endregion
+    private double CalculateSimilarity(int[] edgesA, int[] edgesB) {
+      if (edgesA.Length != edgesB.Length)
+        throw new InvalidOperationException("ERROR in " + Name + ": Similarity can only be calculated between instances of an equal number of cities");
+      int cities = edgesA.Length;
       int similarEdges = 0;
-      for (int i = 1; i <= x.Length; i++) {
-        if (Math.Abs(ryData[x[(i < x.Length) ? (i) : (0)]] - ryData[x[i - 1]]) == 1
-          || Math.Abs(ryData[x[(i < x.Length) ? (i) : (0)]] - ryData[x[i - 1]]) == x.Length)
+      for (int i = 0; i < edgesA.Length; i++) {
+        if (edgesA[i] == edgesB[i] || edgesA[edgesB[i]] == i)
           similarEdges++;
       }
-      return (double)similarEdges / (double)x.Length;
-
+      return (double)(similarEdges) / cities;
     }