Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2221: Adding path Analyzers and some other fixes

File size: 7.5 KB
Line 
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;
12using HeuristicLab.Random;
13using System;
14using System.Linq;
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,
21  IProblemInstanceConsumer<PTSPData> {
22
23
24    #region Parameter Properties
25    public ValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
26      get { return (ValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
27    }
28    public ValueParameter<IntValue> RealizationsSizeParameter {
29      get { return (ValueParameter<IntValue>)Parameters["RealizationsSize"]; }
30    }
31
32    #endregion
33
34    #region Properties
35    public ItemList<ItemList<IntValue>> Realizations {
36      get { return RealizationsParameter.Value; }
37      set { RealizationsParameter.Value = value; }
38    }
39
40    public IntValue RealizationsSize {
41      get { return RealizationsSizeParameter.Value; }
42      set { RealizationsSizeParameter.Value = value; }
43    }
44    #endregion
45
46    [StorableConstructor]
47    private EstimatedProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
48    private EstimatedProbabilisticTravelingSalesmanProblem(EstimatedProbabilisticTravelingSalesmanProblem original, Cloner cloner)
49      : base(original, cloner) {
50      RegisterEventHandlers();
51    }
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..."));
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
62      Operators.Add(new PTSPEstimatedInversionEvaluator());
63      Operators.Add(new PTSPEstimatedInsertionEvaluator());
64      Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
65      Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());
66
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
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
88      MersenneTwister r = new MersenneTwister();
89      double estimatedSum = 0;
90      for (int i = 0; i < Realizations.Count; i++) {
91        int singleRealization = -1, firstNode = -1;
92        for (int j = 0; j < Realizations[i].Count; j++) {
93          if (Realizations[i][p[j]].Value == 1) {
94            if (singleRealization != -1) {
95              estimatedSum += DistanceMatrix[singleRealization, p[j]];
96            } else {
97              firstNode = p[j];
98            }
99            singleRealization = p[j];
100          }
101        }
102        if (singleRealization != -1) {
103          estimatedSum += DistanceMatrix[singleRealization, firstNode];
104        }
105      }
106      return estimatedSum / RealizationsSize.Value;
107    }
108
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
141   
142
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    }
148
149    private void RealizationsSizeParameter_ValueChanged(object sender, EventArgs e) {
150      UpdateRealizations();
151    }
152
153    private void UpdateRealizations() {
154      MersenneTwister r = new MersenneTwister();
155      int countOnes = 0;
156      Realizations = new ItemList<ItemList<IntValue>>(RealizationsSize.Value);
157      for (int i = 0; i < RealizationsSize.Value; i++) {
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();
162          for (int j = 0; j < DistanceMatrix.Rows; j++) {
163            if (ProbabilityMatrix[j] > r.NextDouble()) {
164              newRealization.Add(new IntValue(1));
165              countOnes++;
166            } else {
167              newRealization.Add(new IntValue(0));
168            }
169          }
170        }
171        countOnes = 0;
172        Realizations.Add(newRealization);
173      }
174    }
175
176    public override void Load(PTSPData data) {
177      base.Load(data);
178      UpdateRealizations();
179
180      foreach (var op in Operators.OfType<PTSPMoveEvaluator>()) {
181        op.RealizationsParameter.Value = Realizations;
182      }
183      foreach (var op in Operators.OfType<PTSPExhaustiveInversionLocalImprovement>()) {
184        op.RealizationsParameter.Value = Realizations;
185      }
186      foreach (var op in Operators.OfType<PTSP25MoveEvaluator>()) {
187        op.RealizationsParameter.Value = Realizations;
188      }
189
190    }
191  }
192}
Note: See TracBrowser for help on using the repository browser.