Changeset 17099

Timestamp:

07/07/19 23:45:15 (5 years ago)

Author:

mkommend

Message:

#2950: Merged 16979, 16980, 16983 into stable.

Location:

stable

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisBuildingBlockAnalyzer.cs (deleted)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs (modified) (8 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (1 diff)

stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs

@@ -1 @@
-using System;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2019 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;
-
+using HEAL.Attic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -8 +29 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Parameters;
-using HEAL.Attic;
 using HeuristicLab.Random;
 using static HeuristicLab.Problems.DataAnalysis.Symbolic.SymbolicExpressionHashExtensions;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  [Item("DiversityCrossover", "Simple crossover operator prioritizing internal nodes according to the given probability.")]
+  [Item("DiversityCrossover", "Simple crossover operator preventing swap between subtrees with the same hash value.")]
   [StorableType("ED35B0D9-9704-4D32-B10B-8F9870E76781")]
   public sealed class SymbolicDataAnalysisExpressionDiversityPreservingCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
@@ -20 +40 @@
     private const string WindowingParameterName = "Windowing";
     private const string ProportionalSamplingParameterName = "ProportionalSampling";
+    private const string StrictHashingParameterName = "StrictHashing";
 
     private static readonly Func<byte[], ulong> hashFunction = HashUtil.JSHash;
@@ -35 +56 @@
       get { return (IValueLookupParameter<BoolValue>)Parameters[ProportionalSamplingParameterName]; }
     }
+
+    public IFixedValueParameter<BoolValue> StrictHashingParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[StrictHashingParameterName]; }
+    }
     #endregion
 
@@ -49 +74 @@
       get { return ProportionalSamplingParameter.ActualValue; }
     }
+
+    bool StrictHashing {
+      get { return StrictHashingParameter.Value.Value; }
+    }
     #endregion
+
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      if (!Parameters.ContainsKey(StrictHashingParameterName)) {
+        Parameters.Add(new FixedValueParameter<BoolValue>(StrictHashingParameterName, "Use strict hashing when calculating subtree hash values."));
+      }
+    }
 
     public SymbolicDataAnalysisExpressionDiversityPreservingCrossover() {
@@ -56 +93 @@
       Parameters.Add(new ValueLookupParameter<BoolValue>(WindowingParameterName, "Use proportional sampling with windowing for cutpoint selection.", new BoolValue(false)));
       Parameters.Add(new ValueLookupParameter<BoolValue>(ProportionalSamplingParameterName, "Select cutpoints proportionally using probabilities as weights instead of randomly.", new BoolValue(true)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(StrictHashingParameterName, "Use strict hashing when calculating subtree hash values."));
     }
 
@@ -72 +110 @@
     }
 
-    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, double internalCrossoverPointProbability, int maxLength, int maxDepth, bool windowing, bool proportionalSampling = false) {
-      var leafCrossoverPointProbability = 1 - internalCrossoverPointProbability;
-
-      var nodes0 = ActualRoot(parent0).MakeNodes().Sort(hashFunction);
-      var nodes1 = ActualRoot(parent1).MakeNodes().Sort(hashFunction);
+    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, double internalCrossoverPointProbability, int maxLength, int maxDepth, bool windowing, bool proportionalSampling = false, bool strictHashing = false) {
+      var nodes0 = ActualRoot(parent0).MakeNodes(strictHashing).Sort(hashFunction);
+      var nodes1 = ActualRoot(parent1).MakeNodes(strictHashing).Sort(hashFunction);
 
       IList<HashNode<ISymbolicExpressionTreeNode>> sampled0;
@@ -126 +162 @@
       var proportionalSampling = ProportionalSampling.Value;
 
-      return Cross(random, parent0, parent1, internalCrossoverPointProbability, maxLength, maxDepth, windowing, proportionalSampling);
+      return Cross(random, parent0, parent1, internalCrossoverPointProbability, maxLength, maxDepth, windowing, proportionalSampling, StrictHashing);
     }
 

stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs

@@ -21 +21 @@
 
 using System;
-using System.Collections.Generic;
+using System.Linq;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
@@ -38 +38 @@
       public SimplifyAction Simplify;
 
-      public IComparer<T> Comparer;
+      //public IComparer<T> Comparer;
 
       public bool IsLeaf => Arity == 0;
 
-      public HashNode(IComparer<T> comparer) {
-        Comparer = comparer;
-      }
-
-      private HashNode() { }
+      //public HashNode(IComparer<T> comparer) {
+      //  Comparer = comparer;
+      //}
+
+      //public HashNode() { }
 
       public int CompareTo(HashNode<T> other) {
-        var res = Comparer.Compare(Data, other.Data);
-        return res == 0 ? CalculatedHashValue.CompareTo(other.CalculatedHashValue) : res;
+        return CalculatedHashValue.CompareTo(other.CalculatedHashValue);
       }
 
@@ -103 +102 @@
 
     public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
-      var reduced = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
-
-      for (int i = 0; i < reduced.Length; ++i) {
-        var node = reduced[i];
-        if (node.IsLeaf) {
-          continue;
-        }
-        node.Simplify?.Invoke(ref reduced, i);
-      }
-      // detect if anything was simplified
-      var count = 0;
-      foreach (var node in reduced) {
-        if (!node.Enabled) { ++count; }
-      }
-      if (count == 0) {
-        return reduced;
-      }
-
-      var simplified = new HashNode<T>[reduced.Length - count];
-      int j = 0;
-      foreach (var node in reduced) {
-        if (node.Enabled) {
-          simplified[j++] = node;
-        }
-      }
-      return simplified.UpdateNodeSizes().Reduce().Sort(hashFunction);
+      bool simplified = false;
+      nodes = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
+      do {
+        if (simplified) {
+          simplified = false;
+          nodes = nodes.Where(x => x.Enabled).ToArray().UpdateNodeSizes().Reduce().Sort(hashFunction);
+        }
+
+        for (int i = 0; i < nodes.Length; ++i) {
+          var node = nodes[i];
+          if (node.IsLeaf) {
+            continue;
+          }
+          node.Simplify?.Invoke(ref nodes, i);
+          for (int j = i - node.Size; j < i; ++j) {
+            // detect if anything was simplified
+            if (!nodes[j].Enabled) {
+              simplified = true;
+              break;
+            }
+          }
+        }
+      } while (simplified);
+      return nodes.UpdateNodeSizes().Sort(hashFunction);
     }
 
@@ -207 +204 @@
     }
 
-    private static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
+    public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
       int count = 0;
       for (int i = 0; i < nodes.Length; ++i) {

stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs

@@ -38 +38 @@
     private static readonly Constant constant = new Constant();
 
-    private static readonly ISymbolicExpressionTreeNodeComparer comparer = new SymbolicExpressionTreeNodeComparer();
     private static ISymbolicExpressionTreeNode ActualRoot(this ISymbolicExpressionTree tree) => tree.Root.GetSubtree(0).GetSubtree(0);
 
@@ -74 +73 @@
       }
       var hash = (ulong)name.GetHashCode();
-      var hashNode = new HashNode<ISymbolicExpressionTreeNode>(comparer) {
+      var hashNode = new HashNode<ISymbolicExpressionTreeNode> {
         Data = node,
         Arity = node.SubtreeCount,

stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -137 +137 @@
   <ItemGroup>
     <Compile Include="Analyzers\SymbolicDataAnalysisBottomUpDiversityAnalyzer.cs" />
-    <Compile Include="Analyzers\SymbolicDataAnalysisBuildingBlockAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectivePruningAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveValidationParetoBestSolutionAnalyzer.cs" />