Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs @ 17260

Last change on this file since 17260 was 17260, checked in by abeham, 4 years ago

#2521: Worked on PTSP refactoring

File size: 8.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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.Collections.Generic;
24using System.Linq;
25using HEAL.Attic;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.PermutationEncoding;
30using HeuristicLab.Parameters;
31using HeuristicLab.Random;
32
33namespace HeuristicLab.Problems.PTSP {
34  [Item("Estimated Probabilistic TSP (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.")]
35  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
36  [StorableType("d1b4149b-8ab9-4314-8d96-9ea04a4d5b8b")]
37  public sealed class EstimatedPTSP : ProbabilisticTSP {
38
39    #region Parameter Properties
40    [Storable] public IFixedValueParameter<IntValue> RealizationsSeedParameter { get; private set; }
41    [Storable] public IFixedValueParameter<IntValue> RealizationsParameter { get; private set; }
42    [Storable] private IValueParameter<ReadOnlyItemList<BoolArray>> RealizationDataParameter { get; set; }
43    #endregion
44
45    #region Properties
46
47    public int RealizationsSeed {
48      get { return RealizationsSeedParameter.Value.Value; }
49      set { RealizationsSeedParameter.Value.Value = value; }
50    }
51
52    public int Realizations {
53      get { return RealizationsParameter.Value.Value; }
54      set { RealizationsParameter.Value.Value = value; }
55    }
56   
57    private ReadOnlyItemList<BoolArray> RealizationData {
58      get { return RealizationDataParameter.Value; }
59      set { RealizationDataParameter.Value = value; }
60    }
61    #endregion
62
63    [StorableConstructor]
64    private EstimatedPTSP(StorableConstructorFlag _) : base(_) { }
65    private EstimatedPTSP(EstimatedPTSP original, Cloner cloner)
66      : base(original, cloner) {
67      RealizationsSeedParameter = cloner.Clone(original.RealizationsSeedParameter);
68      RealizationsParameter = cloner.Clone(original.RealizationsParameter);
69      RealizationDataParameter = cloner.Clone(original.RealizationDataParameter);
70      RegisterEventHandlers();
71    }
72    public EstimatedPTSP() {
73      Parameters.Add(RealizationsSeedParameter = new FixedValueParameter<IntValue>("RealizationsSeed", "The starting seed of the RNG from which realizations should be drawn.", new IntValue(1)));
74      Parameters.Add(RealizationsParameter = new FixedValueParameter<IntValue>("Realizations", "The number of realizations that should be made.", new IntValue(100)));
75      Parameters.Add(RealizationDataParameter = new ValueParameter<ReadOnlyItemList<BoolArray>>("RealizationData", "The actual realizations.") { Hidden = true, GetsCollected = false });
76
77      Operators.Add(new PTSPEstimatedInversionMoveEvaluator());
78      Operators.Add(new PTSPEstimatedInsertionMoveEvaluator());
79      Operators.Add(new PTSPEstimatedInversionLocalImprovement());
80      Operators.Add(new PTSPEstimatedInsertionLocalImprovement());
81      Operators.Add(new PTSPEstimatedTwoPointFiveLocalImprovement());
82
83      Operators.Add(new ExhaustiveTwoPointFiveMoveGenerator());
84      Operators.Add(new StochasticTwoPointFiveMultiMoveGenerator());
85      Operators.Add(new StochasticTwoPointFiveSingleMoveGenerator());
86      Operators.Add(new TwoPointFiveMoveMaker());
87      Operators.Add(new PTSPEstimatedTwoPointFiveMoveEvaluator());
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 EstimatedPTSP(this, cloner);
100    }
101
102    public override double Evaluate(Permutation tour, IRandom random) {
103      return Evaluate(tour, ProbabilisticTSPData, RealizationData);
104    }
105
106    [StorableHook(HookType.AfterDeserialization)]
107    private void AfterDeserialization() {
108      RegisterEventHandlers();
109    }
110
111    public static double Evaluate(Permutation tour, IProbabilisticTSPData data, IEnumerable<BoolArray> realizations) {
112      // Estimation-based evaluation, here without calculating variance for faster evaluation
113      var estimatedSum = 0.0;
114      var count = 0;
115      foreach (var r in realizations) {
116        int singleRealization = -1, firstNode = -1;
117        for (var j = 0; j < data.Cities; j++) {
118          if (r[tour[j]]) {
119            if (singleRealization != -1) {
120              estimatedSum += data.GetDistance(singleRealization, tour[j]);
121            } else {
122              firstNode = tour[j];
123            }
124            singleRealization = tour[j];
125          }
126        }
127        if (singleRealization != -1)
128          estimatedSum += data.GetDistance(singleRealization, firstNode);
129        count++;
130      }
131      return estimatedSum / count;
132    }
133
134    /// <summary>
135    /// An evaluate method that can be used if mean as well as variance should be calculated
136    /// </summary>
137    /// <param name="tour">The tour between all cities.</param>
138    /// <param name="data">The main parameters of the pTSP.</param>
139    /// <param name="realizations">How many realizations to achieve.</param>
140    /// <param name="seed">The starting seed of generating the realizations.</param>
141    /// <param name="variance">The estimated variance will be returned in addition to the mean.</param>
142    /// <returns>A vector with length two containing mean and variance.</returns>
143    public static double Evaluate(Permutation tour, IProbabilisticTSPData data, IEnumerable<BoolArray> realizations, out double variance) {
144      // Estimation-based evaluation
145      var estimatedSum = 0.0;
146      var partialSums = new List<double>();
147      var count = 0;
148      foreach (var r in realizations) {
149        var pSum = 0.0;
150        int singleRealization = -1, firstNode = -1;
151        for (var j = 0; j < data.Cities; j++) {
152          if (r[tour[j]]) {
153            if (singleRealization != -1) {
154              pSum += data.GetDistance(singleRealization, tour[j]);
155            } else {
156              firstNode = tour[j];
157            }
158            singleRealization = tour[j];
159          }
160        }
161        if (singleRealization != -1) {
162          pSum += data.GetDistance(singleRealization, firstNode);
163        }
164        estimatedSum += pSum;
165        partialSums.Add(pSum);
166        count++;
167      }
168      var mean = estimatedSum / count;
169      variance = 0.0;
170      for (var i = 0; i < count; i++) {
171        variance += Math.Pow((partialSums[i] - mean), 2);
172      }
173      variance = variance / count;
174      return mean;
175    }
176
177    private void RegisterEventHandlers() {
178      RealizationsParameter.Value.ValueChanged += RealizationsOnChanged;
179      RealizationsSeedParameter.Value.ValueChanged += RealizationsSeedOnChanged;
180    }
181
182    private void RealizationsSeedOnChanged(object sender, EventArgs e) {
183      UpdateRealizations();
184    }
185
186    private void RealizationsOnChanged(object sender, EventArgs e) {
187      if (Realizations <= 0) Realizations = 1;
188      else UpdateRealizations();
189    }
190
191    private void UpdateRealizations() {
192      var data = new List<BoolArray>(Realizations);
193      var rng = new FastRandom(RealizationsSeed);
194      for (var i = 0; i < Realizations; i++) {
195        var cities = 0;
196        var r = new bool[ProbabilisticTSPData.Cities];
197        for (var j = 0; j < ProbabilisticTSPData.Cities; j++) {
198          if (rng.NextDouble() < ProbabilisticTSPData.GetProbability(j)) {
199            r[j] = true;
200            cities++;
201          }
202        }
203        if (cities > 0) {
204          data.Add(new BoolArray(r, @readonly: true));
205        }
206      }
207      RealizationData = (new ItemList<BoolArray>(data)).AsReadOnly();
208    }
209  }
210}
Note: See TracBrowser for help on using the repository browser.