source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs @ 12183

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2015 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.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using HeuristicLab.Optimization;
using HeuristicLab.PluginInfrastructure;
using HeuristicLab.Core;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.Instances;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Common;
using HeuristicLab.Parameters;
using HeuristicLab.Data;

namespace HeuristicLab.Problems.PTSP {
  [Item("Probabilistic Traveling Salesman Problem", "Represents a Probabilistic Traveling Salesman Problem.")]
  [Creatable("Problems")]
  [StorableClass]
  public sealed class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
  IProblemInstanceConsumer<TSPData> {
    #region Parameter Properties
    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
    }
    public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
    }
    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
    }
    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
    }
    public ValueParameter<BoolValue> UseAnalyticalEvaluationParameter {
      get { return (ValueParameter<BoolValue>)Parameters["UseAnalyticalEvaluation"]; }
    }
    public OptionalValueParameter<DistanceMatrix> ProbabilityMatrixParameter {
      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["ProbabilityMatrix"]; }
    }
    public ValueParameter<IntValue> SampleSizeParameter {
      get { return (ValueParameter<IntValue>)Parameters["SampleSize"]; }
    }

    #endregion

    #region Properties
    public DoubleMatrix Coordinates {
      get { return CoordinatesParameter.Value; }
      set { CoordinatesParameter.Value = value; }
    }
    public DistanceMatrix DistanceMatrix {
      get { return DistanceMatrixParameter.Value; }
      set { DistanceMatrixParameter.Value = value; }
    }
    public BoolValue UseDistanceMatrix {
      get { return UseDistanceMatrixParameter.Value; }
      set { UseDistanceMatrixParameter.Value = value; }
    }
    public Permutation BestKnownSolution {
      get { return BestKnownSolutionParameter.Value; }
      set { BestKnownSolutionParameter.Value = value; }
    }
    public BoolValue UseAnalyticalEvaluation {
      get { return UseAnalyticalEvaluationParameter.Value; }
      set { UseAnalyticalEvaluationParameter.Value = value; }
    }
    public DistanceMatrix ProbabilityMatrix {
      get { return ProbabilityMatrixParameter.Value; }
      set { ProbabilityMatrixParameter.Value = value; }
    }
    public IntValue SampleSize {
      get { return SampleSizeParameter.Value; }
      set { SampleSizeParameter.Value = value; }
    }
    #endregion
    public override double Evaluate(Individual individual, IRandom random) {
      Permutation p = individual.Permutation();
      if (UseAnalyticalEvaluation.Value) {
        // Analytical evaluation
        double firstSum = 0;
        for (int i = 0; i < p.Length - 1; i++) {
          for (int j = i + 1; j < p.Length - 1; j++) {
            double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[j]];
            for (int k = i + 1; k < j; k++) {
              sum1 = sum1 * (1 - ProbabilityMatrix[0, p[k]]);
            }
            firstSum += sum1;
          }
        }
        double secondSum = 0;
        for (int j = 0; j < p.Length - 1; j++) {
          for (int i = 0; i < j; i++) {
            double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[j]];
            for (int k = j + 1; k < p.Length - 1; k++) {
              sum2 = sum2 * (1 - ProbabilityMatrix[0, p[k]]);
            }
            for (int k = 1; k < i; k++) {
              sum2 = sum2 * (1 - ProbabilityMatrix[0, p[k]]);
            }
            secondSum += sum2;
          }
        }
        return firstSum+secondSum;
      } else {
        // Estimation-based evaluation
        Random r = new Random();
        double estimatedSum = 0;
        for (int i = 0; i < SampleSize.Value; i++) {
          int singleRealization = -1;
          for (int j = 0; j < p.Length - 1; j++) {
            if (ProbabilityMatrix[0, p[j]] > r.NextDouble()) {
              if (singleRealization != -1) {
                estimatedSum += DistanceMatrix[singleRealization, p[j]];
              }
              singleRealization = p[j];
            }
          }
        }
        return estimatedSum / SampleSize.Value;
      }
    }

    public override bool Maximization {
      get { return false; }
    }

    [StorableConstructor]
    private ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
    private ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
      : base(original, cloner) {
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new ProbabilisticTravelingSalesmanProblem(this, cloner);
    }
    public ProbabilisticTravelingSalesmanProblem() {
      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
      Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if the coordinates based evaluators should calculate the distance matrix from the coordinates and use it for evaluation similar to the distance matrix evaluator, otherwise false.", new BoolValue(true)));
      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
      Parameters.Add(new ValueParameter<BoolValue>("UseAnalyticalEvaluation", "Check to use analytical evaluation, uncheck to use estimation-based approach."));
      Parameters.Add(new OptionalValueParameter<DistanceMatrix>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "Size of the sample for the estimation-based evaluation"));
    }

    public void Load(TSPData data) {
      SampleSize = new IntValue(20);
      DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
      // Get Probabilities of cities using random with seed from hash function on the Name of the instance
      ProbabilityMatrix = new DistanceMatrix(1, data.Dimension);
      Random r = new Random(data.Name.GetHashCode());
      for (int i = 0; i < data.Dimension; i++) {
        ProbabilityMatrix[0,i] = r.NextDouble();
      }
      Encoding.Length = data.Dimension;
    }
  }
}