Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14457 was 14186, checked in by swagner, 8 years ago

#2526: Updated year of copyrights in license headers

File size: 4.7 KB
RevLine 
[13412]1#region License Information
2/* HeuristicLab
[14186]3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[13412]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
[13470]22using System;
23using System.Linq;
[13412]24using HeuristicLab.Common;
[12191]25using HeuristicLab.Core;
[13412]26using HeuristicLab.Data;
27using HeuristicLab.Encodings.PermutationEncoding;
[13470]28using HeuristicLab.Optimization;
[12191]29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Problems.PTSP {
[13412]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)]
[12191]34  [StorableClass]
[13412]35  public sealed class AnalyticalProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem {
[12191]36
37    [StorableConstructor]
38    private AnalyticalProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
[13412]39    private AnalyticalProbabilisticTravelingSalesmanProblem(AnalyticalProbabilisticTravelingSalesmanProblem original, Cloner cloner) : base(original, cloner) { }
40    public AnalyticalProbabilisticTravelingSalesmanProblem() {
41      Operators.Add(new BestPTSPSolutionAnalyzer());
[13470]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      }
[12191]63    }
64
65    public override IDeepCloneable Clone(Cloner cloner) {
66      return new AnalyticalProbabilisticTravelingSalesmanProblem(this, cloner);
67    }
68
[13412]69    public override double Evaluate(Permutation tour, IRandom random) {
[13470]70      // abeham: Cache in local variable for performance reasons
71      var distanceMatrix = DistanceMatrix;
72      return Evaluate(tour, (a, b) => distanceMatrix[a, b], Probabilities);
[12191]73    }
74
[13470]75    public static double Evaluate(Permutation tour, Func<int, int, double> distance, DoubleArray probabilities) {
[12269]76      // Analytical evaluation
[13412]77      var firstSum = 0.0;
[13470]78      for (var i = 0; i < tour.Length - 1; i++) {
[13412]79        for (var j = i + 1; j < tour.Length; j++) {
[13470]80          var prod1 = distance(tour[i], tour[j]) * probabilities[tour[i]] * probabilities[tour[j]];
[13412]81          for (var k = i + 1; k < j; k++) {
[13470]82            prod1 = prod1 * (1 - probabilities[tour[k]]);
[12269]83          }
[13470]84          firstSum += prod1;
[12269]85        }
86      }
[13412]87      var secondSum = 0.0;
88      for (var j = 0; j < tour.Length; j++) {
89        for (var i = 0; i < j; i++) {
[13470]90          var prod2 = distance(tour[j], tour[i]) * probabilities[tour[i]] * probabilities[tour[j]];
[13412]91          for (var k = j + 1; k < tour.Length; k++) {
[13470]92            prod2 = prod2 * (1 - probabilities[tour[k]]);
[12269]93          }
[13412]94          for (var k = 0; k < i; k++) {
[13470]95            prod2 = prod2 * (1 - probabilities[tour[k]]);
[12269]96          }
[13470]97          secondSum += prod2;
[12269]98        }
99      }
100      return firstSum + secondSum;
101    }
[13470]102
103    public static double Evaluate(Permutation tour, DistanceMatrix distanceMatrix, DoubleArray probabilities) {
104      return Evaluate(tour, (a, b) => distanceMatrix[a, b], probabilities);
105    }
[12191]106  }
107}
Note: See TracBrowser for help on using the repository browser.