source: branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/UnderstandingSolutionsView.cs @ 13743

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2016 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 HeuristicLab.Analysis;
using HeuristicLab.Analysis.QualityAnalysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.MainForm;
using HeuristicLab.Optimization;
using HeuristicLab.OptimizationExpertSystem.Common;
using HeuristicLab.Random;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
using System.Windows.Forms.DataVisualization.Charting;

namespace HeuristicLab.OptimizationExpertSystem {
  [View("Understanding Solutions")]
  [Content(typeof(KnowledgeCenter), IsDefaultView = false)]
  public partial class UnderstandingSolutionsView : KnowledgeCenterViewBase {
    protected virtual bool SuppressEvents { get; set; }

    public UnderstandingSolutionsView() {
      InitializeComponent();
      solutionNetworkProjectionComboBox.SelectedIndex = 0;
    }

    protected override void OnContentChanged() {
      base.OnContentChanged();
      UpdateSimilarityCalculators();
      UpdateNamesComboboxes();
      UpdateSolutionVisualization();
    }

    protected override void OnProblemChanged() {
      base.OnProblemInstancesChanged();
      UpdateSimilarityCalculators();
      UpdateNamesComboboxes();
      UpdateSolutionVisualization();
    }

    protected override void OnProblemSolutionsChanged() {
      base.OnProblemSolutionsChanged();
      UpdateNamesComboboxes();
      UpdateSolutionVisualization();
    }

    protected override void OnSolutionSeedingPoolChanged() {
      base.OnSolutionSeedingPoolChanged();
      UpdateSolutionNetworkAnalysis(similarityComboBox.SelectedItem as ISolutionSimilarityCalculator, (string)solutionNetworkProjectionComboBox.SelectedItem);
    }

    private void UpdateSimilarityCalculators() {
      var selected = (ISolutionSimilarityCalculator)(similarityComboBox.SelectedIndex >= 0 ? similarityComboBox.SelectedItem : null);
      similarityComboBox.Items.Clear();

      if (Content == null || Content.Problem == null) return;

      foreach (var calc in Content.Problem.Operators.OfType<ISolutionSimilarityCalculator>()) {
        similarityComboBox.Items.Add(calc);
        if (selected != null && calc.ItemName == selected.ItemName) similarityComboBox.SelectedItem = calc;
      }
      if (selected == null && similarityComboBox.Items.Count > 0)
        similarityComboBox.SelectedIndex = 0;
    }

    private void UpdateNamesComboboxes() {
      var selectedSolutionName = solutionNameComboBox.SelectedIndex >= 0 ? (string)solutionNameComboBox.SelectedItem : string.Empty;

      solutionNameComboBox.Items.Clear();
      if (Content == null) return;
      var solutionNames = Content.Problem.Solutions.Select(x => x.Solution).OfType<IScope>().SelectMany(x => x.Variables);

      foreach (var sn in solutionNames.GroupBy(x => x.Name).OrderBy(x => x.Key)) {
        solutionNameComboBox.Items.Add(sn.Key);
        // either it was previously selected, or the variable value is defined in the HeuristicLab.Encodings sub-namespace
        if (sn.Key == selectedSolutionName || (string.IsNullOrEmpty(selectedSolutionName) && sn.All(x => x.Value != null && x.Value.GetType().FullName.StartsWith("HeuristicLab.Encodings."))))
          solutionNameComboBox.SelectedItem = sn.Key;
      }
    }
    
    public void UpdateSolutionVisualization() {
      if (InvokeRequired) { Invoke((Action)UpdateSolutionVisualization); return;  }
      var qualityName = Content.Problem.Problem.Evaluator.QualityParameter.ActualName;
      UpdateSolutionQualityAnalysis(qualityName);
      if (similarityComboBox.SelectedIndex >= 0) {
        var calculator = (ISolutionSimilarityCalculator)similarityComboBox.SelectedItem;
        UpdateSolutionDiversityAnalysis(calculator);
        UpdateSolutionFdcAnalysis(calculator, fdcBetweenBestCheckBox.Checked);
        UpdateSolutionLengthScaleAnalysis(calculator);
        UpdateSolutionNetworkAnalysis(calculator, (string)solutionNetworkProjectionComboBox.SelectedItem);
      } else {
        solutionsDiversityViewHost.Content = null;
        solutionsFdcViewHost.Content = null;
        solutionsLengthScaleViewHost.Content = null;
        solutionsNetworkChart.Series.First().Points.Clear();
      }
    }

    private void UpdateSolutionQualityAnalysis(string qualityName) {
      var dt = solutionsQualityViewHost.Content as DataTable;
      if (dt == null) {
        dt = QualityDistributionAnalyzer.PrepareTable(qualityName);
        dt.VisualProperties.Title = "Quality Distribution";
        solutionsQualityViewHost.Content = dt;
      }
      QualityDistributionAnalyzer.UpdateTable(dt, GetSolutionScopes().Select(x => GetQuality(x, qualityName) ?? double.NaN).Where(x => !double.IsNaN(x)));
    }

    private void UpdateSolutionDiversityAnalysis(ISolutionSimilarityCalculator calculator) {
      try {
        solutionsDiversityViewHost.Content = null;
        var solutionScopes = GetSolutionScopes();
        var similarities = new double[solutionScopes.Count, solutionScopes.Count];
        for (var i = 0; i < solutionScopes.Count; i++) {
          for (var j = 0; j < solutionScopes.Count; j++)
            similarities[i, j] = calculator.CalculateSolutionSimilarity(solutionScopes[i], solutionScopes[j]);
        }
        var hm = new HeatMap(similarities, "Solution Similarities", 0.0, 1.0);
        solutionsDiversityViewHost.Content = hm;
      } catch { }
    }

    private void UpdateSolutionFdcAnalysis(ISolutionSimilarityCalculator calculator, bool distanceToBest) {
      try {
        solutionsFdcViewHost.Content = null;
        fdcSpearmanLabel.Text = "-";
        fdcPearsonLabel.Text = "-";
        var solutionScopes = GetSolutionScopes();
        var points = new List<Point2D<double>>();
        if (distanceToBest) {
          var maximization = ((IValueParameter<BoolValue>)Content.Problem.MaximizationParameter).Value.Value;
          var bestSolutions = (maximization ? solutionScopes.MaxItems(x => GetQuality(x, calculator.QualityVariableName) ?? double.NegativeInfinity)
                                            : solutionScopes.MinItems(x => GetQuality(x, calculator.QualityVariableName) ?? double.PositiveInfinity)).ToList();
          foreach (var solScope in solutionScopes.Except(bestSolutions)) {
            var maxSimilarity = bestSolutions.Max(x => calculator.CalculateSolutionSimilarity(solScope, x));
            var qDiff = (GetQuality(solScope, calculator.QualityVariableName) ?? double.NaN)
                      - (GetQuality(bestSolutions[0], calculator.QualityVariableName) ?? double.NaN);
            points.Add(new Point2D<double>(Math.Abs(qDiff), 1.0 - maxSimilarity));
          }
        } else {
          for (int i = 0; i < solutionScopes.Count; i++) {
            for (int j = 0; j < solutionScopes.Count; j++) {
              if (i == j) continue;
              var qDiff = (GetQuality(solutionScopes[i], calculator.QualityVariableName) ?? double.NaN)
                          - (GetQuality(solutionScopes[j], calculator.QualityVariableName) ?? double.NaN);
              if (double.IsNaN(qDiff)) continue;
              points.Add(new Point2D<double>(Math.Abs(qDiff), 1.0 - calculator.CalculateSolutionSimilarity(solutionScopes[i], solutionScopes[j])));
            }
          }
        }
        var xs = points.Select(p => p.X).ToArray();
        var ys = points.Select(p => p.Y).ToArray();
        var scorr = alglib.spearmancorr2(xs, ys);
        var pcorr = alglib.pearsoncorr2(xs, ys);
        pcorr = pcorr * pcorr;
        fdcSpearmanLabel.Text = scorr.ToString("F2");
        fdcPearsonLabel.Text = pcorr.ToString("F2");

        var splot = new ScatterPlot("Fitness-Distance", "");
        splot.VisualProperties.XAxisTitle = "Absolute Fitness Difference";
        splot.VisualProperties.XAxisMinimumAuto = false;
        splot.VisualProperties.XAxisMinimumFixedValue = 0.0;
        splot.VisualProperties.YAxisTitle = "Solution Distance";
        splot.VisualProperties.YAxisMinimumAuto = false;
        splot.VisualProperties.YAxisMinimumFixedValue = 0.0;
        splot.VisualProperties.YAxisMaximumAuto = false;
        splot.VisualProperties.YAxisMaximumFixedValue = 1.0;
        var row = new ScatterPlotDataRow("Fdc", "", points);
        row.VisualProperties.PointSize = 10;
        row.VisualProperties.ShowRegressionLine = true;
        splot.Rows.Add(row);
        solutionsFdcViewHost.Content = splot;
      } catch { }
    }

    private void UpdateSolutionLengthScaleAnalysis(ISolutionSimilarityCalculator calculator) {
      try {
        solutionsLengthScaleViewHost.Content = null;
        var dt = solutionsLengthScaleViewHost.Content as DataTable;
        if (dt == null) {
          dt = QualityDistributionAnalyzer.PrepareTable("Length Scale");
          solutionsLengthScaleViewHost.Content = dt;
        }
        QualityDistributionAnalyzer.UpdateTable(dt, CalculateLengthScale(calculator));
      } catch {
        solutionsLengthScaleViewHost.Content = null;
      }
    }

    private IEnumerable<double> CalculateLengthScale(ISolutionSimilarityCalculator calculator) {
      var solutionScopes = GetSolutionScopes();
      for (var i = 0; i < solutionScopes.Count; i++) {
        for (var j = 0; j < solutionScopes.Count; j++) {
          if (i == j) continue;
          var sim = calculator.CalculateSolutionSimilarity(solutionScopes[i], solutionScopes[j]);
          if (sim.IsAlmost(0)) continue;
          var qDiff = (GetQuality(solutionScopes[i], calculator.QualityVariableName) ?? double.NaN)
                    - (GetQuality(solutionScopes[j], calculator.QualityVariableName) ?? double.NaN);
          if (!double.IsNaN(qDiff)) yield return Math.Abs(qDiff) / sim;
        }
      }
    }

    private void UpdateSolutionNetworkAnalysis(ISolutionSimilarityCalculator calculator, string projection) {
      var series = solutionsNetworkChart.Series["SolutionSeries"];
      var seedingSeries = solutionsNetworkChart.Series["SeedingSolutionSeries"];
      try {
        series.Points.Clear();
        seedingSeries.Points.Clear();
        var solutionScopes = GetSolutionScopes();
        var dissimilarities = new DoubleMatrix(solutionScopes.Count, solutionScopes.Count);
        for (var i = 0; i < solutionScopes.Count; i++) {
          for (var j = 0; j < solutionScopes.Count; j++) {
            if (i == j) continue;
            dissimilarities[i, j] = 1.0 - calculator.CalculateSolutionSimilarity(solutionScopes[i], solutionScopes[j]);
          }
        }
        DoubleMatrix coords = null;
        if (projection == "SOM")
          coords = Som(dissimilarities, new MersenneTwister(42), jittering: true);
        else coords = MultidimensionalScaling.KruskalShepard(dissimilarities);
        for (var i = 0; i < coords.Rows; i++) {
          var quality = GetQuality(solutionScopes[i], calculator.QualityVariableName) ?? double.NaN;
          var dataPoint = new DataPoint() {
            Name = (i + 1).ToString(),
            XValue = coords[i, 0],
            YValues = new[] {coords[i, 1], quality},
            Label = (i + 1) + ": " + quality,
            Tag = solutionScopes[i]
          };
          if (Content.SolutionSeedingPool.Contains(solutionScopes[i]) && Content.SolutionSeedingPool.ItemChecked(solutionScopes[i]))
            seedingSeries.Points.Add(dataPoint);
          else series.Points.Add(dataPoint);
        }
      } catch {
        // problems in calculating the similarity
        series.Points.Clear();
        seedingSeries.Points.Clear();
      }
    }

    private void SimilarityComboBoxOnSelectedIndexChanged(object sender, EventArgs e) {
      if (InvokeRequired) { Invoke((Action<object, EventArgs>)SimilarityComboBoxOnSelectedIndexChanged, sender, e); return; }
      var calculator = (ISolutionSimilarityCalculator)similarityComboBox.SelectedItem;
      if (calculator != null) {
        calculator.SolutionVariableName = (string)solutionNameComboBox.SelectedItem;
        calculator.QualityVariableName = Content.Problem.Problem.Evaluator.QualityParameter.ActualName;
      }
      UpdateSolutionDiversityAnalysis(calculator);
      UpdateSolutionFdcAnalysis(calculator, fdcBetweenBestCheckBox.Checked);
      UpdateSolutionLengthScaleAnalysis(calculator);
      UpdateSolutionNetworkAnalysis(calculator, (string)solutionNetworkProjectionComboBox.SelectedItem);
    }

    private void SolutionNameComboBoxOnSelectedIndexChanged(object sender, EventArgs e) {
      if (InvokeRequired) { Invoke((Action<object, EventArgs>)SolutionNameComboBoxOnSelectedIndexChanged, sender, e); return; }
      var calculator = (ISolutionSimilarityCalculator)similarityComboBox.SelectedItem;
      if (calculator != null) {
        calculator.SolutionVariableName = (string)solutionNameComboBox.SelectedItem;
        calculator.QualityVariableName = Content.Problem.Problem.Evaluator.QualityParameter.ActualName;
      }
      UpdateSolutionDiversityAnalysis(calculator);
      UpdateSolutionFdcAnalysis(calculator, fdcBetweenBestCheckBox.Checked);
      UpdateSolutionLengthScaleAnalysis(calculator);
      UpdateSolutionNetworkAnalysis(calculator, (string)solutionNetworkProjectionComboBox.SelectedItem);
    }

    private void FdcBetweenBestCheckBoxOnCheckedChanged(object sender, EventArgs e) {
      if (InvokeRequired) { Invoke((Action<object, EventArgs>)FdcBetweenBestCheckBoxOnCheckedChanged, sender, e); return; }
      UpdateSolutionFdcAnalysis((ISolutionSimilarityCalculator)similarityComboBox.SelectedItem, fdcBetweenBestCheckBox.Checked);
    }

    private void SolutionNetworkProjectionComboBoxOnSelectedIndexChanged(object sender, EventArgs e) {
      if (InvokeRequired) { Invoke((Action<object, EventArgs>)SolutionNetworkProjectionComboBoxOnSelectedIndexChanged, sender, e); return; }
      var calculator = (ISolutionSimilarityCalculator)similarityComboBox.SelectedItem;
      if (calculator != null) {
        calculator.SolutionVariableName = (string)solutionNameComboBox.SelectedItem;
        calculator.QualityVariableName = Content.Problem.Problem.Evaluator.QualityParameter.ActualName;
      }
      UpdateSolutionNetworkAnalysis(calculator, (string)solutionNetworkProjectionComboBox.SelectedItem);
    }

    private void SolutionsNetworkChartOnMouseClick(object sender, MouseEventArgs e) {
      var result = solutionsNetworkChart.HitTest(e.X, e.Y);
      if (result.ChartElementType == ChartElementType.DataPoint) {
        var point = (DataPoint)result.Object;
        var solutionScope = (IScope)point.Tag;
        if (!Content.SolutionSeedingPool.Contains(solutionScope)) return;
        Content.SolutionSeedingPool.SetItemCheckedState(solutionScope, !Content.SolutionSeedingPool.ItemChecked(solutionScope));
      }
    }

    private void SolutionsNetworkChartOnMouseDoubleClick(object sender, MouseEventArgs e) {
      var result = solutionsNetworkChart.HitTest(e.X, e.Y);
      if (result.ChartElementType == ChartElementType.DataPoint) {
        var point = (DataPoint)result.Object;
        var solutionScope = (IScope)point.Tag;
        MainForm.ShowContent(solutionScope, true);
      }
    }

    #region Helpers
    private List<IScope> GetSolutionScopes() {
      return Content.Problem.Solutions.Select(x => x.Solution).OfType<IScope>().ToList();
    } 

    private double? GetQuality(IScope scope, string qualityName) {
      IVariable v;
      if (!scope.Variables.TryGetValue(qualityName, out v)) return null;
      var dval = v.Value as DoubleValue;
      if (dval == null) return null;
      return dval.Value;
    }

    #region SOM projection
    /// <summary>
    /// This is the online algorithm described in
    /// Olteanu, M. and Villa-Vialaneix, N. 2015.
    /// On-line relational and multiple relational SOM.
    /// Neurocomputing 147, pp. 15-30.
    /// </summary>
    /// <param name="dissimilarities">The full NxN matrix containing all dissimilarities between N points.</param>
    /// <param name="random">The random number generator to use.</param>
    /// <param name="somSize">The length of a side of the SOM grid (there are somSize * somSize neurons).</param>
    /// <param name="iterations">The amount of iterations to perform in learning.</param>
    /// <param name="learningRate">The initial learning rate.</param>
    /// <param name="learningRadius">The initial learning radius.</param>
    /// <param name="jittering">If the final coordinates should be jittered slightly within the grid.</param>
    /// <returns>A matrix of coordinates having N rows and 2 columns.</returns>
    private DoubleMatrix Som(DoubleMatrix dissimilarities, IRandom random, int somSize = 5, int iterations = 100, double learningRate = double.NaN, double learningRadius = 5.0, bool jittering = true) {
      var K = somSize * somSize;
      var N = dissimilarities.Rows;
      if (double.IsNaN(learningRate)) learningRate = 1.0 / Math.Sqrt(2.0 * N);
      var fixedLearningRate = learningRate / 10.0;
      var varLearningRate = 9.0 * fixedLearningRate;
      Func<int, int, double> learningRateT = (maxIter, iter) => {
        return varLearningRate * ((maxIter - iter) / (double)maxIter) + fixedLearningRate;
      };
      Func<int, int> getX = (neuron) => neuron % somSize;
      Func<int, int> getY = (neuron) => neuron / somSize;
      Func<int, int, int, int, double> neighborhood = (maxIter, iter, k, bmu) => {
        var sigma = 1.0 * ((maxIter - iter) / (double)maxIter) + 0.0001;
        var xK = getX(k);
        var yK = getY(k);
        var xW = getX(bmu);
        var yW = getY(bmu);
        var d = (xK - xW) * (xK - xW) + (yK - yW) * (yK - yW);
        return Math.Exp(-d / (2.0 * sigma * sigma));
      };
      var alphas = Enumerable.Range(0, K).Select(k => Enumerable.Range(0, N).Select(_ => random.NextDouble()).ToArray()).ToArray();
      // normalize s.t. sum(alphas[k]) = 1
      for (var k = 0; k < K; k++) {
        var sum = alphas[k].Sum();
        for (var i = 0; i < alphas[k].Length; i++) alphas[k][i] /= sum;
      }
      var oldAlphas = alphas.Select(x => (double[])x.Clone()).ToArray();

      for (var iter = 0; iter < iterations; iter++) {
        var pointShuffle = Enumerable.Range(0, N).Shuffle(random).ToArray();
        for (var p = 0; p < N; p++) {
          var i = pointShuffle[p];
          var bmu = GetBestMatchingUnit(dissimilarities, alphas, i);

          for (var k = 0; k < K; k++) {
            for (var j = 0; j < N; j++) {
              alphas[k][j] = oldAlphas[k][j] + learningRateT(iterations, iter) * neighborhood(iterations, iter, k, bmu) * ((i == j ? 1.0 : 0.0) - oldAlphas[k][j]);
            }
          }
        }
        for (var k = 0; k < K; k++) {
          for (var j = 0; j < N; j++) {
            oldAlphas[k][j] = alphas[k][j];
          }
        }
      }

      var result = new DoubleMatrix(N, 2);
      for (var i = 0; i < N; i++) {
        var bmu = GetBestMatchingUnit(dissimilarities, alphas, i);
        if (!jittering) {
          result[i, 0] = getX(bmu);
          result[i, 1] = getY(bmu);
        } else {
          result[i, 0] = getX(bmu) + random.NextDouble() * 0.8;
          result[i, 1] = getY(bmu) + random.NextDouble() * 0.8;
        }
      }
      return result;
    }

    private int GetBestMatchingUnit(DoubleMatrix D, double[][] alphas, int i) {
      var bmu = -1;
      var minV = double.MaxValue;
      for (var k = 0; k < alphas.Length; k++) {
        var Daki = 0.0;
        var akDak = 0.0;
        for (var r = 0; r < D.Rows; r++) {
          var Dakr = 0.0;
          for (var s = 0; s < D.Rows; s++) {
            Dakr += D[r, s] * alphas[k][s];
          }
          if (r == i) Daki = Dakr;
          akDak += alphas[k][r] * Dakr;
        }
        var v = Daki - 0.5 * akDak;
        if (v < minV) {
          bmu = k;
          minV = v;
        }
      }
      return bmu;
    }
    #endregion

    private DoubleMatrix Mds(DoubleMatrix dissimilarities) {
      return MultidimensionalScaling.KruskalShepard(dissimilarities);
    }
    #endregion
  }
}