Changeset 4432
 Timestamp:
 09/19/10 01:38:09 (13 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/HeuristicLab.DiversityAnalysis/HeuristicLab.Problems.TravelingSalesman/3.3/Analyzers/TSPPopulationDiversityAnalyzer.cs
r4420 r4432 40 40 // TODO: 41 41 //  iterations sampling 42 //  decide whether old results shall be stored or disposed43 42 //  view 44 //  check results for identical solutions45 43 46 44 public ScopeTreeLookupParameter<Permutation> PermutationParameter { … … 50 48 get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; } 51 49 } 52 public LookupParameter<ItemList<DoubleMatrix>> SimilaritiesParameter {53 get { return ( LookupParameter<ItemList<DoubleMatrix>>)Parameters["Similarities"]; }50 public ValueParameter<BoolValue> StoreCompleteHistoryParameter { 51 get { return (ValueParameter<BoolValue>)Parameters["StoreCompleteHistory"]; } 54 52 } 55 public LookupParameter<ItemList<DoubleArray>> MaximumSimilaritiesParameter {56 get { return ( LookupParameter<ItemList<DoubleArray>>)Parameters["MaximumSimilarities"]; }53 public ValueParameter<ItemList<DoubleMatrix>> SimilaritiesParameter { 54 get { return (ValueParameter<ItemList<DoubleMatrix>>)Parameters["Similarities"]; } 57 55 } 58 public LookupParameter<ItemList<DoubleValue>> AverageMaximumSimilaritiesParameter {59 get { return ( LookupParameter<ItemList<DoubleValue>>)Parameters["AverageMaximumSimilarities"]; }56 public ValueParameter<ItemList<DoubleArray>> MaximumSimilaritiesParameter { 57 get { return (ValueParameter<ItemList<DoubleArray>>)Parameters["MaximumSimilarities"]; } 60 58 } 61 public LookupParameter<ItemList<DoubleValue>> AverageSimilaritiesParameter {62 get { return ( LookupParameter<ItemList<DoubleValue>>)Parameters["AverageSimilarities"]; }59 public ValueParameter<ItemList<DoubleValue>> AverageMaximumSimilaritiesParameter { 60 get { return (ValueParameter<ItemList<DoubleValue>>)Parameters["AverageMaximumSimilarities"]; } 63 61 } 64 65 [NonSerialized] 66 private int[] rxData, ryData; 67 [NonSerialized] 68 private Permutation lastX, lastY; 62 public ValueParameter<ItemList<DoubleValue>> AverageSimilaritiesParameter { 63 get { return (ValueParameter<ItemList<DoubleValue>>)Parameters["AverageSimilarities"]; } 64 } 69 65 70 66 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.")); 73 69 Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the TSP solutions which should be analyzed.")); 74 Parameters.Add(new LookupParameter<ItemList<DoubleMatrix>>("Similarities", "The similarities of the TSP solutions which should be analyzed.")); 75 Parameters.Add(new LookupParameter<ItemList<DoubleArray>>("MaximumSimilarities", "The maximum similarities of the TSP solutions which should be analyzed.")); 76 Parameters.Add(new LookupParameter<ItemList<DoubleValue>>("AverageMaximumSimilarities", "The average maximum similarities of the TSP solutions which should be analyzed.")); 77 Parameters.Add(new LookupParameter<ItemList<DoubleValue>>("AverageSimilarities", "The average similarities of the TSP solutions which should be analyzed.")); 78 rxData = null; 79 ryData = null; 80 lastX = null; 81 lastY = null; 70 Parameters.Add(new ValueParameter<BoolValue>("StoreCompleteHistory", "Flag that denotes whether the complete history of similarity values shall be stored.", new BoolValue(true))); 71 Parameters.Add(new ValueParameter<ItemList<DoubleMatrix>>("Similarities", "The similarities of the TSP solutions which should be analyzed.")); 72 Parameters.Add(new ValueParameter<ItemList<DoubleArray>>("MaximumSimilarities", "The maximum similarities of the TSP solutions which should be analyzed.")); 73 Parameters.Add(new ValueParameter<ItemList<DoubleValue>>("AverageMaximumSimilarities", "The average maximum similarities of the TSP solutions which should be analyzed.")); 74 Parameters.Add(new ValueParameter<ItemList<DoubleValue>>("AverageSimilarities", "The average similarities of the TSP solutions which should be analyzed.")); 82 75 } 83 76 84 77 public override IOperation Apply() { 78 79 #region testing 80 /* 81 Permutation permutationA = new Permutation(PermutationTypes.Absolute, new int[] { 0, 5, 4, 3, 2, 1 }); 82 Permutation permutationB = new Permutation(PermutationTypes.Absolute, new int[] { 0, 3, 2, 4, 5, 1 }); 83 Permutation permutationC = new Permutation(PermutationTypes.Absolute, new int[] { 3, 2, 4, 5, 1, 0 }); 84 Permutation permutationD = new Permutation(PermutationTypes.Absolute, new int[] { 3, 2, 4, 5, 0, 1 }); 85 int[] edgesA = CalculateEdgesVector(permutationA); 86 int[] edgesB = CalculateEdgesVector(permutationB); 87 int[] edgesC = CalculateEdgesVector(permutationC); 88 int[] edgesD = CalculateEdgesVector(permutationD); 89 double s = CalculateSimilarity(edgesA, edgesB); 90 s = CalculateSimilarity(edgesA, edgesA); 91 s = CalculateSimilarity(edgesB, edgesB); 92 s = CalculateSimilarity(edgesC, edgesC); 93 s = CalculateSimilarity(edgesD, edgesD); 94 s = CalculateSimilarity(edgesB, edgesC); 95 s = CalculateSimilarity(edgesC, edgesD); 96 */ 97 #endregion 85 98 86 99 ItemArray<Permutation> permutations = PermutationParameter.ActualValue; … … 107 120 #endregion 108 121 122 int[][] edges = new int[cities][]; 123 for (int i = 0; i < cities; i++) 124 edges[i] = CalculateEdgesVector(permutationsArray[i]); 125 109 126 DoubleMatrix similarities = new DoubleMatrix(cities, cities); 110 127 DoubleArray maxSimilarities = new DoubleArray(cities); … … 113 130 for (int i = 0; i < cities; i++) { 114 131 similarities[i, i] = 1; 115 // for (int j = (i + 1); j < cities; j++) { 116 for (int j = (i); j < cities; j++) { 117 double similarity = CalculateSimilarity(permutationsArray[i], permutationsArray[j]); 132 for (int j = (i + 1); j < cities; j++) { 133 double similarity = CalculateSimilarity(edges[i], edges[j]); 118 134 avgSimilarity += similarity; 119 135 n++; … … 129 145 DoubleValue averageSimilarity = new DoubleValue(avgSimilarity / n); 130 146 131 if (SimilaritiesParameter. ActualValue == null) {132 SimilaritiesParameter. ActualValue = new ItemList<DoubleMatrix>();133 MaximumSimilaritiesParameter. ActualValue = new ItemList<DoubleArray>();134 AverageMaximumSimilaritiesParameter. ActualValue = new ItemList<DoubleValue>();135 AverageSimilaritiesParameter. ActualValue = new ItemList<DoubleValue>();147 if (SimilaritiesParameter.Value == null) { 148 SimilaritiesParameter.Value = new ItemList<DoubleMatrix>(); 149 MaximumSimilaritiesParameter.Value = new ItemList<DoubleArray>(); 150 AverageMaximumSimilaritiesParameter.Value = new ItemList<DoubleValue>(); 151 AverageSimilaritiesParameter.Value = new ItemList<DoubleValue>(); 136 152 } 137 SimilaritiesParameter.ActualValue.Add(similarities); 138 MaximumSimilaritiesParameter.ActualValue.Add(maxSimilarities); 139 AverageMaximumSimilaritiesParameter.ActualValue.Add(averageMaximumSimilarity); 140 AverageSimilaritiesParameter.ActualValue.Add(averageSimilarity); 153 if (!StoreCompleteHistoryParameter.Value.Value && SimilaritiesParameter.Value.Count > 0) { 154 SimilaritiesParameter.Value[SimilaritiesParameter.Value.Count  1] = null; 155 MaximumSimilaritiesParameter.Value[MaximumSimilaritiesParameter.Value.Count  1] = null; 156 } 157 SimilaritiesParameter.Value.Add(similarities); 158 MaximumSimilaritiesParameter.Value.Add(maxSimilarities); 159 AverageMaximumSimilaritiesParameter.Value.Add(averageMaximumSimilarity); 160 AverageSimilaritiesParameter.Value.Add(averageSimilarity); 141 161 142 162 return base.Apply(); 143 163 } 144 164 145 private double CalculateSimilarity(Permutation x, Permutation y) { 165 private static int[] CalculateEdgesVector(Permutation permutation) { 166 int cities = permutation.Length; 167 int[] edgesVector = new int[cities]; 168 for (int i = 0; i < (cities  1); i++) 169 edgesVector[permutation[i]] = permutation[i + 1]; 170 edgesVector[permutation[cities  1]] = permutation[0]; 171 return edgesVector; 172 } 146 173 147 int cities = x.Length; 148 if (rxData == null  rxData.Length != cities) { 149 rxData = new int[cities]; 150 ryData = new int[cities]; 151 } 152 153 if (x.Length != y.Length) throw new InvalidOperationException("ERROR in " + Name + ": Similarity can only be calculated between instances of an equal number of cities"); 154 #region Performance savings when calling the function with at least one parameter identical to the last call 155 if (x == lastX) { // if Solution1 stayed the same 156 if (y != lastY) { // and Solution2 changed 157 for (int i = 0; i < y.Length; i++) 158 ryData[y[i]] = i; 159 } 160 } else { 161 if (y == lastX && x == lastY) { // if Solution1 and Solution2 were reversed the call before 162 int[] h = ryData; 163 ryData = rxData; 164 rxData = h; 165 } else if (y == lastX) { // or if just Solution1 is different now 166 ryData = rxData; 167 rxData = new int[x.Length]; 168 for (int i = 0; i < x.Length; i++) 169 rxData[x[i]] = i; 170 } else if (x == lastY) { // or just Solution2 is different now 171 rxData = ryData; 172 ryData = new int[y.Length]; 173 for (int i = 0; i < y.Length; i++) 174 ryData[y[i]] = i; 175 } else if (y != lastY) { // or none are the same 176 for (int i = 0; i < x.Length; i++) { 177 rxData[x[i]] = i; 178 ryData[y[i]] = i; 179 } 180 } else { // or just Solution2 is the same 181 for (int i = 0; i < x.Length; i++) 182 rxData[x[i]] = i; 183 } 184 } 185 lastX = x; 186 lastY = y; 187 #endregion 174 private double CalculateSimilarity(int[] edgesA, int[] edgesB) { 175 if (edgesA.Length != edgesB.Length) 176 throw new InvalidOperationException("ERROR in " + Name + ": Similarity can only be calculated between instances of an equal number of cities"); 177 int cities = edgesA.Length; 188 178 int similarEdges = 0; 189 for (int i = 1; i <= x.Length; i++) { 190 if (Math.Abs(ryData[x[(i < x.Length) ? (i) : (0)]]  ryData[x[i  1]]) == 1 191  Math.Abs(ryData[x[(i < x.Length) ? (i) : (0)]]  ryData[x[i  1]]) == x.Length) 179 for (int i = 0; i < edgesA.Length; i++) { 180 if (edgesA[i] == edgesB[i]  edgesA[edgesB[i]] == i) 192 181 similarEdges++; 193 182 } 194 return (double)similarEdges / (double)x.Length; 195 183 return (double)(similarEdges) / cities; 196 184 } 197 185
Note: See TracChangeset
for help on using the changeset viewer.