Changeset 16096 for branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/CurveAnalysis.cs

Timestamp:

08/29/18 18:16:05 (6 years ago)

Author:

abeham

Message:

#2457:

• Changed calculation of correlation length (using limit introduced Hordijk 1996)
• Changed RuggednessCalculator (no more a HL item)
• Added additional, information-analysis-based features for directed walks
• Added generic DirectedWalk algorithm (as described in thesis)
• Made OneSizeInstanceProvider parametrizable
• Adapted program for analyzing problem instance reidentification

File:

• branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/CurveAnalysis.cs (modified) (4 diffs)

branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/CurveAnalysis.cs

@@ -1 @@
-using System;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2018 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.Linq;
@@ -7 +28 @@
     public static CurveAnalysisResult GetCharacteristics(List<List<Tuple<T, double>>> trajectories, Func<T, T, double> distFunc) {
       trajectories = trajectories.Where(x => x.Count > 5).ToList();
+      var symbols = GetSymbols(trajectories);
       var f1 = trajectories.Select(path => ApproximateDerivative(path, distFunc).ToList()).ToList();
       var f2 = f1.Select(d1 => ApproximateDerivative(d1, distFunc).ToList()).ToList();
 
-      var sharpness = f1.Average(x => x.Average(y => Math.Abs(y.Item2)));//f2.Average(x => Area(x, distFunc));
+      var sharpness = f1.Average(x => x.Average(y => Math.Abs(y.Item2)));
       var bumpiness = 0.0;
       var flatness = 0.0;
-
+      var count = 0;
       for (var p = 0; p < f2.Count; p++) {
         if (f2[p].Count <= 2) continue;
+        count++;
         var bump = 0;
         var flat = 0;
@@ -28 +51 @@
         flatness += flat / (f2[p].Count - 1.0);
       }
-      bumpiness /= f2.Count;
-      flatness /= f2.Count;
-      return new CurveAnalysisResult(sharpness, bumpiness, flatness);
+      bumpiness /= count;
+      flatness /= count;
+      var per = new[] { 25, 50, 75 };
+      return new CurveAnalysisResult(sharpness, bumpiness, flatness,
+        per.Select(p => symbols.Downward.GetPercentileOrDefault(p, 0)).ToArray(),
+        per.Select(p => symbols.Neutral.GetPercentileOrDefault(p, 0)).ToArray(),
+        per.Select(p => symbols.Upward.GetPercentileOrDefault(p, 0)).ToArray());
     }
 
-    private static double Area(IEnumerable<Tuple<T, double>> path, Func<T, T, double> distFunc) {
-      var iter = path.GetEnumerator();
-      if (!iter.MoveNext()) return 0.0;
-      var area = 0.0;
-      var prev = iter.Current;
-      while (iter.MoveNext()) {
-        area += TrapezoidArea(prev, iter.Current, distFunc);
-        prev = iter.Current;
+    private static Symbols GetSymbols(List<List<Tuple<T, double>>> trajectories) {
+      var sym = new Symbols();
+      foreach (var t in trajectories) {
+        var prev = t[0];
+        for (var i = 1; i < t.Count; i++) {
+          sym.Add(i / (double)t.Count, t[i].Item2, prev.Item2);
+          prev = t[i];
+        }
       }
-      return area;
-    }
-
-    private static double TrapezoidArea(Tuple<T, double> a, Tuple<T, double> b, Func<T, T, double> distFunc) {
-      var area = 0.0;
-      var dist = distFunc(a.Item1, b.Item1);
-      if ((a.Item2 <= 0 && b.Item2 <= 0) || (a.Item2 >= 0 && b.Item2 >= 0))
-        area += dist * (Math.Abs(a.Item2) + Math.Abs(b.Item2)) / 2.0;
-      else {
-        var k = (b.Item2 - a.Item2) / dist;
-        var d = a.Item2;
-        var x = -d / k;
-        area += Math.Abs(x * a.Item2 / 2.0);
-        area += Math.Abs((dist - x) * b.Item2 / 2.0);
-      }
-      return area;
+      return sym;
     }
 
@@ -80 +92 @@
   }
 
+  public enum CurveAnalysisFeature { Sharpness, Bumpiness, Flatness,
+                                     DownQ1, DownQ2, DownQ3,
+                                     NeutQ1, NeutQ2, NeutQ3,
+                                     UpQ1, UpQ2, UpQ3 }
+
   public class CurveAnalysisResult {
-    public double Sharpness { get; private set; }
-    public double Bumpiness { get; private set; }
-    public double Flatness { get; private set; }
+    private Dictionary<CurveAnalysisFeature, double> results = new Dictionary<CurveAnalysisFeature, double>();
 
-    public string[] GetNames() {
-      return new[] { "Sharpness", "Bumpiness", "Flatness" };
+    public double GetValue(CurveAnalysisFeature name) {
+      return results[name];
+    }
+
+    public static IEnumerable<CurveAnalysisFeature> AllFeatures {
+      get { return Enum.GetValues(typeof(CurveAnalysisFeature)).Cast<CurveAnalysisFeature>(); }
     }
 
     public double[] GetValues() {
-      return new[] { Sharpness, Bumpiness, Flatness };
+      return AllFeatures.Select(x => results[x]).ToArray();
     }
 
-    public CurveAnalysisResult(double sharpness, double bumpiness, double flatness) {
-      Sharpness = sharpness;
-      Bumpiness = bumpiness;
-      Flatness = flatness;
+    public CurveAnalysisResult(double sharpness, double bumpiness, double flatness, double[] down, double[] neut, double[] up) {
+      foreach (var v in AllFeatures.Zip(new[] { sharpness, bumpiness, flatness }.Concat(down).Concat(neut).Concat(up), (n, v) => Tuple.Create(n, v))) {
+        results[v.Item1] = v.Item2;
+      }
+    }
+  }
+
+  public class Symbols {
+    public Statistics Downward { get; } = new Statistics();
+    public Statistics Neutral { get; } = new Statistics();
+    public Statistics Upward { get; } = new Statistics();
+
+    public void Add(double step, double fit, double prev) {
+      if (fit < prev) Downward.Add(step);
+      else if (fit > prev) Upward.Add(step);
+      else Neutral.Add(step);
+    }
+  }
+
+  public sealed class Statistics {
+    private List<double> values = new List<double>();
+
+    public int Count { get { return values.Count; } }
+
+    public double Min { get; private set; }
+    public double Max { get; private set; }
+    public double Total { get; private set; }
+    public double Mean { get; private set; }
+    public double StdDev { get { return Math.Sqrt(Variance); } }
+    public double Variance { get { return Count > 0 ? variance / Count : 0.0; } }
+    
+    private double variance;
+    private bool sorted = false;
+    
+    public double GetPercentileOrDefault(int p, double @default = default(double)) {
+      if (p < 0 || p > 100) throw new ArgumentOutOfRangeException(nameof(p), p, "Must be in range [0;100]");
+      SortIfNecessary();
+      if (Count == 0) return @default;
+      else if (Count == 1) return values[0];
+      if (p == 100) return values[Count - 1];
+
+      var x = p / 100.0 * (Count - 1);
+      var inte = (int)x;
+      var frac = x - inte;
+
+      return values[inte] + frac * (values[inte + 1] - values[inte]);
+    }
+
+    public void Add(double value) {
+      sorted = false;
+      values.Add(value);
+
+      if (Count == 1) {
+        Min = Max = Mean = Total = value;
+      } else {
+        if (value < Min) Min = value;
+        if (value > Max) Max = value;
+
+        Total += value;
+        var oldMean = Mean;
+        Mean = oldMean + (value - oldMean) / Count;
+        variance = variance + (value - oldMean) * (value - Mean);
+      }
+    }
+
+    public void AddRange(IEnumerable<double> values) {
+      foreach (var v in values) Add(v);
+    }
+
+    private void SortIfNecessary() {
+      if (!sorted) {
+        values.Sort();
+        sorted = true;
+      }
     }
   }