Changeset 11823 for branches/OptimizationNetworks/HeuristicLab.Networks/3.3/KSPTSPControlCode.cs

Timestamp:

01/26/15 15:52:03 (9 years ago)

Author:

abeham

Message:

#2205:

• Added cosolving KSPTSP network
• Fixed output path in projects for release target
• Fixed penalty in seqsolving KSPTSP network (would produce infeasible solutions)
• Added some additional references

File:

• branches/OptimizationNetworks/HeuristicLab.Networks/3.3/KSPTSPControlCode.cs (copied) (copied from branches/OptimizationNetworks/HeuristicLab.Networks/3.3/KSPTSPConnectorCode.cs) (3 diffs)

branches/OptimizationNetworks/HeuristicLab.Networks/3.3/KSPTSPControlCode.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Drawing;
+using System.Linq;
+using System.Threading;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -25 +29 @@
 using HeuristicLab.Data;
 using HeuristicLab.Encodings.BinaryVectorEncoding;
+using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Networks.Programmable;
+using HeuristicLab.Problems.Knapsack;
 using HeuristicLab.Problems.TravelingSalesman;
-using System.Drawing;
-using System.Linq;
-using System.Threading;
 
 namespace HeuristicLab.Networks {
-  [Item("KSPTSPConnector", "A node of an optimization network which connects a KSP and a TSP.")]
-  public class CompiledKSPTSPConnector : ProgrammableNode.CompiledProgrammableNode {
+  [Item("KSPTSPControl", "A node of an optimization network which connects a KSP and a TSP.")]
+  public class CompiledKSPTSPControl : ProgrammableNode.CompiledProgrammableNode {
+
     public static new Image StaticItemImage {
       get { return HeuristicLab.Common.Resources.VSImageLibrary.RadialChart; }
     }
 
-    protected CompiledKSPTSPConnector(CompiledKSPTSPConnector original, Cloner cloner) : base(original, cloner) { }
-    public CompiledKSPTSPConnector(ProgrammableNode context)
+    new protected KSPTSPControl Context {
+      get { return (KSPTSPControl)base.Context; }
+    }
+
+    protected CompiledKSPTSPControl(CompiledKSPTSPControl original, Cloner cloner) : base(original, cloner) { }
+    public CompiledKSPTSPControl(ProgrammableNode context)
       : base(context) {
       if (Ports.Count == 0)
@@ -46 +54 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new CompiledKSPTSPConnector(this, cloner);
+      return new CompiledKSPTSPControl(this, cloner);
     }
 
     public override void Initialize() {
       base.Initialize();
-      var parameters = new MessagePort("Parameters");
-      Ports.Add(parameters);
-      parameters.Parameters.Add(new PortParameter<DoubleMatrix>("Cities") { Type = PortParameterType.Input });
-      parameters.Parameters.Add(new PortParameter<DoubleValue>("TransportCostsFactor") { Type = PortParameterType.Input });
-
-      var ksp = new MessagePort("KSP Connector");
-      Ports.Add(ksp);
-      ksp.Parameters.Add(new PortParameter<BinaryVector>("KnapsackSolution") { Type = PortParameterType.Input });
-      ksp.Parameters.Add(new PortParameter<DoubleValue>("Quality") { Type = PortParameterType.Input | PortParameterType.Output });
-      ksp.Parameters.Add(new PortParameter<DoubleValue>("TransportCosts") { Type = PortParameterType.Output });
-      ksp.Parameters.Add(new PortParameter<PathTSPTour>("Route") { Type = PortParameterType.Output });
-
-      var tsp = new MessagePort("TSP Connector");
-      Ports.Add(tsp);
-      tsp.Parameters.Add(new PortParameter<DoubleMatrix>("Coordinates") { Type = PortParameterType.Output });
-      tsp.Parameters.Add(new PortParameter<PathTSPTour>("Best TSP Solution") { Type = PortParameterType.Input });
-      tsp.Parameters.Add(new PortParameter<DoubleValue>("BestQuality") { Type = PortParameterType.Input });
+      var configPort = new ConfigurationPort("Configure");
+      Ports.Add(configPort);
+
+      configPort.Parameters.Add(new PortParameter<IntValue>("KnapsackCapacity") {
+        Type = PortParameterType.Input
+      });
+      configPort.Parameters.Add(new PortParameter<IntArray>("Values") {
+        Type = PortParameterType.Input
+      });
+      configPort.Parameters.Add(new PortParameter<IntArray>("Weights") {
+        Type = PortParameterType.Input
+      });
+      configPort.Parameters.Add(new PortParameter<DoubleMatrix>("Coordinates") {
+        Type = PortParameterType.Input
+      });
+      configPort.Parameters.Add(new PortParameter<DoubleValue>("TransportCostsFactor") {
+        Type = PortParameterType.Input
+      });
+
+      var evalKspPort = new MessagePort("Evaluate KSP");
+      Ports.Add(evalKspPort);
+      evalKspPort.Parameters.Add(new PortParameter<BinaryVector>("KnapsackSolution") {
+        Type = PortParameterType.Input
+      });
+      evalKspPort.Parameters.Add(new PortParameter<DoubleValue>("Quality") {
+        Type = PortParameterType.Output
+      });
+
+      var evalTspPort = new MessagePort("Evaluate TSP");
+      Ports.Add(evalTspPort);
+      evalTspPort.Parameters.Add(new PortParameter<Permutation>("TSPTour") {
+        Type = PortParameterType.Input
+      });
+      evalTspPort.Parameters.Add(new PortParameter<DoubleValue>("TSPTourLength") {
+        Type = PortParameterType.Output
+      });
+
+      var addKspSolultionPort = new MessagePort("Add KSP Solution");
+      Ports.Add(addKspSolultionPort);
+      addKspSolultionPort.Parameters.Add(new PortParameter<KnapsackSolution>("BestSolution") {
+        Type = PortParameterType.Input
+      });
+
+      var addTspSolutionPort = new MessagePort("Add TSP Solution");
+      Ports.Add(addTspSolutionPort);
+      addTspSolutionPort.Parameters.Add(new PortParameter<PathTSPTour>("BestSolution") {
+        Type = PortParameterType.Input
+      });
+    }
+
+    private void AddKspSolultionPortOnMessageReceived(object sender, EventArgs<IMessage, CancellationToken> e) {
+      var cities = (KnapsackSolution)(e.Value.Values["BestSolution"]).Value;
+      AddSelectedCities(cities.BinaryVector);
+    }
+
+    private void AddTspSolutionPortOnMessageReceived(object sender, EventArgs<IMessage, CancellationToken> e) {
+      var trip = (PathTSPTour)(e.Value.Values["BestSolution"]).Value;
+      AddPredefinedTrip(trip.Permutation);
+    }
+
+    private void ConfigPortOnMessageReceived(object sender, EventArgs<IMessage, CancellationToken> e) {
+      Context.TransportCostFactor = (DoubleValue)(e.Value["TransportCostsFactor"]);
+      Context.Coordinates = (DoubleMatrix)(e.Value["Coordinates"]);
+      Context.Distances = CalculateEuclidean(Context.Coordinates);
+      Context.CityValues = (IntArray)(e.Value["Values"]);
+      Context.CityWeights = (IntArray)(e.Value["Weights"]);
+      Context.CityLimit = (IntValue)(e.Value["KnapsackCapacity"]);
+    }
+
+    private void EvalKspPortOnMessageReceived(object sender, EventArgs<IMessage, CancellationToken> e) {
+      var cities = (BinaryVector)(e.Value.Values["KnapsackSolution"]).Value;
+      e.Value.Values["Quality"].Value = new DoubleValue(EvaluatePredefinedTrip(cities));
+    }
+
+    private void EvalTspPortOnMessageReceived(object sender, EventArgs<IMessage, CancellationToken> e) {
+      var trip = (Permutation)(e.Value.Values["TSPTour"]).Value;
+      e.Value.Values["TSPTourLength"].Value = new DoubleValue(EvaluateSelectedCities(trip));
     }
 
     public override void RegisterEvents() {
       base.RegisterEvents();
-      var ksp = (IMessagePort)Ports["KSP Connector"];
-      ksp.MessageReceived += Knapsack_MessageReceived;
+      ((IMessagePort)Ports["Configure"]).MessageReceived += ConfigPortOnMessageReceived;
+      ((IMessagePort)Ports["Evaluate KSP"]).MessageReceived += EvalKspPortOnMessageReceived;
+      ((IMessagePort)Ports["Evaluate TSP"]).MessageReceived += EvalTspPortOnMessageReceived;
+      ((IMessagePort)Ports["Add KSP Solution"]).MessageReceived += AddKspSolultionPortOnMessageReceived;
+      ((IMessagePort)Ports["Add TSP Solution"]).MessageReceived += AddTspSolutionPortOnMessageReceived;
+
     }
     public override void DeregisterEvents() {
-      var ksp = (IMessagePort)Ports["KSP Connector"];
-      ksp.MessageReceived -= Knapsack_MessageReceived;
+      ((IMessagePort)Ports["Configure"]).MessageReceived -= ConfigPortOnMessageReceived;
+      ((IMessagePort)Ports["Evaluate KSP"]).MessageReceived -= EvalKspPortOnMessageReceived;
+      ((IMessagePort)Ports["Evaluate TSP"]).MessageReceived -= EvalTspPortOnMessageReceived;
+      ((IMessagePort)Ports["Add KSP Solution"]).MessageReceived -= AddKspSolultionPortOnMessageReceived;
+      ((IMessagePort)Ports["Add TSP Solution"]).MessageReceived -= AddTspSolutionPortOnMessageReceived;
       base.DeregisterEvents();
     }
 
-    private void Knapsack_MessageReceived(object sender, EventArgs<IMessage, CancellationToken> e) {
-      // get parameters
-      var parametersPort = (IMessagePort)Ports["Parameters"];
-      var parameters = parametersPort.PrepareMessage();
-      parametersPort.SendMessage(parameters, e.Value2);
-      var cities = (DoubleMatrix)parameters["Cities"];
-      var factor = ((DoubleValue)parameters["TransportCostsFactor"]).Value;
-
-      // build coordinates
-      var kspMsg = e.Value;
-      var kspSolution = (BinaryVector)kspMsg["KnapsackSolution"];
-      var kspQuality = ((DoubleValue)kspMsg["Quality"]).Value;
-      var coords = new DoubleMatrix(kspSolution.Count(x => x), 2);
-      int j = 0;
-      for (int i = 0; i < kspSolution.Length; i++) {
-        if (kspSolution[i]) {
-          coords[j, 0] = cities[i, 0];
-          coords[j, 1] = cities[i, 1];
-          j++;
+    public double EvaluatePredefinedTrip(BinaryVector cities) {
+      if (Context.SelectedCities.Count == 0) {
+        Context.SelectedCities.Add(cities);
+        Context.KspWait.Set();
+        Context.TspWait.WaitOne();
+      }
+      return EvaluateBoth(cities, Context.PredefinedTrip.Last());
+    }
+
+    public double EvaluateSelectedCities(Permutation trip) {
+      if (Context.PredefinedTrip.Count == 0) {
+        Context.PredefinedTrip.Add(trip);
+        Context.TspWait.Set();
+        Context.KspWait.WaitOne();
+      }
+      return EvaluateBoth(Context.SelectedCities.Last(), trip);
+    }
+
+    public double EvaluateBoth(BinaryVector cities, Permutation trip) {
+      var cityValues = cities.Select((v, i) => v ? Context.CityValues[i] : 0).Sum();
+      var cityWeights = cities.Select((v, i) => v ? Context.CityWeights[i] : 0).Sum();
+      var subtour = trip.Where(x => cities[x]).ToArray();
+      var tourLength = 0.0;
+      for (var i = 1; i < subtour.Length; i++)
+        tourLength += Context.Distances[subtour[i - 1], subtour[i]];
+      tourLength += Context.Distances[subtour.Last(), subtour[0]];
+      if (cityWeights > Context.CityLimit.Value) // infeasible solution
+        return Context.CityLimit.Value - cityWeights - tourLength * Context.TransportCostFactor.Value;
+      return cityValues - tourLength * Context.TransportCostFactor.Value;
+    }
+
+    public void AddPredefinedTrip(Permutation trip) {
+      Context.TspWait.Set();
+      Context.KspWait.WaitOne();
+      lock (Context.Locker) {
+        Context.PredefinedTrip.Add(trip);
+      }
+    }
+
+    public void AddSelectedCities(BinaryVector cities) {
+      Context.KspWait.Set();
+      Context.TspWait.WaitOne();
+      lock (Context.Locker) {
+        Context.SelectedCities.Add(cities);
+      }
+    }
+
+    public static DoubleMatrix CalculateEuclidean(DoubleMatrix cities) {
+      var len = cities.Rows;
+      var distances = new DoubleMatrix(len, len);
+      for (var i = 0; i < len - 1; i++) {
+        var sX = cities[i, 0];
+        var sY = cities[i, 1];
+        for (var j = i + 1; j < len; j++) {
+          var tX = cities[j, 0];
+          var tY = cities[j, 1];
+          distances[i, j] = Math.Sqrt((sX - tX) * (sX - tX) + (sY - tY) * (sY - tY));
+          distances[j, i] = distances[i, j];
         }
       }
-
-      // solve TSP
-      var tspConnectorPort = (IMessagePort)Ports["TSP Connector"];
-      var tspMsg = tspConnectorPort.PrepareMessage();
-      tspMsg["Coordinates"] = coords;
-      tspConnectorPort.SendMessage(tspMsg, e.Value2);
-      var tspSolution = (PathTSPTour)tspMsg["Best TSP Solution"];
-      var tspQuality = ((DoubleValue)tspMsg["BestQuality"]).Value;
-
-      // calculate transport costs
-      ((DoubleValue)kspMsg["Quality"]).Value = kspQuality - factor * tspQuality;
-      kspMsg["TransportCosts"] = new DoubleValue(factor * tspQuality);
-      kspMsg["Route"] = tspSolution;
-    }
+      return distances;
+    }
+
   }
 }