Changeset 15504 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluation/GQAPNMoveEvaluator.cs

Timestamp:

12/10/17 22:11:10 (6 years ago)

Author:

abeham

Message:

#1614: refactored code

• change problem to derive from basic problem
• using a combined instance class instead of individual parameters

Location:

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

Files:

• . (moved) (moved from branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluators)
• GQAPNMoveEvaluator.cs (modified) (7 diffs)

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

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -25 +27 @@
 using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Operators;
-using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -32 +33 @@
   [Item("N-Move Evaluator", "Evaluates an N-Move.")]
   [StorableClass]
-  public class GQAPNMoveEvaluator : SingleSuccessorOperator, IGQAPNMoveEvaluator, IAssignmentAwareGQAPOperator,
-  IQualityAwareGQAPOperator, ITransportationCostsAwareGQAPOperator,
-  IExpectedRandomQualityAwareGQAPOperator, IWeightsAwareGQAPOperator, IDistancesAwareGQAPOperator,
-  IInstallationCostsAwareGQAPOperator, IDemandsAwareGQAPOperator, ICapacitiesAwareGQAPOperator,
-  IEvaluatorAwareGQAPOperator {
+  public class GQAPNMoveEvaluator : SingleSuccessorOperator, IGQAPNMoveEvaluator,
+    IQualityAwareGQAPOperator, IProblemInstanceAwareGQAPOperator {
 
     #region Parameter Descriptions
     public static readonly string MoveQualityDescription = "The quality of the move if it would be applied.";
-    public static readonly string MoveFlowDistanceQualityDescription = "The quality of the move regarding the flow-distance criteria.";
-    public static readonly string MoveInstallationQualityDescription = "The quality of the move regarding the installation costs.";
-    public static readonly string MoveOverbookedCapacityDescription = "The sum of the overbooked capacities of the move relative to the capacity of each location.";
+    public static readonly string MoveEvaluationDescription = "The results of evaluating the move.";
     #endregion
 
     #region Parameter Properties
-    ILookupParameter<BoolValue> IQualityAwareGQAPOperator.MaximizationParameter {
-      get { return MaximizationParameter; }
-    }
-    ILookupParameter<BoolValue> IGQAPMoveEvaluator.MaximizationParameter {
-      get { return MaximizationParameter; }
-    }
-    public ILookupParameter<BoolValue> MaximizationParameter {
-      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
-    }
     public ILookupParameter<DoubleValue> MoveQualityParameter {
       get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
     }
-    public ILookupParameter<DoubleValue> MoveFlowDistanceQualityParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["MoveFlowDistanceQuality"]; }
-    }
-    public ILookupParameter<DoubleValue> MoveInstallationQualityParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["MoveInstallationQuality"]; }
-    }
-    public ILookupParameter<DoubleValue> MoveOverbookedCapacityParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["MoveOverbookedCapacity"]; }
+    public ILookupParameter<Evaluation> MoveEvaluationParameter {
+      get { return (ILookupParameter<Evaluation>)Parameters["MoveEvaluation"]; }
     }
     public ILookupParameter<NMove> MoveParameter {
@@ -73 +54 @@
       get { return (ILookupParameter<IntegerVector>)Parameters["Assignment"]; }
     }
-    ILookupParameter<DoubleValue> ISingleObjectiveMoveEvaluator.QualityParameter {
-      get { return QualityParameter; }
-    }
-    ILookupParameter<DoubleValue> IQualityAwareGQAPOperator.QualityParameter {
-      get { return QualityParameter; }
-    }
     public ILookupParameter<DoubleValue> QualityParameter {
       get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
     }
-    public ILookupParameter<DoubleValue> FlowDistanceQualityParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
+    public ILookupParameter<Evaluation> EvaluationParameter {
+      get { return (ILookupParameter<Evaluation>)Parameters["Evaluation"]; }
     }
-    public ILookupParameter<DoubleValue> InstallationQualityParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
-    }
-    public ILookupParameter<DoubleValue> OverbookedCapacityParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
-    }
-    public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
-      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
-    }
-    public IValueLookupParameter<DoubleValue> ExpectedRandomQualityParameter {
-      get { return (IValueLookupParameter<DoubleValue>)Parameters["ExpectedRandomQuality"]; }
-    }
-    public ILookupParameter<DoubleMatrix> WeightsParameter {
-      get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
-    }
-    public ILookupParameter<DoubleMatrix> DistancesParameter {
-      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
-    }
-    public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
-      get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
-    }
-    public ILookupParameter<DoubleArray> DemandsParameter {
-      get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }
-    }
-    public ILookupParameter<DoubleArray> CapacitiesParameter {
-      get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }
-    }
-    public IValueLookupParameter<IGQAPEvaluator> EvaluatorParameter {
-      get { return (IValueLookupParameter<IGQAPEvaluator>)Parameters["Evaluator"]; }
+    public ILookupParameter<GQAPInstance> ProblemInstanceParameter {
+      get { return (ILookupParameter<GQAPInstance>)Parameters["ProblemInstance"]; }
     }
     #endregion
@@ -124 +72 @@
       Parameters.Add(new LookupParameter<IntegerVector>("Assignment", GQAPSolutionCreator.AssignmentDescription));
       Parameters.Add(new LookupParameter<NMove>("Move", GQAPNMoveGenerator.MoveDescription));
-      Parameters.Add(new LookupParameter<BoolValue>("Maximization", GeneralizedQuadraticAssignmentProblem.MaximizationDescription));
-      Parameters.Add(new LookupParameter<DoubleValue>("Quality", GQAPEvaluator.QualityDescription));
-      Parameters.Add(new LookupParameter<DoubleValue>("FlowDistanceQuality", GQAPEvaluator.FlowDistanceQualityDescription));
-      Parameters.Add(new LookupParameter<DoubleValue>("InstallationQuality", GQAPEvaluator.InstallationQualityDescription));
-      Parameters.Add(new LookupParameter<DoubleValue>("OverbookedCapacity", GQAPEvaluator.OverbookedCapacityDescription));
+      Parameters.Add(new LookupParameter<DoubleValue>("Quality", ""));
+      Parameters.Add(new LookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription));
       Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", MoveQualityDescription));
-      Parameters.Add(new LookupParameter<DoubleValue>("MoveFlowDistanceQuality", MoveFlowDistanceQualityDescription));
-      Parameters.Add(new LookupParameter<DoubleValue>("MoveInstallationQuality", MoveInstallationQualityDescription));
-      Parameters.Add(new LookupParameter<DoubleValue>("MoveOverbookedCapacity", MoveOverbookedCapacityDescription));
-      Parameters.Add(new ValueLookupParameter<DoubleValue>("ExpectedRandomQuality", GeneralizedQuadraticAssignmentProblem.ExpectedRandomQualityDescription));
-      Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
-      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", GeneralizedQuadraticAssignmentProblem.WeightsDescription));
-      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", GeneralizedQuadraticAssignmentProblem.DistancesDescription));
-      Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", GeneralizedQuadraticAssignmentProblem.InstallationCostsDescription));
-      Parameters.Add(new LookupParameter<DoubleArray>("Demands", GeneralizedQuadraticAssignmentProblem.DemandsDescription));
-      Parameters.Add(new LookupParameter<DoubleArray>("Capacities", GeneralizedQuadraticAssignmentProblem.CapacitiesDescription));
-      Parameters.Add(new ValueLookupParameter<IGQAPEvaluator>("Evaluator", "The evaluator that is used to evaluate GQAP solutions."));
+      Parameters.Add(new LookupParameter<Evaluation>("MoveEvaluation", MoveEvaluationDescription));
+      Parameters.Add(new LookupParameter<GQAPInstance>("ProblemInstance", GQAP.ProblemInstanceDescription));
     }
 
@@ -147 +83 @@
     }
 
-    public static double Evaluate(NMove move, IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
-      DoubleArray demands, DoubleArray capacities, double transportationCosts, double expectedRandomQuality, IGQAPEvaluator evaluator) {
-      double moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity;
-      Evaluate(move, assignment, weights, distances, installationCosts, demands, capacities, evaluator,
-        out moveFlowDistanceQuality, out moveInstallationQuality, out moveOverbookedCapacity);
-      return evaluator.GetFitness(moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity,
-        transportationCosts, expectedRandomQuality);
-    }
-
-    public static void Evaluate(NMove move, IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
-      DoubleArray demands, DoubleArray capacities, IGQAPEvaluator evaluator, out double moveFlowDistanceQuality, out double moveInstallationQuality, out double moveOverbookedCapacity) {
-      moveFlowDistanceQuality = moveInstallationQuality = moveOverbookedCapacity = 0.0;
+    public static Evaluation Evaluate(NMove move, IntegerVector assignment, Evaluation evaluation, GQAPInstance problemInstance) {
       int moves = move.N;
-      var slack = (DoubleArray)capacities.Clone();
-      var oldSlack = (DoubleArray)slack.Clone();
-      bool first = true;
+      var newEvaluation = new Evaluation() {
+        ExcessDemand = evaluation.ExcessDemand,
+        FlowCosts = evaluation.FlowCosts,
+        InstallationCosts = evaluation.InstallationCosts,
+        Slack = evaluation.Slack.ToArray()
+      };
       foreach (var kvp in move.NewAssignments) {
         int equip = kvp.Key;
         int newLoc = kvp.Value;
-        moveInstallationQuality -= installationCosts[equip, assignment[equip]];
-        moveInstallationQuality += installationCosts[equip, newLoc];
+        int oldLoc = assignment[equip];
+        var equipDemand = problemInstance.Demands[equip];
+        newEvaluation.InstallationCosts -= problemInstance.InstallationCosts[equip, oldLoc];
+        newEvaluation.InstallationCosts += problemInstance.InstallationCosts[equip, newLoc];
         for (int j = 0; j < assignment.Length; j++) {
           if (!move.NewAssignments.ContainsKey(j)) {
-            moveFlowDistanceQuality += weights[equip, j] * distances[newLoc, assignment[j]];
-            moveFlowDistanceQuality -= weights[equip, j] * distances[assignment[equip], assignment[j]];
-            moveFlowDistanceQuality += weights[j, equip] * distances[assignment[j], newLoc];
-            moveFlowDistanceQuality -= weights[j, equip] * distances[assignment[j], assignment[equip]];
-            if (first) { // only once for each untouched equipment deduct the demand from the capacity
-              slack[assignment[j]] -= demands[j];
-              oldSlack[assignment[j]] -= demands[j];
-            }
+            newEvaluation.FlowCosts += problemInstance.Weights[equip, j] * problemInstance.Distances[newLoc, assignment[j]];
+            newEvaluation.FlowCosts -= problemInstance.Weights[equip, j] * problemInstance.Distances[oldLoc, assignment[j]];
+            newEvaluation.FlowCosts += problemInstance.Weights[j, equip] * problemInstance.Distances[assignment[j], newLoc];
+            newEvaluation.FlowCosts -= problemInstance.Weights[j, equip] * problemInstance.Distances[assignment[j], oldLoc];
           } else {
-            moveFlowDistanceQuality += weights[equip, j] * distances[newLoc, move.NewAssignments[j]];
-            moveFlowDistanceQuality -= weights[equip, j] * distances[assignment[equip], assignment[j]];
+            newEvaluation.FlowCosts += problemInstance.Weights[equip, j] * problemInstance.Distances[newLoc, move.NewAssignments[j]];
+            newEvaluation.FlowCosts -= problemInstance.Weights[equip, j] * problemInstance.Distances[oldLoc, assignment[j]];
           }
         }
-        first = false;
-        slack[newLoc] -= demands[equip];
-        oldSlack[assignment[equip]] -= demands[equip];
+        newEvaluation.Slack[oldLoc] += equipDemand;
+        if (newEvaluation.Slack[oldLoc] < equipDemand)
+          newEvaluation.ExcessDemand -= Math.Min(equipDemand, equipDemand - newEvaluation.Slack[oldLoc]);
+        newEvaluation.Slack[newLoc] -= equipDemand;
+        if (newEvaluation.Slack[newLoc] < 0)
+          newEvaluation.ExcessDemand += Math.Min(equipDemand, -newEvaluation.Slack[newLoc]);
       }
 
-      moveOverbookedCapacity = evaluator.EvaluateOverbooking(slack, capacities) - evaluator.EvaluateOverbooking(oldSlack, capacities);
+      return newEvaluation;
     }
 
     public override IOperation Apply() {
-      var evaluator = EvaluatorParameter.ActualValue;
-      double moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity;
-      double quality = QualityParameter.ActualValue.Value;
-      double transportationCosts = TransportationCostsParameter.ActualValue.Value;
-      double expectedRandomQuality = ExpectedRandomQualityParameter.ActualValue.Value;
+      var problemInstance = ProblemInstanceParameter.ActualValue;
+      var evaluation = EvaluationParameter.ActualValue;
 
-      double flowDistanceQuality = FlowDistanceQualityParameter.ActualValue.Value;
-      double installationQuality = InstallationQualityParameter.ActualValue.Value;
-      double overbookedCapacity = OverbookedCapacityParameter.ActualValue.Value;
+      var moveEvaluation = Evaluate(MoveParameter.ActualValue,
+               AssignmentParameter.ActualValue,
+               evaluation,
+               problemInstance);
 
-      Evaluate(MoveParameter.ActualValue,
-               AssignmentParameter.ActualValue,
-               WeightsParameter.ActualValue, DistancesParameter.ActualValue,
-               InstallationCostsParameter.ActualValue,
-               DemandsParameter.ActualValue, CapacitiesParameter.ActualValue,
-               evaluator,
-               out moveFlowDistanceQuality, out moveInstallationQuality, out moveOverbookedCapacity);
-
-      MoveFlowDistanceQualityParameter.ActualValue = new DoubleValue(flowDistanceQuality + moveFlowDistanceQuality);
-      MoveInstallationQualityParameter.ActualValue = new DoubleValue(installationQuality + moveInstallationQuality);
-      MoveOverbookedCapacityParameter.ActualValue = new DoubleValue(overbookedCapacity + moveOverbookedCapacity);
-
-      MoveQualityParameter.ActualValue = new DoubleValue(evaluator.GetFitness(
-        flowDistanceQuality + moveFlowDistanceQuality,
-        installationQuality + moveInstallationQuality,
-        overbookedCapacity + moveOverbookedCapacity,
-        transportationCosts, expectedRandomQuality));
+      MoveEvaluationParameter.ActualValue = moveEvaluation;
       return base.Apply();
     }