Changeset 8216

Timestamp:

07/04/12 18:00:00 (12 years ago)

Author:

jkarder

Message:

#1886:

• added SchemaAnalyzer
• added BrokenInteritanceSchemaAnalyzer

Location:

branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior/3.3

Files:

• Analyzers/BrokenInteritanceSchemaAnalyzer.cs (added)
• Analyzers/BuildingBlockAnalyzer.cs (modified) (7 diffs)
• Analyzers/GenealogyAnalyzer.cs (modified) (1 diff)
• Analyzers/SchemaAnalyzer.cs (added)
• HeuristicLab.Analysis.AlgorithmBehavior-3.3.csproj (modified) (1 diff)

branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior/3.3/Analyzers/BuildingBlockAnalyzer.cs

@@ -29 +29 @@
 
 namespace HeuristicLab.Analysis.AlgorithmBehavior {
+  using System;
   using System.Collections.Generic;
   using HeuristicLab.Data;
@@ -37 +38 @@
   /// An operator that analyzes building blocks.
   /// </summary>
-  [Item("BuildingBlockAnalyzer", "An operator that tracks the genealogy of every individual.")]
+  [Item("BuildingBlockAnalyzer", "An operator that analyzes building blocks.")]
   [StorableClass]
   public sealed class BuildingBlockAnalyzer : SingleSuccessorOperator, IAnalyzer {
@@ -44 +45 @@
     private const string PopulationGraphResultParameterName = "PopulationGraph";
     private const string BuildingBlockSchemaMatrixParameterName = "BuildingBlockSchemaMatrix";
+    private const string BrokenInteritanceSchemaOccurrenceName = "BrokenInteritanceSchemaOccurrenceMatrix";
+    private const string UnbrokenInteritanceSchemaOccurrenceName = "UnbrokenInteritanceSchemaOccurrence";
     private const string BuildingBlockPatternMatrixParameterName = "BuildingBlockPatternMatrix";
 
@@ -100 +103 @@
             var categories = new int[3];
             categories[0] = ExploreGlobalSchemaOccurrence(graph, schema);
-            categories[1] = ExploreBrokenInteritanceSchemaOccurrence(graph, schema);
-            categories[2] = ExploreUnbrokenInteritanceSchemaOccurrence(graph, schema);
+            categories[1] = -1;
+            categories[2] = -1;
             schemataMatrix.Add(schema, categories);
           }
@@ -109 +112 @@
       // order schemas according to their global occurrence count
       var sortedSchemataMatrix = schemataMatrix.OrderByDescending(x => x.Value[0]).ToDictionary(x => x.Key, x => x.Value);
-
-      var stringMatrix = new StringMatrix(sortedSchemataMatrix.Keys.Count, 4);
+      IList<string> rowNames = new List<string>();
+      var schemataStringMatrix = new StringMatrix(sortedSchemataMatrix.Keys.Count, 3);
       for (int i = 0; i < sortedSchemataMatrix.Keys.Count; i++) {
         var element = sortedSchemataMatrix.ElementAt(i);
-        stringMatrix[i, 0] = new Permutation(PermutationTypes.RelativeUndirected, element.Key).ToString();
+        rowNames.Add(new Permutation(PermutationTypes.RelativeUndirected, element.Key).ToString());
         for (int j = 0; j < element.Value.Count(); j++) {
-          stringMatrix[i, j + 1] = element.Value[j].ToString();
-        }
-      }
-      stringMatrix.ColumnNames = new[] { "Schema", "GlobalSchemaOccurrence", "BrokenInteritanceSchemaOccurrence", "UnbrokenInteritanceSchemaOccurrence" };
-
-      Results.Add(new Result(BuildingBlockSchemaMatrixParameterName, stringMatrix));
+          schemataStringMatrix[i, j] = element.Value[j].ToString();
+        }
+      }
+      schemataStringMatrix.RowNames = rowNames;
+      schemataStringMatrix.ColumnNames = new[] { "GlobalSchemaOccurrence", "<unused>", "<unused>" };
+      Results.Add(new Result(BuildingBlockSchemaMatrixParameterName, schemataStringMatrix));
+
+      var brokenInteritanceSchemaOccurrenceMatrix = new StringMatrix(sortedSchemataMatrix.Keys.Count, generationZero.Count());
+      IList<string> brokenRowNames = new List<string>();
+      IList<string> brokenColumnNames = new List<string>();
+      for (int i = 0; i < sortedSchemataMatrix.Keys.Count; i++) {
+        var entry = sortedSchemataMatrix.ElementAt(i);
+        brokenRowNames.Add(new Permutation(PermutationTypes.RelativeUndirected, entry.Key).ToString());
+        for (int j = 0; j < generationZero.Count(); j++) {
+          var individual = generationZero.ElementAt(j);
+          if (i == 0) brokenColumnNames.Add(((Permutation)individual.Data).ToString());
+          brokenInteritanceSchemaOccurrenceMatrix[i, j] = CalculateBrokenInheritanceOccurrences(entry.Key, individual).ToString();
+        }
+      }
+      brokenInteritanceSchemaOccurrenceMatrix.RowNames = brokenRowNames;
+      brokenInteritanceSchemaOccurrenceMatrix.ColumnNames = brokenColumnNames;
+      Results.Add(new Result(BrokenInteritanceSchemaOccurrenceName, brokenInteritanceSchemaOccurrenceMatrix));
+
+      var unbrokenInteritanceSchemaOccurrenceMatrix = new StringMatrix(sortedSchemataMatrix.Keys.Count, generationZero.Count());
+      IList<string> unbrokenRowNames = new List<string>();
+      IList<string> unbrokenColumnNames = new List<string>();
+      for (int i = 0; i < sortedSchemataMatrix.Keys.Count; i++) {
+        var entry = sortedSchemataMatrix.ElementAt(i);
+        unbrokenRowNames.Add(new Permutation(PermutationTypes.RelativeUndirected, entry.Key).ToString());
+        for (int j = 0; j < generationZero.Count(); j++) {
+          var individual = generationZero.ElementAt(j);
+          if (i == 0) unbrokenColumnNames.Add(((Permutation)individual.Data).ToString());
+          unbrokenInteritanceSchemaOccurrenceMatrix[i, j] = CalculateUnbrokenInheritanceOccurrences(entry.Key, individual).ToString();
+        }
+      }
+      unbrokenInteritanceSchemaOccurrenceMatrix.RowNames = unbrokenRowNames;
+      unbrokenInteritanceSchemaOccurrenceMatrix.ColumnNames = brokenColumnNames;
+      Results.Add(new Result(UnbrokenInteritanceSchemaOccurrenceName, unbrokenInteritanceSchemaOccurrenceMatrix));
 
       return base.Apply();
+    }
+
+    private int CalculateBrokenInheritanceOccurrences(int[] schema, GenealogyGraphNode individual) {
+      // TODO
+      return -1;
+    }
+
+    private int CalculateUnbrokenInheritanceOccurrences(int[] schema, GenealogyGraphNode individual) {
+      var filteredDescendants = individual.Descendants().Where(x => IsMatch(schema, ((Permutation)x.Data).ToArray()));
+      return filteredDescendants.Any() ? (int)filteredDescendants.Max(x => x.Rank) : 0;
     }
 
@@ -130 +175 @@
         if (IsSubtour(schema, (Permutation)individual.Data)) occurrences++;
       return occurrences;
-    }
-
-    private int ExploreBrokenInteritanceSchemaOccurrence(GenealogyGraph<Permutation> graph, int[] schema) {
-      // TODO
-      return 0;
-    }
-
-    private int ExploreUnbrokenInteritanceSchemaOccurrence(GenealogyGraph<Permutation> graph, int[] schema) {
-      // TODO
-      return 0;
     }
 
@@ -171 +206 @@
     }
 
+    // attention: brute force matching
+    // should be replaced with KMP, BM or RK
+    private bool IsMatch(int[] pattern, int[] tour) {
+      bool match = false;
+      for (int i = 0; i <= tour.Length - pattern.Length && !match; i++) {
+        for (int j = 0; j < pattern.Length && (match = pattern[j] == tour[i + j] || pattern[j] == -1); j++) ;
+      }
+      return match;
+    }
+
+    private IList<int[]> GenerateWildcardSchemata(int[] schema) {
+      string formatString = "{0:d" + schema.Length + "}";
+      var combs = new List<bool[]>();
+      string comb = string.Empty;
+
+      // create all desired wildcard combinations
+      int i = 0;
+      int wildcardCount = 0; // first wildcard combination contains no wildcards
+      while (wildcardCount < schema.Length) {
+        if (wildcardCount > schema.Length / 8 && wildcardCount < schema.Length / 2)
+          combs.Add(comb.Select(x => x == '1').ToArray()); // '1' becomes true which indicates a wildcard
+        wildcardCount = (comb = string.Format(formatString, Convert.ToString(++i, 2))).Count(x => x == '1');
+      }
+
+      // create all desired wildcard instances
+      var wildcardSchemata = new List<int[]>();
+      foreach (var c in combs) {
+        wildcardSchemata.Add(schema.Select((x, index) => c[index] ? -1 : x).ToArray()); // -1 is a wildcard in the schema
+      }
+
+      return wildcardSchemata;
+    }
+
+
     private class SchemaEqualityComparer : EqualityComparer<int[]> {
       public override bool Equals(int[] x, int[] y) {

branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior/3.3/Analyzers/GenealogyAnalyzer.cs

@@ -202 +202 @@
           foreach (var parent in parents) {
             if (GlobalTraceMap.ContainsKey(parent)) {
-              // handle cycle
+              // handle mutation
               double quality = Evaluate(parent);
               var node = new GenealogyGraphNode(parent) { Quality = quality, Label = label, Rank = generation - 0.5 };

branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior/3.3/HeuristicLab.Analysis.AlgorithmBehavior-3.3.csproj

@@ -75 +75 @@
   <ItemGroup>
     <Compile Include="Analyzers\BuildingBlockAnalyzer.cs" />
+    <Compile Include="Analyzers\BrokenInteritanceSchemaAnalyzer.cs" />
+    <Compile Include="Analyzers\SchemaAnalyzer.cs" />
     <Compile Include="Analyzers\GenealogyAnalyzer.cs" />
     <Compile Include="GenealogyGraph.cs" />