source: branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization/3.3/TtpOrchestratorNode4.cs @ 14592

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Core.Networks;
using HeuristicLab.Data;
using HeuristicLab.Encodings.BinaryVectorEncoding;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Encodings.RealVectorEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.Knapsack;
using HeuristicLab.Problems.TravelingSalesman;

namespace HeuristicLab.Networks.IntegratedOptimization {
  [Item("TtpOrchestratorNode4", "An abstract base class for an orchestrator node for the TTP.")]
  [StorableClass]
  public sealed class TtpOrchestratorNode4 : OrchestratorNode {
    #region Constants
    private const string TspParameterName = "TSP";
    private const string KspParameterName = "KSP";
    private const string AvailabilityParameterName = "Availability";
    private const string MinSpeedParameterName = "MinSpeed";
    private const string MaxSpeedParameterName = "MaxSpeed";
    private const string RentingRatioParameterName = "RentingRatio";
    private const string IterationsParameterName = "Iterations";
    private const string MetaSolverName = "MetaSolver";
    private const string TspSolverName = "TspSolver";
    private const string KspSolverName = "KspSolver";
    private const string TspResultsResultName = "TspResults";
    private const string KspResultsResultName = "KspResults";
    private const string TtpResultsResultName = "TtpResults";
    #endregion

    #region Thread Results
    private object locker = new object();
    private ConcurrentDictionary<int, ResultCollection> tspThreadResults = new ConcurrentDictionary<int, ResultCollection>();
    private ConcurrentDictionary<int, ResultCollection> kspThreadResults = new ConcurrentDictionary<int, ResultCollection>();
    #endregion

    #region Parameters
    public IValueParameter<IntValue> IterationsParameter {
      get { return (IValueParameter<IntValue>)Parameters[IterationsParameterName]; }
    }

    public IValueParameter<TravelingSalesmanProblem> TspParameter {
      get { return (IValueParameter<TravelingSalesmanProblem>)Parameters[TspParameterName]; }
    }

    public IValueParameter<BinaryKnapsackProblem> KspParameter {
      get { return (IValueParameter<BinaryKnapsackProblem>)Parameters[KspParameterName]; }
    }

    public IValueParameter<IntArray> AvailabilityParameter {
      get { return (IValueParameter<IntArray>)Parameters[AvailabilityParameterName]; }
    }

    public IValueParameter<DoubleValue> MinSpeedParameter {
      get { return (IValueParameter<DoubleValue>)Parameters[MinSpeedParameterName]; }
    }

    public IValueParameter<DoubleValue> MaxSpeedParameter {
      get { return (IValueParameter<DoubleValue>)Parameters[MaxSpeedParameterName]; }
    }

    public IValueParameter<DoubleValue> RentingRatioParameter {
      get { return (IValueParameter<DoubleValue>)Parameters[RentingRatioParameterName]; }
    }
    #endregion

    #region Ports
    public IConfigurationPort MetaSolverOrchestrationPort {
      get { return (IConfigurationPort)Ports[MetaSolverName + OrchestrationPortNameSuffix]; }
    }

    public IConfigurationPort MetaSolverEvaluationPort {
      get { return (IConfigurationPort)Ports[MetaSolverName + EvaluationPortNameSuffix]; }
    }

    public IConfigurationPort TspSolverOrchestrationPort {
      get { return (IConfigurationPort)Ports[TspSolverName + OrchestrationPortNameSuffix]; }
    }

    public IConfigurationPort TspSolverEvaluationPort {
      get { return (IConfigurationPort)Ports[TspSolverName + EvaluationPortNameSuffix]; }
    }

    public IConfigurationPort KspSolverOrchestrationPort {
      get { return (IConfigurationPort)Ports[KspSolverName + OrchestrationPortNameSuffix]; }
    }

    public IConfigurationPort KspSolverEvaluationPort {
      get { return (IConfigurationPort)Ports[KspSolverName + EvaluationPortNameSuffix]; }
    }
    #endregion

    #region Results
    public ItemList<ResultCollection> TspResults {
      get { return (ItemList<ResultCollection>)Results[TspResultsResultName].Value; }
    }

    public ItemList<ResultCollection> KspResults {
      get { return (ItemList<ResultCollection>)Results[KspResultsResultName].Value; }
    }

    public ItemList<ResultCollection> TtpResults {
      get { return (ItemList<ResultCollection>)Results[TtpResultsResultName].Value; }
    }
    #endregion

    [StorableConstructor]
    private TtpOrchestratorNode4(bool deserializing) : base(deserializing) { }
    private TtpOrchestratorNode4(TtpOrchestratorNode4 original, Cloner cloner) : base(original, cloner) { }
    public TtpOrchestratorNode4() : this("TtpOrchestratorNode4") { }
    public TtpOrchestratorNode4(string name) : base(name) {
      #region Configure Parameters
      Parameters.Add(new ValueParameter<IntValue>(IterationsParameterName, new IntValue(20)));
      Parameters.Add(new ValueParameter<TravelingSalesmanProblem>(TspParameterName, new TravelingSalesmanProblem()));
      Parameters.Add(new ValueParameter<BinaryKnapsackProblem>(KspParameterName, new BinaryKnapsackProblem()));
      Parameters.Add(new ValueParameter<IntArray>(AvailabilityParameterName));
      Parameters.Add(new ValueParameter<DoubleValue>(MinSpeedParameterName, new DoubleValue(0.1)));
      Parameters.Add(new ValueParameter<DoubleValue>(MaxSpeedParameterName, new DoubleValue(1.0)));
      Parameters.Add(new ValueParameter<DoubleValue>(RentingRatioParameterName, new DoubleValue(0.5)));
      #endregion

      #region Configure Ports
      AddOrchestrationPort<VariegationProblem>(MetaSolverName);
      AddEvaluationPort<RealVector>(MetaSolverName, "RealVector", "Quality");
      AddOrchestrationPort<TravelingSalesmanProblem>(TspSolverName);
      AddEvaluationPort<Permutation>(TspSolverName, "TSPTour", "TSPTourLength");
      AddOrchestrationPort<BinaryKnapsackProblem>(KspSolverName);
      AddEvaluationPort<BinaryVector>(KspSolverName, "KnapsackSolution", "Quality");

      MetaSolverOrchestrationPort.ConnectedPortChanged += MetaSolverOrchestrationPort_ConnectedPortChanged;
      TspSolverOrchestrationPort.ConnectedPortChanged += TspSolverOrchestrationPort_ConnectedPortChanged;
      KspSolverOrchestrationPort.ConnectedPortChanged += KspSolverOrchestrationPort_ConnectedPortChanged;
      #endregion
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new TtpOrchestratorNode4(this, cloner);
    }

    public override void Prepare() {
      tspThreadResults.Clear();
      kspThreadResults.Clear();
      Results.Clear();
      Results.Add(new Result(TspResultsResultName, new ItemList<ResultCollection>()));
      Results.Add(new Result(KspResultsResultName, new ItemList<ResultCollection>()));
      Results.Add(new Result(TtpResultsResultName, new ItemList<ResultCollection>()));
    }

    public override void Start() {
      var metaMsg = MetaSolverOrchestrationPort.PrepareMessage();
      metaMsg["OrchestrationMessage"] = new EnumValue<OrchestrationMessage>(OrchestrationMessage.QualityAdaption);
      var problem = new VariegationProblem();
      problem.Encoding.Length = TspParameter.Value.Coordinates.Rows * 2;
      problem.Encoding.Bounds = new DoubleMatrix(new[,] { { -1.0, 1.0 } });
      metaMsg["Problem"] = problem;
      MetaSolverOrchestrationPort.SendMessage(metaMsg);
    }

    public override void Pause() {
      throw new NotImplementedException();
    }

    public override void Stop() {
      throw new NotImplementedException();
    }

    protected override void ProcessMessage(IMessage message, IMessagePort port, CancellationToken token) {
      var messageActions = new Dictionary<IMessagePort, Action<IMessage>>();
      messageActions.Add(MetaSolverOrchestrationPort, MetaSolverOrchestrationPortMessage);
      messageActions.Add(MetaSolverEvaluationPort, MetaSolverEvaluationPortMessage);
      messageActions.Add(TspSolverOrchestrationPort, TspSolverOrchestrationPortMessage);
      messageActions.Add(TspSolverEvaluationPort, TspSolverEvaluationPortMessage);
      messageActions.Add(KspSolverOrchestrationPort, KspSolverOrchestrationPortMessage);
      messageActions.Add(KspSolverEvaluationPort, KspSolverEvaluationPortMessage);

      messageActions[port](message);

      base.ProcessMessage(message, port, token);
    }

    #region MetaSolver Message Handling
    private void MetaSolverOrchestrationPortMessage(IMessage message) { }

    private void MetaSolverEvaluationPortMessage(IMessage message) {
      var factors = (RealVector)message["RealVector"];

      var tsp = (TravelingSalesmanProblem)TspParameter.Value.Clone();
      for (int j = 0; j < tsp.Coordinates.Rows; j++) {
        tsp.Coordinates[j, 0] = (int)Math.Ceiling(tsp.Coordinates[j, 0] * factors[j * 2]);
        tsp.Coordinates[j, 1] = (int)Math.Ceiling(tsp.Coordinates[j, 1] * factors[j * 2 + 1]);
      }

      var tspMsg = TspSolverOrchestrationPort.PrepareMessage();
      tspMsg["OrchestrationMessage"] = new EnumValue<OrchestrationMessage>(OrchestrationMessage.Start);
      tspMsg["Problem"] = tsp;
      TspSolverOrchestrationPort.SendMessage(tspMsg);

      var tspResults = tspThreadResults[Thread.CurrentThread.ManagedThreadId];
      var tour = (PathTSPTour)tspResults["Best TSP Solution"].Value;
      tour.Coordinates = (DoubleMatrix)TspParameter.Value.Coordinates.Clone();
      tour.Quality.Value = TSPCoordinatesPathEvaluator.Apply(new TSPEuclideanPathEvaluator(), tour.Coordinates, tour.Permutation);

      var kspMsg = KspSolverOrchestrationPort.PrepareMessage();
      kspMsg["OrchestrationMessage"] = new EnumValue<OrchestrationMessage>(OrchestrationMessage.Start);
      kspMsg["Problem"] = (BinaryKnapsackProblem)KspParameter.Value.Clone();
      KspSolverOrchestrationPort.SendMessage(kspMsg);

      var kspResults = kspThreadResults[Thread.CurrentThread.ManagedThreadId];
      var bestKspSolution = (BinaryVector)kspResults["Best Solution"].Value;
      var kspCapacity = (IntValue)KspParameter.Value.KnapsackCapacity.Clone();
      var kspPenalty = new DoubleValue(0.0);
      var kspWeights = (IntArray)KspParameter.Value.Weights.Clone();
      var kspValues = (IntArray)KspParameter.Value.Values.Clone();
      var bestKspQuality = KnapsackEvaluator.Apply(bestKspSolution, kspCapacity, kspPenalty, kspWeights, kspValues).Quality;
      var loot = new KnapsackSolution(bestKspSolution, bestKspQuality, kspCapacity, kspWeights, kspValues);
      kspResults.Add(new Result("Best KSP Solution", loot));

      #region Analyze
      double objectiveValue = EvaluateTtp(TspParameter.Value, tour.Permutation.ToArray(), KspParameter.Value, loot.BinaryVector.ToArray());
      ((DoubleValue)message["Quality"]).Value = objectiveValue;

      var ttpResults = new ResultCollection();
      ttpResults.Add(new Result("Quality", new DoubleValue(objectiveValue)));
      ttpResults.Add(new Result("Tour", tour));
      ttpResults.Add(new Result("Loot", loot));

      lock (locker) {
        TtpResults.Add(ttpResults);
        TspResults.Add(tspResults);
        KspResults.Add(kspResults);

        IResult bestQuality;
        if (!Results.TryGetValue("Best TTP Quality", out bestQuality)) {
          Results.Add(new Result("Best TTP Quality", new DoubleValue(objectiveValue)));
          Results.Add(new Result("Best Tour", tour));
          Results.Add(new Result("Best Loot", loot));
        } else if (((DoubleValue)bestQuality.Value).Value < objectiveValue) {
          ((DoubleValue)bestQuality.Value).Value = objectiveValue;
          Results["Best Tour"].Value = tour;
          Results["Best Loot"].Value = loot;
        }
      }
      #endregion
    }
    #endregion

    #region TspSolver Message Handling
    private void TspSolverOrchestrationPortMessage(IMessage message) {
      var results = (ResultCollection)message["Results"];
      if (results.ContainsKey("Best TSP Solution")) {
        tspThreadResults[Thread.CurrentThread.ManagedThreadId] = results;
      }
    }

    private void TspSolverEvaluationPortMessage(IMessage message) { }
    #endregion

    #region KspSolver Message Handling
    private void KspSolverOrchestrationPortMessage(IMessage message) {
      var results = (ResultCollection)message["Results"];
      if (results.ContainsKey("Best Solution")) {
        kspThreadResults[Thread.CurrentThread.ManagedThreadId] = results;
      }
    }

    private void KspSolverEvaluationPortMessage(IMessage message) { }
    #endregion

    #region Helpers
    private double EvaluateTtp(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot) {
      bool feasible;
      return EvaluateTtp(tsp, tour, ksp, loot, out feasible);
    }

    private double EvaluateTtp(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, out bool feasible) {
      double collectedWeight = 0.0;
      double objectiveValue = 0.0;
      double infeasibleBaseLine = -1000000.0;
      double speedCoefficient = (MaxSpeedParameter.Value.Value - MinSpeedParameter.Value.Value) / ksp.KnapsackCapacity.Value;

      int hideoutIdx = 0;
      while (tour[hideoutIdx] != 0) hideoutIdx++;
      int cityIdx = (hideoutIdx + 1) % tour.Length;
      int lastCityIdx = hideoutIdx;

      while (cityIdx != hideoutIdx) {
        double oldCollectedWeight = collectedWeight;
        var availableItems = AvailabilityParameter.Value.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];
        }

        objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[cityIdx]) * RentingRatioParameter.Value.Value /
                          (MaxSpeedParameter.Value.Value - speedCoefficient * oldCollectedWeight);
        lastCityIdx = cityIdx;
        cityIdx = (cityIdx + 1) % tour.Length;
      }

      objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[hideoutIdx]) * RentingRatioParameter.Value.Value /
                        (MaxSpeedParameter.Value.Value - speedCoefficient * collectedWeight);

      feasible = collectedWeight <= ksp.KnapsackCapacity.Value;
      if (!feasible) objectiveValue = infeasibleBaseLine - collectedWeight;

      return objectiveValue;
    }

    private double Distance(double[,] coords, int fromIdx, int toIdx) {
      double fromX = coords[fromIdx, 0], fromY = coords[fromIdx, 1],
             toX = coords[toIdx, 0], toY = coords[toIdx, 1];
      return (int)Math.Ceiling(Math.Sqrt((toX - fromX) * (toX - fromX) + (toY - fromY) * (toY - fromY)));
    }
    #endregion

    #region Event Handlers
    private void MetaSolverOrchestrationPort_ConnectedPortChanged(object sender, EventArgs e) {
      if (MetaSolverOrchestrationPort.ConnectedPort == null) return;

      var node = MetaSolverOrchestrationPort.ConnectedPort.Parent as OrchestratedAlgorithmNode;
      if (node == null) return;

      var hook = new HookOperator { Name = "Meta Eval Hook" };
      hook.Parameters.Add(new LookupParameter<RealVector>("RealVector") { Hidden = true });
      hook.Parameters.Add(new LookupParameter<DoubleValue>("Quality") { Hidden = true });
      node.EvalHook = hook;

      node.OrchestrationPort.CloneParametersFromPort(MetaSolverOrchestrationPort);
      node.EvaluationPort.CloneParametersFromPort(MetaSolverEvaluationPort);
      node.EvaluationPort.ConnectedPort = MetaSolverEvaluationPort;
    }

    private void TspSolverOrchestrationPort_ConnectedPortChanged(object sender, EventArgs e) {
      if (TspSolverOrchestrationPort.ConnectedPort == null) return;

      var node = TspSolverOrchestrationPort.ConnectedPort.Parent as OrchestratedAlgorithmNode;
      if (node == null) return;

      var hook = new HookOperator { Name = "TSP Eval Hook" };
      hook.Parameters.Add(new LookupParameter<Permutation>("TSPTour") { Hidden = true });
      hook.Parameters.Add(new LookupParameter<DoubleValue>("TSPTourLength") { Hidden = true });
      node.EvalHook = hook;

      node.OrchestrationPort.CloneParametersFromPort(TspSolverOrchestrationPort);
      node.EvaluationPort.CloneParametersFromPort(TspSolverEvaluationPort);
      node.EvaluationPort.ConnectedPort = TspSolverEvaluationPort;
    }

    private void KspSolverOrchestrationPort_ConnectedPortChanged(object sender, EventArgs e) {
      if (KspSolverOrchestrationPort.ConnectedPort == null) return;

      var node = KspSolverOrchestrationPort.ConnectedPort.Parent as OrchestratedAlgorithmNode;
      if (node == null) return;

      var hook = new HookOperator { Name = "KSP Eval Hook" };
      hook.Parameters.Add(new LookupParameter<BinaryVector>("KnapsackSolution") { Hidden = true });
      hook.Parameters.Add(new LookupParameter<DoubleValue>("Quality") { Hidden = true });
      node.EvalHook = hook;

      node.OrchestrationPort.CloneParametersFromPort(KspSolverOrchestrationPort);
      node.EvaluationPort.CloneParametersFromPort(KspSolverEvaluationPort);
      node.EvaluationPort.ConnectedPort = KspSolverEvaluationPort;
    }
    #endregion
  }
}