Changeset 11311 for branches/HeuristicLab.Problems.Orienteering

Timestamp:

08/27/14 10:53:57 (10 years ago)

Author:

pfleck

Message:

#2208 Added distance penalty calculation in OrienteeringEvaluator.

Location:

branches/HeuristicLab.Problems.Orienteering

Files:

• HeuristicLab.Problems.Orienteering.Views/3.3/OrienteeringProblemView.cs (modified) (1 diff)
• HeuristicLab.Problems.Orienteering.Views/3.3/OrienteeringSolutionView.cs (modified) (4 diffs)
• HeuristicLab.Problems.Orienteering/3.3/Analyzers/BestOrienteeringSolutionAnalyser.cs (modified) (7 diffs)
• HeuristicLab.Problems.Orienteering/3.3/Evaluators/OrienteeringEvaluator.cs (modified) (4 diffs)
• HeuristicLab.Problems.Orienteering/3.3/OrienteeringSolution.cs (modified) (7 diffs)

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering.Views/3.3/OrienteeringProblemView.cs

@@ -63 +63 @@
       } else {
         orienteeringSolutionView.Content = new OrienteeringSolution(
-          Content.BestKnownSolution, Content.Coordinates, Content.StartingPoint, Content.TerminusPoint, Content.Scores, Content.BestKnownQuality);
+          Content.BestKnownSolution, Content.Coordinates, Content.StartingPoint, Content.TerminusPoint, Content.Scores, Content.BestKnownQuality, penalty: null);
       }
     }

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering.Views/3.3/OrienteeringSolutionView.cs

@@ -42 +42 @@
     protected override void DeregisterContentEvents() {
       Content.QualityChanged -= new EventHandler(Content_QualityChanged);
+      Content.PenaltyChanged -= new EventHandler(Content_PenaltyChanged);
       Content.CoordinatesChanged -= new EventHandler(Content_CoordinatesChanged);
       Content.StartingPointChanged -= new EventHandler(Content_StartingPointChanged);
@@ -52 +53 @@
       base.RegisterContentEvents();
       Content.QualityChanged += new EventHandler(Content_QualityChanged);
+      Content.PenaltyChanged += new EventHandler(Content_PenaltyChanged);
       Content.CoordinatesChanged += new EventHandler(Content_CoordinatesChanged);
       Content.StartingPointChanged += new EventHandler(Content_StartingPointChanged);
@@ -114 +116 @@
                   tour[i] = points[integerVector[i]];
                 }
-                graphics.DrawLines(Pens.Black, tour);
+                bool visualizePenalty = Content.Penalty != null && Content.Penalty.Value > 0;
+                graphics.DrawLines(visualizePenalty ? Pens.Red : Pens.Black, tour);
               }
 
@@ -154 +157 @@
         qualityViewHost.Content = Content.Quality;
     }
+    private void Content_PenaltyChanged(object sender, EventArgs e) {
+      if (InvokeRequired)
+        Invoke(new EventHandler(Content_PenaltyChanged), sender, e);
+      else
+        GenerateImage();
+    }
     private void Content_CoordinatesChanged(object sender, EventArgs e) {
       if (InvokeRequired)

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Analyzers/BestOrienteeringSolutionAnalyser.cs

@@ -55 +55 @@
       get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
     }
+    public ScopeTreeLookupParameter<DoubleValue> PenaltyParameter {
+      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Penalty"]; }
+    }
     public LookupParameter<OrienteeringSolution> BestSolutionParameter {
       get { return (LookupParameter<OrienteeringSolution>)Parameters["BestSolution"]; }
@@ -66 +69 @@
     public LookupParameter<IntegerVector> BestKnownSolutionParameter {
       get { return (LookupParameter<IntegerVector>)Parameters["BestKnownSolution"]; }
+    }
+    public LookupParameter<DoubleValue> BestKnownSolutionPenaltyParameter {
+      get { return (LookupParameter<DoubleValue>)Parameters["BestKnownSolutionPenalty"]; }
     }
 
@@ -82 +88 @@
       Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));
       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the Orienteering solutions which should be analyzed."));
+      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Penalty", "The applied penalty of the Orienteering solutions."));
       Parameters.Add(new LookupParameter<OrienteeringSolution>("BestSolution", "The best Orienteering solution."));
       Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the best Orienteering solution should be stored."));
       Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this Orienteering instance."));
       Parameters.Add(new LookupParameter<IntegerVector>("BestKnownSolution", "The best known solution of this Orienteering instance."));
+      Parameters.Add(new LookupParameter<DoubleValue>("BestKnownSolutionPenalty", "The penalty of the best known solution of this Orienteering instance."));
     }
 
@@ -91 +99 @@
       var solutions = IntegerVector.ActualValue;
       var qualities = QualityParameter.ActualValue;
+      var penalties = PenaltyParameter.ActualValue;
       var results = ResultsParameter.ActualValue;
       var bestKnownQuality = BestKnownQualityParameter.ActualValue;
@@ -99 +108 @@
         BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIndex].Value);
         BestKnownSolutionParameter.ActualValue = (IntegerVector)solutions[bestIndex].Clone();
+        BestKnownSolutionPenaltyParameter.ActualValue = new DoubleValue(penalties[bestIndex].Value);
       }
 
@@ -113 +123 @@
           terminusPoint,
           scores,
-          new DoubleValue(qualities[bestIndex].Value));
+          new DoubleValue(qualities[bestIndex].Value),
+          new DoubleValue(penalties[bestIndex].Value));
         BestSolutionParameter.ActualValue = solution;
         results.Add(new Result("Best Orienteering Solution", solution));
+        results.Add(new Result("BestKnownSolutionPenalty", solution.Penalty));
       } else {
         if (solution.Quality.Value < qualities[bestIndex].Value) {
@@ -122 +134 @@
           solution.IntegerVector = (IntegerVector)solutions[bestIndex].Clone();
           solution.Quality.Value = qualities[bestIndex].Value;
+          solution.Penalty.Value = penalties[bestIndex].Value;
+          results["BestKnownSolutionPenalty"].Value = solution.Penalty;
         }
       }

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Evaluators/OrienteeringEvaluator.cs

@@ -20 +20 @@
 #endregion
 
+using System.Linq;
+using System.Security.Permissions;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -30 +32 @@
 namespace HeuristicLab.Problems.Orienteering {
   public class OrienteeringEvaluator : InstrumentedOperator, IOrienteeringEvaluator {
+
+    #region ParameterProperties
     public ILookupParameter<DoubleValue> QualityParameter {
       get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
+    }
+    public ILookupParameter<DoubleValue> PenaltyParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["Penalty"]; }
+    }
+    public ILookupParameter<DoubleValue> DistancePenaltyFactorParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["DistancePenaltyFactor"]; }
     }
     public ILookupParameter<IntegerVector> IntegerVectorParameter {
@@ -39 +49 @@
       get { return (ILookupParameter<DoubleArray>)Parameters["Scores"]; }
     }
+    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
+      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
+    }
+    public ILookupParameter<DoubleValue> MaximumDistanceParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["MaximumDistance"]; }
+    }
+    public ILookupParameter<DoubleValue> FixedPenaltyParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["FixedPenalty"]; }
+    }
+    #endregion
 
     [StorableConstructor]
@@ -53 +73 @@
       : base() {
       Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The evaluated quality of the Orienteering solution."));
+      Parameters.Add(new LookupParameter<DoubleValue>("Penalty", "The applied penalty"));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("DistancePenaltyFactor", "The penalty applied per distance violation.", new DoubleValue(0)));
+
       Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The Orienteering Solution given in path representation."));
       Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));
+      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
+      Parameters.Add(new LookupParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
+      Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
     }
 
     public class OrienteeringEvaluation {
       public DoubleValue Quality;
+      public DoubleValue Penalty;
     }
 
-    public static OrienteeringEvaluation Apply(IntegerVector solution, DoubleArray scores) {
-      // TODO distance penalty
-      double score = 0.0;
+    public static OrienteeringEvaluation Apply(IntegerVector solution, DoubleArray scores,
+      DistanceMatrix distances, DoubleValue maximumDistance, DoubleValue fixedPenalty, DoubleValue distancePenaltyFactor) {
 
-      for (int i = 0; i < solution.Length; i++) {
-        score += scores[solution[i]];
-      }
+      double score = solution.Sum(t => scores[t]);
+      double distance = distances.CalculateTourLength(solution.ToList(), fixedPenalty.Value);
+
+      double distanceViolation = distance - maximumDistance.Value;
+
+      double penalty = 0.0;
+      penalty += distanceViolation > 0 ? distanceViolation * distancePenaltyFactor.Value : 0;
+
+      double quality = score - penalty;
 
       return new OrienteeringEvaluation {
-        Quality = new DoubleValue(score)
+        Quality = new DoubleValue(quality),
+        Penalty = new DoubleValue(penalty)
       };
     }
 
     public override IOperation InstrumentedApply() {
-      var evaluation = Apply(IntegerVectorParameter.ActualValue, ScoresParameter.ActualValue);
+      var evaluation = Apply(IntegerVectorParameter.ActualValue, ScoresParameter.ActualValue,
+        DistanceMatrixParameter.ActualValue, MaximumDistanceParameter.ActualValue,
+        FixedPenaltyParameter.ActualValue, DistancePenaltyFactorParameter.ActualValue);
 
       QualityParameter.ActualValue = evaluation.Quality;
+      PenaltyParameter.ActualValue = evaluation.Penalty;
 
       return base.InstrumentedApply();

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/OrienteeringSolution.cs

@@ -90 +90 @@
           if (quality != null) RegisterQualityEvents();
           OnQualityChanged();
+        }
+      }
+    }
+    [Storable]
+    private DoubleValue penalty;
+    public DoubleValue Penalty {
+      get { return penalty; }
+      set {
+        if (penalty != value) {
+          if (penalty != null) DeregisterPenaltyEvents();
+          penalty = value;
+          if (penalty != null) RegisterPenaltyEvents();
+          OnPenaltyChanged();
         }
       }
@@ -102 +115 @@
       this.coordinates = cloner.Clone(original.coordinates);
       this.quality = cloner.Clone(original.quality);
+      this.penalty = cloner.Clone(original.penalty);
       Initialize();
     }
     public OrienteeringSolution(IntegerVector integerVector, DoubleMatrix coordinates, IntValue startingPoint, IntValue terminusPoint,
-      DoubleArray scores, DoubleValue quality)
+      DoubleArray scores, DoubleValue quality, DoubleValue penalty)
       : base() {
       this.integerVector = integerVector;
@@ -113 +127 @@
       this.scores = scores;
       this.quality = quality;
+      this.penalty = penalty;
       Initialize();
     }
@@ -132 +147 @@
       if (scores != null) RegisterScoresEvents();
       if (quality != null) RegisterQualityEvents();
+      if (penalty != null) RegisterPenaltyEvents();
     }
 
@@ -177 +193 @@
     }
 
+    public event EventHandler PenaltyChanged;
+    private void OnPenaltyChanged() {
+      var changed = PenaltyChanged;
+      if (changed != null)
+        changed(this, EventArgs.Empty);
+    }
+
     private void RegisterIntegerVectorEvents() {
       IntegerVector.ItemChanged += new EventHandler<EventArgs<int>>(IntegerVector_ItemChanged);
@@ -219 +242 @@
       Quality.ValueChanged -= new EventHandler(Quality_ValueChanged);
     }
+    private void RegisterPenaltyEvents() {
+      Penalty.ValueChanged += new EventHandler(Penalty_ValueChanged);
+    }
+    private void DeregisterPenaltyEvents() {
+      Penalty.ValueChanged -= new EventHandler(Penalty_ValueChanged);
+    }
 
     private void IntegerVector_ItemChanged(object sender, EventArgs<int> e) {
@@ -246 +275 @@
     private void Quality_ValueChanged(object sender, EventArgs e) {
       OnQualityChanged();
+    }
+    private void Penalty_ValueChanged(object sender, EventArgs e) {
+      OnPenaltyChanged();
     }
     #endregion