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

#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
    // - decide whether old results shall be stored or disposed
    // - view
    // - check results for identical solutions

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

    [NonSerialized]
    private int[] rxData, ryData;
    [NonSerialized]
    private Permutation lastX, lastY;

    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 LookupParameter<ItemList<DoubleMatrix>>("Similarities", "The similarities of the TSP solutions which should be analyzed."));
      Parameters.Add(new LookupParameter<ItemList<DoubleArray>>("MaximumSimilarities", "The maximum similarities of the TSP solutions which should be analyzed."));
      Parameters.Add(new LookupParameter<ItemList<DoubleValue>>("AverageMaximumSimilarities", "The average maximum similarities of the TSP solutions which should be analyzed."));
      Parameters.Add(new LookupParameter<ItemList<DoubleValue>>("AverageSimilarities", "The average similarities of the TSP solutions which should be analyzed."));
      rxData = null;
      ryData = null;
      lastX = null;
      lastY = null;
    }

    public override IOperation Apply() {

      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

      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++) {
        for (int j = (i); j < cities; j++) {
          double similarity = CalculateSimilarity(permutationsArray[i], permutationsArray[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.ActualValue == null) {
        SimilaritiesParameter.ActualValue = new ItemList<DoubleMatrix>();
        MaximumSimilaritiesParameter.ActualValue = new ItemList<DoubleArray>();
        AverageMaximumSimilaritiesParameter.ActualValue = new ItemList<DoubleValue>();
        AverageSimilaritiesParameter.ActualValue = new ItemList<DoubleValue>();
      }
      SimilaritiesParameter.ActualValue.Add(similarities);
      MaximumSimilaritiesParameter.ActualValue.Add(maxSimilarities);
      AverageMaximumSimilaritiesParameter.ActualValue.Add(averageMaximumSimilarity);
      AverageSimilaritiesParameter.ActualValue.Add(averageSimilarity);

      return base.Apply();
    }

    private double CalculateSimilarity(Permutation x, Permutation y) {

      int cities = x.Length;
      if (rxData == null || rxData.Length != cities) {
        rxData = new int[cities];
        ryData = new int[cities];
      }

      if (x.Length != y.Length) throw new InvalidOperationException("ERROR in " + Name + ": Similarity can only be calculated between instances of an equal number of cities");
      #region Performance savings when calling the function with at least one parameter identical to the last call
      if (x == lastX) { // if Solution1 stayed the same
        if (y != lastY) { // and Solution2 changed
          for (int i = 0; i < y.Length; i++)
            ryData[y[i]] = i;
        }
      } else {
        if (y == lastX && x == lastY) { // if Solution1 and Solution2 were reversed the call before
          int[] h = ryData;
          ryData = rxData;
          rxData = h;
        } else if (y == lastX) { // or if just Solution1 is different now
          ryData = rxData;
          rxData = new int[x.Length];
          for (int i = 0; i < x.Length; i++)
            rxData[x[i]] = i;
        } else if (x == lastY) { // or just Solution2 is different now
          rxData = ryData;
          ryData = new int[y.Length];
          for (int i = 0; i < y.Length; i++)
            ryData[y[i]] = i;
        } else if (y != lastY) { // or none are the same
          for (int i = 0; i < x.Length; i++) {
            rxData[x[i]] = i;
            ryData[y[i]] = i;
          }
        } else { // or just Solution2 is the same
          for (int i = 0; i < x.Length; i++)
            rxData[x[i]] = i;
        }
      }
      lastX = x;
      lastY = y;
      #endregion
      int similarEdges = 0;
      for (int i = 1; i <= x.Length; i++) {
        if (Math.Abs(ryData[x[(i < x.Length) ? (i) : (0)]] - ryData[x[i - 1]]) == 1
          || Math.Abs(ryData[x[(i < x.Length) ? (i) : (0)]] - ryData[x[i - 1]]) == x.Length)
          similarEdges++;
      }
      return (double)similarEdges / (double)x.Length;

    }

  }
}