Changeset 14653 for branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpUtils.cs

Timestamp:

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

Author:

jkarder

Message:

#2205: worked on optimization networks

• improved ttp evaluation

File:

• branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpUtils.cs (modified) (4 diffs)

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;
       }
     }