source: branches/2747_CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/MultiNestCFSAPSolvingStrategy.cs @ 17550

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using HeuristicLab.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.Scheduling.CFSAP {
  [Item("MultiNest CFSAP Solver", "Solving strategy that applies an algorithm instance to the worst nest.")]
  [StorableClass]
  [Creatable(CreatableAttribute.Categories.Algorithms)]
  public class MultiNestCFSAPSolvingStrategy : BasicAlgorithm {
    public override bool SupportsPause => true;

    public override Type ProblemType => typeof(MultiNestCFSAP);

    public new MultiNestCFSAP Problem {
      get { return (MultiNestCFSAP)base.Problem; }
      set { base.Problem = value; }
    }

    public IValueParameter<IAlgorithm> SolverParameter {
      get { return (IValueParameter<IAlgorithm>)Parameters["Solver"]; }
    }

    public IFixedValueParameter<TimeSpanValue> MaximumRuntimeParameter {
      get { return (IFixedValueParameter<TimeSpanValue>)Parameters["MaximumRuntime"]; }
    }

    public IFixedValueParameter<StringValue> EvaluatedSolutionsNameParameter {
      get { return (IFixedValueParameter<StringValue>)Parameters["EvaluatedSolutionsName"]; }
    }

    public IValueParameter<BoolValue> RestartParameter {
      get { return (IValueParameter<BoolValue>)Parameters["Restart"]; }
    }

    public IValueParameter<IntValue> MinTriesParameter {
      get { return (IValueParameter<IntValue>)Parameters["Restart.MinTries"]; }
    }

    public IValueParameter<DoubleValue> LastSuccessPercentageParameter {
      get { return (IValueParameter<DoubleValue>)Parameters["Restart.LastSuccessPercentage"]; }
    }

    public IAlgorithm Solver {
      get { return SolverParameter.Value; }
      set { SolverParameter.Value = value; }
    }

    public TimeSpan MaximumRuntime {
      get { return MaximumRuntimeParameter.Value.Value; }
      set { MaximumRuntimeParameter.Value.Value = value; }
    }

    public string EvaluatedSolutionsName {
      get { return EvaluatedSolutionsNameParameter.Value.Value; }
      set { EvaluatedSolutionsNameParameter.Value.Value = value; }
    }

    public bool Restart {
      get => RestartParameter.Value.Value;
      set => RestartParameter.Value.Value = value;
    }

    public int MinTries {
      get => MinTriesParameter.Value.Value;
      set => MinTriesParameter.Value.Value = value;
    }

    public double LastSuccessPercentage {
      get => LastSuccessPercentageParameter.Value.Value;
      set => LastSuccessPercentageParameter.Value.Value = value;
    }

    [StorableConstructor]
    protected MultiNestCFSAPSolvingStrategy(bool deserializing) : base(deserializing) { }

    protected MultiNestCFSAPSolvingStrategy(MultiNestCFSAPSolvingStrategy original, Cloner cloner)
      : base(original, cloner) {
      if (original.algorithms != null)
        algorithms = original.algorithms.Select(x => cloner.Clone(x)).ToList();
      if (original.qualities != null)
        qualities = original.qualities.ToArray();
      if (original.algorithmsResults != null)
        algorithmsResults = cloner.Clone(original.algorithmsResults);
      if (original.qualityPerClock != null)
        qualityPerClock = cloner.Clone(original.qualityPerClock);
      if (original.qualityPerEvaluations != null)
        qualityPerEvaluations = cloner.Clone(original.qualityPerEvaluations);

      restart = original.restart;
      minTries = original.minTries;
      lastSuccessPercentage = original.lastSuccessPercentage;
    }

    public MultiNestCFSAPSolvingStrategy() {
      Parameters.Add(new ValueParameter<IAlgorithm>("Solver", "The actual solver template.") { GetsCollected = false });
      Parameters.Add(new FixedValueParameter<TimeSpanValue>("MaximumRuntime", "The maximum time that the strategy should run.", new TimeSpanValue(TimeSpan.FromSeconds(60))));
      Parameters.Add(new FixedValueParameter<StringValue>("EvaluatedSolutionsName", "The name of the result that shows the number of evaluated solutions by the actual solver.", new StringValue("EvaluatedSolutions")));
      Parameters.Add(new ValueParameter<BoolValue>("Restart", "Whether the worst algorithm should be restarted, if it doesn't find any better solutions.", new BoolValue(restart)));
      Parameters.Add(new ValueParameter<IntValue>("Restart.MinTries", "The minimum number of tries before the worst algorithm is restarted.", new IntValue(minTries)));
      Parameters.Add(new ValueParameter<DoubleValue>("Restart.LastSuccessPercentage", "Only if the last found best solution is older than x percent of the total number of tries, the worst algorithm is restarted.", new DoubleValue(lastSuccessPercentage)));
    }

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

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      if (!Parameters.ContainsKey("EvaluatedSolutionsName"))
        Parameters.Add(new FixedValueParameter<StringValue>("EvaluatedSolutionsName", "The name of the result that shows the number of evaluated solutions by the actual solver.", new StringValue("EvaluatedSolutions")));
      if (!Parameters.ContainsKey("Restart"))
        Parameters.Add(new ValueParameter<BoolValue>(nameof(Restart), "Whether the worst algorithm should be restarted, if it doesn't find any better solutions.", new BoolValue(restart)));
      if (!Parameters.ContainsKey("Restart.MinTries"))
        Parameters.Add(new ValueParameter<IntValue>("Restart.MinTries", "The minimum number of tries before the worst algorithm is restarted.", new IntValue(minTries)));
      if (!Parameters.ContainsKey("Restart.LastSuccessPercentage"))
        Parameters.Add(new ValueParameter<DoubleValue>("Restart.LastSuccessPercentage", "Only if the last found best solution is older than x percent of the total number of tries, the worst algorithm is restarted.", new DoubleValue(lastSuccessPercentage)));
    }

    [Storable]
    private List<IAlgorithm> algorithms;
    [Storable]
    private int[] qualities;
    [Storable]
    private ResultCollection algorithmsResults;
    [Storable]
    private IndexedDataTable<double> qualityPerClock;
    [Storable]
    private IndexedDataTable<double> qualityPerEvaluations;
    [Storable]
    private bool restart = true;
    [Storable]
    private int minTries = 10000;
    [Storable]
    private double lastSuccessPercentage = 0.1;

    protected override void OnPrepared() {
      base.OnPrepared();
      algorithms = null;
      qualities = null;
      algorithmsResults = null;
      qualityPerClock = null;
      qualityPerEvaluations = null;
    }

    protected override void Initialize(CancellationToken cancellationToken) {
      var nests = Problem.ProcessingTimesParameter.Value.Count;
      algorithms = new List<IAlgorithm>(nests);
      algorithmsResults = new ResultCollection();
      for (var n = 0; n < nests; n++) {
        var clone = (IAlgorithm)SolverParameter.Value.Clone();
        clone.Prepare();
        var cfsap = (ICFSAP)clone.Problem;
        cfsap.ProcessingTimes = Problem.ProcessingTimes[n];
        cfsap.SetupTimes = Problem.SetupTimes[n];
        cfsap.UpdateEncoding();
        algorithms.Add(clone);
        algorithmsResults.Add(new Result($"Nest {n + 1}", clone.Results));
        clone.Start();
      }
      qualities = algorithms.Select(x => (int)((DoubleValue)x.Results["BestQuality"].Value).Value).ToArray();
      var worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
      var min = worst.Quality;

      qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
      var qpcRow = new IndexedDataRow<double>("First-hit Graph");
      qpcRow.Values.Add(Tuple.Create(ExecutionTime.TotalSeconds, (double)min));
      qpcRow.Values.Add(Tuple.Create(ExecutionTime.TotalSeconds, (double)min));
      qualityPerClock.Rows.Add(qpcRow);
      qualityPerEvaluations = new IndexedDataTable<double>("Quality per Evaluations");
      var qpeRow = new IndexedDataRow<double>("First-hit Graph");
      qualityPerEvaluations.Rows.Add(qpeRow);
      double evaluations = GetEvaluatedSolutions();
      qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
      qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));

      Results.Add(new Result("Nest with maximum T", new IntValue(worst.Index + 1)));
      Results.Add(new Result("Maximum T", new IntValue(min)));
      Results.Add(new Result("BestQuality", new DoubleValue(min)));
      Results.Add(new Result("Best Solution Found After Evaluated Solutions", new DoubleValue(evaluations)));
      Results.Add(new Result("Best Solution Found At", new TimeSpanValue(ExecutionTime)));
      Results.Add(new Result("Delta T", new PercentValue((min - Problem.BestKnownQuality) / Problem.BestKnownQuality)));
      Results.Add(new Result("Nest Results", algorithmsResults));
      Results.Add(new Result("QualityPerClock", qualityPerClock));
      Results.Add(new Result("QualityPerEvaluations", qualityPerEvaluations));
      Results.Add(new Result("Tries", new IntValue(nests)));
      Results.Add(new Result("Nests", new IntValue(nests)));
      Results.Add(new Result("Jobs", new IntValue(Problem.ProcessingTimes.First().Count() / Problem.SetupTimes.First().Count())));

      base.Initialize(cancellationToken);
    }

    private double GetEvaluatedSolutions() {
      if (algorithmsResults == null)
        throw new InvalidOperationException("Strategy has not been started yet.");
      return algorithmsResults.Select(x => {
        if (((ResultCollection)x.Value).TryGetValue(EvaluatedSolutionsName, out var res)) {
          var itm = res.Value;
          if (itm is IntValue)
            return ((IntValue)itm).Value;
          else if (itm is DoubleValue)
            return ((DoubleValue)itm).Value;
        }
        throw new InvalidOperationException($"No result {EvaluatedSolutionsName} in the collection of {x.Name}");
      }).Sum();
    }

    protected override void Run(CancellationToken cancellationToken) {
      var evaluationsPrevTries = 0.0;
      var worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
      var min = worst.Quality;

      var overallBestQualities = algorithms.Select(a => ((DoubleValue)a.Results["BestQuality"].Value).Value).ToArray();

      do {
        var tries = 0;
        var lastSuccess = 0;

        while (ExecutionTime < MaximumRuntime && !cancellationToken.IsCancellationRequested &&
            (!Restart || (tries < MinTries || (tries - lastSuccess) < tries * LastSuccessPercentage))) {
          ++tries;
          ++((IntValue)Results["Tries"].Value).Value;

          algorithms[worst.Index].Start(cancellationToken);
          qualities[worst.Index] = (int)((DoubleValue)algorithms[worst.Index].Results["BestQuality"].Value).Value;
          worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();

          var evaluations = evaluationsPrevTries + GetEvaluatedSolutions();
          var time = ExecutionTime.TotalSeconds;
          var qpcRow = qualityPerClock.Rows.First();
          var qpeRow = qualityPerEvaluations.Rows.First();
          qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, (double)Math.Min(worst.Quality, min));
          qpeRow.Values[qpeRow.Values.Count - 1] = Tuple.Create(evaluations, (double)Math.Min(worst.Quality, min));

          if (worst.Quality < min) {
            min = worst.Quality;
            overallBestQualities[worst.Index] = min;
            ((IntValue)Results["Nest with maximum T"].Value).Value = worst.Index + 1;
            ((IntValue)Results["Maximum T"].Value).Value = min;
            ((DoubleValue)Results["BestQuality"].Value).Value = min;
            ((DoubleValue)Results["Best Solution Found After Evaluated Solutions"].Value).Value = evaluations;
            ((TimeSpanValue)Results["Best Solution Found At"].Value).Value = TimeSpan.FromSeconds(time);
            ((PercentValue)Results["Delta T"].Value).Value = (min - Problem.BestKnownQuality) / Problem.BestKnownQuality;
            qpcRow.Values.Add(Tuple.Create(time, (double)min));
            qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
            lastSuccess = tries;
          }
        }

        if (cancellationToken.IsCancellationRequested || ExecutionTime >= MaximumRuntime || !Restart)
          break;

        evaluationsPrevTries += GetEvaluatedSolutions();

        // restart worst algorithm
        var worstAlgorithm = algorithms[worst.Index];
        var prevGenerations = ((IntValue)worstAlgorithm.Results["Generation"].Value).Value;
        var prevEvaluatedSolutions = ((IntValue)worstAlgorithm.Results["EvaluatedSolutions"].Value).Value;

        worstAlgorithm.Prepare();
        worstAlgorithm.Start(cancellationToken);
        ++((IntValue)Results["Tries"].Value).Value;

        ((IntValue)worstAlgorithm.Results["Generation"].Value).Value += prevGenerations;
        ((IntValue)worstAlgorithm.Results["EvaluatedSolutions"].Value).Value += prevEvaluatedSolutions;
      } while (Restart);

      for (var i = 0; i < algorithms.Count(); ++i) {
        if (overallBestQualities[i] < ((DoubleValue)algorithms[i].Results["BestQuality"].Value).Value) {
          ((DoubleValue)algorithms[i].Results["BestQuality"].Value).Value = overallBestQualities[i];
        }
      }
    }
  }
}