#region License Information
/* HeuristicLab
* Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
*
* This file is part of HeuristicLab.
*
* HeuristicLab is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* HeuristicLab is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with HeuristicLab. If not, see .
*/
#endregion
using System;
using System.Linq;
using HeuristicLab.Analysis;
using HeuristicLab.Core;
using HeuristicLab.Common;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using System.Data;
namespace HeuristicLab.Problems.TravelingSalesman {
///
/// An operator for analyzing the diversity of a population of solutions for a Traveling Salesman Problems given in path representation using city coordinates.
///
[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.")]
[StorableClass]
public sealed class TSPPopulationDiversityAnalyzer : SingleSuccessorOperator, IAnalyzer {
// TODO:
// - iterations sampling
// - view
// - extract population diversity basic behavior into separate project
// - analyze variation of values
public const string PermutationKey = "Permutation";
public ScopeTreeLookupParameter PermutationParameter {
get { return (ScopeTreeLookupParameter)Parameters[PermutationKey]; }
}
public const string QualityKey = "Quality";
public ScopeTreeLookupParameter QualityParameter {
get { return (ScopeTreeLookupParameter)Parameters[QualityKey]; }
}
public const string StoreCompleteHistoryKey = "StoreCompleteHistory";
public ValueParameter StoreCompleteHistoryParameter {
get { return (ValueParameter)Parameters[StoreCompleteHistoryKey]; }
}
public const string CurrentAverageSimilarityKey = "Current Average Population Similarity";
public const string AverageSimilarityProgressKey = "Average Population Similarity Progress";
public const string CurrentAverageMaximumSimilarityKey = "Current Average Maximum Population Similarity";
public const string AverageMaximumSimilarityProgressKey = "Average Maximum Population Similarity Progress";
public const string PopulationDiversityAnalysisResultsDetailsKey = "Population Diversity Analysis Results Details";
public const string ResultsKey = "Results";
public ValueLookupParameter ResultsParameter {
get { return (ValueLookupParameter)Parameters[ResultsKey]; }
}
public TSPPopulationDiversityAnalyzer()
: base() {
Parameters.Add(new ScopeTreeLookupParameter(PermutationKey, "The TSP solutions given in path representation from which the best solution should be analyzed."));
Parameters.Add(new ScopeTreeLookupParameter(QualityKey, "The qualities of the TSP solutions which should be analyzed."));
Parameters.Add(new ValueParameter(StoreCompleteHistoryKey, "Flag that denotes whether the complete history of similarity values shall be stored.", new BoolValue(true)));
Parameters.Add(new ValueLookupParameter("Results", "The results collection in which the population diversity analysis results should be stored."));
}
public override IOperation Apply() {
ItemArray permutations = PermutationParameter.ActualValue;
ItemArray qualities = QualityParameter.ActualValue;
Permutation[] permutationsArray = permutations.ToArray();
DoubleValue[] qualitiesArray = qualities.ToArray();
int cities = permutationsArray.Length;
ResultCollection results = ResultsParameter.ActualValue;
#region sort permutations array
for (int i = 0; i < cities; i++) {
int minIndex = i;
for (int j = i + 1; j < cities; j++) {
if (qualitiesArray[j].Value < qualitiesArray[minIndex].Value)
minIndex = j;
}
if (minIndex != i) {
Permutation p = permutationsArray[i];
permutationsArray[i] = permutationsArray[minIndex];
permutationsArray[minIndex] = p;
DoubleValue d = qualitiesArray[i];
qualitiesArray[i] = qualitiesArray[minIndex];
qualitiesArray[minIndex] = d;
}
}
#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);
double avgSimilarity = 0;
int n = 0;
for (int i = 0; i < cities; i++) {
similarities[i, i] = 1;
for (int j = (i + 1); j < cities; j++) {
double similarity = CalculateSimilarity(edges[i], edges[j]);
avgSimilarity += similarity;
n++;
similarities[i, j] = similarity;
similarities[j, i] = similarity;
if (maxSimilarities[i] < similarity)
maxSimilarities[i] = similarity;
if (maxSimilarities[j] < similarity)
maxSimilarities[j] = similarity;
}
}
DoubleValue averageMaximumSimilarity = new DoubleValue(maxSimilarities.Average());
DoubleValue averageSimilarity = new DoubleValue(avgSimilarity / n);
#region Store average similarity values
if (results.ContainsKey(CurrentAverageSimilarityKey))
results[CurrentAverageSimilarityKey].Value = averageSimilarity;
else
results.Add(new Result(CurrentAverageSimilarityKey, averageSimilarity));
if (!results.ContainsKey(AverageSimilarityProgressKey))
results.Add(new Result(AverageSimilarityProgressKey, new Analysis.DataTable(AverageSimilarityProgressKey)));
Analysis.DataTable averageSimilarityProgressDataTable = (Analysis.DataTable)(results[AverageSimilarityProgressKey].Value);
if (averageSimilarityProgressDataTable.Rows.Count == 0)
averageSimilarityProgressDataTable.Rows.Add(new Analysis.DataRow(AverageSimilarityProgressKey));
averageSimilarityProgressDataTable.Rows[AverageSimilarityProgressKey].Values.Add(averageSimilarity.Value);
#endregion
#region Store average maximum similarity values
if (results.ContainsKey(CurrentAverageMaximumSimilarityKey))
results[CurrentAverageMaximumSimilarityKey].Value = averageMaximumSimilarity;
else
results.Add(new Result(CurrentAverageMaximumSimilarityKey, averageMaximumSimilarity));
if (!results.ContainsKey(AverageMaximumSimilarityProgressKey))
results.Add(new Result(AverageMaximumSimilarityProgressKey, new Analysis.DataTable(AverageMaximumSimilarityProgressKey)));
Analysis.DataTable averageMaximumSimilarityProgressDataTable = (Analysis.DataTable)(results[AverageMaximumSimilarityProgressKey].Value);
if (averageMaximumSimilarityProgressDataTable.Rows.Count == 0)
averageMaximumSimilarityProgressDataTable.Rows.Add(new Analysis.DataRow(AverageMaximumSimilarityProgressKey));
averageMaximumSimilarityProgressDataTable.Rows[AverageMaximumSimilarityProgressKey].Values.Add(averageMaximumSimilarity.Value);
#endregion
#region Store details
TSPPopulationDiversityAnalysisDetails details;
if (!results.ContainsKey(PopulationDiversityAnalysisResultsDetailsKey)) {
details = new TSPPopulationDiversityAnalysisDetails();
results.Add(new Result(PopulationDiversityAnalysisResultsDetailsKey, details));
} else {
details = (TSPPopulationDiversityAnalysisDetails)(results[PopulationDiversityAnalysisResultsDetailsKey].Value);
}
details.AverageSimilarities.Add(averageSimilarity);
details.AverageMaximumSimilarities.Add(averageMaximumSimilarity);
details.Similarities.Add(similarities);
details.MaximumSimilarities.Add(maxSimilarities);
if (!StoreCompleteHistoryParameter.Value.Value && details.Similarities.Count > 1) {
details.Similarities[details.Similarities.Count - 1] = null;
details.MaximumSimilarities[details.MaximumSimilarities.Count - 1] = null;
}
#endregion
return base.Apply();
}
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;
}
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 = 0; i < edgesA.Length; i++) {
if (edgesA[i] == edgesB[i] || edgesA[edgesB[i]] == i)
similarEdges++;
}
return (double)(similarEdges) / cities;
}
}
}