source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/AnalyticalPTSP.cs @ 12803

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("Analytical Probabilistic Traveling Salesman Problem", "Represents an analytical Probabilistic Traveling Salesman Problem.")]
  [Creatable("Problems")]
  [StorableClass]
  public sealed class AnalyticalProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
  IProblemInstanceConsumer<PTSPData> {

    [StorableConstructor]
    private AnalyticalProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
    private AnalyticalProbabilisticTravelingSalesmanProblem(AnalyticalProbabilisticTravelingSalesmanProblem original, Cloner cloner)
      : base(original, cloner) {
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new AnalyticalProbabilisticTravelingSalesmanProblem(this, cloner);
    }

    public override double Evaluate(Individual individual, IRandom random) {
      Permutation p = individual.Permutation();
      // Compute A and B matrices
      DoubleMatrix A = new DoubleMatrix(p.Length, p.Length - 1);
      DoubleMatrix B = new DoubleMatrix(p.Length, p.Length - 1);
      //for (int i = 0; i < p.Length; i++) {
      //  for (int k = 0; k < p.Length - 1; k++) {
      //    double firstPartial = 0;
      //    for (int r = k; k < p.Length - 1; r++) {
      //       double sum0 = DistanceMatrix[p[i],p[i+r]]* ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[i+r]];
      //       for(int s = i+1; s < i+r; s++) {
      //         sum0 = sum0 * (1 - ProbabilityMatrix[0, p[s]]);
      //       }
      //       firstPartial+=sum0;
      //    }
      //    double secondPartial = 0;
      //    for (int r = k; k < p.Length - 1; r++) {
      //       double sum1 = DistanceMatrix[p[i-r],p[i]]* ProbabilityMatrix[0, p[i-r]] * ProbabilityMatrix[0, p[i]];
      //       for (int s = i + 1; s < p.Length-1; s++) {
      //         sum1 = sum1 * (1 - ProbabilityMatrix[0, p[s]]);
      //       }
      //       for (int t = 1; t < i-1; t++) {
      //         sum1 = sum1 * (1 - ProbabilityMatrix[0, p[t]]);
      //       }
      //       secondPartial+=sum1;
      //    }
      //    A[i, k] = firstPartial;
      //    B[i, k] = secondPartial;
      //  }
      //}
      
      // 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[p[i]] * ProbabilityMatrix[p[j]];
          for (int k = i + 1; k < j; k++) {
            sum1 = sum1 * (1 - ProbabilityMatrix[p[k]]);
          }
          A[i, j - 1] = sum1;
          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[p[i]] * ProbabilityMatrix[p[j]];
          for (int k = j + 1; k < p.Length - 1; k++) {
            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]);
          }
          for (int k = 1; k < i; k++) {
            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]);
          }
          B[i, j] = sum2;
          secondSum += sum2;
        }
      }
      foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
        op.AParameter.Value = A;
        op.BParameter.Value = B;
      }
      return firstSum + secondSum;
    }

    public double EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, Permutation individual) {
      Permutation p = individual;
      // Compute A and B matrices
      DoubleMatrix A = new DoubleMatrix(p.Length, p.Length - 1);
      DoubleMatrix B = new DoubleMatrix(p.Length, p.Length - 1);
      // Analytical evaluation
      double firstSum = 0;
      for (int i = 0; i < p.Length; i++) {
        for (int j = i + 1; j < p.Length; j++) {
          double sum1 = distances[p[i], p[j]] * probabilities[p[i]] * probabilities[p[j]];
          for (int k = i + 1; k < j; k++) {
            sum1 = sum1 * (1 - probabilities[p[k]]);
          }
          A[i, j - 1] = sum1;
          firstSum += sum1;
        }
      }
      double secondSum = 0;
      for (int j = 0; j < p.Length; j++) {
        for (int i = 0; i < j; i++) {
          double sum2 = distances[p[j], p[i]] * probabilities[p[i]] * probabilities[p[j]];
          for (int k = j + 1; k < p.Length; k++) {
            sum2 = sum2 * (1 - probabilities[p[k]]);
          }
          for (int k = 0; k < i; k++) {
            sum2 = sum2 * (1 - probabilities[p[k]]);
          }
          B[j,i] = sum2;
          secondSum += sum2;
        }
      }
      foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
        op.AParameter.Value = A;
        op.BParameter.Value = B;
      }
      return firstSum + secondSum;
    }

    public AnalyticalProbabilisticTravelingSalesmanProblem() {
      Operators.Add(new PTSPAnalyticalInversionMovePathEvaluator());
    }

    public override void Load(PTSPData data) {
      base.Load(data);
      foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
        op.ProbabilitiesParameter.Value = ProbabilityMatrix;
      }
    }

  }
}