- Timestamp:
- 11/28/15 23:38:51 (9 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/AnalyticalPTSP.cs
r12306 r13412 1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6 using HeuristicLab.Optimization; 7 using HeuristicLab.PluginInfrastructure; 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 22 using HeuristicLab.Common; 8 23 using HeuristicLab.Core; 24 using HeuristicLab.Data; 25 using HeuristicLab.Encodings.PermutationEncoding; 9 26 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 10 using HeuristicLab.Problems.Instances;11 using HeuristicLab.Encodings.PermutationEncoding;12 using HeuristicLab.Common;13 using HeuristicLab.Parameters;14 using HeuristicLab.Data;15 27 16 28 namespace HeuristicLab.Problems.PTSP { 17 [Item("Analytical Probabilistic Traveling Salesman Problem ", "Represents an analytical Probabilistic Traveling Salesman Problem.")]18 [Creatable( "Problems")]29 [Item("Analytical Probabilistic Traveling Salesman Problem (PTSP)", "Represents a probabilistic traveling salesman problem where the expected tour length is calculated exactly.")] 30 [Creatable(CreatableAttribute.Categories.CombinatorialProblems)] 19 31 [StorableClass] 20 public sealed class AnalyticalProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent, 21 IProblemInstanceConsumer<PTSPData> { 32 public sealed class AnalyticalProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem { 22 33 23 34 [StorableConstructor] 24 35 private AnalyticalProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { } 25 private AnalyticalProbabilisticTravelingSalesmanProblem(AnalyticalProbabilisticTravelingSalesmanProblem original, Cloner cloner) 26 : base(original, cloner) { 36 private AnalyticalProbabilisticTravelingSalesmanProblem(AnalyticalProbabilisticTravelingSalesmanProblem original, Cloner cloner) : base(original, cloner) { } 37 public AnalyticalProbabilisticTravelingSalesmanProblem() { 38 Operators.Add(new BestPTSPSolutionAnalyzer()); 27 39 } 28 40 … … 31 43 } 32 44 33 public override double Evaluate(Individual individual, IRandom random) { 34 Permutation p = individual.Permutation(); 35 // Compute A and B matrices 36 DoubleMatrix A = new DoubleMatrix(p.Length, p.Length - 1); 37 DoubleMatrix B = new DoubleMatrix(p.Length, p.Length - 1); 38 //for (int i = 0; i < p.Length; i++) { 39 // for (int k = 0; k < p.Length - 1; k++) { 40 // double firstPartial = 0; 41 // for (int r = k; k < p.Length - 1; r++) { 42 // double sum0 = DistanceMatrix[p[i],p[i+r]]* ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[i+r]]; 43 // for(int s = i+1; s < i+r; s++) { 44 // sum0 = sum0 * (1 - ProbabilityMatrix[0, p[s]]); 45 // } 46 // firstPartial+=sum0; 47 // } 48 // double secondPartial = 0; 49 // for (int r = k; k < p.Length - 1; r++) { 50 // double sum1 = DistanceMatrix[p[i-r],p[i]]* ProbabilityMatrix[0, p[i-r]] * ProbabilityMatrix[0, p[i]]; 51 // for (int s = i + 1; s < p.Length-1; s++) { 52 // sum1 = sum1 * (1 - ProbabilityMatrix[0, p[s]]); 53 // } 54 // for (int t = 1; t < i-1; t++) { 55 // sum1 = sum1 * (1 - ProbabilityMatrix[0, p[t]]); 56 // } 57 // secondPartial+=sum1; 58 // } 59 // A[i, k] = firstPartial; 60 // B[i, k] = secondPartial; 61 // } 62 //} 63 45 public override double Evaluate(Permutation tour, IRandom random) { 64 46 // Analytical evaluation 65 47 double firstSum = 0; 66 for (int i = 0; i < p.Length - 1; i++) {67 for (int j = i + 1; j < p.Length - 1; j++) {68 double sum1 = DistanceMatrix[ p[i], p[j]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]];48 for (int i = 0; i < tour.Length - 1; i++) { 49 for (int j = i + 1; j < tour.Length - 1; j++) { 50 double sum1 = DistanceMatrix[tour[i], tour[j]] * Probabilities[tour[i]] * Probabilities[tour[j]]; 69 51 for (int k = i + 1; k < j; k++) { 70 sum1 = sum1 * (1 - Probabilit yMatrix[p[k]]);52 sum1 = sum1 * (1 - Probabilities[tour[k]]); 71 53 } 72 A[i, j - 1] = sum1;73 54 firstSum += sum1; 74 55 } 75 56 } 76 57 double secondSum = 0; 77 for (int j = 0; j < p.Length - 1; j++) {58 for (int j = 0; j < tour.Length - 1; j++) { 78 59 for (int i = 0; i < j; i++) { 79 double sum2 = DistanceMatrix[ p[j], p[i]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]];80 for (int k = j + 1; k < p.Length - 1; k++) {81 sum2 = sum2 * (1 - Probabilit yMatrix[p[k]]);60 double sum2 = DistanceMatrix[tour[j], tour[i]] * Probabilities[tour[i]] * Probabilities[tour[j]]; 61 for (int k = j + 1; k < tour.Length - 1; k++) { 62 sum2 = sum2 * (1 - Probabilities[tour[k]]); 82 63 } 83 64 for (int k = 1; k < i; k++) { 84 sum2 = sum2 * (1 - Probabilit yMatrix[p[k]]);65 sum2 = sum2 * (1 - Probabilities[tour[k]]); 85 66 } 86 B[i, j] = sum2;87 67 secondSum += sum2; 88 68 } 89 }90 foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {91 op.AParameter.Value = A;92 op.BParameter.Value = B;93 69 } 94 70 return firstSum + secondSum; 95 71 } 96 72 97 public double EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, Permutation individual) { 98 Permutation p = individual; 99 // Compute A and B matrices 100 DoubleMatrix A = new DoubleMatrix(p.Length, p.Length - 1); 101 DoubleMatrix B = new DoubleMatrix(p.Length, p.Length - 1); 73 public static double Evaluate(Permutation tour, DistanceMatrix distanceMatrix, DoubleArray probabilities) { 102 74 // Analytical evaluation 103 double firstSum =0;104 for ( int i = 0; i < p.Length; i++) {105 for ( int j = i + 1; j < p.Length; j++) {106 double sum1 = distances[p[i], p[j]] * probabilities[p[i]] * probabilities[p[j]];107 for ( intk = i + 1; k < j; k++) {108 sum1 = sum1 * (1 - probabilities[ p[k]]);75 var firstSum = 0.0; 76 for (var i = 0; i < tour.Length; i++) { 77 for (var j = i + 1; j < tour.Length; j++) { 78 var sum1 = distanceMatrix[tour[i], tour[j]] * probabilities[tour[i]] * probabilities[tour[j]]; 79 for (var k = i + 1; k < j; k++) { 80 sum1 = sum1 * (1 - probabilities[tour[k]]); 109 81 } 110 A[i, j - 1] = sum1;111 82 firstSum += sum1; 112 83 } 113 84 } 114 double secondSum =0;115 for ( int j = 0; j < p.Length; j++) {116 for ( inti = 0; i < j; i++) {117 double sum2 = distances[p[j], p[i]] * probabilities[p[i]] * probabilities[p[j]];118 for ( int k = j + 1; k < p.Length; k++) {119 sum2 = sum2 * (1 - probabilities[ p[k]]);85 var secondSum = 0.0; 86 for (var j = 0; j < tour.Length; j++) { 87 for (var i = 0; i < j; i++) { 88 var sum2 = distanceMatrix[tour[j], tour[i]] * probabilities[tour[i]] * probabilities[tour[j]]; 89 for (var k = j + 1; k < tour.Length; k++) { 90 sum2 = sum2 * (1 - probabilities[tour[k]]); 120 91 } 121 for ( intk = 0; k < i; k++) {122 sum2 = sum2 * (1 - probabilities[ p[k]]);92 for (var k = 0; k < i; k++) { 93 sum2 = sum2 * (1 - probabilities[tour[k]]); 123 94 } 124 B[j,i] = sum2;125 95 secondSum += sum2; 126 96 } 127 97 } 128 foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {129 op.AParameter.Value = A;130 op.BParameter.Value = B;131 }132 98 return firstSum + secondSum; 133 99 } 134 135 public AnalyticalProbabilisticTravelingSalesmanProblem() {136 Operators.Add(new PTSPAnalyticalInversionMovePathEvaluator());137 }138 139 public override void Load(PTSPData data) {140 base.Load(data);141 foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {142 op.ProbabilitiesParameter.Value = ProbabilityMatrix;143 }144 }145 146 100 } 147 101 }
Note: See TracChangeset
for help on using the changeset viewer.