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

#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 <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Linq;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.TravelingSalesman {
  /// <summary>
  /// An operator for analyzing the diversity of a population of solutions for a Traveling Salesman Problems given in path representation using city coordinates.
  /// </summary>
  [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

    public ScopeTreeLookupParameter<Permutation> PermutationParameter {
      get { return (ScopeTreeLookupParameter<Permutation>)Parameters["Permutation"]; }
    }
    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
    }
    public ValueParameter<BoolValue> StoreCompleteHistoryParameter {
      get { return (ValueParameter<BoolValue>)Parameters["StoreCompleteHistory"]; }
    }
    public ValueParameter<ItemList<DoubleMatrix>> SimilaritiesParameter {
      get { return (ValueParameter<ItemList<DoubleMatrix>>)Parameters["Similarities"]; }
    }
    public ValueParameter<ItemList<DoubleArray>> MaximumSimilaritiesParameter {
      get { return (ValueParameter<ItemList<DoubleArray>>)Parameters["MaximumSimilarities"]; }
    }
    public ValueParameter<ItemList<DoubleValue>> AverageMaximumSimilaritiesParameter {
      get { return (ValueParameter<ItemList<DoubleValue>>)Parameters["AverageMaximumSimilarities"]; }
    }
    public ValueParameter<ItemList<DoubleValue>> AverageSimilaritiesParameter {
      get { return (ValueParameter<ItemList<DoubleValue>>)Parameters["AverageSimilarities"]; }
    }

    public TSPPopulationDiversityAnalyzer()
      : base() {
      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 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;
      ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
      Permutation[] permutationsArray = permutations.ToArray();
      DoubleValue[] qualitiesArray = qualities.ToArray();
      int cities = permutationsArray.Length;
      #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);

      if (SimilaritiesParameter.Value == null) {
        SimilaritiesParameter.Value = new ItemList<DoubleMatrix>();
        MaximumSimilaritiesParameter.Value = new ItemList<DoubleArray>();
        AverageMaximumSimilaritiesParameter.Value = new ItemList<DoubleValue>();
        AverageSimilaritiesParameter.Value = new ItemList<DoubleValue>();
      }
      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 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;
    }

  }
}