Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs @ 16178

Last change on this file since 16178 was 15584, checked in by swagner, 7 years ago

#2640: Updated year of copyrights in license headers on stable

File size: 9.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.PermutationEncoding;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Problems.Instances;
32using HeuristicLab.Random;
33
34namespace HeuristicLab.Problems.PTSP {
35  [Item("Estimated Probabilistic Traveling Salesman Problem (PTSP)", "Represents a probabilistic traveling salesman problem where the expected tour length is estimated by averaging over the length of tours on a number of, so called, realizations.")]
36  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
37  [StorableClass]
38  public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem {
39
40    #region Parameter Properties
41    public IValueParameter<ItemList<BoolArray>> RealizationsParameter {
42      get { return (IValueParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
43    }
44    public IFixedValueParameter<IntValue> RealizationsSizeParameter {
45      get { return (IFixedValueParameter<IntValue>)Parameters["RealizationsSize"]; }
46    }
47    #endregion
48
49    #region Properties
50    public ItemList<BoolArray> Realizations {
51      get { return RealizationsParameter.Value; }
52      set { RealizationsParameter.Value = value; }
53    }
54
55    public int RealizationsSize {
56      get { return RealizationsSizeParameter.Value.Value; }
57      set { RealizationsSizeParameter.Value.Value = value; }
58    }
59    #endregion
60
61    [StorableConstructor]
62    private EstimatedProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
63    private EstimatedProbabilisticTravelingSalesmanProblem(EstimatedProbabilisticTravelingSalesmanProblem original, Cloner cloner)
64      : base(original, cloner) {
65      RegisterEventHandlers();
66    }
67    public EstimatedProbabilisticTravelingSalesmanProblem() {
68      Parameters.Add(new FixedValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimation-based evaluation", new IntValue(100)));
69      Parameters.Add(new ValueParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances.", new ItemList<BoolArray>()));
70
71      Operators.Add(new BestPTSPSolutionAnalyzer());
72
73      Operators.Add(new PTSPEstimatedInversionMoveEvaluator());
74      Operators.Add(new PTSPEstimatedInsertionMoveEvaluator());
75      Operators.Add(new PTSPEstimatedInversionLocalImprovement());
76      Operators.Add(new PTSPEstimatedInsertionLocalImprovement());
77      Operators.Add(new PTSPEstimatedTwoPointFiveLocalImprovement());
78
79      Operators.Add(new ExhaustiveTwoPointFiveMoveGenerator());
80      Operators.Add(new StochasticTwoPointFiveMultiMoveGenerator());
81      Operators.Add(new StochasticTwoPointFiveSingleMoveGenerator());
82      Operators.Add(new TwoPointFiveMoveMaker());
83      Operators.Add(new PTSPEstimatedTwoPointFiveMoveEvaluator());
84
85      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
86      Operators.RemoveAll(x => x is SingleObjectiveMoveMaker);
87      Operators.RemoveAll(x => x is SingleObjectiveMoveEvaluator);
88
89      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
90      foreach (var twopointfiveMoveOperator in Operators.OfType<ITwoPointFiveMoveOperator>()) {
91        twopointfiveMoveOperator.TwoPointFiveMoveParameter.ActualName = "Permutation.TwoPointFiveMove";
92      }
93
94      UpdateRealizations();
95      RegisterEventHandlers();
96    }
97
98    public override IDeepCloneable Clone(Cloner cloner) {
99      return new EstimatedProbabilisticTravelingSalesmanProblem(this, cloner);
100    }
101
102    [StorableHook(HookType.AfterDeserialization)]
103    private void AfterDeserialization() {
104      RegisterEventHandlers();
105    }
106
107    private void RegisterEventHandlers() {
108      RealizationsSizeParameter.Value.ValueChanged += RealizationsSizeParameter_ValueChanged;
109    }
110
111    private void RealizationsSizeParameter_ValueChanged(object sender, EventArgs e) {
112      UpdateRealizations();
113    }
114
115    public override double Evaluate(Permutation tour, IRandom random) {
116      // abeham: Cache parameters in local variables for performance reasons
117      var realizations = Realizations;
118      var realizationsSize = RealizationsSize;
119      var useDistanceMatrix = UseDistanceMatrix;
120      var distanceMatrix = DistanceMatrix;
121      var distanceCalculator = DistanceCalculator;
122      var coordinates = Coordinates;
123
124      // Estimation-based evaluation, here without calculating variance for faster evaluation
125      var estimatedSum = 0.0;
126      for (var i = 0; i < realizations.Count; i++) {
127        int singleRealization = -1, firstNode = -1;
128        for (var j = 0; j < realizations[i].Length; j++) {
129          if (realizations[i][tour[j]]) {
130            if (singleRealization != -1) {
131              estimatedSum += useDistanceMatrix ? distanceMatrix[singleRealization, tour[j]] : distanceCalculator.Calculate(singleRealization, tour[j], coordinates);
132            } else {
133              firstNode = tour[j];
134            }
135            singleRealization = tour[j];
136          }
137        }
138        if (singleRealization != -1) {
139          estimatedSum += useDistanceMatrix ? distanceMatrix[singleRealization, firstNode] : distanceCalculator.Calculate(singleRealization, firstNode, coordinates);
140        }
141      }
142      return estimatedSum / realizationsSize;
143    }
144
145    /// <summary>
146    /// An evaluate method that can be used if mean as well as variance should be calculated
147    /// </summary>
148    /// <param name="tour">The tour between all cities.</param>
149    /// <param name="distanceMatrix">The distances between the cities.</param>
150    /// <param name="realizations">A sample of realizations of the stochastic instance</param>
151    /// <param name="variance">The estimated variance will be returned in addition to the mean.</param>
152    /// <returns>A vector with length two containing mean and variance.</returns>
153    public static double Evaluate(Permutation tour, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations, out double variance) {
154      return Evaluate(tour, (a, b) => distanceMatrix[a, b], realizations, out variance);
155    }
156
157    /// <summary>
158    /// An evaluate method that can be used if mean as well as variance should be calculated
159    /// </summary>
160    /// <param name="tour">The tour between all cities.</param>
161    /// <param name="distance">A func that accepts the index of two cities and returns the distance as a double.</param>
162    /// <param name="realizations">A sample of realizations of the stochastic instance</param>
163    /// <param name="variance">The estimated variance will be returned in addition to the mean.</param>
164    /// <returns>A vector with length two containing mean and variance.</returns>
165    public static double Evaluate(Permutation tour, Func<int, int, double> distance, ItemList<BoolArray> realizations, out double variance) {
166      // Estimation-based evaluation
167      var estimatedSum = 0.0;
168      var partialSums = new double[realizations.Count];
169      for (var i = 0; i < realizations.Count; i++) {
170        partialSums[i] = 0;
171        int singleRealization = -1, firstNode = -1;
172        for (var j = 0; j < realizations[i].Length; j++) {
173          if (realizations[i][tour[j]]) {
174            if (singleRealization != -1) {
175              partialSums[i] += distance(singleRealization, tour[j]);
176            } else {
177              firstNode = tour[j];
178            }
179            singleRealization = tour[j];
180          }
181        }
182        if (singleRealization != -1) {
183          partialSums[i] += distance(singleRealization, firstNode);
184        }
185        estimatedSum += partialSums[i];
186      }
187      var mean = estimatedSum / realizations.Count;
188      variance = 0.0;
189      for (var i = 0; i < realizations.Count; i++) {
190        variance += Math.Pow((partialSums[i] - mean), 2);
191      }
192      variance = variance / realizations.Count;
193      return mean;
194    }
195
196    public override void Load(PTSPData data) {
197      base.Load(data);
198      UpdateRealizations();
199
200      foreach (var op in Operators.OfType<IEstimatedPTSPOperator>()) {
201        op.RealizationsParameter.ActualName = RealizationsParameter.Name;
202      }
203    }
204
205    private void UpdateRealizations() {
206      var realizations = new ItemList<BoolArray>(RealizationsSize);
207      var rand = new MersenneTwister();
208      for (var i = 0; i < RealizationsSize; i++) {
209        var newRealization = new BoolArray(Probabilities.Length);
210        var countOnes = 0;
211        do {
212          countOnes = 0;
213          for (var j = 0; j < Probabilities.Length; j++) {
214            newRealization[j] = Probabilities[j] < rand.NextDouble();
215            if (newRealization[j]) countOnes++;
216          }
217          // only generate realizations with at least 4 cities visited
218        } while (countOnes < 4 && Probabilities.Length > 3);
219        realizations.Add(newRealization);
220      }
221      Realizations = realizations;
222    }
223  }
224}
Note: See TracBrowser for help on using the repository browser.