source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs @ 13333

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;
using HeuristicLab.Random;
using System;
using System.Linq;

namespace HeuristicLab.Problems.PTSP {
  [Item("Estimated Probabilistic Traveling Salesman Problem", "Represents an estimated Probabilistic Traveling Salesman Problem.")]
  [Creatable("Problems")]
  [StorableClass]
  public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
  IProblemInstanceConsumer<PTSPData> {


    #region Parameter Properties
    public ValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
      get { return (ValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
    }
    public ValueParameter<IntValue> RealizationsSizeParameter {
      get { return (ValueParameter<IntValue>)Parameters["RealizationsSize"]; }
    }

    #endregion

    #region Properties
    public ItemList<ItemList<IntValue>> Realizations {
      get { return RealizationsParameter.Value; }
      set { RealizationsParameter.Value = value; }
    }

    public IntValue RealizationsSize {
      get { return RealizationsSizeParameter.Value; }
      set { RealizationsSizeParameter.Value = value; }
    }
    #endregion

    [StorableConstructor]
    private EstimatedProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
    private EstimatedProbabilisticTravelingSalesmanProblem(EstimatedProbabilisticTravelingSalesmanProblem original, Cloner cloner)
      : base(original, cloner) {
      RegisterEventHandlers();
    }
    public EstimatedProbabilisticTravelingSalesmanProblem() {
      Parameters.Add(new ValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimation-based evaluation"));
      Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));

      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
      Operators.RemoveAll(x => x is IMoveGenerator);
      Operators.RemoveAll(x => x is IMoveMaker);

      Operators.Add(new BestPTSPSolutionAnalyzer());

      Operators.Add(new PTSPEstimatedInversionEvaluator());
      Operators.Add(new PTSPEstimatedInsertionEvaluator());
      Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
      Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());

      Operators.Add(new Exhaustive25MoveGenerator());
      Operators.Add(new Stochastic25MultiMoveGenerator());
      Operators.Add(new Stochastic25SingleMoveGenerator());
      Operators.Add(new TwoPointFiveMoveMaker());
      Operators.Add(new PTSP25MoveEvaluator());

      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
      foreach (var twopointfiveMoveOperator in Operators.OfType<I25MoveOperator>()) {
        twopointfiveMoveOperator.TwoPointFiveMoveParameter.ActualName = "Permutation.TwoPointFiveMove";
      }
      RealizationsSize = new IntValue(100);
      RegisterEventHandlers();
    }

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

    public override double Evaluate(Individual individual, IRandom random) {
      Permutation p = individual.Permutation();
      // Estimation-based evaluation
      MersenneTwister r = new MersenneTwister();
      double estimatedSum = 0;
      for (int i = 0; i < Realizations.Count; i++) {
        int singleRealization = -1, firstNode = -1;
        for (int j = 0; j < Realizations[i].Count; j++) {
          if (Realizations[i][p[j]].Value == 1) {
            if (singleRealization != -1) {
              estimatedSum += DistanceMatrix[singleRealization, p[j]];
            } else {
              firstNode = p[j];
            }
            singleRealization = p[j];
          }
        }
        if (singleRealization != -1) {
          estimatedSum += DistanceMatrix[singleRealization, firstNode];
        }
      }
      return estimatedSum / RealizationsSize.Value;
    }

    public double[] EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, ItemList<ItemList<IntValue>> realizations, Permutation individual ) {
      // Estimation-based evaluation
      MersenneTwister r = new MersenneTwister();
      double estimatedSum = 0;
      double[] partialSums = new double[realizations.Count];
      for (int i = 0; i < realizations.Count; i++) {
        partialSums[i] = 0;
        int singleRealization = -1, firstNode = -1;
        for (int j = 0; j < realizations[i].Count; j++) {
          if (realizations[i][individual[j]].Value == 1) {
            if (singleRealization != -1) {
              partialSums[i] += distances[singleRealization, individual[j]];
            } else {
              firstNode = individual[j];
            }
            singleRealization = individual[j];
          }
        }
        if (singleRealization != -1) {
          partialSums[i] += distances[singleRealization, firstNode];
        }
        estimatedSum += partialSums[i];
      }
      double mean = estimatedSum / realizations.Count;
      double variance = 0;
      for (int i = 0; i < realizations.Count; i++) {
        variance += Math.Pow((partialSums[i] - mean), 2);
      }
      variance = variance / realizations.Count;
      return new double[] {mean,variance};
    }

    

    private void RegisterEventHandlers() {
      //RealizationsSizeParameter.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
      RealizationsSize.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
      //RealizationsSizeParameter.Value.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
    }

    private void RealizationsSizeParameter_ValueChanged(object sender, EventArgs e) {
      UpdateRealizations();
    }

    private void UpdateRealizations() {
      MersenneTwister r = new MersenneTwister();
      int countOnes = 0;
      Realizations = new ItemList<ItemList<IntValue>>(RealizationsSize.Value);
      for (int i = 0; i < RealizationsSize.Value; i++) {
        ItemList<IntValue> newRealization = new ItemList<IntValue>();
        while (countOnes < 4) { //only generate realizations with at least 4 cities visited
          countOnes = 0;
          newRealization.Clear();
          for (int j = 0; j < DistanceMatrix.Rows; j++) {
            if (ProbabilityMatrix[j] > r.NextDouble()) {
              newRealization.Add(new IntValue(1));
              countOnes++;
            } else {
              newRealization.Add(new IntValue(0));
            }
          }
        }
        countOnes = 0;
        Realizations.Add(newRealization);
      }
    }

    public override void Load(PTSPData data) {
      base.Load(data);
      UpdateRealizations();

      foreach (var op in Operators.OfType<PTSPMoveEvaluator>()) {
        op.RealizationsParameter.Value = Realizations;
      }
      foreach (var op in Operators.OfType<PTSPExhaustiveInversionLocalImprovement>()) {
        op.RealizationsParameter.Value = Realizations;
      }
      foreach (var op in Operators.OfType<PTSP25MoveEvaluator>()) {
        op.RealizationsParameter.Value = Realizations;
      }

    }
  }
}