Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.DiversityAnalysis/HeuristicLab.Problems.TravelingSalesman/3.3/Analyzers/TSPPopulationDiversityAnalyzer.cs @ 4501

Last change on this file since 4501 was 4501, checked in by swinkler, 13 years ago

Worked on population diversity analyzer for TSP: Implemented storing of population diversity result overview in the algorithm's results collection. (#1188)

File size: 10.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Linq;
24using HeuristicLab.Analysis;
25using HeuristicLab.Core;
26using HeuristicLab.Common;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.PermutationEncoding;
29using HeuristicLab.Operators;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using System.Data;
34
35namespace HeuristicLab.Problems.TravelingSalesman {
36  /// <summary>
37  /// An operator for analyzing the diversity of a population of solutions for a Traveling Salesman Problems given in path representation using city coordinates.
38  /// </summary>
39  [Item("TSPPopulationDiversityAnalyzer", "An operator for analyzing the diversity of a population of solutions for a Traveling Salesman Problems given in path representation using city coordinates.")]
40  [StorableClass]
41  public sealed class TSPPopulationDiversityAnalyzer : SingleSuccessorOperator, IAnalyzer {
42
43    // TODO:
44    // - iterations sampling
45    // - view
46    // - implement data structure for population diversity details
47
48    public const string PermutationKey = "Permutation";
49    public ScopeTreeLookupParameter<Permutation> PermutationParameter {
50      get { return (ScopeTreeLookupParameter<Permutation>)Parameters[PermutationKey]; }
51    }
52    public const string QualityKey = "Quality";
53    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
54      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters[QualityKey]; }
55    }
56
57    public const string StoreCompleteHistoryKey = "StoreCompleteHistory";
58    public ValueParameter<BoolValue> StoreCompleteHistoryParameter {
59      get { return (ValueParameter<BoolValue>)Parameters[StoreCompleteHistoryKey]; }
60    }
61
62    public const string SimilaritiesKey = "Similarities";
63    public ValueParameter<ItemList<DoubleMatrix>> SimilaritiesParameter {
64      get { return (ValueParameter<ItemList<DoubleMatrix>>)Parameters[SimilaritiesKey]; }
65    }
66    public const string MaximumSimilaritiesKey = "MaximumSimilarities";
67    public ValueParameter<ItemList<DoubleArray>> MaximumSimilaritiesParameter {
68      get { return (ValueParameter<ItemList<DoubleArray>>)Parameters[MaximumSimilaritiesKey]; }
69    }
70
71    public const string CurrentAverageSimilarityKey = "Current Average Population Similarity";
72    public const string AverageSimilarityProgressKey = "Average Population Similarity Progress";
73    public const string CurrentAverageMaximumSimilarityKey = "Current Average Maximum Population Similarity";
74    public const string AverageMaximumSimilarityProgressKey = "Average Maximum Population Similarity Progress";
75
76    public const string ResultsKey = "Results";
77    public ValueLookupParameter<ResultCollection> ResultsParameter {
78      get { return (ValueLookupParameter<ResultCollection>)Parameters[ResultsKey]; }
79    }
80
81    public TSPPopulationDiversityAnalyzer()
82      : base() {
83      Parameters.Add(new ScopeTreeLookupParameter<Permutation>(PermutationKey, "The TSP solutions given in path representation from which the best solution should be analyzed."));
84      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityKey, "The qualities of the TSP solutions which should be analyzed."));
85      Parameters.Add(new ValueParameter<BoolValue>(StoreCompleteHistoryKey, "Flag that denotes whether the complete history of similarity values shall be stored.", new BoolValue(true)));
86      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The results collection in which the population diversity analysis results should be stored."));
87
88      Parameters.Add(new ValueParameter<ItemList<DoubleMatrix>>(SimilaritiesKey, "The similarities of the TSP solutions which should be analyzed."));
89      Parameters.Add(new ValueParameter<ItemList<DoubleArray>>(MaximumSimilaritiesKey, "The maximum similarities of the TSP solutions which should be analyzed."));
90    }
91
92    public override IOperation Apply() {
93
94      ItemArray<Permutation> permutations = PermutationParameter.ActualValue;
95      ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
96      Permutation[] permutationsArray = permutations.ToArray();
97      DoubleValue[] qualitiesArray = qualities.ToArray();
98      int cities = permutationsArray.Length;
99      ResultCollection results = ResultsParameter.ActualValue;
100
101      #region sort permutations array
102      for (int i = 0; i < cities; i++) {
103        int minIndex = i;
104        for (int j = i + 1; j < cities; j++) {
105          if (qualitiesArray[j].Value < qualitiesArray[minIndex].Value)
106            minIndex = j;
107        }
108        if (minIndex != i) {
109          Permutation p = permutationsArray[i];
110          permutationsArray[i] = permutationsArray[minIndex];
111          permutationsArray[minIndex] = p;
112          DoubleValue d = qualitiesArray[i];
113          qualitiesArray[i] = qualitiesArray[minIndex];
114          qualitiesArray[minIndex] = d;
115        }
116      }
117      #endregion
118
119      int[][] edges = new int[cities][];
120      for (int i = 0; i < cities; i++)
121        edges[i] = CalculateEdgesVector(permutationsArray[i]);
122
123      DoubleMatrix similarities = new DoubleMatrix(cities, cities);
124      DoubleArray maxSimilarities = new DoubleArray(cities);
125      double avgSimilarity = 0;
126      int n = 0;
127      for (int i = 0; i < cities; i++) {
128        similarities[i, i] = 1;
129        for (int j = (i + 1); j < cities; j++) {
130          double similarity = CalculateSimilarity(edges[i], edges[j]);
131          avgSimilarity += similarity;
132          n++;
133          similarities[i, j] = similarity;
134          similarities[j, i] = similarity;
135          if (maxSimilarities[i] < similarity)
136            maxSimilarities[i] = similarity;
137          if (maxSimilarities[j] < similarity)
138            maxSimilarities[j] = similarity;
139        }
140      }
141      DoubleValue averageMaximumSimilarity = new DoubleValue(maxSimilarities.Average());
142      DoubleValue averageSimilarity = new DoubleValue(avgSimilarity / n);
143
144      if (SimilaritiesParameter.Value == null) {
145        SimilaritiesParameter.Value = new ItemList<DoubleMatrix>();
146        MaximumSimilaritiesParameter.Value = new ItemList<DoubleArray>();
147      }
148      if (!StoreCompleteHistoryParameter.Value.Value && SimilaritiesParameter.Value.Count > 0) {
149        SimilaritiesParameter.Value[SimilaritiesParameter.Value.Count - 1] = null;
150        MaximumSimilaritiesParameter.Value[MaximumSimilaritiesParameter.Value.Count - 1] = null;
151      }
152      SimilaritiesParameter.Value.Add(similarities);
153      MaximumSimilaritiesParameter.Value.Add(maxSimilarities);
154
155      #region Store average similarity values
156      if (results.ContainsKey(CurrentAverageSimilarityKey))
157        results[CurrentAverageSimilarityKey].Value = averageSimilarity;
158      else
159        results.Add(new Result(CurrentAverageSimilarityKey, averageSimilarity));
160
161      if (!results.ContainsKey(AverageSimilarityProgressKey))
162        results.Add(new Result(AverageSimilarityProgressKey, new Analysis.DataTable(AverageSimilarityProgressKey)));
163      Analysis.DataTable averageSimilarityProgressDataTable = (Analysis.DataTable)(results[AverageSimilarityProgressKey].Value);
164      if (averageSimilarityProgressDataTable.Rows.Count == 0)
165        averageSimilarityProgressDataTable.Rows.Add(new Analysis.DataRow(AverageSimilarityProgressKey));
166      averageSimilarityProgressDataTable.Rows[AverageSimilarityProgressKey].Values.Add(averageSimilarity.Value);
167      #endregion
168      #region Store average maximum similarity values
169      if (results.ContainsKey(CurrentAverageMaximumSimilarityKey))
170        results[CurrentAverageMaximumSimilarityKey].Value = averageMaximumSimilarity;
171      else
172        results.Add(new Result(CurrentAverageMaximumSimilarityKey, averageMaximumSimilarity));
173
174      if (!results.ContainsKey(AverageMaximumSimilarityProgressKey))
175        results.Add(new Result(AverageMaximumSimilarityProgressKey, new Analysis.DataTable(AverageMaximumSimilarityProgressKey)));
176      Analysis.DataTable averageMaximumSimilarityProgressDataTable = (Analysis.DataTable)(results[AverageMaximumSimilarityProgressKey].Value);
177      if (averageMaximumSimilarityProgressDataTable.Rows.Count == 0)
178        averageMaximumSimilarityProgressDataTable.Rows.Add(new Analysis.DataRow(AverageMaximumSimilarityProgressKey));
179      averageMaximumSimilarityProgressDataTable.Rows[AverageMaximumSimilarityProgressKey].Values.Add(averageMaximumSimilarity.Value);
180      #endregion
181
182      return base.Apply();
183    }
184
185    private static int[] CalculateEdgesVector(Permutation permutation) {
186      int cities = permutation.Length;
187      int[] edgesVector = new int[cities];
188      for (int i = 0; i < (cities - 1); i++)
189        edgesVector[permutation[i]] = permutation[i + 1];
190      edgesVector[permutation[cities - 1]] = permutation[0];
191      return edgesVector;
192    }
193
194    private double CalculateSimilarity(int[] edgesA, int[] edgesB) {
195      if (edgesA.Length != edgesB.Length)
196        throw new InvalidOperationException("ERROR in " + Name + ": Similarity can only be calculated between instances of an equal number of cities");
197      int cities = edgesA.Length;
198      int similarEdges = 0;
199      for (int i = 0; i < edgesA.Length; i++) {
200        if (edgesA[i] == edgesB[i] || edgesA[edgesB[i]] == i)
201          similarEdges++;
202      }
203      return (double)(similarEdges) / cities;
204    }
205
206  }
207}
Note: See TracBrowser for help on using the repository browser.