[4420] | 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 |
|
---|
| 22 | using System;
|
---|
| 23 | using System.Linq;
|
---|
[4501] | 24 | using HeuristicLab.Analysis;
|
---|
[4420] | 25 | using HeuristicLab.Core;
|
---|
[4501] | 26 | using HeuristicLab.Common;
|
---|
[4420] | 27 | using HeuristicLab.Data;
|
---|
| 28 | using HeuristicLab.Encodings.PermutationEncoding;
|
---|
| 29 | using HeuristicLab.Operators;
|
---|
| 30 | using HeuristicLab.Optimization;
|
---|
| 31 | using HeuristicLab.Parameters;
|
---|
| 32 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
[4501] | 33 | using System.Data;
|
---|
[4420] | 34 |
|
---|
| 35 | namespace 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
|
---|
[4502] | 46 | // - extract population diversity basic behavior into separate project
|
---|
[4552] | 47 | // - analyze variation of values
|
---|
[4420] | 48 |
|
---|
[4501] | 49 | public const string PermutationKey = "Permutation";
|
---|
[4420] | 50 | public ScopeTreeLookupParameter<Permutation> PermutationParameter {
|
---|
[4501] | 51 | get { return (ScopeTreeLookupParameter<Permutation>)Parameters[PermutationKey]; }
|
---|
[4420] | 52 | }
|
---|
[4501] | 53 | public const string QualityKey = "Quality";
|
---|
[4420] | 54 | public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
|
---|
[4501] | 55 | get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters[QualityKey]; }
|
---|
[4420] | 56 | }
|
---|
[4501] | 57 |
|
---|
| 58 | public const string StoreCompleteHistoryKey = "StoreCompleteHistory";
|
---|
[4432] | 59 | public ValueParameter<BoolValue> StoreCompleteHistoryParameter {
|
---|
[4501] | 60 | get { return (ValueParameter<BoolValue>)Parameters[StoreCompleteHistoryKey]; }
|
---|
[4420] | 61 | }
|
---|
[4501] | 62 |
|
---|
| 63 | public const string CurrentAverageSimilarityKey = "Current Average Population Similarity";
|
---|
| 64 | public const string AverageSimilarityProgressKey = "Average Population Similarity Progress";
|
---|
| 65 | public const string CurrentAverageMaximumSimilarityKey = "Current Average Maximum Population Similarity";
|
---|
| 66 | public const string AverageMaximumSimilarityProgressKey = "Average Maximum Population Similarity Progress";
|
---|
[4502] | 67 | public const string PopulationDiversityAnalysisResultsDetailsKey = "Population Diversity Analysis Results Details";
|
---|
[4501] | 68 |
|
---|
| 69 | public const string ResultsKey = "Results";
|
---|
| 70 | public ValueLookupParameter<ResultCollection> ResultsParameter {
|
---|
| 71 | get { return (ValueLookupParameter<ResultCollection>)Parameters[ResultsKey]; }
|
---|
[4420] | 72 | }
|
---|
| 73 |
|
---|
| 74 | public TSPPopulationDiversityAnalyzer()
|
---|
| 75 | : base() {
|
---|
[4501] | 76 | Parameters.Add(new ScopeTreeLookupParameter<Permutation>(PermutationKey, "The TSP solutions given in path representation from which the best solution should be analyzed."));
|
---|
| 77 | Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityKey, "The qualities of the TSP solutions which should be analyzed."));
|
---|
| 78 | Parameters.Add(new ValueParameter<BoolValue>(StoreCompleteHistoryKey, "Flag that denotes whether the complete history of similarity values shall be stored.", new BoolValue(true)));
|
---|
| 79 | Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The results collection in which the population diversity analysis results should be stored."));
|
---|
[4420] | 80 | }
|
---|
| 81 |
|
---|
| 82 | public override IOperation Apply() {
|
---|
| 83 |
|
---|
| 84 | ItemArray<Permutation> permutations = PermutationParameter.ActualValue;
|
---|
| 85 | ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
|
---|
| 86 | Permutation[] permutationsArray = permutations.ToArray();
|
---|
| 87 | DoubleValue[] qualitiesArray = qualities.ToArray();
|
---|
| 88 | int cities = permutationsArray.Length;
|
---|
[4501] | 89 | ResultCollection results = ResultsParameter.ActualValue;
|
---|
| 90 |
|
---|
[4420] | 91 | #region sort permutations array
|
---|
| 92 | for (int i = 0; i < cities; i++) {
|
---|
| 93 | int minIndex = i;
|
---|
| 94 | for (int j = i + 1; j < cities; j++) {
|
---|
| 95 | if (qualitiesArray[j].Value < qualitiesArray[minIndex].Value)
|
---|
| 96 | minIndex = j;
|
---|
| 97 | }
|
---|
| 98 | if (minIndex != i) {
|
---|
| 99 | Permutation p = permutationsArray[i];
|
---|
| 100 | permutationsArray[i] = permutationsArray[minIndex];
|
---|
| 101 | permutationsArray[minIndex] = p;
|
---|
| 102 | DoubleValue d = qualitiesArray[i];
|
---|
| 103 | qualitiesArray[i] = qualitiesArray[minIndex];
|
---|
| 104 | qualitiesArray[minIndex] = d;
|
---|
| 105 | }
|
---|
| 106 | }
|
---|
| 107 | #endregion
|
---|
| 108 |
|
---|
[4432] | 109 | int[][] edges = new int[cities][];
|
---|
| 110 | for (int i = 0; i < cities; i++)
|
---|
| 111 | edges[i] = CalculateEdgesVector(permutationsArray[i]);
|
---|
| 112 |
|
---|
[4544] | 113 | DoubleMatrix similarities = new DoubleMatrix(cities, cities);
|
---|
| 114 | DoubleArray maxSimilarities = new DoubleArray(cities);
|
---|
[4420] | 115 | double avgSimilarity = 0;
|
---|
| 116 | int n = 0;
|
---|
| 117 | for (int i = 0; i < cities; i++) {
|
---|
| 118 | similarities[i, i] = 1;
|
---|
[4432] | 119 | for (int j = (i + 1); j < cities; j++) {
|
---|
| 120 | double similarity = CalculateSimilarity(edges[i], edges[j]);
|
---|
[4420] | 121 | avgSimilarity += similarity;
|
---|
| 122 | n++;
|
---|
| 123 | similarities[i, j] = similarity;
|
---|
| 124 | similarities[j, i] = similarity;
|
---|
| 125 | if (maxSimilarities[i] < similarity)
|
---|
| 126 | maxSimilarities[i] = similarity;
|
---|
| 127 | if (maxSimilarities[j] < similarity)
|
---|
| 128 | maxSimilarities[j] = similarity;
|
---|
| 129 | }
|
---|
| 130 | }
|
---|
| 131 | DoubleValue averageMaximumSimilarity = new DoubleValue(maxSimilarities.Average());
|
---|
| 132 | DoubleValue averageSimilarity = new DoubleValue(avgSimilarity / n);
|
---|
| 133 |
|
---|
[4501] | 134 | #region Store average similarity values
|
---|
| 135 | if (results.ContainsKey(CurrentAverageSimilarityKey))
|
---|
| 136 | results[CurrentAverageSimilarityKey].Value = averageSimilarity;
|
---|
| 137 | else
|
---|
| 138 | results.Add(new Result(CurrentAverageSimilarityKey, averageSimilarity));
|
---|
| 139 |
|
---|
| 140 | if (!results.ContainsKey(AverageSimilarityProgressKey))
|
---|
| 141 | results.Add(new Result(AverageSimilarityProgressKey, new Analysis.DataTable(AverageSimilarityProgressKey)));
|
---|
| 142 | Analysis.DataTable averageSimilarityProgressDataTable = (Analysis.DataTable)(results[AverageSimilarityProgressKey].Value);
|
---|
| 143 | if (averageSimilarityProgressDataTable.Rows.Count == 0)
|
---|
| 144 | averageSimilarityProgressDataTable.Rows.Add(new Analysis.DataRow(AverageSimilarityProgressKey));
|
---|
| 145 | averageSimilarityProgressDataTable.Rows[AverageSimilarityProgressKey].Values.Add(averageSimilarity.Value);
|
---|
| 146 | #endregion
|
---|
| 147 | #region Store average maximum similarity values
|
---|
| 148 | if (results.ContainsKey(CurrentAverageMaximumSimilarityKey))
|
---|
| 149 | results[CurrentAverageMaximumSimilarityKey].Value = averageMaximumSimilarity;
|
---|
| 150 | else
|
---|
| 151 | results.Add(new Result(CurrentAverageMaximumSimilarityKey, averageMaximumSimilarity));
|
---|
| 152 |
|
---|
| 153 | if (!results.ContainsKey(AverageMaximumSimilarityProgressKey))
|
---|
| 154 | results.Add(new Result(AverageMaximumSimilarityProgressKey, new Analysis.DataTable(AverageMaximumSimilarityProgressKey)));
|
---|
| 155 | Analysis.DataTable averageMaximumSimilarityProgressDataTable = (Analysis.DataTable)(results[AverageMaximumSimilarityProgressKey].Value);
|
---|
| 156 | if (averageMaximumSimilarityProgressDataTable.Rows.Count == 0)
|
---|
| 157 | averageMaximumSimilarityProgressDataTable.Rows.Add(new Analysis.DataRow(AverageMaximumSimilarityProgressKey));
|
---|
| 158 | averageMaximumSimilarityProgressDataTable.Rows[AverageMaximumSimilarityProgressKey].Values.Add(averageMaximumSimilarity.Value);
|
---|
| 159 | #endregion
|
---|
[4502] | 160 | #region Store details
|
---|
| 161 | TSPPopulationDiversityAnalysisDetails details;
|
---|
| 162 | if (!results.ContainsKey(PopulationDiversityAnalysisResultsDetailsKey)) {
|
---|
| 163 | details = new TSPPopulationDiversityAnalysisDetails();
|
---|
| 164 | results.Add(new Result(PopulationDiversityAnalysisResultsDetailsKey, details));
|
---|
| 165 | } else {
|
---|
| 166 | details = (TSPPopulationDiversityAnalysisDetails)(results[PopulationDiversityAnalysisResultsDetailsKey].Value);
|
---|
| 167 | }
|
---|
[4544] | 168 | details.AverageSimilarities.Add(averageSimilarity);
|
---|
| 169 | details.AverageMaximumSimilarities.Add(averageMaximumSimilarity);
|
---|
[4502] | 170 | details.Similarities.Add(similarities);
|
---|
| 171 | details.MaximumSimilarities.Add(maxSimilarities);
|
---|
| 172 | if (!StoreCompleteHistoryParameter.Value.Value && details.Similarities.Count > 1) {
|
---|
| 173 | details.Similarities[details.Similarities.Count - 1] = null;
|
---|
| 174 | details.MaximumSimilarities[details.MaximumSimilarities.Count - 1] = null;
|
---|
| 175 | }
|
---|
| 176 | #endregion
|
---|
[4501] | 177 |
|
---|
[4420] | 178 | return base.Apply();
|
---|
| 179 | }
|
---|
| 180 |
|
---|
[4432] | 181 | private static int[] CalculateEdgesVector(Permutation permutation) {
|
---|
| 182 | int cities = permutation.Length;
|
---|
| 183 | int[] edgesVector = new int[cities];
|
---|
| 184 | for (int i = 0; i < (cities - 1); i++)
|
---|
| 185 | edgesVector[permutation[i]] = permutation[i + 1];
|
---|
| 186 | edgesVector[permutation[cities - 1]] = permutation[0];
|
---|
| 187 | return edgesVector;
|
---|
| 188 | }
|
---|
[4420] | 189 |
|
---|
[4432] | 190 | private double CalculateSimilarity(int[] edgesA, int[] edgesB) {
|
---|
| 191 | if (edgesA.Length != edgesB.Length)
|
---|
| 192 | throw new InvalidOperationException("ERROR in " + Name + ": Similarity can only be calculated between instances of an equal number of cities");
|
---|
| 193 | int cities = edgesA.Length;
|
---|
[4420] | 194 | int similarEdges = 0;
|
---|
[4432] | 195 | for (int i = 0; i < edgesA.Length; i++) {
|
---|
| 196 | if (edgesA[i] == edgesB[i] || edgesA[edgesB[i]] == i)
|
---|
[4420] | 197 | similarEdges++;
|
---|
| 198 | }
|
---|
[4432] | 199 | return (double)(similarEdges) / cities;
|
---|
[4420] | 200 | }
|
---|
| 201 |
|
---|
| 202 | }
|
---|
| 203 | }
|
---|