Changeset 12380 for branches/PTSP/HeuristicLab.Problems.PTSP/3.3
- Timestamp:
- 05/04/15 18:30:26 (9 years ago)
- Location:
- branches/PTSP/HeuristicLab.Problems.PTSP/3.3
- Files:
-
- 1 added
- 3 deleted
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs
r12306 r12380 104 104 Parameters.Add(new ValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimation-based evaluation")); 105 105 Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete...")); 106 Operators.Add(new PTSPEstimatedInversion MovePathEvaluator());106 Operators.Add(new PTSPEstimatedInversionEvaluator()); 107 107 Operators.Add(new PTSPEstimatedInsertionEvaluator()); 108 108 Operators.Add(new PTSPExhaustiveInversionLocalImprovement()); … … 121 121 } 122 122 123 private int Ttest(int ProblemSize) {124 MersenneTwister random = new MersenneTwister();125 Permutation p1 = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);126 Permutation p2 = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);127 ItemList<ItemList<IntValue>> realizations = new ItemList<ItemList<IntValue>>();128 int index = -1;129 while (true) {130 for (int i = index+1; i < index+5; i++) {131 realizations.Add(new ItemList<IntValue>());132 for (int j = 0; j < ProblemSize; j++) {133 if (ProbabilityMatrix[j] > random.NextDouble()) {134 realizations.ElementAt(i).Add(new IntValue(1));135 } else {136 realizations.ElementAt(i).Add(new IntValue(0));137 }138 }139 }140 index += 4;141 double[] eval1 = EvaluateWithParams(DistanceMatrix, ProbabilityMatrix, realizations, p1);142 double[] eval2 = EvaluateWithParams(DistanceMatrix, ProbabilityMatrix, realizations, p2);143 double sx1x2 = Math.Sqrt((eval1[1]+eval2[1])/2);144 int degrees = 2 * realizations.Count - 2;145 double t = (eval1[0]-eval2[0])/(sx1x2*Math.Sqrt(2.0/(double)realizations.Count));146 }147 }148 149 123 public override void Load(PTSPData data) { 150 124 base.Load(data); 151 // For now uses sample size of 20 but should use Student's t-test152 //Ttest(data.Dimension);153 125 RealizationsSize = new IntValue(100); 154 126 MersenneTwister r = new MersenneTwister(); 127 128 // TODO : This should be made in another function and attached to a listener 155 129 int countOnes = 0; 156 130 Realizations = new ItemList<ItemList<IntValue>>(RealizationsSize.Value); … … 173 147 } 174 148 175 foreach (var op in Operators.OfType<PTSP PathMoveEvaluator>()) {149 foreach (var op in Operators.OfType<PTSPMoveEvaluator>()) { 176 150 op.RealizationsParameter.Value = Realizations; 177 151 } -
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj
r12272 r12380 120 120 <Compile Include="Improvers\PTSPExhaustiveInversionLocalImprovement.cs" /> 121 121 <Compile Include="Interfaces\I25MoveOperator.cs" /> 122 <Compile Include="Interfaces\IPTSPPathMoveEvaluator.cs" />123 122 <Compile Include="Interfaces\IPTSPMoveEvaluator.cs" /> 124 123 <Compile Include="MoveEvaluators\OneShift\PTSPEstimatedInsertionEvaluator.cs" /> 125 124 <Compile Include="MoveEvaluators\PTSPMoveEvaluator.cs" /> 126 <Compile Include="MoveEvaluators\PTSPPathMoveEvaluator.cs" />127 125 <Compile Include="MoveEvaluators\TwoOpt\PTSPAnalyticalInversionMovePathEvaluator.cs" /> 128 <Compile Include="MoveEvaluators\TwoOpt\PTSPEstimatedInversion MovePathEvaluator.cs" />126 <Compile Include="MoveEvaluators\TwoOpt\PTSPEstimatedInversionEvaluator.cs" /> 129 127 <Compile Include="MoveEvaluators\TwoPointFiveOpt\PTSP25MoveEvaluator.cs" /> 130 128 <Compile Include="MoveGenerators\Exhaustive25MoveGenerator.cs" /> -
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInversionLocalImprovement.cs
r12228 r12380 107 107 double evaluations = 0.0; 108 108 foreach (var move in ExhaustiveInversionMoveGenerator.Generate(assignment)) { 109 double moveQuality = PTSPEstimatedInversion MovePathEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);109 double moveQuality = PTSPEstimatedInversionEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations); 110 110 evaluations += 2 * (move.Index2 - move.Index1 + 1) / (double)assignment.Length; 111 111 if (maximization && moveQuality > bestQuality -
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Interfaces/IPTSPMoveEvaluator.cs
r12191 r12380 20 20 #endregion 21 21 22 using HeuristicLab.Core; 23 using HeuristicLab.Data; 24 using HeuristicLab.Encodings.PermutationEncoding; 25 using HeuristicLab.Optimization; 22 26 using System; 23 using HeuristicLab.Optimization;24 27 25 28 namespace HeuristicLab.Problems.PTSP { 26 public interface IPTSPMoveEvaluator : ISingleObjectiveMoveEvaluator, IMoveOperator {29 public interface IPTSPMoveEvaluator : ISingleObjectiveMoveEvaluator, IMoveOperator, IPermutationMoveOperator { 27 30 Type EvaluatorType { get; } 31 ILookupParameter<DoubleMatrix> CoordinatesParameter { get; } 32 ILookupParameter<DistanceMatrix> DistanceMatrixParameter { get; } 33 ILookupParameter<BoolValue> UseDistanceMatrixParameter { get; } 34 28 35 } 29 36 } -
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/OneShift/PTSPEstimatedInsertionEvaluator.cs
r12272 r12380 31 31 [Item("PTSPEstimatedInsertionEvaluator", "Evaluates an insertion move (1-shift)")] 32 32 [StorableClass] 33 public class PTSPEstimatedInsertionEvaluator : PTSP PathMoveEvaluator, IPermutationTranslocationMoveOperator {33 public class PTSPEstimatedInsertionEvaluator : PTSPMoveEvaluator, IPermutationTranslocationMoveOperator { 34 34 35 35 public override Type EvaluatorType { -
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/PTSPMoveEvaluator.cs
r12191 r12380 1 using System; 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 System; 2 23 using HeuristicLab.Common; 3 24 using HeuristicLab.Core; 4 25 using HeuristicLab.Data; 26 using HeuristicLab.Encodings.PermutationEncoding; 27 using HeuristicLab.Parameters; 28 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 5 29 using HeuristicLab.Operators; 6 30 using HeuristicLab.Optimization; 7 using HeuristicLab.Parameters;8 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;9 31 10 32 namespace HeuristicLab.Problems.PTSP { … … 21 43 } 22 44 45 public ILookupParameter<Permutation> PermutationParameter { 46 get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; } 47 } 48 public ILookupParameter<DoubleMatrix> CoordinatesParameter { 49 get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; } 50 } 51 public ILookupParameter<DistanceMatrix> DistanceMatrixParameter { 52 get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; } 53 } 54 public ILookupParameter<BoolValue> UseDistanceMatrixParameter { 55 get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; } 56 } 57 public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter { 58 get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; } 59 } 60 23 61 public ILookupParameter<DoubleValue> QualityParameter { 24 62 get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; } … … 33 71 protected PTSPMoveEvaluator() 34 72 : base() { 73 Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation.")); 74 Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The city's coordinates.")); 75 Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities.")); 76 Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated (if it does not exist already) and used for evaluation, otherwise false.")); 77 Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete...")); 35 78 Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of a TSP solution.")); 36 79 Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The evaluated quality of a move on a TSP solution.")); 37 80 } 81 82 [StorableHook(HookType.AfterDeserialization)] 83 private void AfterDeserialization() { 84 // BackwardsCompatibility3.3 85 #region Backwards compatible code (remove with 3.4) 86 LookupParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as LookupParameter<DoubleMatrix>; 87 if (oldDistanceMatrixParameter != null) { 88 Parameters.Remove(oldDistanceMatrixParameter); 89 Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities.")); 90 DistanceMatrixParameter.ActualName = oldDistanceMatrixParameter.ActualName; 91 } 92 #endregion 93 } 94 95 public override IOperation Apply() { 96 Permutation permutation = PermutationParameter.ActualValue; 97 DoubleMatrix coordinates = CoordinatesParameter.ActualValue; 98 double relativeQualityDifference = 0; 99 if (UseDistanceMatrixParameter.ActualValue.Value) { 100 DistanceMatrix distanceMatrix = DistanceMatrixParameter.ActualValue; 101 if (distanceMatrix == null) { 102 if (coordinates == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given."); 103 distanceMatrix = CalculateDistanceMatrix(coordinates); 104 DistanceMatrixParameter.ActualValue = distanceMatrix; 105 } 106 relativeQualityDifference = EvaluateByDistanceMatrix(permutation, distanceMatrix); 107 } else { 108 if (coordinates == null) throw new InvalidOperationException("No coordinates were given."); 109 relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates); 110 } 111 DoubleValue moveQuality = MoveQualityParameter.ActualValue; 112 if (moveQuality == null) MoveQualityParameter.ActualValue = new DoubleValue(QualityParameter.ActualValue.Value + relativeQualityDifference); 113 else moveQuality.Value = QualityParameter.ActualValue.Value + relativeQualityDifference; 114 return base.Apply(); 115 } 116 117 protected abstract double CalculateDistance(double x1, double y1, double x2, double y2); 118 protected abstract double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix); 119 protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates); 120 121 private DistanceMatrix CalculateDistanceMatrix(DoubleMatrix c) { 122 DistanceMatrix distanceMatrix = new DistanceMatrix(c.Rows, c.Rows); 123 for (int i = 0; i < distanceMatrix.Rows; i++) { 124 for (int j = 0; j < distanceMatrix.Columns; j++) 125 distanceMatrix[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]); 126 } 127 return (DistanceMatrix)distanceMatrix.AsReadOnly(); 128 } 38 129 } 39 130 } -
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPAnalyticalInversionMovePathEvaluator.cs
r12228 r12380 33 33 [Item("PTSPAnalyticalInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) of the PTSP in with the closed form expression")] 34 34 [StorableClass] 35 public class PTSPAnalyticalInversionMovePathEvaluator : PTSP PathMoveEvaluator, IPermutationInversionMoveOperator {35 public class PTSPAnalyticalInversionMovePathEvaluator : PTSPMoveEvaluator, IPermutationInversionMoveOperator { 36 36 37 37 private static DoubleArray probabilities;
Note: See TracChangeset
for help on using the changeset viewer.