Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
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:
7 edited

Legend:

Unmodified
Added
Removed

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

    r14629 r14653  
    4747    public Permutation FixedTspSolution { get; set; }
    4848    [Storable]
    49     public int[] Availability { get; set; }
     49    public Dictionary<int, int[]> Availability { get; set; }
    5050    [Storable]
    5151    public double RentingRatio { get; set; }
    … …  
    5454    [Storable]
    5555    public double MaxSpeed { get; set; }
    56     [Storable]
    57     public TtpUtils.DistanceType DistanceType { get; set; }
    5856
    5957    [StorableConstructor]
    … …  
    6361      Ksp = cloner.Clone(original.Ksp);
    6462      FixedTspSolution = cloner.Clone(original.FixedTspSolution);
    65       Availability = original.Availability != null ? (int[])original.Availability.Clone() : null;
     63      Availability = original.Availability != null ? original.Availability.ToDictionary(k => k.Key, v => (int[])v.Value.Clone()) : null;
    6664      RentingRatio = original.RentingRatio;
    6765      MinSpeed = original.MinSpeed;
    6866      MaxSpeed = original.MaxSpeed;
    69       DistanceType = original.DistanceType;
    7067    }
    7168    public LootProfitProblem() : base() {
    … …  
    8077      return TtpUtils.Evaluate(Tsp, FixedTspSolution.ToArray(),
    8178                               Ksp, vector.ToArray(),
    82                                Availability, RentingRatio, MinSpeed, MaxSpeed, DistanceType);
     79                               Availability, RentingRatio, MinSpeed, MaxSpeed);
    8380    }
    8481

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

    r14629 r14653  
    4646    public BinaryVector FixedKspSolution { get; set; }
    4747    [Storable]
    48     public int[] Availability { get; set; }
     48    public Dictionary<int, int[]> Availability { get; set; }
    4949    [Storable]
    5050    public double RentingRatio { get; set; }
    … …  
    5353    [Storable]
    5454    public double MaxSpeed { get; set; }
    55     [Storable]
    56     public TtpUtils.DistanceType DistanceType { get; set; }
    5755
    5856    [StorableConstructor]
    … …  
    6260      Ksp = cloner.Clone(original.Ksp);
    6361      FixedKspSolution = cloner.Clone(original.FixedKspSolution);
    64       Availability = original.Availability != null ? (int[])original.Availability.Clone() : null;
     62      Availability = original.Availability != null ? original.Availability.ToDictionary(k => k.Key, v => (int[])v.Value.Clone()) : null;
    6563      RentingRatio = original.RentingRatio;
    6664      MinSpeed = original.MinSpeed;
    6765      MaxSpeed = original.MaxSpeed;
    68       DistanceType = original.DistanceType;
    6966    }
    7067    public TourProfitProblem() : base() {
    … …  
    7976      return TtpUtils.Evaluate(Tsp, individual.Permutation().ToArray(),
    8077                               Ksp, FixedKspSolution.ToArray(),
    81                                Availability, RentingRatio, MinSpeed, MaxSpeed, DistanceType);
     78                               Availability, RentingRatio, MinSpeed, MaxSpeed);
    8279    }
    8380

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

    r14628 r14653  
    207207      var tsp = TspParameter.Value;
    208208      tsp.Coordinates = new DoubleMatrix(tspCoordinates);
     209      tsp.DistanceMatrix = new DistanceMatrix(TtpUtils.GetDistances(tsp.Coordinates, distanceType));
    209210
    210211      var ksp = KspParameter.Value;

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

    r14628 r14653  
    9090      var loot = new KnapsackSolution(bestKspSolution, bestKspQuality, kspCapacity, kspWeights, kspValues);
    9191
     92      var availability = TtpUtils.GetAvailability(AvailabilityParameter.Value.ToArray());
     93
    9294      var tspMsg = TspSolverOrchestrationPort.PrepareMessage();
    9395      tspMsg["OrchestrationMessage"] = new EnumValue<OrchestrationMessage>(OrchestrationMessage.Prepare | OrchestrationMessage.ClearRuns | OrchestrationMessage.Start);
    … …  
    9698        Ksp = (BinaryKnapsackProblem)KspParameter.Value.Clone(),
    9799        FixedKspSolution = bestKspSolution,
    98         Availability = AvailabilityParameter.Value.ToArray(),
     100        Availability = availability,
    99101        RentingRatio = RentingRatioParameter.Value.Value,
    100102        MinSpeed = MinSpeedParameter.Value.Value,
    101103        MaxSpeed = MaxSpeedParameter.Value.Value,
    102         DistanceType = distanceType
    103104      };
    104105      tpp.Encoding.Length = TspParameter.Value.Coordinates.Rows;
    … …  
    114115      #region Analyze
    115116      double objectiveValue = TtpUtils.Evaluate(TspParameter.Value, tour.Permutation.ToArray(), KspParameter.Value, loot.BinaryVector.ToArray(),
    116         AvailabilityParameter.Value.ToArray(), RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value, distanceType);
     117        availability, RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value);
    117118      ((DoubleValue)message["Quality"]).Value = objectiveValue;
    118119

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

    r14628 r14653  
    7575        tsp.Coordinates[i, 1] = (int)Math.Ceiling(tsp.Coordinates[i, 1] * factors[i * 2 + 1]);
    7676      }
     77      tsp.DistanceMatrix = new DistanceMatrix(TtpUtils.GetDistances(tsp.Coordinates, distanceType));
    7778
    7879      var tspMsg = TspSolverOrchestrationPort.PrepareMessage();
    … …  
    8788      var tour = new PathTSPTour(coordinates, bestTspSolution.Permutation, new DoubleValue(TSPCoordinatesPathEvaluator.Apply(new TSPEuclideanPathEvaluator(), coordinates, bestTspSolution.Permutation)));
    8889
     90      var availability = TtpUtils.GetAvailability(AvailabilityParameter.Value.ToArray());
     91
    8992      var kspMsg = KspSolverOrchestrationPort.PrepareMessage();
    9093      kspMsg["OrchestrationMessage"] = new EnumValue<OrchestrationMessage>(OrchestrationMessage.Prepare | OrchestrationMessage.ClearRuns | OrchestrationMessage.Start);
    … …  
    9396        Ksp = (BinaryKnapsackProblem)KspParameter.Value.Clone(),
    9497        FixedTspSolution = bestTspSolution.Permutation,
    95         Availability = AvailabilityParameter.Value.ToArray(),
     98        Availability = availability,
    9699        RentingRatio = RentingRatioParameter.Value.Value,
    97100        MinSpeed = MinSpeedParameter.Value.Value,
    98101        MaxSpeed = MaxSpeedParameter.Value.Value,
    99         DistanceType = distanceType
    100102      };
    101103      lpp.Encoding.Length = KspParameter.Value.Length;
    … …  
    115117      #region Analyze
    116118      double objectiveValue = TtpUtils.Evaluate(TspParameter.Value, tour.Permutation.ToArray(), KspParameter.Value, loot.BinaryVector.ToArray(),
    117         AvailabilityParameter.Value.ToArray(), RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value, distanceType);
     119        availability, RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value);
    118120      ((DoubleValue)message["Quality"]).Value = objectiveValue;
    119121

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

    r14629 r14653  
    9797        tsp.Coordinates[j, 1] = (int)Math.Ceiling(tsp.Coordinates[j, 1] * factors[fi + j * 2 + 1]);
    9898      }
     99      tsp.DistanceMatrix = new DistanceMatrix(TtpUtils.GetDistances(tsp.Coordinates, distanceType));
    99100
    100101      var tspMsg = TspSolverOrchestrationPort.PrepareMessage();
    … …  
    111112      #region Analyze
    112113      double objectiveValue = TtpUtils.Evaluate(TspParameter.Value, tour.Permutation.ToArray(), KspParameter.Value, loot.BinaryVector.ToArray(),
    113         AvailabilityParameter.Value.ToArray(), RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value, distanceType);
     114        TtpUtils.GetAvailability(AvailabilityParameter.Value.ToArray()), RentingRatioParameter.Value.Value, MinSpeedParameter.Value.Value, MaxSpeedParameter.Value.Value);
    114115      ((DoubleValue)message["Quality"]).Value = objectiveValue;
    115116

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

    r14604 r14653  
    11using System;
     2using System.Collections.Generic;
    23using System.IO;
    34using System.Linq;
     5using HeuristicLab.Data;
    46using HeuristicLab.Problems.TravelingSalesman;
    57
    … …  
    6870    }
    6971
    70     public static double Evaluate(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, int[] availability, double rentingRatio, double minSpeed, double maxSpeed, DistanceType distanceType) {
    71       bool feasible;
    72       return Evaluate(tsp, tour, ksp, loot, availability, rentingRatio, minSpeed, maxSpeed, distanceType, out feasible);
    73     }
    74 
    75     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) {
     72    public static double Evaluate(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, Dictionary<int, int[]> availability, double rentingRatio, double minSpeed, double maxSpeed) {
    7673      double collectedWeight = 0.0;
    7774      double objectiveValue = 0.0;
    … …  
    8683      while (cityIdx != hideoutIdx) {
    8784        double oldCollectedWeight = collectedWeight;
    88         var availableItems = availability.Select((c, i) => new { CityIdx = c, ItemIdx = i }).Where(x => x.CityIdx == tour[cityIdx]);
    8985
    90         foreach (var item in availableItems) {
    91           if (!loot[item.ItemIdx]) continue;
    92           collectedWeight += ksp.Weights[item.ItemIdx];
    93           objectiveValue += ksp.Values[item.ItemIdx];
     86        foreach (var itemIdx in availability[tour[cityIdx]]) {
     87          if (!loot[itemIdx]) continue;
     88          collectedWeight += ksp.Weights[itemIdx];
     89          objectiveValue += ksp.Values[itemIdx];
    9490        }
    9591
    96         objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[cityIdx], distanceType) * rentingRatio /
    97                           (maxSpeed - speedCoefficient * oldCollectedWeight);
     92        objectiveValue -= tsp.DistanceMatrix[tour[lastCityIdx], tour[cityIdx]] * rentingRatio / (maxSpeed - speedCoefficient * oldCollectedWeight);
    9893        lastCityIdx = cityIdx;
    9994        cityIdx = (cityIdx + 1) % tour.Length;
    10095      }
    10196
    102       objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[hideoutIdx], distanceType) * rentingRatio /
    103                         (maxSpeed - speedCoefficient * collectedWeight);
     97      objectiveValue -= tsp.DistanceMatrix[tour[lastCityIdx], tour[hideoutIdx]] * rentingRatio / (maxSpeed - speedCoefficient * collectedWeight);
    10498
    105       feasible = collectedWeight <= ksp.KnapsackCapacity.Value;
     99      bool feasible = collectedWeight <= ksp.KnapsackCapacity.Value;
    106100      if (!feasible) objectiveValue = infeasibleBaseLine - collectedWeight;
    107101
    … …  
    109103    }
    110104
    111     private static double Distance(double[,] coords, int fromIdx, int toIdx, DistanceType distanceType) {
    112       double fromX = coords[fromIdx, 0], fromY = coords[fromIdx, 1],
    113              toX = coords[toIdx, 0], toY = coords[toIdx, 1];
     105    public static Dictionary<int, int[]> GetAvailability(int[] availability) {
     106      return availability.Select((c, i) => Tuple.Create(c, i)).GroupBy(x => x.Item1).ToDictionary(k => k.Key, v => v.Select(x => x.Item2).ToArray());
     107    }
     108
     109    public static double[,] GetDistances(DoubleMatrix coordinates, DistanceType distanceType) {
     110      int nrOfNodes = coordinates.Rows;
     111      var distances = new double[nrOfNodes, nrOfNodes];
     112
     113      for (int i = 1; i < nrOfNodes; i++)
     114        for (int j = 0; j < i; j++)
     115          distances[i, j] = distances[j, i] = Distance(coordinates, i, j, distanceType);
     116
     117      return distances;
     118    }
     119
     120    private static double Distance(DoubleMatrix coordinates, int fromIdx, int toIdx, DistanceType distanceType) {
     121      double fromX = coordinates[fromIdx, 0];
     122      double fromY = coordinates[fromIdx, 1];
     123      double toX = coordinates[toIdx, 0];
     124      double toY = coordinates[toIdx, 1];
     125
    114126      double distance = Math.Sqrt((toX - fromX) * (toX - fromX) + (toY - fromY) * (toY - fromY));
     127
    115128      switch (distanceType) {
    116129        case DistanceType.CEIL_2D: return (int)Math.Ceiling(distance);
    117130        case DistanceType.EUC_2D: return distance;
    118         default: return 0.0;
     131        default: return double.NaN;
    119132      }
    120133    }
Note: See TracChangeset for help on using the changeset viewer.