Changeset 13743

Timestamp:

04/06/16 12:00:09 (8 years ago)

Author:

abeham

Message:

#2457: adding relational SOM projection for solution network visualization

Location:

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3

Files:

• . (modified) (1 prop)
• HeuristicLab.OptimizationExpertSystem-3.3.csproj (modified) (1 diff)
• HeuristicLab.OptimizationExpertSystem-3.3.csproj.user (deleted)
• Views/UnderstandingSolutionsView.Designer.cs (modified) (8 diffs)
• Views/UnderstandingSolutionsView.cs (modified) (10 diffs)

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3

@@ -2 +2 @@
 obj
 Plugin.cs
+*.user

@@ -2 +2 @@
 obj
 Plugin.cs
+*.user

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/HeuristicLab.OptimizationExpertSystem-3.3.csproj

@@ -151 +151 @@
       <SpecificVersion>False</SpecificVersion>
       <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
+      <Private>False</Private>
+    </Reference>
+    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
       <Private>False</Private>
     </Reference>

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/UnderstandingSolutionsView.Designer.cs

@@ -62 +62 @@
       this.solutionsDiversityViewHost = new HeuristicLab.MainForm.WindowsForms.ViewHost();
       this.solutionsFdcTabPage = new System.Windows.Forms.TabPage();
+      this.fdcSpearmanLabel = new System.Windows.Forms.Label();
+      this.fdcPearsonLabel = new System.Windows.Forms.Label();
+      this.spearmansRankLabel = new System.Windows.Forms.Label();
+      this.pearsonsRSquaredLabel = new System.Windows.Forms.Label();
       this.fdcBetweenBestCheckBox = new System.Windows.Forms.CheckBox();
       this.solutionsFdcViewHost = new HeuristicLab.MainForm.WindowsForms.ViewHost();
       this.solutionsNetworkTabPage = new System.Windows.Forms.TabPage();
+      this.solutionNetworkProjectionLabel = new System.Windows.Forms.Label();
+      this.solutionNetworkProjectionComboBox = new System.Windows.Forms.ComboBox();
       this.solutionsNetworkChart = new HeuristicLab.Visualization.ChartControlsExtensions.EnhancedChart();
-      this.pearsonsRSquaredLabel = new System.Windows.Forms.Label();
-      this.fdcPearsonLabel = new System.Windows.Forms.Label();
-      this.spearmansRankLabel = new System.Windows.Forms.Label();
-      this.fdcSpearmanLabel = new System.Windows.Forms.Label();
       this.solutionsTabControl.SuspendLayout();
       this.solutionsQualityTabPage.SuspendLayout();
@@ -227 +229 @@
       this.solutionsFdcTabPage.UseVisualStyleBackColor = true;
       // 
+      // fdcSpearmanLabel
+      // 
+      this.fdcSpearmanLabel.AutoSize = true;
+      this.fdcSpearmanLabel.Location = new System.Drawing.Point(357, 7);
+      this.fdcSpearmanLabel.Name = "fdcSpearmanLabel";
+      this.fdcSpearmanLabel.Size = new System.Drawing.Size(10, 13);
+      this.fdcSpearmanLabel.TabIndex = 4;
+      this.fdcSpearmanLabel.Text = "-";
+      // 
+      // fdcPearsonLabel
+      // 
+      this.fdcPearsonLabel.AutoSize = true;
+      this.fdcPearsonLabel.Location = new System.Drawing.Point(512, 7);
+      this.fdcPearsonLabel.Name = "fdcPearsonLabel";
+      this.fdcPearsonLabel.Size = new System.Drawing.Size(10, 13);
+      this.fdcPearsonLabel.TabIndex = 4;
+      this.fdcPearsonLabel.Text = "-";
+      // 
+      // spearmansRankLabel
+      // 
+      this.spearmansRankLabel.AutoSize = true;
+      this.spearmansRankLabel.Location = new System.Drawing.Point(281, 7);
+      this.spearmansRankLabel.Name = "spearmansRankLabel";
+      this.spearmansRankLabel.Size = new System.Drawing.Size(74, 13);
+      this.spearmansRankLabel.TabIndex = 3;
+      this.spearmansRankLabel.Text = "Spearman\'s ρ:";
+      // 
+      // pearsonsRSquaredLabel
+      // 
+      this.pearsonsRSquaredLabel.AutoSize = true;
+      this.pearsonsRSquaredLabel.Location = new System.Drawing.Point(436, 7);
+      this.pearsonsRSquaredLabel.Name = "pearsonsRSquaredLabel";
+      this.pearsonsRSquaredLabel.Size = new System.Drawing.Size(65, 13);
+      this.pearsonsRSquaredLabel.TabIndex = 3;
+      this.pearsonsRSquaredLabel.Text = "Pearson\'s r²:";
+      // 
       // fdcBetweenBestCheckBox
       // 
@@ -256 +294 @@
       // solutionsNetworkTabPage
       // 
+      this.solutionsNetworkTabPage.Controls.Add(this.solutionNetworkProjectionLabel);
+      this.solutionsNetworkTabPage.Controls.Add(this.solutionNetworkProjectionComboBox);
       this.solutionsNetworkTabPage.Controls.Add(this.solutionsNetworkChart);
       this.solutionsNetworkTabPage.Location = new System.Drawing.Point(4, 22);
@@ -265 +305 @@
       this.solutionsNetworkTabPage.UseVisualStyleBackColor = true;
       // 
+      // solutionNetworkProjectionLabel
+      // 
+      this.solutionNetworkProjectionLabel.AutoSize = true;
+      this.solutionNetworkProjectionLabel.Location = new System.Drawing.Point(6, 9);
+      this.solutionNetworkProjectionLabel.Name = "solutionNetworkProjectionLabel";
+      this.solutionNetworkProjectionLabel.Size = new System.Drawing.Size(57, 13);
+      this.solutionNetworkProjectionLabel.TabIndex = 4;
+      this.solutionNetworkProjectionLabel.Text = "Projection:";
+      // 
+      // solutionNetworkProjectionComboBox
+      // 
+      this.solutionNetworkProjectionComboBox.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
+      this.solutionNetworkProjectionComboBox.FormattingEnabled = true;
+      this.solutionNetworkProjectionComboBox.Items.AddRange(new object[] {
+            "SOM",
+            "MDS"});
+      this.solutionNetworkProjectionComboBox.Location = new System.Drawing.Point(69, 6);
+      this.solutionNetworkProjectionComboBox.Name = "solutionNetworkProjectionComboBox";
+      this.solutionNetworkProjectionComboBox.Size = new System.Drawing.Size(180, 21);
+      this.solutionNetworkProjectionComboBox.TabIndex = 3;
+      this.solutionNetworkProjectionComboBox.SelectedIndexChanged += new System.EventHandler(this.SolutionNetworkProjectionComboBoxOnSelectedIndexChanged);
+      // 
       // solutionsNetworkChart
       // 
+      this.solutionsNetworkChart.Anchor = ((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) 
+            | System.Windows.Forms.AnchorStyles.Left) 
+            | System.Windows.Forms.AnchorStyles.Right)));
       chartArea1.AxisX.IsStartedFromZero = false;
       chartArea1.AxisX.LabelStyle.Enabled = false;
@@ -279 +344 @@
       chartArea1.Name = "SolutionsNetworkChartArea";
       this.solutionsNetworkChart.ChartAreas.Add(chartArea1);
-      this.solutionsNetworkChart.Dock = System.Windows.Forms.DockStyle.Fill;
       legend1.Enabled = false;
       legend1.Name = "Legend1";
       this.solutionsNetworkChart.Legends.Add(legend1);
-      this.solutionsNetworkChart.Location = new System.Drawing.Point(3, 3);
+      this.solutionsNetworkChart.Location = new System.Drawing.Point(3, 33);
       this.solutionsNetworkChart.Name = "solutionsNetworkChart";
       series1.ChartArea = "SolutionsNetworkChartArea";
@@ -303 +367 @@
       this.solutionsNetworkChart.Series.Add(series1);
       this.solutionsNetworkChart.Series.Add(series2);
-      this.solutionsNetworkChart.Size = new System.Drawing.Size(718, 446);
+      this.solutionsNetworkChart.Size = new System.Drawing.Size(718, 416);
       this.solutionsNetworkChart.TabIndex = 0;
       this.solutionsNetworkChart.Text = "enhancedChart1";
       this.solutionsNetworkChart.MouseClick += new System.Windows.Forms.MouseEventHandler(this.SolutionsNetworkChartOnMouseClick);
       this.solutionsNetworkChart.MouseDoubleClick += new System.Windows.Forms.MouseEventHandler(this.SolutionsNetworkChartOnMouseDoubleClick);
-      // 
-      // pearsonsRSquaredLabel
-      // 
-      this.pearsonsRSquaredLabel.AutoSize = true;
-      this.pearsonsRSquaredLabel.Location = new System.Drawing.Point(436, 7);
-      this.pearsonsRSquaredLabel.Name = "pearsonsRSquaredLabel";
-      this.pearsonsRSquaredLabel.Size = new System.Drawing.Size(65, 13);
-      this.pearsonsRSquaredLabel.TabIndex = 3;
-      this.pearsonsRSquaredLabel.Text = "Pearson\'s r²:";
-      // 
-      // fdcPearsonLabel
-      // 
-      this.fdcPearsonLabel.AutoSize = true;
-      this.fdcPearsonLabel.Location = new System.Drawing.Point(512, 7);
-      this.fdcPearsonLabel.Name = "fdcPearsonLabel";
-      this.fdcPearsonLabel.Size = new System.Drawing.Size(10, 13);
-      this.fdcPearsonLabel.TabIndex = 4;
-      this.fdcPearsonLabel.Text = "-";
-      // 
-      // spearmansRankLabel
-      // 
-      this.spearmansRankLabel.AutoSize = true;
-      this.spearmansRankLabel.Location = new System.Drawing.Point(281, 7);
-      this.spearmansRankLabel.Name = "spearmansRankLabel";
-      this.spearmansRankLabel.Size = new System.Drawing.Size(74, 13);
-      this.spearmansRankLabel.TabIndex = 3;
-      this.spearmansRankLabel.Text = "Spearman\'s ρ:";
-      // 
-      // fdcSpearmanLabel
-      // 
-      this.fdcSpearmanLabel.AutoSize = true;
-      this.fdcSpearmanLabel.Location = new System.Drawing.Point(357, 7);
-      this.fdcSpearmanLabel.Name = "fdcSpearmanLabel";
-      this.fdcSpearmanLabel.Size = new System.Drawing.Size(10, 13);
-      this.fdcSpearmanLabel.TabIndex = 4;
-      this.fdcSpearmanLabel.Text = "-";
       // 
       // UnderstandingSolutionsView
@@ -363 +391 @@
       this.solutionsFdcTabPage.PerformLayout();
       this.solutionsNetworkTabPage.ResumeLayout(false);
+      this.solutionsNetworkTabPage.PerformLayout();
       ((System.ComponentModel.ISupportInitialize)(this.solutionsNetworkChart)).EndInit();
       this.ResumeLayout(false);
@@ -391 +420 @@
     private System.Windows.Forms.Label fdcSpearmanLabel;
     private System.Windows.Forms.Label spearmansRankLabel;
+    private System.Windows.Forms.Label solutionNetworkProjectionLabel;
+    private System.Windows.Forms.ComboBox solutionNetworkProjectionComboBox;
   }
 }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/UnderstandingSolutionsView.cs

@@ -28 +28 @@
 using HeuristicLab.Optimization;
 using HeuristicLab.OptimizationExpertSystem.Common;
+using HeuristicLab.Random;
 using System;
 using System.Collections.Generic;
@@ -42 +43 @@
     public UnderstandingSolutionsView() {
       InitializeComponent();
+      solutionNetworkProjectionComboBox.SelectedIndex = 0;
     }
 
@@ -66 +68 @@
     protected override void OnSolutionSeedingPoolChanged() {
       base.OnSolutionSeedingPoolChanged();
-      UpdateSolutionNetworkAnalysis(similarityComboBox.SelectedItem as ISolutionSimilarityCalculator);
+      UpdateSolutionNetworkAnalysis(similarityComboBox.SelectedItem as ISolutionSimilarityCalculator, (string)solutionNetworkProjectionComboBox.SelectedItem);
     }
 
@@ -107 +109 @@
         UpdateSolutionFdcAnalysis(calculator, fdcBetweenBestCheckBox.Checked);
         UpdateSolutionLengthScaleAnalysis(calculator);
-        UpdateSolutionNetworkAnalysis(calculator);
+        UpdateSolutionNetworkAnalysis(calculator, (string)solutionNetworkProjectionComboBox.SelectedItem);
       } else {
         solutionsDiversityViewHost.Content = null;
@@ -221 +223 @@
     }
 
-    private void UpdateSolutionNetworkAnalysis(ISolutionSimilarityCalculator calculator) {
+    private void UpdateSolutionNetworkAnalysis(ISolutionSimilarityCalculator calculator, string projection) {
       var series = solutionsNetworkChart.Series["SolutionSeries"];
       var seedingSeries = solutionsNetworkChart.Series["SeedingSolutionSeries"];
@@ -235 +237 @@
           }
         }
-        var coords = MultidimensionalScaling.KruskalShepard(dissimilarities);
+        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;
@@ -266 +271 @@
       UpdateSolutionFdcAnalysis(calculator, fdcBetweenBestCheckBox.Checked);
       UpdateSolutionLengthScaleAnalysis(calculator);
-      UpdateSolutionNetworkAnalysis(calculator);
+      UpdateSolutionNetworkAnalysis(calculator, (string)solutionNetworkProjectionComboBox.SelectedItem);
     }
 
@@ -279 +284 @@
       UpdateSolutionFdcAnalysis(calculator, fdcBetweenBestCheckBox.Checked);
       UpdateSolutionLengthScaleAnalysis(calculator);
-      UpdateSolutionNetworkAnalysis(calculator);
+      UpdateSolutionNetworkAnalysis(calculator, (string)solutionNetworkProjectionComboBox.SelectedItem);
     }
 
@@ -285 +290 @@
       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);
     }
 
@@ -318 +333 @@
       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
   }

@@ -2 +2 @@
 obj
 Plugin.cs
+*.user