Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 12803 was 12799, checked in by apolidur, 9 years ago

#2221: Adding path Analyzers and some other fixes

File size: 7.5 KB
RevLine 
[12191]1using System.Text;
2using System.Threading.Tasks;
3using HeuristicLab.Optimization;
4using HeuristicLab.PluginInfrastructure;
5using HeuristicLab.Core;
6using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
7using HeuristicLab.Problems.Instances;
8using HeuristicLab.Encodings.PermutationEncoding;
9using HeuristicLab.Common;
10using HeuristicLab.Parameters;
11using HeuristicLab.Data;
[12261]12using HeuristicLab.Random;
[12191]13using System;
[12219]14using System.Linq;
[12191]15
16namespace HeuristicLab.Problems.PTSP {
17  [Item("Estimated Probabilistic Traveling Salesman Problem", "Represents an estimated Probabilistic Traveling Salesman Problem.")]
18  [Creatable("Problems")]
19  [StorableClass]
20  public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
[12306]21  IProblemInstanceConsumer<PTSPData> {
[12191]22
[12219]23
[12306]24    #region Parameter Properties
[12387]25    public ValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
26      get { return (ValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
[12306]27    }
[12387]28    public ValueParameter<IntValue> RealizationsSizeParameter {
29      get { return (ValueParameter<IntValue>)Parameters["RealizationsSize"]; }
30    }
31
[12306]32    #endregion
33
34    #region Properties
35    public ItemList<ItemList<IntValue>> Realizations {
36      get { return RealizationsParameter.Value; }
37      set { RealizationsParameter.Value = value; }
38    }
[12387]39
40    public IntValue RealizationsSize {
41      get { return RealizationsSizeParameter.Value; }
42      set { RealizationsSizeParameter.Value = value; }
43    }
[12306]44    #endregion
45
[12191]46    [StorableConstructor]
47    private EstimatedProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
48    private EstimatedProbabilisticTravelingSalesmanProblem(EstimatedProbabilisticTravelingSalesmanProblem original, Cloner cloner)
49      : base(original, cloner) {
[12387]50      RegisterEventHandlers();
[12191]51    }
[12387]52    public EstimatedProbabilisticTravelingSalesmanProblem() {
53      Parameters.Add(new ValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimation-based evaluation"));
54      Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
[12799]55
56      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
57      Operators.RemoveAll(x => x is IMoveGenerator);
58      Operators.RemoveAll(x => x is IMoveMaker);
59
60      Operators.Add(new BestPTSPSolutionAnalyzer());
61
[12387]62      Operators.Add(new PTSPEstimatedInversionEvaluator());
63      Operators.Add(new PTSPEstimatedInsertionEvaluator());
64      Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
65      Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());
[12191]66
[12387]67      Operators.Add(new Exhaustive25MoveGenerator());
68      Operators.Add(new Stochastic25MultiMoveGenerator());
69      Operators.Add(new Stochastic25SingleMoveGenerator());
70      Operators.Add(new TwoPointFiveMoveMaker());
71      Operators.Add(new PTSP25MoveEvaluator());
72
73      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
74      foreach (var twopointfiveMoveOperator in Operators.OfType<I25MoveOperator>()) {
75        twopointfiveMoveOperator.TwoPointFiveMoveParameter.ActualName = "Permutation.TwoPointFiveMove";
76      }
77      RealizationsSize = new IntValue(100);
78      RegisterEventHandlers();
79    }
80
[12191]81    public override IDeepCloneable Clone(Cloner cloner) {
82      return new EstimatedProbabilisticTravelingSalesmanProblem(this, cloner);
83    }
84
85    public override double Evaluate(Individual individual, IRandom random) {
86      Permutation p = individual.Permutation();
87      // Estimation-based evaluation
[12261]88      MersenneTwister r = new MersenneTwister();
[12191]89      double estimatedSum = 0;
[12306]90      for (int i = 0; i < Realizations.Count; i++) {
[12261]91        int singleRealization = -1, firstNode = -1;
[12306]92        for (int j = 0; j < Realizations[i].Count; j++) {
93          if (Realizations[i][p[j]].Value == 1) {
[12191]94            if (singleRealization != -1) {
95              estimatedSum += DistanceMatrix[singleRealization, p[j]];
[12261]96            } else {
97              firstNode = p[j];
[12191]98            }
99            singleRealization = p[j];
100          }
101        }
[12261]102        if (singleRealization != -1) {
103          estimatedSum += DistanceMatrix[singleRealization, firstNode];
104        }
[12191]105      }
[12306]106      return estimatedSum / RealizationsSize.Value;
[12191]107    }
108
[12261]109    public double[] EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, ItemList<ItemList<IntValue>> realizations, Permutation individual ) {
110      // Estimation-based evaluation
111      MersenneTwister r = new MersenneTwister();
112      double estimatedSum = 0;
113      double[] partialSums = new double[realizations.Count];
114      for (int i = 0; i < realizations.Count; i++) {
115        partialSums[i] = 0;
116        int singleRealization = -1, firstNode = -1;
117        for (int j = 0; j < realizations[i].Count; j++) {
118          if (realizations[i][individual[j]].Value == 1) {
119            if (singleRealization != -1) {
120              partialSums[i] += distances[singleRealization, individual[j]];
121            } else {
122              firstNode = individual[j];
123            }
124            singleRealization = individual[j];
125          }
126        }
127        if (singleRealization != -1) {
128          partialSums[i] += distances[singleRealization, firstNode];
129        }
130        estimatedSum += partialSums[i];
131      }
132      double mean = estimatedSum / realizations.Count;
133      double variance = 0;
134      for (int i = 0; i < realizations.Count; i++) {
135        variance += Math.Pow((partialSums[i] - mean), 2);
136      }
137      variance = variance / realizations.Count;
138      return new double[] {mean,variance};
139    }
140
[12387]141   
[12272]142
[12387]143    private void RegisterEventHandlers() {
144      //RealizationsSizeParameter.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
145      RealizationsSize.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
146      //RealizationsSizeParameter.Value.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
147    }
[12272]148
[12387]149    private void RealizationsSizeParameter_ValueChanged(object sender, EventArgs e) {
150      UpdateRealizations();
[12191]151    }
152
[12387]153    private void UpdateRealizations() {
[12261]154      MersenneTwister r = new MersenneTwister();
155      int countOnes = 0;
[12306]156      Realizations = new ItemList<ItemList<IntValue>>(RealizationsSize.Value);
157      for (int i = 0; i < RealizationsSize.Value; i++) {
[12261]158        ItemList<IntValue> newRealization = new ItemList<IntValue>();
159        while (countOnes < 4) { //only generate realizations with at least 4 cities visited
160          countOnes = 0;
161          newRealization.Clear();
[12387]162          for (int j = 0; j < DistanceMatrix.Rows; j++) {
[12261]163            if (ProbabilityMatrix[j] > r.NextDouble()) {
164              newRealization.Add(new IntValue(1));
165              countOnes++;
166            } else {
167              newRealization.Add(new IntValue(0));
168            }
[12219]169          }
170        }
[12261]171        countOnes = 0;
[12306]172        Realizations.Add(newRealization);
[12219]173      }
[12387]174    }
[12228]175
[12387]176    public override void Load(PTSPData data) {
177      base.Load(data);
178      UpdateRealizations();
179
[12380]180      foreach (var op in Operators.OfType<PTSPMoveEvaluator>()) {
[12306]181        op.RealizationsParameter.Value = Realizations;
[12219]182      }
[12228]183      foreach (var op in Operators.OfType<PTSPExhaustiveInversionLocalImprovement>()) {
[12306]184        op.RealizationsParameter.Value = Realizations;
[12228]185      }
[12272]186      foreach (var op in Operators.OfType<PTSP25MoveEvaluator>()) {
[12306]187        op.RealizationsParameter.Value = Realizations;
[12272]188      }
189
[12191]190    }
191  }
192}
Note: See TracBrowser for help on using the repository browser.