Free cookie consent management tool by TermsFeed Policy Generator

source: branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization/3.3/TtpOrchestratorNode1.cs @ 14604

Last change on this file since 14604 was 14598, checked in by jkarder, 8 years ago

#2205: worked on optimization networks

  • switched from IConfigurationPorts to IMessagePorts
  • removed option to clone algorithms in OrchestratedAlgorithmNodes
  • made properties of TourProfitProblem storable
  • fixed event handler registration
File size: 19.7 KB
Line 
1//using System;
2//using System.Collections.Generic;
3//using System.Linq;
4//using System.Threading;
5//using HeuristicLab.Common;
6//using HeuristicLab.Core;
7//using HeuristicLab.Core.Networks;
8//using HeuristicLab.Data;
9//using HeuristicLab.Encodings.BinaryVectorEncoding;
10//using HeuristicLab.Encodings.PermutationEncoding;
11//using HeuristicLab.Operators;
12//using HeuristicLab.Optimization;
13//using HeuristicLab.Parameters;
14//using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
15//using HeuristicLab.Problems.Knapsack;
16//using HeuristicLab.Problems.TravelingSalesman;
17
18//namespace HeuristicLab.Networks.IntegratedOptimization {
19//  [Item("TtpOrchestratorNode", "An abstract base class for an orchestrator node for the TTP.")]
20//  [StorableClass]
21//  public sealed class TtpOrchestratorNode1 : OrchestratorNode {
22//    #region Constants
23//    private const string TspParameterName = "TSP";
24//    private const string KspParameterName = "KSP";
25//    private const string AvailabilityParameterName = "Availability";
26//    private const string MinSpeedParameterName = "MinSpeed";
27//    private const string MaxSpeedParameterName = "MaxSpeed";
28//    private const string RentingRatioParameterName = "RentingRatio";
29//    private const string IterationsParameterName = "Iterations";
30//    private const string TspSolverName = "TspSolver";
31//    private const string KspSolverName = "KspSolver";
32//    private const string TspResultsResultName = "TspResults";
33//    private const string KspResultsResultName = "KspResults";
34//    private const string TtpResultsResultName = "TtpResults";
35//    #endregion
36
37//    private Stack<ResultCollection> tspResultsStack = new Stack<ResultCollection>();
38//    private Stack<ResultCollection> kspResultsStack = new Stack<ResultCollection>();
39//    private KnapsackProblem currentKsp;
40
41//    #region Parameters
42//    public IValueParameter<IntValue> IterationsParameter {
43//      get { return (IValueParameter<IntValue>)Parameters[IterationsParameterName]; }
44//    }
45
46//    public IValueParameter<TravelingSalesmanProblem> TspParameter {
47//      get { return (IValueParameter<TravelingSalesmanProblem>)Parameters[TspParameterName]; }
48//    }
49
50//    public IValueParameter<KnapsackProblem> KspParameter {
51//      get { return (IValueParameter<KnapsackProblem>)Parameters[KspParameterName]; }
52//    }
53
54//    public IValueParameter<IntArray> AvailabilityParameter {
55//      get { return (IValueParameter<IntArray>)Parameters[AvailabilityParameterName]; }
56//    }
57
58//    public IValueParameter<DoubleValue> MinSpeedParameter {
59//      get { return (IValueParameter<DoubleValue>)Parameters[MinSpeedParameterName]; }
60//    }
61
62//    public IValueParameter<DoubleValue> MaxSpeedParameter {
63//      get { return (IValueParameter<DoubleValue>)Parameters[MaxSpeedParameterName]; }
64//    }
65
66//    public IValueParameter<DoubleValue> RentingRatioParameter {
67//      get { return (IValueParameter<DoubleValue>)Parameters[RentingRatioParameterName]; }
68//    }
69//    #endregion
70
71//    #region Ports
72//    public IMessagePort TspSolverOrchestrationPort {
73//      get { return (IMessagePort)Ports[TspSolverName + OrchestrationPortNameSuffix]; }
74//    }
75
76//    public IMessagePort TspSolverEvaluationPort {
77//      get { return (IMessagePort)Ports[TspSolverName + EvaluationPortNameSuffix]; }
78//    }
79
80//    public IMessagePort KspSolverOrchestrationPort {
81//      get { return (IMessagePort)Ports[KspSolverName + OrchestrationPortNameSuffix]; }
82//    }
83
84//    public IMessagePort KspSolverEvaluationPort {
85//      get { return (IMessagePort)Ports[KspSolverName + EvaluationPortNameSuffix]; }
86//    }
87//    #endregion
88
89//    #region Results
90//    public ItemList<ResultCollection> TspResults {
91//      get { return (ItemList<ResultCollection>)Results[TspResultsResultName].Value; }
92//    }
93
94//    public ItemList<ResultCollection> KspResults {
95//      get { return (ItemList<ResultCollection>)Results[KspResultsResultName].Value; }
96//    }
97
98//    public ItemList<ResultCollection> TtpResults {
99//      get { return (ItemList<ResultCollection>)Results[TtpResultsResultName].Value; }
100//    }
101//    #endregion
102
103//    [StorableConstructor]
104//    private TtpOrchestratorNode1(bool deserializing) : base(deserializing) { }
105//    private TtpOrchestratorNode1(TtpOrchestratorNode1 original, Cloner cloner) : base(original, cloner) { }
106//    public TtpOrchestratorNode1() : this("TtpOrchestratorNode") { }
107//    public TtpOrchestratorNode1(string name) : base(name) {
108//      #region Configure Parameters
109//      Parameters.Add(new ValueParameter<IntValue>(IterationsParameterName, new IntValue(20)));
110//      Parameters.Add(new ValueParameter<TravelingSalesmanProblem>(TspParameterName, new TravelingSalesmanProblem()));
111//      Parameters.Add(new ValueParameter<KnapsackProblem>(KspParameterName, new KnapsackProblem()));
112//      Parameters.Add(new ValueParameter<IntArray>(AvailabilityParameterName));
113//      Parameters.Add(new ValueParameter<DoubleValue>(MinSpeedParameterName, new DoubleValue(0.1)));
114//      Parameters.Add(new ValueParameter<DoubleValue>(MaxSpeedParameterName, new DoubleValue(1.0)));
115//      Parameters.Add(new ValueParameter<DoubleValue>(RentingRatioParameterName, new DoubleValue(0.5)));
116//      #endregion
117
118//      #region Configure Ports
119//      AddOrchestrationPort<TravelingSalesmanProblem>(TspSolverName);
120//      AddEvaluationPort<Permutation>(TspSolverName, "TSPTour", "TSPTourLength");
121//      AddOrchestrationPort<KnapsackProblem>(KspSolverName);
122//      AddEvaluationPort<BinaryVector>(KspSolverName, "KnapsackSolution", "Quality");
123
124//      TspSolverOrchestrationPort.ConnectedPortChanged += TspSolverOrchestrationPort_ConnectedPortChanged;
125//      KspSolverOrchestrationPort.ConnectedPortChanged += KspSolverOrchestrationPort_ConnectedPortChanged;
126//      #endregion
127//    }
128
129//    public override IDeepCloneable Clone(Cloner cloner) {
130//      return new TtpOrchestratorNode1(this, cloner);
131//    }
132
133//    public override void Start() {
134//      tspResultsStack.Clear();
135//      kspResultsStack.Clear();
136//      Results.Clear();
137//      Results.Add(new Result(TspResultsResultName, new ItemList<ResultCollection>()));
138//      Results.Add(new Result(KspResultsResultName, new ItemList<ResultCollection>()));
139//      Results.Add(new Result(TtpResultsResultName, new ItemList<ResultCollection>()));
140
141//      var kspMsg = KspSolverOrchestrationPort.PrepareMessage();
142//      kspMsg["OrchestrationMessage"] = OrchestrationMessageParameter.Value;
143//      kspMsg["Problem"] = currentKsp = (KnapsackProblem)KspParameter.Value.Clone();
144//      KspSolverOrchestrationPort.SendMessageAsync(kspMsg);
145//    }
146
147//    public override void Pause() {
148//      throw new NotImplementedException();
149//    }
150
151//    public override void Stop() {
152//      throw new NotImplementedException();
153//    }
154
155//    protected override void ProcessMessage(IMessage message, IMessagePort port, CancellationToken token) {
156//      var messageActions = new Dictionary<IMessagePort, Action<IMessage>>();
157//      messageActions.Add(TspSolverOrchestrationPort, TspSolverOrchestrationPortMessage);
158//      messageActions.Add(TspSolverEvaluationPort, TspSolverEvaluationPortMessage);
159//      messageActions.Add(KspSolverOrchestrationPort, KspSolverOrchestrationPortMessage);
160//      messageActions.Add(KspSolverEvaluationPort, KspSolverEvaluationPortMessage);
161
162//      messageActions[port](message);
163
164//      base.ProcessMessage(message, port, token);
165//    }
166
167//    private void TspSolverEvaluationPortMessage(IMessage message) { }
168
169//    private void KspSolverEvaluationPortMessage(IMessage message) {
170//      var selectedItems = (BinaryVector)message["KnapsackSolution"];
171//      double weight = 0.0;
172//      for (int i = 0; i < selectedItems.Length; i++)
173//        if (selectedItems[i]) weight += KspParameter.Value.Weights[i];
174
175//      bool feasible = weight <= KspParameter.Value.KnapsackCapacity.Value;
176//      if (feasible) {
177//        var tspMsg = TspSolverOrchestrationPort.PrepareMessage();
178//        tspMsg["OrchestrationMessage"] = new EnumValue<OrchestrationMessage>(OrchestrationMessage.ProblemVariegation);
179//        tspMsg["Problem"] = ReduceTsp(selectedItems.ToArray());
180//        TspSolverOrchestrationPort.SendMessage(tspMsg);
181
182//        var tour = (PathTSPTour)tspResultsStack.Pop()["Best TSP Solution"].Value;
183//        int[] cityMapping = MapCities(selectedItems.ToArray());
184//        double quality = EvaluateTtp(TspParameter.Value, tour.Permutation.Select(x => cityMapping[x]).ToArray(), KspParameter.Value, selectedItems.ToArray());
185//        ((DoubleValue)message["Quality"]).Value = quality;
186//      }
187//    }
188
189//    private void TspSolverOrchestrationPortMessage(IMessage message) {
190//      ResultCollection results;
191//      switch (OrchestrationMessageParameter.Value.Value) {
192//        #region Black Box
193//        case OrchestrationMessage.QualityAdaption:
194//          results = (ResultCollection)message["Results"];
195//          if (results.ContainsKey("Best TSP Solution")) {
196//            tspResultsStack.Push(results);
197//          }
198//          break;
199//        #endregion
200//        #region White Box
201//        case OrchestrationMessage.ProblemVariegation:
202//          results = (ResultCollection)message["Results"];
203//          if (results.ContainsKey("Best TSP Solution")) {
204//            tspResultsStack.Push(results);
205
206//            #region Analyze
207//            var tspResults = tspResultsStack.Peek();
208//            var tour = (PathTSPTour)tspResults["Best TSP Solution"].Value;
209//            var kspResults = kspResultsStack.Peek();
210//            var loot = (KnapsackSolution)kspResults["Best Knapsack Solution"].Value;
211
212//            int[] cityMapping = MapCities(loot.BinaryVector.ToArray());
213//            double objectiveValue = EvaluateTtp(TspParameter.Value, tour.Permutation.Select(x => cityMapping[x]).ToArray(), KspParameter.Value, loot.BinaryVector.ToArray());
214//            loot.Values = (IntArray)KspParameter.Value.Values.Clone();
215
216//            var ttpResults = new ResultCollection();
217//            ttpResults.Add(new Result("Quality", new DoubleValue(objectiveValue)));
218//            ttpResults.Add(new Result("Tour", tour));
219//            ttpResults.Add(new Result("Loot", loot));
220//            TtpResults.Add(ttpResults);
221//            TspResults.Add(tspResults);
222//            KspResults.Add(kspResults);
223
224//            IResult bestQuality;
225//            if (!Results.TryGetValue("Best TTP Quality", out bestQuality)) {
226//              Results.Add(new Result("Best TTP Quality", new DoubleValue(objectiveValue)));
227//              Results.Add(new Result("Best Tour", tour));
228//              Results.Add(new Result("Best Loot", loot));
229//            } else if (((DoubleValue)bestQuality.Value).Value < objectiveValue) {
230//              ((DoubleValue)bestQuality.Value).Value = objectiveValue;
231//              Results["Best Tour"].Value = tour;
232//              Results["Best Loot"].Value = loot;
233//            }
234//            #endregion
235
236//            if (TtpResults.Count < IterationsParameter.Value.Value) {
237//              var tsp = (TravelingSalesmanProblem)TspParameter.Value.Clone();
238//              tour = (PathTSPTour)Results["Best Tour"].Value;
239//              loot = (KnapsackSolution)Results["Best Loot"].Value;
240//              currentKsp = VariegateKsp(tsp, tour.Permutation.ToArray(), currentKsp, loot.BinaryVector.ToArray());
241
242//              var kspMsg = KspSolverOrchestrationPort.PrepareMessage();
243//              kspMsg["OrchestrationMessage"] = OrchestrationMessageParameter.Value;
244//              kspMsg["Problem"] = currentKsp;
245//              KspSolverOrchestrationPort.SendMessageAsync(kspMsg);
246//            }
247//          }
248//          break;
249//          #endregion
250//      }
251//    }
252
253//    private void KspSolverOrchestrationPortMessage(IMessage message) {
254//      switch (OrchestrationMessageParameter.Value.Value) {
255//        #region Black Box
256//        case OrchestrationMessage.QualityAdaption:
257//          break;
258//        #endregion
259//        #region White Box
260//        case OrchestrationMessage.ProblemVariegation:
261//          var results = (ResultCollection)message["Results"];
262//          if (results.ContainsKey("Best Knapsack Solution")) {
263//            kspResultsStack.Push(results);
264//            var selectedItems = ((KnapsackSolution)results["Best Knapsack Solution"].Value).BinaryVector;
265//            var tspMsg = TspSolverOrchestrationPort.PrepareMessage();
266//            tspMsg["OrchestrationMessage"] = OrchestrationMessageParameter.Value;
267//            tspMsg["Problem"] = ReduceTsp(selectedItems.ToArray());
268//            TspSolverOrchestrationPort.SendMessage(tspMsg);
269//          }
270//          break;
271//          #endregion
272//      }
273//    }
274
275//    #region Helpers
276//    private TravelingSalesmanProblem ReduceTsp(bool[] selectedItems) {
277//      var selection = MapCities(selectedItems);
278//      var problem = (TravelingSalesmanProblem)TspParameter.Value.Clone();
279//      var originalCoordinates = problem.Coordinates;
280
281//      var coordinates = new DoubleMatrix(selection.Length, 2);
282//      for (int i = 0; i < selection.Length; i++) {
283//        coordinates[i, 0] = originalCoordinates[selection[i], 0];
284//        coordinates[i, 1] = originalCoordinates[selection[i], 1];
285//      }
286//      problem.Coordinates = coordinates;
287//      return problem;
288//    }
289
290//    private KnapsackProblem VariegateKsp(TravelingSalesmanProblem tsp, int[] tour, KnapsackProblem ksp, bool[] loot) {
291//      int[] cities = Enumerable.Range(0, TspParameter.Value.SolutionCreator.LengthParameter.Value.Value).ToArray();
292//      int[] cityMapping = MapCities(loot);
293//      int[] deselectedCities = cities.Except(cityMapping).ToArray();
294//      double quality = EvaluateTtp(tsp, tour.Select(x => cityMapping[x]).ToArray(), ksp, loot);
295
296//      var increase = new HashSet<int>();
297
298//      foreach (var dc in deselectedCities) {
299//        var availableItems = AvailabilityParameter.Value.Select((c, i) => new { CityIdx = c, ItemIdx = i }).Where(x => x.CityIdx == dc).ToArray();
300//        if (!availableItems.Any()) continue;
301
302//        // build new loot
303//        bool[] newLoot = (bool[])loot.Clone();
304//        newLoot[availableItems[0].ItemIdx] = true;
305
306//        // build new ksp
307//        var newKsp = (KnapsackProblem)ksp.Clone();
308//        int avgValue = (int)Math.Round(availableItems.Average(x => newKsp.Values[x.ItemIdx]));
309//        int avgWeight = (int)Math.Round(availableItems.Average(x => newKsp.Weights[x.ItemIdx]));
310//        newKsp.Values[availableItems[0].ItemIdx] = avgValue;
311//        newKsp.Weights[availableItems[0].ItemIdx] = avgWeight;
312
313//        bool better = false;
314//        for (int i = 1; i < cityMapping.Length; i++) {
315//          // evaluate
316//          var newCityMapping = (int[])cityMapping.Clone();
317//          newCityMapping[i] = dc;
318//          double q = EvaluateTtp(tsp, tour.Select(x => newCityMapping[x]).ToArray(), newKsp, newLoot);
319//          if (q > quality) {
320//            better = true;
321//            break;
322//          }
323//        }
324
325//        if (better)
326//          foreach (var item in availableItems)
327//            increase.Add(item.ItemIdx);
328//      }
329
330//      var result = (KnapsackProblem)ksp.Clone();
331//      if (increase.Any()) {
332//        // increase values by 5 %
333//        foreach (var itemIndex in increase)
334//          result.Values[itemIndex] = (int)Math.Ceiling(result.Values[itemIndex] * 1.05);
335//      }
336//      return result;
337//    }
338
339//    private double EvaluateTtp(TravelingSalesmanProblem tsp, int[] tour, KnapsackProblem ksp, bool[] loot) {
340//      bool feasible;
341//      return EvaluateTtp(tsp, tour, ksp, loot, out feasible);
342//    }
343
344//    private double EvaluateTtp(TravelingSalesmanProblem tsp, int[] tour, KnapsackProblem ksp, bool[] loot, out bool feasible) {
345//      double collectedWeight = 0.0;
346//      double objectiveValue = 0.0;
347//      double infeasibleBaseLine = -1000000.0;
348//      double speedCoefficient = (MaxSpeedParameter.Value.Value - MinSpeedParameter.Value.Value) / ksp.KnapsackCapacity.Value;
349
350//      int hideoutIdx = 0;
351//      while (tour[hideoutIdx] != 0) hideoutIdx++;
352//      int cityIdx = (hideoutIdx + 1) % tour.Length;
353//      int lastCityIdx = hideoutIdx;
354
355//      while (cityIdx != hideoutIdx) {
356//        double oldCollectedWeight = collectedWeight;
357//        var availableItems = AvailabilityParameter.Value.Select((c, i) => new { CityIdx = c, ItemIdx = i }).Where(x => x.CityIdx == tour[cityIdx]);
358
359//        foreach (var item in availableItems) {
360//          if (!loot[item.ItemIdx]) continue;
361//          collectedWeight += ksp.Weights[item.ItemIdx];
362//          objectiveValue += ksp.Values[item.ItemIdx];
363//        }
364
365//        objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[cityIdx]) * RentingRatioParameter.Value.Value /
366//                          (MaxSpeedParameter.Value.Value - speedCoefficient * oldCollectedWeight);
367//        lastCityIdx = cityIdx;
368//        cityIdx = (cityIdx + 1) % tour.Length;
369//      }
370
371//      objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[hideoutIdx]) * RentingRatioParameter.Value.Value /
372//                        (MaxSpeedParameter.Value.Value - speedCoefficient * collectedWeight);
373
374//      feasible = collectedWeight <= ksp.KnapsackCapacity.Value;
375//      if (!feasible) objectiveValue = infeasibleBaseLine - collectedWeight;
376
377//      return objectiveValue;
378//    }
379
380//    private int[] MapCities(bool[] loot) {
381//      var map = new HashSet<int> { 0 };
382//      for (int i = 0; i < loot.Length; i++)
383//        if (loot[i]) map.Add(AvailabilityParameter.Value[i]);
384//      return map.OrderBy(x => x).ToArray();
385//    }
386
387//    private double Distance(double[,] coords, int fromIdx, int toIdx) {
388//      double fromX = coords[fromIdx, 0], fromY = coords[fromIdx, 1],
389//             toX = coords[toIdx, 0], toY = coords[toIdx, 1];
390//      return Math.Sqrt((toX - fromX) * (toX - fromX) + (toY - fromY) * (toY - fromY));
391//    }
392//    #endregion
393
394//    #region Event Handlers
395//    private void TspSolverOrchestrationPort_ConnectedPortChanged(object sender, EventArgs e) {
396//      if (TspSolverOrchestrationPort.ConnectedPort == null) return;
397
398//      var node = TspSolverOrchestrationPort.ConnectedPort.Parent as OrchestratedAlgorithmNode;
399//      if (node == null) return;
400
401//      var hook = new HookOperator { Name = "TSP Eval Hook" };
402//      hook.Parameters.Add(new LookupParameter<Permutation>("TSPTour") { Hidden = true });
403//      hook.Parameters.Add(new LookupParameter<DoubleValue>("TSPTourLength") { Hidden = true });
404//      node.EvalHook = hook;
405
406//      node.OrchestrationPort.CloneParametersFromPort(TspSolverOrchestrationPort);
407//      node.EvaluationPort.CloneParametersFromPort(TspSolverEvaluationPort);
408//      node.EvaluationPort.ConnectedPort = TspSolverEvaluationPort;
409//    }
410
411//    private void KspSolverOrchestrationPort_ConnectedPortChanged(object sender, EventArgs e) {
412//      if (KspSolverOrchestrationPort.ConnectedPort == null) return;
413
414//      var node = KspSolverOrchestrationPort.ConnectedPort.Parent as OrchestratedAlgorithmNode;
415//      if (node == null) return;
416
417//      var hook = new HookOperator { Name = "KSP Eval Hook" };
418//      hook.Parameters.Add(new LookupParameter<BinaryVector>("KnapsackSolution") { Hidden = true });
419//      hook.Parameters.Add(new LookupParameter<DoubleValue>("Quality") { Hidden = true });
420//      node.EvalHook = hook;
421
422//      node.OrchestrationPort.CloneParametersFromPort(KspSolverOrchestrationPort);
423//      node.EvaluationPort.CloneParametersFromPort(KspSolverEvaluationPort);
424//      node.EvaluationPort.ConnectedPort = KspSolverEvaluationPort;
425//    }
426//    #endregion
427//  }
428//}
Note: See TracBrowser for help on using the repository browser.