Changeset 14653 for branches/OptimizationNetworks

Timestamp:

02/07/17 21:54:23 (8 years ago)

Author:

jkarder

Message:

#2205: worked on optimization networks

• improved ttp evaluation

Location:

branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3

Files:

• Problems/LootProfitProblem.cs (modified) (4 diffs)
• Problems/TourProfitProblem.cs (modified) (4 diffs)
• TtpOrchestratorNode.cs (modified) (1 diff)
• TtpOrchestratorNode1.cs (modified) (3 diffs)
• TtpOrchestratorNode2.cs (modified) (4 diffs)
• TtpOrchestratorNode3.cs (modified) (2 diffs)
• TtpUtils.cs (modified) (4 diffs)

branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/Problems/LootProfitProblem.cs

@@ -47 +47 @@
     public Permutation FixedTspSolution { get; set; }
     [Storable]
-    public int[] Availability { get; set; }
+    public Dictionary<int, int[]> Availability { get; set; }
     [Storable]
     public double RentingRatio { get; set; }
@@ -54 +54 @@
     [Storable]
     public double MaxSpeed { get; set; }
-    [Storable]
-    public TtpUtils.DistanceType DistanceType { get; set; }
 
     [StorableConstructor]
@@ -63 +61 @@
       Ksp = cloner.Clone(original.Ksp);
       FixedTspSolution = cloner.Clone(original.FixedTspSolution);
-      Availability = original.Availability != null ? (int[])original.Availability.Clone() : null;
+      Availability = original.Availability != null ? original.Availability.ToDictionary(k => k.Key, v => (int[])v.Value.Clone()) : null;
       RentingRatio = original.RentingRatio;
       MinSpeed = original.MinSpeed;
       MaxSpeed = original.MaxSpeed;
-      DistanceType = original.DistanceType;
     }
     public LootProfitProblem() : base() {
@@ -80 +77 @@
       return TtpUtils.Evaluate(Tsp, FixedTspSolution.ToArray(),
                                Ksp, vector.ToArray(),
-                               Availability, RentingRatio, MinSpeed, MaxSpeed, DistanceType);
+                               Availability, RentingRatio, MinSpeed, MaxSpeed);
     }
 

branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/Problems/TourProfitProblem.cs

@@ -46 +46 @@
     public BinaryVector FixedKspSolution { get; set; }
     [Storable]
-    public int[] Availability { get; set; }
+    public Dictionary<int, int[]> Availability { get; set; }
     [Storable]
     public double RentingRatio { get; set; }
@@ -53 +53 @@
     [Storable]
     public double MaxSpeed { get; set; }
-    [Storable]
-    public TtpUtils.DistanceType DistanceType { get; set; }
 
     [StorableConstructor]
@@ -62 +60 @@
       Ksp = cloner.Clone(original.Ksp);
       FixedKspSolution = cloner.Clone(original.FixedKspSolution);
-      Availability = original.Availability != null ? (int[])original.Availability.Clone() : null;
+      Availability = original.Availability != null ? original.Availability.ToDictionary(k => k.Key, v => (int[])v.Value.Clone()) : null;
       RentingRatio = original.RentingRatio;
       MinSpeed = original.MinSpeed;
       MaxSpeed = original.MaxSpeed;
-      DistanceType = original.DistanceType;
     }
     public TourProfitProblem() : base() {
@@ -79 +76 @@
       return TtpUtils.Evaluate(Tsp, individual.Permutation().ToArray(),
                                Ksp, FixedKspSolution.ToArray(),
-                               Availability, RentingRatio, MinSpeed, MaxSpeed, DistanceType);
+                               Availability, RentingRatio, MinSpeed, MaxSpeed);
     }
 

branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpOrchestratorNode.cs

@@ -207 +207 @@
       var tsp = TspParameter.Value;
       tsp.Coordinates = new DoubleMatrix(tspCoordinates);
+      tsp.DistanceMatrix = new DistanceMatrix(TtpUtils.GetDistances(tsp.Coordinates, distanceType));
 
       var ksp = KspParameter.Value;

branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpOrchestratorNode1.cs

@@ -90 +90 @@
       var loot = new KnapsackSolution(bestKspSolution, bestKspQuality, kspCapacity, kspWeights, kspValues);
 
+      var availability = TtpUtils.GetAvailability(AvailabilityParameter.Value.ToArray());
+
       var tspMsg = TspSolverOrchestrationPort.PrepareMessage();
       tspMsg["OrchestrationMessage"] = new EnumValue<OrchestrationMessage>(OrchestrationMessage.Prepare | OrchestrationMessage.ClearRuns | OrchestrationMessage.Start);
@@ -96 +98 @@
         Ksp = (BinaryKnapsackProblem)KspParameter.Value.Clone(),
         FixedKspSolution = bestKspSolution,
-        Availability = AvailabilityParameter.Value.ToArray(),
+        Availability = availability,
         RentingRatio = RentingRatioParameter.Value.Value,
         MinSpeed = MinSpeedParameter.Value.Value,
         MaxSpeed = MaxSpeedParameter.Value.Value,
-        DistanceType = distanceType
       };
       tpp.Encoding.Length = TspParameter.Value.Coordinates.Rows;
@@ -114 +115 @@
       #region Analyze
       double objectiveValue = TtpUtils.Evaluate(TspParameter.Value, tour.Permutation.ToArray(), KspParameter.Value, loot.BinaryVector.ToArray(),
-        AvailabilityParameter.Value.ToArray(), RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value, distanceType);
+        availability, RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value);
       ((DoubleValue)message["Quality"]).Value = objectiveValue;
 

branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpOrchestratorNode2.cs

@@ -75 +75 @@
         tsp.Coordinates[i, 1] = (int)Math.Ceiling(tsp.Coordinates[i, 1] * factors[i * 2 + 1]);
       }
+      tsp.DistanceMatrix = new DistanceMatrix(TtpUtils.GetDistances(tsp.Coordinates, distanceType));
 
       var tspMsg = TspSolverOrchestrationPort.PrepareMessage();
@@ -87 +88 @@
       var tour = new PathTSPTour(coordinates, bestTspSolution.Permutation, new DoubleValue(TSPCoordinatesPathEvaluator.Apply(new TSPEuclideanPathEvaluator(), coordinates, bestTspSolution.Permutation)));
 
+      var availability = TtpUtils.GetAvailability(AvailabilityParameter.Value.ToArray());
+
       var kspMsg = KspSolverOrchestrationPort.PrepareMessage();
       kspMsg["OrchestrationMessage"] = new EnumValue<OrchestrationMessage>(OrchestrationMessage.Prepare | OrchestrationMessage.ClearRuns | OrchestrationMessage.Start);
@@ -93 +96 @@
         Ksp = (BinaryKnapsackProblem)KspParameter.Value.Clone(),
         FixedTspSolution = bestTspSolution.Permutation,
-        Availability = AvailabilityParameter.Value.ToArray(),
+        Availability = availability,
         RentingRatio = RentingRatioParameter.Value.Value,
         MinSpeed = MinSpeedParameter.Value.Value,
         MaxSpeed = MaxSpeedParameter.Value.Value,
-        DistanceType = distanceType
       };
       lpp.Encoding.Length = KspParameter.Value.Length;
@@ -115 +117 @@
       #region Analyze
       double objectiveValue = TtpUtils.Evaluate(TspParameter.Value, tour.Permutation.ToArray(), KspParameter.Value, loot.BinaryVector.ToArray(),
-        AvailabilityParameter.Value.ToArray(), RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value, distanceType);
+        availability, RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value);
       ((DoubleValue)message["Quality"]).Value = objectiveValue;
 

branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpOrchestratorNode3.cs

@@ -97 +97 @@
         tsp.Coordinates[j, 1] = (int)Math.Ceiling(tsp.Coordinates[j, 1] * factors[fi + j * 2 + 1]);
       }
+      tsp.DistanceMatrix = new DistanceMatrix(TtpUtils.GetDistances(tsp.Coordinates, distanceType));
 
       var tspMsg = TspSolverOrchestrationPort.PrepareMessage();
@@ -111 +112 @@
       #region Analyze
       double objectiveValue = TtpUtils.Evaluate(TspParameter.Value, tour.Permutation.ToArray(), KspParameter.Value, loot.BinaryVector.ToArray(),
-        AvailabilityParameter.Value.ToArray(), RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value, distanceType);
+        TtpUtils.GetAvailability(AvailabilityParameter.Value.ToArray()), RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value);
       ((DoubleValue)message["Quality"]).Value = objectiveValue;
 

branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpUtils.cs

@@ -1 +1 @@
 using System;
+using System.Collections.Generic;
 using System.IO;
 using System.Linq;
+using HeuristicLab.Data;
 using HeuristicLab.Problems.TravelingSalesman;
 
@@ -68 +70 @@
     }
 
-    public static double Evaluate(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, int[] availability, double rentingRatio, double minSpeed, double maxSpeed, DistanceType distanceType) {
-      bool feasible;
-      return Evaluate(tsp, tour, ksp, loot, availability, rentingRatio, minSpeed, maxSpeed, distanceType, out feasible);
-    }
-
-    public static double Evaluate(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, int[] availability, double rentingRatio, double minSpeed, double maxSpeed, DistanceType distanceType, out bool feasible) {
+    public static double Evaluate(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, Dictionary<int, int[]> availability, double rentingRatio, double minSpeed, double maxSpeed) {
       double collectedWeight = 0.0;
       double objectiveValue = 0.0;
@@ -86 +83 @@
       while (cityIdx != hideoutIdx) {
         double oldCollectedWeight = collectedWeight;
-        var availableItems = availability.Select((c, i) => new { CityIdx = c, ItemIdx = i }).Where(x => x.CityIdx == tour[cityIdx]);
 
-        foreach (var item in availableItems) {
-          if (!loot[item.ItemIdx]) continue;
-          collectedWeight += ksp.Weights[item.ItemIdx];
-          objectiveValue += ksp.Values[item.ItemIdx];
+        foreach (var itemIdx in availability[tour[cityIdx]]) {
+          if (!loot[itemIdx]) continue;
+          collectedWeight += ksp.Weights[itemIdx];
+          objectiveValue += ksp.Values[itemIdx];
         }
 
-        objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[cityIdx], distanceType) * rentingRatio /
-                          (maxSpeed - speedCoefficient * oldCollectedWeight);
+        objectiveValue -= tsp.DistanceMatrix[tour[lastCityIdx], tour[cityIdx]] * rentingRatio / (maxSpeed - speedCoefficient * oldCollectedWeight);
         lastCityIdx = cityIdx;
         cityIdx = (cityIdx + 1) % tour.Length;
       }
 
-      objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[hideoutIdx], distanceType) * rentingRatio /
-                        (maxSpeed - speedCoefficient * collectedWeight);
+      objectiveValue -= tsp.DistanceMatrix[tour[lastCityIdx], tour[hideoutIdx]] * rentingRatio / (maxSpeed - speedCoefficient * collectedWeight);
 
-      feasible = collectedWeight <= ksp.KnapsackCapacity.Value;
+      bool feasible = collectedWeight <= ksp.KnapsackCapacity.Value;
       if (!feasible) objectiveValue = infeasibleBaseLine - collectedWeight;
 
@@ -109 +103 @@
     }
 
-    private static double Distance(double[,] coords, int fromIdx, int toIdx, DistanceType distanceType) {
-      double fromX = coords[fromIdx, 0], fromY = coords[fromIdx, 1],
-             toX = coords[toIdx, 0], toY = coords[toIdx, 1];
+    public static Dictionary<int, int[]> GetAvailability(int[] availability) {
+      return availability.Select((c, i) => Tuple.Create(c, i)).GroupBy(x => x.Item1).ToDictionary(k => k.Key, v => v.Select(x => x.Item2).ToArray());
+    }
+
+    public static double[,] GetDistances(DoubleMatrix coordinates, DistanceType distanceType) {
+      int nrOfNodes = coordinates.Rows;
+      var distances = new double[nrOfNodes, nrOfNodes];
+
+      for (int i = 1; i < nrOfNodes; i++)
+        for (int j = 0; j < i; j++)
+          distances[i, j] = distances[j, i] = Distance(coordinates, i, j, distanceType);
+
+      return distances;
+    }
+
+    private static double Distance(DoubleMatrix coordinates, int fromIdx, int toIdx, DistanceType distanceType) {
+      double fromX = coordinates[fromIdx, 0];
+      double fromY = coordinates[fromIdx, 1];
+      double toX = coordinates[toIdx, 0];
+      double toY = coordinates[toIdx, 1];
+
       double distance = Math.Sqrt((toX - fromX) * (toX - fromX) + (toY - fromY) * (toY - fromY));
+
       switch (distanceType) {
         case DistanceType.CEIL_2D: return (int)Math.Ceiling(distance);
         case DistanceType.EUC_2D: return distance;
-        default: return 0.0;
+        default: return double.NaN;
       }
     }