source: branches/PerformanceComparison/HeuristicLab.Optimization.Views/3.3/RunCollectionViews/RunCollectionIteratedSamplingView.cs @ 13485

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2015 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.Collections.Generic;
using System.ComponentModel;
using System.Globalization;
using System.Linq;
using System.Windows.Forms.DataVisualization.Charting;
using HeuristicLab.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Data;
using HeuristicLab.MainForm;
using HeuristicLab.MainForm.WindowsForms;

namespace HeuristicLab.Optimization.Views.RunCollectionViews {
  [View("Run-length Cut-off Estimation View")]
  [Content(typeof(RunCollection), IsDefaultView = false)]
  public sealed partial class RunCollectionIteratedSamplingView : AsynchronousContentView {
    private bool suppressEvents;

    public new RunCollection Content {
      get { return (RunCollection)base.Content; }
      set { base.Content = value; }
    }

    public RunCollectionIteratedSamplingView() {
      InitializeComponent();
    }

    protected override void DeregisterContentEvents() {
      base.DeregisterContentEvents();
    }

    protected override void RegisterContentEvents() {
      base.RegisterContentEvents();
    }

    protected override void OnContentChanged() {
      base.OnContentChanged();
      suppressEvents = true;
      try {
        UpdateGroupComboBox();
        RecalculateTarget();
      } finally { suppressEvents = false; }
    }

    protected override void SetEnabledStateOfControls() {
      base.SetEnabledStateOfControls();
      groupComboBox.Enabled = Content != null;
      groupInstanceComboBox.Enabled = Content != null && groupInstanceComboBox.Items.Count > 1;
      problemComboBox.Enabled = Content != null && problemComboBox.Items.Count > 1;
      dataTableComboBox.Enabled = Content != null && dataTableComboBox.Items.Count > 1;
    }

    private void UpdateGroupComboBox() {
      try {

        var selectedGroupItem = (string)groupComboBox.SelectedItem;
        groupComboBox.Items.Clear();
        groupComboBox.SelectedItem = null;

        var paramNames = Content.ParameterNames.OrderBy(x => x, new NaturalStringComparer());
        foreach (var name in paramNames) {
          groupComboBox.Items.Add(name);
          if (selectedGroupItem == name) groupComboBox.SelectedItem = name;
        }
        if (groupComboBox.SelectedItem == null && groupComboBox.Items.Count > 0)
          groupComboBox.SelectedItem = groupComboBox.Items[0];

      } finally { UpdateGroupInstanceComboBox(); }
    }

    private void UpdateGroupInstanceComboBox() {
      try {

        var selectedGroupInstanceItem = (string)groupInstanceComboBox.SelectedItem;
        groupInstanceComboBox.Items.Clear();
        groupInstanceComboBox.SelectedItem = null;

        var selectedGroupItem = (string)groupComboBox.SelectedItem;
        if (selectedGroupItem == null) return;

        var paramValues = GetRunsFiltered()
                              .Select(x => x.Parameters[selectedGroupItem].ToString())
                              .Distinct()
                              .OrderBy(x => x, new NaturalStringComparer());
        foreach (var value in paramValues) {
          groupInstanceComboBox.Items.Add(value);
          if (selectedGroupInstanceItem == value) groupInstanceComboBox.SelectedItem = value;
        }
        if (groupInstanceComboBox.SelectedItem == null && groupInstanceComboBox.Items.Count > 0)
          groupInstanceComboBox.SelectedItem = groupInstanceComboBox.Items[0];

      } finally { UpdateProblemCombobBox(); }
    }

    private void UpdateProblemCombobBox() {
      try {

        var selectedProblemItem = (ProblemDescription)problemComboBox.SelectedItem;
        problemComboBox.Items.Clear();
        problemComboBox.SelectedItem = null;

        var problems = new HashSet<ProblemDescription>();
        foreach (var run in GetRunsFiltered()) {
          problems.Add(new ProblemDescription(run));
        }

        var problemTypesDifferent = problems.Select(x => x.ProblemType).Where(x => !string.IsNullOrEmpty(x)).Distinct().Count() > 1;
        var problemNamesDifferent = problems.Select(x => x.ProblemName).Where(x => !string.IsNullOrEmpty(x)).Distinct().Count() > 1;
        var evaluatorDifferent = problems.Select(x => x.Evaluator).Where(x => !string.IsNullOrEmpty(x)).Distinct().Count() > 1;
        var allEqual = !problemTypesDifferent && !problemNamesDifferent && !evaluatorDifferent;

        foreach (var prob in problems.OrderBy(x => x.ToString()).ToList()) {
          prob.DisplayProblemType = problemTypesDifferent;
          prob.DisplayProblemName = problemNamesDifferent || allEqual;
          prob.DisplayEvaluator = evaluatorDifferent;
          problemComboBox.Items.Add(prob);
          if (prob.Equals(selectedProblemItem)) problemComboBox.SelectedItem = prob;
        }

        if (problemComboBox.SelectedItem == null && problemComboBox.Items.Count > 0) {
          problemComboBox.SelectedItem = problemComboBox.Items[0];
          RecalculateTarget();
        }

      } finally { UpdateDataTableComboBox(); }
    }

    private void UpdateDataTableComboBox() {
      var selectedItem = (string)dataTableComboBox.SelectedItem;
      dataTableComboBox.Items.Clear();
      dataTableComboBox.SelectedItem = null;

      var dataTables = (from run in GetRunsFiltered()
                        from result in run.Results
                        where result.Value is IndexedDataTable<double>
                        select result.Key).Distinct().OrderBy(x => x, new NaturalStringComparer());

      foreach (var dt in dataTables) {
        dataTableComboBox.Items.Add(dt);
        if (selectedItem == dt) dataTableComboBox.SelectedItem = dt;
      }
      if (dataTableComboBox.SelectedItem == null && dataTableComboBox.Items.Count > 0)
        dataTableComboBox.SelectedItem = dataTableComboBox.Items[0];
    }

    private IEnumerable<IRun> GetRunsFiltered() {
      var result = Content.Where(x => x.Visible);

      var selectedGroup = (string)groupComboBox.SelectedItem;
      if (!string.IsNullOrEmpty(selectedGroup)) {
        result = result.Where(x => x.Parameters.ContainsKey(selectedGroup));

        var selectedGroupInstance = (string)groupInstanceComboBox.SelectedItem;
        if (!string.IsNullOrEmpty(selectedGroupInstance))
          result = result.Where(x => x.Parameters[selectedGroup].ToString() == selectedGroupInstance);
      }
      var selectedProblem = (ProblemDescription)problemComboBox.SelectedItem;
      if (selectedProblem != null)
        result = result.Where(x => selectedProblem.Match(x));

      return result;
    }

    private void groupComboBox_SelectedIndexChanged(object sender, EventArgs e) {
      if (suppressEvents) return;
      suppressEvents = true;
      try {
        UpdateGroupInstanceComboBox();
      } finally { suppressEvents = false; }

      UpdateOptimalCutoff();
    }

    private void groupInstanceComboBox_SelectedIndexChanged(object sender, EventArgs e) {
      if (suppressEvents) return;
      suppressEvents = true;
      try {
        UpdateProblemCombobBox();
      } finally { suppressEvents = false; }

      UpdateOptimalCutoff();
    }

    private void problemComboBox_SelectedIndexChanged(object sender, EventArgs e) {
      if (suppressEvents) return;
      suppressEvents = true;
      try {
        UpdateDataTableComboBox();
        RecalculateTarget();
      } finally { suppressEvents = false; }

      UpdateOptimalCutoff();
    }

    private void dataTableComboBox_SelectedIndexChanged(object sender, EventArgs e) {
      if (suppressEvents) return;

      UpdateOptimalCutoff();
    }

    private void RecalculateTarget() {
      var problemDesc = (ProblemDescription)problemComboBox.SelectedItem;
      var dataTable = (string)dataTableComboBox.SelectedItem;
      if (problemDesc == null || dataTable == null) return;
      var target = CalculateBestTarget(problemDesc, dataTable, IsMaximization());
      targetTextBox.Text = target.ToString(CultureInfo.CurrentCulture.NumberFormat);
    }

    private void targetTextBox_Validating(object sender, CancelEventArgs e) {
      if (InvokeRequired)
        if (suppressEvents) return;
      double target;
      if (!double.TryParse(targetTextBox.Text, out target)) {
        e.Cancel = true;
        errorProvider.SetError(targetTextBox, "Please enter a valid fitness value.");
        return;
      }
      errorProvider.SetError(targetTextBox, null);

      UpdateOptimalCutoff();
    }

    private void UpdateOptimalCutoff() {
      double target;
      if (!double.TryParse(targetTextBox.Text, NumberStyles.Float, CultureInfo.CurrentCulture.NumberFormat, out target)) return;

      var resultName = (string)dataTableComboBox.SelectedItem;
      if (resultName == null) return;

      var pool = GetRunsFiltered()
                  .Where(x => x.Results.ContainsKey(resultName) && x.Results[resultName] is IndexedDataTable<double>)
                  .Select(x => (IndexedDataTable<double>)x.Results[resultName]).ToList();
      if (pool.Count == 0) return;

      var maximization = IsMaximization();

      var data = pool.Select(x => x.Rows.First().Values.SkipWhile(y => !HasAchievedTarget(maximization, y, target)).FirstOrDefault() /* get the entry where the run reached the target */
                                  ?? Tuple.Create(x.Rows.First().Values.Last().Item1, double.NaN) /* otherwise note the maximum effort */)
                     .Where(x => !x.Equals(default(Tuple<double, double>))).OrderBy(x => x.Item1).ToList();
      double prob;
      var cutoff = CalculateOptimalCutoff(data, maximization, target, out prob);
      optimalCutOffTextBox.Text = cutoff.ToString(CultureInfo.CurrentCulture.NumberFormat);
      UpdateGraph(cutoff, prob, target, maximization);
    }

    private double CalculateOptimalCutoff(List<Tuple<double, double>> data, bool maximization, double target, out double bestProbability) {
      bestProbability = 1.0;
      var bestProbabilityEffort = 0.0;
      var succ = 0;
      foreach (var d in data) {
        if (double.IsNaN(d.Item2)) continue;
        if (HasAchievedTarget(maximization, d, target)) succ++;
        // probability of having no successful run with effort d.Item1
        var prob = (1.0 - succ / (double)data.Count);
        // normalizing probability to effort 1 (assuming exponential convergence)
        prob = Math.Pow(prob, 1.0 / d.Item1);
        if (prob < bestProbability) {
          bestProbability = prob;
          bestProbabilityEffort = d.Item1;
        }
      }
      return bestProbabilityEffort;
    }

    private bool HasAchievedTarget(bool maximization, Tuple<double, double> y, double target) {
      return maximization ? y.Item2 >= target : y.Item2 <= target;
    }

    private void UpdateGraph(double cutoff, double bestProbability, double target, bool maximization) {
      var table = (string)dataTableComboBox.SelectedItem;
      var runs = GetRunsFiltered().Select(x => (IndexedDataTable<double>)x.Results[table]).ToList();
      var evaluations = runs.SelectMany(x => x.Rows.First().Values.Select(y => y.Item1)).Distinct().OrderBy(x => x).ToList();
      var totalRuns = evaluations.ToDictionary(x => x, x => 0);
      var hits = evaluations.ToDictionary(x => x, x => 0.0);
      foreach (var r in runs) {
        var evalIter = evaluations.GetEnumerator();
        evalIter.MoveNext();
        var eff = evalIter.Current;
        var evalIterAbort = false;
        var targetFirstReached = double.MaxValue;
        foreach (var v in r.Rows.First().Values) {
          if (targetFirstReached == double.MaxValue && (maximization && v.Item2 >= target || !maximization && v.Item2 <= target))
            targetFirstReached = v.Item1;
          while (eff <= v.Item1) {
            totalRuns[eff]++;
            if (eff >= targetFirstReached) hits[eff]++;
            if (evalIter.MoveNext())
              eff = evalIter.Current;
            else {
              evalIterAbort = true;
              break;
            }
          }
        }
        if (!evalIterAbort) {
          do {
            eff = evalIter.Current;
            totalRuns[eff]++;
            if (eff >= targetFirstReached) hits[eff]++;
          } while (evalIter.MoveNext());
        }
      }

      foreach (var e in evaluations) {
        hits[e] /= totalRuns[e];
      }

      enhancedChart.SuspendRepaint();

      var cutOffIdx = -1;
      var series = enhancedChart.Series["rldSeries"];
      series.Points.Clear();
      foreach (var h in hits) {
        series.Points.AddXY(h.Key, h.Value);
        if (h.Key <= cutoff) cutOffIdx++;
      }

      var series2 = enhancedChart.Series["rldApproximationSeries"];
      series2.Points.Clear();
      var evalMax = evaluations.Max();
      var steps = evalMax / 100.0;

      var result = ExpectedRuntimeHelper.CalculateErt(GetRunsFiltered().ToList(), table, target, maximization);
      var lambda = 1.0 / result.ExpectedRuntime;
      foreach (var e in Enumerable.Range(0, 100)) {
        var x = e * steps;
        series2.Points.AddXY(x, Math.Max(0, 1.0 - Math.Exp(-lambda * x)));
      }
      var series3 = enhancedChart.Series["optimalSeries"];
      series3.Points.Clear();
      if (bestProbability <= 0) bestProbability = 1 - lambda;
      foreach (var e in Enumerable.Range(0, 100)) {
        var x = e * steps;
        series3.Points.AddXY(x, Math.Max(0, 1.0 - Math.Pow(bestProbability, x)));
      }

      enhancedChart.Annotations.Clear();
      if (cutOffIdx >= 0) {
        var annotation = new VerticalLineAnnotation();
        annotation.AnchorDataPoint = series.Points[cutOffIdx];
        annotation.Height = series.Points[cutOffIdx].YValues[0] > enhancedChart.ChartAreas[series.ChartArea].AxisY.Maximum / 2.0 ? 10 : -10;
        annotation.LineWidth = 2;
        annotation.StartCap = LineAnchorCapStyle.Arrow;
        enhancedChart.Annotations.Add(annotation);
      }
      enhancedChart.ResumeRepaint(true);
    }

    #region Helpers
    // Determines if the RunCollection contains maximization or minimization runs
    private bool IsMaximization() {
      if (Content == null) return false;
      foreach (var run in GetRunsFiltered().Where(x => x.Parameters.ContainsKey("Maximization"))) {
        var maximization = run.Parameters["Maximization"] as BoolValue;
        if (maximization == null) continue;
        return maximization.Value;
      }
      var selectedTable = (string)dataTableComboBox.SelectedItem;
      if (selectedTable != null) {
        foreach (var run in GetRunsFiltered().Where(x => x.Results.ContainsKey(selectedTable))) {
          var table = run.Results[selectedTable] as IndexedDataTable<double>;
          if (table == null) continue;
          var firstRowValues = table.Rows.First().Values;
          if (firstRowValues.Count < 2) continue;
          return firstRowValues[0].Item2 < firstRowValues[firstRowValues.Count - 1].Item2;
        }
      }
      // assume minimization by default
      return false;
    }

    private double CalculateBestTarget(ProblemDescription pd, string dataTableResult, bool maximization) {
      var targets = (from r in Content
                     where r.Visible && pd.Match(r)
                     let target = r.Parameters.ContainsKey("BestKnownQuality")
                                  && r.Parameters["BestKnownQuality"] is DoubleValue
                       ? ((DoubleValue)r.Parameters["BestKnownQuality"]).Value
                       : ((IndexedDataTable<double>)r.Results[dataTableResult]).Rows.First().Values.Last().Item2
                     select target);
      return maximization ? targets.Max() : targets.Min();
    }
    #endregion

    private class ProblemDescription {

      private ProblemDescription() {
        ProblemType = string.Empty;
        ProblemName = string.Empty;
        Evaluator = string.Empty;
        DisplayProblemType = false;
        DisplayProblemName = false;
        DisplayEvaluator = false;
      }

      public ProblemDescription(IRun run) {
        ProblemType = GetStringValueOrEmpty(run, "Problem Type");
        ProblemName = GetStringValueOrEmpty(run, "Problem Name");
        Evaluator = GetStringValueOrEmpty(run, "Evaluator");
        DisplayProblemType = !string.IsNullOrEmpty(ProblemType);
        DisplayProblemName = !string.IsNullOrEmpty(ProblemName);
        DisplayEvaluator = !string.IsNullOrEmpty(Evaluator);
      }

      public bool DisplayProblemType { get; set; }
      public string ProblemType { get; set; }
      public bool DisplayProblemName { get; set; }
      public string ProblemName { get; set; }
      public bool DisplayEvaluator { get; set; }
      public string Evaluator { get; set; }

      public bool Match(IRun run) {
        return GetStringValueOrEmpty(run, "Problem Type") == ProblemType
               && GetStringValueOrEmpty(run, "Problem Name") == ProblemName
               && GetStringValueOrEmpty(run, "Evaluator") == Evaluator;
      }

      private string GetStringValueOrEmpty(IRun run, string key) {
        return run.Parameters.ContainsKey(key) ? ((StringValue)run.Parameters[key]).Value : string.Empty;
      }

      public override bool Equals(object obj) {
        var other = obj as RunCollectionIteratedSamplingView.ProblemDescription;
        if (other == null) return false;
        return ProblemType == other.ProblemType
               && ProblemName == other.ProblemName
               && Evaluator == other.Evaluator;
      }

      public override int GetHashCode() {
        return ProblemType.GetHashCode() ^ ProblemName.GetHashCode() ^ Evaluator.GetHashCode();
      }

      public override string ToString() {
        return string.Join("  --  ", new[] {
          (DisplayProblemType ? ProblemType : string.Empty),
          (DisplayProblemName ? ProblemName : string.Empty),
          (DisplayEvaluator ? Evaluator : string.Empty) }.Where(x => !string.IsNullOrEmpty(x)));
      }
    }
  }
}