Changeset 2675

Timestamp:

01/22/10 16:12:26 (15 years ago)

Author:

gkronber

Message:

Implemented a fix in TreeGardener for #836 (Initial population doesn't contain all functions in combination with SimpleFunctionLibraryInjector). Added test cases for SimpleFunctionLibraryInjector. Changed code for calculation of minTreeHeight and minTreeSize in FunctionBase

Location:

trunk/sources

Files:

• HeuristicLab.GP.StructureIdentification/3.3/FunctionLibraryInjectors/SimpleFunctionLibraryInjector.cs (modified) (4 diffs)
• HeuristicLab.GP.Tests/HeuristicLab.GP.Tests.csproj (modified) (1 diff)
• HeuristicLab.GP.Tests/SimpleFunctionLibraryTest.cs (added)
• HeuristicLab.GP/3.3/BaseClasses/FunctionBase.cs (modified) (4 diffs)
• HeuristicLab.GP/3.3/TreeGardener.cs (modified) (4 diffs)

trunk/sources/HeuristicLab.GP.StructureIdentification/3.3/FunctionLibraryInjectors/SimpleFunctionLibraryInjector.cs

@@ -67 +67 @@
 
     protected override FunctionLibrary CreateFunctionLibrary() {
+      return Create(
+        GetVariableValue<BoolData>(DIFFERENTIALS_ALLOWED, null, false).Data,
+        minTimeOffset,
+        maxTimeOffset);
+    }
+
+    public static FunctionLibrary Create(bool differentialAllowed, int minTimeOffset, int maxTimeOffset) {
       FunctionLibrary functionLibrary = new FunctionLibrary();
 
@@ -85 +92 @@
 
       List<IFunction> valueNodes = new List<IFunction>();
-      ConditionalAddFunction(DIFFERENTIALS_ALLOWED, differential, valueNodes);
+      if (differentialAllowed) valueNodes.Add(differential);
       valueNodes.Add(variable);
       valueNodes.Add(constant);
@@ -122 +129 @@
       SetAllowedSubOperators(tangens, valueNodes);
 
-      ConditionalAddOperator(DIFFERENTIALS_ALLOWED, functionLibrary, differential);
+      if (differentialAllowed) functionLibrary.AddFunction(differential);
 
       allFunctions.ForEach(x => functionLibrary.AddFunction(x));
@@ -131 +138 @@
       return functionLibrary;
     }
-
-    private void ConditionalAddFunction(string condName, IFunction fun, List<IFunction> list) {
-      if (GetVariableValue<BoolData>(condName, null, false).Data) list.Add(fun);
-    }
-
-    private void ConditionalAddOperator(string condName, FunctionLibrary functionLib, IFunction op) {
-      if (GetVariableValue<BoolData>(condName, null, false).Data) functionLib.AddFunction(op);
-    }
   }
 }

trunk/sources/HeuristicLab.GP.Tests/HeuristicLab.GP.Tests.csproj

@@ -63 +63 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="SimpleFunctionLibraryTest.cs" />
     <Compile Include="NetworkFunctionLibraryTest.cs" />
     <Compile Include="HL3TreeEvaluatorTest.cs" />

trunk/sources/HeuristicLab.GP/3.3/BaseClasses/FunctionBase.cs

@@ -27 +27 @@
 using System.Diagnostics;
 using HeuristicLab.GP.Interfaces;
+using System.Linq;
 
 namespace HeuristicLab.GP {
@@ -72 +73 @@
       get {
         if (minTreeSize <= 0) RecalculateMinimalTreeSize();
+        Debug.Assert(minTreeSize > 0);
         return minTreeSize;
       }
@@ -79 +81 @@
       get {
         if (minTreeHeight <= 0) RecalculateMinimalTreeHeight();
+        Debug.Assert(minTreeHeight > 0);
         return minTreeHeight;
       }
@@ -130 +133 @@
 
     private void RecalculateMinimalTreeSize() {
-      minTreeSize = int.MaxValue;
-      int sum = 1;
-      int minSize = int.MaxValue;
-      for (int i = 0; i < MinSubTrees; i++) {
-        foreach (IFunction subFun in GetAllowedSubFunctions(i)) {
-          minSize = Math.Min(minSize, subFun.MinTreeSize);
-        }
-        sum += minSize;
-      }
-      minTreeSize = sum;
+      if (MinSubTrees == 0) minTreeSize = 1;
+      else {
+        minTreeSize = int.MaxValue; // prevent infinite recursion
+        minTreeSize = 1 + (from slot in Enumerable.Range(0, MinSubTrees)
+                           let minForSlot = (from function in GetAllowedSubFunctions(slot)
+                                             where function != this
+                                             select function.MinTreeSize).Min()
+                           select minForSlot).Sum();
+      }
     }
 
     private void RecalculateMinimalTreeHeight() {
-      minTreeHeight = int.MaxValue;
-      int height = 0;
-      int minHeight = int.MaxValue;
-      for (int i = 0; i < MinSubTrees; i++) {
-        foreach (IFunction subFun in GetAllowedSubFunctions(i)) {
-          minHeight = Math.Min(minHeight, subFun.MinTreeHeight);
-        }
-        height = Math.Max(height, minHeight);
-      }
-      minTreeHeight = height + 1;
+      if (MinSubTrees == 0) minTreeHeight = 1;
+      else {
+        minTreeHeight = int.MaxValue;
+        minTreeHeight = 1 + (from slot in Enumerable.Range(0, MinSubTrees)
+                             let minForSlot = (from function in GetAllowedSubFunctions(slot)
+                                               where function != this
+                                               select function.MinTreeHeight).Min()
+                             select minForSlot).Max();
+      }
     }
 

trunk/sources/HeuristicLab.GP/3.3/TreeGardener.cs

@@ -120 +120 @@
           int a = (int)nextExtension[1];
           int d = (int)nextExtension[2];
-          if (d == maxDepth) {
+          if (d + parent.Function.MinTreeHeight >= maxDepth) {
             parent.RemoveSubTree(a);
             IFunctionTree branch = CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1);
@@ -127 +127 @@
             totalListMinSize -= branch.GetSize();
           } else {
-            IFunction selectedFunction = TreeGardener.RandomSelect(random, GetAllowedSubFunctions(parent.Function, a).Where(
-              f => IsRecursiveExpansionPossible(f) && f.MinTreeHeight + (d - 1) <= maxDepth).ToArray());
+            var allowedSubFunctions = from f in GetAllowedSubFunctions(parent.Function, a)
+                                      where f.MinTreeHeight + (d - 1) < maxDepth
+                                      where IsRecursiveExpansionPossible(f) ||
+                                            totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow
+                                                                                         // terminals or terminal-branches
+                                      select f;
+            IFunction selectedFunction = TreeGardener.RandomSelect(random, allowedSubFunctions.ToList());
             IFunctionTree newTree = selectedFunction.GetTreeNode();
             parent.RemoveSubTree(a);
@@ -146 +151 @@
               list.Add(new object[] { newTree, i, d + 1 });
             }
-            totalListMinSize += newTree.Function.MinTreeSize - 1;
+            totalListMinSize += newTree.Function.MinTreeSize;
           }
         }
@@ -164 +169 @@
     }
 
-    private bool IsRecursiveExpansionPossible(IFunction parent) {
-      return FindCycle(parent, new Stack<IFunction>());
+    private bool IsRecursiveExpansionPossible(IFunction function) {
+      return FindCycle(function, new Stack<IFunction>());
     }
 
     private Dictionary<IFunction, bool> inCycle = new Dictionary<IFunction, bool>();
-    private bool FindCycle(IFunction parent, Stack<IFunction> parentChain) {
-      if (inCycle.ContainsKey(parent)) {
-        return inCycle[parent];
-      } else if (IsTerminal(parent)) {
-        inCycle[parent] = false;
+    private bool FindCycle(IFunction function, Stack<IFunction> functionChain) {
+      if (inCycle.ContainsKey(function)) {
+        return inCycle[function];
+      } else if (IsTerminal(function)) {
+        inCycle[function] = false;
         return false;
-      } else if (parentChain.Contains(parent)) {
-        inCycle[parent] = true;
+      } else if (functionChain.Contains(function)) {
+        inCycle[function] = true;
         return true;
       } else {
-        parentChain.Push(parent);
+        functionChain.Push(function);
         bool result = false;
         // all slot indexes
-        for (int i = 0; i < parent.MaxSubTrees; i++) {
-          foreach (IFunction subFunction in GetAllowedSubFunctions(parent, i)) {
-            result |= FindCycle(subFunction, parentChain);
+        for (int i = 0; i < function.MaxSubTrees; i++) {
+          foreach (IFunction subFunction in GetAllowedSubFunctions(function, i)) {
+            result |= FindCycle(subFunction, functionChain);
           }
         }
 
-        parentChain.Pop();
-        inCycle[parent] = result;
+        functionChain.Pop();
+        inCycle[function] = result;
         return result;
       }