source: branches/PerformanceComparison/HeuristicLab.Analysis/3.3/Optimizers/IteratedAlgorithm.cs @ 12864

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

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

namespace HeuristicLab.Analysis {
  /// <summary>
  /// A run in which an algorithm is executed for a certain maximum time only.
  /// </summary>
  [Item("Iterated Algorithm", "An algorithm that repeats an algorithm until either a certain target value is reached or a maximum budget is exceeded.")]
  [Creatable(CreatableAttribute.Categories.TestingAndAnalysis, Priority = 116)]
  [StorableClass]
  public sealed class IteratedAlgorithm : Algorithm, IStorableContent {
    private const string ExecutionTimeResultName = "Execution Time";
    private const string BestQualityResultName = "BestQuality";
    private const string RandomRestartsResultName = "RandomRestarts";
    private const string EvaluatedSolutionsResultName = "EvaluatedSolutions";
    private const string EvaluatedMovesResultName = "EvaluatedMoves";
    private const string QualityPerClockResultName = "QualityPerClock";
    private const string QualityPerEvaluationsResultName = "QualityPerEvaluations";
    private const string EvaluationsResultName = "Evaluations";

    public string Filename { get; set; }

    public override Type ProblemType { get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); } }
    public new ISingleObjectiveHeuristicOptimizationProblem Problem {
      get { return (ISingleObjectiveHeuristicOptimizationProblem)base.Problem; }
      set {
        base.Problem = value;
        if (Algorithm != null) Algorithm.Problem = Problem;
        if (Problem != null) UpdateTargetValueFromBestKnownQuality();
      }
    }

    public IValueParameter<TimeSpanValue> MaximumExecutionTimeParameter {
      get { return (IValueParameter<TimeSpanValue>)Parameters["MaximumExecutionTime"]; }
    }

    public IValueParameter<IntValue> MaximumEvaluationsParameter {
      get { return (IValueParameter<IntValue>)Parameters["MaximumEvaluations"]; }
    }

    public IValueParameter<DoubleValue> TargetValueParameter {
      get { return (IValueParameter<DoubleValue>)Parameters["TargetValue"]; }
    }

    private IFixedValueParameter<DoubleValue> MoveCostPerSolutionParameter {
      get { return (IFixedValueParameter<DoubleValue>)Parameters["MoveCostPerSolution"]; }
    }

    private IFixedValueParameter<BoolValue> StoreSolutionInRunParameter {
      get { return (IFixedValueParameter<BoolValue>)Parameters["StoreSolutionInRun"]; }
    }

    private IValueParameter<IAlgorithm> AlgorithmParameter {
      get { return (IValueParameter<IAlgorithm>)Parameters["Algorithm"]; }
    }

    [Storable]
    private ResultCollection results;
    public override ResultCollection Results {
      get { return results; }
    }

    [Storable]
    private QualityPerClockAnalyzer perClockAnalyzer;
    [Storable]
    private QualityPerEvaluationsAnalyzer perEvaluationsAnalyzer;

    public double MoveCostPerSolution {
      get { return MoveCostPerSolutionParameter.Value.Value; }
      set { MoveCostPerSolutionParameter.Value.Value = value; }
    }

    public bool StoreSolutionInRun {
      get { return StoreSolutionInRunParameter.Value.Value; }
      set { StoreSolutionInRunParameter.Value.Value = value; }
    }

    private IAlgorithm algorithm;
    public IAlgorithm Algorithm {
      get { return algorithm; }
      set {
        if (algorithm == value) return;
        if (algorithm != null) {
          DeregisterAlgorithmEvents();
          RemoveAlgorithmAnalyzers();
        }
        algorithm = value;
        if (algorithm != null) {
          if (algorithm.ExecutionState != ExecutionState.Prepared)
            algorithm.Prepare(true);
          algorithm.Problem = Problem;
          RegisterAlgorithmEvents();
          AddAlgorithmAnalyzers();
        }
        if (AlgorithmParameter.Value != algorithm)
          AlgorithmParameter.Value = algorithm;
        Prepare();
      }
    }

    private bool Maximization {
      get { return Problem != null && ((IValueParameter<BoolValue>)Problem.MaximizationParameter).Value.Value; }
    }

    private bool IsFinished {
      get {
        var executionTime = Results.ContainsKey(ExecutionTimeResultName) ? ((TimeSpanValue)Results[ExecutionTimeResultName].Value).Value : TimeSpan.Zero;
        var evaluations = Results.ContainsKey(EvaluationsResultName) ? ((DoubleValue)Results[EvaluationsResultName].Value).Value : 0;
        var bestQuality = Results.ContainsKey(BestQualityResultName) ? ((DoubleValue)Results[BestQualityResultName].Value).Value
                                                                     : (Maximization ? double.MinValue : double.MaxValue);
        var targetValue = TargetValueParameter.Value != null ? TargetValueParameter.Value.Value
                                                             : Maximization ? double.MaxValue : double.MinValue;

        var timeHit = MaximumExecutionTimeParameter.Value != null && executionTime >= MaximumExecutionTimeParameter.Value.Value;
        var evalHit = MaximumEvaluationsParameter.Value != null && evaluations >= MaximumEvaluationsParameter.Value.Value;
        var targetHit = Maximization && bestQuality >= targetValue || !Maximization && bestQuality <= targetValue;

        return timeHit || evalHit || targetHit;
      }
    }

    [StorableConstructor]
    private IteratedAlgorithm(bool deserializing) : base(deserializing) { }
    private IteratedAlgorithm(IteratedAlgorithm original, Cloner cloner)
      : base(original, cloner) {
      results = cloner.Clone(original.Results);
      perClockAnalyzer = cloner.Clone(original.perClockAnalyzer);
      perEvaluationsAnalyzer = cloner.Clone(original.perEvaluationsAnalyzer);
      algorithm = cloner.Clone(original.algorithm);
      RegisterEventHandlers();
    }
    public IteratedAlgorithm()
      : base() {
      results = new ResultCollection();
      Parameters.Add(new OptionalValueParameter<TimeSpanValue>("MaximumExecutionTime", "The maximum wall-clock time that the algorithm should run."));
      Parameters.Add(new OptionalValueParameter<IntValue>("MaximumEvaluations", "The maximum number of function evaluations that the algorithm should run.", new IntValue(100000000)));
      Parameters.Add(new OptionalValueParameter<DoubleValue>("TargetValue", "The target value that the algorithm should run for."));
      Parameters.Add(new FixedValueParameter<DoubleValue>("MoveCostPerSolution", "The amount of solution evaluation equivalents of a single move. Use 1 for a black-box scenario.", new DoubleValue(1)));
      Parameters.Add(new FixedValueParameter<BoolValue>("StoreSolutionInRun", "Whether the solution data types should be kept in the run."));
      Parameters.Add(new ValueParameter<IAlgorithm>("Algorithm", "The algorithm to iterate.") { GetsCollected = false }); // due to storage efficiency, by default we don't want to store the algorithm instance in the run

      perClockAnalyzer = new QualityPerClockAnalyzer();
      perEvaluationsAnalyzer = new QualityPerEvaluationsAnalyzer();

      RegisterEventHandlers();
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      if (ExecutionState == ExecutionState.Started) throw new InvalidOperationException(string.Format("Clone not allowed in execution state \"{0}\".", ExecutionState));
      return new IteratedAlgorithm(this, cloner);
    }

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      algorithm = AlgorithmParameter.Value;
      RegisterEventHandlers();
    }

    #region Register Event Handlers
    protected override void RegisterProblemEvents() {
      var bkParam = Problem.BestKnownQualityParameter as IValueParameter<DoubleValue>;
      if (bkParam != null) {
        bkParam.ValueChanged += Problem_BestKnownQualityParameter_ValueChanged;
      }
      base.RegisterProblemEvents();
    }
    protected override void DeregisterProblemEvents() {
      base.DeregisterProblemEvents();
      var bkParam = Problem.BestKnownQualityParameter as IValueParameter<DoubleValue>;
      if (bkParam != null) {
        bkParam.ValueChanged -= Problem_BestKnownQualityParameter_ValueChanged;
      }
    }
    private void RegisterAlgorithmEvents() {
      Algorithm.ExceptionOccurred += Algorithm_ExceptionOccurred;
      Algorithm.Paused += Algorithm_Paused;
      Algorithm.Stopped += Algorithm_Stopped;
      Algorithm.ProblemChanged += Algorithm_ProblemChanged;
    }
    private void DeregisterAlgorithmEvents() {
      Algorithm.ExceptionOccurred -= Algorithm_ExceptionOccurred;
      Algorithm.Paused -= Algorithm_Paused;
      Algorithm.Stopped -= Algorithm_Stopped;
      Algorithm.ProblemChanged -= Algorithm_ProblemChanged;
    }
    #endregion

    private void RegisterEventHandlers() {
      if (Algorithm != null) RegisterAlgorithmEvents();
      if (Problem != null) RegisterProblemEvents();
      AlgorithmParameter.ValueChanged += AlgorithmParameterOnValueChanged;
    }

    private void AlgorithmParameterOnValueChanged(object sender, EventArgs eventArgs) {
      Algorithm = AlgorithmParameter.Value;
    }

    #region Prepare, Start, Pause, Stop
    public override void Prepare() {
      if (Problem == null || Algorithm == null) return;

      Algorithm.Prepare(true);

      results.Clear();
      OnPrepared();
    }

    public override void Start() {
      base.Start();
      OnStarted();
      var task = Task.Factory.StartNew(Run, null);
      task.ContinueWith(t => {
        try {
          t.Wait();
        } catch (AggregateException ex) {
          try {
            ex.Flatten().Handle(x => x is OperationCanceledException);
          } catch (AggregateException remaining) {
            if (remaining.InnerExceptions.Count == 1) OnExceptionOccurred(remaining.InnerExceptions[0]);
            else OnExceptionOccurred(remaining);
          }
        }
        if (Algorithm.ExecutionState == ExecutionState.Paused) OnPaused();
        else OnStopped();
      });
    }

    public override void Pause() {
      base.Pause();
      Algorithm.Pause();
    }

    public override void Stop() {
      base.Stop();
      Algorithm.Stop();
    }
    #endregion

    private DateTime lastUpdateTime;
    private void Run(object state) {
      lastUpdateTime = DateTime.UtcNow;
      System.Timers.Timer timer = new System.Timers.Timer(250);
      timer.AutoReset = true;
      timer.Elapsed += timer_Elapsed;
      timer.Start();
      try {
        Run();
      } finally {
        timer.Elapsed -= timer_Elapsed;
        timer.Stop();
        ExecutionTime += DateTime.UtcNow - lastUpdateTime;
      }
    }

    private readonly AutoResetEvent algorithmWaitHandle = new AutoResetEvent(false);
    private void Run() {
      if (!Results.ContainsKey(ExecutionTimeResultName)) Results.Add(new Result(ExecutionTimeResultName, new TimeSpanValue(TimeSpan.Zero)));
      if (!Results.ContainsKey(EvaluatedSolutionsResultName)) Results.Add(new Result(EvaluatedSolutionsResultName, new DoubleValue(0)));
      if (!Results.ContainsKey(EvaluatedMovesResultName)) Results.Add(new Result(EvaluatedMovesResultName, new DoubleValue(0)));
      if (!Results.ContainsKey(EvaluationsResultName)) Results.Add(new Result(EvaluationsResultName, new DoubleValue(0)));
      if (!Results.ContainsKey(BestQualityResultName)) Results.Add(new Result(BestQualityResultName, new DoubleValue(double.NaN)));

      do {
        if (!Results.ContainsKey(RandomRestartsResultName)) Results.Add(new Result(RandomRestartsResultName, new IntValue(0)));
        else if (Algorithm.ExecutionState == ExecutionState.Prepared) ((IntValue)Results[RandomRestartsResultName].Value).Value++;

        Algorithm.Start();
        algorithmWaitHandle.WaitOne();

        if (Algorithm.ExecutionState == ExecutionState.Paused) return;

        var execTime = ((TimeSpanValue)Results[ExecutionTimeResultName].Value);
        var solEvals = ((DoubleValue)Results[EvaluatedSolutionsResultName].Value);
        var movEvals = ((DoubleValue)Results[EvaluatedMovesResultName].Value);
        var restarts = ((IntValue)Results[RandomRestartsResultName].Value);
        var evaluations = ((DoubleValue)Results[EvaluationsResultName].Value);
        var bestQuality = ((DoubleValue)Results[BestQualityResultName].Value);
        var improvement = false;

        IResult result;
        if (Algorithm.Results.TryGetValue(perEvaluationsAnalyzer.EvaluatedSolutionsParameter.ActualName, out result)) {
          var evals = ((IntValue)result.Value).Value;
          evaluations.Value += evals;
          solEvals.Value += evals;
        }
        if (Algorithm.Results.TryGetValue(perEvaluationsAnalyzer.EvaluatedMovesParameter.ActualName, out result)) {
          var evals = ((IntValue)result.Value).Value;
          evaluations.Value += MoveCostPerSolution * evals;
          movEvals.Value += evals;
        }
        if (Algorithm.Results.TryGetValue(perEvaluationsAnalyzer.BestQualityParameter.ActualName, out result)) {
          var newBestQuality = ((DoubleValue)result.Value).Value;
          if (double.IsNaN(bestQuality.Value)
              || Maximization && newBestQuality > bestQuality.Value
              || !Maximization && newBestQuality < bestQuality.Value) {
            bestQuality.Value = newBestQuality;
            improvement = true;
          }
        }
        if (Algorithm.Results.TryGetValue(perClockAnalyzer.QualityPerClockParameter.ResultName, out result)) {
          UpdateQualityPerClockResult((IndexedDataTable<double>)result.Value, restarts.Value);
        }
        if (Algorithm.Results.TryGetValue(perEvaluationsAnalyzer.QualityPerEvaluationsParameter.ResultName, out result)) {
          UpdateQualityPerEvaluationsResult((IndexedDataTable<double>)result.Value, restarts.Value);
        }
        if (StoreSolutionInRun) {
          foreach (var r in Algorithm.Results) {
            if (r.Name.ToLower().EndsWith("solution") && improvement) {
              if (!Results.TryGetValue(r.Name, out result))
                Results.Add(new Result(r.Name, (IItem)r.Value.Clone()));
              else result.Value = (IItem)r.Value.Clone();
            }
          }
        }

        execTime.Value = ExecutionTime;

        Algorithm.Prepare(true);
      } while (!IsFinished);
    }

    private void UpdateQualityPerClockResult(IndexedDataTable<double> perClock, int restarts) {
      IndexedDataTable<double> dt;
      if (!Results.ContainsKey(QualityPerClockResultName)) {
        dt = (IndexedDataTable<double>)perClock.Clone();
        if (!dt.Rows.ContainsKey("Restarts"))
          dt.Rows.Add(new IndexedDataRow<double>("Restarts") {
            VisualProperties = {
              ChartType = DataRowVisualProperties.DataRowChartType.StepLine,
              SecondYAxis = true
            }
          });
        foreach (var v in dt.Rows.First().Values)
          dt.Rows["Restarts"].Values.Add(Tuple.Create(v.Item1, 0.0));
        Results.Add(new Result(QualityPerClockResultName, dt));
      } else {
        dt = (IndexedDataTable<double>)Results[QualityPerClockResultName].Value;
        var qualityValues = dt.Rows.First().Values;
        var restartValues = dt.Rows["Restarts"].Values;
        var best = qualityValues.Last().Item2;
        var execTime = qualityValues.Last().Item1;
        var improvement = false;
        foreach (var tupl in perClock.Rows.First().Values) {
          if (Maximization && tupl.Item2 > best || !Maximization && tupl.Item2 < best) {
            if (!improvement) {
              // the last entry always holds the same value, but with highest execution time
              qualityValues.RemoveAt(qualityValues.Count - 1);
              restartValues.RemoveAt(restartValues.Count - 1);
              improvement = true;
            }
            qualityValues.Add(Tuple.Create(execTime + tupl.Item1, tupl.Item2));
            restartValues.Add(Tuple.Create(execTime + tupl.Item1, (double)restarts));
            best = tupl.Item2;
          }
        }
        if (improvement) {
          var totalExecTime = execTime + perClock.Rows.First().Values.Last().Item1;
          qualityValues.Add(Tuple.Create(totalExecTime, best));
          restartValues.Add(Tuple.Create(totalExecTime, (double)restarts));
        }
      }
    }

    private void UpdateQualityPerEvaluationsResult(IndexedDataTable<double> perEvaluations, int restarts) {
      IndexedDataTable<double> dt;
      if (!Results.ContainsKey(QualityPerEvaluationsResultName)) {
        dt = (IndexedDataTable<double>)perEvaluations.Clone();
        if (!dt.Rows.ContainsKey("Restarts"))
          dt.Rows.Add(new IndexedDataRow<double>("Restarts") {
            VisualProperties = {
              ChartType = DataRowVisualProperties.DataRowChartType.StepLine,
              SecondYAxis = true
            }
          });
        foreach (var v in dt.Rows.First().Values)
          dt.Rows["Restarts"].Values.Add(Tuple.Create(v.Item1, 0.0));
        Results.Add(new Result(QualityPerEvaluationsResultName, dt));
      } else {
        dt = (IndexedDataTable<double>)Results[QualityPerEvaluationsResultName].Value;
        var qualityValues = dt.Rows.First().Values;
        var restartValues = dt.Rows["Restarts"].Values;
        var best = qualityValues.Last().Item2;
        var evaluations = qualityValues.Last().Item1;
        var improvement = false;
        foreach (var tupl in perEvaluations.Rows.First().Values) {
          if (Maximization && tupl.Item2 > best || !Maximization && tupl.Item2 < best) {
            if (!improvement) {
              // the last entry always holds the same value, but with highest evaluations
              qualityValues.RemoveAt(qualityValues.Count - 1);
              restartValues.RemoveAt(restartValues.Count - 1);
              improvement = true;
            }
            qualityValues.Add(Tuple.Create(evaluations + tupl.Item1, tupl.Item2));
            restartValues.Add(Tuple.Create(evaluations + tupl.Item1, (double)restarts));
            best = tupl.Item2;
          }
        }
        if (improvement) { // add the best quality again as value with highest evaluations
          var totalEvaluations = evaluations + perEvaluations.Rows.First().Values.Last().Item1;
          qualityValues.Add(Tuple.Create(totalEvaluations, best));
          restartValues.Add(Tuple.Create(totalEvaluations, (double)restarts));
        }
      }
    }

    private void UpdateTargetValueFromBestKnownQuality() {
      var bkParam = Problem.BestKnownQualityParameter as IValueParameter<DoubleValue>;
      if (bkParam != null && bkParam.Value != null)
        TargetValueParameter.Value = new DoubleValue(bkParam.Value.Value);
      else if (bkParam != null && bkParam.Value == null)
        TargetValueParameter.Value = null;
    }

    private void AddAlgorithmAnalyzers() {
      if (Algorithm == null) return;
      if (!Algorithm.Parameters.ContainsKey("Analyzer")) return;
      var analyzerParam = Algorithm.Parameters["Analyzer"] as IValueParameter<MultiAnalyzer>;
      if (analyzerParam != null) {
        foreach (var analyzer in analyzerParam.Value.Operators.OfType<QualityPerClockAnalyzer>().ToList())
          analyzerParam.Value.Operators.Remove(analyzer);
        analyzerParam.Value.Operators.Add(perClockAnalyzer);
        foreach (var analyzer in analyzerParam.Value.Operators.OfType<QualityPerEvaluationsAnalyzer>().ToList())
          analyzerParam.Value.Operators.Remove(analyzer);
        analyzerParam.Value.Operators.Add(perEvaluationsAnalyzer);
      } else {
        var analyzerParam2 = Algorithm.Parameters["Analyzer"] as IValueParameter<IMultiAnalyzer>;
        if (analyzerParam2 == null) return;
        foreach (var analyzer in analyzerParam2.Value.Operators.OfType<QualityPerClockAnalyzer>().ToList())
          analyzerParam2.Value.Operators.Remove(analyzer);
        analyzerParam2.Value.Operators.Add(perClockAnalyzer);
        foreach (var analyzer in analyzerParam2.Value.Operators.OfType<QualityPerEvaluationsAnalyzer>().ToList())
          analyzerParam2.Value.Operators.Remove(analyzer);
        analyzerParam2.Value.Operators.Add(perEvaluationsAnalyzer);
      }
    }

    private void RemoveAlgorithmAnalyzers() {
      if (Algorithm == null) return;
      if (!Algorithm.Parameters.ContainsKey("Analyzer")) return;
      var analyzerParam = Algorithm.Parameters["Analyzer"] as IValueParameter<MultiAnalyzer>;
      if (analyzerParam != null) {
        analyzerParam.Value.Operators.Remove(perClockAnalyzer);
        analyzerParam.Value.Operators.Remove(perEvaluationsAnalyzer);
      } else {
        var analyzerParam2 = Algorithm.Parameters["Analyzer"] as IValueParameter<IMultiAnalyzer>;
        if (analyzerParam2 != null) {
          analyzerParam2.Value.Operators.Remove(perClockAnalyzer);
          analyzerParam2.Value.Operators.Remove(perEvaluationsAnalyzer);
        }
      }
    }

    #region Event Handlers
    private void Algorithm_ExceptionOccurred(object sender, EventArgs<Exception> e) {
      OnExceptionOccurred(e.Value);
    }
    private void Algorithm_Paused(object sender, EventArgs e) {
      algorithmWaitHandle.Set();
    }
    private void Algorithm_Stopped(object sender, EventArgs e) {
      algorithmWaitHandle.Set();
    }

    private void Algorithm_ProblemChanged(object sender, EventArgs e) {
      if (Algorithm.Problem != Problem) Problem = (ISingleObjectiveHeuristicOptimizationProblem)Algorithm.Problem;
      AddAlgorithmAnalyzers();
    }

    private void Problem_BestKnownQualityParameter_ValueChanged(object sender, EventArgs e) {
      var param = sender as IValueParameter<DoubleValue>;
      if (param != null) {
        if (param.Value != null) param.Value.ValueChanged += Problem_BestKnownQualityParameter_Value_ValueChanged;
        UpdateTargetValueFromBestKnownQuality();
      }
    }

    private void Problem_BestKnownQualityParameter_Value_ValueChanged(object sender, EventArgs e) {
      UpdateTargetValueFromBestKnownQuality();
    }

    protected override void Problem_Reset(object sender, EventArgs eventArgs) {
      if (Algorithm != null) AddAlgorithmAnalyzers();
    }

    protected override void Problem_OperatorsChanged(object sender, EventArgs eventArgs) {
      if (Algorithm != null) AddAlgorithmAnalyzers();
    }

    private void timer_Elapsed(object sender, System.Timers.ElapsedEventArgs e) {
      System.Timers.Timer timer = (System.Timers.Timer)sender;
      timer.Enabled = false;
      DateTime now = DateTime.UtcNow;
      ExecutionTime += now - lastUpdateTime;
      lastUpdateTime = now;
      timer.Enabled = true;
    }
    #endregion
  }
}