Changeset 16137 for branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis

Timestamp:

09/12/18 15:12:29 (6 years ago)

Author:

abeham

Message:

#2457:

• Restructured FLA plugin (moved files between folders, added common base classes)
• Fixed AC1 in QAPDirectedWalk (ouch!)
• Changed PartialInformationContent to be in range [0;1]
• Added unit test for information analysis
• Refactored information analysis and discard ability to use more symbols than 2 as shapes

Location:

branches/2457_ExpertSystem

Files:

• . (modified) (1 prop)
• HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis/InformationAnalysis.cs (modified) (5 diffs)
• HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis/InformationAnalyzer.cs (modified) (2 diffs)
• HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis/UniqueThresholdCalculator.cs (deleted)

branches/2457_ExpertSystem

@@ -5 +5 @@
 .gitignore
 .vs
+packages

@@ -5 +5 @@
 .gitignore
 .vs
+packages

branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis/InformationAnalysis.cs

@@ -38 +38 @@
 
     public List<double> InformationContent { get; private set; }
+    public List<double> SymmetricInformationContent { get; private set; }
     public List<double> PartialInformationContent { get; private set; }
     public List<double> DensityBasinInformation { get; private set; }
+    public List<double> SymmetricDensityBasinInformation { get; private set; }
     public List<double> TotalEntropy { get; private set; }
+    public List<double> SymmetricTotalEntropy { get; private set; }
     public List<double> QualityDelta { get; private set; }
     public double InformationStability { get; private set; }
@@ -46 +49 @@
     public int Diversity { get; private set; }
     public Peak PeakInformationContent { get; private set; }
-    public Peak PeakPartialInformationContent { get; private set; }
+    public Peak PeakSymmetricInformationContent { get; private set; }
     public Peak PeakDensityBasinInformation { get; private set; }
+    public Peak PeakSymmetricDensityBasinInformation { get; private set; }
     public Peak PeakTotalEntropy { get; private set; }
-
-    public InformationAnalysis(IList<double> qualities, int nQuantiles, int shapeSize) {
-      InformationContent = new List<double>();
-      PartialInformationContent = new List<double>();
-      DensityBasinInformation = new List<double>();
-      TotalEntropy = new List<double>();
-      QualityDelta = new List<double>();
-      if (shapeSize < 1)
-        throw new ArgumentException("Shape size must be at least 1 (better 2)");
+    public Peak PeakSymmetricTotalEntropy { get; private set; }
+
+    public InformationAnalysis(IList<double> qualities, int nQuantiles = 20) {
+      InformationContent = new List<double>(nQuantiles);
+      SymmetricInformationContent = new List<double>(nQuantiles);
+      PartialInformationContent = new List<double>(nQuantiles);
+      DensityBasinInformation = new List<double>(nQuantiles);
+      SymmetricDensityBasinInformation = new List<double>(nQuantiles);
+      TotalEntropy = new List<double>(nQuantiles);
+      SymmetricTotalEntropy = new List<double>(nQuantiles);
+      QualityDelta = new List<double>(nQuantiles);
       if (qualities.Count > 1)
-        PerformAnalysis(qualities, nQuantiles, shapeSize);
-    }
-
-    private void PerformAnalysis(IList<double> qualities, int nQuantiles, int shapeSize) {
+        PerformAnalysis(qualities, nQuantiles);
+    }
+
+    private void PerformAnalysis(IList<double> qualities, int nQuantiles) {
       var differences = Differences(qualities).ToList();
       InformationStability = differences.Select(Math.Abs).Max();
@@ -80 +86 @@
           PartialInformationContent.DuplicateLast();
         } else {
-          var slopes = Slopes(eps, differences).ToList();
-          var shapes = Shapes(shapeSize, slopes).ToList();
-          var shapeCounts = CountShapes(shapes);
+          var slopes = ToSlopes(eps, differences).ToList();
+          var shapes = ToShapes(slopes).ToList();
+          var symmetricShapes = shapes.Select(x => Shape.GetSymmetric(x)).ToList();
+
+          var shapeFreqs = GetFrequencies(shapes);
+          var symShapeFreqs = GetFrequencies(symmetricShapes);
+
+          foreach (var symShape in Shape.Symmetric.Where(x => x.Sum > 0)) {
+            if (symShapeFreqs.TryGetValue(symShape, out var freq)) {
+              symShapeFreqs[symShape] = freq / 2;
+            }
+          }
           QualityDelta.Add(eps);
-          InformationContent.Add(CalculateEntropy(Shape.GetAll(shapeSize, Shape.Form.NonUni), shapeCounts, shapes.Count));
-          DensityBasinInformation.Add(CalculateEntropy(Shape.GetAll(shapeSize, Shape.Form.Uni), shapeCounts, shapes.Count));
-          TotalEntropy.Add(CalculateEntropy(Shape.GetAll(shapeSize, Shape.Form.Any), shapeCounts, shapes.Count));
+
+          InformationContent.Add(CalculateEntropy(shapeFreqs, Shape.NonUniform.ToList(), shapes.Count));
+          SymmetricInformationContent.Add(CalculateEntropy(symShapeFreqs, Shape.SymmetricNonUniform.ToList(), symmetricShapes.Count));
+
+          DensityBasinInformation.Add(CalculateEntropy(shapeFreqs, Shape.Uniform.ToList(), shapes.Count));
+          SymmetricDensityBasinInformation.Add(CalculateEntropy(symShapeFreqs, Shape.SymmetricUniform.ToList(), symmetricShapes.Count));
+
+          TotalEntropy.Add(CalculateEntropy(shapeFreqs, Shape.All.ToList(), shapes.Count));
+          SymmetricTotalEntropy.Add(CalculateEntropy(symShapeFreqs, Shape.Symmetric.ToList(), symmetricShapes.Count));
+
           PartialInformationContent.Add(CalculatePartialInformationContent(eps, differences));
         }
       }
       PeakInformationContent = GetPeak(QualityDelta, InformationContent);
+      PeakSymmetricInformationContent = GetPeak(QualityDelta, SymmetricInformationContent);
       PeakDensityBasinInformation = GetPeak(QualityDelta, DensityBasinInformation);
-      PeakPartialInformationContent = GetPeak(QualityDelta, PartialInformationContent);
+      PeakSymmetricDensityBasinInformation = GetPeak(QualityDelta, SymmetricDensityBasinInformation);
       PeakTotalEntropy = GetPeak(QualityDelta, TotalEntropy);
+      PeakSymmetricTotalEntropy = GetPeak(QualityDelta, SymmetricTotalEntropy);
     }
 
@@ -107 +131 @@
     }
 
-    public class Shape : IEnumerable<Slope>, IComparable<Shape> {
-
-      #region types, fields and properties
-      public enum Form { Uni, NonUni, Any }
-
-      private readonly Slope[] slopes;
-
-      private static readonly Dictionary<Tuple<Form, int>, IList<Shape>> SHAPES =
-        new Dictionary<Tuple<Form, int>, IList<Shape>>();
-      #endregion
-
-      public Shape(IEnumerable<Slope> slopes) {
-        this.slopes = slopes.ToArray();
-      }
-
-      #region static methods
-
-      public static Shape Get(params Slope[] slopes) {
-        return new Shape(slopes);
-      }
-
-      public static IList<Shape> GetAll(int size, Form type) {
-        var key = Tuple.Create(type, size);
-        IList<Shape> allShapes;
-        if (!SHAPES.TryGetValue(key, out allShapes)) {
-          allShapes = CreateAll(size, type).ToList();
-          SHAPES[key] = allShapes;
+    public class Shape {
+      private static readonly Shape[] s = new Shape[] {
+        new Shape() { First = Slope.Down, Second = Slope.Down }, // 0
+        new Shape() { First = Slope.Down, Second = Slope.Flat }, // 1
+        new Shape() { First = Slope.Down, Second = Slope.Up   }, // 2
+        new Shape() { First = Slope.Flat, Second = Slope.Down }, // 3
+        new Shape() { First = Slope.Flat, Second = Slope.Flat }, // 4
+        new Shape() { First = Slope.Flat, Second = Slope.Up   }, // 5
+        new Shape() { First = Slope.Up,   Second = Slope.Down }, // 6
+        new Shape() { First = Slope.Up,   Second = Slope.Flat }, // 7
+        new Shape() { First = Slope.Up,   Second = Slope.Up   }, // 8
+      };
+      public static IEnumerable<Shape> All { get { return s; } }
+      public static IEnumerable<Shape> Uniform { get { return All.Where(x => x.First == x.Second); } }
+      public static IEnumerable<Shape> NonUniform { get { return All.Where(x => x.First != x.Second); } }
+      public static IEnumerable<Shape> Symmetric { get { return All.Where(x => x.Sum >= 0); } }
+      public static IEnumerable<Shape> SymmetricUniform { get { return Uniform.Where(x => x.First != Slope.Down); } }
+      public static IEnumerable<Shape> SymmetricNonUniform { get { return NonUniform.Where(x => x.Sum >= 0); } }
+
+      public Slope First { get; private set; }
+      public Slope Second { get; private set; }
+
+      internal int Sum { get { return (int)First + (int)Second; } }
+
+      public IEnumerable<Slope> Slopes {
+        get {
+          yield return First;
+          yield return Second;
         }
-        return allShapes;
-      }
-
-      private static IEnumerable<Shape> CreateAll(int size, Form type) {
-        if (size == 0) {
-          yield return Get();
-        } else {
-          foreach (var s in CreateAll(size - 1, type)) {
-            foreach (var s2 in s.ExtendAll(type))
-              yield return s2;
-          }
-        }
-      }
-      #endregion
-
-      private Shape Extend(Slope s) {
-        return new Shape(slopes.Concat(new[] { s }));
-      }
-
-      private IEnumerable<Shape> ExtendAll(Form t) {
-        if (Length == 0 || t == Form.Any) {
-          yield return Extend(Slope.Up);
-          yield return Extend(Slope.Flat);
-          yield return Extend(Slope.Down);
-        } else if (t == Form.Uni) {
-          yield return Extend(slopes[0]);
-        } else if (t == Form.NonUni) {
-          if (slopes.Last() != Slope.Up) yield return Extend(Slope.Up);
-          if (slopes.Last() != Slope.Flat) yield return Extend(Slope.Flat);
-          if (slopes.Last() != Slope.Down) yield return Extend(Slope.Down);
-        }
-      }
-
-      public int Length {
-        get { return slopes.Length; }
-      }
-
-      public Slope this[int i] {
-        get { return slopes[i]; }
-      }
-
-      #region IEnumerable Members
-      public IEnumerator<Slope> GetEnumerator() {
-        return (IEnumerator<Slope>)slopes.GetEnumerator();
-      }
-      System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
-        return GetEnumerator();
-      }
-      #endregion
-
-      #region IComparable Members
-
-      public int CompareTo(Shape other) {
-        if (other.Length < Length)
-          return -1;
-        if (other.Length > Length)
-          return 1;
-        for (var i = 0; i < Length; i++) {
-          var d = slopes[i].CompareTo(other.slopes[i]);
-          if (d != 0)
-            return d;
-        }
-        return 0;
-      }
-      public override bool Equals(object obj) {
-        var s = obj as Shape;
-        if (s == null) return false;
-        return CompareTo(s) == 0;
-      }
-      public override int GetHashCode() {
-        return slopes.Aggregate(0, (a, s) => a * 3 + ((int)s + 1)).GetHashCode();
-      }
-
-      #endregion
-
-      private string asString;
+      }
+
+      private Shape() {
+
+      }
+
+      public static Shape Get(Slope first, Slope second) {
+        var a = 1 + (int)first; var b = 1 + (int)second;
+        return s[a * 3 + b];
+      }
+
+      public static Shape GetSymmetric(Shape shape) {
+        if (shape.Sum >= 0) return shape;
+        if (shape.Sum == -2) return s[8]; // both are Slope.Down
+        if (shape.First == Slope.Down) return s[5];
+        return s[7]; // shape.Second == Slope.Down
+      }
+
       public override string ToString() {
-        return asString ?? (asString = string.Join("", slopes.Select(s => (s == Slope.Down ? "\\" : (s == Slope.Up ? "/" : "-")))));
-      }
-    }
-
-    private static IEnumerable<Slope> Slopes(double eps, IEnumerable<double> differences) {
+        return string.Join("", Slopes.Select(s => (s == Slope.Down ? "\\" : (s == Slope.Up ? "/" : "-"))));
+      }
+    }
+
+    
+
+    private static IEnumerable<Slope> ToSlopes(double eps, IEnumerable<double> differences) {
       return differences.Select(d => (d > eps ? Slope.Up : (d < -eps ? Slope.Down : Slope.Flat)));
     }
 
-    private static IEnumerable<Shape> Shapes(int size, IEnumerable<Slope> slopes) {
-      var q = new Queue<Slope>();
-      foreach (var s in slopes) {
-        q.Enqueue(s);
-        if (q.Count < size) continue;
-        yield return new Shape(q);
-        q.Dequeue();
-      }
-    }
-
-    private static double CalculateEntropy(IList<Shape> shapes, Dictionary<Shape, int> shapeCounts, int totalNShapes) {
-      return shapes.Aggregate(0.0, (current, s) => current - Entropy(shapeCounts.GetValueOrDefault(s, 0), totalNShapes, shapes.Count));
+    private static IEnumerable<Shape> ToShapes(IEnumerable<Slope> slopes) {
+      var iter = slopes.GetEnumerator();
+      if (!iter.MoveNext()) yield break;
+      var prev = iter.Current;
+      while (iter.MoveNext()) {
+        var cur = iter.Current;
+        yield return Shape.Get(prev, cur);
+        prev = cur;
+      }
+    }
+
+    private static double CalculateEntropy(Dictionary<Shape, int> shapeCounts, ICollection<Shape> shapeTypes, int totalShapes) {
+      return shapeTypes.Where(x => shapeCounts.ContainsKey(x))
+        .Aggregate(0.0, (current, s) => current - Entropy(shapeCounts[s], totalShapes, shapeTypes.Count));
     }
 
     private static double CalculatePartialInformationContent(double eps, ICollection<double> differences) {
-      int slope = 0;
-      int nPeaks = 0;
-      foreach (var d in differences) {
+      var iter = differences.GetEnumerator();
+      if (!iter.MoveNext()) return 0;
+
+      var slope = iter.Current < -eps ? -1 : (iter.Current > eps ? 1 : 0);
+      var nPeaks = Math.Abs(slope);
+      var count = 1;
+      while (iter.MoveNext()) {
+        var d = iter.Current;
         if (d > eps) {
           if (slope < 0) nPeaks++;
@@ -245 +221 @@
           slope = -1;
         }
-      }
-      return 1.0 * nPeaks / differences.Count;
-    }
-
-    private static Dictionary<Shape, int> CountShapes(IEnumerable<Shape> shapes) {
-      var shapeCounts = new Dictionary<Shape, int>();
-      foreach (var group in shapes.GroupBy(s => s))
-        shapeCounts[group.Key] = group.Count();
-      return shapeCounts;
+        count++;
+      }
+      return nPeaks / (double)count;
+    }
+
+    private static Dictionary<Shape, int> GetFrequencies(IEnumerable<Shape> shapes) {
+      return shapes.GroupBy(x => x).ToDictionary(x => x.Key, x => x.Count());
     }
 
     private static double Entropy(int count, int total, int nCases) {
-      if (count == 0)
-        return 0;
-      double freq = 1.0 * count / total;
+      if (count == 0) return 0;
+      var freq = 1.0 * count / total;
       return freq * Math.Log(freq, nCases);
     }

branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis/InformationAnalyzer.cs

@@ -91 +91 @@
 
       Parameters.Add(new ValueLookupParameter<IntValue>("NQuantiles", "The number of delta quantiles to display", new IntValue(20)));
-      Parameters.Add(new ValueLookupParameter<IntValue>("ShapeSize", "The number of slopes to consider as shapes.", new IntValue(2)));
 
       Parameters.Add(new LookupParameter<DoubleValue>("InformationContent", "The information content H(0) at eps = 0"));
@@ -118 +117 @@
 
       var nQuantiles = NQuantilesParameter.ActualValue.Value;
-      var shapeSize = ShapeSizeParameter.ActualValue.Value;
       var results = ResultsParameter.ActualValue;
 
-      var analysis = new InformationAnalysis(qualities, nQuantiles, shapeSize);
+      var analysis = new InformationAnalysis(qualities, nQuantiles);
       var ic = new DoubleValue(analysis.InformationContent.FirstOrDefault());
       InformationContentParameter.ActualValue = ic;

@@ -5 +5 @@
 .gitignore
 .vs
+packages