# source:branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/CurveAnalysis.cs@15713

Last change on this file since 15713 was 14691, checked in by abeham, 5 years ago

#2457: working on identification of problem instances

File size: 3.5 KB
Line
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5namespace HeuristicLab.Analysis.FitnessLandscape {
6  public static class CurveAnalysis<T> {
7    public static CurveAnalysisResult GetCharacteristics(List<List<Tuple<T, double>>> trajectories, Func<T, T, double> distFunc) {
8      trajectories = trajectories.Where(x => x.Count > 5).ToList();
9      var f1 = trajectories.Select(path => ApproximateDerivative(path, distFunc).ToList()).ToList();
10      var f2 = f1.Select(d1 => ApproximateDerivative(d1, distFunc).ToList()).ToList();
11
12      var sharpness = f1.Average(x => x.Average(y => Math.Abs(y.Item2)));//f2.Average(x => Area(x, distFunc));
13      var bumpiness = 0.0;
14      var flatness = 0.0;
15
16      for (var p = 0; p < f2.Count; p++) {
17        if (f2[p].Count <= 2) continue;
18        var bump = 0;
19        var flat = 0;
20        for (var i = 0; i < f2[p].Count - 1; i++) {
21          if ((f2[p][i].Item2 > 0 && f2[p][i + 1].Item2 < 0) || (f2[p][i].Item2 < 0 && f2[p][i + 1].Item2 > 0)) {
22            bump++;
23          } else if (f2[p][i].Item2 == 0) {
24            flat++;
25          }
26        }
27        bumpiness += bump / (f2[p].Count - 1.0);
28        flatness += flat / (f2[p].Count - 1.0);
29      }
30      bumpiness /= f2.Count;
31      flatness /= f2.Count;
32      return new CurveAnalysisResult(sharpness, bumpiness, flatness);
33    }
34
35    private static double Area(IEnumerable<Tuple<T, double>> path, Func<T, T, double> distFunc) {
36      var iter = path.GetEnumerator();
37      if (!iter.MoveNext()) return 0.0;
38      var area = 0.0;
39      var prev = iter.Current;
40      while (iter.MoveNext()) {
41        area += TrapezoidArea(prev, iter.Current, distFunc);
42        prev = iter.Current;
43      }
44      return area;
45    }
46
47    private static double TrapezoidArea(Tuple<T, double> a, Tuple<T, double> b, Func<T, T, double> distFunc) {
48      var area = 0.0;
49      var dist = distFunc(a.Item1, b.Item1);
50      if ((a.Item2 <= 0 && b.Item2 <= 0) || (a.Item2 >= 0 && b.Item2 >= 0))
51        area += dist * (Math.Abs(a.Item2) + Math.Abs(b.Item2)) / 2.0;
52      else {
53        var k = (b.Item2 - a.Item2) / dist;
54        var d = a.Item2;
55        var x = -d / k;
56        area += Math.Abs(x * a.Item2 / 2.0);
57        area += Math.Abs((dist - x) * b.Item2 / 2.0);
58      }
59      return area;
60    }
61
62    private static IEnumerable<Tuple<T, double>> ApproximateDerivative(IEnumerable<Tuple<T, double>> data, Func<T, T, double> distFunc) {
63      Tuple<T, double> prev = null, prev2 = null;
64      foreach (var d in data) {
65        if (prev == null) {
66          prev = d;
67          continue;
68        }
69        if (prev2 == null) {
70          prev2 = prev;
71          prev = d;
72          continue;
73        }
74        var dist = distFunc(prev2.Item1, d.Item1);
75        yield return Tuple.Create(prev.Item1, (d.Item2 - prev2.Item2) / dist);
76        prev2 = prev;
77        prev = d;
78      }
79    }
80  }
81
82  public class CurveAnalysisResult {
83    public double Sharpness { get; private set; }
84    public double Bumpiness { get; private set; }
85    public double Flatness { get; private set; }
86
87    public string[] GetNames() {
88      return new[] { "Sharpness", "Bumpiness", "Flatness" };
89    }
90
91    public double[] GetValues() {
92      return new[] { Sharpness, Bumpiness, Flatness };
93    }
94
95    public CurveAnalysisResult(double sharpness, double bumpiness, double flatness) {
96      Sharpness = sharpness;
97      Bumpiness = bumpiness;
98      Flatness = flatness;
99    }
100  }
101}
Note: See TracBrowser for help on using the repository browser.