Changeset 9363 for branches/OaaS/HeuristicLab.Problems.QuadraticAssignment
- Timestamp:
- 04/16/13 13:13:41 (11 years ago)
- Location:
- branches/OaaS
- Files:
-
- 8 edited
- 4 copied
Legend:
- Unmodified
- Added
- Removed
-
branches/OaaS
- Property svn:ignore
-
old new 21 21 protoc.exe 22 22 _ReSharper.HeuristicLab 3.3 Tests 23 Google.ProtocolBuffers-2.4.1.473.dll 23 24 packages
-
- Property svn:mergeinfo changed
- Property svn:ignore
-
branches/OaaS/HeuristicLab.Problems.QuadraticAssignment
- Property svn:mergeinfo changed
/trunk/sources/HeuristicLab.Problems.QuadraticAssignment (added) merged: 8246,8338,8553,8600,8846-8847,8910,9029
- Property svn:mergeinfo changed
-
branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/BoundsCalculators/GilmoreLawlerBoundCalculator.cs
r8092 r9363 22 22 using System; 23 23 using HeuristicLab.Data; 24 using HeuristicLab.Encodings.PermutationEncoding; 24 25 using HeuristicLab.Problems.LinearAssignment; 25 26 … … 27 28 public static class GilmoreLawlerBoundCalculator { 28 29 public static double CalculateLowerBound(DoubleMatrix weights, DoubleMatrix distances) { 30 Permutation tmp; 31 return CalculateLowerBound(weights, distances, out tmp); 32 } 33 34 public static double CalculateLowerBound(DoubleMatrix weights, DoubleMatrix distances, out Permutation solution) { 29 35 int N = weights.Rows; 30 36 DoubleMatrix sortedWeights = SortEachRowExceptDiagonal(weights), sortedDistances = SortEachRowExceptDiagonal(distances); … … 40 46 41 47 double result; 42 LinearAssignmentProblemSolver.Solve(costs, out result);48 solution = new Permutation(PermutationTypes.Absolute, LinearAssignmentProblemSolver.Solve(costs, out result)); 43 49 return result; 44 50 } -
branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj
r7877 r9363 125 125 <Compile Include="Interfaces\IQAPEvaluator.cs" /> 126 126 <Compile Include="Interfaces\IQAPMoveEvaluator.cs" /> 127 <Compile Include="LocalImprovement\QAPExhaustiveInsertionLocalImprovement.cs" /> 128 <Compile Include="LocalImprovement\QAPStochasticScrambleLocalImprovement.cs" /> 127 129 <Compile Include="LocalImprovement\QAPExhaustiveSwap2LocalImprovement.cs" /> 130 <Compile Include="LocalImprovement\QAPExhaustiveInversionLocalImprovement.cs" /> 128 131 <Compile Include="QAPAssignment.cs" /> 129 132 <Compile Include="QAPPermutationProximityCalculator.cs" /> 130 133 <Compile Include="QuadraticAssignmentProblem.cs" /> 134 <Compile Include="QAPSimilarityCalculator.cs" /> 131 135 <None Include="Plugin.cs.frame" /> 132 136 <Compile Include="Plugin.cs" /> … … 178 182 <Private>False</Private> 179 183 </ProjectReference> 184 <ProjectReference Include="..\..\HeuristicLab.Optimization.Operators\3.3\HeuristicLab.Optimization.Operators-3.3.csproj"> 185 <Project>{25087811-f74c-4128-bc86-8324271da13e}</Project> 186 <Name>HeuristicLab.Optimization.Operators-3.3</Name> 187 <Private>False</Private> 188 </ProjectReference> 180 189 <ProjectReference Include="..\..\HeuristicLab.Optimization\3.3\HeuristicLab.Optimization-3.3.csproj"> 181 190 <Project>{14AB8D24-25BC-400C-A846-4627AA945192}</Project> … … 210 219 <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" /> 211 220 <PropertyGroup> 212 <PreBuildEvent >set Path=%25Path%25;$(ProjectDir);$(SolutionDir)221 <PreBuildEvent Condition=" '$(OS)' == 'Windows_NT' ">set Path=%25Path%25;$(ProjectDir);$(SolutionDir) 213 222 set ProjectDir=$(ProjectDir) 214 223 set SolutionDir=$(SolutionDir) … … 216 225 217 226 call PreBuildEvent.cmd</PreBuildEvent> 227 <PreBuildEvent Condition=" '$(OS)' != 'Windows_NT' "> 228 export ProjectDir=$(ProjectDir) 229 export SolutionDir=$(SolutionDir) 230 231 $SolutionDir/PreBuildEvent.sh 232 </PreBuildEvent> 218 233 </PropertyGroup> 219 234 <PropertyGroup> -
branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs
r7878 r9363 21 21 22 22 using System; 23 using System.Threading; 23 24 using HeuristicLab.Common; 24 25 using HeuristicLab.Core; … … 46 47 } 47 48 49 public ILookupParameter<IntValue> LocalIterationsParameter { 50 get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; } 51 } 52 48 53 public IValueLookupParameter<IntValue> MaximumIterationsParameter { 49 54 get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; } … … 76 81 public ILookupParameter<DoubleMatrix> DistancesParameter { 77 82 get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; } 83 } 84 85 public IValueLookupParameter<BoolValue> UseFastEvaluationParameter { 86 get { return (IValueLookupParameter<BoolValue>)Parameters["UseFastEvaluation"]; } 78 87 } 79 88 … … 86 95 public QAPExhaustiveSwap2LocalImprovement() 87 96 : base() { 88 Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum amount of iterations that should be performed (note that this operator will abort earlier when a local optimum is reached.", new IntValue(10000))); 97 Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed.")); 98 Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum amount of iterations that should be performed (note that this operator will abort earlier when a local optimum is reached).", new IntValue(10000))); 89 99 Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The amount of evaluated solutions (here a move is counted only as 4/n evaluated solutions with n being the length of the permutation).")); 90 100 Parameters.Add(new LookupParameter<ResultCollection>("Results", "The collection where to store results.")); … … 94 104 Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix.")); 95 105 Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix.")); 106 Parameters.Add(new ValueLookupParameter<BoolValue>("UseFastEvaluation", "Enabling this option will use a NxN double matrix to save the last move qualities. The moves of the first iteration will then be evaluated in O(N) while all further moves will be evaluated in O(1).", new BoolValue(true))); 96 107 } 97 108 … … 100 111 } 101 112 102 public static double Improve(Permutation assignment, double quality, DoubleMatrix weights, DoubleMatrix distances, bool maximization, int maxIterations, out double evaluatedSolutions) { 103 evaluatedSolutions = 0.0; 113 // BackwardsCompatibility3.3 114 #region Backwards compatible code, remove with 3.4 115 [StorableHook(HookType.AfterDeserialization)] 116 private void AfterDeserialization() { 117 if (!Parameters.ContainsKey("LocalIterations")) 118 Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed.")); 119 if (!Parameters.ContainsKey("UseFastEvaluation")) 120 Parameters.Add(new ValueLookupParameter<BoolValue>("UseFastEvaluation", "Enabling this option will use a NxN double matrix to save the last move qualities. The moves of the first iteration will then be evaluated in O(N) while all further moves will be evaluated in O(1).", new BoolValue(false))); 121 } 122 #endregion 123 124 public static void Improve(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) { 104 125 double evalSolPerMove = 4.0 / assignment.Length; 105 126 106 for (int i = 0; i < maxIterations; i++) {127 for (int i = localIterations.Value; i < maxIterations; i++) { 107 128 Swap2Move bestMove = null; 108 129 double bestQuality = 0; // we have to make an improvement, so 0 is the baseline 130 double evaluations = 0.0; 109 131 foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) { 110 132 double moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances); 111 evaluatedSolutions += evalSolPerMove; 133 evaluations += evalSolPerMove; 134 if (maximization && moveQuality > bestQuality 135 || !maximization && moveQuality < bestQuality) { 136 bestQuality = moveQuality; 137 bestMove = move; 138 } 139 } 140 evaluatedSolutions.Value += (int)Math.Ceiling(evaluations); 141 if (bestMove == null) break; 142 Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2); 143 quality.Value += bestQuality; 144 localIterations.Value++; 145 cancellation.ThrowIfCancellationRequested(); 146 } 147 } 148 149 public static void ImproveFast(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) { 150 Swap2Move bestMove = null; 151 double evaluations = 0.0; 152 var lastQuality = new double[assignment.Length, assignment.Length]; 153 for (int i = localIterations.Value; i < maxIterations; i++) { 154 double bestQuality = 0; // we have to make an improvement, so 0 is the baseline 155 var lastMove = bestMove; 156 bestMove = null; 157 foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) { 158 double moveQuality; 159 if (lastMove == null) { 160 moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances); 161 evaluations += 4.0 / assignment.Length; 162 } else { 163 moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, lastQuality[move.Index1, move.Index2], weights, distances, lastMove); 164 if (move.Index1 == lastMove.Index1 || move.Index2 == lastMove.Index1 || move.Index1 == lastMove.Index2 || move.Index2 == lastMove.Index2) 165 evaluations += 4.0 / assignment.Length; 166 else evaluations += 2.0 / (assignment.Length * assignment.Length); 167 } 168 lastQuality[move.Index1, move.Index2] = moveQuality; 112 169 if (maximization && moveQuality > bestQuality 113 170 || !maximization && moveQuality < bestQuality) { … … 118 175 if (bestMove == null) break; 119 176 Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2); 120 quality += bestQuality; 177 quality.Value += bestQuality; 178 localIterations.Value++; 179 if (cancellation.IsCancellationRequested) { 180 evaluatedSolutions.Value += (int)Math.Round(evaluations); 181 throw new OperationCanceledException(); 182 } 121 183 } 122 return quality;184 evaluatedSolutions.Value += (int)Math.Round(evaluations); 123 185 } 124 186 125 187 public override IOperation Apply() { 126 int maxIterations = MaximumIterationsParameter.ActualValue.Value; 127 Permutation assignment = AssignmentParameter.ActualValue; 128 bool maximization = MaximizationParameter.ActualValue.Value; 129 DoubleMatrix weights = WeightsParameter.ActualValue; 130 DoubleMatrix distances = DistancesParameter.ActualValue; 131 double quality = QualityParameter.ActualValue.Value; 132 133 double evaluations; 134 QualityParameter.ActualValue.Value = Improve(assignment, quality, weights, distances, maximization, maxIterations, out evaluations); 135 EvaluatedSolutionsParameter.ActualValue.Value += (int)Math.Ceiling(evaluations); 188 var maxIterations = MaximumIterationsParameter.ActualValue.Value; 189 var assignment = AssignmentParameter.ActualValue; 190 var maximization = MaximizationParameter.ActualValue.Value; 191 var weights = WeightsParameter.ActualValue; 192 var distances = DistancesParameter.ActualValue; 193 var quality = QualityParameter.ActualValue; 194 var localIterations = LocalIterationsParameter.ActualValue; 195 var evaluations = EvaluatedSolutionsParameter.ActualValue; 196 if (localIterations == null) { 197 localIterations = new IntValue(0); 198 LocalIterationsParameter.ActualValue = localIterations; 199 } 200 201 if (UseFastEvaluationParameter.ActualValue.Value) 202 ImproveFast(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken); 203 else Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken); 204 205 localIterations.Value = 0; 136 206 return base.Apply(); 137 207 } -
branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/Plugin.cs.frame
r7877 r9363 23 23 24 24 namespace HeuristicLab.Problems.QuadraticAssignment { 25 [Plugin("HeuristicLab.Problems.QuadraticAssignment", "3.3. 6.$WCREV$")]25 [Plugin("HeuristicLab.Problems.QuadraticAssignment", "3.3.7.$WCREV$")] 26 26 [PluginFile("HeuristicLab.Problems.QuadraticAssignment-3.3.dll", PluginFileType.Assembly)] 27 27 [PluginDependency("HeuristicLab.Analysis", "3.3")] … … 34 34 [PluginDependency("HeuristicLab.Operators", "3.3")] 35 35 [PluginDependency("HeuristicLab.Optimization", "3.3")] 36 [PluginDependency("HeuristicLab.Optimization.Operators", "3.3")] 36 37 [PluginDependency("HeuristicLab.Parameters", "3.3")] 37 38 [PluginDependency("HeuristicLab.Persistence", "3.3")] -
branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/Properties/AssemblyInfo.cs.frame
r7259 r9363 55 55 // [assembly: AssemblyVersion("1.0.*")] 56 56 [assembly: AssemblyVersion("3.3.0.0")] 57 [assembly: AssemblyFileVersion("3.3. 6.$WCREV$")]57 [assembly: AssemblyFileVersion("3.3.7.$WCREV$")] -
branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs
r7877 r9363 177 177 if (!Parameters.ContainsKey("AverageQuality")) { 178 178 Parameters.Add(new OptionalValueParameter<DoubleValue>("AverageQuality", "The expected quality of a random solution.")); 179 AverageQuality = new DoubleValue( Weights.Average() * Distances.Average() * Weights.Rows * Weights.Rows);179 AverageQuality = new DoubleValue(ComputeAverageQuality()); 180 180 } 181 181 #endregion … … 303 303 Operators.Add(new QAPPopulationDiversityAnalyzer()); 304 304 Operators.Add(new QAPExhaustiveSwap2LocalImprovement()); 305 Operators.Add(new QAPSimilarityCalculator()); 305 306 ParameterizeAnalyzers(); 306 307 ParameterizeOperators(); … … 386 387 localOpt.WeightsParameter.ActualName = WeightsParameter.Name; 387 388 } 389 390 QAPSimilarityCalculator similarityCalculator = Operators.OfType<QAPSimilarityCalculator>().SingleOrDefault(); 391 if (similarityCalculator != null) { 392 similarityCalculator.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName; 393 similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName; 394 } 388 395 } 389 396 … … 401 408 402 409 private void UpdateParameterValues() { 403 LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances)); 404 AverageQuality = new DoubleValue(Weights.Average() * Distances.Average() * Weights.Rows * Weights.Rows); 410 Permutation lbSolution; 411 // calculate the optimum of a LAP relaxation and use it as lower bound of our QAP 412 LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances, out lbSolution)); 413 // evalute the LAP optimal solution as if it was a QAP solution 414 var lbSolutionQuality = QAPEvaluator.Apply(lbSolution, Weights, Distances); 415 // in case both qualities are the same it means that the LAP optimum is also a QAP optimum 416 if (LowerBound.Value.IsAlmost(lbSolutionQuality)) { 417 BestKnownSolution = lbSolution; 418 BestKnownQuality = new DoubleValue(LowerBound.Value); 419 } 420 AverageQuality = new DoubleValue(ComputeAverageQuality()); 421 } 422 423 private double ComputeAverageQuality() { 424 double rt = 0, rd = 0, wt = 0, wd = 0; 425 int n = Weights.Rows; 426 for (int i = 0; i < n; i++) 427 for (int j = 0; j < n; j++) { 428 if (i == j) { 429 rd += Distances[i, i]; 430 wd += Weights[i, i]; 431 } else { 432 rt += Distances[i, j]; 433 wt += Weights[i, j]; 434 } 435 } 436 437 return rt * wt / (n * (n - 1)) + rd * wd / n; 405 438 } 406 439 #endregion … … 412 445 Description = data.Description; 413 446 Load(weights, distances); 447 if (data.BestKnownQuality.HasValue) BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value); 414 448 EvaluateAndLoadAssignment(data.BestKnownAssignment); 415 449 OnReset(); … … 426 460 Description = data.Description; 427 461 Load(weights, distances); 462 if (data.BestKnownQuality.HasValue) BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value); 428 463 EvaluateAndLoadAssignment(data.BestKnownTour); 429 464 OnReset();
Note: See TracChangeset
for help on using the changeset viewer.