1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022015 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 


22  using System;


23  using System.Linq;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Data;


27  using HeuristicLab.Encodings.PermutationEncoding;


28  using HeuristicLab.Parameters;


29  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


30  using HeuristicLab.Problems.Instances;


31  using HeuristicLab.Random;


32 


33  namespace HeuristicLab.Problems.PTSP {


34  [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.")]


35  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]


36  [StorableClass]


37  public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem {


38 


39  #region Parameter Properties


40  public IValueParameter<ItemList<BoolArray>> RealizationsParameter {


41  get { return (IValueParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }


42  }


43  public IFixedValueParameter<IntValue> RealizationsSizeParameter {


44  get { return (IFixedValueParameter<IntValue>)Parameters["RealizationsSize"]; }


45  }


46  #endregion


47 


48  #region Properties


49  public ItemList<BoolArray> Realizations {


50  get { return RealizationsParameter.Value; }


51  set { RealizationsParameter.Value = value; }


52  }


53 


54  public int RealizationsSize {


55  get { return RealizationsSizeParameter.Value.Value; }


56  set { RealizationsSizeParameter.Value.Value = value; }


57  }


58  #endregion


59 


60  [StorableConstructor]


61  private EstimatedProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }


62  private EstimatedProbabilisticTravelingSalesmanProblem(EstimatedProbabilisticTravelingSalesmanProblem original, Cloner cloner)


63  : base(original, cloner) {


64  RegisterEventHandlers();


65  }


66  public EstimatedProbabilisticTravelingSalesmanProblem() {


67  Parameters.Add(new FixedValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimationbased evaluation", new IntValue(100)));


68  Parameters.Add(new ValueParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances.", new ItemList<BoolArray>()));


69 


70  Operators.Add(new BestPTSPSolutionAnalyzer());


71 


72  Operators.Add(new PTSPEstimatedInversionMoveEvaluator());


73  Operators.Add(new PTSPEstimatedInsertionMoveEvaluator());


74  Operators.Add(new PTSPExhaustiveInversionLocalImprovement());


75  Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());


76 


77  Operators.Add(new ExhaustiveTwoPointFiveMoveGenerator());


78  Operators.Add(new StochasticTwoPointFiveMultiMoveGenerator());


79  Operators.Add(new StochasticTwoPointFiveSingleMoveGenerator());


80  Operators.Add(new TwoPointFiveMoveMaker());


81  Operators.Add(new PTSPTwoPointFiveMoveEvaluator());


82 


83  Encoding.ConfigureOperators(Operators.OfType<IOperator>());


84  foreach (var twopointfiveMoveOperator in Operators.OfType<ITwoPointFiveMoveOperator>()) {


85  twopointfiveMoveOperator.TwoPointFiveMoveParameter.ActualName = "Permutation.TwoPointFiveMove";


86  }


87 


88  RegisterEventHandlers();


89  }


90 


91  public override IDeepCloneable Clone(Cloner cloner) {


92  return new EstimatedProbabilisticTravelingSalesmanProblem(this, cloner);


93  }


94 


95  [StorableHook(HookType.AfterDeserialization)]


96  private void AfterDeserialization() {


97  RegisterEventHandlers();


98  }


99 


100  private void RegisterEventHandlers() {


101  RealizationsSizeParameter.Value.ValueChanged += RealizationsSizeParameter_ValueChanged;


102  }


103 


104  private void RealizationsSizeParameter_ValueChanged(object sender, EventArgs e) {


105  UpdateRealizations();


106  }


107 


108  public override double Evaluate(Permutation tour, IRandom random) {


109  // Estimationbased evaluation


110  var estimatedSum = 0.0;


111  for (var i = 0; i < Realizations.Count; i++) {


112  int singleRealization = 1, firstNode = 1;


113  for (var j = 0; j < Realizations[i].Length; j++) {


114  if (Realizations[i][tour[j]]) {


115  if (singleRealization != 1) {


116  estimatedSum += GetDistance(singleRealization, tour[j]);


117  } else {


118  firstNode = tour[j];


119  }


120  singleRealization = tour[j];


121  }


122  }


123  if (singleRealization != 1) {


124  estimatedSum += GetDistance(singleRealization, firstNode);


125  }


126  }


127  return estimatedSum / RealizationsSize;


128  }


129 


130  /// <summary>


131  /// An evaluate method that can be used if mean as well as variance should be calculated


132  /// </summary>


133  /// <param name="tour">The tour between all cities.</param>


134  /// <param name="distanceMatrix">The distances between the cities.</param>


135  /// <param name="realizations">A sample of realizations of the stochastic instance</param>


136  /// <returns>A vector with length two containing mean and variance.</returns>


137  public static double[] Evaluate(Permutation tour, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) {


138  // Estimationbased evaluation


139  var estimatedSum = 0.0;


140  var partialSums = new double[realizations.Count];


141  for (var i = 0; i < realizations.Count; i++) {


142  partialSums[i] = 0;


143  int singleRealization = 1, firstNode = 1;


144  for (var j = 0; j < realizations[i].Length; j++) {


145  if (realizations[i][tour[j]]) {


146  if (singleRealization != 1) {


147  partialSums[i] += distanceMatrix[singleRealization, tour[j]];


148  } else {


149  firstNode = tour[j];


150  }


151  singleRealization = tour[j];


152  }


153  }


154  if (singleRealization != 1) {


155  partialSums[i] += distanceMatrix[singleRealization, firstNode];


156  }


157  estimatedSum += partialSums[i];


158  }


159  var mean = estimatedSum / realizations.Count;


160  var variance = 0.0;


161  for (var i = 0; i < realizations.Count; i++) {


162  variance += Math.Pow((partialSums[i]  mean), 2);


163  }


164  variance = variance / realizations.Count;


165  return new[] { mean, variance };


166  }


167 


168  public double GetDistance(int from, int to) {


169  if (UseDistanceMatrix) return DistanceMatrix[from, to];


170  return DistanceCalculator.Calculate(from, to, Coordinates);


171  }


172 


173  private void UpdateRealizations() {


174  var realizations = new ItemList<BoolArray>(RealizationsSize);


175  var rand = new MersenneTwister();


176  for (var i = 0; i < RealizationsSize; i++) {


177  var newRealization = new BoolArray(Probabilities.Length);


178  var countOnes = 0;


179  while (countOnes < 4) { // only generate realizations with at least 4 cities visited


180  countOnes = 0;


181  for (var j = 0; j < Probabilities.Length; j++) {


182  newRealization[j] = Probabilities[j] < rand.NextDouble();


183  if (newRealization[j]) countOnes++;


184  }


185  }


186  Realizations.Add(newRealization);


187  }


188  Realizations = realizations;


189  }


190 


191  public override void Load(PTSPData data) {


192  base.Load(data);


193  UpdateRealizations();


194 


195  foreach (var op in Operators.OfType<IEstimatedPTSPOperator>()) {


196  op.RealizationsParameter.ActualName = RealizationsParameter.Name;


197  }


198  }


199  }


200  } 
