Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.PTSP/3.3/AnalyticalPTSP.cs @ 14112

Last change on this file since 14112 was 13470, checked in by abeham, 9 years ago

#2221:

  • implemented review comments
    • hid rng as private class, implemented djb2 hash function (hash function implementation may also change)
    • added missing probabilities
    • base class for instance providers
    • prebuild event events
    • build platforms
    • unit test will be removed on trunk integration
    • corrected assembly file version
    • distance calculator parameter was not hidden, can be changed by user, updates distance matrix
    • fixed performance problems (ouch!) also for estimated ptsp (inlined GetDistance method)
  • added moves (full evaluation) for analytical tsp
  • added local improvement operators for analytical ptsp
  • added recalculation of distance matrix when parameters change
  • still lots of other changes
File size: 4.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Problems.PTSP {
32  [Item("Analytical Probabilistic Traveling Salesman Problem (PTSP)", "Represents a probabilistic traveling salesman problem where the expected tour length is calculated exactly.")]
33  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
34  [StorableClass]
35  public sealed class AnalyticalProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem {
36
37    [StorableConstructor]
38    private AnalyticalProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
39    private AnalyticalProbabilisticTravelingSalesmanProblem(AnalyticalProbabilisticTravelingSalesmanProblem original, Cloner cloner) : base(original, cloner) { }
40    public AnalyticalProbabilisticTravelingSalesmanProblem() {
41      Operators.Add(new BestPTSPSolutionAnalyzer());
42
43      Operators.Add(new PTSPAnalyticalInversionMoveEvaluator());
44      Operators.Add(new PTSPAnalyticalInsertionMoveEvaluator());
45      Operators.Add(new PTSPAnalyticalInversionLocalImprovement());
46      Operators.Add(new PTSPAnalyticalInsertionLocalImprovement());
47      Operators.Add(new PTSPAnalyticalTwoPointFiveLocalImprovement());
48
49      Operators.Add(new ExhaustiveTwoPointFiveMoveGenerator());
50      Operators.Add(new StochasticTwoPointFiveMultiMoveGenerator());
51      Operators.Add(new StochasticTwoPointFiveSingleMoveGenerator());
52      Operators.Add(new TwoPointFiveMoveMaker());
53      Operators.Add(new PTSPAnalyticalTwoPointFiveMoveEvaluator());
54
55      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
56      Operators.RemoveAll(x => x is SingleObjectiveMoveMaker);
57      Operators.RemoveAll(x => x is SingleObjectiveMoveEvaluator);
58
59      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
60      foreach (var twopointfiveMoveOperator in Operators.OfType<ITwoPointFiveMoveOperator>()) {
61        twopointfiveMoveOperator.TwoPointFiveMoveParameter.ActualName = "Permutation.TwoPointFiveMove";
62      }
63    }
64
65    public override IDeepCloneable Clone(Cloner cloner) {
66      return new AnalyticalProbabilisticTravelingSalesmanProblem(this, cloner);
67    }
68
69    public override double Evaluate(Permutation tour, IRandom random) {
70      // abeham: Cache in local variable for performance reasons
71      var distanceMatrix = DistanceMatrix;
72      return Evaluate(tour, (a, b) => distanceMatrix[a, b], Probabilities);
73    }
74
75    public static double Evaluate(Permutation tour, Func<int, int, double> distance, DoubleArray probabilities) {
76      // Analytical evaluation
77      var firstSum = 0.0;
78      for (var i = 0; i < tour.Length - 1; i++) {
79        for (var j = i + 1; j < tour.Length; j++) {
80          var prod1 = distance(tour[i], tour[j]) * probabilities[tour[i]] * probabilities[tour[j]];
81          for (var k = i + 1; k < j; k++) {
82            prod1 = prod1 * (1 - probabilities[tour[k]]);
83          }
84          firstSum += prod1;
85        }
86      }
87      var secondSum = 0.0;
88      for (var j = 0; j < tour.Length; j++) {
89        for (var i = 0; i < j; i++) {
90          var prod2 = distance(tour[j], tour[i]) * probabilities[tour[i]] * probabilities[tour[j]];
91          for (var k = j + 1; k < tour.Length; k++) {
92            prod2 = prod2 * (1 - probabilities[tour[k]]);
93          }
94          for (var k = 0; k < i; k++) {
95            prod2 = prod2 * (1 - probabilities[tour[k]]);
96          }
97          secondSum += prod2;
98        }
99      }
100      return firstSum + secondSum;
101    }
102
103    public static double Evaluate(Permutation tour, DistanceMatrix distanceMatrix, DoubleArray probabilities) {
104      return Evaluate(tour, (a, b) => distanceMatrix[a, b], probabilities);
105    }
106  }
107}
Note: See TracBrowser for help on using the repository browser.