- Timestamp:
- 03/10/15 16:00:47 (9 years ago)
- Location:
- branches/PTSP/HeuristicLab.Problems.PTSP/3.3
- Files:
-
- 1 added
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj
r12166 r12183 37 37 </PropertyGroup> 38 38 <ItemGroup> 39 <Reference Include="HeuristicLab.Collections-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL"> 40 <SpecificVersion>False</SpecificVersion> 41 <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Collections-3.3.dll</HintPath> 42 <Private>False</Private> 43 </Reference> 39 44 <Reference Include="HeuristicLab.Common-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL"> 40 45 <SpecificVersion>False</SpecificVersion> … … 103 108 <None Include="Properties\AssemblyInfo.cs.frame" /> 104 109 <None Include="Plugin.cs.frame" /> 110 <Compile Include="DistanceMatrix.cs" /> 105 111 <Compile Include="PTSP.cs" /> 106 112 <Compile Include="Plugin.cs" /> -
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs
r12166 r12183 41 41 public sealed class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent, 42 42 IProblemInstanceConsumer<TSPData> { 43 #region Parameter Properties 44 public OptionalValueParameter<DoubleMatrix> CoordinatesParameter { 45 get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; } 46 } 47 public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter { 48 get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; } 49 } 50 public ValueParameter<BoolValue> UseDistanceMatrixParameter { 51 get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; } 52 } 53 public OptionalValueParameter<Permutation> BestKnownSolutionParameter { 54 get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; } 55 } 56 public ValueParameter<BoolValue> UseAnalyticalEvaluationParameter { 57 get { return (ValueParameter<BoolValue>)Parameters["UseAnalyticalEvaluation"]; } 58 } 59 public OptionalValueParameter<DistanceMatrix> ProbabilityMatrixParameter { 60 get { return (OptionalValueParameter<DistanceMatrix>)Parameters["ProbabilityMatrix"]; } 61 } 62 public ValueParameter<IntValue> SampleSizeParameter { 63 get { return (ValueParameter<IntValue>)Parameters["SampleSize"]; } 64 } 65 66 #endregion 67 68 #region Properties 69 public DoubleMatrix Coordinates { 70 get { return CoordinatesParameter.Value; } 71 set { CoordinatesParameter.Value = value; } 72 } 73 public DistanceMatrix DistanceMatrix { 74 get { return DistanceMatrixParameter.Value; } 75 set { DistanceMatrixParameter.Value = value; } 76 } 77 public BoolValue UseDistanceMatrix { 78 get { return UseDistanceMatrixParameter.Value; } 79 set { UseDistanceMatrixParameter.Value = value; } 80 } 81 public Permutation BestKnownSolution { 82 get { return BestKnownSolutionParameter.Value; } 83 set { BestKnownSolutionParameter.Value = value; } 84 } 85 public BoolValue UseAnalyticalEvaluation { 86 get { return UseAnalyticalEvaluationParameter.Value; } 87 set { UseAnalyticalEvaluationParameter.Value = value; } 88 } 89 public DistanceMatrix ProbabilityMatrix { 90 get { return ProbabilityMatrixParameter.Value; } 91 set { ProbabilityMatrixParameter.Value = value; } 92 } 93 public IntValue SampleSize { 94 get { return SampleSizeParameter.Value; } 95 set { SampleSizeParameter.Value = value; } 96 } 97 #endregion 43 98 public override double Evaluate(Individual individual, IRandom random) { 44 return random.NextDouble(); 99 Permutation p = individual.Permutation(); 100 if (UseAnalyticalEvaluation.Value) { 101 // Analytical evaluation 102 double firstSum = 0; 103 for (int i = 0; i < p.Length - 1; i++) { 104 for (int j = i + 1; j < p.Length - 1; j++) { 105 double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[j]]; 106 for (int k = i + 1; k < j; k++) { 107 sum1 = sum1 * (1 - ProbabilityMatrix[0, p[k]]); 108 } 109 firstSum += sum1; 110 } 111 } 112 double secondSum = 0; 113 for (int j = 0; j < p.Length - 1; j++) { 114 for (int i = 0; i < j; i++) { 115 double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[j]]; 116 for (int k = j + 1; k < p.Length - 1; k++) { 117 sum2 = sum2 * (1 - ProbabilityMatrix[0, p[k]]); 118 } 119 for (int k = 1; k < i; k++) { 120 sum2 = sum2 * (1 - ProbabilityMatrix[0, p[k]]); 121 } 122 secondSum += sum2; 123 } 124 } 125 return firstSum+secondSum; 126 } else { 127 // Estimation-based evaluation 128 Random r = new Random(); 129 double estimatedSum = 0; 130 for (int i = 0; i < SampleSize.Value; i++) { 131 int singleRealization = -1; 132 for (int j = 0; j < p.Length - 1; j++) { 133 if (ProbabilityMatrix[0, p[j]] > r.NextDouble()) { 134 if (singleRealization != -1) { 135 estimatedSum += DistanceMatrix[singleRealization, p[j]]; 136 } 137 singleRealization = p[j]; 138 } 139 } 140 } 141 return estimatedSum / SampleSize.Value; 142 } 45 143 } 46 144 … … 50 148 51 149 [StorableConstructor] 52 pr otectedProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }53 pr otectedProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)150 private ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { } 151 private ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner) 54 152 : base(original, cloner) { 55 153 } … … 58 156 } 59 157 public ProbabilisticTravelingSalesmanProblem() { 60 Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The coordinates of the cities.")); 158 Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.")); 159 Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities.")); 160 Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if the coordinates based evaluators should calculate the distance matrix from the coordinates and use it for evaluation similar to the distance matrix evaluator, otherwise false.", new BoolValue(true))); 161 Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance.")); 162 Parameters.Add(new ValueParameter<BoolValue>("UseAnalyticalEvaluation", "Check to use analytical evaluation, uncheck to use estimation-based approach.")); 163 Parameters.Add(new OptionalValueParameter<DistanceMatrix>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities.")); 164 Parameters.Add(new ValueParameter<IntValue>("SampleSize", "Size of the sample for the estimation-based evaluation")); 61 165 } 62 166 63 167 public void Load(TSPData data) { 64 168 SampleSize = new IntValue(20); 169 DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix()); 170 // Get Probabilities of cities using random with seed from hash function on the Name of the instance 171 ProbabilityMatrix = new DistanceMatrix(1, data.Dimension); 172 Random r = new Random(data.Name.GetHashCode()); 173 for (int i = 0; i < data.Dimension; i++) { 174 ProbabilityMatrix[0,i] = r.NextDouble(); 175 } 176 Encoding.Length = data.Dimension; 65 177 } 66 178 }
Note: See TracChangeset
for help on using the changeset viewer.