Changeset 15507 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3

Timestamp:

12/11/17 15:42:12 (7 years ago)

Author:

abeham

Message:

#1614:

• fixed some bugs introduced in last commit (project file, tests)
• fixed ApproximateLocalSearch due to change in move evaluator that outputs an absolute quality of the move and not a delta
• added evaluated solution counting to approximate local search
• GRASP+PR: restructured main loop and combined iteration initialization with variable creator outside

Location:

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3

Files:

• Evaluation/GQAPNMoveEvaluator.cs (modified) (1 diff)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj (modified) (1 diff)
• Operators/LocalImprovers/ApproximateLocalSearch.cs (modified) (5 diffs)

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluation/GQAPNMoveEvaluator.cs

@@ -130 +130 @@
 
       MoveEvaluationParameter.ActualValue = moveEvaluation;
+      MoveQualityParameter.ActualValue = new DoubleValue(problemInstance.ToSingleObjective(moveEvaluation));
       return base.Apply();
     }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj

@@ -102 +102 @@
     <Compile Include="GQAPAssignment.cs" />
     <Compile Include="GQAPInstance.cs" />
+    <Compile Include="Interfaces\Parameter\IAssignmentAwareGQAPOperator.cs" />
     <Compile Include="Operators\Crossovers\CordeauCrossover.cs" />
     <Compile Include="SolutionCreators\SlackMinimizationSolutionCreator.cs" />

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs

@@ -106 +106 @@
     /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
     /// <param name="problemInstance">The problem instance that contains the data.</param>
+    /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
     /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
     public static void Apply(IRandom random, IntegerVector assignment,
       DoubleValue quality, ref Evaluation evaluation, IntValue maxCLS, IntValue maximumIterations,
-      GQAPInstance problemInstance, PercentValue oneMoveProbability) {
+      GQAPInstance problemInstance, IntValue evaluatedSolutions, PercentValue oneMoveProbability) {
       var capacities = problemInstance.Capacities;
       var demands = problemInstance.Demands;
-      //var weights = problemInstance.Weights;
-      //var distances = problemInstance.Distances;
-      //var installationCosts = problemInstance.InstallationCosts;
+      var evaluations = 0.0;
+      var deltaEvaluationFactor = 1.0 / assignment.Length;
       while (true) {
         int count = 0;
@@ -126 +126 @@
           
           var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
+          evaluations += move.NewAssignments.Count * deltaEvaluationFactor;
           double moveQuality = problemInstance.ToSingleObjective(moveEval);
 
-          if (moveEval.ExcessDemand <= 0.0 && moveQuality < 0.0) {
+          if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality.Value) {
             CLS.Add(Tuple.Create(move, moveQuality, moveEval));
             sum += 1.0 / moveQuality;
@@ -135 +136 @@
         } while (CLS.Count < maxCLS.Value && count < maximumIterations.Value);
 
-        if (CLS.Count == 0)
+        if (CLS.Count == 0) {
+          evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
           return; // END
-        else {
+        } else {
           var ball = random.NextDouble() * sum;
           var selected = CLS.Last();
@@ -148 +150 @@
           }
           NMoveMaker.Apply(assignment, selected.Item1);
-          quality.Value += selected.Item2;
+          quality.Value = selected.Item2;
           evaluation = selected.Item3;
         }
@@ -163 +165 @@
         MaximumIterationsParameter.ActualValue,
         ProblemInstanceParameter.ActualValue,
+        EvaluatedSolutionsParameter.ActualValue,
         OneMoveProbabilityParameter.ActualValue);
       EvaluationParameter.ActualValue = evaluation;